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)を持つ
    • SPEからメインメモリへは直接アクセスできない
      • SPEが持つMFC(Memory Flow Controller)へ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 の実行をパイプライン化している。 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 終了のメールを減らすことが出来る。 TaskArrayを導入することによって、wait time が削減された。 これにより、並列度が向上した。

  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. 他のアーキテクチャへの対応

    PS3 が Linux をサポートしなくなっため、これ以上のCell上での実験が困難になってきている。
    そこで、汎用マルチコア向けのパラレルタスクのサポートを行った。

  17. 他のアーキテクチャへの対応

    異なるアーキテクチャで動作させるにあたり、アーキテクチャの依存を吸収できるインターフェイスが望ましい。
    現在のSPEからのメモリアクセスは直接DMA転送を行うのではなく、MemorySegment API を用いて記述している。 MemorySegment API は、読み込んだデータの LSへのLRU方式のキャッシュをサポートする。そのため無駄なデータの転送が 削減された。 このAPIを用いる前は、Task内部で直接DMA転送を行っており、一度LSに読み込んだデータを再利用する機構がなかった。 このMemorySegmentのAPIには MainMemory のアドレスが用いられており、Cell 以外のアーキテクチャでも問題なく動作する。

  18. Ceriumの改良-MemorySegment(1/6)

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

  19. Ceriumの改良-MemorySegment(2/6)

  20. Ceriumの改良-MemorySegment(3/6)

  21. Ceriumの改良-MemorySegment(6/6)

    MemorySegment を導入し、

  22. まとめ

    並列プログラミングフレームワーク Cerium の改良を行った。
    以上の改良を行い、稼働率の向上、Cellのみでなく、他の汎用マルチコアCPUへの対応にも成功した。

  23. OpenGL との比較

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

  24. 今後の課題

  25. /*end*/