# HG changeset patch # User Yuhi TOMARI # Date 1413874341 -32400 # Node ID fb400fcfbb3a0f6d9bdd8fb4d335b17477eceb4f # Parent 8b6d326c1402b74a8efc9a02eb13c43966783189 malloc diff -r 8b6d326c1402 -r fb400fcfbb3a s6/blank.html --- 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 @@ -\ + @@ -88,7 +88,7 @@ @@ -114,137 +114,220 @@

研究目的

+

+ 当研究室ではCellおよびLinux、 + Mac OSX上で動く並列プログラミングフレームワーク、 + Ceriumの開発・改良を行っている。 +

+

本研究では新たにGPU上での並列実行に対応し、 + ヘテロジニアス(異種混合)環境下でのプログラミングをサポートする +

+

+ GPGPUでは通常のマルチコアCPUとは異なる並列プログラミング + と特別なチューニングが必要となる。 + そこでCeriumを用いてその差を吸収し、自動的なチューニングを可能にする。 +

+

+ しかし、GPUのみで並列計算を行った場合、Taskによっては並列度が出ない場合がある。 + そこでチューニングの一環として、MultiCoreとGPU上での同時実行を可能にする。 +

+
+ + +
+

進捗

+
+
Scalaで遊んでた
+
mallocのお勉強
+
kernel reading party(小崎さん)
+
動画
+
資料
+
+ +
+

mallocってなんだっけ……？

+ 
+          void *malloc(size_t size);
+ + 
+          char *str = (char*)malloc(length); // 使う型でキャストする
-

Code/Data Segment Systemの構造

- -

全てはDSとして扱われる。CSもDSの一種。

-

TaskもDSで、CSとDSの組になっている。

+

古典的malloc(K&R malloc)

+ + +
+ 
+          union header {
+              struct {
+                  union header *ptr;  // 空きリストの上なら次のブロック
+                  unsigned size;      // このブロックの大きさ
+              } s;
+          };
+
+ +
+

First Fit

+

+ リストを頭から見ていって、最初に見つけたものを使用するというすごいシンプルな方法。 +

+
-

Temporary/Persistent Space

-
-

Ceriumの再設計

+

CeriumにおけるGPGPUの最適化
+

First Fit

+ +

実は、もう一個先にもっと適切なブロックがあった。こんな場合に対応できない…というか、対応しないのがfirst fit。

+

あまりよくない……

+ + +
+

free

+ 
+          void free(void *ptr);
+

+ メモリの開放自体は、使用中のブロックをfree listに追加するだけで良い。 + 引数で受け取ったポインタ部分を開放したら良い……かに思える。 + でもそれだけじゃダメで、開放したい領域と隣接しているブロックが空きブロックなら併合しないといけない。 +

+ +
+ +
+

free

+ +

+ listから最初のポインタと、その次のポインタを取得。prev < p < nextを満たすまで走査していく +

+
+ +
+

free

+ +

あった！！

+

+ 開放後に前後のメモリと併合する必要がある場合があるので、prevとp・pとnextが隣接してるか判定する。 +

+
+ +
+

free

+ +

チェックに引っかかったところをマージする。

+
+ +
+

古典的malloc & freeまとめ

+

フラグメンテーションが頻発する。

+ + +
+ + +
+

mallocの改良

+

そもそも、一つのfree listで管理することが無理がある

+

サイズ16Byte用のリスト、サイズ24Byte用のリスト……というようにリストを複数作ってやる

+
- +
-
-
-
Temporary Space, Persistent Space
-
  • DSはTemporary SpaceかPersistent Spaceに属する
    • -
  • Temporary Spaceはポインタでアクセス。
    • -
  • Persistent SpaceはURLでアクセス。つまり、名前を持つ。
    - (Persistent Space に書き込む = DBに登録する)
    • -
    -
    + +     		+
      +
    • mallocで要求されたsizeを8で割れば自分が使用するindexとなる
      • +
    • 無限にリストを増やすわけにはいかないので、このリストを使うのは512バイト以下の場合のみ
      • +
    • 512バイト以上の大きいデータの場合は、特殊な管理を行う
      • +
    • 大きいデータと小さいデータを一緒に管理するからフラグメンテーションが進むんだ
      + →大きいデータ用の領域がもう一個欲しい
      →そうだ、mmapを使おう
    -
    Task
    -
  • Input DS, Output DS
    • -
  • Input DSが全て揃った時点で実行される。そろったかどうかはTaskが持つ。
    • -
  • DSには持ってるTaskへのポインタが必要(Cerium、Aliceと同じ)
    • -
  • 接続って具体的にどうやる？Ceriumで言うcreateTaskに相当する？
    • -

    Persistent DS

    -

    - Persitent DSはkey(URL)を持つ。keyを持ってるので、書き込みは - 

    -            goto write(ds);
    - でよい。DS自体がURLを持っているので、goto write(ds, key);とかしなくて良い。 -

    -

    - ? ds->nextは即座に実行される。ds->nextがなければ、そこで計算は終了。 -

    -

    - 読み込みは、 - 

    -          goto read(ds);
    - すれば良いだけだが、ds->nextに次に行う演算が入っている。 -

    -
    - - - -
    -

    Meta Space, Core Space

    - - - - - - - - - +

    mmapってなんだっけ……？

    + + 
    +          void *alloc_mmap(size_t size) {
+              int fd    = open("/dev/zero", O_RDONLY);
+              void *ret = mmap(addr, length, prot, flags, fd, offset); 
+              return ret;
+          }
    +
    -

    Meta SpeceにはTaskのScheduleを行うScheduler、 - DSの管理を行うDS Manager、Taskの生成を行うTaskManager(Ceriumと同等の機能)がある。 -

    -
    -

    CoreSpaceにはCS間の遷移を行うDispatcher、同期制御を行うsynchronizer、 - Memory Spaceの制御を行うSegment Manager(OSやOpenCLにもある)がある。 - Segment ManagerはMemory間のコピーも行う -

    -

    - このDispatcher、Segment Manager辺りを担当することになる？ -

    -
    + + + + + + + + + + + + + + +
    addrmapするメモリアドレス。NULLを渡せばkernelがアドレスを選択する。
    lengthaddrから何バイトマッピングするか。
    protマッピングのメモリ保護の指定。Read Write Exec None等がある。
    flagsマップを要求された時、共有するかコピーを渡すか。
    offsetファイルの何バイト目からをメモリにマップするか。
    -

    Memory Manager

    +

    Huge Block

    +

    mmapで確保するので、free listからは独立している。 - - + -
    + + +

    - DataSegmentは2^n allocatorで配分される。それらは

    -
      -
    • Physical Memory
      • -
    • Cache Memory
      • -
    • Parsistent Memory(Disk or Flash)
      • -
    + listを使って管理しているわけではないので、listをたどったりしなくて良い。

    - にMappingされる。 -

    -

    - Persistent Space はDSの非破壊なBlanced Binary Treeにより構成される(jungle) + ほしかったらmmapして、いらなくなったらmunmapすればよい。

    +

    - - -
    -

    とりあえず取り掛かれること

    -

    ここらへん？

    - -
    -