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

    金城　裕

    並列信頼研究室

  2. 研究概要

    本研究では並列プログラムフレームワーク Cerium の改良を行い、並列処理の並列度向上とCell以外のマルチコアCPUへの対応に成功した。
    • アムダールの法則より、プログラム全体の並列化率が低ければマルチコアの性能を活かすことができない
    • 現在の Cerium を用いたプログラムの開発では、高い並列度が保証されない
    • Cerium はPS3/Cell での並列処理を行えるが、当初はCell向けに作られた為、他の汎用マルチコアCPU に対応していない

    Cerium の他CPUへの対応と、自明な並列度があるレンダリングとゲーム処理を例題に、高い並列度の維持を目的とする

  3. 発表構成

  4. Cell Broadband Engine

    研究、実験の題材となった Cell Broadband Engine とは、
    • 1基のPPEと8基のSPEがリングバス(EIB)で構成されている。動作クロックは3.2GHz(実験で使えるSPEの数は6基)
    • リングバスのデータ帯域幅は1サイクルあたり最大96byte(3.2GHz駆動時には307.2GB/sec)
    • SPEは256KBのLocalStore(LS)を持つ
    • PPEとSPEはMFC(Memory Flow Controller)を持つ
    • SPEからメインメモリへは直接アクセスできない
      • SPEが持つMFCへDMA命令を送り、データの転送を行う

  5. Cellの機能

    Mailbox
    • SPEのMFC内にあるFIFOキュー
    • PPE と SPE 間で32ビットメッセージの交換ができる
    • Mail の Queue の種類
      • SPU inbound Mailbox: PPE -> SPE (キューのサイズは4)
      • SPU Outbound Mailbox: SPE -> PPE (キューのサイズは1)

    Outbound Mailbox へ Mail を書き込む際、キューがいっぱいの時は、PPE 側から読み込まれるまで待つ。

  6. Cerium

    Cerium の構成
    • TaskManager
      • ユーザが定義したTaskを管理し、各コアに割り当てる
    • RenderingEngine
      • オブジェクトを画面に描画する
      • 3種類のTaskから構成される
    • SceneGraph
      • ゲームのシーンを作成し、それを切り替えながらゲームを進行する
      • OpenSceneGraphのようなもの

  7. TaskManager

    TaskManager は、Taskと呼ばれる分割された各プログラムを管理する。Task の単位 はサブルーチンである。Task 同士の依存関係を考慮しながら実行していく。

    Task を生成する際に、以下のような要素が設定可能である

    • input data, output data, parameter
      　これらは関数でいうところの引数に価する
    • cpu type
      　Task を PPE または SPE のどちらで実行するのかを示している
    • dependency
      • 　他の Task との依存関係を示している

  8. TaskManager

    • 生成された Task は TaskList としてまとめられ SPE で実行される
    • SPE 側では受け取った TaskList から Task を抜き出し、パイプライン的に実行していく

  9. Mailのやり取り

    • SPE と PPE 間の同期は Mail のやり取りを行う

    • Mailのタイミング

      • SPE -> PPE
      • タスクの終了(Taskの依存関係の解決のため)
      • 新しい TaskList のリクエスト

      PPE -> SPE
      • 新しい TaskList の送信

  10. PPEとSPEで行われるパイプライン処理

    PPEとSPE 間で Mail を介して Task の実行をパイプライン化している。 PPE が SPE側 から送られてくる Mail の受け取りは PPE 側からポーリングして確認しており、PPE のMain ループで定期的に チェックしている。
    パイプラインがうまく動作する例 当初はこれでうまくパイプラインが実行されていると思われていたが、うまくいかないパターンが存在することが明らかになった。

  11. PPEとSPEで行われるパイプライン処理

    PPE 側で実行される Task の処理が長い場合に、Mail チェックの頻度が少なくなる。 Outbound Mailbox がひとつの Mail で占有される時間が長くなり、SPE 側の終了した Task の終了Mail が書き出せなくなる。 そのため、書き込み待ちが発生し、SPE に待ち時間が発生する。
    パイプラインが崩れてしまう例 これが並列度の低下を招いている。

  12. PPEとSPEで行われるパイプライン処理

    そこで、その問題を解決するため、一つ目のアプローチとして Outbound Mailbox と Task の終了処理の間に ソフトウェア MailQueue を導入した。 Outbound Mailbox がいっぱいの場合その Queue に Task 終了 Mail を挿入し、次の Task が実行されるようになった
    MailQueueを導入によりパイプラインが正常に動作している例 そのため、SPE の待ち時間の削減に成功した

  13. PPEとSPEで行われるパイプライン処理

    二つ目のアプローチとして、複数の Task を TaskArray としてグルーピングする方法をとった。 依存関係が線形である Task は TaskArray としてまとめることにより、Task 終了のメール自体を減らすことが出来る。 これによっても、待ち時間の削減に成功した

  14. 改良効果の測定

    RenderingEngine を用いて、効果を計測した。レンダリングの例題として、ball bound と panelを用いた。
    ball bound は赤いボールが跳ねる例題である。描画領域が画面の中でボールの部分だけであり、描画領域が狭い。
    panel は画面一面に画像を描画する例題である。描画領域が最大である。

  15. 改良効果の測定

    ballbound
    改良項目 FPS mail待ちの割合 SPE稼働率 SPE稼働率の差分
    改良なし 30.2 74.3% 23.7% -
    TaskArray適用後 32.2 66.7% 30.8% +7.1%
    MailQueue適用後 41.7 56.8% 40.0% +10.8%
    panel
    改良項目 FPS mail待ちの割合 SPE稼働率 SPE稼働率の差分
    改良なし 4.0 11.1% 67.6% -
    TaskArray適用後 4.2 5.7% 71.8% +4.2%
    MailQueue適用後 4.2 4.1% 72.3% +0.5%
    改良を加え 各例題 のFPS、稼働率の向上。Mail 待ちの時間が削減され、並列度が向上したといえる

  16. アーキテクチャ依存記述の隠蔽

    Cerium では Task内部でのデータ転送を行うときは、DMA転送を行ってた。Core i7 や Xeon のような SharedMemory に対応するために DMA転送は不要である
    そこで、Task内部でのデータ転送を抽象化する MemorySegment を実装した。
    • MemorySegment はデータ構造である
    • MainMemory と SPE LS をマッピングする
    • LS 内に一定のメモリを確保し、キャッシュ機能を持つ
    • キャッシュはLRU方式で管理する

    このMemorySegmentのAPIには MainMemory のアドレスが用いられており、Cell 以外のアーキテクチャでも問題なく動作する。

  17. MemorySegmentのgetの様子

    MemorySegment の API として、get_segmentがある。指定された MainMemory のアドレスから SPE LS へのデータロードが可能である。

  18. MemorySegment

    MemorySegment を導入し、

  19. まとめ

    並列プログラミングフレームワーク Cerium の改良を行った。
    以上の改良を行い、約18%稼働率の向上、とShardMemoryマルチコアCPUへの対応にも成功した。

  20. OpenGL との比較

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

  21. 今後の方針

    • 自動的な依存関係の解決
      • 扱うデータから Task の依存関係がわかる
      • ユーザが複雑な依存関係を設定しない
    • DataSegmentの設計
      • MemorySegmentでは、Task 内でのデータロードを抽象化した
      • Task内でのデータロードだけでなく、すべてのデータや扱うプログラムなどを管理する包括的なデータ構造が必要になる
    • そのDataSegment の設計は分散ネットワーク環境にも適応でき、それについては次の赤嶺が発表する
    • また現在 CeriumはIntel Xeon上に移行され、並列動作する。その結果は當間が卒業研究として発表する
    • 彼らの発表にも乞うご期待!

  22. 発表文献

    • 金城裕,河野真治,多賀野海人,小林佑亮. ゲームフレームワーク Cerium TaskMan- ager の改良, 情報処理学会システムソフトウェアとオペレーティング・システム研 究会 (OS), April, 2011
    • 金城 裕 , 河野 真治. Fine grain Task Manager Cerium のチューニング, 日本ソフト ウェア科学会第 27 回大会論文集, Sep, 2010