view presen/presen1.html @ 22:fe88829c8fe3 draft

add file
author Yutaka_Kinjyo <yutaka@cr.ie.u-ryukyu.ac.jp>
date Sun, 12 Feb 2012 17:51:19 +0900
parents e5e563dc8270
children 02067287fac3
line wrap: on
line source

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
        "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">

<html xmlns="http://www.w3.org/1999/xhtml">

<head>
<title>S5: An Introduction</title>
<!-- metadata -->
<meta name="generator" content="S5" />
<meta name="version" content="S5 1.3" />
<meta name="author" content="Eric A. Meyer" />
<meta name="company" content="Complex Spiral Consulting" />
<!-- meta extensions -->
<meta name="subject" content="S5 1.3beta7" />
<meta name="creator" content="Christian Effenberger" />
<meta name="contributor" content="youcan[64]netzgesta[46]de" />
<meta name="publisher" content="s5.netzgesta.de" />
<meta name="description" content="S5 1.3 is a very flexible and lightweight slide show system available for anyone to use (including transitions and scalable fonts and images)" />
<meta name="keywords" content="S5, slide show, projection-mode, powerpoint-like, scala-like, keynote-like, incremental display, scalable fonts, scalable images, transitions, notes, osf, xoxo, css, javascript, xhtml, public domain" />
<meta name="robots" content="index, follow" />
<meta name="revisit-after" content="7 days" />
<!-- meta temporary -->
<meta http-equiv="content-type" content="text/html; charset=utf-8" />
<meta http-equiv="Content-Script-Type" content="text/javascript" />
<meta http-equiv="Content-Style-Type" content="text/css" />
<!-- configuration parameters -->
<meta name="defaultView" content="slideshow" />
<meta name="controlVis" content="hidden" />
<!-- configuration extensions -->
<meta name="tranSitions" content="true" />
<meta name="fadeDuration" content="500" />
<meta name="incrDuration" content="250" />
<!-- configuration autoplay extension -->
<meta name="autoMatic" content="false" />
<meta name="playLoop" content="true" />
<meta name="playDelay" content="10000" />
<!-- configuration audio extension -->
<meta name="audioSupport" content="false" />
<meta name="audioVolume" content="100" />
<meta name="audioError" content="false" />
<!-- configuration audio debug -->
<meta name="audioDebug" content="false" />
<!-- style sheet links -->
<link rel="stylesheet" href="ui/default_utf/slides.css" type="text/css" media="projection" id="slideProj" />
<link rel="stylesheet" href="ui/default_utf/outline.css" type="text/css" media="screen" id="outlineStyle" />
<link rel="stylesheet" href="ui/default_utf/print.css" type="text/css" media="print" id="slidePrint" />
<link rel="stylesheet" href="ui/default_utf/opera.css" type="text/css" media="projection" id="operaFix" />
<!-- embedded styles -->
<style type="text/css" media="all">
.imgcon {width: 100%; margin: 0 auto; padding: 0; text-align: center;}
#anim {width: 33%; height: 320px; position: relative;}
#anim img {position: absolute; top: 0px; left: 0px;}

</style>
<!-- S5 JS -->
<script src="ui/default_utf/slides.js" type="text/javascript"></script>

</head>
<body>

<div class="layout">
<div id="controls"><!-- DO NOT EDIT --></div>
<div id="currentSlide"><!-- DO NOT EDIT --></div>
<div id="header"></div>
<div id="footer">

<h1></h1>
<h2></h2>
</div>
</div>

<ol class="xoxo presentation">

<li class="slide">
<h1>並列プログラミングフレームワーク Cerium の改良</h1>
<h3>金城 裕</h3>
<h4>琉球大学理工学研究科情報工学専攻</h4>
<div class="handout"></div>
</li>

<li class="slide">
<h1>研究背景と目的(1/2)</h1>
<font size="5">
当研究室では、マルチコアCPU上での開発を支援するたの、並列プログラミングフレームワーク Cerium を開発し、学生実験で使用している。本研究では
Cerium の信頼性の向上を目的とし、改良を行った (信頼性 = 仕様通りに動作する)<br>

マルチコア上の並列プログラミングでは
<ul>
  <li>並列処理部分の特定や同期処理を適切に行わなければ、台数効果は得られない。</li>
  <li>再現性ないバグなどが発生する可能性がある</li>
  <li>アーキテクチャを理解し最適なプログラムを書く必要がある</li>
