Mercurial > hg > Papers > 2011 > yutaka-jssst

comparison paper/datasegment.ind @ 11:6ba51690320a

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ref and fig
author Shinji KONO <kono@ie.u-ryukyu.ac.jp>
date Thu, 11 Aug 2011 23:23:05 +0900
parents 99f297cb7d34
children
comparison
equal deleted inserted replaced
10:99f297cb7d34 11:6ba51690320a
1 -title: Cerium における DataSegment API の設計 1 -title: Cerium における DataSegment API の設計
2
3 -author: 金城裕 and 河野真治
2 4
3 --abstract: 5 --abstract:
4 6
5 本研究室では、Cell 用の並列TaskManager Ceriumを作成し、Rendering Engine を含む 7 本研究室では、Cell \cite{Cell}用の並列TaskManager Cerium\cite{kono10c,kono08d}を作成し、Rendering Engine を含む
6 ゲームや並列計算の例題の作成と評価を行ってきた。TaskManager と Rendering Engine はシューティングゲーム 8 ゲームや並列計算の例題の作成と評価を行ってきた。TaskManager と Rendering Engine はシューティングゲーム
7 やレーシングゲームを記述するのに十分な性能を持っており、台数効果も満足いくものと 9 やレーシングゲームを記述するのに十分な性能を持っており、台数効果も満足いくものと
8 なっている。しかし、この開発により Ceirum の問題点も明らかになってきている。 10 なっている。しかし、この開発により Ceirum の問題点も明らかになってきている。
9 本論文では、今まので Cerium の構成と問題点を記述し、新しい TaskManager の設計 11 本論文では、今まので Cerium の構成と問題点を記述し、新しい TaskManager の設計
10 方針を述べる。 12 方針を述べる。
11 13
12 --Cell用Task Manager Cerium 14 --Cell用Task Manager Cerium
13 15
14 Cerium は PS3 (Cell) 用のゲームフレームワークであり、ソフトウェアレンダリングを含む 16 Cerium は PS3 (Cell\cite{Cell}) 用のゲームフレームワークであり、ソフトウェアレンダリングを含む
15 並列処理を Task 単位で記述する。今は C++ で記述されており、基本的な例題や、 17 並列処理を Task 単位で記述する。今は C++ で記述されており、基本的な例題や、
16 シューティングなどの例題で妥当な性能がでている。 18 シューティングなどの例題で妥当な性能がでている。
17 19
18 しかし、Taskの種類などが増え、記述が繁雑であるなどの欠点も明らかになっている。この 20 しかし、Taskの種類などが増え、記述が繁雑であるなどの欠点も明らかになっている。この
19 論文では Many Core 向けの改良を提案する。 21 論文では Many Core 向けの改良を提案する。
22 24
23 Cerium では、ゲームプログラミング及び、sort や word count などの例題を書いたが、いくつかの問題点が明らかになっている。 25 Cerium では、ゲームプログラミング及び、sort や word count などの例題を書いたが、いくつかの問題点が明らかになっている。
24 26
25 Task の取り扱うデータ型が示されない 27 Task の取り扱うデータ型が示されない
26 Task 自体は簡単だが Task を構成する方法が繁雑 28 Task 自体は簡単だが Task を構成する方法が繁雑
27 Open CL に比べても構文的に複雑 29 Open CL\cite{opencl} に比べても構文的に複雑
28 Task の種類が複雑 30 Task の種類が複雑
29 Task の依存関係の記述がデータの依存関係と無関係 31 Task の依存関係の記述がデータの依存関係と無関係
30 Task Scheduler が大きくメモリを圧迫 32 Task Scheduler が大きくメモリを圧迫
31 33
32 などである。実装方法的にもいくつか問題がある。 34 などである。実装方法的にもいくつか問題がある。
36 38
37 Task Scheduler は Queue からTaskを取り出して一つ一つパイプライン実行を行うインタプリタ的な構造を持っている。これが、Task Manager 自体を複雑にする原因になっている。 39 Task Scheduler は Queue からTaskを取り出して一つ一つパイプライン実行を行うインタプリタ的な構造を持っている。これが、Task Manager 自体を複雑にする原因になっている。
38 40
39 --Continuation based C との相性 41 --Continuation based C との相性
40 42
41 当研究室で開発している Continuation based C は、並列処理の基本単位である Task に対応した code segment を持っている。これを Cerium に対応させようとすると以下のような問題がある。 43 当研究室で開発している Continuation based C \cite{kono08e}は、並列処理の基本単位である Task に対応した code segment を持っている。これを Cerium に対応させようとすると以下のような問題がある。
42 44
43 Inteface の型が整合しないとTask同士を接続できない 45 Inteface の型が整合しないとTask同士を接続できない
44 Scheduler への接続が特定のInterfaceを要求する 46 Scheduler への接続が特定のInterfaceを要求する
45 47
46 どちらも、Code segment の interface (入力と出力) は、決まった形であるべきだと言うことを示している。しかし、Task 自体は様々なデータを取り扱う必要がある。ここに矛盾がある。この矛盾を解決するためには、データ側も基本単位を導入するべきだいうことになる。 48 どちらも、Code segment の interface (入力と出力) は、決まった形であるべきだと言うことを示している。しかし、Task 自体は様々なデータを取り扱う必要がある。ここに矛盾がある。この矛盾を解決するためには、データ側も基本単位を導入するべきだいうことになる。
47 49
48 Data Segment は、Code segment の双対概念であり、C の構造体に相当する。CbC の Code segment は、 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 は、
49 53
50 input interface (関数の引数の型) 54 input interface (関数の引数の型)
51 output interface (goto 文の引数の型) 55 output interface (goto 文の引数の型)
52 56
53 を持っているが、これらを 57 を持っているが、これらを
54 58
55 input datasegments 59 input datasegments
56 output datasegments 60 output datasegments
57 61
58 に置き換える。つまり、Code segment は、複数の動的に割り当てられた Data segment を持っている。これらは、標準的な構造を持っているので、Interface の型の不整合を避けることができる。 62 に置き換える。つまり、Code segment は、複数の動的に割り当てられた Data segment を持っている(図\ref{DS and CS})。これらは、標準的な構造を持っているので、Interface の型の不整合を避けることができる。
59 63
60 Data segment は型を持っていて、その型は実行時に一致している必要がある。分散通信を考えて、Data segment の型は MessagePack \cite{MessagePack} を用いる。 64 Data segment は型を持っていて、その型は実行時に一致している必要がある。分散通信を考えて、Data segment の型は MessagePack \cite{MessagePack} を用いる。
61 65
62 --C++ との相性 66 --C++ との相性
63 67
64 Cerium の Task は、Cell のspuとppuで共通であり、同じ Task ID で管理されている。これは C++ のオブジェクトとは関係ない。Cerium の開発でわかったのは、Cerium のデータは、Actor の become 的\cite{Act3} に書き換えられるということである。C++のようなポインタを使い合わし、オブジェクトの内部の書き換えで状態を作るようなオブジェクト指向プログラミングと、細分化したTaskを並列に廻す Ceirum のようなシステムとの相性は良くない。 68 Cerium の Task は、Cell のspuとppuで共通であり、同じ Task ID で管理されている。これは C++ のオブジェクトとは関係ない。Cerium の開発でわかったのは、Cerium のデータは、Actor の become 的\cite{actor87} に書き換えられるということである。C++のようなポインタを使い合わし、オブジェクトの内部の書き換えで状態を作るようなオブジェクト指向プログラミングと、細分化したTaskを並列に廻す Ceirum のようなシステムとの相性は良くない。
65 Task の入力と出力は異なる場所に書かれる。処理は、常にダブルバッファを用いて行われているのでそのようになる。 69 Task の入力と出力は異なる場所に書かれる。処理は、常にダブルバッファを用いて行われているのでそのようになる。
66 70
67 --階層的パイプライン 71 --階層的パイプライン
68 72
69 プログラム中の自明な並列性は、データ並列とループのパイプラインの二つであり、パイプラインはプログラムの中で、様々なレベルで行われる。Task そのものは入力データから出力データを計算するだけなので単純だが、その入出力データをダブルバッファリングとして切替えたり、適切な並列度を得られるように徐々に生成するのは非常に繁雑になる。 73 プログラム中の自明な並列性は、データ並列とループのパイプラインの二つであり、パイプラインはプログラムの中で、様々なレベルで行われる。Task そのものは入力データから出力データを計算するだけなので単純だが、その入出力データをダブルバッファリングとして切替えたり、適切な並列度を得られるように徐々に生成するのは非常に繁雑になる。
155 一つのCoreでは、Data Segment に付属する Code segment を順次実行することにより、パイプライン 159 一つのCoreでは、Data Segment に付属する Code segment を順次実行することにより、パイプライン
156 を実行する。 160 を実行する。
157 161
158 Data Segment による依存関係を追い越さなければ並列実行は自由に行われる。これは、Task Scheduling 162 Data Segment による依存関係を追い越さなければ並列実行は自由に行われる。これは、Task Scheduling
159 を担当する Code Segment によってアーキテクチャに合わせて実行される。 163 を担当する Code Segment によってアーキテクチャに合わせて実行される。
164 (図\ref{DS Pipeline})
165
166 <center><img src="fig/DSCS2.pdf" alt="DS Pipeline"></center>
160 167
161 ---Data Segment Storage Type 168 ---Data Segment Storage Type
162 169
163 Data Segment には位置とIdentityを表す ID が付いている。Many Core 版ではメモリアドレス(64bit) 170 Data Segment には位置とIdentityを表す ID が付いている。Many Core 版ではメモリアドレス(64bit)
164 をIDとして使って良い。 171 をIDとして使って良い。