Mercurial > hg > Papers > 2011 > yutaka-jssst
annotate paper/datasegment.ind @ 11:6ba51690320a
ref and fig
| author | Shinji KONO <kono@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Thu, 11 Aug 2011 23:23:05 +0900 |
| parents | 99f297cb7d34 |
| children |
| rev | line source |
|---|---|
|
7
f5982d0deab5
裕さんが送信した形に修正、裕さんが送信した内容はabstract_yutaka.txt内に保存
Daichi TOMA <e085740@ie.u-ryukyu.ac.jp>
parents:
6
diff
changeset
|
1 -title: Cerium における DataSegment API の設計 |
| 2 | 2 |
| 11 | 3 -author: 金城裕 and 河野真治 |
| 4 | |
| 2 | 5 --abstract: |
| 6 | |
| 11 | 7 本研究室では、Cell \cite{Cell}用の並列TaskManager Cerium\cite{kono10c,kono08d}を作成し、Rendering Engine を含む |
| 2 | 8 ゲームや並列計算の例題の作成と評価を行ってきた。TaskManager と Rendering Engine はシューティングゲーム |
| 9 やレーシングゲームを記述するのに十分な性能を持っており、台数効果も満足いくものと | |
| 10 なっている。しかし、この開発により Ceirum の問題点も明らかになってきている。 | |
| 11 本論文では、今まので Cerium の構成と問題点を記述し、新しい TaskManager の設計 | |
| 12 方針を述べる。 | |
| 13 | |
| 10 | 14 --Cell用Task Manager Cerium |
| 15 | |
| 11 | 16 Cerium は PS3 (Cell\cite{Cell}) 用のゲームフレームワークであり、ソフトウェアレンダリングを含む |
| 10 | 17 並列処理を Task 単位で記述する。今は C++ で記述されており、基本的な例題や、 |
| 18 シューティングなどの例題で妥当な性能がでている。 | |
| 19 | |
| 20 しかし、Taskの種類などが増え、記述が繁雑であるなどの欠点も明らかになっている。この | |
| 21 論文では Many Core 向けの改良を提案する。 | |
| 22 | |
| 8 | 23 --Ceriumでの並列プログラミングの問題点 |
| 2 | 24 |
| 8 | 25 Cerium では、ゲームプログラミング及び、sort や word count などの例題を書いたが、いくつかの問題点が明らかになっている。 |
| 2 | 26 |
| 8 | 27 Task の取り扱うデータ型が示されない |
| 28 Task 自体は簡単だが Task を構成する方法が繁雑 | |
| 11 | 29 Open CL\cite{opencl} に比べても構文的に複雑 |
| 8 | 30 Task の種類が複雑 |
| 31 Task の依存関係の記述がデータの依存関係と無関係 | |
| 32 Task Scheduler が大きくメモリを圧迫 | |
| 33 | |
| 34 などである。実装方法的にもいくつか問題がある。 | |
| 2 | 35 |
| 8 | 36 C++ と Task 記述の相性が良くない |
| 37 Task Manager が複雑になりすぎ | |
| 38 | |
| 39 Task Scheduler は Queue からTaskを取り出して一つ一つパイプライン実行を行うインタプリタ的な構造を持っている。これが、Task Manager 自体を複雑にする原因になっている。 | |
| 2 | 40 |
| 41 --Continuation based C との相性 | |
| 42 | |
| 11 | 43 当研究室で開発している Continuation based C \cite{kono08e}は、並列処理の基本単位である Task に対応した code segment を持っている。これを Cerium に対応させようとすると以下のような問題がある。 |
| 8 | 44 |
| 45 Inteface の型が整合しないとTask同士を接続できない | |
| 46 Scheduler への接続が特定のInterfaceを要求する | |
| 47 | |
| 48 どちらも、Code segment の interface (入力と出力) は、決まった形であるべきだと言うことを示している。しかし、Task 自体は様々なデータを取り扱う必要がある。ここに矛盾がある。この矛盾を解決するためには、データ側も基本単位を導入するべきだいうことになる。 | |
| 49 | |
| 11 | 50 <center><img src="fig/DSCS.pdf" alt="DS and CS"></center> |
| 51 | |
| 52 Data Segment は、Code segment の双対概念であり、C の構造体に相当する。CbC\cite{cbc-sourceforge} の Code segment は、 | |
| 8 | 53 |
| 54 input interface (関数の引数の型) | |
| 55 output interface (goto 文の引数の型) | |
| 56 | |
| 57 を持っているが、これらを | |
| 58 | |
| 59 input datasegments | |
| 60 output datasegments | |
| 61 | |
| 11 | 62 に置き換える。つまり、Code segment は、複数の動的に割り当てられた Data segment を持っている(図\ref{DS and CS})。これらは、標準的な構造を持っているので、Interface の型の不整合を避けることができる。 |
| 8 | 63 |
| 64 Data segment は型を持っていて、その型は実行時に一致している必要がある。分散通信を考えて、Data segment の型は MessagePack \cite{MessagePack} を用いる。 | |
| 65 | |
| 2 | 66 --C++ との相性 |
| 67 | |
| 11 | 68 Cerium の Task は、Cell のspuとppuで共通であり、同じ Task ID で管理されている。これは C++ のオブジェクトとは関係ない。Cerium の開発でわかったのは、Cerium のデータは、Actor の become 的\cite{actor87} に書き換えられるということである。C++のようなポインタを使い合わし、オブジェクトの内部の書き換えで状態を作るようなオブジェクト指向プログラミングと、細分化したTaskを並列に廻す Ceirum のようなシステムとの相性は良くない。 |
| 9 | 69 Task の入力と出力は異なる場所に書かれる。処理は、常にダブルバッファを用いて行われているのでそのようになる。 |
| 70 | |
| 71 --階層的パイプライン | |
| 8 | 72 |
| 9 | 73 プログラム中の自明な並列性は、データ並列とループのパイプラインの二つであり、パイプラインはプログラムの中で、様々なレベルで行われる。Task そのものは入力データから出力データを計算するだけなので単純だが、その入出力データをダブルバッファリングとして切替えたり、適切な並列度を得られるように徐々に生成するのは非常に繁雑になる。 |
| 8 | 74 |
| 9 | 75 これらのデータの管理は、中心となるアルゴリズムとは別に並列実行を行うアーキテクチャに特化した処理が必要となる。例えば、分散環境で並列処理するのか、MPIなのか、Cell や Open CL なのかによって異なる。これらを、すべて Task という一括りで扱うと並列計算しない複雑なTaskができてしまう。 |
| 76 | |
| 77 これらのデータ管理用の Task は、本質的には Data Segment に対する Iterator であり、ライブラリまたはコンパイラにより生成されるべきものだと考えられる。 | |
| 8 | 78 |
| 10 | 79 --Task 内部での Task 生成 |
| 80 | |
| 81 Cerium では、複数の input と output を決めたパイプライン実行が通常であるが、 | |
| 82 Task の途中で Main Memory を参照したいことが良くある。 | |
| 83 | |
| 84 描画Texture のデータ | |
| 85 SceneGraphの次のノード | |
| 86 | |
| 87 これらは実行時にしか次のデータのアドレスを決定することができない。これを読み出し前のTaskと | |
| 88 読み出し後のTaskに分割して、さらにパイプライン実行してやると良いが、この記述は今までの | |
| 89 Cerium では不可能で、明示的な DMA API を使う必要があった。 | |
| 90 | |
| 91 Task内部でTask生成をしてやると、これを記述することが可能だが、TaskManagerの複雑度が上がってしまう | |
| 92 とう問題点があった。 | |
| 93 | |
| 2 | 94 --Data Segment を用いた Cerium の再設計 |
| 95 | |
| 9 | 96 Cell 用のTaskManager Cerium の再設計の方針としては以下のようになる。 |
| 97 | |
| 98 CbCのCode segment の導入 | |
| 10 | 99 定型的な Data 単位である Data segment |
| 100 Data segment の型の指定 | |
| 101 Task Manager の Code segment による実装 | |
| 102 Code segment (Task) の生成API | |
| 9 | 103 |
| 2 | 104 ---Data Segment の型 |
| 105 | |
| 10 | 106 Cerium では Task の入出力は単なる memory buffer だったので型が存在しなかった。今回は Message Pack |
| 107 を用いて、Json 的に型を指定する。 | |
| 108 | |
| 109 Data segment は様々なメモリ上に位置するので、それを識別する必要がある。Many Core 版の Cerium では、 | |
| 110 | |
| 111 Main Memory | |
| 112 SPU local memory | |
| 113 Cache | |
| 114 | |
| 115 の三種類を用意する。これらは DMA や Cache 操作命令を通して移動する。移動したものは同一のものである。Cell SPUのTask や Many Core では、当然だが lcoal memory や Cache に乗らない限りアクセスできない。 | |
| 116 | |
| 117 Data segment は、Code Segment に input と output として接続される。 | |
| 118 | |
| 2 | 119 ---Data Segment のAPI |
| 120 | |
| 10 | 121 Data Segment は以下のAPIを持っている |
| 122 | |
| 123 create | |
| 124 read | |
| 125 update | |
| 126 delete | |
| 127 | |
| 128 Create は allocate に相当する。型と位置を指定して create する。Main Memory 上の Data segment を読み書きする場合は、local memory または Cache を通してパイプライン的に実行される。 | |
| 129 | |
| 130 複数のCode Segment から update が起きる場合は、以下の操作を選択する。 | |
| 131 | |
| 132 Queuing | |
| 133 Update | |
| 134 Proority Queue | |
| 135 | |
| 136 生成された Data segment は synchronized queue として使うことができる。 | |
| 137 | |
| 2 | 138 ---Task Dependendcy |
| 139 | |
| 10 | 140 今までの Cerium では、\verb+task->wait_for(task1);+ という形で明示的に Task の依存性を指定していた。 |
| 141 この方法では、\verb+task+ の寿命(既に終了してしまった task を待つような場合)などの問題がある。 | |
| 142 | |
| 143 しかし、Code Segment は input / outpu Data Segment によって自然な依存関係を持つので、明示的な | |
| 144 \verb+wait_for+ は必要なくなる。 | |
| 145 | |
| 146 Code Segment と Data Segment は task を処理して行くうちに自然に消滅してしまう。Persistent な | |
| 147 データは明示的にデータベースに格納する必要がある。つまり、Data Segment に Persistentという | |
| 148 位置が存在する。 | |
| 149 | |
| 150 ---Pipeline Execution | |
| 151 | |
| 152 Cerium では、Task のread/exec/write は三段のパイプラインで実行されていた。Data Segment は | |
| 153 Code Segment の実行の前に行われるが、他の Code Segment とオーバラップして実行して良い。 | |
| 154 Data Segment には、Data Segment の位置を変更するための Code Segment が存在している。 | |
| 155 | |
| 156 つまり、Data Segment は複数の Code Segment ( この Data segment を待っている Code segment ) | |
| 157 と、Data Segment の位置などを変える Code Segment などが付随している。 | |
| 158 | |
| 159 一つのCoreでは、Data Segment に付属する Code segment を順次実行することにより、パイプライン | |
| 160 を実行する。 | |
| 161 | |
| 162 Data Segment による依存関係を追い越さなければ並列実行は自由に行われる。これは、Task Scheduling | |
| 163 を担当する Code Segment によってアーキテクチャに合わせて実行される。 | |
| 11 | 164 (図\ref{DS Pipeline}) |
| 165 | |
| 166 <center><img src="fig/DSCS2.pdf" alt="DS Pipeline"></center> | |
| 10 | 167 |
| 2 | 168 ---Data Segment Storage Type |
| 169 | |
| 10 | 170 Data Segment には位置とIdentityを表す ID が付いている。Many Core 版ではメモリアドレス(64bit) |
| 171 をIDとして使って良い。 | |
| 172 | |
| 173 SPUのようなlocal memoryでは、hash を使ってData Segmentの管理を行う。 | |
| 174 | |
| 175 Persistent な Data Segment では ID は使用する Database のtableとkeyを表す。 | |
| 176 | |
| 2 | 177 ---Data Segment の処理の記述 |
| 178 | |
| 10 | 179 Data Segment は Message Pack でもあり、Json 的な木構造を持っている。これが Cerium の |
| 180 SceneGraph に相当する。 | |
| 181 | |
| 2 | 182 --期待される効果 |
| 183 | |
| 10 | 184 Data Segment API は、これから実装することになるが、 |
| 185 | |
| 186 Cerium の既存の例題が動くこと | |
| 187 | |
| 188 が一つの基準となる。PS3 が無事ならば PS3 でも動かしたい。Core i7 系、GPGPU 系、Open CL での | |
| 189 共通のプログラミングフレームワークとして使用することができると期待している。 | |
| 190 | |
| 191 詳細なAPIは、これから決めることになると思うが、今のCeriumのAPI | |
| 192 | |
| 193 | |
| 194 |