Mercurial > hg > Papers > 2012 > yutaka-master

view presen/presen1.html @ 24:716f0a413687 draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add file
author Yutaka_Kinjyo <yutaka@cr.ie.u-ryukyu.ac.jp>
date Mon, 13 Feb 2012 11:55:11 +0900
parents 02067287fac3
children fa8b52588f67
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>研究背景と目的</h1>
<font size="5">
<u>本研究では並列プログラムフレームワーク Cerium の改良を行い、並列処理の並列度向上とCell以外のマルチコアCPUへの対応に成功した。</u><br>

<img src="pix/amdahl.jpg" style="display:block; width:50%; float: right; margin-top:0%">

<ul>
  <li>アムダールの法則より、プログラム全体の並列化率が低ければマルチコアの性能を活かすことができない</li>
  <li>現在の Cerium を用いたプログラムの開発では、高い並列度が保証されない</li>
  <li>Cerium はPS3/Cell での並列処理を行えるが、当初はCell向けに作られた為、他の汎用マルチコアCPU に対応していない</li>
</ul><br>

Cerium の他CPUへの対応と、自明な並列度があるレンダリングとゲーム処理を例題に、高い並列度の維持を目的とする

</font>


<li class="slide">
<h1>発表構成</h1>
<ul>
  <li>Cellの機能</li>
  <li>Ceriumの構成</li>
  <li>Cerium の問題点1(Mail の待ち時間)</li>
  <ul>
    <li>TaskArray での改良と効果</li>
    <li>MailQueue での改良と効果</li>
  </ul>
  <li>Cerium の問題点2(アーキテクチャ依存の記述)</li>
  <ul>
    <li>MemorySegmentでの改良と効果</li>
  </ul>
  <li>まとめ</li>
  <li>OpenGLとの比較</li>
  <li>今後の課題</li>
</ul>

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

研究、実験の題材となった Cell Broadband Engine とは、

<img src="pix/cell.png" style="display:block; width:50%; float: right; margin-top:0%">

<ul>
  <li>1基のPPEと8基のSPEがリングバス(EIB)で構成されている。動作クロックは3.2GHz(実験で使えるSPEの数は6基)</li>
  <li>リングバスのデータ帯域幅は1サイクルあたり最大96byte(3.2GHz駆動時には307.2GB/sec)</li>
  <li>SPEは256KBのLocalStore(LS)を持つ</li>
  <li>SPEからメインメモリへは直接アクセスできない</li>
  <ul>
    <li>SPEが持つMFC(Memory Flow Controller)へDMA命令を送ることで行う</li>
  </ul>
</ul>

</font>

<li class="slide">
<h1>Cellの機能</h1>
<font size="6">

<u>Mailbox</u>

<ul>
  <li>SPEのMFC内にあるFIFOキュー</li>
  <li>PPE と SPE 間で32ビットメッセージの交換ができる</li>
  <li>Mail の Queue の種類</li>
  <ul>
    <li>SPU inbound Mailbox: PPE -> SPE (キューのサイズは4)</li>
    <li>SPU Outbound Mailbox: SPE -> PPE (キューのサイズは1)</li>
  </ul>
</ul><br>

Outbound Mailbox へ Mail を書き込む際、キューがいっぱいの時は、PPE 側から読み込まれるまで待つ。

</font>
<li class="slide">
<h1>Cerium</h1>
<font size="5">
Cerium の構成

<img src="pix/cerium.png" style="display:block; width:50%; float: right; margin-top:0%">

<ul>
  <li>TaskManager</li>
  <ul>
    <li><font size="5">ユーザが定義したTaskを管理し、各コアに割り当てる</font></li>
  </ul>

  <li>RenderingEngine</li>
  <ul>
    <li><font size="5">オブジェクトを画面に描画する</font></li>
    <li><font size="5">3種類のTaskから構成される</font></li>
  </ul>

  <li>SceneGraph</li>
  <ul>
    <li><font size="5">ゲームのシーンを作成し、それを切り替えながらゲームを進行する</font></li>
    <li><font size="5">OpenSceneGraphのようなもの</font></li>
  </ul>

</ul><br>

</font>

<li class="slide">
<h1>TaskManager</h1>
<font size="5">
TaskManager は、Taskと呼ばれる分割された各プログラムを管理する。Task の単位
はサブルーチンである。Task 同士の依存関係を考慮しながら実行していく。</p>
<p>Task を生成する際に、以下のような要素が設定可能である</p>

