Mercurial > hg > Papers > 2018 > parusu-master
changeset 96:14bd1b466bcc
Update slide
| author | Tatsuki IHA <innparusu@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Tue, 13 Feb 2018 03:36:25 +0900 |
| parents | 3fddb8ee71ea |
| children | 8596c1e30858 |
| files | slide/images/compareExamples.svg slide/slide.html slide/slide.md |
| diffstat | 3 files changed, 322 insertions(+), 154 deletions(-) [+] |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/slide/images/compareExamples.svg Tue Feb 13 03:36:25 2018 +0900 @@ -0,0 +1,170 @@ +<?xml version="1.0" encoding="utf-8" standalone="no"?> +<svg + width="600" height="480" + viewBox="0 0 600 480" + xmlns="http://www.w3.org/2000/svg" + xmlns:xlink="http://www.w3.org/1999/xlink" +> + +<title>Gnuplot</title> +<desc>Produced by GNUPLOT 5.2 patchlevel 2 </desc> + +<g id="gnuplot_canvas"> + +<rect x="0" y="0" width="600" height="480" fill="none"/> +<defs> + + <circle id='gpDot' r='0.5' stroke-width='0.5'/> + <path id='gpPt0' stroke-width='0.222' stroke='currentColor' d='M-1,0 h2 M0,-1 v2'/> + <path id='gpPt1' stroke-width='0.222' stroke='currentColor' d='M-1,-1 L1,1 M1,-1 L-1,1'/> + <path id='gpPt2' stroke-width='0.222' stroke='currentColor' d='M-1,0 L1,0 M0,-1 L0,1 M-1,-1 L1,1 M-1,1 L1,-1'/> + <rect id='gpPt3' stroke-width='0.222' stroke='currentColor' x='-1' y='-1' width='2' height='2'/> + <rect id='gpPt4' stroke-width='0.222' stroke='currentColor' fill='currentColor' x='-1' y='-1' width='2' height='2'/> + <circle id='gpPt5' stroke-width='0.222' stroke='currentColor' cx='0' cy='0' r='1'/> + <use xlink:href='#gpPt5' id='gpPt6' fill='currentColor' stroke='none'/> + <path id='gpPt7' stroke-width='0.222' stroke='currentColor' d='M0,-1.33 L-1.33,0.67 L1.33,0.67 z'/> + <use xlink:href='#gpPt7' id='gpPt8' fill='currentColor' stroke='none'/> + <use xlink:href='#gpPt7' id='gpPt9' stroke='currentColor' transform='rotate(180)'/> + <use xlink:href='#gpPt9' id='gpPt10' fill='currentColor' stroke='none'/> + <use xlink:href='#gpPt3' id='gpPt11' stroke='currentColor' transform='rotate(45)'/> + <use xlink:href='#gpPt11' id='gpPt12' fill='currentColor' stroke='none'/> + <path id='gpPt13' stroke-width='0.222' stroke='currentColor' d='M0,1.330 L1.265,0.411 L0.782,-1.067 L-0.782,-1.076 L-1.265,0.411 z'/> + <use xlink:href='#gpPt13' id='gpPt14' fill='currentColor' stroke='none'/> + <filter id='textbox' filterUnits='objectBoundingBox' x='0' y='0' height='1' width='1'> + <feFlood flood-color='white' flood-opacity='1' result='bgnd'/> + <feComposite in='SourceGraphic' in2='bgnd' operator='atop'/> + </filter> + <filter id='greybox' filterUnits='objectBoundingBox' x='0' y='0' height='1' width='1'> + <feFlood flood-color='lightgrey' flood-opacity='1' result='grey'/> + <feComposite in='SourceGraphic' in2='grey' operator='atop'/> + </filter> +</defs> +<g fill="none" color="white" stroke="black" stroke-width="1.00" stroke-linecap="butt" stroke-linejoin="miter"> +</g> +<g fill="none" color="black" stroke="currentColor" stroke-width="1.00" stroke-linecap="butt" stroke-linejoin="miter"> + <path stroke='black' d='M80.2,422.4 L89.2,422.4 M575.0,422.4 L566.0,422.4 '/> <g transform="translate(71.9,426.3)" stroke="none" fill="black" font-family="Arial" font-size="12.00" text-anchor="end"> + <text><tspan font-family="Arial" > 0</tspan></text> + </g> +</g> +<g fill="none" color="black" stroke="currentColor" stroke-width="1.00" stroke-linecap="butt" stroke-linejoin="miter"> + <path stroke='black' d='M80.2,361.0 L89.2,361.0 M575.0,361.0 L566.0,361.0 '/> <g transform="translate(71.9,364.9)" stroke="none" fill="black" font-family="Arial" font-size="12.00" text-anchor="end"> + <text><tspan font-family="Arial" > 200</tspan></text> + </g> +</g> +<g fill="none" color="black" stroke="currentColor" stroke-width="1.00" stroke-linecap="butt" stroke-linejoin="miter"> + <path stroke='black' d='M80.2,299.6 L89.2,299.6 M575.0,299.6 L566.0,299.6 '/> <g transform="translate(71.9,303.5)" stroke="none" fill="black" font-family="Arial" font-size="12.00" text-anchor="end"> + <text><tspan font-family="Arial" > 400</tspan></text> + </g> +</g> +<g fill="none" color="black" stroke="currentColor" stroke-width="1.00" stroke-linecap="butt" stroke-linejoin="miter"> + <path stroke='black' d='M80.2,238.2 L89.2,238.2 M575.0,238.2 L566.0,238.2 '/> <g transform="translate(71.9,242.1)" stroke="none" fill="black" font-family="Arial" font-size="12.00" text-anchor="end"> + <text><tspan font-family="Arial" > 600</tspan></text> + </g> +</g> +<g fill="none" color="black" stroke="currentColor" stroke-width="1.00" stroke-linecap="butt" stroke-linejoin="miter"> + <path stroke='black' d='M80.2,176.9 L89.2,176.9 M575.0,176.9 L566.0,176.9 '/> <g transform="translate(71.9,180.8)" stroke="none" fill="black" font-family="Arial" font-size="12.00" text-anchor="end"> + <text><tspan font-family="Arial" > 800</tspan></text> + </g> +</g> +<g fill="none" color="black" stroke="currentColor" stroke-width="1.00" stroke-linecap="butt" stroke-linejoin="miter"> + <path stroke='black' d='M80.2,115.5 L89.2,115.5 M575.0,115.5 L566.0,115.5 '/> <g transform="translate(71.9,119.4)" stroke="none" fill="black" font-family="Arial" font-size="12.00" text-anchor="end"> + <text><tspan font-family="Arial" > 1000</tspan></text> + </g> +</g> +<g fill="none" color="black" stroke="currentColor" stroke-width="1.00" stroke-linecap="butt" stroke-linejoin="miter"> + <path stroke='black' d='M80.2,54.1 L89.2,54.1 M575.0,54.1 L566.0,54.1 '/> <g transform="translate(71.9,58.0)" stroke="none" fill="black" font-family="Arial" font-size="12.00" text-anchor="end"> + <text><tspan font-family="Arial" > 1200</tspan></text> + </g> +</g> +<g fill="none" color="black" stroke="currentColor" stroke-width="1.00" stroke-linecap="butt" stroke-linejoin="miter"> + <path stroke='black' d='M80.2,422.4 L80.2,413.4 M80.2,54.1 L80.2,63.1 '/> <g transform="translate(80.2,444.3)" stroke="none" fill="black" font-family="Arial" font-size="12.00" text-anchor="middle"> + <text><tspan font-family="Arial" > 1</tspan></text> + </g> +</g> +<g fill="none" color="black" stroke="currentColor" stroke-width="1.00" stroke-linecap="butt" stroke-linejoin="miter"> + <path stroke='black' d='M179.2,422.4 L179.2,413.4 M179.2,54.1 L179.2,63.1 '/> <g transform="translate(179.2,444.3)" stroke="none" fill="black" font-family="Arial" font-size="12.00" text-anchor="middle"> + <text><tspan font-family="Arial" > 2</tspan></text> + </g> +</g> +<g fill="none" color="black" stroke="currentColor" stroke-width="1.00" stroke-linecap="butt" stroke-linejoin="miter"> + <path stroke='black' d='M278.1,422.4 L278.1,413.4 M278.1,54.1 L278.1,63.1 '/> <g transform="translate(278.1,444.3)" stroke="none" fill="black" font-family="Arial" font-size="12.00" text-anchor="middle"> + <text><tspan font-family="Arial" > 4</tspan></text> + </g> +</g> +<g fill="none" color="black" stroke="currentColor" stroke-width="1.00" stroke-linecap="butt" stroke-linejoin="miter"> + <path stroke='black' d='M377.1,422.4 L377.1,413.4 M377.1,54.1 L377.1,63.1 '/> <g transform="translate(377.1,444.3)" stroke="none" fill="black" font-family="Arial" font-size="12.00" text-anchor="middle"> + <text><tspan font-family="Arial" > 8</tspan></text> + </g> +</g> +<g fill="none" color="black" stroke="currentColor" stroke-width="1.00" stroke-linecap="butt" stroke-linejoin="miter"> + <path stroke='black' d='M476.0,422.4 L476.0,413.4 M476.0,54.1 L476.0,63.1 '/> <g transform="translate(476.0,444.3)" stroke="none" fill="black" font-family="Arial" font-size="12.00" text-anchor="middle"> + <text><tspan font-family="Arial" > 16</tspan></text> + </g> +</g> +<g fill="none" color="black" stroke="currentColor" stroke-width="1.00" stroke-linecap="butt" stroke-linejoin="miter"> + <path stroke='black' d='M575.0,422.4 L575.0,413.4 M575.0,54.1 L575.0,63.1 '/> <g transform="translate(575.0,444.3)" stroke="none" fill="black" font-family="Arial" font-size="12.00" text-anchor="middle"> + <text><tspan font-family="Arial" > 32</tspan></text> + </g> +</g> +<g fill="none" color="black" stroke="currentColor" stroke-width="1.00" stroke-linecap="butt" stroke-linejoin="miter"> +</g> +<g fill="none" color="black" stroke="currentColor" stroke-width="1.00" stroke-linecap="butt" stroke-linejoin="miter"> + <path stroke='black' d='M80.2,54.1 L80.2,422.4 L575.0,422.4 L575.0,54.1 L80.2,54.1 Z '/></g> +<g fill="none" color="black" stroke="currentColor" stroke-width="1.00" stroke-linecap="butt" stroke-linejoin="miter"> + <g transform="translate(16.3,238.3) rotate(270)" stroke="none" fill="black" font-family="Arial" font-size="12.00" text-anchor="middle"> + <text><tspan font-family="Arial" >time(ms)</tspan></text> + </g> +</g> +<g fill="none" color="black" stroke="currentColor" stroke-width="1.00" stroke-linecap="butt" stroke-linejoin="miter"> + <g transform="translate(327.6,471.3)" stroke="none" fill="black" font-family="Arial" font-size="12.00" text-anchor="middle"> + <text><tspan font-family="Arial" >CPUs</tspan></text> + </g> +</g> +<g fill="none" color="black" stroke="currentColor" stroke-width="1.00" stroke-linecap="butt" stroke-linejoin="miter"> + <g transform="translate(327.6,31.0)" stroke="none" fill="black" font-family="Arial" font-size="12.00" text-anchor="middle"> + <text><tspan font-family="Arial" >twice</tspan></text> + </g> +</g> + <g id="gnuplot_plot_1" ><title>"gears_poweredge"</title> +<g fill="none" color="black" stroke="currentColor" stroke-width="1.00" stroke-linecap="butt" stroke-linejoin="miter"> + <g transform="translate(507.9,76.0)" stroke="none" fill="black" font-family="Arial" font-size="12.00" text-anchor="end"> + <text>"gears_poweredge"</text> + </g> +</g> +<g fill="none" color="black" stroke="currentColor" stroke-width="1.00" stroke-linecap="butt" stroke-linejoin="miter"> + <path stroke='rgb( 0, 0, 255)' d='M516.2,72.1 L558.4,72.1 M80.2,59.9 L179.2,229.7 L278.1,322.9 L377.1,373.3 L476.0,396.2 L575.0,406.5 + '/></g> + </g> + <g id="gnuplot_plot_2" ><title>"go_poweredge"</title> +<g fill="none" color="black" stroke="currentColor" stroke-width="1.00" stroke-linecap="butt" stroke-linejoin="miter"> + <g transform="translate(507.9,94.0)" stroke="none" fill="black" font-family="Arial" font-size="12.00" text-anchor="end"> + <text>"go_poweredge"</text> + </g> +</g> +<g fill="none" color="black" stroke="currentColor" stroke-width="1.00" stroke-linecap="butt" stroke-linejoin="miter"> + <path stroke='rgb(255, 0, 0)' d='M516.2,90.1 L558.4,90.1 M80.2,363.9 L179.2,384.5 L278.1,407.0 L377.1,406.4 L476.0,405.9 L575.0,408.9 + '/></g> + </g> + <g id="gnuplot_plot_3" ><title>"openmp_poweredge"</title> +<g fill="none" color="black" stroke="currentColor" stroke-width="1.00" stroke-linecap="butt" stroke-linejoin="miter"> + <g transform="translate(507.9,112.0)" stroke="none" fill="black" font-family="Arial" font-size="12.00" text-anchor="end"> + <text>"openmp_poweredge"</text> + </g> +</g> +<g fill="none" color="black" stroke="currentColor" stroke-width="1.00" stroke-linecap="butt" stroke-linejoin="miter"> + <path stroke='rgb( 0, 255, 0)' d='M516.2,108.1 L558.4,108.1 M80.2,323.4 L179.2,363.1 L278.1,390.7 L377.1,406.2 L476.0,412.5 L575.0,413.3 + '/></g> + </g> +<g fill="none" color="white" stroke="rgb( 0, 255, 0)" stroke-width="2.00" stroke-linecap="butt" stroke-linejoin="miter"> +</g> +<g fill="none" color="black" stroke="currentColor" stroke-width="2.00" stroke-linecap="butt" stroke-linejoin="miter"> +</g> +<g fill="none" color="black" stroke="black" stroke-width="1.00" stroke-linecap="butt" stroke-linejoin="miter"> +</g> +<g fill="none" color="black" stroke="currentColor" stroke-width="1.00" stroke-linecap="butt" stroke-linejoin="miter"> + <path stroke='black' d='M80.2,54.1 L80.2,422.4 L575.0,422.4 L575.0,54.1 L80.2,54.1 Z '/></g> +<g fill="none" color="black" stroke="currentColor" stroke-width="1.00" stroke-linecap="butt" stroke-linejoin="miter"> +</g> +</g> +</svg> +
--- a/slide/slide.html Tue Feb 13 02:23:41 2018 +0900 +++ b/slide/slide.html Tue Feb 13 03:36:25 2018 +0900 @@ -87,7 +87,7 @@ <!-- === begin markdown block === generated by markdown/1.2.0 on Ruby 2.3.0 (2015-12-25) [x86_64-darwin16] - on 2018-02-13 02:23:21 +0900 with Markdown engine kramdown (1.13.2) + on 2018-02-13 03:34:14 +0900 with Markdown engine kramdown (1.13.2) using options {} --> @@ -271,7 +271,7 @@ <!-- _S9SLIDE_ --> <h2 id="stub-code-gear">stub Code Gear</h2> <ul> - <li>Data Gear にアクセスするにはContext を経由する</li> + <li>Data Gear にアクセスするには Context から番号を指定して行う</li> <li>だが、通常の Code Gear では Meta Data Gear である Context の参照は避ける必要がある</li> <li>Gears OS ではメタレベルで通常の Code Gear で必要な Data Gear を Context から取り出す処理を行う stub Code Gear を用意している</li> </ul> @@ -314,6 +314,11 @@ <li>操作(API)自体のCode Gear の型</li> </ul> </li> + <li><strong>__code next(…)</strong> は一種のクロージャであり、 引数で Code Gear を渡すことが出来る + <ul> + <li>… は可変長引数のような扱いで、Code Gear が複数の値をInput Data Gear とする可能性がある</li> + </ul> + </li> </ul> <pre lang="c"><code>typedef struct Queue<Impl>{ @@ -343,7 +348,7 @@ <li>実装した Data Gear の生成は関数呼び出しで行われ、外から見るとInterface の型で扱われる</li> </ul> -<pre><code>Queue* createSingleLinkedQueue(struct Context* context) { +<pre lang="c"><code>Queue* createSingleLinkedQueue(struct Context* context) { struct Queue* queue = new Queue(); // Allocate Queue interface struct SingleLinkedQueue* singleLinkedQueue = new SingleLinkedQueue(); // Allocate Queue implement queue->queue = (union Data*)singleLinkedQueue; @@ -361,39 +366,13 @@ </div> <div class='slide '> <!-- _S9SLIDE_ --> -<h2 id="interface--2">Interface の実装例</h2> -<ul> - <li>SingleLinkedQueue の put 実装</li> - <li>引数は Queue Interface の put 定義にあわせる</li> - <li>第1引数は 実装対象の Data Gear の型になる</li> - <li>第3引数の(…) は Output Data Gear を記述する - <ul> - <li>… は可変長引数のような扱いで、 継続先の Code Gear が複数の値をInput Data Gear とする可能性がある</li> - </ul> - </li> -</ul> - -<pre lang="c"><code>__code putSingleLinkedQueue(struct SingleLinkedQueue* queue, union Data* data, __code next(...)) { - Element* element = new Element(); - element->data = data; - element->next = NULL; - queue->last->next = element; - queue->last = element; - goto next(...); -} -</code></pre> - - -</div> -<div class='slide '> -<!-- _S9SLIDE_ --> <h2 id="interface--code-gear-">Interface を利用した Code Gear の呼び出し</h2> <ul> <li>Interface を利用した Code Gear への継続は <code>goto interface->method</code> で行われる</li> <li>ここでの <strong>interface</strong> は Interfaceの型で包んだData Gear、 <strong>method</strong> は実装した Code Gear に対応する</li> </ul> -<pre><code>__code code1() { +<pre lang="c"><code>__code code1() { Queue* queue = createSingleLinkedQueue(context); Node* node = new Node(); node->color = Red; @@ -417,7 +396,7 @@ <li>呼び出すCode Gear の引数情報に合わせて引数に格納し、 実装された Code Gear へ継続する</li> </ul> -<pre><code>__code code1(struct Context *context) { +<pre lang="c"><code>__code code1(struct Context *context) { Queue* queue = createSingleLinkedQueue(context); Node* node = &ALLOCATE(context, Node)->Node; node->color = Red; @@ -438,7 +417,8 @@ <li>Interface を実装した Code Gear は Interface の定義から stub Code Gear の自動生成が可能である</li> </ul> -<pre lang="c"><code>__code putSingleLinkedQueue(struct Context *context,struct SingleLinkedQueue* queue, union Data* data, enum Code next) { +<pre lang="c"><code>__code putSingleLinkedQueue(struct Context *context,struct SingleLinkedQueue* queue, + union Data* data, enum Code next) { Element* element = &ALLOCATE(context, Element)->Element; element->data = data; element->next = NULL; @@ -474,7 +454,7 @@ <ul> <li>SynchronizedQueue から Task を一つずつ取得し、実行する</li> <li>Worker は CPU、 GPU の対応した数分生成する</li> - <li>Worker 毎に POSIX Therad などのスレッドを生成し、 Code Gear を実行する</li> + <li>Worker 毎に POSIX Therad などを生成し、それぞれのスレッドで Code Gear を実行する</li> </ul> </li> <li>SynchronizedQueue @@ -514,18 +494,12 @@ </ul> <div> - <div style="float: left;"> - <img src="./images/sendTask.svg" alt="message" width="600" /> - </div> - <div style="float: left; font-size=100%;"> + <img src="./images/sendTask.svg" alt="message" style="float: left;width: 50%;" /> + <div style="float: left; width: 50%;"> <ol> - <li value="0">Task を Input Data Gear として</li> - TaskManager の spawn を呼び出す - <li value="1">Task内の idgCountをチェックする</li> - idgCount は待っているInput Data Gear のカウンタである - そのため、カウンタが0の場合 Input Data Gear が揃っていることになる - <li value="2">揃っている場合、 Worker の Queue に</li> - Task を送信する + <li value="0">Task を Input Data Gear としてTaskManager の spawn を呼び出す</li> + <li value="1">Task が待っている Data Gear のカウンタである idgCount をチェックする</li> + <li value="2">idgCount が0の場合 Data Gear が 揃っているので Worker の Queue に Task を送信する</li> </ol> </div> <div style="clear: both;"></div> @@ -542,18 +516,15 @@ </ul> <div> - <div style="float: left;"> - <img src="./images/workerRun.svg" alt="message" width="600" /> - </div> - <div style="float: left; font-size=100%;"> + <img src="./images/workerRun.svg" alt="message" style="float: left;width: 50%;" /> + <div style="float: left; width: 50%;"> <ol> <li>Worker は Queue から Task を取得する</li> - <li>Worker の Context から</li> - Task の Context へ入れ替える + <li>Worker の Context からTask の Context へ入れ替える</li> + <li>Task に設定されている Code Gear を実行</li> <li>Task の Output Data Gear の書き出し</li> - <li>Task Context から</li> - Worker の Context へ入れ替える + <li>Task Context から Worker の Context へ入れ替える</li> <li>Worker は再び Queue から Task を取得する</li> </ol> </div> @@ -621,11 +592,25 @@ <li>この記述を直接書くと Meta Data Gear である Context を直接参照しているため、ノーマルレベルでの記述では好ましくない</li> <li>Task の設定は煩雑な記述であるが、並列実行されることを除けば通常の CbC の goto 文と同等である</li> <li>そこで Context を直接参照しない並列構文、 <strong>par goto</strong> 構文を新たに考案した</li> +</ul> + + +</div> +<div class='slide '> +<!-- _S9SLIDE_ --> +<h2 id="par-goto-">par goto 構文</h2> +<ul> + <li>par goto 構文を記述すると新しく Context を生成し、TaskManager を通して Worker に送信される</li> <li>par goto 構文には引数として Input/Output Data Gear等を渡す <ul> <li>スクリプトによって Code Gear の Input/Output の数を解析する</li> </ul> </li> + <li>Task は <strong>__exit</strong> に継続することで終了する + <ul> + <li>Gears OS は Output Data Gear 生成した時点で終了するため<strong>__exit</strong> に直接継続せずに Data Gear を書き出す処理に継続する</li> + </ul> + </li> </ul> <pre lang="c"><code>__code code1(Integer *integer1, Integer * integer2, Integer *output) { @@ -751,6 +736,9 @@ <ul> <li>Twice は与えられた整数配列を2倍にする例題である</li> <li>並列実行の依存関係がなく、並列度が高い課題である</li> + <li>要素数 2^27</li> + <li>CPU での実行時は 2^27 を 2^6 個に分割して Task を生成する</li> + <li>GPU での実行時は1次元の block 数を 2^15、 block 内の thread 数を 2^10 で展開</li> </ul> @@ -759,9 +747,6 @@ <!-- _S9SLIDE_ --> <h2 id="twice-">Twice の結果</h2> <ul> - <li>要素数 2^27</li> - <li>CPU での実行時は 2^27 を 2^6 個に分割して Task を生成する</li> - <li>GPU での実行時は1次元の block 数を 2^15、 block 内の thread 数を 2^10 で展開</li> <li>1 CPU と 32 CPU では 約27.1倍の速度向上が見られた</li> <li>GPU 実行は kernel のみの実行時間は32 CPU に比べて約7.2倍の速度向上、通信時間を含めると 16 CPU より遅い</li> <li>通信時間がオーバーヘッドになっている</li> @@ -816,6 +801,9 @@ <ul> <li>並列処理向けのソートアルゴリズム</li> <li>決まった2点間の要素の入れ替えをステージ毎に並列に実行し、 Output Data Gear として書き出し、次のステージの Code Gear の Input Data Gear とする</li> + <li>要素数 2^24</li> + <li>CPU での実行時は 2^24 を 2^6 個に分割して Task を生成する</li> + <li>GPU での実行時は1次元の block 数を 2^14、 block 内の thread 数を 2^10 で展開</li> </ul> @@ -824,9 +812,6 @@ <!-- _S9SLIDE_ --> <h2 id="bitonicsort-">BitonicSort の結果</h2> <ul> - <li>要素数 2^24</li> - <li>CPU での実行時は 2^24 を 2^6 個に分割して Task を生成する</li> - <li>GPU での実行時は1次元の block 数を 2^14、 block 内の thread 数を 2^10 で展開</li> <li>1 CPU と 32 CPU で約22.12倍の速度向上</li> <li>GPU は通信時間を含めると 8 CPU の約1.16倍、 kernel のみの実行では 32 CPU の約11.48倍になった</li> <li>現在の Gears OS の CUDA 実装では Output Data Gear を書き出す際に一度 GPU から CPU へ kernel の結果の書き出しを行っているため、差がでてしまった</li> @@ -922,37 +907,6 @@ </div> <div class='slide '> <!-- _S9SLIDE_ --> -<h2 id="openmp--1">OpenMP との比較</h2> -<ul> - <li>OpenMP で Twice を実装し、速度比較を行った</li> - <li>OpenMP は 1CPU と 32CPU で約10.8倍の速度向上が見られた</li> - <li>一方 Gears OS では約27.1倍と台数効果は高くなっている</li> - <li>しかし、 Gears OS は 1CPU の実行速度が OpenMP に比べて大幅に遅くなっている</li> -</ul> - -<div style="text-align: center;"> - <img src="./images/vsopenmp.svg" alt="message" width="500" /> -</div> - - -</div> -<div class='slide '> -<!-- _S9SLIDE_ --> -<h2 id="go--1">Go 言語との比較</h2> -<ul> - <li>Go 言語でも OpenMP と同様に Twice を実装し、速度比較を行った</li> - <li>Go 言語は 1CPU と 32CPU で約4.33倍の速度向上が見られた</li> - <li>OpenMP と同様に台数効果自体は Gears OS が高いが、 1CPU での実行時間は Go 言語が大幅に速い</li> -</ul> - -<div style="text-align: center;"> - <img src="./images/vsgo.svg" alt="message" width="500" /> -</div> - - -</div> -<div class='slide '> -<!-- _S9SLIDE_ --> <h2 id="section-5">まとめ</h2> <ul> <li>Gears OS の並列処理機構の実装を行った</li> @@ -968,24 +922,74 @@ <h2 id="section-6">今後の課題</h2> <ul> <li>Gears OS の並列処理の信頼性の保証、チューニングを行う</li> +</ul> + + +</div> +<div class='slide '> +<!-- _S9SLIDE_ --> +<h2 id="section-7">今後の課題</h2> +<ul> <li>Gears OS では検証とモデル検査をメタレベルで実現することで信頼性を保証する <ul> <li>証明は CbC のプログラムを証明支援系の Agda に対応して行う。 並列処理の信頼性を保証するには SynchronizedQueue の証明を行う必要がある</li> <li>モデル検査は CbC で記述された モデル検査器である akasha を使用して行う。 モデル検査の方針としては Code Gear の並列実行を擬似並列で実行し、全ての組合せを列挙する方法で行う</li> </ul> </li> +</ul> + + +</div> +<div class='slide '> +<!-- _S9SLIDE_ --> +<h2 id="section-8">今後の課題</h2> +<ul> <li>現在の CUDA 実装では CPU、GPU 間のデータの通信コストがかかってしまうことが例題からわかった <ul> <li>Meta Data Gear に Data Gear が CPU、 GPU のどこで所持されているのかを持たせ、 GPU の Data Gear が CPU で必要になったときに始めてデータの通信を行う</li> </ul> </li> - <li>OpenMP、 Goとの比較から、 Gears OS が 1CPU での動作が遅いということがわかった。 +</ul> + + +</div> +<div class='slide '> +<!-- _S9SLIDE_ --> +<h2 id="section-9">今後の課題</h2> +<ul> + <li>OpenMP、 Go で Twice を実装し、 Gears OS の性能比較を行った</li> + <li>その結果、 Gears OS が 1CPU での動作が遅いということがわかった。 <ul> <li>par goto 文を使用する度に Context を生成するため、 ある程度の時間がかかってしまう</li> <li>モデル検査で par goto の Code Gear のフローを解析し、処理がかる場合は Context を生成せずに関数呼出しを行う等の最適化が必要</li> </ul> </li> </ul> + +<div style="text-align: center;"> + <img src="./images/compareExamples.svg" alt="message" width="600" /> +</div> + +<!-- +## OpenMP との比較 +- OpenMP で Twice を実装し、速度比較を行った +- OpenMP は 1CPU と 32CPU で約10.8倍の速度向上が見られた +- 一方 Gears OS では約27.1倍と台数効果は高くなっている +- しかし、 Gears OS は 1CPU の実行速度が OpenMP に比べて大幅に遅くなっている + +<div style="text-align: center;"> + <img src="./images/vsopenmp.svg" alt="message" width="500"> +</div> + +## Go 言語との比較 +- Go 言語でも OpenMP と同様に Twice を実装し、速度比較を行った +- Go 言語は 1CPU と 32CPU で約4.33倍の速度向上が見られた +- OpenMP と同様に台数効果自体は Gears OS が高いが、 1CPU での実行時間は Go 言語が大幅に速い + +<div style="text-align: center;"> + <img src="./images/vsgo.svg" alt="message" width="500"> +</div> +--> <!-- === end markdown block === --> </div>
--- a/slide/slide.md Tue Feb 13 02:23:41 2018 +0900 +++ b/slide/slide.md Tue Feb 13 03:36:25 2018 +0900 @@ -103,7 +103,7 @@ - Gears OS ではメタ計算で Context を経由して Code/Data Gear にアクセスする ## stub Code Gear -- Data Gear にアクセスするにはContext を経由する +- Data Gear にアクセスするには Context から番号を指定して行う - だが、通常の Code Gear では Meta Data Gear である Context の参照は避ける必要がある - Gears OS ではメタレベルで通常の Code Gear で必要な Data Gear を Context から取り出す処理を行う stub Code Gear を用意している @@ -126,6 +126,8 @@ - Interface の定義には以下の内容を定義する - 操作(API)の引数群の型 - 操作(API)自体のCode Gear の型 +- **__code next(...)** は一種のクロージャであり、 引数で Code Gear を渡すことが出来る + - ... は可変長引数のような扱いで、Code Gear が複数の値をInput Data Gear とする可能性がある ``` c typedef struct Queue<Impl>{ @@ -149,7 +151,7 @@ - 代入する Code Gear を入れ替えることで別の実装を表現する - 実装した Data Gear の生成は関数呼び出しで行われ、外から見るとInterface の型で扱われる -``` +``` c Queue* createSingleLinkedQueue(struct Context* context) { struct Queue* queue = new Queue(); // Allocate Queue interface struct SingleLinkedQueue* singleLinkedQueue = new SingleLinkedQueue(); // Allocate Queue implement @@ -164,29 +166,11 @@ } ``` -## Interface の実装例 -- SingleLinkedQueue の put 実装 -- 引数は Queue Interface の put 定義にあわせる -- 第1引数は 実装対象の Data Gear の型になる -- 第3引数の(...) は Output Data Gear を記述する - - ... は可変長引数のような扱いで、 継続先の Code Gear が複数の値をInput Data Gear とする可能性がある - -``` c -__code putSingleLinkedQueue(struct SingleLinkedQueue* queue, union Data* data, __code next(...)) { - Element* element = new Element(); - element->data = data; - element->next = NULL; - queue->last->next = element; - queue->last = element; - goto next(...); -} -``` - ## Interface を利用した Code Gear の呼び出し - Interface を利用した Code Gear への継続は `goto interface->method` で行われる - ここでの **interface** は Interfaceの型で包んだData Gear、 **method** は実装した Code Gear に対応する -``` +``` c __code code1() { Queue* queue = createSingleLinkedQueue(context); Node* node = new Node(); @@ -202,7 +186,7 @@ - この Data Gear は Context を初期化した際に特別に生成され、型は Interface と同じになる - 呼び出すCode Gear の引数情報に合わせて引数に格納し、 実装された Code Gear へ継続する -``` +``` c __code code1(struct Context *context) { Queue* queue = createSingleLinkedQueue(context); Node* node = &ALLOCATE(context, Node)->Node; @@ -219,7 +203,8 @@ - Interface を実装した Code Gear は Interface の定義から stub Code Gear の自動生成が可能である ``` c -__code putSingleLinkedQueue(struct Context *context,struct SingleLinkedQueue* queue, union Data* data, enum Code next) { +__code putSingleLinkedQueue(struct Context *context,struct SingleLinkedQueue* queue, + union Data* data, enum Code next) { Element* element = &ALLOCATE(context, Element)->Element; element->data = data; element->next = NULL; @@ -245,7 +230,7 @@ - Worker - SynchronizedQueue から Task を一つずつ取得し、実行する - Worker は CPU、 GPU の対応した数分生成する - - Worker 毎に POSIX Therad などのスレッドを生成し、 Code Gear を実行する + - Worker 毎に POSIX Therad などを生成し、それぞれのスレッドで Code Gear を実行する - SynchronizedQueue - マルチスレッド 環境でもデータの一貫性を保証する Queue - をInterface で実装した @@ -262,18 +247,12 @@ - 依存関係を解決した Task を各 Worker の Queue に送信する <div> - <div style="float: left;"> - <img src="./images/sendTask.svg" alt="message" width="600"> - </div> - <div style="float: left; font-size=100%;"> + <img src="./images/sendTask.svg" alt="message" style="float: left;width: 50%;"> + <div style="float: left; width: 50%;"> <ol> - <li value="0">Task を Input Data Gear として</li> - TaskManager の spawn を呼び出す - <li value="1">Task内の idgCountをチェックする</li> - idgCount は待っているInput Data Gear のカウンタである - そのため、カウンタが0の場合 Input Data Gear が揃っていることになる - <li value="2">揃っている場合、 Worker の Queue に</li> - Task を送信する + <li value="0">Task を Input Data Gear としてTaskManager の spawn を呼び出す</li> + <li value="1">Task が待っている Data Gear のカウンタである idgCount をチェックする</li> + <li value="2">idgCount が0の場合 Data Gear が 揃っているので Worker の Queue に Task を送信する</li> </ol> </div> <div style="clear: both;"></div> @@ -284,18 +263,15 @@ - TaskManager から送信された Task を一つずつ取得して実行する <div> - <div style="float: left;"> - <img src="./images/workerRun.svg" alt="message" width="600"> - </div> - <div style="float: left; font-size=100%;"> + <img src="./images/workerRun.svg" alt="message" style="float: left;width: 50%;"> + <div style="float: left; width: 50%;"> <ol> <li>Worker は Queue から Task を取得する</li> - <li>Worker の Context から</li> - Task の Context へ入れ替える + <li>Worker の Context からTask の Context へ入れ替える</li> + <li>Task に設定されている Code Gear を実行</li> <li>Task の Output Data Gear の書き出し</li> - <li>Task Context から</li> - Worker の Context へ入れ替える + <li>Task Context から Worker の Context へ入れ替える</li> <li>Worker は再び Queue から Task を取得する</li> </ol> </div> @@ -341,8 +317,13 @@ - この記述を直接書くと Meta Data Gear である Context を直接参照しているため、ノーマルレベルでの記述では好ましくない - Task の設定は煩雑な記述であるが、並列実行されることを除けば通常の CbC の goto 文と同等である - そこで Context を直接参照しない並列構文、 **par goto** 構文を新たに考案した + +## par goto 構文 +- par goto 構文を記述すると新しく Context を生成し、TaskManager を通して Worker に送信される - par goto 構文には引数として Input/Output Data Gear等を渡す - スクリプトによって Code Gear の Input/Output の数を解析する +- Task は **__exit** に継続することで終了する + - Gears OS は Output Data Gear 生成した時点で終了するため**__exit** に直接継続せずに Data Gear を書き出す処理に継続する ``` c __code code1(Integer *integer1, Integer * integer2, Integer *output) { @@ -413,11 +394,11 @@ ## Twice - Twice は与えられた整数配列を2倍にする例題である - 並列実行の依存関係がなく、並列度が高い課題である - -## Twice の結果 - 要素数 2^27 - CPU での実行時は 2^27 を 2^6 個に分割して Task を生成する - GPU での実行時は1次元の block 数を 2^15、 block 内の thread 数を 2^10 で展開 + +## Twice の結果 - 1 CPU と 32 CPU では 約27.1倍の速度向上が見られた - GPU 実行は kernel のみの実行時間は32 CPU に比べて約7.2倍の速度向上、通信時間を含めると 16 CPU より遅い - 通信時間がオーバーヘッドになっている @@ -466,11 +447,11 @@ ## BitonicSort - 並列処理向けのソートアルゴリズム - 決まった2点間の要素の入れ替えをステージ毎に並列に実行し、 Output Data Gear として書き出し、次のステージの Code Gear の Input Data Gear とする - -## BitonicSort の結果 - 要素数 2^24 - CPU での実行時は 2^24 を 2^6 個に分割して Task を生成する - GPU での実行時は1次元の block 数を 2^14、 block 内の thread 数を 2^10 で展開 + +## BitonicSort の結果 - 1 CPU と 32 CPU で約22.12倍の速度向上 - GPU は通信時間を含めると 8 CPU の約1.16倍、 kernel のみの実行では 32 CPU の約11.48倍になった - 現在の Gears OS の CUDA 実装では Output Data Gear を書き出す際に一度 GPU から CPU へ kernel の結果の書き出しを行っているため、差がでてしまった @@ -552,6 +533,35 @@ } ``` +## まとめ +- Gears OS の並列処理機構の実装を行った +- Interface を導入することで、見通しの良し Gears OS のプログラミングが可能となった +- par goto 構文を導入することで、ノーマルレベルで並列処理の記述が可能になった +- 2つの例題である程度の台数効果が出ることを確認した + +## 今後の課題 +- Gears OS の並列処理の信頼性の保証、チューニングを行う + +## 今後の課題 +- Gears OS では検証とモデル検査をメタレベルで実現することで信頼性を保証する + - 証明は CbC のプログラムを証明支援系の Agda に対応して行う。 並列処理の信頼性を保証するには SynchronizedQueue の証明を行う必要がある + - モデル検査は CbC で記述された モデル検査器である akasha を使用して行う。 モデル検査の方針としては Code Gear の並列実行を擬似並列で実行し、全ての組合せを列挙する方法で行う + +## 今後の課題 +- 現在の CUDA 実装では CPU、GPU 間のデータの通信コストがかかってしまうことが例題からわかった + - Meta Data Gear に Data Gear が CPU、 GPU のどこで所持されているのかを持たせ、 GPU の Data Gear が CPU で必要になったときに始めてデータの通信を行う + +## 今後の課題 +- OpenMP、 Go で Twice を実装し、 Gears OS の性能比較を行った +- その結果、 Gears OS が 1CPU での動作が遅いということがわかった。 + - par goto 文を使用する度に Context を生成するため、 ある程度の時間がかかってしまう + - モデル検査で par goto の Code Gear のフローを解析し、処理がかる場合は Context を生成せずに関数呼出しを行う等の最適化が必要 + +<div style="text-align: center;"> + <img src="./images/compareExamples.svg" alt="message" width="600"> +</div> + +<!-- ## OpenMP との比較 - OpenMP で Twice を実装し、速度比較を行った - OpenMP は 1CPU と 32CPU で約10.8倍の速度向上が見られた @@ -570,20 +580,4 @@ <div style="text-align: center;"> <img src="./images/vsgo.svg" alt="message" width="500"> </div> - -## まとめ -- Gears OS の並列処理機構の実装を行った -- Interface を導入することで、見通しの良し Gears OS のプログラミングが可能となった -- par goto 構文を導入することで、ノーマルレベルで並列処理の記述が可能になった -- 2つの例題である程度の台数効果が出ることを確認した - -## 今後の課題 -- Gears OS の並列処理の信頼性の保証、チューニングを行う -- Gears OS では検証とモデル検査をメタレベルで実現することで信頼性を保証する - - 証明は CbC のプログラムを証明支援系の Agda に対応して行う。 並列処理の信頼性を保証するには SynchronizedQueue の証明を行う必要がある - - モデル検査は CbC で記述された モデル検査器である akasha を使用して行う。 モデル検査の方針としては Code Gear の並列実行を擬似並列で実行し、全ての組合せを列挙する方法で行う -- 現在の CUDA 実装では CPU、GPU 間のデータの通信コストがかかってしまうことが例題からわかった - - Meta Data Gear に Data Gear が CPU、 GPU のどこで所持されているのかを持たせ、 GPU の Data Gear が CPU で必要になったときに始めてデータの通信を行う -- OpenMP、 Goとの比較から、 Gears OS が 1CPU での動作が遅いということがわかった。 - - par goto 文を使用する度に Context を生成するため、 ある程度の時間がかかってしまう - - モデル検査で par goto の Code Gear のフローを解析し、処理がかる場合は Context を生成せずに関数呼出しを行う等の最適化が必要 +-->