</ul><br>

など信頼性のあるプログラムを開発するには逐次プログラミングよりも技術と手間がかかる問題がある<br>
Cell上でのゲーム作成を行う学生実験でも、講義期間中に作品が一定のレベルに達しない問題が生じた。そこで学生実験での使用を考慮した フレームワーク Cerium を開発した<br>

</font>

<li class="slide">
<h1>研究背景と目的(2/2)</h1>
<font size="5">
Cerium を用いて 期間中のゲームの作成が可能になった。しかし学生実験での使用や、例題の実装を行い Cerium の信頼性が十分でない点が明らかになった。
<ul>
  <li>仕様通りの稼働率がでない</li>
  <li>アーキテクチャ依存の記述が含まれている</li>
</ul><br>
以上の問題点を解決するため
<ul>
  <li>ソフトウェアMailQueueの実装</li>
  <li>TaskをグルーピングするTaskArrayの実装</li>
  <li>明示的なDMAロードを隠蔽するMemorySegmentのAPIの実装</li>
</ul>
などの改良を行い、信頼性のある並列プログラミングフレームワークを目指す。
</font>

<li class="slide">
<h1>Cell Broadband Engine</h1>
<font size="5">

研究、実験の題材となった Cell Broadband Engine とは、
<ul>
  <li>ソニー、SCE、 IBM、 東芝によって開発されたプロセッサ</li>
  <li>マルチコアで、9つのコアを持つ</li>
  <ul>
    <li>制御用コア PorwerPC Processor Element 1基</li>
    <li>演算用コア Synergistic Processor Element 8基 (実験で使用できるのは6基)</li>
    <li>各コアは Element Interconnect Bus を経由してデータアクセスを行う</li>
  </ul>
</ul>

<p style="text-align: center;">
<img class="scale" src="pix/cell.png" alt="" title="At a Glance" />
</p>

</font>

<li class="slide">
<h1>DMA転送</h1>
SPE は直接 MainMemory にアクセスできない。 明示的な DMA 転送命令を用いてデータにアクセスする。データは

<ul>
  <li>16アラインメントに揃える</li>
  <li>16byte の倍数のサイズ</li>
  <li>一度の転送は16KB の大きさまで</li>
</ul>


<li class="slide">
<h1>Mailbox</h1>

PPE と SPE の通信には Mailbox を用いる

<ul>
  <li>PPE と SPE 間で32ビットメッセージの交換ができる</li>
  <li>Mail の Queue は3種類</li>
  <ul>
    <li>SPU inbound Mailbox: PPE -> SPE</li>
    <li>SPU Outbound Mailbox: SPE -> PPE</li>
    <li>SPU Outbound interrupt Mailbox: SPE -> PPE (割り込み)</li>
  </ul>
</ul>

<li class="slide">
<h1>Cerium</h1>
Cerium とは
<ul>
  <li>並列プログラミング用のフレームワーク</li>
  <li>学生実験での使用を考慮して PS3/Cell, Linux, MacOSX で動作する</li>
  <li>構成</li>
  <ul>
    <li>TaskManager</li>
    <li>RenderingEngine</li>
    <li>SceneGraph</li>
  </ul>
</ul>


<li class="slide">
<h1>TaskManager</h1>
TaskManager とは Task のスケジューラ

<ul>
  <li>Task とよばれるデータ構造を提供</li>
  <li>処理(単位は関数に近い)を Task で記述していく</li>
  <li>定義された、Task の情報に沿って各コアに処理を割り振る</li>
</ul>

Task で記述された部分の、自動的な並列処理スケジューリングを行う。

<li class="slide">
<h1>RenderingEngine(1/2)</h1>
PS3 では Graphics Engien の仕様が公開されていないので、独自の RenderingEngine を開発した。
Task で記述され、主に3つの Task から構成される
<ul>
  <li>CreatePolygonTask</li>
  <ul>
    <li>モデリングデータを、三角形のポリゴンに変換する</li>
  </ul>
  <li>CreateSpanTask</li>
  <ul>
    <li>ポリゴンを水平な線(Span)に分割する</li>
  </ul>
  <li>DrawSpanTask</li>
  <ul>
    <li>Span を Texture とマッピングし画面に出力する</li>
  </ul>
</ul>

<li class="slide">
<h1>RenderingEngine(2/2)</h1>

例: Cube のモデリングデータの場合には、以下のように Task が働く。

