Mercurial > hg > Papers > 2009 > gongo-master

view presen/presen.html @ 28:356077fb1c38

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add resume
author gongo@gendarme.cr.ie.u-ryukyu.ac.jp
date Tue, 17 Feb 2009 12:27:00 +0900
parents 90128e098120
children
line wrap: on
line source

<?xml version="1.0" encoding="utf-8" ?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<meta name="generator" content="Docutils 0.4: http://docutils.sourceforge.net/" />
<meta name="version" content="S5 1.1" />
<title>Cell 用の Fine-Grain Task Manager の実装</title>
<style type="text/css">

/*
:Author: David Goodger
:Contact: goodger@users.sourceforge.net
:Date: $Date: 2005-12-18 01:56:14 +0100 (Sun, 18 Dec 2005) $
:Revision: $Revision: 4224 $
:Copyright: This stylesheet has been placed in the public domain.

Default cascading style sheet for the HTML output of Docutils.

See http://docutils.sf.net/docs/howto/html-stylesheets.html for how to
customize this style sheet.
*/

/* used to remove borders from tables and images */
.borderless, table.borderless td, table.borderless th {
  border: 0 }

table.borderless td, table.borderless th {
  /* Override padding for "table.docutils td" with "! important".
     The right padding separates the table cells. */
  padding: 0 0.5em 0 0 ! important }

.first {
  /* Override more specific margin styles with "! important". */
  margin-top: 0 ! important }

.last, .with-subtitle {
  margin-bottom: 0 ! important }

.hidden {
  display: none }

a.toc-backref {
  text-decoration: none ;
  color: black }

blockquote.epigraph {
  margin: 2em 5em ; }

dl.docutils dd {
  margin-bottom: 0.5em }

/* Uncomment (and remove this text!) to get bold-faced definition list terms
dl.docutils dt {
  font-weight: bold }
*/

div.abstract {
  margin: 2em 5em }

div.abstract p.topic-title {
  font-weight: bold ;
  text-align: center }

div.admonition, div.attention, div.caution, div.danger, div.error,
div.hint, div.important, div.note, div.tip, div.warning {
  margin: 2em ;
  border: medium outset ;
  padding: 1em }

div.admonition p.admonition-title, div.hint p.admonition-title,
div.important p.admonition-title, div.note p.admonition-title,
div.tip p.admonition-title {
  font-weight: bold ;
  font-family: sans-serif }

div.attention p.admonition-title, div.caution p.admonition-title,
div.danger p.admonition-title, div.error p.admonition-title,
div.warning p.admonition-title {
  color: red ;
  font-weight: bold ;
  font-family: sans-serif }

/* Uncomment (and remove this text!) to get reduced vertical space in
   compound paragraphs.
div.compound .compound-first, div.compound .compound-middle {
  margin-bottom: 0.5em }

div.compound .compound-last, div.compound .compound-middle {
  margin-top: 0.5em }
*/

div.dedication {
  margin: 2em 5em ;
  text-align: center ;
  font-style: italic }

div.dedication p.topic-title {
  font-weight: bold ;
  font-style: normal }

div.figure {
  margin-left: 2em ;
  margin-right: 2em }

div.footer, div.header {
  clear: both;
  font-size: smaller }

div.line-block {
  display: block ;
  margin-top: 1em ;
  margin-bottom: 1em }

div.line-block div.line-block {
  margin-top: 0 ;
  margin-bottom: 0 ;
  margin-left: 1.5em }

div.sidebar {
  margin-left: 1em ;
  border: medium outset ;
  padding: 1em ;
  background-color: #ffffee ;
  width: 40% ;
  float: right ;
  clear: right }

div.sidebar p.rubric {
  font-family: sans-serif ;
  font-size: medium }

div.system-messages {
  margin: 5em }

div.system-messages h1 {
  color: red }

div.system-message {
  border: medium outset ;
  padding: 1em }

div.system-message p.system-message-title {
  color: red ;
  font-weight: bold }

div.topic {
  margin: 2em }

h1.section-subtitle, h2.section-subtitle, h3.section-subtitle,
h4.section-subtitle, h5.section-subtitle, h6.section-subtitle {
  margin-top: 0.4em }

h1.title {
  text-align: center }

h2.subtitle {
  text-align: center }

hr.docutils {
  width: 75% }

img.align-left {
  clear: left }

img.align-right {
  clear: right }

ol.simple, ul.simple {
  margin-bottom: 1em }

ol.arabic {
  list-style: decimal }

