並列プログラミングフレームワーク Cerium の改良

金城　裕

琉球大学理工学研究科情報工学専攻

研究背景と目的(1/2)

当研究室では、マルチコアCPU上での開発を支援するたの、並列プログラミングフレームワーク Cerium を開発し、学生実験で使用している。本研究では Cerium の信頼性の向上を目的とし、改良を行った (信頼性 = 仕様通りに動作する)
マルチコア上の並列プログラミングでは

並列処理部分の特定や同期処理を適切に行わなければ、台数効果は得られない。
再現性ないバグなどが発生する可能性がある
アーキテクチャを理解し最適なプログラムを書く必要がある

など信頼性のあるプログラムを開発するには逐次プログラミングよりも技術と手間がかかる問題がある
Cell上でのゲーム作成を行う学生実験でも、講義期間中に作品が一定のレベルに達しない問題が生じた。そこで学生実験での使用を考慮したフレームワーク Cerium を開発した

研究背景と目的(2/2)

Cerium を用いて期間中のゲームの作成が可能になった。しかし学生実験での使用や、例題の実装を行い　Cerium の信頼性が十分でない点が明らかになった。

仕様通りの稼働率がでない
アーキテクチャ依存の記述が含まれている

以上の問題点を解決するため

ソフトウェアMailQueueの実装
TaskをグルーピングするTaskArrayの実装
明示的なDMAロードを隠蔽するMemorySegmentのAPIの実装

などの改良を行い、信頼性のある並列プログラミングフレームワークを目指す。

発表構成

Cellの機能
Ceriumの構成
Ceriumに行った改良とその効果

TaskArrayの実装(Mailの待ち時間の削減)
ソフトウェアMailQueueの実装(Mailの待ち時間の削減)
MemorySegmentの実装(アーキテクチャ依存記述の隠蔽)

まとめ
今後の課題

Cell Broadband Engine

研究、実験の題材となった Cell Broadband Engine とは、

ソニー、SCE、 IBM、東芝によって開発されたプロセッサ
マルチコアで、9つのコアを持つ

制御用コア PorwerPC Processor Element 1基
演算用コア Synergistic Processor Element 8基 (実験で使用できるのは6基)
各コアは Element Interconnect Bus を経由してデータアクセスを行う

Cellの機能(DMA転送)

Cell の SPE は直接 MainMemory にアクセスできない。明示的な DMA 転送命令を用いてデータにアクセスする。転送するデータの条件として

16アラインメントに揃える
16byte の倍数のサイズでなければならない
一度の転送は16KB の大きさまでできる

プログラムが明示的にDMA命令を発行して、データ転送を行う

Cellの機能(Mailbox)

PPE と SPE の通信には Mailbox を用いる

PPE と SPE 間で32ビットメッセージの交換ができる
Mail の Queue は3種類

SPU inbound Mailbox: PPE -> SPE
SPU Outbound Mailbox: SPE -> PPE
SPU Outbound interrupt Mailbox: SPE -> PPE (割り込み)

Cerium

Cerium とは

並列プログラミング用のフレームワーク
学生実験での使用を考慮して PS3/Cell, Linux, MacOSX で動作する
Ceriumの構成

TaskManager
RenderingEngine
SceneGraph

TaskManager

TaskManager とは Task のスケジューラ

Task とよばれるデータ構造を提供
ユーザは処理(単位は関数に近い)を Task で記述していく
定義されたTask は、Task 情報に沿って各コアに処理を割り振られる

Task で記述された部分の、自動的な並列処理スケジューリングを行う。

RenderingEngine(1/2)

PS3 では Graphics Engine の仕様が公開されていないので、独自の RenderingEngine を開発した。 Task で記述され、主に3つの Task から構成される

CreatePolygonTask

モデリングデータを、三角形のポリゴンに変換する

CreateSpanTask

ポリゴンを水平な線(Span)に分割する

DrawSpanTask

Span を Texture とマッピングし画面に出力する

