Mercurial > hg > Papers > 2008 > kono-ieice-vld
view manycore.html @ 2:35b71ac6ce17 default tip
update tags
author | convert-repo |
---|---|
date | Mon, 10 Nov 2008 05:00:42 +0000 |
parents | 685b35adf419 |
children |
line wrap: on
line source
<html> <META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=Shift_JIS"> <head> <title> 検証を自身で表現できるハードウェア、ソフトウェア記述言語 Continuation based C と、そのCell への応用</title> </head> <body> <h1> 検証を自身で表現できるハードウェア、ソフトウェア記述言語 Continuation based C と、そのCell への応用</h1> <a href=#content>content</a><br> <nr> <p> <author> 河野真治</author> <hr> <h1><a name="content000">title-e: Self descriptive verfication in Continuation based C and it's application to Cell architecture</a></h1> <hr> <h1><a name="content001">abstract-e:</a></h1> hoge <p> <quote> 近年、CPUの性能向上は、クロックサイクルをあげることよりも、 複数のCPUコア(Many Core Architecture)を導入することにより得られるようになって来ている。しかし、Many Core Architecture のプログラムは複雑であり、 その信頼性を確保することは難しい。本論文では、本研究室で開 発した Cのサブセット であるContination based C を用いて、Many Core Architecture のプログラミングと、その検証を行う手法について考察する。ここでは例題として、Cell Broadband Engine を用いたレンダリングエンジンを用いる。 <p> </quote> <hr> <h2><a name="content002">Multi core system</a></h2> 複数のCPUを載せたコンピュータは昔から使われて来たが、最近の傾向は、一つのChipに複数のCPUコアを載せたものの登場である。 従来のマルチプロセッサは同期をサポートしたキャッシュを経由しメインメモリにアクセスすることが多いが、最近開発されたMulti Core では、CPU間の通信に特別なポートを用意している。 例えば、IntelはQuick Pathと言う通信ポートががある。 これにより、メインメモリへのアクセスによる競合を避けることができる。しかし、その分、複雑なプログラミングが必要となる。 <p> Cell Broadband Engine\cite{Cell} は、SCEIとIBMによって開発されたPS3ゲーム機用のCPUであり、2 thread のPPU(PowerPC Unit)と、8個のSPU (Synergetic Processing Unit) を持つ(図\ref{cellarch})。本研究で用いたPS3Linux (FedoreCore 6)では、6個のSPUを使うことが出来る。SPUはそれぞれ256kbのローカルメモリを持ち、バスに負担をかけることなく並列に計算を進めることが出来る。SPUからメインメモリへは、SPUの機械語から直接アクセス することは出来ず、CellのMFC(Memory Flow Controller)へDMA (Direct Memory Access) 命令を送ることで行われる。 SPUはグラフィックスに適した、4つの固定小数点、浮動小数点を同時に演算する命令などを持ち、PPUに比べて高速な演算が可能であり、 ほとんどの演算をSPU上で進めることが推奨されている。 <p> <center><img src="fig/cell.pdf" alt="cellarch"></center> <p> <hr> <h2><a name="content003">Many Core 上のプログラムの特徴</a></h2> 従来の逐次型のプログラムでは、Many Coreの性能を十分に引き出すことは出来ない。ここでは、その性能を活かすMany Core プログラムの特徴について考察する。ここでは、{\tt 定常的な並列度の必要性、 データ並列、パイプライン実行、 プログラムとデータの分割、 同期の問題、 マルチスレッド、 デバッグ}に関して考察を行う。 <p> <hr> <h3><a name="content004">定常的な並列度の必要性</a></h3> 並列実行にはAmdahl則\cite{java-conncurrecy}があり、プログラムの並列化率が低ければ、その性能を活かすことは出来ない。0.8 程度の並列化率では、6CPUでも3倍程度の性能向上しか得られない(\ref{amdhal})。 <p> <center><img src="fig/amdahl.pdf" alt="amdahl"></center> <p> 高い並列度ではなくとも、恒常的に並列度を維持する必要がある。このため、 <p> <pre> 逐次型のプログラムの一部を並列化する </pre> という手法では不十分である。LSIなどのハードウェア場合は演算の対象がもともと多量の演算とデータパスを持つので並列計算の効果を定常的に得られることが多いが、C等で記述されたプログラムでは、 for 文や配列のアクセスなどに並列性が隠されてしまい、それを引き出すことが難しい。 <p> プログラムの中の並列度は、主に二つの形で取り出すことが出来る。 一つは、配列や木の中の個々の要素に対して並列に実行する <p> <pre> データ並列 </pre> である。もう一つは、複数の逐次処理の隣同士を重ねて実行する <p> <pre> パイプライン処理 </pre> である。この二つを同時に用いることで定常的な並列度を維持することが可能となることがある。パイプライン処理は、プログラム中で階層的に使われることが多い。 <p> <hr> <h3><a name="content005">プログラムとデータの分割</a></h3> データ並列とパイプライン処理を可能にするためには、プログラムとデータの適切な分割を行う必要がある。for文、あるいは、木をだとって処理する個々のステートメントがプログラムの分割の対象となる。 データは自明に分割できるわけではなく、分割できるデータ構造を採用し、 必要ならばコピーを行う。 <p> 分割されたデータは、メモリ上に置かれるが、Cellの場合はSPUのローカルメモリ上に置かれることになる。共有メモリベースの場合でもキャッシュを考慮した配置をする必要がある。具体的には、データのアライメントをそろえる必要がある。メインメモリ上で計算を行う逐次型プログラムと異なり、 コピーのコストを払ってでもデータを分割し、複数のCPUで独立に処理する必要がある。特に、DMA中心のアクセスになるCellの場合は、 コピーしやすいように、数Kbyte毎の配列にする方が良い。 <p> Cellの場合はさらにコードもローカルメモリ上に置かれるために、 コードをロードする仕組みも必要になる。 <p> <hr> <h3><a name="content006">同期の問題</a></h3> ここで言う同期は、複数のCPUがデータの待ち合わせ、または、整合性を維持するために、他のCPUとの待ち合わせを行うことである。従来のマルチCPUでは、並列度が低いために同期は希であり、キャッシュ上のSpin lock を用いることが多かった。これは、メモリの特定の場所をtest and set 等の特殊な命令で繰り返しアクセスして待ち合わせる手法である。Unix OSのkernel、POSIX Thread など同期機構の実装に使われている。 <p> Many Core では、待ち合わせを行うと並列度が下がってしまうので、 同期自体を減らす必要がある。そのためには、各CPUが独立に(Lock無しに)データにアクセス出来るようにデータを分割すれば良い。Cell では、 SPUがローカルメモリを持っているので、そちらにコピーすることになる。 しかし、SPUはメインメモリからデータを取得する必要があるので、その取得の際には同期を取る必要がある。 Cellでは、SPUとPPU間の同期にはMail box というFIFOメッセージ キューが用意されていて、readch,writech という命令でSPUからアクセスする。Spin lock と違って、メッセージ交換なので待ち合わせを避けることが可能である。 <p> 共有メモリベースのシステムの場合でも、同じ場所をアクセスする場合はキャッシュの競合が生じるので、コピーなどを用いて領域の分割を行う必要がある。Thread local などを用いる場合もある。 <p> 複数のCPUが出力する結果を一つのキューに挿入するようなことをすると、 挿入時に必ず同期が必要になるので同期のコストが高い。 <p> <hr> <h3><a name="content007">マルチスレッド</a></h3> 従来の共有メモリ型のマルチCPUでは、POSIX Thread を用いて並列実行 を実現することが多い。特にHyper Thread では、複数の命令ストリームを使って、メモリアクセス時等のの命令実行パイプラインのストールをスレッドを切替えて隠すことが出来る。しかし、Many Core の場合に、 個々のCoreに複数のThreadを割り当てるとワーキングセット(Threadが使用するデータ)の大きさが大きくなりキャッシュやローカルメモリに入らなくなる場合がある。 <p> スレッド(Hyper Thread)は本来、I/O待ちやメインメモリアクセス等に対して有効であり、ほとんどのデータがキャッシュやローカルメモリにあると考えられるMany Coreには向いていない。個々のタスクを実行するCPU 上で複数のスレッドを使用するメリットはほとんどないと思われる。 一方で、個々のCPUは細分化されたタスクを十分に持っていなければ恒常的な並列度を維持できない。 <p> 一方で、同期機構で待ち合わせを行う場合に、Spin lockを避けるとすれば、 条件付変数などのスレッドのタスクの待ち合わせ機構が必要となる。 <p> Many Core の台数にも寄るが、実行するタスクの管理を行うマネージャーを複数スレッドで構成し、そのうちの一つが、ポーリングベースで複数のCoreに対する待ち合わせを行うようにするのが良いと思われる。 Cellでは、SPURS\cite{spurs}という仕組みが提案されている。 <p> <hr> <h3><a name="content008">デバッグ</a></h3> 複数のCoreを走らせた状態でのデバッグは難しい。並列プログラムの特徴として、実行が非決定的(同じ状態で実行しても結果が異なる)ことがあり、バグの状態を再現することが難しいことがある。また、個々のCore上のデータを調べる必要があり、デバッガが複数のCoreを取り扱えることが必須である。 <p> <hr> <h2><a name="content009">Many Core 上のプログラムの作り方</a></h2> 本論文では、本研究室で作成したPS3上のレンダリングエンジンであるCerium Rendering Engine を例題として使う。詳細は別な論文\cite{cerium-akira}に譲り、ここでは簡単に記述する。 <p> Cerium は、Scene Graph (3Dオブジェクトを木構造にしたもの)をフレームバッファ上にSPUを用いて描画するRendering Engine であり、教育用としてシンプルな構成を持っている。Cerium は、 <p> <pre> 1. Scene GraphのPolygonの座標から表示する 2. 座標の計算を行い PolygonPack を生成する 3. PolygonPack から、同じY座標を持つ線分の集合SpanPackを生成する 4. SpanPackを(Texture を読込ながら)Z bufferを用いて描画する。 </pre> という4つのタスクを持つ。並列実行は、Scene Graphの木、PolygonPack, SpanPack に対してデータ並列実行を行う。さらに、この4つが表示画面毎にパイプライン的に実行される。 <p> これらのタスクは、SPUで実行するために小さなセグメントに分割される必要がある。分割されたタスクを、PPUまたはSPUで実行するのはCerium task manager である。Task manager はタスク依存を解決する機能を持っていて、タスク依存が満たされたものをアクティブキューに入れ、SPUを起動する。SPUはアクティブキューから、処理するコードとデータを取得し自律的に実行を行う。 <p> Cerium Rendering engine を作るには、以下の手順に実装とテストを行う。 <p> <pre> 1. 普通のCで実装した Rendering algorithm 2. データ構造(PolygonPack, SpanPack)を導入したもの 3. コードをタスクに分割し、FIFOキューでシーケンシャルに実行する 4. タスクをSPUに割り当て並列実行する </pre> これにより、Algorithmの正しさを確認した上で並列実行に移行することが出来る。 <p> <hr> <h2><a name="content010">Continuation based C</a></h2> CbC (Continuation based C)は、Cからサブルーチンやループ構造を除いたCの下位言語であり、ハードウェアとソフトウェア、特に組込みシステムの記述言語として本研究室で提案している言語である。 <p> Cの関数の代わりに、 たコード・ セグメントという単位を持つ。コードセグメントには、入口に相当するInput interface と、出口に相当するParameterized goto 文が存在する。 <p> <center><img src="fig/code.eps"></center> <p> 以下は簡単なCbCのプログラムである。 <p> <pre> code fact(int n,int result, code print()){ if(n>0){ result *= n; n--; goto fact(n,result,print); } else goto (*print)(result); } </pre> 間接gotoと、直接gotoが、プログラムの単位の結び付きをボトムアップに規定して、自然なグループを構成する。 <p> CbCの継続は、Schemeなどの継続とは異なり環境(関数の呼び出し履歴)を持たない。 コードセグメントは、関数呼び出しではないので環境を持つ必要がない。 <p> Cにコードセグメントと引数つきgoto文を付加したCwCは、Cのスーパセット であり、 コードセグメント内から通常のCの関数を呼び出すことも可能ある。また、 通常の関数からコードセグメントへgotoしたり、コードセグメントから、 呼び出された関数へ値を戻すことも出来る。 <p> コードセグメントは状態遷移記述と対応しているので、ハードウェア記述 とも相性が良い。 <p> CbCコンパイラは、micro-C base のものと GCC base, TCC base のものが動いており、実用的に使うことができる。{\tt sourceforge.jp} 上で公開されている。 <p> <hr> <h3><a name="content011">CからCbCへの変換</a></h3> Cのスタックを明示的に構成することによりCのプログラムをCbCに変換することが可能である。 <p> <pre> j = g(i+3); </pre> のようなCの関数呼び出しは、 \verb+struct f_g0_save+ などの明示的なスタックの中身を表す構造体を用いて、 <pre> struct f_g0_interface *c = (struct f_g0_save *)(sp -= sizeof(struct f_g0_save)); c = sp; c->ret = f_g1; goto g(i+3,sp); </pre> のような形で、明示的なスタック操作に変換される。これは変換の一例であり、他の方法、例えばリンクトリストなどを用いても良い。 \verb+f_g1+ は、関数呼び出しの後の継続であり、\verb+g+ では、 <pre> code g(int i,stack sp) { goto (* ((struct f_g0_save *)sp)->ret) (i+4,sp); } </pre> のように間接的に呼び出される。スタックの中は、継続と中間変数などを格納する構造体である。スタックそのものは、 これらの構造体を格納するメモリである。 <p> これらの変換は自動的に行うことが出来き、試作変換系を実装した報告\cite{c2cbc}もあるが、実用レベルの変換系はまだ存在しない。 現在は変換と、その後の最適化はは手動で行う必要がある。 <p> <hr> <h3><a name="content012">CbCでの並列実行記述</a></h3> 並列実行記述ではタスクの生成と同期機構の記述が問題になる。Verilog やVHDLなどでも並列タスクの記述があり、POSIX Thread ではライブラリコールとして{\tt pthread_create}や{\tt pthread_mutex_lock}などがある。 <p> これらの動作記述は、マニュアルやFormal Description で示されている。 例えば、以下のような記述である。 <p> {\tt The pthread_mutex_lock() function locks mutex. If the mutex is already locked, the calling thread will block until the mutex becomes available. } <p> CbC ではad-hoc な並列記述プリミティブは必要ではなく、自分自身で並列実行を記述することが可能である。これは、コードセグメントには隠された情報が存在しないので、実行に必要な情報をすべてInput interface から取得できるからである。 <p> 実行キューを作成しCbC自体でSchedulerを記述することにより、 並列実行を記述する。この場合の並列実行単位はコードセグメントとなる。goto 文を規則的にscheduler へのgoto文に書き換えることにより、並列実行を記述することが出来る。 <p> 以下は、CbCで記述した Dining Philosopher の状態の一部である。 <pre> code pickup_rfork(PhilsPtr self) { if (self->right_fork->owner == NULL) { self->right_fork->owner = self; goto eating(self); } else { goto hungry2(self); } } </pre> これを並列実行するためには、 <p> <pre> code pickup_rfork(PhilsPtr self, TaskPtr current_task) { if (self->right_fork->owner == NULL) { self->right_fork->owner = self; self->next = eating; goto scheduler(self, current_task); } else { self->next = hungry2; goto scheduler(self, current_task); } } </pre> という形に記述を変える。Scheculer の実装は例えば、FIFOであれば、 <p> <pre> code scheduler(PhilsPtr self, TaskPtr list) { TaskPtr t = list; TaskPtr e; list = list->next; goto list->phils->next(list->phils,list); } </pre> という形になる。このように自分自身で並列実行スケジューラを記述できることがCbCの特徴である。同期機構であるが、ここでは{\tt right_fork}の排他制御は、 コードセグメントが同時に実行されることはないので、自動的に保証されている。条件付変数のような待ち合わせを実現したい場合は、 TaskPtr への操作として実現すれば良い。 <p> <hr> <h3><a name="content013">CbCでの並列実行の実装</a></h3> FIFO scheduler を例えば Cell のSPUのactive task queue への挿入とし、active task queue を各SPUが自律的に取得するようにする(SPU scheduler)と、実際にCbCのコードセグメントを並列実行することが出来る。 <p> FIFO schedulerと実際の並列実行の同期機構が一致するようにするのは、一般的には自明ではない。同期機構をコードセグメントで記述 して、SPU scheduler によって実現しても良いし、コードセグメント 内部で、例えば、{\tt pthread_mutex_lock}を呼び出しても良い。 <p> <hr> <h2><a name="content014">CbCでのCellのプログラムの流れ</a></h2> CbCを用いて、Many Core Architecture のプログラムを作成する流れは以下のようになる。 <p> <pre> 1. C によりアルゴリズムをシーケンシャルに記述する 2. データを並列用に分割した構造に変更する 3. Cの記述をCbCの記述に変換する(必要な部分のみ。手動) 4. コードセグメントを並列実行用に分割する 5. FIFOスケジューラにより動作を確認する 6. SPUスケジューラによりCell上での動作を確認する </pre> これらの各過程すべてでエラーが入る可能性がある。また、 論理的なエラーだけなく、仕様に沿った十分な性能が出るかどうかも検証する必要がある。 <p> 1 の段階は通常のCのプログラミングであり、この部分がちゃんと動くことが必須である。この段階では、入力に対して出力が一意に決まる状況であり、テストは容易である。バグも実行トレースの二分法により容易に行うことが出来る。 <p> 4段階まではプログラム変換の問題であり、一つ前の段階と同じ結果を得られるかどうか検証する必要がある。 <p> 5 段階以前はアーキテクチャに依存しないので、ターゲット が開発途中の段階でも記述することが可能である。しかし、 5段階では、FIFOスケジューラの替わりに、Randomスケジューラなどを使うことができ、並列実行特有の非決定的な実行が導入される。 <p> 非決定的な実行は、クロックベースのハードウェアでは入力の任意性から生じることが多い。ハードウェアでも複数のタスクを使用したり、外界と相互作用する場合は非決定的な実行が現れる。 <p> 段階5では、これらの非決定的な実行でも4段階までと同じ仕様を満たすことを検証する必要がある。これは、 逐次型のプログラムでは出て来ない問題である。 <p> 段階6では、段階5まできちんと動いていれば、問題なく動作すると期待される。しかし、FIFOスケジューラとSPUスケジューラでは、同期機構の実現が異なることがある。これは、並列実行と同期機構のの粒度と意味論が異なるために起きると考えられる。 <p> ここで、段階1が仕様であり段階5が実装であると考えることもできる。実際のプログラムとは別に、 実行時に満たして欲しい仕様の記述がある場合もある。 これらの記述は、例えば、「計算がいつか終る」 等の時相論理的な記述になる。時相論理としては、 LTTL\cite{LTTL}, CTL*\cite{CTL}, ITL\cite{ITL}などを使うことができる。 <p> <hr> <h2><a name="content015">CbCでのCellのプログラムの検証</a></h2> CbCでの検証は、プログラム作成の各段階で行われる。 CbC では実行要素はコードセグメントであり、そのInput interface の値により動作は一意に決まる。 従って、検証はコードセグメント単位良い。コードセグメント 内部の正当性はテストあるいは証明こ行われるべきである。 <p> <hr> <h3><a name="content016">コードセグメントの入出力テスト</a></h3> これは、通常のプログラムのテスト手法と同じであり、 FIOスケジューラを導入する前の段階では、入力と出力に対応するテストを行う。 <p> コードセグメント毎にテストデータを作成するべきであるが、結果の正しさを確認するプログラムを書く必要とする場合もある。 <p> データ及びコードの分割が終った段階では、データをMulti Core CPUがアクセスできるようにコピーするコードが入ることがある。このコピーは、FIFOスケジューラレベルでは、ポインタ渡しに避けても良い。しかし、 コピーコード自体にエラーが出る場合も多い。例えば、 Cellでは、MFCによるDMAは64bit alignmentが必要であり、 これが満たされないと例外が発生してしまう。 <p> <hr> <h3><a name="content017">FIFOスケジューラレベルでのテスト</a></h3> FIFOスケジューラレベルのテストでは、非決定性が導入される。Cell では組み込まれたSPUは、すべて決定的に動作するが、データによってSPUの演算の終了結果は異なり、結果的に非決定性が生じる。 <p> これらの非決定性を、網羅的に調べることも可能であり、 モデル検査\cite{model-checker}と呼ばれる。 <p> CbCでは、状態を記録しながら、すべての可能な非決定的実行を行 うスケジューラを実装することが可能である。 <p> <pre> メモリ状態をデータベースから調べる すでにあれば、一つ前の状態に戻して他の実行を探す なければ、一段深い実行に進み状態を探す </pre> という形である。実際の実装は以下のようになっている。 <p> <pre> code tableau(TaskPtr list) { if (lookup_StateDB(&st, &state_db, &out)) { // found in the state database printf("found %d\n",count); while(!(list = next_task_iterator(task_iter))) { // no more branch, go back to the previous one TaskIteratorPtr prev_iter = task_iter->prev; if (!prev_iter) { printf("All done count %d\n",count); .... } printf("no more branch %d\n",count); depth--; free_task_iterator(task_iter); task_iter = prev_iter; } // return to previous state // here we assume task list is fixed, we don't have to // recover task list itself restore_memory(task_iter->state->memory); printf("restore list %x next %x\n",(int)list,(int)(list->next)); } else { // one step further depth++; task_iter = create_task_iterator(list,out,task_iter); } goto list->phils->next(list->phils,list); } </pre> この検証系は、SPUを使った実機上で動かすには、SPU内部のメモリを記録するなどの工夫が必要となる。また、探索空間が膨大になる場合もある。 <p> 探索空間を小さくするには、並列実行の粒度を大きくしたり、メモリの状態を抽象化したりする方法が考えられる。これらの手法は、CbC自身で記述することが可能である。 <p> <hr> <h2><a name="content018">本手法の利点と欠点</a></h2> <hr> <h2><a name="content019">学生による実際の実装の現状</a></h2> 変換の途中でad-hoc なコードが入る <p> テストしない <p> <hr> <h2><a name="content020">CbCを用いた検証手法と他の手法との比較</a></h2> Cの関数による分割 <p> SPIN <p> Java PathFinder <p> <h2><a name="content">Content</h2> <ol> <li><a href="#content000"> title-e: Self descriptive verfication in Continuation based C and it's application to Cell architecture</a> <li><a href="#content001"> abstract-e:</a> <li><a href="#content002"> Multi core system</a> <li><a href="#content003"> Many Core 上のプログラムの特徴</a> <li><a href="#content004"> 定常的な並列度の必要性</a> <li><a href="#content005"> プログラムとデータの分割</a> <li><a href="#content006"> 同期の問題</a> <li><a href="#content007"> マルチスレッド</a> <li><a href="#content008"> デバッグ</a> <li><a href="#content009"> Many Core 上のプログラムの作り方</a> <li><a href="#content010"> Continuation based C</a> <li><a href="#content011"> CからCbCへの変換</a> <li><a href="#content012"> CbCでの並列実行記述</a> <li><a href="#content013"> CbCでの並列実行の実装</a> <li><a href="#content014"> CbCでのCellのプログラムの流れ</a> <li><a href="#content015"> CbCでのCellのプログラムの検証</a> <li><a href="#content016"> コードセグメントの入出力テスト</a> <li><a href="#content017"> FIFOスケジューラレベルでのテスト</a> <li><a href="#content018"> 本手法の利点と欠点</a> <li><a href="#content019"> 学生による実際の実装の現状</a> <li><a href="#content020"> CbCを用いた検証手法と他の手法との比較</a> </ol> </body></html>