<ul>
<li><b>input data, output data, parameter</b><br>
　これらは関数でいうところの引数に価する</li>
<li><b>cpu type</b><br>
　Task を PPE または SPE のどちらで実行するのかを示している</li>
<li><b>dependency</b></li>
　他の Task との依存関係を示している
</li>
</ul>

</font>

<li class="slide">
<h1>TaskManager</h1>
<font size="5">

<img src="pix/scheduler1.png" style="display:block; width:50%; float: right; margin-top:0%">

<ul>
  <li>生成された Task は TaskList としてまとめられ SPE で実行される</li>
  <li>SPE 側では受け取った TaskList から Task を受け取り、パイプライン的に実行していく</li>
</ul>

</font>


<li class="slide">
<h1>Mailのやり取り</h1>
<font size="6">
<ul>
  <li>SPE と PPE 間の同期は Mail のやり取りを行う</li>
  <br>
  <li>Mailのタイミング</li>
  <br>
  <font color="red">SPE -> PPE</font>
  <ul>
    <li>タスクの終了(Taskの依存関係の解決のため)</li>
    <li>新しい TaskList のリクエスト</li>
  </ul>
  <br>
  <font color="red">PPE -> SPE</font>
  <ul>
    <li>新しい TaskList の送信</li>
  </ul>
</ul>

</font>

<li class="slide">
<h1>PPEとSPEで行われるパイプライン処理</h1>
<font size="5">
PPEとSPE 間で Mail を介して Task の実行をパイプライン化している。
Mail の受け取りは PPE 側から定期的にポーリングするしかなく、PPE のMain ループで定期的に チェックしている。<br>
<u>パイプラインがうまく動作する例</u>
<img src="pix/mailsched1.png" style="display:block; width:60%; float: center; margin-top:0%">

当初はこれでうまくパイプラインが実行されていると思われていたが、うまくいかないパターンが存在することが明らかになった。


</font>

<li class="slide">
<h1>PPEとSPEで行われるパイプライン処理</h1>
<font size="5">
PPE 側で実行される Task の処理が多い時に、Mail チェックの頻度が少なくなる。
Outbound Mailbox がひとつの Mail で占有される時間が長くなり、SPE 側の終了した Task の終了Mail が書き出せなくなる。
そのため、書き込み待ちが発生し、SPE に待ち時間が発生する。<br>
<u>パイプラインが崩れてしまう例</u>
<img src="pix/mailsched2.png" style="display:block; width:57%; float: center; margin-top:0%">

これが並列度の低下を招いている。
</font>


<li class="slide">
<h1>PPEとSPEで行われるパイプライン処理</h1>
<font size="5">
そこで、その問題を解決するため、一つ目のアプローチとして Outbound Mailbox と Task の終了処理の間に ソフトウェア MailQueue を導入した。
Outbound Mailbox がいっぱいの場合その Queue に Task 終了 Mail を挿入し、次の Task が実行されるようになった<br>

<u>MailQueueを導入によりパイプラインが正常に動作している例</u>
<img src="pix/mailsched3.png" style="display:block; width:55%; float: center; margin-top:0%">

そのため、SPE の待ち時間が無くなり、並列度が向上した。<br>
</font>

<li class="slide">
<h1>PPEとSPEで行われるパイプライン処理</h1>
<font size="5">
二つ目のアプローチとして、複数の Task を TaskArray としてグルーピングする 方法を考えた。
依存関係が線形である Task は TaskArray としてまとめることにより、Task 終了のメールを減らすことが出来る。
<img src="pix/taskarray3.png" style="display:block; width:60%; float: center; margin-top:0%">
TaskArrayを導入することによって、wait time が削減された。
<img src="pix/taskarray2.png" style="display:block; width:60%; float: center; margin-top:0%">
これにより、並列度が向上した。
</font>

<li class="slide">
<h1>改良効果の測定</h1>
RenderingEngine を用いて、効果を計測した。レンダリングの例題として、ball bound と panelを用いた。<br>
ball bound は赤いボールが跳ねる例題である。描画領域が画面の中でボールの部分だけであり、描画領域が狭いと言える。<br>
panel は画面一面に画像を描画する例題である。描画領域が最大である。<br>
<img src="pix/ball_bound1.png" style="display:block; width:30%; float: left; margin-top:0%">
<img src="pix/panel1.png" style="display:block; width:30%; float: right; margin:5% 20% 0% 20%">

</font>

<li class="slide">
<h1>改良効果の測定</h1>
<font size="5">

<table border="1" cellspacing="0" cellspacing="2" cellpadding="5"  align="center">
<caption>ballbound</caption>