RenderingEngine(2/2)

例: Cube のモデリングデータの場合には、以下のように Task が働く。

SceneGraph

ゲームのシーンを構成する木構造のグラフ。各 Node がゲームのオブジェクトになる。オブジェクトには Move 関数と collision 関数が設定でき、ステイトパターンで入れ替える。

Cerium の改良(Mailの待ち時間)

RenderingEngine を用いた例題で、ball bound, panel がある。(FPS = Frame per second)

	FPS	DMA転送待ち割合	mail待ち割合	SPE稼働率
ball bound	30.2	1.8%	74.3%	23.7%
panel	4.0	21.3%	11.1%	67.6%

panel

解像度1980x1080の一枚の画像の描画行う。

ball bound

球が跳ねる例題。

ball bound では Mail 待ちが約70%、稼働率23%と十分な稼働率ではない。(panel は ball bound より描画の処理が重く、その分稼働率が高くなっている)
アムダールの法則より稼働率がでないとマルチコアの性能は発揮されない。フレームワークとしての信頼性が十分でない問題がある

Mail 通知のスケジューリング

稼働率を向上させるために、Mail の待ち時間を削減する。

Cerium では SPE が Mail で待ち時間が発生するタイミングは2つ

TaskList を待つ場合
SPE から Mailbox へ書き込む際の待ち

TaskListのMail待ち

TaskList は処理する Task の List である。PPE で生成され SPE へ Mail で通知される

TaskList が生成され SPE に通知されるまで、SPE に待ち時間が発生する。

Mail の書き込み待ち

Task が終了した際と TaskList が終了した際に SPE が Mailbox へ書き込みを行う(依存関係解決のため)。Outbound Mailbox はサイズが1なので、他のMailが書き込まれている場合、それが PPE側から読み込まれるまで、待つ。

TaskList が生成され SPE に通知されるまで、SPE に待ち時間が発生する。

TaskArray(1/3)

Task毎に依存関係の解決のため、Mail を通知する。バリア同期など複数の Task が同じ Task を待つ場合にはグルーピングできる。 Task のグルーピングを可能にするために TaskArray を実装した。

TaskArray(2/3)

例えば　TaskListのサイズが4, TaskArray のサイズが4の場合、Task が8個の場合

グルーピングされるため Task 毎の Mail 回数が減る。TaskList の要求回数が減る。そのため Mail の待ち時間が入る箇所が削減され、Mail の待ち時間自体の削減につながる。

TaskArray(3/3)

TaskArray の効果を示す

ballbound
TaskArray	FPS	DMA転送待ち時間	mail待ちの割合	SPE稼働率
なし	30.2	1.8%	74.3%	23.7%
あり	32.2	2.5%	66.7%	30.8%

panel
TaskArray	FPS	DMA転送待ち時間	mail待ちの割合	SPE稼働率
なし	4.0	21.3%	11.1%	67.6%
あり	4.2	22.5%	5.7%	71.8%

TaskArray を ball bound, panel の DrawSpanTask に適応。FPS、稼働率の向上。Mail 待ちの時間が削減された

MailQueue(1/3)

Task 毎の Mail 書き込み時の待ち時間を削減するため、MailQueue を実装した。

SPE から Mailbox に書き出せない場合に MailQueue へと書きだす
MailQueue に Mail がある場合は、MailQueue から Mailbox へ書き出す
MailQueue に残っている Mail は TaskList のTask を消化した時点で、すべて書き出す処理を挟む

MailQueue(2/3)

Mailbox に書き込めない場合は、MailQueue に書き込む例

MailQueue(3/3)

MailQeueuの効果

ball bound
MailQueue	FPS	DMA転送待ち時間	mail待ちの割合	SPE稼働率
なし	32.2	2.5%	66.7%	30.8%
あり	41.7	3.3%	56.8%	40.0%

panel
MailQueue	FPS	DMA転送待ち時間	mail待ちの割合	SPE稼働率
なし	4.2	22.5%	5.7%	71.8%
あり	4.2	23.7%	4.1%	72.3%

