Mercurial > hg > Members > yuuhi > slide

--- a/s6/blank.html	Mon Oct 20 02:12:02 2014 +0900
+++ b/s6/blank.html	Tue Oct 21 15:52:21 2014 +0900
@@ -1,4 +1,4 @@
-\<!DOCTYPE html>
+<!DOCTYPE html>
 <html>
   <head>
     <meta charset='utf-8'>
@@ -88,7 +88,7 @@
         <table width="90%" height="90%" border="0" align="center">
           <tr>
             <td><div align="center">
-                <h1><font color="#808db5">Ceriumの再設計</font></h1>
+                <h1><font color="#808db5">CeriumにおけるGPGPUの最適化</font></h1>
             </div></td>
           </tr>
           <tr>
@@ -114,137 +114,220 @@

       <div class='slide'>
         <h2>研究目的</h2>
+        <p>
+          当研究室ではCellおよびLinux、
+          Mac OSX上で動く並列プログラミングフレームワーク、
+          Ceriumの開発・改良を行っている。
+        </p>
+        <p>本研究では新たにGPU上での並列実行に対応し、
+          ヘテロジニアス(異種混合)環境下でのプログラミングをサポートする
+        </p>
+        <p>
+          GPGPUでは通常のマルチコア<font color="red">CPUとは異なる並列プログラミング</font>
+          と<font color="red">特別なチューニング</font>が必要となる。
+          そこでCeriumを用いてその差を吸収し、自動的なチューニングを可能にする。
+        </p>
+        <p>
+          しかし、GPUのみで並列計算を行った場合、Taskによっては並列度が出ない場合がある。
+          そこでチューニングの一環として、MultiCoreとGPU上での同時実行を可能にする。
+        </p>
+      </div>
+
+      <!-- h1.hidden => use heading just for table of contents (toc) -->
+      <div class='slide'>
+        <h2>進捗</h2>
+        <dl>
+          <dt>Scalaで遊んでた</dt>
+          <dt>mallocのお勉強</dt>
+          <dd>kernel reading party(小崎さん)</dd>
+          <dd><a href="http://shelby.tv/video/youtube/0-vWT-t0UHg/the-67th-yokohama-kernel-reading-party">動画</a></dd>
+          <dd><a href="http://www.slideshare.net/kosaki55tea/glibc-malloc">資料</a></dd>
+      </div>
+
+      <div class='slide'>
+        <h2>mallocってなんだっけ……？</h2>
+        <pre class="code">
+          void *malloc(size_t size);</pre>
+        <img src="images/malloc.png" width="500">
         <ul>
-          <li>当研究室ではCS/DSを使用したプログラミングを行っている</li>
-          <dd>CS/DSについて</dd>
-          <li>CS/DSベースのフレームワーク(?)の開発</li>
-          <dd>もっと大きい何かなのでは……？</dd>
-          <li>独自のMemory Managementの機構を持つ</li>
-          <li>Cerium・Alice・jungleで得られた知見を……</li>
-          <li>なぜ新しく設計し直す必要がある？</li>
-          <li>名前も考える必要がある？</li>
+          <li>mallocはsizeバイト分のメモリを割り当て、ポインタを返す</li>
+          <li>返ってくるのはvoidのポインタなので、戻り値を型でキャストする必要がある</li>
+          <li>中身は初期化されていない</li>
+          <li>確保した領域はfreeを忘れずに</li>
         </ul>
+        <pre class="code">
+          char *str = (char*)malloc(length); // 使う型でキャストする</pre>
       </div>

       <div class='slide'>
-        <h2>Code/Data Segment Systemの構造</h2>
-        <img src="images/new_cerium.png" width="800">
-        <p>全てはDSとして扱われる。CSもDSの一種。</p>
-        <p>TaskもDSで、CSとDSの組になっている。</p>
+        <h2>古典的malloc(K&R malloc)</h2>
+        <img src="images/heap.png" width="700">
+        <ul>
+          <li>使用可能なブロックを繋げたリスト構造、free list (freeされているブロックのlist?)
+          <li>listを使ってメモリを管理
+          <li>管理領域(header)分だけ多くallocateして、先頭に管理領域を付加
+          <li>first fit
+        </ul>
+        <hr>
+        <pre class="code">
+          union header {
+              struct {
+                  union header *ptr;  // 空きリストの上なら次のブロック
+                  unsigned size;      // このブロックの大きさ
+              } s;
+          };</pre>
+      </div>
+
+      <div class='slide'>
+        <h2>First Fit</h2>
+        <p>
+          リストを頭から見ていって、最初に見つけたものを使用するというすごいシンプルな方法。
+        </p>
+        <img src="images/firstfit.png" width="500">
       </div>

       <div class='slide'>
