Mercurial > hg > Papers > 2014 > masakoha-sigos

--- a/slide/final.html	Mon May 05 23:09:26 2014 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,384 +0,0 @@
-<!DOCTYPE html>
-
-<html>
-<head>
-    <title>Presentation</title>
-    <meta charset='utf-8'>
-    <script src='./slides.js'></script>
-</head>
-
-<style>
-/* Your individual styles here, or just use inline styles if that’s
-   what you want. */
-
-</style>
-
-<body style='display: none'>
-<section class='slides layout-regular template-default'>
-
-<!--
-Your slides (<article>s) go here. Delete or comment out the
-slides below.
--->
-<article>
-    <h1>Cerium による並列処理向け I/O の設計と実装</h1>
-    <h3 class="title">Masataka Kohagura 27th, February</h3>
-    <div align="right">担当教官 : 河野 真治</div>
-</article>
-
-<article>
-    <h3>I/Oを含むアプリケーションの並列化</h3>
-    I/O を含む Task は ディスクかの読み込む時間がかかる。<br>
-    -> <font color = red>I/O をどうにか速くできないか?</font>
-    <p>
-    Cerium : <br>
-    CellおよびLinux、 Mac OS X 上で動く並列プログラミングフレームワーク
-    </p>
-    <img src='images/resources.png' style="height:170px" align="middle">
-    <ul>
-    <li><font color=red>ファイル読み込みとアプリケーションの分離</font> </li>
-    <li><font color=red>I/O専用の Threadを追加</font></li>
-    </ul>
-    mmap 実装と比較して1.5倍の速度を得た
-</article>
-
-
-<article>
-    <h3>Cerium Task Manager の構造</h3>
-    <table  border="0" cellpadding="0" cellspacing="0">
-        <tbody>
-            <tr>
-            <td><img src='images/ceriumtaskmanager.png' style="height:280px"></td>
-            <td>
-                <ol>
-                    <li>Taskを生成</li>
-                    <li>依存関係のチェック</li>
-                    <li>Schedulerに転送</li>
-                    <li>並列実行</li>
-                </ol>
-            </td>
-            </tr>
-        </tbody>
-    </table>
-    <p>
-    ファイルを読みながら、Word Count や grep などを<br>
-    並列実行したい
-    </p>
-    <p>
-    計算よりも読み込みを優先しなければならない。読み込みで待ちが入ってしまうので、IO Thread を追加
-    </p>
-</article>
-
-<article>
-    <h3>Block 単位の読み込みと並列計算</h3>
-    <br>
-    <img src='images/includeIOTask.png' style="height:270px" align="middle">
-    <ol>
-        <li>ファイルをある一定の大きさで読み込む</li>
-        <li>読み込んだテキストファイルに対して、それぞれ計算を行う</li>
-        <li>計算した結果を集計する</li>
-    </ol>
-    </article>
-
-<article>
-    <h3>mmap の特徴</h3>
-    従来では mmap を使って読み込んでいた
-    <table  border="0" cellpadding="0" cellspacing="0">
-        <tbody>
-            <tr>
-                <td><img src='images/mmap.png' style="height:350px" align="middle"></td>
-                <td>
-                    <ul>
-                        <font size = 5>
-                            <li>
-                            mmap は、ファイルを直接メモリ空間に map する。<br>
-                            アクセスされたメモリ部分を OS が自動的に読み込む。<br>
-                            </li>
-                            <li>
-                            code がシンプルだが、読み込み終わるまで待たされる。 <br>
-                            </li>
-                        </font>
-                    </ul>
-                </td>
-            </tr>
-        </tbody>
-    </table>
-</article>
-
-
-<article>
-    <h3>読み込みながら計算を行う</h3>
-    <br>
-    <img src='images/divide_read.png' style="height:250px" align="middle" >
-    <br>
-
-    <ul>
-        <li> Read は 連続で動作しファイルを読み込む </li>
-        <li> Read の待ちは CPU を消費しない </li>
-        <li> 読み込み終わったブロックに対して、<br>並列 Task を起動する </li>
-    </ul>
-</article>
-
-<article>
-    <h3>Blocked Read の実装</h3>
-    <br>
-    <img src='images/blockread.png' style="height:250px"align="middle">
-    <br>
-
-    <ul>
-        <li>
-        Task を一度に生成するとメモリを圧迫する。<br>
-        Block 単位で徐々に起動していく。
-        </li>
-        <li>
-        Blocked Read Task が読み込み終わるまで、<br>Task Blockを待たせる
-        </li>
-        <li>
-        待ち合わせには Cerium の wait for を使用する。
-        </li>
-    </ul>
-</article>
-
-<!--
-<article class = 'smaller'>
-<h3>I/O 専用の therad を追加 (1/2)</h3>
-<br>
-<img src='images/SPE_ANYblockread.png' style="height:350px"align="middle">
-<ul>
-<li>
-Task 単位で使用するデバイスをセットすることができる。
-</li>
-<li>
-SPE_ANY でセットすると、Cerium Task Manager 側で自動的に CPU を割り振る。
-</li>
-<li>
-自動的に割り振るので、Blocked Read に 他のTask が割り込むおそれがある。
-</li>
-</ul>
-</article>
--->
-
-
-<article>
-    <h3>I/O 専用 thread での Blocked Read の実装</h3>
-    <br>
-    <img src='images/IO_0blockread.png' style="height:350px">
-    <ul>
-        <li>priority が最優先されるので、Blocked Read Task に割り込みが行われなくなる<br>
-        <li>pthread_setschedparam にて実装<br>
-        </li>
-    </ul>
-</article>
-
-<article>
-    <h3>I/O 専用の thread を使用しない場合</h3>
-    <br>
-    <img src='images/SPE_ANYblockread.png' style="height:350px">
-    <ul>
-        <li>Blocked Read は連続で行われなければならない。<br>しかし、Task が割り振られてしまう可能性がある。 </li>
-    </ul>
-</article>
-
-<article>
-<h3>実験環境</h3>
-<br>
-<ul>
-    <li> Mac OS X 10.9.1</li>
-    <li> 2*2.66 GHz 6-Core Intel Xeon</li>
-    <li> Memory 16GB 1333MHz DDR3</li>
-    <li> HHD 1TB</li>
-    <li> file size : 約 10 GB</li>
-    <li> ファイルに対して Boyer-Moore String Seaech で文字列検索をかける </li>
-    <li> ファイルの読み込みから結果までを測定</li>
-</ul>
-</article>
-
-<article>
-<h3>実験結果</h3>
-<table  border="2" cellpadding="0" cellspacing="0">
-    <tbody>
-        <tr>
-            <td>read mode</td>
-            <td>CPU num</td>
-            <td>ave time(s)</td>
-        </tr>
-        <tr>
-            <td>mmap</td>
-            <td>2</td>
-            <td>106.2</td>
-        </tr>
-        <tr>
-            <td bgcolor="#ffffcc">mmap</td>
-            <td bgcolor="#ffffcc">12</td>
-            <td bgcolor="#ffffcc">154.6</td>
-        </tr>
-        <tr>
-            <td>一括Read</td>
-            <td>12</td>
-            <td>114.9</td>
-        </tr>
-        <tr>
-            <td>Blocked Read(SPE_ANY)</td>
-            <td>12</td>
-            <td>106.0</td>
-        </tr>
-        <tr>
-            <td bgcolor="#ffffcc">Blocked Read(IO_0)</td>
-            <td bgcolor="#ffffcc">(IO) 1 + (Task) 11</td>
-            <td bgcolor="#ffffcc">99.2</td>
-        </tr>
-    </tbody>
-</table>
-
-    <ul>
-        <li> Blocked Read & IO_0 が mmap より<font color=red>1.55倍</font>速度が向上<br> </li>
-        <li> Blocked Read を IO 専用 thread で実装すると、<font color=red>6%</font>改善<br> </li>
-        <!--
-        <li> mmap では 1つ1つの Task がファイルの読み込みを行ってしまうため、読み込み回数が多くなり実行速度が遅くなったと考えられる。 </li>
-
-        -->
-        <li> mmap で並列の Task で走らせると 1つ1つの Task がファイルを読み込み、ランダムアクセスとなって<br>しまうため速度が遅くなってしまう。</li>
-    </ul>
-</article>
-
-<article>
-    <h3>まとめ</h3>
-    <ul>
-        <li> I/O と Task を分離し、同時に動くように改良した。 </li>
-        <li> I/O 専用の Thread の追加 </li>
-        <li>
-        I/O を含む Task をで並列実装するときに mmap では不向きであり、
-        Blocked Read で読み込みを制御したほうが効果的。
-        </li>
-    </ul>
-    <h3 class="yellow">今後の課題</h3>
-    <ul>
-        <li> Cerium の API として実装 </li>
-        <li>
-        様々な実装の試み<br>(I/O threads を 2つ、分割 mmap・・・)
-        </li>
-        <li>
-        grepの実装
-        </li>
-    </ul>
-</article>
-
-<article>
-    <h3>Cerium Task の生成の例(1)</h3>
-    <p>(例題) multiply : 2つの数を掛け算するプログラム</p>
-    <h3 class="yellow">main.cc の記述</h3>
-<pre>
-float* A, B, C;
-// Task の宣言
-HTaskPtr multiply = manager->create_task(MULTIPLY_TASK);
-// Task を実行する デバイスの設定
-multiply->set_cpu(SPE_ANY);
-// Task に入力データのアドレスを追加
-multiply->set_inData(0, (memaddr)A, sizeof(float)*length);
-multiply->set_inData(1, (memaddr)B, sizeof(float)*length);
-// Task に出力データのアドレスを追加
-multiply->set_outData(0, (memaddr)C, sizeof(float)*length);
-// Task へ値を1つだけ渡す
-multiply->set_param(0,length);
-// Task を TaskList に set する
-multiply->spawn();
-</pre>
-</article>
-
-<article>
-    <h3> Cerium Task の生成(2)</h3>
-    <br>
-    <h3 class="yellow">Task の記述</h3>
-<pre>
-static int
-multiply(SchedTask *s,void *rbuf, void *wbuf)
-{
-    float *A,*B,*C
-        // 登録した inData を取得
-        A = (float*)s->get_input(rbuf,0);
-    B = (float*)s->get_input(rbuf,1);
-    // 登録した outData を取得
-    C = (float*)s->get_output(wbuf,0);
-    // 登録した param を取得
-    long  length=(long)s->get_param(0);
-    for (int i=0;i &lt; length;i++) {
-        C[i] = A[i] * B[i];
-    }
-    return 0;
-}
-</pre>
-</article>
-
-<article>
-    <h3>mmap での I/O の実装</h3>
-    <br>
-    <h3 class="yellow">mmap の記述</h3>
-    <pre>
-mmap(SchedTask *s, void *in, void *out)
-{
-    // FileReadPtr : File情報などを格納している構造体
-    FileReadPtr fr = (FileReadPtr)in;
-    int map = MAP_PRIVATE;
-
-    fr->read_text =
-        (char*)mmap(NULL,fr->filesize,PROT_READ,map,fr->fd,(off_t)0);
-}
-    </pre>
-
-    <ul>
-        <li> PROT_READ : 読み込み可 </li>
-        <li> MAP_PRIVATE : 読み込んだ領域に対して書き込みが起こると複製し、複製した領域に対して書き込みを行う </li>
-    </ul>
-</article>
-
-<article class='smaller'>
-    <h3>Block Read の実装(1/2)</h3>
-    <br>
-    <h3 class="yellow">Block Read の実装</h3>
-    <pre>
-HTaskPtr t_read = manager->create_task(READ_TASK);
-t_read->set_cpu(read_spe_cpu);
-// 読み出すファイルの格納場所を設定
-t_read->set_outData(0,
-        w->file_mmap + w->task_spawned * w->division_size,
-        w->task_blocks * w->division_size);
-// ファイルディスクリプタの受け渡し
-t_read->set_param(0,w->fd);
-// ファイル読み込みの始点
-t_read->set_param(1,w->task_spawned*w->division_size);
-
-// run_tasks(manager,w, w->task_blocks, t_read, t_next, w->division_size + w->extra_len);
-// ここで、ファイルに対して何らかの計算を掛けるような Task を設定する
-run_tasks(manager,w, w->task_blocks,・・・ );
-
-// ファイル読み込みの終点
-t_read->set_param(2,w->task_spawned*w->division_size + w->extra_len);
-
-t_read->spawn();
-
-    </pre>
-</article>
-
-<article>
-    <h3>Block Read の実装(2/2)</h3>
-    <br>
-    <h3 class="yellow"> Block Read の記述</h3>
-    <pre>
-    static int
-read_task(SchedTask *s, void *rbuf, void *wbuf)
-{
-    long fd = (long)s->get_param(0);
-    long start_read_position = (long)s->get_param(1);
-    long end_read_position = (long)s->get_param(2);
-    char *read_text = (char*)s->get_output(wbuf,0);
-    long read_size = end_read_position - start_read_position;
-
-    pread(fd, read_text, read_size , start_read_position);
-    return 0;
-}
-    </pre>
-</article>
-
-
-</body>
-</html>