ball bound , panel ともに Mail 待ち時間が削減され、稼働率、FPS の向上につながった。

Ceriumの改良(アーキテクチャ依存記述の隠蔽)

RenderingEngine の Task内では明示的にDMA転送命令を記述している。

処理するデータ構造上の理由、Task内でのデータロードが必要
DMA転送命令は Cell アーキテクチャ依存の記述
他のアーキテクチャなどでは不要

フレームワークとしての汎用性に欠ける。アーキテクチャ依存の記述を隠蔽できるAPIが必要になった。

MemorySegment(1/6)

明示的なDMA転送命令を隠蔽するため MemorySegment を実装した MemorySegemnt はデータ構造。LS 内のデータを管理する。

一定のメモリを確保し、ハッシュで管理(LRU方式)
API 内部で自動的なキャッシュを行う (サイズは任意に設定できる)
dma 命令を MemorySegment というデータ構造を操作する命令に置き換える

dma_load -> get_segment
dma_store -> put_segment
dma_wait -> wait_segment

MemorySegment(2/6)

MemorySegment(3/6)

MemorySegment(4/6)

明示的に記述したDMA転送命令の例

loop() {

  tmp_data = get_data;
  get_data = send_data;
  send_data = tmp_data;

  dma_wait(WAIT_STORE);

  dma_store(send_data, send_addr, data_size, WAIT_STORE);
  dma_load(get_data, get_addr, data_size, WAIT_LOAD);

  dma_wait(WAIT_LOAD);

  calc(get_data);

}

MemorySegment(5/6)

MemorySegment を適応させた例

loop() {

  wait_segment(put_ms);

  put_ms = get_ms;

  put_segment(put_ms);
  get_ms = get_segment(get_addr, ml);

  wait_segment(get_ms);
  get_data =  get_ms->data;

  calc(get_data);
}

MemorySegment(6/6)

MemorySemgment を導入

アーキテクチャ依存の記述を隠蔽することに成功した
汎用的な Task 内でのデータ転送APIとして使用でき
Core i7, Xeon などの汎用のメニーコアにも対応可能

まとめ(1/2)

並列プログラミングフレームワーク Cerium の改良を行った。

MailQeueu, TaskArry を実装、導入した。その結果 Mail の待ち時間の削減、稼働率と FPS の向上に成功した
MemorySegment を実装し、汎用的なデータ転送APIが利用できるようになった。Cell アーキテクチャ依存の記述の隠蔽に成功

以上の改良を行い、稼働率の向上、アーキテクチャ依存のコードの排除に成功し、フレームワークとしての信頼性が向上した。

まとめ(2/2)

改良の効果を示す

ball bound
	FPS	DMA転送待ち時間	mail待ちの割合	SPE稼働率
改良前	30.2	1.8%	74.3%	23.7%
改良後	41.7	3.3%	56.8%	40.0%

panel
	FPS	DMA転送待ち時間	mail待ちの割合	SPE稼働率
改良前	4.0	21.3%	11.1%	67.6%
改良後	4.2	23.7%	4.1%	72.3%

OpenGL との比較

学生実験で作成されたシューティングゲーム「SuperDandy」を例題に OpenGL と比較。OpenGL は PPE 1基のみを使用。Cerium は SPE6基+PPE1基を使用した。

シューティングゲーム
	OpenGL	Cerium	性能差
SuperDandy	17.5 FPS	49.5 FPS	2.9 倍

今後の課題

SceneGraph 部分の Task 化

Task 化によって並列化率の向上

自動的な依存関係の解決

扱うデータから Task の依存関係がわかる
ユーザが複雑な依存関係を設定しない

プログラムとデータの On demand Load

プログラムコードはすべて LS に置いている
LS の容量を圧迫しプログラムが動作しなくなる
すべてのデータを扱う包括的なデータ構造が必要

/*end*/