<p style="text-align: center;">
<img class="scale" src="pix/rendering3.png" width="50%" alt="" title="At a Glance" />
</p>

<li class="slide">
<h1>SceneGraph</h1>
ゲームのシーンを構成する木構造のグラフ。

<li class="slide">
<h1>Cerium の改良</h1>
<font size="5">
RenderingEngine を用いた例題で、ball bound, panel がある。(FPS = Frame per second)

<table border="1" cellspacing="0" cellspacing="2" cellpadding="5"  align="center">
<tr>
<th></th>
<th>FPS</th>
<th>DMA転送待ち割合</th>
<th>mail待ち割合</th>
<th>SPE稼働率</th>
</tr>
<tr>
<th>ball bound</th>
<th>30.2</th>
<th>1.8%</th>
<th>74.3%</th>
<th>23.7%</th>
</tr>
<tr>
<th>panel</th>
<th>4.0</th>
<th>21.3%</th>
<th>11.1%</th>
<th>67.6%</th>
</tr>
</table>

<ul>
  <li>panel</li>
  <ul>
    <li>解像度1980x1080の一枚の画像の描画行う。</li>
  </ul>
  <li>ball bound</li>
  <ul>
    <li>球が跳ねる例題。</li>
  </ul>
</ul>

ball bound では Mail 待ちが約70%と、稼働率が出ていない。<br>
panel は ball bound より処理の描画の処理が重く、その分稼働率が高くなっている。
アムダールの法則より稼働率がでないとマルチコアの性能は発揮されない。フレームワークとしての信頼性が十分でない
</font>

<li class="slide">
<h1>Mail 通知のスケジューリング</h1>
Cerium では SPE が Mail で 待ち時間が発生するタイミングは2つ

<ul>
  <li>TaskList を待つ場合</li>
  <li>Mail の書き込みを待つ場合</li>
  <ul>

  </ul>
</ul>

<li class="slide">
<h1>TaskListのMail待ち</h1>
TaskList は処理する Task の List である。PPE で生成され SPE へ Mail で通知される

<p style="text-align: center;">
<img class="scale" src="pix/tasklistmail1.png" width="80%" alt="" title="At a Glance" />
</p>

TaskList が生成され SPE に通知されるまで、SPE に待ち時間が発生する。

<li class="slide">
<h1>Mail の書き込み待ち</h1>
Task が終了した際と TaskList が終了した際に SPE が Mailbox へ書き込みを行う(依存関係解決のため)。Outbound Mailbox はサイズが1なので、他のMailが書き込まれている場合、それが PPE側から読み込まれるまで、待つ。

<p style="text-align: center;">
<img class="scale" src="pix/mailschedule2.png" width="80%" alt="" title="At a Glance" />
</p>

TaskList が生成され SPE に通知されるまで、SPE に待ち時間が発生する。


<li class="slide">
<h1>TaskArray(1/3)</h1>
TaskList は Cerium 側で固定長であり、ユーザは変更することができない。ユーザが設定できる TaskList のようなものが、TaskArrayである。TaskArray は複数の Task をグルーピングできる。

<p style="text-align: center;">
<img class="scale" src="pix/taskarray1.png" width="80%" alt="" title="At a Glance" />
</p>

<li class="slide">
<h1>TaskArray(2/3)</h1>
例えば TaskListのサイズが4, TaskArray のサイズが4の場合、Task が8個の場合

<p style="text-align: center;">
<img class="scale" src="pix/taskarray2.png" width="80%" alt="" title="At a Glance" />
</p>

グルーピングされるため Task 毎の Mail 回数が減る。TaskList の要求回数が減る。そのため Mail の待ち時間が入る箇所が削減され、Mail の待ち時間自体の削減につながる。

<li class="slide">
<h1>TaskArray(3/3)</h1>
<font size="5">
TaskArray の効果を示す

<table border="1" cellspacing="0" cellspacing="2" cellpadding="5"  align="center">
<caption>ballbound</caption>
<tr>
<th>TaskArray</th>
<th>FPS</th>
<th>DMA転送待ち時間</th>
<th>mail待ちの割合</th>
<th>SPE稼働率</th>
</tr>
<tr>
<th> なし </th>
<th>30.2</th>
<th>1.8%</th>
<th>74.3%</th>
<th>23.7%</th>
</tr>
<tr>

