Mercurial > hg > Papers > 2015 > yuhi-master

changeset 63:3a35d13818e5

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
multicore cpu
author Yuhi TOMARI <yuhi@cr.ie.u-ryukyu.ac.jp>
date Wed, 18 Feb 2015 00:15:07 +0900
parents 17f33e4aa7ba
children 4c245ed4e61a
files paper/graffle/fsort_bsort.graffle paper/images/fsort_bsort.pdf slide/blank.html slide/graffle/.DS_Store slide/images/fsort_bsort.png slide/images/gpu_image.png slide/images/iterate.png
diffstat 7 files changed, 211 insertions(+), 43 deletions(-) [+]
line wrap: on
line diff
--- a/paper/graffle/fsort_bsort.graffle	Tue Feb 17 19:03:27 2015 +0900
+++ b/paper/graffle/fsort_bsort.graffle	Wed Feb 18 00:15:07 2015 +0900
@@ -58,7 +58,7 @@
 			<array>
 				<dict>
 					<key>Bounds</key>
-					<string>{{322.79717460743382, 569.84775184279226}, {30, 19}}</string>
+					<string>{{784.99085428309888, 123.7941319413849}, {30, 19}}</string>
 					<key>Class</key>
 					<string>ShapedGraphic</string>
 					<key>FitText</key>
@@ -115,7 +115,7 @@
 				</dict>
 				<dict>
 					<key>Bounds</key>
-					<string>{{322.95581328094931, 537.44725785986498}, {30.939228057861328, 91.215476989746094}}</string>
+					<string>{{785.14949295661438, 91.393637958457617}, {30.939228057861328, 91.215476989746094}}</string>
 					<key>Class</key>
 					<string>ShapedGraphic</string>
 					<key>ID</key>
@@ -209,7 +209,7 @@
 			<array>
 				<dict>
 					<key>Bounds</key>
-					<string>{{122.79716828473093, 569.84774378466523}, {30, 19}}</string>
+					<string>{{584.99084796039585, 123.79412388325787}, {30, 19}}</string>
 					<key>Class</key>
 					<string>ShapedGraphic</string>
 					<key>FitText</key>
@@ -266,7 +266,7 @@
 				</dict>
 				<dict>
 					<key>Bounds</key>
-					<string>{{122.95580695824646, 537.44724980173805}, {30.939228057861328, 91.215476989746094}}</string>
+					<string>{{585.14948663391135, 91.393629900330694}, {30.939228057861328, 91.215476989746094}}</string>
 					<key>Class</key>
 					<string>ShapedGraphic</string>
 					<key>ID</key>
