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

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

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

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

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


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

- 研究の背景と目的
- Cell アーキテクチャの概要
- Many Core プログラミングの特徴
- Task Manager の実装
- Task Manager を用いた並列プログラム
- Cerium
- Cerium を用いたゲーム
- まとめと今後の課題


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

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

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

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

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

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

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

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

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

Many Core Architecture を用いた並列プログラムの開発をサポートするフレームワーク :maroon:`Fine Grain Task Manager` を提案する

- 動作環境

  - Mac OS X、Linux、PS3(Cell)

- Fine Grain Task の単位

  - サブルーチンまたは関数

- Task Manager を用いた開発行程

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

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


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

**Cerium**
  Task Manager を用いた、PS3ゲーム開発用フレームワーク

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

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


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

- :silver:`研究の背景と目的`
- :big:`Cell アーキテクチャの概要`
- :silver:`Many Core プログラミングの特徴`
- :silver:`Task Manager の実装`
- :silver:`Task Manager を用いた並列プログラム`
- :silver:`Cerium`
- :silver:`Cerium を用いたゲーム`
- :silver:`まとめと今後の課題`

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

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

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

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

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

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

- :maroon:`DMA (Direct Memory Access)`

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

  DMA 転送を行うにはいくつか条件がある

  - データサイズは 16 バイトの倍数
  - 転送元と転送先のアドレスが 16 バイト境界に揃えられている

- :maroon:`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:`研究の背景と目的`
- :silver:`Cell アーキテクチャの概要`
- :big:`Many Core プログラミングの特徴`
- :silver:`Task Manager の実装`
- :silver:`Task Manager を用いた並列プログラム`
- :silver:`Cerium`
- :silver:`Cerium を用いたゲーム`
- :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 が独立に (ロック無しで) データにアクセスできる様にデータを分割すれば良い

**デバッグ**

- 並列プログラムの実行は非決定的

  - 非決定的 = 同じ状態で実行しても結果が異なる

- バグの状態を再現することが難しい

- 個々の CPU 上のデータを調べる必要がある


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

並列プログラミングでは、以下の段階において、それぞれ実装とテストを行う。

1. C によるシーケンシャルな実装
2. 並列実行を考慮したデータ構造を持つ実装
3. コードを分割し、シーケンシャルに実行する実装
4. 分割したコードを並列実行する実装


比較 - Gallium
===========================

.. _Gallium: http://www.tungstengraphics.com/wiki/index.php/Gallium3D
.. _OSMesa: http://www.mesa3d.org/

Gallium_
  オープンソースの 3D グラフィックドライバ

フレームバッファエンジン用のレンダリングエンジンである OSMesa_ の
Cell ドライバとして用いられている

- Triangle (Polygon) を SPE に送り、その中から得られた Span に
  テクスチャを貼ってレンダリングする
- SPE は6 個使用
- SIMD 演算を積極的に使用している。

先行研究では Rendering Engine に OSMesa を使用していたため、
Cerium Rendering Engine のレンダリング手法は OSMesa を参考にしている


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

- 先行研究 (神里)

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

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

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

- Gallium 

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

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

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

- Cerium

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

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

- 実行速度比較

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

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

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

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

.. _OpenGL: http://www.opengl.org/

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

- ポリゴンの描画

.. raw:: html

  <div align="center" style="color: maroon; font-size: large;">
    // 線分3つ指定し、三角形を生成<br/>
    glVertex3d(x1, y1, z1);<br/>
    glVertex3d(x2, y2, z2);<br/>
    glVertex3d(x3, y3, z3);<br/>
  </div>

- OpenGL での親子関係の表現

  glPushMatrix();
    //現在処理してるオブジェクトの変換行列をスタックに登録

  makePolygon();
    //このオブジェクトは今まで Push された変換行列の影響を受ける

  glPopMatrix();
    //スタックから変換行列を取り出す


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

レンダリングは Cerium Rendering Engine を用いて、
ゲームオブジェクトの操作は OpenGL を用いることでゲーム開発は可能

- OpenGL が持つレンダリングドライバは使用せずに、オブジェクトの操作結果をポリゴンとして出力するためには、各オブジェクトの変換行列が必要

  - 各オブジェクトのパラメータは変換行列が掛けられる前の状態を保持

- 変換行列は OpenGL が内部にもつ Matrix Stack に格納されている

- Matrix Stack から、 :maroon:`各オブジェクトに対応する変換行列` を取り出す必要がある

最初から自身の変換行列を持っている SceneGraph というデータ構造を用いれば、
SPE 上でオブジェクトの操作から変換行列による更新まで一括して行える



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

**OpenCL**
  マルチコアCPUやGPU、その他のプロセッサによる、ヘテロジニアスコンピューティングのフレームワーク

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

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

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

**OpenCL**

- あらゆる Many Core Architecture に対応できるような汎用的な実装
- 開発環境にあわせた記述が必要

**Task Manager**

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

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

- 学生による Cell プログラミングフレームワークとしては Task Manager が扱いやすい