Mercurial > hg > Papers > 2009 > gongo-master

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/presen/Makefile	Sat Feb 14 23:45:47 2009 +0900
@@ -0,0 +1,13 @@
+TARGET = presen
+
+COMMAND = rst2s5.py
+RM      = rm -f
+
+all: html
+	open $(TARGET).html
+
+html:
+	$(COMMAND) < $(TARGET).rst > $(TARGET).html
+
+clean:
+	$(RM) *~ \#*
Binary file presen/images/com_gallium.jpg has changed
Binary file presen/images/cp_opencl_plat.graffle has changed
Binary file presen/images/cp_opencl_plat.jpg has changed
Binary file presen/images/manycore_data_split.graffle has changed
Binary file presen/images/manycore_data_split.jpg has changed
Binary file presen/images/manycore_pipeline.graffle has changed
Binary file presen/images/manycore_pipeline.jpg has changed
--- a/presen/presen.html	Sat Feb 14 19:40:02 2009 +0900
+++ b/presen/presen.html	Sat Feb 14 23:45:47 2009 +0900
@@ -352,6 +352,19 @@

 </div>
 <div class="slide" id="id1">
+<h1>発表の流れ</h1>
+<ul class="simple">
+<li>研究の背景と目的</li>
+<li>Cell アーキテクチャの概要</li>
+<li>Many Core プログラミングの特徴</li>
+<li>Task Manager の実装</li>
+<li>Task Manager を用いた並列プログラム</li>
+<li>Cerium</li>
+<li>Cerium を用いたゲーム</li>
+<li>まとめと今後の課題</li>
+</ul>
+</div>
+<div class="slide" id="id2">
 <h1>研究の背景</h1>
 <p>現在、学生実験で PS3Linux を用いてゲーム開発を行っているが、
 学生には困難であることがわかってきている</p>
@@ -371,21 +384,25 @@
 <p>実験期間の大半を Cell の勉強に費やさねばならず、
 開発されるゲームのレベルが例年一定以上にならない</p>
 </div>
-<div class="slide" id="id2">
+<div class="slide" id="id3">
 <h1>研究目的</h1>
 <p>Many Core Architecture を用いた並列プログラムの開発をサポートするフレームワーク <span class="text-maroon">Fine Grain Task Manager</span> を提案する</p>
 <ul>
 <li><p class="first">動作環境</p>
-<p>Mac OS X、Linux、PS3(Cell)</p>
+<ul class="simple">
+<li>Mac OS X、Linux、PS3(Cell)</li>
+</ul>
 </li>
 <li><p class="first">Fine Grain Task の単位</p>
-<p>サブルーチンまたは関数</p>
+<ul class="simple">
+<li>サブルーチンまたは関数</li>
+</ul>
 </li>
 <li><p class="first">Task Manager を用いた開発行程</p>
 <ol class="arabic simple">
-<li>逐次型プログラム</li>
-<li>データやコードを分割したプログラム</li>
-<li>並列に動かすプログラム</li>
+<li>逐次型プログラム (MacOSX、Linux)</li>
+<li>データやコードを分割したプログラム (MacOSX、Linux)</li>
+<li>並列に動かすプログラム (Cell)</li>
 </ol>
 <p>各段階で信頼性を確保しながら開発を進める</p>
 </li>
@@ -406,21 +423,10 @@
 割り振りを行うカーネル <span class="text-maroon">TaskManager</span></li>
 </ul>
 </div>
-<div class="slide" id="id3">
-<h1>発表の流れ</h1>
-<ul class="simple">
-<li>Cell アーキテクチャの概要</li>
-<li>Many Core プログラミングの特徴</li>
-<li>Task Manager の実装</li>
-<li>Task Manager を用いた並列プログラム</li>
-<li>Cerium</li>
-<li>Cerium を用いたゲーム</li>
-<li>まとめと今後の課題</li>
-</ul>
-</div>
 <div class="slide" id="cell">
 <h1>Cell アーキテクチャの概要</h1>
 <ul class="simple">
