次いでCtである。Ctは端的に言えば、既存のプログラムを如何にパラレル化するか、という手法である(Photo41)。具体的には、配列とかネストしたデータモデルを、如何にフラットに変換してパラレル化して扱うか、というあたりがキーとなる(Photo42)。

Photo41:この目標についてはこちらのエントリを参照。Extend "Deterministic" prarallel programming modelsの意味はこちらのエントリに深く説明がある。まぁ今のところ、こうしたプログラミングモデルが殆どのケースで使われている訳で、これはある意味当然ではあるのだが。

Photo42:配列とかネストになると、それを順にアクセスするのに時間が掛かる分、パラレル化はしにくい。特にTera-Scale Computingで想定している80コアに投入することを考えた場合、例えば4x4程度の配列であれば16個のフラットな配列と見なして展開して、各コアに投入してしまえば非常に高速に処理が出来る事になる。ここで言う"Flat"data parallelというのは、つまりそういう意味である。

具体的にCtはどんな処理を考えているのか、という実例が以下に続く。例えば配列演算の場合、全ての項目にデータがきちんと入っていれば問題ないが、そうでない場合もある(Photo43)。こうした場合にこれをフラット化して処理するというケースがまず該当する。

Photo43:こういう具合に展開するのが賢明かどうか、というのはケースによって変わってくる気もする。場合によっては素直に"1,2,0,5,0,0,0,6,0,3,0,0,0,0,4,7"と展開すべき時もあるので、あくまでも展開「例」と考えるべきなのだろう。

Nested Parallelismの代表例として引き合いに出されたのははTree-sortである(Photo44)。再帰的な呼び出しを掛ける中で、Task Parallelismは増えるが、Task Parallelismはむしろ減少するというもので、こうしたケースではTaskとDataのどちらに比重をおいてParallel化するかは非常に判断が難しい。もう一つのNested ParallelismはD&C(Divice & Concuer)の様なケースで、これもData Parallelismがどんどん減少してゆき、Task Parallelismが次第に増えてゆくわけで、効率よくParallel化するための配慮が難しい。

Photo44:Binary-sortの一種で、演習問題などには良く出てくるが、実際にこれを使うケースは希な気もする。

Photo45:日本語では「分割統治法」だが、要するにマージソートの事。

そんなわけでやるべき内容は結構難しいのだが、Ct自体はかなり高い目標を掲げている(Photo46)。プログラミングには殆ど手を加えず、CtのRuntimeを使うことでこれを実現しよう、というものだ。実際Ctの目標は、Cなどで苦労してParallel化しなくても、簡単な記述で後はCtのランタイムが対応してくれる、という事である(Photo47)。もっともこれを自動化しないと、コアの数にあわせてプログラミングのやり直しになってしまうわけで、今後バリエーションが増える(Nehalem世代では最大16threadが1CPU上で動くわけだし)マルチコアに最適化するのは難しい、ということだろう(Photo48)。

Photo46:あくまでこのパラレル化を自動で行う、というのがCtの目標の様だ(プログラム中に記述するのならOpenMPを拡張すれば済むと、いう事とデータのParallel化をメインにおいているから、自動化せざるを得ないというあたりもあるのだろう。これが最初に出てきたDeterministic prarallel programmingにも繋がる話である。

Photo47:ちなみに右のサンプルコードは

-----

TVEC smvpCSC(TVEC A, TVEC(I32> rind,
               TVECMI32> cols, TVEC v) {
    TVEC<64> expv, product, result;
    expv = v.distribute(cols);
    product = A*expv;
    product = product.applyNesting(rind, ctSparse);
    return product.reduceSum();
}

-----

となっている。

Photo48:ここには出ていないが、Larabeeなども間違いなくこのCtの対象となるだろう。というよりも、最初のCtのターゲットはLarabeeかもしれない。

ExoとかSTMに比べるとまだ先の道のりは長い気もするが、Many Core時代のProgrammingにおける本命はこのCtではないか、というのが筆者の素直な感想であり、その意味で今後の進捗が気になるところだ。