@@ -808,7 +808,7 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{244.19890245811382, 458.1563533720003}, {32, 19}}</string>
+			<string>{{542.40944608096129, 251.93370962196823}, {32, 19}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>FitText</key>
@@ -875,8 +875,8 @@
 			<integer>379</integer>
 			<key>Points</key>
 			<array>
-				<string>{239.75000508626303, 487.7777777777776}</string>
-				<string>{239.84025531832702, 436.64604356553821}</string>
+				<string>{701.94368476192756, 209.92575699746388}</string>
+				<string>{453.09025531832697, 352.54524400499133}</string>
 			</array>
 			<key>Style</key>
 			<dict>
@@ -996,7 +996,7 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{26.500006569756408, 488.00873014661988}, {79.472221374511719, 21.333333969116211}}</string>
+			<string>{{488.69368624542096, 41.95511024521241}, {79.472221374511719, 21.333333969116211}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>ID</key>
@@ -1046,8 +1046,8 @@
 			<integer>368</integer>
 			<key>Points</key>
 			<array>
-				<string>{239.75001356336804, 604.38905334472679}</string>
-				<string>{239.75001356336804, 641.60905334472739}</string>
+				<string>{701.94369323903322, 158.33543344331946}</string>
+				<string>{701.94369323903322, 195.55543344331994}</string>
 			</array>
 			<key>Style</key>
 			<dict>
@@ -1066,7 +1066,7 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{39.249807569715728, 603.61000061035179}, {50, 38.999057769775391}}</string>
+			<string>{{501.44348724538014, 157.55638070894446}, {50, 38.999057769775391}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>FontInfo</key>
@@ -1124,7 +1124,7 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{89.250200483534101, 603.61000061035179}, {50, 39.000000000000007}}</string>
+			<string>{{551.44388015919901, 157.55638070894446}, {50, 39.000000000000007}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>FontInfo</key>
@@ -1178,7 +1178,7 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{139.25020048353412, 603.61000061035179}, {50, 39.000000000000007}}</string>
+			<string>{{601.44388015919901, 157.55638070894446}, {50, 39.000000000000007}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>FontInfo</key>
@@ -1232,7 +1232,7 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{189.25020048353406, 603.61000061035179}, {50, 39.000000000000007}}</string>
+			<string>{{651.44388015919901, 157.55638070894446}, {50, 39.000000000000007}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>FontInfo</key>
@@ -1286,7 +1286,7 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{239.25078794691296, 603.61000061035179}, {50, 39.000000000000007}}</string>
+			<string>{{701.44446762257814, 157.55638070894446}, {50, 39.000000000000007}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>ID</key>
@@ -1328,7 +1328,7 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{289.25078794691308, 603.61000061035179}, {50, 39.000000000000007}}</string>
+			<string>{{751.44446762257814, 157.55638070894446}, {50, 39.000000000000007}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>ID</key>
@@ -1370,7 +1370,7 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{339.25078794691308, 603.61000061035179}, {50, 39.000000000000007}}</string>
+			<string>{{801.44446762257792, 157.55638070894446}, {50, 39.000000000000007}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>ID</key>
@@ -1412,7 +1412,7 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{389.25078794691308, 603.61000061035179}, {50, 39.000000000000007}}</string>
+			<string>{{851.44446762257792, 157.55638070894446}, {50, 39.000000000000007}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>ID</key>
@@ -1459,8 +1459,8 @@
 			<integer>356</integer>
 			<key>Points</key>
 			<array>
-				<string>{239.75000593397351, 524.38999999999976}</string>
-				<string>{240.25000593397351, 561.61000000000024}</string>
+				<string>{701.94368560963869, 78.336380098592272}</string>
+				<string>{702.44368560963869, 115.55638009859294}</string>
 			</array>
 			<key>Style</key>
 			<dict>
@@ -1479,7 +1479,7 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{38.499613020155174, 523.49999999999977}, {50, 38.999057769775391}}</string>
+			<string>{{500.69329269581959, 77.446380098592286}, {50, 38.999057769775391}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>FontInfo</key>
@@ -1537,7 +1537,7 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{88.500005933973554, 523.49999999999977}, {50, 39.000000000000007}}</string>
+			<string>{{550.69368560963846, 77.446380098592286}, {50, 39.000000000000007}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>FontInfo</key>
@@ -1591,7 +1591,7 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{138.50000593397357, 523.49999999999977}, {50, 39.000000000000007}}</string>
+			<string>{{600.69368560963846, 77.446380098592286}, {50, 39.000000000000007}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>FontInfo</key>
@@ -1645,7 +1645,7 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{188.50000593397351, 523.49999999999977}, {50, 39.000000000000007}}</string>
+			<string>{{650.69368560963846, 77.446380098592286}, {50, 39.000000000000007}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>FontInfo</key>
@@ -1699,7 +1699,7 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{238.50059339735242, 523.49999999999977}, {50, 39.000000000000007}}</string>
+			<string>{{700.6942730730176, 77.446380098592286}, {50, 39.000000000000007}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>ID</key>
@@ -1741,7 +1741,7 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{288.50059339735253, 523.49999999999977}, {50, 39.000000000000007}}</string>
+			<string>{{750.6942730730176, 77.446380098592286}, {50, 39.000000000000007}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>ID</key>
@@ -1783,7 +1783,7 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{338.50059339735253, 523.49999999999977}, {50, 39.000000000000007}}</string>
+			<string>{{800.69427307301737, 77.446380098592286}, {50, 39.000000000000007}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>ID</key>
@@ -1825,7 +1825,7 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{388.50059339735253, 523.49999999999977}, {50, 39.000000000000007}}</string>
+			<string>{{850.69427307301737, 77.446380098592286}, {50, 39.000000000000007}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>ID</key>
@@ -1867,7 +1867,7 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{17.806330362955734, 463.77777777777766}, {53, 19}}</string>
+			<string>{{480.00001003862036, 17.724157876370128}, {53, 19}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>FitText</key>
@@ -1929,8 +1929,8 @@
 			<integer>39</integer>
 			<key>Points</key>
 			<array>
-				<string>{14.638893127441364, 452.88888888888874}</string>
-				<string>{464.86111534967347, 452.88888888888874}</string>
+				<string>{464.36112572953391, 435.91161599064242}</string>
+				<string>{465.36112572193315, 11.049724106226677}</string>
 			</array>
 			<key>Style</key>
 			<dict>
@@ -3820,7 +3820,7 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{26.50000508626303, 487.77777777777766}, {426.5, 168.20159912109375}}</string>
+			<string>{{488.69368476192756, 41.724157876370128}, {426.5, 168.20159912109375}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>ID</key>
@@ -3901,7 +3901,7 @@
 	<key>MasterSheets</key>
 	<array/>
 	<key>ModificationDate</key>
-	<string>2015-02-16 17:53:15 +0000</string>
+	<string>2015-02-17 13:45:56 +0000</string>
 	<key>Modifier</key>
 	<string>yuhi</string>
 	<key>NotesVisible</key>
@@ -4001,7 +4001,7 @@
 		<key>SidebarWidth</key>
 		<integer>119</integer>
 		<key>VisibleRegion</key>
-		<string>{{-142, 170.16575123589081}, {765.19339435619736, 499.44752960144575}}</string>
+		<string>{{149.17127543406014, 0}, {765.19339435619736, 499.44752960144581}}</string>
 		<key>Zoom</key>
 		<real>1.809999942779541</real>
 		<key>ZoomValues</key>
Binary file paper/images/fsort_bsort.pdf has changed
--- a/slide/blank.html	Tue Feb 17 19:03:27 2015 +0900
+++ b/slide/blank.html	Wed Feb 18 00:15:07 2015 +0900
@@ -114,16 +114,14 @@
       
       <div class='slide'>
         <h2>マルチプラットフォームなフレームワークにおける並列プログラミング 1/2</h2>
-        <p>プログラムが PC に要求する処理性能は上がってきているが、
-          消費電力や発熱、クロックの限界といった問題から CPU の性能を上げることによる処理性能の向上は難しい。</p>
-        <p>プロセッサメーカーはマルチコア CPU や、GPU を含んだヘテロジニアス構成の路線を打ち出している。
+        <p>
+          消費電力や発熱、クロックの限界といった問題から CPU の性能を上げることによる処理性能の向上は難しい。
+          マルチコア CPU や GPU を含んだヘテロジニアス構成が主流になっている。
           クロックの性能を上げるのではなく、コア数を増やす事でパフォーマンスを向上させている。
         </p>
         <p>
           マルチコア CPU や GPU といった<font color="red">マルチコアプラットフォーム</font>なアーキテクチャ上で
           リソースを有効活用するには、それぞれのプラットフォームに最適な形でプログラムを並列に動作させる必要がある。
-          ここでいう最適な形とは、実行の順番やどのリソース上で Task を実行するかといった、
-          Scheduling を含めたチューニングのことである。
         </p>
         <p>しかしこれらのチューニングは複雑で、コーディング時に毎回行うと複雑さや拡張性の問題がある。</p>
       </div>
@@ -152,7 +150,9 @@
         <p>
           Cerium は Linux、MacOSX 上で動作する汎用計算用の並列プログラミングフレームワークである。
         </p>
-        <img src="./images/cerium_image.png" width="700">
+        <div align="center">
+          <img src="./images/cerium_image.png" width="700">
+        </div>
         <p>Cerium を用いることでマルチコア CPU と GPU において Scheduling を含めたプログラミングを可能となる。</p>
       </div>
 
@@ -231,6 +231,87 @@
       </div>
 
       <div class='slide'>
+        <h2>Task の依存関係の記述</h2>
+        <p>
+          並列処理を行う場合、Task を大量に生成する場合がある。
+          そういった場合において一括で Task を生成/実行してしまうと並列度が落ちてしまう。
+          これは生成しただけで Task そのものがメモリを圧迫してしまっていることが原因となる。
+        </p>
+        <p>
+          そういった 例題において、Task は一定数ずつ徐々に生成/実行する必要がある。
+          ということは、Block 間で依存関係を設定する必要がある。
+          依存関係について Cerium の Bitonic Sort を例題に考える。
+        </p>
+      </div>
+
+
+      <div class='slide'>
+        <h2>Bitonic Sort の例題</h2>
+        <p>Bitonic Sort は配列の分割を行い、分割した部分に対して Sort を行う。
+          分割後の Sort には QuickSort を使用している。Bitonic Sort は2つの Sort を行う。
+        </p>
+        <ul>
+          <li>使用する CPU 数を元に分割数を算出し、分割した箇所に対して Sort する(fsort)
+          <li>Block の中間から次の Block の中間までを Sort する(bsort)
+        </ul>
+        <p>この2つの Sort を分割数分繰り返している</p>
+      </div>
+
+      <div class='slide'>
+        <h2>Bitonic Sort の例題</h2>
+        <div align="center">
+          <img src="./images/fsort_bsort.png" width="850">
+        </div>
+      </div>
+
+      <div class='slide'>
+        <h2>Task 間の依存関係</h2>
+        <p>Bitonic Sort を行う際、依存関係として bsort は fsort の結果に対して sort を行い、
+          fsort は前の Stage の bsort に対して Sort を行う必要がある
+        </p>
+        <p>よって、BitonicSort のような大量に Task を生成する例題を並列実行する場合、
+          「例題の性質としての依存関係」と「Task を徐々に生成するための依存関係」
+          の二種類の依存関係を記述する必要がある。</p>
+      </div>
+
+      <div class='slide'>
+        <h2>依存関係の記述</h2>
+        <p>例題独自の依存関係</p>
+              <pre class="code" align="left">static int
+sort_start(SchedTask *manager, void *d, void *e)
+{
+    Sort *s =  (Sort*)manager->get_param(0);
+    long half_num = s->split_num-1;
+
+    for (int i = 0; i < s->split_num-1; i++) {
+        s->fsort[i] = manager->create_task(QUICK_SORT,(memaddr)&s->data[i*block_num],
+                                           sizeof(Data)*block_num,
+                                           (memaddr)&s->data[i*block_num],
+                                           sizeof(Data)*block_num);
+
+            s->fsort[i]->wait_for(s->bsort[i-1]);
+    }
+~省略~
+              </pre>
+     </div>
+      <div class='slide'>
+        <h2>依存関係の記述</h2>
+        <p>Task を徐々に生成するための依存関係</p>
+        <pre class="code" align="left">
+    // recursive Task
+    HTaskPtr restart = manager->create_task(SortSimple,0,0,0,0);
+    restart->set_param(0,(memaddr)s);
+    restart->wait_for(s->fsort[0]);
+    for (int i = 0; i < s->split_num; i++) {
+        s->fsort[i]->spawn();
+    }
+    restart->spawn();
+    return 0;
+}
+        </pre>
+     </div>
+
+      <div class='slide'>
         <h2>TaskManager の構成</h2>
         <div align="center">
           <img src='images/createtask.png' width="700">
@@ -306,19 +387,106 @@
       </div>
       
       <div class='slide'>
-        <h2>DMA の prefetch を用いた改良</h2>
-        
+        <h2>マルチコア CPU におけるデータ並列</h2>
+        <p>
+          Cerium はタスク並列による実行のみを行っていた。
+          並列化を行う問題によってはデータ並列を行った方が良い場合がある。
+        </p> 
+        <p>
+          タスク並列は1つのデータに対して異なる処理方法を適用し、それぞれ独立して実行させるものである。
+        </p>
+
+        <p>
+          データ並列は多くのデータを1つのタスクに与え、データごとに独立した処理を行わせる手法である。
+        </p>
+        <p>処理対象となるデータが充分な数のサブセットへ分割可能な場合、データ並列が有効となる。</p>
       </div>
 
       <div class='slide'>
-        <h2>マルチコア CPU におけるデータ並列</h2>
+        <h2>iterate API</h2>
+        <p>
+          データ並列による実行を行う場合、一つの記述から複数のTaskを生成する必要がある。
+          生成した各TaskにIDとinput/output dataを割り当てる「iterate」というAPIを実装した。
+        </p>
+
+        <table>
+          <tr>
+            <td>
+              <img src="images/iterate.png" height="450"></img>
+            </td>
+            <td>
+              <ul>
+                <li>1つの記述から複数のTaskを生成する</li>
+                <li>生成した複数のTaskにIDとInput/Output Dataを割り当てる</li>
+              </ul>
+                この例だと、Taskの持つidとTaskに割り当てられるデータは
+                1対1で対応している。id=割り当てられたdataのindexとなっている。<br><br>
+              並列プログラミングだと、並列化部分が全て同一の Task であるという場合は少なくない。
+              iterate API ならループで回すような処理をする必要が無く、容易な Syntax で記述できる。
+            </td>
+        </tr></table>
+      </div>
+
+      <div class='slide'>
+        <h2>マルチコア CPU によるデータ並列実行</h2>
+        <p>
+          マルチコア CPU においてデータ並列実行する場合、以下のように記述する。
+          例題として 2つの input のデータの積を output データに格納して返す例題、multiply を用いた。
+        </p>
+        <pre class="code">
+static int 
+run(SchedTask *s, void *rbuf, void *wbuf) {
+    float *indata1, *indata2, *outdata;
+
+    indata1 = (float*)s->get_input(rbuf, 0);
+    indata2 = (float*)s->get_input(rbuf, 0);
+    outdata = (float*)s->get_output(wbuf, 0);
+
+    long id = (long)s->get_param(0);
+    outdata[id] = indata1[id] * indata2[id];
+    return 0;
+}
+        </pre>
+      <p>get_param によって自分の担当する index を取得し、担当範囲のみを計算する。</p>
+      <p>データ並列実行する場合、各Task に Input/Outpu を設定するのではなく、
+        全ての Task でデータを共有する。共有したデータの自分の担当する箇所にのみ計算を行う。
+        そのため少ないコピーにおさえることができる。
+      </p>
+      </div>
+
+    
+      <div class='slide'>
+        <h2>DMA 転送</h2>
+        <p>Cerium は DMA 転送をサポートしている。
+          DMA とは CPU を介さずに周辺装置とメモリ間でデータ転送を行う転送方式である。
+        </p>
+        <p>
+          DMA は prefetch と呼ばれる転送先読みの機能がある。
+          DMA の転送効率を向上させるために送信データを予め取り込んでおく機能である。
+          prefetch による転送機能を追加した。
+        </p>
       </div>
 
       <div class='slide'>
         <h2>GPU 上での並列実行</h2>
+        <p>
+          GPU 上での並列実行をサポートするフレームワークとして、OpenCL と CUDA が挙げられる。
+          これらのフレームワークを用いて Cerium に GPU 上で 並列実行する機能を加えた。
+        </p>
+        <p>
+          Scheduler から受け取った Task やデータをOpenCL、CUDA の API を介して GPU に転送する機構、
+          GpuScheduler と CudaScheduler を実装した。
+        </p>
+        <div align="center">
+          <img src="./images/gpu_image.png" width="600">
+        </div>
       </div>
       
       <div class='slide'>
+        <h2>フレームワークを用いた GPU の制御</h2>
+      </div>
+
+      <div class='slide'>
         <h2>GPGPU におけるパイプラインの実装</h2>
       </div>
 
Binary file slide/graffle/.DS_Store has changed
Binary file slide/images/fsort_bsort.png has changed
Binary file slide/images/gpu_image.png has changed
Binary file slide/images/iterate.png has changed