+<li><span class="text-silver">研究の背景と目的</span></li>
 <li><span class="text-big">Cell アーキテクチャの概要</span></li>
 <li><span class="text-silver">Many Core プログラミングの特徴</span></li>
 <li><span class="text-silver">Task Manager の実装</span></li>
@@ -472,6 +478,7 @@
 <div class="slide" id="many-core">
 <h1>Many Core プログラミングの特徴</h1>
 <ul class="simple">
+<li><span class="text-silver">研究の背景と目的</span></li>
 <li><span class="text-silver">Cell アーキテクチャの概要</span></li>
 <li><span class="text-big">Many Core プログラミングの特徴</span></li>
 <li><span class="text-silver">Task Manager の実装</span></li>
@@ -493,6 +500,224 @@
   3倍程度の性能向上しか得られない
 </div><p>Amdahl 則より、恒常的に並列プログラムの並列度を維持する必要がある</p>
 </div>
+<div class="slide" id="id6">
+<h1>プログラム及びデータの分割</h1>
+<p>プログラム中の並列度は、以下の形で取り出すことが可能</p>
+<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><p>上二つの処理を行うには、プログラムとデータの適切な分割が必要</p>
+<ul class="simple">
+<li>プログラムの分割<ul>
+<li>for 文、木構造で処理する個々のステートメント</li>
+</ul>
+</li>
+<li>データの分割<ul>
+<li>自明には行えない可能性がある</li>
+<li>分割できるデータ構造の採用が必要となる</li>
+</ul>
+</li>
+</ul>
+</div>
+<div class="slide" id="id7">
+<h1>Many Core の同期とデバッグ</h1>
+<dl class="docutils">
+<dt><strong>同期</strong></dt>
+<dd>複数の CPU がデータの待ち合わせ、または、整合性を維持するために、他の CPU との待ち合わせを行うこと</dd>
+</dl>
+<ul class="simple">
+<li>各 CPU が待ち合わせを行うと、並列度が下がってしまうため、同期自体を減らす必要がある</li>
+</ul>
+<div align="center">
+  &darr;
+</div><ul class="simple">
+<li>各 CPU が独立に (ロック無しで) データにアクセスできる様にデータを分割すれば良い</li>
+</ul>
+<p><strong>デバッグ</strong></p>
+<ul class="simple">
+<li>並列プログラムの実行は非決定的<ul>
+<li>非決定的 = 同じ状態で実行しても結果が異なる</li>
+</ul>
+</li>
+<li>バグの状態を再現することが難しい</li>
+<li>個々の CPU 上のデータを調べる必要がある</li>
+</ul>
+</div>
+<div class="slide" id="id8">
+<h1>並列プログラムの開発行程</h1>
+<p>並列プログラミングでは、以下の段階において、それぞれ実装とテストを行う。</p>
+<ol class="arabic simple">
+<li>C によるシーケンシャルな実装</li>
+<li>並列実行を考慮したデータ構造を持つ実装</li>
+<li>コードを分割し、シーケンシャルに実行する実装</li>
+<li>分割したコードを並列実行する実装</li>
+</ol>
+</div>
+<div class="slide" id="gallium">
+<h1>比較 - Gallium</h1>
+<dl class="docutils">
+<dt><a class="reference" href="http://www.tungstengraphics.com/wiki/index.php/Gallium3D">Gallium</a></dt>
+<dd>オープンソースの 3D グラフィックドライバ</dd>
+</dl>
+<p>フレームバッファエンジン用のレンダリングエンジンである <a class="reference" href="http://www.mesa3d.org/">OSMesa</a> の
+Cell ドライバとして用いられている</p>
+<ul class="simple">
+<li>Triangle (Polygon) を SPE に送り、その中から得られた Span に
+テクスチャを貼ってレンダリングする</li>
+<li>SPE は6 個使用</li>
+<li>SIMD 演算を積極的に使用している。</li>
+</ul>
+<p>先行研究では Rendering Engine に OSMesa を使用していたため、
+Cerium Rendering Engine のレンダリング手法は OSMesa を参考にしている</p>
+</div>
+<div class="slide" id="gallium-con-t">
+<h1>比較 - Gallium (Con't)</h1>
+<ul class="simple">
+<li>先行研究 (神里)<ul>
+<li>現在 PS3Linux からは <span class="text-maroon">GPU にアクセスできない</span></li>
+<li><span class="text-maroon">フレームバッファは使用できる</span> ため、OSMesa を使用</li>
+<li>OSMesa の機能の一部を SPE に乗せ、高速化に成功</li>
+<li>ソースコードの複雑化を招いた<ul>
+<li>OSMesa の元々の実装の影響 (巨大なマクロ、構造体)</li>
+</ul>
+</li>
+<li>以降のメンテナンスや機能の追加、改良が困難と判断</li>
+<li>独自に Rendering Engine を持つことに</li>
+</ul>
+</li>
+<li>Gallium<ul>
+<li>OSMesa の Cell Driver</li>
+<li>OpenGL + Gallium でのゲーム開発は可能</li>
+<li>PS3 上のゲーム開発において、レンダリングのみを SPE に実装するのでは足りない<ul>
+<li>ゲームに登場するオブジェクトの計算 (衝突判定等)</li>
+<li>Amdahl 則の問題</li>
+</ul>
+</li>
+<li>レンダリングだけでなく、ゲームオブジェクトも SPE で処理できるように
+しなければならない</li>
+</ul>
+</li>
+<li>Cerium<ul>
+<li>SceneGraph、レンダリングを SPE 上で処理する</li>
+</ul>
+</li>
+</ul>
+</div>
+<div class="slide" id="id10">
+<h1>比較 - Gallium (Con't)</h1>
+<ul class="simple">
+<li>実行速度比較<ul>
+<li>出力解像度は 1920x1080</li>
+<li>地球のテクスチャを貼った球体のオブジェクトを表示</li>
+</ul>
+</li>
+</ul>
+<div align="center" class="align-center"><img alt="images/com_gallium.jpg" class="align-center" src="images/com_gallium.jpg" style="width: 350px;" /></div>
+<table border="1" class="docutils">
+<colgroup>
+<col width="55%" />
+<col width="45%" />
+</colgroup>
+<tbody valign="top">
+<tr><td>Gallium (SPE 6 個)</td>
+<td>5.4 FPS</td>
+</tr>
+<tr><td>Cerium (SPE 1 個)</td>
+<td>2.5 FPS</td>
+</tr>
+<tr><td>Cerium (SPE 6 個)</td>
+<td><span class="text-maroon">9.5 FPS</span></td>
+</tr>
+</tbody>
+</table>
+</div>
+<div class="slide" id="opengl">
+<h1>比較 - OpenGL</h1>
+<dl class="docutils">
+<dt><a class="reference" href="http://www.opengl.org/">OpenGL</a></dt>
+<dd>オープンソースの3Dグラフィックスプログラムインターフェース</dd>
+</dl>
+<ul class="simple">
+<li>ポリゴンの描画</li>
+</ul>
+<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><ul>
+<li><p class="first">OpenGL での親子関係の表現</p>
+<dl class="docutils">
+<dt>glPushMatrix();</dt>
+<dd><p class="first last">//現在処理してるオブジェクトの変換行列をスタックに登録</p>
+</dd>
+<dt>makePolygon();</dt>
+<dd><p class="first last">//このオブジェクトは今まで Push された変換行列の影響を受ける</p>
+</dd>
+<dt>glPopMatrix();</dt>
+<dd><p class="first last">//スタックから変換行列を取り出す</p>
+</dd>
+</dl>
+</li>
+</ul>
+</div>
+<div class="slide" id="opengl-con-t">
+<h1>比較 - OpenGL (Con't)</h1>
+<p>レンダリングは Cerium Rendering Engine を用いて、
+ゲームオブジェクトの操作は OpenGL を用いることでゲーム開発は可能</p>
+<ul class="simple">
+<li>OpenGL が持つレンダリングドライバは使用せずに、オブジェクトの操作結果をポリゴンとして出力するためには、各オブジェクトの変換行列が必要<ul>
+<li>各オブジェクトのパラメータは変換行列が掛けられる前の状態を保持</li>
+</ul>
+</li>
+<li>変換行列は OpenGL が内部にもつ Matrix Stack に格納されている</li>
+<li>Matrix Stack から、 <span class="text-maroon">各オブジェクトに対応する変換行列</span> を取り出す必要がある</li>
+</ul>
+<p>最初から自身の変換行列を持っている SceneGraph というデータ構造を用いれば、
+SPE 上でオブジェクトの操作から変換行列による更新まで一括して行える</p>
+</div>
+<div class="slide" id="opencl">
+<h1>比較 - OpenCL</h1>
+<dl class="docutils">
+<dt><strong>OpenCL</strong></dt>
+<dd>マルチコアCPUやGPU、その他のプロセッサによる、ヘテロジニアスコンピューティングのフレームワーク</dd>
+</dl>
+<div align="center" class="align-center"><img alt="images/cp_opencl_plat.jpg" class="align-center" src="images/cp_opencl_plat.jpg" style="width: 300px;" /></div>
+<ul class="simple">
+<li>Host から PE へ実行コマンドが送られる</li>
+<li>Host や OpenCL Device はコマンドの管理を行う kernel を持つ</li>
+<li>OpenCL Device 毎に独立したメモリ領域を持つ</li>
+<li>データ並列、タスク並列をサポート</li>
+</ul>
+</div>
+<div class="slide" id="opencl-con-t">
+<h1>比較 - OpenCL (Con't)</h1>
+<p><strong>OpenCL</strong></p>
+<ul class="simple">
+<li>あらゆる Many Core Architecture に対応できるような汎用的な実装</li>
+<li>開発環境にあわせた記述が必要</li>
+</ul>
+<p><strong>Task Manager</strong></p>
+<ul class="simple">
+<li>Cell アーキテクチャに重きを置いた記述</li>
+<li>DMA によるメモリアクセスなど、決まった記述で開発できる</li>
+<li>大幅なコードの変更無く Mac OS X や Linux など複数の環境で動作させることが可能</li>
+</ul>
+<p>Task Manager は <span class="text-maroon">OpenCL による実装の一つ</span> と言える</p>
+<ul class="simple">
+<li>学生による Cell プログラミングフレームワークとしては Task Manager が扱いやすい</li>
+</ul>
+</div>
 </div>
 </body>
 </html>
--- a/presen/presen.rst	Sat Feb 14 19:40:02 2009 +0900
+++ b/presen/presen.rst	Sat Feb 14 23:45:47 2009 +0900
@@ -15,6 +15,19 @@
   **琉球大学 理工学研究科 情報工学専攻 並列信頼研究室**


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

@@ -41,17 +54,17 @@

 - 動作環境

-  Mac OS X、Linux、PS3(Cell)
+  - Mac OS X、Linux、PS3(Cell)

 - Fine Grain Task の単位

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

 - Task Manager を用いた開発行程

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

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

@@ -70,20 +83,11 @@
 - Rendering Engine や Scene Graph の処理単位を Task とし、複数の Core へ
   割り振りを行うカーネル :maroon:`TaskManager`

-発表の流れ
-======================
-
-- Cell アーキテクチャの概要
-- Many Core プログラミングの特徴
-- Task Manager の実装
-- Task Manager を用いた並列プログラム
-- Cerium
-- Cerium を用いたゲーム
-- まとめと今後の課題

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

+- :silver:`研究の背景と目的`
 - :big:`Cell アーキテクチャの概要`
 - :silver:`Many Core プログラミングの特徴`
 - :silver:`Task Manager の実装`
@@ -136,6 +140,7 @@
 Many Core プログラミングの特徴
 ================================

+- :silver:`研究の背景と目的`
 - :silver:`Cell アーキテクチャの概要`
 - :big:`Many Core プログラミングの特徴`
 - :silver:`Task Manager の実装`
@@ -163,3 +168,232 @@
   </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 が扱いやすい