<tr>
<th> あり </th>
<th>32.2</th>
<th>2.5%</th>
<th>66.7%</th>
<th>30.8%</th>
</tr>

</table>

<table border="1" cellspacing="0" cellspacing="2" cellpadding="5"  align="center">
<caption>panel</caption>
<tr>
<th>TaskArray</th>
<th>FPS</th>
<th>DMA転送待ち時間</th>
<th>mail待ちの割合</th>
<th>SPE稼働率</th>
</tr>

<th>なし</th>
<th>4.0</th>
<th>21.3%</th>
<th>11.1%</th>
<th>67.6%</th>
</tr>


<tr>
<th>あり</th>
<th>4.2</th>
<th>22.5%</th>
<th>5.7%</th>
<th>71.8%</th>
</tr>
</table>

TaskArray を ball bound, panel の DrawSpanTask に適応。FPS、稼働率の向上。Mail 待ちの時間が削減された

</font>

<li class="slide">
<h1>MailQueue(1/3)</h1>
ソフトウェア MailQueue の実装

<ul>
  <li>SPE から Mailbox に書き出せない場合に MailQueue へと書きだす</li>
  <li>MailQueue に Mail がある場合は、MailQueue から Mailbox へ書き出す</li>
  <li>MailQueue に残っている Mail は TaskList のTask を消化した時点で、すべて書き出す処理を挟む</li>
</ul>

Task 毎の Mail 書き込み時の待ち時間を削減するのが目的

<li class="slide">
<h1>MailQueue(2/3)</h1>

Mailbox に書き込めない場合は、MailQueue に書き込む例

<p style="text-align: center;">
<img class="scale" src="pix/mailqueue1.png" width="70%" alt="" title="At a Glance" />
</p>

<li class="slide">
<h1>MailQueue(3/3)</h1>
MailQeueuの効果

<font size="5">
<table border="1" cellspacing="0" cellspacing="2" cellpadding="5"  align="center">
<caption>ball bound</caption>
<tr>
<th>MailQueue</th>
<th>FPS</th>
<th>DMA転送待ち時間</th>
<th>mail待ちの割合</th>
<th>SPE稼働率</th>
</tr>
<tr>
<th> なし </th>
<th>32.2</th>
<th>2.5%</th>
<th>66.7%</th>
<th>30.8%</th>
</tr>
<tr>

<tr>
<th> あり </th>
<th>41.7</th>
<th>3.3%</th>
<th>56.8%</th>
<th>40.0%</th>
</tr>

</table>

<table border="1" cellspacing="0" cellspacing="2" cellpadding="5"  align="center">
<caption>panel</caption>
<tr>
<th>MailQueue</th>
<th>FPS</th>
<th>DMA転送待ち時間</th>
<th>mail待ちの割合</th>
<th>SPE稼働率</th>
</tr>

<tr>
<th>なし</th>
<th>4.2</th>
<th>22.5%</th>
<th>5.7%</th>
<th>71.8%</th>
</tr>

<th>あり</th>
<th>4.2</th>
<th>23.7%</th>
<th>4.1%</th>
<th>72.3%</th>
</tr>

</table>
</font>

<li class="slide">
<h1>MemorySegment(1/7)</h1>
CreateSpanTask では明示的にDMA転送命令を記述している。

<ul>
  <li>処理するデータ構造上の理由、Task内でのデータロードが必要</li>
  <li>DMA転送命令は Cell アーキテクチャ依存の記述</li>
  <li>他のアーキテクチャなどでは不要</li>
</ul><br>

アーキテクチャ依存の記述を隠蔽できるAPIが必要になった。

<li class="slide">
<h1>MemorySegment(2/7)</h1>
明示的なDMA転送命令を隠蔽するため MemorySegment を実装した

<ul>
  <li>一定のメモリを確保し、ハッシュで管理(LRU方式)</li>
  <li>API 内部で自動的なキャッシュを行う (サイズは任意に設定できる)</li>
  <li>dma 命令を MemorySegment というデータ構造を操作する命令に置き換える</li>
  <ul>
    <li>dma_load -> get_segment</li>
    <li>dma_store -> put_segment</li>
    <li>dma_wait -> wait_segment</li>
  </ul>
</ul>

<li class="slide">
<h1>MemorySegment(3/7)</h1>

<p style="text-align: center;">
<img class="scale" src="pix/getsegment1.png" width="50%" alt="" title="At a Glance" />
</p>


