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

--abstract:

--Cell用Task Manager Cerium

本研究室では、Cell 用の並列TaskManager Ceriumを作成し、Rendering Engine を含む
ゲームや並列計算の例題の作成と評価を行ってきた。TaskManager と Rendering Engine はシューティングゲーム
やレーシングゲームを記述するのに十分な性能を持っており、台数効果も満足いくものと
なっている。しかし、この開発により Ceirum の問題点も明らかになってきている。
本論文では、今まので Cerium の構成と問題点を記述し、新しい TaskManager の設計
方針を述べる。

--Ceriumでの並列プログラミングの問題点

Cerium では、ゲームプログラミング及び、sort や word count などの例題を書いたが、いくつかの問題点が明らかになっている。

  Task の取り扱うデータ型が示されない
  Task 自体は簡単だが Task を構成する方法が繁雑
  Open CL に比べても構文的に複雑
  Task の種類が複雑
  Task の依存関係の記述がデータの依存関係と無関係
  Task Scheduler が大きくメモリを圧迫
  
などである。実装方法的にもいくつか問題がある。

  C++ と Task 記述の相性が良くない
  Task Manager が複雑になりすぎ

Task Scheduler は Queue からTaskを取り出して一つ一つパイプライン実行を行うインタプリタ的な構造を持っている。これが、Task Manager 自体を複雑にする原因になっている。

--Continuation based C との相性

当研究室で開発している Continuation based C は、並列処理の基本単位である Task に対応した code segment を持っている。これを Cerium に対応させようとすると以下のような問題がある。

   Inteface の型が整合しないとTask同士を接続できない
   Scheduler への接続が特定のInterfaceを要求する

どちらも、Code segment の interface (入力と出力) は、決まった形であるべきだと言うことを示している。しかし、Task 自体は様々なデータを取り扱う必要がある。ここに矛盾がある。この矛盾を解決するためには、データ側も基本単位を導入するべきだいうことになる。

Data Segment は、Code segment の双対概念であり、C の構造体に相当する。CbC の Code segment は、

   input interface (関数の引数の型)
   output interface (goto 文の引数の型)

を持っているが、これらを

   input datasegments
   output datasegments

に置き換える。つまり、Code segment は、複数の動的に割り当てられた Data segment を持っている。これらは、標準的な構造を持っているので、Interface の型の不整合を避けることができる。

Data segment は型を持っていて、その型は実行時に一致している必要がある。分散通信を考えて、Data segment の型は MessagePack \cite{MessagePack} を用いる。

--C++ との相性

Cerium の Task は、Cell のspuとppuで共通であり、同じ Task ID で管理されている。これは C++ のオブジェクトとは関係ない。Cerium の開発でわかったのは、Cerium のデータは、Actor の become 的\cite{Act3} に書き換えられるということである。C++のようなポインタを使い合わし、オブジェクトの内部の書き換えで状態を作るようなオブジェクト指向プログラミングと、細分化したTaskを並列に廻す Ceirum のようなシステムとの相性は良くない。
Task の入力と出力は異なる場所に書かれる。処理は、常にダブルバッファを用いて行われているのでそのようになる。

--階層的パイプライン

プログラム中の自明な並列性は、データ並列とループのパイプラインの二つであり、パイプラインはプログラムの中で、様々なレベルで行われる。Task そのものは入力データから出力データを計算するだけなので単純だが、その入出力データをダブルバッファリングとして切替えたり、適切な並列度を得られるように徐々に生成するのは非常に繁雑になる。

これらのデータの管理は、中心となるアルゴリズムとは別に並列実行を行うアーキテクチャに特化した処理が必要となる。例えば、分散環境で並列処理するのか、MPIなのか、Cell や Open CL なのかによって異なる。これらを、すべて Task という一括りで扱うと並列計算しない複雑なTaskができてしまう。

これらのデータ管理用の Task は、本質的には Data Segment に対する Iterator であり、ライブラリまたはコンパイラにより生成されるべきものだと考えられる。

--Data Segment を用いた Cerium の再設計

Cell 用のTaskManager Cerium の再設計の方針としては以下のようになる。

  CbCのCode segment の導入
  定型的な Data 単位である Data

---Data Segment の型

---Data Segment のAPI

---Task Dependendcy

---Data Segment Storage Type

---Data Segment の処理の記述

--期待される効果