-        <h2>Temporary/Persistent Space</h2>
-        <table>
+        <h2>First Fit</h2>
+        <img src="images/firstfit2.png" width="500">
+        <p>実は、もう一個先にもっと適切なブロックがあった。こんな場合に対応できない…というか、対応しないのがfirst fit。</p>
+        <p>あまりよくない……</p>
+      </div>
+
+      <div class='slide'>
+        <h2>free</h2>
+        <pre class="code">
+          void free(void *ptr);</pre>
+        <p>
+          メモリの開放自体は、使用中のブロックをfree listに追加するだけで良い。
+          引数で受け取ったポインタ部分を開放したら良い……かに思える。
+          でもそれだけじゃダメで、開放したい領域と隣接しているブロックが空きブロックなら併合しないといけない。
+        </p>
+        <img src="images/free_merge.png" width="700">
+      </div>
+
+      <div class='slide'>
+        <h2>free</h2>
+        <img src="images/free1.png" width="700">
+        <p>
+          listから最初のポインタと、その次のポインタを取得。prev < p < nextを満たすまで走査していく
+                                                                       </p>
+      </div>
+
+      <div class='slide'>
+        <h2>free</h2>
+        <img src="images/free2.png" width="700">
+        <p>あった！！</p>
+        <p>
+          開放後に前後のメモリと併合する必要がある場合があるので、prevとp・pとnextが隣接してるか判定する。
+        </p>
+        <ul>
+          <li>(prev+prev-&gt size) != p なので、隣接していない </li>
+          <li>(p+p-&gt size)        = next    なので、隣接している</li>
+          <p>ブロックが隣接している場合は併合する。</p>
+      </div>
+
+      <div class='slide'>
+        <h2>free</h2>
+        <img src="images/free_after.png" width="700">
+        <p>チェックに引っかかったところをマージする。</p>
+      </div>
+
+      <div class='slide'>
+        <h2>古典的malloc & freeまとめ</h2>
+        <p>フラグメンテーションが頻発する。</p>
+        <ul>
+          <li>このmallocが主流だった時は「メモリはプログラムの最初に一気に確保するもの」だった</li>
+          <li>メモリが充分に空いている状態で、
+              必要なメモリを一気に確保するならフラグメンテーションは起きにくい</li>
+          <li>今はJava・C++のようなオブジェクト指向言語、
+              Rubyのようなスクリプト言語等、小さいmallocが頻発するものが多い</li>
+          <li>それをfirst fitでやるのはよくない</li>
+        </ul>
+
+      </div>
+
+
+      <div class='slide'>
+        <h2>mallocの改良</h2>
+        <p>そもそも、一つのfree listで管理することが無理がある</p>
+        <p>サイズ16Byte用のリスト、サイズ24Byte用のリスト……というようにリストを複数作ってやる</p>
+        <table border="0">
           <tr>
-            <th><img src="images/ts_ps.png" width="400"></th>
             <th>
-              <dl align="left">
-                <dl align="left">
-                  <dt>Temporary Space, Persistent Space</dt>
-                  <dd><li>DSはTemporary SpaceかPersistent Spaceに属する</dd>
-                  <dd><li>Temporary Spaceはポインタでアクセス。</li>
-                    <li>Persistent SpaceはURLでアクセス。つまり、名前を持つ。<br>
-                      (Persistent Space に書き込む = DBに登録する)</dd>
-                </dl>
-              </dl>
+              <img src="images/free_list_list.png" width="400">
+            </th>
+            <th valign="top" align="left">
+              <ul>
+                <li>mallocで要求されたsizeを8で割れば自分が使用するindexとなる</li>
+                <li>無限にリストを増やすわけにはいかないので、このリストを使うのは512バイト以下の場合のみ</li>
+                <li>512バイト以上の大きいデータの場合は、特殊な管理を行う</li>
+                <li>大きいデータと小さいデータを一緒に管理するからフラグメンテーションが進むんだ<br>
+                  →大きいデータ用の領域がもう一個欲しい<br>→そうだ、mmapを使おう</li>
             </th>
           </tr>
         </table>
-        <dt>Task</dt>
-        <dd><li>Input DS, Output DS</li></dd>
-        <dd><li>Input DSが全て揃った時点で実行される。そろったかどうかはTaskが持つ。</dd>
-        <dd><li>DSには持ってるTaskへのポインタが必要(Cerium、Aliceと同じ)</dd>
-        <dd><li>接続って具体的にどうやる？Ceriumで言うcreateTaskに相当する？</dd>
       </div>


       <div class='slide'>
