ModificationDate - 2015-02-16 17:53:15 +0000 + 2015-02-17 13:45:56 +0000 Modifier yuhi NotesVisible @@ -4001,7 +4001,7 @@ SidebarWidth 119 VisibleRegion - {{-142, 170.16575123589081}, {765.19339435619736, 499.44752960144575}} + {{149.17127543406014, 0}, {765.19339435619736, 499.44752960144581}} Zoom 1.809999942779541 ZoomValues diff -r 17f33e4aa7ba -r 3a35d13818e5 paper/images/fsort_bsort.pdf Binary file paper/images/fsort_bsort.pdf has changed diff -r 17f33e4aa7ba -r 3a35d13818e5 slide/blank.html --- 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 @@

マルチプラットフォームなフレームワークにおける並列プログラミング 1/2

プログラムが PC に要求する処理性能は上がってきているが、 - 消費電力や発熱、クロックの限界といった問題から CPU の性能を上げることによる処理性能の向上は難しい。

プロセッサメーカーはマルチコア CPU や、GPU を含んだヘテロジニアス構成の路線を打ち出している。 +

+ 消費電力や発熱、クロックの限界といった問題から CPU の性能を上げることによる処理性能の向上は難しい。 + マルチコア CPU や GPU を含んだヘテロジニアス構成が主流になっている。クロックの性能を上げるのではなく、コア数を増やす事でパフォーマンスを向上させている。

マルチコア CPU や GPU といったマルチコアプラットフォームなアーキテクチャ上でリソースを有効活用するには、それぞれのプラットフォームに最適な形でプログラムを並列に動作させる必要がある。 - ここでいう最適な形とは、実行の順番やどのリソース上で Task を実行するかといった、 - Scheduling を含めたチューニングのことである。

しかしこれらのチューニングは複雑で、コーディング時に毎回行うと複雑さや拡張性の問題がある。

@@ -152,7 +150,9 @@

Cerium は Linux、MacOSX 上で動作する汎用計算用の並列プログラミングフレームワークである。

Cerium を用いることでマルチコア CPU と GPU において Scheduling を含めたプログラミングを可能となる。

@@ -231,6 +231,87 @@

Task の依存関係の記述

+ 並列処理を行う場合、Task を大量に生成する場合がある。 + そういった場合において一括で Task を生成/実行してしまうと並列度が落ちてしまう。 + これは生成しただけで Task そのものがメモリを圧迫してしまっていることが原因となる。 +

+ そういった例題において、Task は一定数ずつ徐々に生成/実行する必要がある。 + ということは、Block 間で依存関係を設定する必要がある。 + 依存関係について Cerium の Bitonic Sort を例題に考える。 +

+ + +

Bitonic Sort の例題

Bitonic Sort は配列の分割を行い、分割した部分に対して Sort を行う。 + 分割後の Sort には QuickSort を使用している。Bitonic Sort は2つの Sort を行う。 +

使用する CPU 数を元に分割数を算出し、分割した箇所に対して Sort する(fsort) +
Block の中間から次の Block の中間までを Sort する(bsort) +

この2つの Sort を分割数分繰り返している

+ +

Bitonic Sort の例題

+ +

Task 間の依存関係

Bitonic Sort を行う際、依存関係として bsort は fsort の結果に対して sort を行い、 + fsort は前の Stage の bsort に対して Sort を行う必要がある +

よって、BitonicSort のような大量に Task を生成する例題を並列実行する場合、 + 「例題の性質としての依存関係」と「Task を徐々に生成するための依存関係」 + の二種類の依存関係を記述する必要がある。

+ +

依存関係の記述

例題独自の依存関係

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]);
+    }
+~省略~
+

依存関係の記述

Task を徐々に生成するための依存関係

+    // 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;
+}
+

+ +

TaskManager の構成

@@ -306,19 +387,106 @@

DMA の prefetch を用いた改良

- +

マルチコア CPU におけるデータ並列

+ Cerium はタスク並列による実行のみを行っていた。 + 並列化を行う問題によってはデータ並列を行った方が良い場合がある。 +

+ タスク並列は1つのデータに対して異なる処理方法を適用し、それぞれ独立して実行させるものである。 +

+ +

+ データ並列は多くのデータを1つのタスクに与え、データごとに独立した処理を行わせる手法である。 +

処理対象となるデータが充分な数のサブセットへ分割可能な場合、データ並列が有効となる。

マルチコア CPU におけるデータ並列

iterate API

+ データ並列による実行を行う場合、一つの記述から複数のTaskを生成する必要がある。 + 生成した各TaskにIDとinput/output dataを割り当てる「iterate」というAPIを実装した。 +

+ + + + + +

+ +	+ + 1つの記述から複数のTaskを生成する + 生成した複数のTaskにIDとInput/Output Dataを割り当てる + + この例だと、Taskの持つidとTaskに割り当てられるデータは + 1対1で対応している。id=割り当てられたdataのindexとなっている。 + 並列プログラミングだと、並列化部分が全て同一の Task であるという場合は少なくない。 + iterate API ならループで回すような処理をする必要が無く、容易な Syntax で記述できる。 +

+ +

マルチコア CPU によるデータ並列実行

+ マルチコア CPU においてデータ並列実行する場合、以下のように記述する。 + 例題として 2つの input のデータの積を output データに格納して返す例題、multiply を用いた。 +

+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;
+}
+

get_param によって自分の担当する index を取得し、担当範囲のみを計算する。

データ並列実行する場合、各Task に Input/Outpu を設定するのではなく、 + 全ての Task でデータを共有する。共有したデータの自分の担当する箇所にのみ計算を行う。 + そのため少ないコピーにおさえることができる。 +

+ + +

DMA 転送

Cerium は DMA 転送をサポートしている。 + DMA とは CPU を介さずに周辺装置とメモリ間でデータ転送を行う転送方式である。 +

+ DMA は prefetch と呼ばれる転送先読みの機能がある。 + DMA の転送効率を向上させるために送信データを予め取り込んでおく機能である。 + prefetch による転送機能を追加した。 +

GPU 上での並列実行

+ GPU 上での並列実行をサポートするフレームワークとして、OpenCL と CUDA が挙げられる。 + これらのフレームワークを用いて Cerium に GPU 上で並列実行する機能を加えた。 +

+ Scheduler から受け取った Task やデータをOpenCL、CUDA の API を介して GPU に転送する機構、 + GpuScheduler と CudaScheduler を実装した。 +

フレームワークを用いた GPU の制御

+ +

GPGPU におけるパイプラインの実装

diff -r 17f33e4aa7ba -r 3a35d13818e5 slide/graffle/.DS_Store Binary file slide/graffle/.DS_Store has changed diff -r 17f33e4aa7ba -r 3a35d13818e5 slide/images/fsort_bsort.png Binary file slide/images/fsort_bsort.png has changed diff -r 17f33e4aa7ba -r 3a35d13818e5 slide/images/gpu_image.png Binary file slide/images/gpu_image.png has changed diff -r 17f33e4aa7ba -r 3a35d13818e5 slide/images/iterate.png Binary file slide/images/iterate.png has changed