ol.loweralpha {
  list-style: lower-alpha }

ol.upperalpha {
  list-style: upper-alpha }

ol.lowerroman {
  list-style: lower-roman }

ol.upperroman {
  list-style: upper-roman }

p.attribution {
  text-align: right ;
  margin-left: 50% }

p.caption {
  font-style: italic }

p.credits {
  font-style: italic ;
  font-size: smaller }

p.label {
  white-space: nowrap }

p.rubric {
  font-weight: bold ;
  font-size: larger ;
  color: maroon ;
  text-align: center }

p.sidebar-title {
  font-family: sans-serif ;
  font-weight: bold ;
  font-size: larger }

p.sidebar-subtitle {
  font-family: sans-serif ;
  font-weight: bold }

p.topic-title {
  font-weight: bold }

pre.address {
  margin-bottom: 0 ;
  margin-top: 0 ;
  font-family: serif ;
  font-size: 100% }

pre.literal-block, pre.doctest-block {
  margin-left: 2em ;
  margin-right: 2em ;
  background-color: #eeeeee }

span.classifier {
  font-family: sans-serif ;
  font-style: oblique }

span.classifier-delimiter {
  font-family: sans-serif ;
  font-weight: bold }

span.interpreted {
  font-family: sans-serif }

span.option {
  white-space: nowrap }

span.pre {
  white-space: pre }

span.problematic {
  color: red }

span.section-subtitle {
  /* font-size relative to parent (h1..h6 element) */
  font-size: 80% }

table.citation {
  border-left: solid 1px gray;
  margin-left: 1px }

table.docinfo {
  margin: 2em 4em }

table.docutils {
  margin-top: 0.5em ;
  margin-bottom: 0.5em }

table.footnote {
  border-left: solid 1px black;
  margin-left: 1px }

table.docutils td, table.docutils th,
table.docinfo td, table.docinfo th {
  padding-left: 0.5em ;
  padding-right: 0.5em ;
  vertical-align: top }

table.docutils th.field-name, table.docinfo th.docinfo-name {
  font-weight: bold ;
  text-align: left ;
  white-space: nowrap ;
  padding-left: 0 }

h1 tt.docutils, h2 tt.docutils, h3 tt.docutils,
h4 tt.docutils, h5 tt.docutils, h6 tt.docutils {
  font-size: 100% }

tt.docutils {
  background-color: #eeeeee }

ul.auto-toc {
  list-style-type: none }

</style>
<!-- configuration parameters -->
<meta name="defaultView" content="slideshow" />
<meta name="controlVis" content="hidden" />
<!-- style sheet links -->
<script src="ui/default/slides.js" type="text/javascript"></script>
<link rel="stylesheet" href="ui/default/slides.css"
      type="text/css" media="projection" id="slideProj" />
<link rel="stylesheet" href="ui/default/outline.css"
      type="text/css" media="screen" id="outlineStyle" />
<link rel="stylesheet" href="ui/default/print.css"
      type="text/css" media="print" id="slidePrint" />
<link rel="stylesheet" href="ui/default/opera.css"
      type="text/css" media="projection" id="operaFix" />

<style type="text/css">
#currentSlide {display: none;}
</style>
</head>
<body>
<div class="layout">
<div id="controls"></div>
<div id="currentSlide"></div>
<div id="header">

</div>
<div id="footer">
<h1>Cell 用の Fine-Grain Task Manager の実装</h1>

</div>
</div>
<div class="presentation">
<div class="slide" id="slide0">
<h1 class="title">Cell 用の Fine-Grain Task Manager の実装</h1>
<!-- Definitions of interpreted text roles (classes) for S5/HTML data. -->
<!-- This data file has been placed in the public domain. -->
<!-- Colours
======= -->
<!-- Text Sizes
========== -->
<!-- Display in Slides (Presentation Mode) Only
========================================== -->
<!-- Display in Outline Mode Only
============================ -->
<!-- Display in Print Only
===================== -->
<!-- Incremental Display
=================== -->
<!-- This data file has been placed in the public domain. -->
<!-- Derived from the Unicode character mappings available from
<http://www.w3.org/2003/entities/xml/>.
Processed by unicode2rstsubs.py, part of Docutils:
<http://docutils.sourceforge.net>. -->
<dl class="docutils">
<dt><em>発表者</em></dt>
<dd><strong>宮國渡</strong></dd>
<dt><em>指導教官</em></dt>
<dd><strong>河野真治</strong></dd>
<dt><em>所属</em></dt>
<dd><strong>琉球大学 理工学研究科 情報工学専攻 並列信頼研究室</strong></dd>
</dl>

</div>
<div class="slide" id="id1">
<h1>研究の背景</h1>
<p>現在、学生実験で PS3Linux を用いてゲーム開発を行っているが、
学生には困難であることがわかってきている</p>
<ul>
<li><p class="first"><span class="text-maroon">問題1</span> : <span class="text-underline">Cell アーキテクチャプログラミング</span></p>
<ul>
<li><p class="first">Many Core による並列プログラミング</p>
<p>(データ、コードの分割の必要性)</p>
</li>
<li><p class="first">Cell の仕様 (DMA、データのアライメント、etc..)</p>
</li>
</ul>
</li>
<li><p class="first"><span class="text-maroon">問題2</span> : <span class="text-underline">ゲーム開発用の Framework が無い</span></p>
</li>
</ul>
<p>実験期間の大半を Cell の勉強に費やさねばならず、
開発されるゲームのレベルが例年一定以上にならない</p>
</div>
<div class="slide" id="id2">
<h1>研究目的</h1>
<p>Many Core Architecture を用いた並列プログラムの開発をサポートするフレームワーク <span class="text-maroon">Fine Grain Task Manager</span> 、それを組み込んだ、
PS3 ゲーム開発用フレームワーク <span class="text-maroon">Cerium</span> を提案する</p>
<ul>
<li><p class="first">動作環境</p>
<ul class="simple">
<li>Mac OS X、Linux、PS3(Cell)</li>
</ul>
</li>
<li><p class="first">Fine Grain Task の単位</p>
<ul class="simple">
<li>サブルーチン</li>
</ul>
</li>
<li><p class="first">Cerium を用いた開発行程</p>
<ol class="arabic simple">
<li>逐次型プログラム</li>
<li>データやコードを分割したプログラム</li>
<li>並列に動かすプログラム</li>
</ol>
<p>各段階で信頼性を確保しながら開発を進める</p>
</li>
</ul>
</div>
<div class="slide" id="con-t">
<h1>研究目的 (Con't)</h1>
<p><strong>Cerium</strong></p>
<p>3 つの機能で構成されている</p>
<ul class="simple">
<li>独自の <span class="text-maroon">Rendering Engine</span></li>
<li>ゲームに登場するオブジェクトやルールなど、ゲームを構成する要素を
木構造として持つ <span class="text-maroon">Scene Graph</span></li>
<li>Rendering Engine や Scene Graph の処理単位を Task とし、複数の Core へ
割り振りを行うカーネル <span class="text-maroon">TaskManager</span></li>
</ul>
<p>学生が Cell アーキテクチャを理解しながら、
期間内でゲーム開発が行える、シンプルな
マルチタスクフレームワークを目指す</p>
</div>
<div class="slide" id="id3">
<h1>発表の流れ</h1>
<ul class="simple">
<li>Cell アーキテクチャの概要</li>
<li>Many Core プログラミングの特徴</li>
<li>Task Manager の実装</li>
<li>Cerium</li>
<li>比較</li>
<li>まとめと今後の課題</li>
</ul>
</div>
<div class="slide" id="cell">
<h1>Cell アーキテクチャの概要</h1>
<ul class="simple">
<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>
<li><span class="text-silver">Cerium</span></li>
<li><span class="text-silver">比較</span></li>
<li><span class="text-silver">まとめと今後の課題</span></li>
</ul>
</div>
<div class="slide" id="cell-broadband-engine">
<h1>Cell Broadband Engine</h1>
<div align="center" class="align-center"><img alt="images/cell_arch.jpg" class="align-center" src="images/cell_arch.jpg" style="width: 480px;" /></div>
<ul class="simple">
<li>1個の PPE と 8 個の SPE がリングバスで構成されている<ul>
<li>Linux 側から使える SPE は 6 個</li>
</ul>
</li>
<li>SPE は <span class="text-maroon">256KB</span> の Local Store (LS) を持つ</li>
<li>SPE からメインメモリへは直接アクセスできない<ul>
<li>SPE が持つ MFC (Memory Flow Controller) へ
<span class="text-maroon">DMA 命令</span> を送ることで行う</li>
</ul>
</li>
<li>SPE は 128 ビットレジスタを 128 個持っている<ul>
<li>SIMD (Single Instruction Multiple Data) が可能
(32bit のデータ4つを同時に演算)</li>
</ul>
</li>
</ul>
</div>
<div class="slide" id="id4">
<h1>Cell の基本機能</h1>
<p><strong>DMA</strong></p>
<ul class="simple">
<li>メインメモリと LS 間でデータが転送される</li>
</ul>
<p><strong>Mailbox</strong></p>
<ul>
<li><p class="first">SPE の MFC 内にある FIFO キュー</p>
</li>
<li><p class="first">PPE と SPE 間で 32 ビットメッセージの交換に用いられる</p>
<p>キューは 3 種類</p>
<ul class="simple">
<li>SPU Inbound Mailbox : PPE → SPE</li>
<li>SPU Outbound Mailbox : SPE → PPE</li>
<li>SPU Outbound interrupt Mailbox : SPE → PPE (割り込み)</li>
</ul>
</li>
</ul>
</div>
<div class="slide" id="many-core">
<h1>Many Core プログラミングの特徴</h1>
<ul class="simple">
<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>
<li><span class="text-silver">Cerium</span></li>
<li><span class="text-silver">比較</span></li>
<li><span class="text-silver">まとめと今後の課題</span></li>
</ul>
</div>
<div class="slide" id="id5">
<h1>定常的な並列度の必要性</h1>
<dl class="docutils">
<dt><strong>Amdahl 則</strong></dt>
<dd>プログラムの並列化率が低ければ、その性能を生かすことは出来ない</dd>
</dl>
<div align="center" class="align-center"><img alt="images/amdahl.jpg" class="align-center" src="images/amdahl.jpg" style="width: 360px;" /></div>
<div align="center" style="font-size: large;">
  6 CPU を使っても、プログラムの並列化率が 8 割程度では<br />
  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>
</ul>
</li>
</ul>
<p>二つの分割は自明には行えないことが多いため、工夫が必要</p>
</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 と干渉するデータ入出力の場合、待ち合わせる必要がある<ul>
<li>待ち時間が無駄になる</li>
</ul>
</li>
<li>データ待ちの為にストップする状態を減らす</li>
</ul>
<div align="center">
  &darr;
</div><ul class="simple">
<li>各 CPU が独立に (ロック無しで) データにアクセスできる様にデータを分割すれば良い</li>
</ul>
</div>
<div class="slide" id="id8">
<h1>並列プログラムの開発行程</h1>
<p>以下の5段階に置いて、実装とテストを行う</p>
<ol class="arabic simple">
<li>C によるシーケンシャルな実装</li>
</ol>
<ul class="simple">
<li>アルゴリズムの確認</li>
</ul>
<ol class="arabic simple" start="2">
<li>並列実行を考慮したデータ構造を持つ実装</li>
</ol>
<ul class="simple">
<li>データ構造が変化しても 1. と結果が同じになるかを確認</li>
</ul>
<ol class="arabic simple" start="3">
<li>コードを分割し、それらをシーケンシャルに実行する実装</li>
</ol>
<ul class="simple">
<li>この段階まではアーキテクチャに依存しない</li>
<li>二分法によるデバッグが可能</li>
</ul>
</div>
<div class="slide" id="id9">
<h1>並列プログラムの開発行程 (Con't)</h1>
<ol class="arabic simple" start="4">
<li>分割したコードを並列実行する実装</li>
<li>アーキテクチャに特化した実装</li>
</ol>
<ul class="simple">
<li>Cell の場合は SIMD</li>
</ul>
<p>4、5段階目でエラーが出た場合、一度 3. まで戻って
データ構造、プログラムの分割を確認する</p>
</div>
<div class="slide" id="task-manager">
<h1>Task Manager の実装</h1>
<ul class="simple">
<li><span class="text-silver">Cell アーキテクチャの概要</span></li>
<li><span class="text-silver">Many Core プログラミングの特徴</span></li>
<li><span class="text-big">Task Manager の実装</span></li>
<li><span class="text-silver">Cerium</span></li>
<li><span class="text-silver">比較</span></li>
<li><span class="text-silver">まとめと今後の課題</span></li>
</ul>
</div>
<div class="slide" id="id10">
<h1>Task Manager</h1>
<table>
  <tr>
    <td><p>Task と呼ばれる、分割された各プログラムを管理する</p>
<ul>
<li><p class="first">Task はサブルーチン</p>
</li>
<li><p class="first">Task 同士の依存関係を考慮</p>
</li>
<li><p class="first">実行状態になった Task を各 SPE に割り振る</p>
</li>
<li><p class="first">C++ で実装</p>
<p><span class="text-maroon">Task Manager User API</span></p>
</li>
</ul>
<table border="1" class="small docutils">
<colgroup>
<col width="100%" />
</colgroup>
<tbody valign="top">
<tr><td><dl class="first last docutils">
<dt>HTask* TaskManager::create_task(int ID);</dt>
<dd>Task の生成</dd>
</dl>
</td>
</tr>
<tr><td><dl class="first last docutils">
<dt>void* TaskManager::allocate(int size)</dt>
<dd>実行環境のアライメントを考慮した allocator</dd>
</dl>
</td>
</tr>
</tbody>
</table>
</td>
<td align="center"><p><span class="text-maroon">Task API</span></p>
<table border="1" class="small docutils">
<colgroup>
<col width="100%" />
</colgroup>
<tbody valign="top">
<tr><td><dl class="first last docutils">
<dt>task-&gt;add_inData(int addr, int size);</dt>
<dd>Task の入力データの設定 (入力元アドレス、データサイズ)</dd>
</dl>
</td>
</tr>
<tr><td><dl class="first last docutils">
<dt>task-&gt;add_outData(int addr, int size);</dt>
<dd>Task の出力データの設定 (出力先アドレス、データサイズ)</dd>
</dl>
</td>
</tr>
<tr><td><dl class="first last docutils">
<dt>task-&gt;add_param(int param);</dt>
<dd>Task のパラメータ (32bit)</dd>
</dl>
</td>
</tr>
<tr><td><dl class="first last docutils">
<dt>task-&gt;wait_for(HTask *wait);</dt>
<dd>Task の依存関係の考慮</dd>
</dl>
</td>
</tr>
<tr><td><dl class="first last docutils">
<dt>task-&gt;set_cpu(CPU_TYPE type);</dt>
<dd>Task を実行する CPU の設定</dd>
</dl>
</td>
</tr>
<tr><td><dl class="first last docutils">
<dt>task-&gt;spawn(void);</dt>
<dd><p class="first">task を ActiveQueue へ格納する</p>
<p class="last">TaskManager は ActiveQueue にある task を
SPE へ割り振る</p>
</dd>
</dl>
</td>
</tr>
</tbody>
</table>
   </td>
  </tr>
</table></div>
<div class="slide" id="task">
<h1>Task の生成</h1>
<pre class="literal-block">
HTask *task = manager-&gt;create_task(TASK_ID)
task-&gt;add_inData(in, sizeof(int)*16); // 入力データは in から取得
task-&gt;add_outData(out, sizeof(int)*16); // 出力結果は out へ
task-&gt;spawn();
</pre>
<dl class="docutils">
<dt>Task ID</dt>
<dd>各タスクに割り振られているグローバルID</dd>
</dl>
<ul class="simple">
<li>逐次型プログラムでは、Task に関数ポインタを持たせれば良い</li>
<li>PPE と SPE ではアドレス空間が異なるため、
単純に関数ポインタを持たせても意味が無い</li>
<li>予め SPE 上の領域に置いてある Task (関数) を選択して実行するために
ID を指定する</li>
<li>HTask が持つのは、SPE 上にある Task を実行するための情報</li>
</ul>
</div>
<div class="slide" id="id11">
<h1>Task の依存関係の解決</h1>
<p>TaskManager はタスク依存を解決する機能をもつ</p>
<pre class="small literal-block">
/* task2 は task1、task3 の終了を待つ */
task2-&gt;wait_for(task1);
task2-&gt;wait_for(task3);

/* Task が持つ依存関係の変数 */
TaskQueuePtr wait_me;  // List of task waiting for me
TaskQueuePtr wait_i;   // List of task for which I am waiting
</pre>
<div align="center" class="align-center"><img alt="images/tm_task_depend.jpg" class="align-center" src="images/tm_task_depend.jpg" style="width: 430px;" /></div>
</div>
<div class="slide" id="task-cpu">
<h1>Task を実行させる CPU の選択</h1>
<p>Task をどの CPU で実行させるかを明示的に選択できる</p>
<pre class="literal-block">
/* SPE1で実行する */
task1-&gt;set_cpu(SPE_1);

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

/* PPEで実行する  */
task3-&gt;set_cpu(PPE);
</pre>
<ul class="simple">
<li>PPE 内でもタスクの実行が可能</li>
<li>Mac OS X や Linux で実行する場合、SPE_* を指定したタスクは
そのままメインスレッドで実行される</li>
<li>違う環境へプログラムを移行する場合<ul>
<li>set_cpu で実行 CPU を変更する、もしくはそのままでもよい</li>
<li>環境依存のプログラム変換はタスク内部だけになる</li>
</ul>
</li>
</ul>
</div>
<div class="slide" id="cpu">
<h1>CPU スレッドスケジューラ</h1>
<table>
  <tr>
    <td><div align="center" class="align-center"><img alt="images/tm_scheduler.jpg" class="align-center" src="images/tm_scheduler.jpg" style="width: 400px;" /></div>
</td>
<td><ul class="simple">
<li>PPE から TaskList (Task の集合) を受け取る</li>
<li>TaskList から Task を取り出し、パイプラインに沿って、
ステージを遷移させながら実行していく</li>
<li>TaskList が空になったら、次の TaskList 要求メッセージを PPE に送る</li>
</ul>
    </td>
  </tr>
</table></div>
<div class="slide" id="id12">
<h1>メインスレッドと CPU スレッド間の同期</h1>
<ul>
<li><p class="first">同期は 32 ビットメッセージの交換 (Mailbox) により行う</p>
</li>
<li><p class="first">同期のタイミング</p>
<p><span class="text-maroon">SPE -&gt; PPE</span></p>
<ul class="simple">
<li>タスクの終了</li>
<li>新しい TaskList のリクエスト</li>
</ul>
<p><span class="text-maroon">PPE -&gt; SPE</span></p>
<ul class="simple">
<li>新しい TaskList の送信</li>
</ul>
</li>
<li><p class="first">メッセージ交換なので、スレッド間の待ち合わせは起こらない</p>
</li>
</ul>
</div>
<div class="slide" id="bitonic-sort">
<h1>例題 Bitonic Sort</h1>
<p>Task Manager を用いて、学生が記述</p>
<div align="center" class="align-center"><img alt="images/tm_sort.jpg" class="align-center" src="images/tm_sort.jpg" style="width: 350px;" /></div>
<ul class="simple">
<li>ソートデータを複数のブロックに分割</li>
<li>隣り合ったブロックでソートするタスクを生成し、実行</li>
<li>次ステップでは1ブロックずらしてソート</li>
<li>上の手順を、分割ブロック数だけ繰り返す</li>
</ul>
</div>
<div class="slide" id="id13">
<h1>例題 Bitonic Sort 実行結果</h1>
<ul class="simple">
<li>整数データは 100 万</li>
<li>SPE の数を変化させて実行速度を比較</li>
</ul>
<div align="center" class="align-center"><img alt="images/tm_sort_calc1m.jpg" class="align-center" src="images/tm_sort_calc1m.jpg" style="width: 480px;" /></div>
<ul class="simple">
<li>SPE 6 個で 5.1 倍</li>
<li>Task Manager 自体のオーバーヘッドは問題ない</li>
</ul>
</div>
<div class="slide" id="cerium">
<h1>Cerium</h1>
<ul class="simple">
<li><span class="text-silver">Cell アーキテクチャの概要</span></li>
<li><span class="text-silver">Many Core プログラミングの特徴</span></li>
<li><span class="text-silver">Task Manager の実装</span></li>
<li><span class="text-big">Cerium</span></li>
<li><span class="text-silver">比較</span></li>
<li><span class="text-silver">まとめと今後の課題</span></li>
</ul>
</div>
<div class="slide" id="id14">
<h1>Cerium</h1>
<p>PS3ゲーム開発用フレームワーク</p>
<div align="center" class="align-center"><img alt="images/cerium.jpg" class="align-center" src="images/cerium.jpg" style="width: 400px;" /></div>
<ul class="simple">
<li>Rendering Engine<ul>
<li>Cerium 独自</li>
</ul>
</li>
<li>Scene Graph<ul>
<li>ゲームに登場するオブジェクトやルールなど、ゲームを構成する要素にもつ木構造</li>
</ul>
</li>
<li>Task Manager<ul>
<li>Rendering Engine や Scene Graph の処理 (Task) を複数のSPEへ割り振る</li>
</ul>
</li>
</ul>
</div>
<div class="slide" id="scene-graph">
<h1>Scene Graph</h1>
<div align="center" class="align-center"><img alt="images/cerium_sg_tree.jpg" class="align-center" src="images/cerium_sg_tree.jpg" style="width: 95%;" /></div>
<ul class="simple">
<li>Blender <a class="footnote-reference" href="#id16" id="id15" name="id15">[1]</a> で生成したオブジェクトを 独自の XML 形式で出力</li>
<li>XML が持つ情報 (頂点座標、テクスチャ座標、イメージなど) から
SceneGraphNode を生成</li>
<li>ポリゴン情報の他に、オブジェクトの操作(move, collision) を持つ</li>
</ul>
<table class="small docutils footnote" frame="void" id="id16" rules="none">
<colgroup><col class="label" /><col /></colgroup>
<tbody valign="top">
<tr><td class="label"><a class="fn-backref" href="#id15" name="id16">[1]</a></td><td>オープンソースの3Dモデリングツール</td></tr>
</tbody>
</table>
</div>
<div class="slide" id="rendering">
<h1>Rendering</h1>
<table>
  <tr>
    <td><div align="center" class="align-center"><img alt="images/rendering.jpg" class="align-center" src="images/rendering.jpg" style="width: 400px;" /></div>
</td>
<td><dl class="docutils">
<dt>SG2PP</dt>
<dd>SceneGraph を操作後、ポリゴンに変換し PolygonPack (ポリゴンの集合)を生成する</dd>
<dt>PP2SP</dt>
<dd>ポリゴンの中から、Span (ポリゴン内にあるx軸に水平な線分) を抽出し、
SpanPack (Span の集合)を生成する</dd>
<dt>DrawSpan</dt>
<dd>Span を使って 1 ラインずつ FrameBuffer に描画していく</dd>
</dl>
    </td>
  </tr>
</table></div>
<div class="slide" id="rendering-task">
<h1>Rendering Task のパイプライン</h1>
<div align="center" class="align-center"><img alt="images/rendering_pipeline.jpg" class="align-center" src="images/rendering_pipeline.jpg" style="width: 80%; height: 165px;" /></div>
<p>レンダリングはフレームが進む毎に全画面更新する</p>
<dl class="docutils">
<dt><strong>フレーム</strong></dt>
<dd>演算や描画の処理 1ループの間隔</dd>
</dl>
<ol class="arabic simple">
<li>前フレームに抽出した Span を描画する</li>
<li>現フレームのポリゴンから Span を抽出する</li>
<li>次フレームのポリゴンを計算する</li>
</ol>
<p>SG2PP、PP2SP、Draw の 3つのタスクが平行して処理できる</p>
</div>
<div class="slide" id="id17">
<h1>Cerium を用いたゲーム開発</h1>
<div align="center" class="align-center"><img alt="images/cerium_game.jpg" class="align-center" src="images/cerium_game.jpg" style="width: 450px;" /></div>
<div align="center">
  SuperDandy3D
</div><ul class="simple">
<li>3D シューティングゲーム</li>
<li>Cerium を用いて学生が作成</li>
<li>ジョイスティックやキーボードでの操作が可能<ul>
<li>SDL を用いて入力値を取得している</li>
</ul>
</li>
</ul>
</div>
<div class="slide" id="id18">
<h1>ゲームの実行結果(速度検証)</h1>
<table width="95%">
  <tr>
    <td align="center"><p class="small">ポリゴン数</p>
<table border="1" class="small docutils">
<colgroup>
<col width="56%" />
<col width="44%" />
</colgroup>
<tbody valign="top">
<tr><td>自機</td>
<td>250</td>
</tr>
<tr><td>敵機</td>
<td>44</td>
</tr>
<tr><td>背景</td>
<td>2</td>
</tr>
</tbody>
</table>
<p class="small">Mac OS X 以外は Frame Buffer へ直接出力</p>
<p class="small">Mac OS X は SDL 経由で出力している</p>
</td>
<td><table border="1" class="docutils">
<colgroup>
<col width="40%" />
<col width="60%" />
</colgroup>
<tbody valign="top">
<tr><td>Architecture</td>
<td>Speed (FPS : Frame Per Second)</td>
</tr>
<tr><td>Mac OS X 10.5</td>
<td>5.7 FPS</td>
</tr>
<tr><td>Linux (Fedora 10)</td>
<td>7.8 FPS</td>
</tr>
<tr><td>PS3 SPE 1 個</td>
<td>8.1 FPS</td>
</tr>
<tr><td>PS3 SPE 6 個</td>
<td><span class="text-maroon">29.3 FPS</span></td>
</tr>
</tbody>
</table>
    </td>
  </tr>
</table><ul class="simple">
<li>SPE ６個で 1 個のものより 3.6 倍</li>
<li>現状<ul>
<li>SceneGraph の演算を SPE で行っていない</li>
<li>SPE での処理に SIMD 演算を組み込んでいない</li>
</ul>
</li>
<li>速度向上する余地あり</li>
</ul>
</div>
<div class="slide" id="id19">
<h1>他システムとの比較</h1>
<ul class="simple">
<li><span class="text-silver">Cell アーキテクチャの概要</span></li>
<li><span class="text-silver">Many Core プログラミングの特徴</span></li>
<li><span class="text-silver">Task Manager の実装</span></li>
<li><span class="text-silver">Cerium</span></li>
<li><span class="text-big">比較</span></li>
<li><span class="text-silver">まとめと今後の課題</span></li>
</ul>
</div>
<div class="slide" id="osmesa-gallium">
<h1>比較 - OSMesa (Gallium)</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 で動作</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="gallium-con-t">
<h1>比較 - Gallium (Con't)</h1>
<ul class="simple">
<li>実行速度比較<ul>
<li>出力解像度は 1920x1080</li>
<li>地球のテクスチャを貼った球体のオブジェクトを表示</li>
</ul>
</li>
</ul>
<table width="90%">
 <tr>
   <td><div align="center" class="align-center"><img alt="images/com_gallium.jpg" class="align-center" src="images/com_gallium.jpg" style="width: 350px;" /></div>
</td>
<td align="center"><p class="small">ポリゴン数 : 1984</p>
<table border="1" class="small 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>
    </td>
  </tr>
</table><ul class="simple">
<li>Gallium には OpenGL API の機能が全て乗っているわけではない</li>
<li>Cerium とのレンダリングの機能の違い<ul>
<li>光源、アルファブレンディング、etc..</li>
</ul>
</li>
<li>Cerium、Gallium ともにまだ開発段階</li>
</ul>
</div>
<div class="slide" id="opengl">
<h1>比較 - OpenGL</h1>
<dl class="docutils">
<dt>OpenGL</dt>
<dd>オープンソースの3Dグラフィックスプログラムインターフェース</dd>
</dl>
<ul class="simple">
<li>変換行列、光源、カメラなどの API を実装</li>
<li>親子関係の表現も可能</li>
</ul>
<p>Cerium での OpenGL の使用の問題</p>
<ul class="simple">
<li>SceneGraph の OpenGL の API にあわせるオーバーヘッド</li>
<li>SceneGraph は自身の変換行列を持っている<ul>
<li>SceneGraph 単体でオブジェクトの操作は可能</li>
</ul>
</li>
<li>SceneGraph だけで問題ない</li>
</ul>
</div>
<div class="slide" id="opencl">
<h1>比較 - OpenCL</h1>
<dl class="docutils">
<dt><strong>OpenCL</strong> (2008年12月9日 策定)</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: 350px;" /></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>
<li>現在、Cell 用に実装されたものは無い</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 アーキテクチャの理解、及び Cell プログラミングを行う際は
Task Manager が適している</li>
</ul>
</div>
<div class="slide" id="id20">
<h1>結論</h1>
<ul class="simple">
<li><span class="text-silver">Cell アーキテクチャの概要</span></li>
<li><span class="text-silver">Many Core プログラミングの特徴</span></li>
<li><span class="text-silver">Task Manager の実装</span></li>
<li><span class="text-silver">Cerium</span></li>
<li><span class="text-silver">比較</span></li>
<li><span class="text-big">まとめと今後の課題</span></li>
</ul>
</div>
<div class="slide" id="id21">
<h1>まとめ</h1>
<ul class="simple">
<li>並列プログラミングのフレームワークとして
TaskManager を提案し、それを用いた、PS3ゲーム開発フレームワークである
Cerium を開発した</li>
<li>Cerium を用いれば、
学生が手を付けやすい環境(MacOSX、Linux)から開発を始め、
コードの大幅な変更なく PS3 (Cell) での動作を確認できる</li>
</ul>
</div>
<div class="slide" id="id22">
<h1>今後の課題</h1>
<ul class="simple">
<li>SceneGraph の SPE 上での実行</li>
<li>SIMD 演算の使用、もしくはそれに適したデータ構造の採用</li>
<li>プログラムコードの SPE 上での On demand Load<ul>
<li>現在は予めコードを全て置いておく必要がある</li>
<li>SPE のメモリ領域 (256KB) を考えると好ましくない</li>
</ul>
</li>
<li>レンダリングの機能の追加<ul>
<li>アルファブレンディング</li>
<li>光源</li>
<li>Z-sort</li>
</ul>
</li>
</ul>
</div>
<div class="slide" id="id23">
<h1>終</h1>
</div>
</div>
</body>
</html>