-        <h2>Persistent DS</h2>
-        <p>
-          Persitent DSはkey(URL)を持つ。keyを持ってるので、書き込みは
-          <pre class="code">
-            goto write(ds);</pre>
-          でよい。DS自体がURLを持っているので、goto write(ds, key);とかしなくて良い。
-        </p>
-        <p>
-          ? ds->nextは即座に実行される。ds->nextがなければ、そこで計算は終了。
-        </p>
-        <p>
-          読み込みは、
-          <pre class="code">
-          goto read(ds);</pre>
-          すれば良いだけだが、ds->nextに次に行う演算が入っている。
-        </p>
-      </div>
-
-
-
-      <div class='slide'>
-        <h2>Meta Space, Core Space</h2>
-        <table>
-          <tr>
-            <th><img src="images/meta_space.png" width="400"></th>
-            <th align="left">
-              <p>Meta SpeceにはTaskのScheduleを行うScheduler、
-                DSの管理を行うDS Manager、Taskの生成を行うTaskManager(Ceriumと同等の機能)がある。
-              </p>
-            </th>
-          </tr>
-
-          <tr>
-            <th><img src="images/core_space.png" width="400"></th>
-            <th align="left">
-              <p>CoreSpaceにはCS間の遷移を行うDispatcher、同期制御を行うsynchronizer、
-                Memory Spaceの制御を行うSegment Manager(OSやOpenCLにもある)がある。
-                Segment ManagerはMemory間のコピーも行う
-              </p>
-              <p>
-                このDispatcher、Segment Manager辺りを担当することになる？
-              </p>
-            </th>
+        <h2>mmapってなんだっけ……？</h2>
+        <ul>
+          <li>ファイル(fdで指定したもの)をメモリにマップする</li>
+          <li>fdで&quot;/dev/zero&quot;を指定することでmmapをメモリ確保APIとして使用</li>
+          <li>このAPIを使ってHuge Blockはmmapで直接kernelから取得する</li>
+        </ul>
+        <pre class="code">
+          void *alloc_mmap(size_t size) {
+              int fd    = open("/dev/zero", O_RDONLY);
+              void *ret = mmap(addr, length, prot, flags, fd, offset);
+              return ret;
+          }</pre>
+        <table border="1" >
+          <tr bgcolor="dbffa3">
+            <th align="left" style="margin:10px 10px 10px;">addr</th><th align="left">mapするメモリアドレス。NULLを渡せばkernelがアドレスを選択する。</th>
           </tr>

+          <tr bgcolor="palegreen">
+            <th align="left">length</th><th align="left">addrから何バイトマッピングするか。</th>
+          </tr>
+
+          <tr bgcolor="dbffa3">
+            <th align="left" >prot</th><th align="left">マッピングのメモリ保護の指定。Read Write Exec None等がある。</th>
+          </tr>
+          <tr bgcolor="palegreen">
+            <th align="left">flags</th><th align="left">マップを要求された時、共有するかコピーを渡すか。</th>
+          </tr>
+          <tr bgcolor="dbffa3">
+            <th align="left">offset</th><th align="left">ファイルの何バイト目からをメモリにマップするか。</th>
+          </tr>
         </table>
       </div>

       <div class='slide'>
-        <h2>Memory Manager</h2>
+        <h2>Huge Block</h2>
+        <p>mmapで確保するので、free listからは独立している。
         <table>
           <tr>
-            <th><img src="images/memory_manager.png" width="500"></th>
-            <th align="left">
+            <th>
+              <img src="images/huge_block.png" width="500">
+            </th>
+            <th valign="top" align="left">
               <p>
-                DataSegmentは2^n allocatorで配分される。それらは</p>
-                <ul>
-                  <li>Physical Memory</li>
-                  <li>Cache Memory</li>
-                  <li>Parsistent Memory(Disk or Flash)</li>
-              </ul>
+                listを使って管理しているわけではないので、listをたどったりしなくて良い。</p>
               <p>
-                にMappingされる。
-              </p>
-              <p>
-                Persistent Space はDSの非破壊なBlanced Binary Treeにより構成される(jungle)
+                ほしかったらmmapして、いらなくなったらmunmapすればよい。
               </p>
             </th>
           </tr>
-
         </table>
+        <ul>
+          <li>free list上でフラグメンテーションが起きにくくなった(当たり前)</li>
+          <li>メモリの無駄が少ない<br>
+            大きなメモリは同じサイズでもう一度mallocされる可能性は低いので、
+          使わなくなったらすぐOSに返却するのは正しい</li>
+        </ul>
       </div>

-
-
-      <div class='slide'>
-        <h2>とりあえず取り掛かれること</h2>
-        <p>ここらへん？</p>
-        <ul>
-          <li>Segment Manager(Memory Allocator)
-          <li>Data SegmentのNon Destructive Tree
-          <li>TaskManager(Ceriumと同等の機能)
-        </ul>
-      </div>
-
     </div> <!-- presentation -->
   </body>
 </html>