-title: Cerium における DataSegment API の設計

-author:  金城裕  河野真治

--affiliation:  琉球大学

--Cell用TaskManager Cerium 

Cellの6 SPUのTask をパイプラインで管理する
Open CL と似たフレームワーク。

並列プログラムの例題や、ゲームプログラムを作成してきた。

もう、Linux が PS3 で動かないのでやっても意味がない。


--Cerium, Open/CLでの並列プログラミングの問題点

	Task の取り扱うデータ型が示されない
	Task 自体は簡単だが Task を構成する方法が繁雑
	Open CL に比べても構文的に複雑
	Task の種類が複雑
	Task の依存関係の記述がデータの依存関係と無関係
	Task Scheduler が大きくメモリを圧迫
	C++ と Task 記述の相性が良くない
	Task Manager が複雑になりすぎ

--Task の取り扱うデータ型が示されない


    static int
    run(SchedTask *s, void* rbuff, void* wbuff) {

    int end = s->get_inputSize(0)/sizeof(Data);
    DataPtr r_data = (DataPtr)s->get_input(0);

void* で受けてしまうので型チェックができない。

-- Task 自体は簡単だが Task を構成する方法が繁雑

        int i = s->split_num-1;

        s->fsort[i] = manager->create_task(QUICK_SORT,
            (memaddr)&s->data[i*block_num], sizeof(Data)*last_block_num,
            (memaddr)&s->data[i*block_num], sizeof(Data)*last_block_num);
        if (i>0 && s->bsort[i-1]) {
            s->fsort[i]->wait_for(s->bsort[i-1]);
        }
        s->fsort[i]->set_cpu(SPE_ANY);

Open CL に比べても構文的に複雑

-- Task の種類が複雑

    SimpleTask     read と write が一つ
    Task           read と write が8個まで
    ArrayTask      read と write が任意個、ひと続きで実行される
    MainTask       ppe で動作、Task生成が可能

--Task の依存関係の記述がデータの依存関係と無関係

    for (int i = 0; i < s->split_num-1; i++) {
        s->fsort[i] = manager->create_task(QUICK_SORT,
            (memaddr)&s->data[i*block_num], sizeof(Data)*block_num,
            (memaddr)&s->data[i*block_num], sizeof(Data)*block_num);
        if (i>0 && s->bsort[i-1]) {
            s->fsort[i]->wait_for(s->bsort[i-1]);
        }
        if (i<s->split_num-2 && s->bsort[i]) {
            s->fsort[i]->wait_for(s->bsort[i]);
        }
        s->fsort[i]->set_cpu(SPE_ANY);

--その他

	Task Scheduler が大きくメモリを圧迫

	C++ と Task 記述の相性が良くない

	Task Manager が複雑になりすぎ

--Continuation based C

関数呼び出しの代わりに goto を持つ C

Input Interface, Output Interface

<pre>
       __code f(struct input a) { goto g(struct input a) ; }
       __code f(struct input a, __code (*g)()) { goto g(struct input b) ; }
</pre>
<img src="fig/code.jpg">

--Code Segment 単位での並列実行

First, make single process code segments.

<img src="fig/single.jpg"     id="anim" alt=""/>

これを並列に実行する。

<img src="fig/concurrent.jpg" id="anim" alt=""/>

code segment を並べ替えて、分散通信したりスケジューリングしたい


--再接続の問題

    type miss match

    fix argument type on applications

<img src="fig/cbc.jpg">

--再接続の問題

汎用の型でないと再接続できない。

<img src="fig/reconnection.jpg" class="incremental">

--Data segment

Code Segment の双対。型を持つメモリの切れ端。

Code Segment の Interface を置き換えるもの。

   input datasegments
   output datasegments

<img src="fig/datasegment.jpg">

--Data segmentを使ったパイプライン実行

<img src="fig/pipeline.jpg">

--Code segment の参照

Data segment を処理する Code Segment への参照

   Pointer ではない
   GPGPUやSPUで、実行コードは別空間なことが多い

GPGPUでも、通常のCPUでも両方で動かしたい。ポインタでは困る。

Code Segment は ID で指定する。番号。
    実行CPUも指定できる	
    分散フレームワークでは、Geo Addressing を使用。

--get_segment, put_segment

Cell  / SPU では、ローカルメモリ

read, write 以外に実行時に必要なデータもある。

    get_segment
    wait_segment

で Cache / LRU 的に取得する。

    smanager->wait_segment(span_put_ms);

    span_put_ms = span_get_ms;
    smanager->put_segment(span_put_ms);

    span_get_ms = smanager->get_segment((memaddr)spackList[index], span_ml);
    smanager->wait_segment(span_get_ms);

    prev_index = index;
    spack = (SpanPackPtr)span_get_ms->data;


--Data Segement 

    get_segment で全部実装した方が良い?

    Data Segment として API を整理しよう。

    Json で表す

    分散計算でも使えるように

    Protocol Buffer や MessagePack

---Data Segment のAPI

Data Segment は以下のAPIを持っている

  create
  read
  update
  delete

KVS 的にアクセスする。

--Data Segment 更新の Atomicity

  Queuing
  Update
  Proority Queue

生成された Data segment は synchronized queue として使うことができる。

<img src="fig/DSCS.jpg">

---Task Dependendcy

Cerium では、

    task->wait_for(task1);

としていたが、繁雑。Data dependency が自然に依存関係を決めるので、それを
使うのが良い。

Data segment を Code segment に割り当てた時に、自動的に dependency が決まる。

    Data segment -> Code segment -> Datas segment

---Data Segment Storage Type

Data segment は様々な場所に置ける。

    Main Memory
    Local Memory
    Cache Memory

    Persitent Store

Code segment からは、指定された Data segment にしかアクセスできない。

--まとめ

PS3 Cell 用のTaskMangaer Cerium の利点/欠点を考察し、

Data Segment と Code Segment を用いた新しいフレームワークを提案した。

Continuation based C と組み合わせる

分散計算にも同様のAPIを用意し、並列環境でも分散環境でも共通に使える

フレームワークを作成したい。