<tr>
<th>改良項目</th>
<th>FPS</th>
<th>mail待ちの割合</th>
<th>SPE稼働率</th>
<th>SPE稼働率の差分</th>
</tr>

<tr>
<th>改良なし</th>
<th>30.2</th>
<th>74.3%</th>
<th>23.7%</th>
<th>-</th>
</tr>

<tr>
<th>TaskArray適用後</th>
<th>32.2</th>
<th>66.7%</th>
<th>30.8%</th>
<th><font color="red">+7.1%</font></th>
</tr>

<tr>
<th>MailQueue適用後</th>
<th>41.7</th>
<th>56.8%</th>
<th>40.0%</th>
<th><font color="red">+10.8%</font></th>
</tr>


</table>

<table border="1" cellspacing="0" cellspacing="2" cellpadding="5"  align="center">
<caption>panel</caption>

<tr>
<th>改良項目</th>
<th>FPS</th>
<th>mail待ちの割合</th>
<th>SPE稼働率</th>
<th>SPE稼働率の差分</th>
</tr>

<th>改良なし</th>
<th>4.0</th>
<th>11.1%</th>
<th>67.6%</th>
<th>-</th>
</tr>

<tr>
<th>TaskArray適用後</th>
<th>4.2</th>
<th>5.7%</th>
<th>71.8%</th>
<th><font color="red">+4.2%</font></th>
</tr>

<tr>
<th>MailQueue適用後</th>
<th>4.2</th>
<th>4.1%</th>
<th>72.3%</th>
<th><font color="red">+0.5%</font></th>
</tr>
</table>

改良を加え 各例題 の<u>FPS、稼働率の向上。Mail 待ちの時間が削減され、並列度が向上したといえる</u>

</font>

<li class="slide">
<h1>他のアーキテクチャへの対応</h1>
PS3 が Linux をサポートしなくなっため、これ以上のCell上での実験が困難になってきている。<br>
<ul>
  <li>これまでアーキテクチャ依存を排除して MacOSX,Linux などの上でも動作する設計を行なっていたため他のアーキテクチャでも動作はする。</li>
  <li>しかし並列実行はサポートしておらず、FIFOを用いた 逐次処理のみをサポートしていた。 </li>
</ul>

そこで、汎用マルチコア向けのパラレルタスクのサポートを行った。

<li class="slide">
<h1>他のアーキテクチャへの対応</h1>

異なるアーキテクチャで動作させるにあたり、アーキテクチャの依存を吸収できるインターフェイスが望ましい。<br>
現在のSPEからのメモリアクセスは直接DMA転送を行うのではなく、MemorySegment API を用いて記述している。
MemorySegment API は、読み込んだデータの LSへのLRU方式のキャッシュをサポートする。そのため無駄なデータの転送が
削減された。
このAPIを用いる前は、Task内部で直接DMA転送を行っており、一度LSに読み込んだデータを再利用する機構がなかった。
このMemorySegmentのAPIには MainMemory のアドレスが用いられており、Cell 以外のアーキテクチャでも問題なく動作する。



<li class="slide">
<h1>Ceriumの改良-MemorySegment(1/6)</h1>
明示的なDMA転送命令を隠蔽するため MemorySegment を実装した
MemorySegemnt はデータ構造。LS 内のデータを管理する。
<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>Ceriumの改良-MemorySegment(2/6)</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>Ceriumの改良-MemorySegment(3/6)</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>Ceriumの改良-MemorySegment(6/6)</h1>
MemorySegment を導入し、

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

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

<ul>
  <li>MailQeueu, TaskArry を実装、導入した。その結果 Mail の待ち時間の削減、稼働率と FPS の向上に成功した</li>
  <li>MemorySegmentを適応し、汎用的なデータ転送APIが利用できるようになった。</li>
</ul><br>

以上の改良を行い、稼働率の向上、Cellのみでなく、他の汎用マルチコアCPUへの対応にも成功した。

<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>

<ul>
  <li>SceneGraph 部分の Task 化</li>
  <ul>
    <li>Task 化によって並列化率の向上</li>
  </ul>
  <li>自動的な依存関係の解決</li>
  <ul>
    <li>扱うデータから Task の依存関係がわかる</li>
    <li>ユーザが複雑な依存関係を設定しない</li>
  </ul>
  <li>DataSegment</li>
  <ul>
    <li>プログラムコードはすべて LS に置いている</li>
    <li>LS の容量を圧迫しプログラムが動作しなくなる</li>
    <li>すべてのデータを扱う包括的なデータ構造が必要</li>
  </ul>
</ul>

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

/*end*/

</ol>

</body>
</html>