.. include:: s5defs.txt
.. include:: <mmlalias.txt>

===========================================
Cell 用の Fine-Grain Task Manager の実装
===========================================

*発表者*
  **宮國渡**

*指導教官*
  **河野真治**

*所属*
  **琉球大学 理工学研究科 情報工学専攻 並列信頼研究室**



研究の背景
===================

現在、学生実験で PS3Linux を用いてゲーム開発を行っているが、
学生には困難であることがわかってきている

+ :maroon:`問題1` : :underline:`Cell アーキテクチャプログラミング`

  + Many Core による並列プログラミング

    (データ、コードの分割の必要性)

  + Cell の仕様 (DMA、データのアライメント、etc..)

+ :maroon:`問題2` : :underline:`ゲーム開発用の Framework が無い`

実験期間の大半を Cell の勉強に費やさねばならず、
開発されるゲームのレベルが例年一定以上にならない


研究目的
============

Many Core Architecture を用いた並列プログラムの開発をサポートするフレームワーク :maroon:`Fine Grain Task Manager` 、それを組み込んだ、
PS3 ゲーム開発用フレームワーク :maroon:`Cerium` を提案する

- 動作環境

  - Mac OS X、Linux、PS3(Cell)

- Fine Grain Task の単位

  - サブルーチン

- Cerium を用いた開発行程

  1. 逐次型プログラム
  #. データやコードを分割したプログラム
  #. 並列に動かすプログラム

  各段階で信頼性を確保しながら開発を進める


