view presen/presen1.html @ 34:472f45ab9fca draft default tip

fix
author Yutaka_Kinjyo <yutaka@cr.ie.u-ryukyu.ac.jp>
date Thu, 16 Feb 2012 23:46:16 +0900
parents fa8b52588f67
children
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/amdahl1.png" 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>コアの待ち時間の削減</li>
  <ul>
    <li>TaskArray での改良と効果</li>
    <li>MailQueue での改良と効果</li>
  </ul>
  <li>他のアーキテクチャへの対応</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>PPEとSPEはMFC(Memory Flow Controller)を持つ</li>
  <li>SPEからメインメモリへは直接アクセスできない</li>
  <ul>
    <li>SPEが持つMFCへ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">

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


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


</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 の実行をパイプライン化している。
PPE が SPE側 から送られてくる 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/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>

<font size="5">

Cerium では Task内部でのデータ転送を行うときは、DMA転送を行ってた。Core i7 や Xeon のような SharedMemory に対応するために
DMA転送は不要である<br>
そこで、Task内部でのデータ転送を抽象化する MemorySegment を実装した。

<ul>
  <li>MemorySegment はデータ構造である</li>
  <li>MainMemory と SPE LS をマッピングする</li>
  <li>LS 内に一定のメモリを確保し、キャッシュ機能を持つ</li>
  <li>キャッシュはLRU方式で管理する</li>
</ul><br>

このMemorySegmentのAPIには MainMemory のアドレスが用いられており、Cell 以外のアーキテクチャでも問題なく動作する。<br>

</font>

<li class="slide">
<h1>MemorySegmentのgetの様子</h1>

MemorySegment の API として、get_segmentがある。指定された MainMemory のアドレスから SPE LS へのデータロードが可能である。

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

<li class="slide">
<h1>MemorySegment</h1>
MemorySegment を導入し、

<ul>
  <li>アーキテクチャ依存の記述を隠蔽することに成功した</li>
  <li>Cellのような分散メモリ環境と、Intel Xeon のような共有メモリ環境に Cerium はどちらの環境でも動作可能になった</li>
</ul>

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

<ul>
  <li>MailQeueu, TaskArrey を実装、導入</li>
  <li>MemorySegmentの適応</li>
</ul><br>

以上の改良を行い、約18%稼働率の向上、とShardMemoryマルチコア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>
<font size="5">
<ul>
  <li>自動的な依存関係の解決</li>
  <ul>
    <li>扱うデータから Task の依存関係がわかる</li>
    <li>ユーザが複雑な依存関係を設定しない</li>
  </ul>
  <li>DataSegmentの設計</li>
  <ul>
    <li>MemorySegmentでは、Task 内でのデータロードを抽象化した</li>
    <li>Task内でのデータロードだけでなく、すべてのデータや扱うプログラムなどを管理する包括的なデータ構造が必要になる</li>
  </ul>
  <li>そのDataSegment の設計は分散ネットワーク環境にも適応でき、それについては次の赤嶺が発表する</li>
  <li>また現在 CeriumはIntel Xeon上に移行され、並列動作する。その結果は當間が卒業研究として発表する</li>
  <li>彼らの発表にも乞うご期待!</li>
</ul>
</font>

<li class="slide">
<h1>発表文献</h1>
<font size="5">
<ul>
  <li>金城裕,河野真治,多賀野海人,小林佑亮. ゲームフレームワーク Cerium TaskMan- ager の改良, 情報処理学会システムソフトウェアとオペレーティング・システム研 究会 (OS), April, 2011</li>
  <li>金城 裕 , 河野 真治. Fine grain Task Manager Cerium のチューニング, 日本ソフト ウェア科学会第 27 回大会論文集, Sep, 2010</li>
</ul>

</ol>
</font>

</body>
</html>