<li class="slide">
<h1>MemorySegment(4/7)</h1>

<p style="text-align: center;">
<img class="scale" src="pix/putsegment1.png" width="50%" alt="" title="At a Glance" />
</p>


<li class="slide">
<h1>MemorySegment(5/7)</h1>
明示的に記述したDMA転送命令の例
<pre>
loop() {

  tmp_data = get_data;
  get_data = send_data;
  send_data = tmp_data;

  dma_wait(WAIT_STORE);

  dma_store(send_data, send_addr, data_size, WAIT_STORE);
  dma_load(get_data, get_addr, data_size, WAIT_LOAD);

  dma_wait(WAIT_LOAD);

  calc(get_data);

}
</pre>

<li class="slide">
<h1>MemorySegment(6/7)</h1>
MemorySegment を適応させた例
<pre>
loop() {

  wait_segment(put_ms);

  put_ms = get_ms;

  put_segment(put_ms);
  get_ms = get_segment(get_addr, ml);

  wait_segment(get_ms);
  get_data =  get_ms->data;

  calc(get_data);
}
</pre>

<li class="slide">
<h1>MemorySegment(7/7)</h1>
MemorySemgment を導入

<ul>
  <li>アーキテクチャ依存の記述を隠蔽することに成功した</li>
  <li>汎用的な Task 内でのデータ転送APIとして使用でき</li>
  <li>Core i7, Xeon などの汎用のメニーコアにも対応可能</li>
  <li>CreateSpanTask 内のデータロードと、DrawspanTask の Texture のロードに使用している</li>
</ul>

<li class="slide">
<h1>まとめ(1)</h1>
並列プログラミングフレームワーク Cerium の改良を行った。

<ul>
  <li>Mail の待ち時間を削減、稼働率とFPSの向上に成功</li>
  <li>汎用的なデータ転送APIを実装した</li>
  <li>Cell アーキテクチャ依存の記述の隠蔽に成功</li>
</ul>


<li class="slide">
<h1>まとめ(2)</h1>

改良の効果を示す

<font size="5">
<table border="1" cellspacing="0" cellspacing="2" cellpadding="5"  align="center">
<caption>ball bound</caption>
<tr>
<th></th>
<th>FPS</th>
<th>DMA転送待ち時間</th>
<th>mail待ちの割合</th>
<th>SPE稼働率</th>
</tr>
<tr>
<th>改良前</th>
<th>30.2</th>
<th>1.8%</th>
<th>74.3%</th>
<th>23.7%</th>
</tr>
<tr>

<tr>
<th>改良後</th>
<th>41.7</th>
<th>3.3%</th>
<th>56.8%</th>
<th>40.0%</th>
</tr>
</table>

<table border="1" cellspacing="0" cellspacing="2" cellpadding="5"  align="center">
<caption>panel</caption>
<tr>
<th></th>
<th>FPS</th>
<th>DMA転送待ち時間</th>
<th>mail待ちの割合</th>
<th>SPE稼働率</th>
</tr>

<tr>
<th>改良前</th>
<th>4.0</th>
<th>21.3%</th>
<th>11.1%</th>
<th>67.6%</th>
</tr>

<th>改良後</th>
<th>4.2</th>
<th>23.7%</th>
<th>4.1%</th>
<th>72.3%</th>
</tr>

</table>
</font>

<li class="slide">
<h1>OpenGL との比較</h1>
学生実験で作成された シューティングゲーム「SuperDandy」 を例題に OpenGL と比較。OpenGL は PPE 1基のみを使用。Cerium は
SPE6基+PPE1基を使用した。

<table border="1" cellspacing="0" cellspacing="2" cellpadding="5"  align="center">
<caption>シューティングゲーム</caption>
<tr>
<th></th>
<th>OpenGL</th>
<th>Cerium</th>
<th>性能差</th>
</tr>

<tr>
<th>SuperDandy</th>
<th>17.5 FPS</th>
<th>49.5 FPS</th>
<th>2.9 倍</th>
</tr>

</table>


<li class="slide">
<h1>今後の課題</h1>
アムダールの法則より、


<li class="slide">
<h1>自動的な依存関係の解決</h1>

<li class="slide">
<h1>Task 化による並列化率の向上</h1>

<li class="slide">
<h1>SPE の LS の利用方法</h1>


<li class="slide">
<h1></h1>

/*end*/

</ol>

</body>
</html>