研究目的 (Con't)
==================

**Cerium**

3 つの機能で構成されている

- 独自の :maroon:`Rendering Engine`
- ゲームに登場するオブジェクトやルールなど、ゲームを構成する要素を
  木構造として持つ :maroon:`Scene Graph`
- Rendering Engine や Scene Graph の処理単位を Task とし、複数の Core へ
  割り振りを行うカーネル :maroon:`TaskManager`

学生が Cell アーキテクチャを理解しながら、
期間内でゲーム開発が行える、シンプルな
マルチタスクフレームワークを目指す


発表の流れ
======================

- Cell アーキテクチャの概要
- Many Core プログラミングの特徴
- Task Manager の実装
- Cerium
- 比較
- まとめと今後の課題

Cell アーキテクチャの概要
===========================

- :big:`Cell アーキテクチャの概要`
- :silver:`Many Core プログラミングの特徴`
- :silver:`Task Manager の実装`
- :silver:`Cerium`
- :silver:`比較`
- :silver:`まとめと今後の課題`

Cell Broadband Engine
========================

.. image:: images/cell_arch.jpg
   :align: center
   :width: 480px
  
- 1個の PPE と 8 個の SPE がリングバスで構成されている

  - Linux 側から使える SPE は 6 個

- SPE は :maroon:`256KB` の Local Store (LS) を持つ
- SPE からメインメモリへは直接アクセスできない

  - SPE が持つ MFC (Memory Flow Controller) へ
    :maroon:`DMA 命令` を送ることで行う

- SPE は 128 ビットレジスタを 128 個持っている

  - SIMD (Single Instruction Multiple Data) が可能
    (32bit のデータ4つを同時に演算)

Cell の基本機能
=======================

**DMA**

- メインメモリと LS 間でデータが転送される

**Mailbox**

- SPE の MFC 内にある FIFO キュー
  
- PPE と SPE 間で 32 ビットメッセージの交換に用いられる

  キューは 3 種類

  - SPU Inbound Mailbox : PPE |rightarrow| SPE
  - SPU Outbound Mailbox : SPE |rightarrow| PPE
  - SPU Outbound interrupt Mailbox : SPE |rightarrow| PPE (割り込み)

Many Core プログラミングの特徴
================================

- :silver:`Cell アーキテクチャの概要`
- :big:`Many Core プログラミングの特徴`
- :silver:`Task Manager の実装`
- :silver:`Cerium`
- :silver:`比較`
- :silver:`まとめと今後の課題`


定常的な並列度の必要性
========================

**Amdahl 則**
  プログラムの並列化率が低ければ、その性能を生かすことは出来ない

.. image:: images/amdahl.jpg
   :align: center
   :width: 360px

.. raw:: html

  <div align="center" style="font-size: large;">
    6 CPU を使っても、プログラムの並列化率が 8 割程度では<br />
    3倍程度の性能向上しか得られない
  </div>

Amdahl 則より、恒常的に並列プログラムの並列度を維持する必要がある


プログラム及びデータの分割
============================

プログラム中の並列度は、以下の形で取り出すことが可能

.. raw:: html

 <table>
   <tr>
     <td style="border: 1px solid black;">
       <img src="images/manycore_data_split.jpg" width="350">
     </td>
     <td style="border: 1px solid black;">
       <img src="images/manycore_pipeline.jpg" width="350">
     </td>
   </tr>
   <tr>
     <td align="center">データ並列</td>
     <td align="center">パイプライン処理</td>
   </tr>
 </table>

上二つの処理を行うには、プログラムとデータの適切な分割が必要

- プログラムの分割

  - for 文、木構造で処理する個々のステートメント

- データの分割

  - 分割できるデータ構造の採用が必要となる

二つの分割は自明には行えないことが多いため、工夫が必要


Many Core の同期
============================

**同期**
  複数の CPU がデータの待ち合わせ、または、整合性を維持するために、他の CPU との待ち合わせを行うこと

- 他の CPU と干渉するデータ入出力の場合、待ち合わせる必要がある

  - 待ち時間が無駄になる

- データ待ちの為にストップする状態を減らす

.. raw:: html

  <div align="center">
    &darr;
  </div>

- 各 CPU が独立に (ロック無しで) データにアクセスできる様にデータを分割すれば良い


並列プログラムの開発行程
================================

以下の5段階に置いて、実装とテストを行う

1. C によるシーケンシャルな実装

- アルゴリズムの確認

2. 並列実行を考慮したデータ構造を持つ実装

- データ構造が変化しても 1. と結果が同じになるかを確認

3. コードを分割し、それらをシーケンシャルに実行する実装

- この段階まではアーキテクチャに依存しない
- 二分法によるデバッグが可能


並列プログラムの開発行程 (Con't)
================================

4. 分割したコードを並列実行する実装

5. アーキテクチャに特化した実装

- Cell の場合は SIMD

4、5段階目でエラーが出た場合、一度 3. まで戻って
データ構造、プログラムの分割を確認する


Task Manager の実装
================================

- :silver:`Cell アーキテクチャの概要`
- :silver:`Many Core プログラミングの特徴`
- :big:`Task Manager の実装`
- :silver:`Cerium`
- :silver:`比較`
- :silver:`まとめと今後の課題`


Task Manager
================

.. raw:: html

  <table>
    <tr>
      <td>

Task と呼ばれる、分割された各プログラムを管理する

- Task はサブルーチン
- Task 同士の依存関係を考慮
- 実行状態になった Task を各 SPE に割り振る
- C++ で実装


  :maroon:`Task Manager User API`

.. class:: small

  +----------------------------------------------+
  | HTask* TaskManager::create_task(int ID);     | 
  |   Task の生成                                |
  +----------------------------------------------+
  | void* TaskManager::allocate(int size)        |
  |   実行環境のアライメントを考慮した allocator |
  +----------------------------------------------+

.. raw:: html

      </td>
      <td align="center">


:maroon:`Task API`

.. class:: small

  +--------------------------------------------------------------+
  |task->add_inData(int addr, int size);                         |
  |  Task の入力データの設定 (入力元アドレス、データサイズ)      |
  +--------------------------------------------------------------+
  |task->add_outData(int addr, int size);                        |
  |  Task の出力データの設定 (出力先アドレス、データサイズ)      |
  +--------------------------------------------------------------+
  |task->add_param(int param);                                   | 
  |  Task のパラメータ (32bit)                                   |
  +--------------------------------------------------------------+
  |task->wait_for(HTask \*wait);                                 |
  |  Task の依存関係の考慮                                       |
  +--------------------------------------------------------------+
  |task->set_cpu(CPU_TYPE type);                                 |
  |  Task を実行する CPU の設定                                  |
  +--------------------------------------------------------------+
  |task->spawn(void);                                            |
  |  task を ActiveQueue へ格納する                              |
  |                                                              | 
  |  TaskManager は ActiveQueue にある task を                   |
  |  SPE へ割り振る                                              |
  +--------------------------------------------------------------+
  
.. raw:: html

      </td>
     </tr>
   </table>


Task の生成
================

::

  HTask *task = manager->create_task(TASK_ID)
  task->add_inData(in, sizeof(int)*16); // 入力データは in から取得
  task->add_outData(out, sizeof(int)*16); // 出力結果は out へ
  task->spawn();

Task ID
  各タスクに割り振られているグローバルID

- 逐次型プログラムでは、Task に関数ポインタを持たせれば良い

- PPE と SPE ではアドレス空間が異なるため、
  単純に関数ポインタを持たせても意味が無い

- 予め SPE 上の領域に置いてある Task (関数) を選択して実行するために
  ID を指定する

- HTask が持つのは、SPE 上にある Task を実行するための情報


Task の依存関係の解決
=========================

TaskManager はタスク依存を解決する機能をもつ

.. class:: small

::

    /* task2 は task1、task3 の終了を待つ */
    task2->wait_for(task1);
    task2->wait_for(task3);

    /* Task が持つ依存関係の変数 */
    TaskQueuePtr wait_me;  // List of task waiting for me
    TaskQueuePtr wait_i;   // List of task for which I am waiting


.. image:: images/tm_task_depend.jpg
   :align: center
   :width: 430px


Task を実行させる CPU の選択
=============================

Task をどの CPU で実行させるかを明示的に選択できる

::

  /* SPE1で実行する */
  task1->set_cpu(SPE_1); 

  /* SPEのどれかで実行する */
  task2->set_cpu(SPE_ANY); 

  /* PPEで実行する  */
  task3->set_cpu(PPE); 

- PPE 内でもタスクの実行が可能
- Mac OS X や Linux で実行する場合、SPE_\* を指定したタスクは
  そのままメインスレッドで実行される
- 違う環境へプログラムを移行する場合

  - set_cpu で実行 CPU を変更する、もしくはそのままでもよい
  - 環境依存のプログラム変換はタスク内部だけになる


CPU スレッドスケジューラ
==========================

.. raw:: html

 <table>
   <tr>
     <td>

.. image:: images/tm_scheduler.jpg
   :align: center
   :width: 400px

.. raw:: html

     </td>
     <td>

- PPE から TaskList (Task の集合) を受け取る

- TaskList から Task を取り出し、パイプラインに沿って、
  ステージを遷移させながら実行していく

- TaskList が空になったら、次の TaskList 要求メッセージを PPE に送る

.. raw:: html

     </td>
   </tr>
 </table>


メインスレッドと CPU スレッド間の同期
=======================================

- 同期は 32 ビットメッセージの交換 (Mailbox) により行う

- 同期のタイミング

  :maroon:`SPE -> PPE`

  - タスクの終了
  - 新しい TaskList のリクエスト

  :maroon:`PPE -> SPE`

  - 新しい TaskList の送信

- メッセージ交換なので、スレッド間の待ち合わせは起こらない



例題 Bitonic Sort
=========================

Task Manager を用いて、学生が記述

.. image:: images/tm_sort.jpg
   :align: center
   :width: 350px

- ソートデータを複数のブロックに分割
- 隣り合ったブロックでソートするタスクを生成し、実行
- 次ステップでは1ブロックずらしてソート
- 上の手順を、分割ブロック数だけ繰り返す

例題 Bitonic Sort 実行結果
============================

- 整数データは 100 万
- SPE の数を変化させて実行速度を比較

.. image:: images/tm_sort_calc1m.jpg
   :align: center
   :width: 480px

- SPE 6 個で 5.1 倍
- Task Manager 自体のオーバーヘッドは問題ない

Cerium
================================

- :silver:`Cell アーキテクチャの概要`
- :silver:`Many Core プログラミングの特徴`
- :silver:`Task Manager の実装`
- :big:`Cerium`
- :silver:`比較`
- :silver:`まとめと今後の課題`

Cerium
=============
PS3ゲーム開発用フレームワーク

.. image:: images/cerium.jpg
   :align: center
   :width: 400px

- Rendering Engine

  - Cerium 独自

- Scene Graph

  - ゲームに登場するオブジェクトやルールなど、ゲームを構成する要素にもつ木構造

- Task Manager

  - Rendering Engine や Scene Graph の処理 (Task) を複数のSPEへ割り振る

Scene Graph
=================

.. image:: images/cerium_sg_tree.jpg
   :align: center
   :width: 95%

- Blender [#]_ で生成したオブジェクトを 独自の XML 形式で出力
- XML が持つ情報 (頂点座標、テクスチャ座標、イメージなど) から
  SceneGraphNode を生成
- ポリゴン情報の他に、オブジェクトの操作(move, collision) を持つ


.. class:: small

.. [#] オープンソースの3Dモデリングツール


Rendering 
=============

.. raw:: html

 <table>
   <tr>
     <td>

.. image:: images/rendering.jpg
   :align: center
   :width: 400px

.. raw:: html

     </td>
     <td>

SG2PP
  SceneGraph を操作後、ポリゴンに変換し PolygonPack (ポリゴンの集合)を生成する

PP2SP
 ポリゴンの中から、Span (ポリゴン内にあるx軸に水平な線分) を抽出し、
 SpanPack (Span の集合)を生成する

DrawSpan
   Span を使って 1 ラインずつ FrameBuffer に描画していく

.. raw:: html

     </td>
   </tr>
 </table>

Rendering Task のパイプライン
==============================

.. image:: images/rendering_pipeline.jpg
   :align: center
   :width: 80%
   :height: 165px

レンダリングはフレームが進む毎に全画面更新する

**フレーム**
  演算や描画の処理 1ループの間隔

1. 前フレームに抽出した Span を描画する
#. 現フレームのポリゴンから Span を抽出する
#. 次フレームのポリゴンを計算する

SG2PP、PP2SP、Draw の 3つのタスクが平行して処理できる


Cerium を用いたゲーム開発
===========================

.. image:: images/cerium_game.jpg
   :align: center
   :width: 450px

.. raw:: html

   <div align="center">
     SuperDandy3D
   </div>

- 3D シューティングゲーム
- Cerium を用いて学生が作成
- ジョイスティックやキーボードでの操作が可能

  - SDL を用いて入力値を取得している



ゲームの実行結果(速度検証)
=============================

.. raw:: html

  <table width="95%">
    <tr>
      <td align="center">

.. class:: small

ポリゴン数

.. class:: small

========== ======== 
  自機      250
---------- --------
  敵機       44
---------- --------
  背景       2
========== ======== 

.. class:: small

Mac OS X 以外は Frame Buffer へ直接出力

.. class:: small

Mac OS X は SDL 経由で出力している

.. raw:: html

      </td>
      <td>

=========================  =====================================
 Architecture              Speed (FPS : Frame Per Second)
-------------------------  -------------------------------------
 Mac OS X 10.5             5.7 FPS
-------------------------  -------------------------------------
 Linux (Fedora 10)          7.8 FPS
-------------------------  -------------------------------------
 PS3 SPE 1 個               8.1 FPS
-------------------------  -------------------------------------
 PS3 SPE 6 個               :maroon:`29.3 FPS`
=========================  =====================================

.. raw:: html

      </td>
    </tr>
  </table>

- SPE ６個で 1 個のものより 3.6 倍

- 現状

  - SceneGraph の演算を SPE で行っていない
  - SPE での処理に SIMD 演算を組み込んでいない

- 速度向上する余地あり

他システムとの比較
===============================

- :silver:`Cell アーキテクチャの概要`
- :silver:`Many Core プログラミングの特徴`
- :silver:`Task Manager の実装`
- :silver:`Cerium`
- :big:`比較`
- :silver:`まとめと今後の課題`


比較 - OSMesa (Gallium)
====================================================

- 先行研究 (神里)

  - 現在 PS3Linux からは :maroon:`GPU にアクセスできない`
  - :maroon:`フレームバッファは使用できる` ため、OSMesa を使用
  - OSMesa の機能の一部を SPE に乗せ、高速化に成功
  - ソースコードの複雑化を招いた

    - OSMesa の元々の実装の影響 (巨大なマクロ、構造体)

  - 以降のメンテナンスや機能の追加、改良が困難と判断
  - 独自に Rendering Engine を持つことに

- Gallium 

  - OSMesa の Cell Driver
  - OpenGL で動作
  - PS3 上のゲーム開発において、レンダリングのみを SPE に実装するのでは足りない

    - ゲームに登場するオブジェクトの計算 (衝突判定等)
    - Amdahl 則の問題

  - レンダリングだけでなく、ゲームオブジェクトも SPE で処理できるように
    しなければならない

- Cerium

  - SceneGraph、レンダリングを SPE 上で処理する


比較 - Gallium (Con't)
==========================

- 実行速度比較

  - 出力解像度は 1920x1080
  - 地球のテクスチャを貼った球体のオブジェクトを表示

.. raw:: html

  <table width="90%">
   <tr>
     <td>

.. image:: images/com_gallium.jpg
   :align: center
   :width: 350px

.. raw:: html

     </td>
     <td align="center">

.. class:: small

ポリゴン数 : 1984

.. class:: small

=====================  ===============
 Gallium (SPE 6 個)     5.4 FPS
---------------------  ---------------
 Cerium (SPE 1 個)      2.5 FPS 
---------------------  ---------------
 Cerium (SPE 6 個)     :maroon:`9.5 FPS`
=====================  ===============

.. raw:: html

      </td>
    </tr>
  </table>

- Gallium には OpenGL API の機能が全て乗っているわけではない
- Cerium とのレンダリングの機能の違い

  - 光源、アルファブレンディング、etc..

- Cerium、Gallium ともにまだ開発段階  

比較 - OpenGL
==========================

OpenGL
  オープンソースの3Dグラフィックスプログラムインターフェース

- 変換行列、光源、カメラなどの API を実装
- 親子関係の表現も可能

Cerium での OpenGL の使用の問題

- SceneGraph の OpenGL の API にあわせるオーバーヘッド
- SceneGraph は自身の変換行列を持っている

  - SceneGraph 単体でオブジェクトの操作は可能

- SceneGraph だけで問題ない


比較 - OpenCL 
=====================

**OpenCL** (2008年12月9日 策定)
  マルチコアCPUやGPU、その他のプロセッサによる、ヘテロジニアスコンピューティングのフレームワーク

.. image:: images/cp_opencl_plat.jpg
   :align: center
   :width: 350px

- Host から PE へ実行コマンドが送られる
- Host や OpenCL Device はコマンドの管理を行う kernel を持つ
- OpenCL Device 毎に独立したメモリ領域を持つ
- データ並列、タスク並列をサポート

比較 - OpenCL (Con't)
======================

**OpenCL**

- あらゆる Many Core Architecture に対応できるような汎用的な実装
- 開発環境にあわせた記述が必要
- 現在、Cell 用に実装されたものは無い

**Task Manager**

- Cell アーキテクチャに重きを置いた記述
- DMA によるメモリアクセスなど、決まった記述で開発できる
- 大幅なコードの変更無く Mac OS X や Linux など複数の環境で動作させることが可能

Task Manager は :maroon:`OpenCLのような物の一つの実装` と言える

- 学生が Cell アーキテクチャの理解、及び Cell プログラミングを行う際は
  Task Manager が適している


結論
===============================

- :silver:`Cell アーキテクチャの概要`
- :silver:`Many Core プログラミングの特徴`
- :silver:`Task Manager の実装`
- :silver:`Cerium`
- :silver:`比較`
- :big:`まとめと今後の課題`


まとめ
=========================

- 並列プログラミングのフレームワークとして
  TaskManager を提案し、それを用いた、PS3ゲーム開発フレームワークである
  Cerium を開発した

- Cerium を用いれば、
  学生が手を付けやすい環境(MacOSX、Linux)から開発を始め、
  コードの大幅な変更なく PS3 (Cell) での動作を確認できる


今後の課題
=======================

- SceneGraph の SPE 上での実行

- SIMD 演算の使用、もしくはそれに適したデータ構造の採用

- プログラムコードの SPE 上での On demand Load

  - 現在は予めコードを全て置いておく必要がある
  - SPE のメモリ領域 (256KB) を考えると好ましくない

- レンダリングの機能の追加

  - アルファブレンディング
  - 光源
  - Z-sort

終
==============