Chapelメモ - 2

プログラミング Chapel

前置き

さうさう、云ひ忘れてゐたけれど、Chapelと云ふのは竝列言語處理系の一つであり、その中でもPGASと呼ばれる部類に入り、MPI等より高水準・高生産な言語である。http://chapel.cray.com/で色々ダウンロードしたりできるので試してみたい方はどうぞ。
さて、今囘はBlockDistについてである。データパラレルなプログラムの竝列化も可能であるChapelではあるが、そのデータの分割方法を明示的に指定する方法は言語標準に組み込まれていない。かはりに、モジュールを用ゐることでこれを明示的に指定できる。今のところ最初から用意されてゐるモジュールはブロック分割とサイクリック分割の二つなのでここでは前者を調べてみる。

Domain Mapについて

Chapelで配列のインデックスに相當するものはdomainと呼ばれているが、これをどうやつてlocale*1に割り當てるかを指定するのがdomain mapである。そして、このdomain mapのうちデフォルトで用意されてゐるのがBlockDistとCyclicDistなのである。

use BlockDist;
var MyBlockDist: dmap(Block(rank=2)) = new dmap(new Block([1..n,1..n]));
var Dom: domain(2) dmapped MyBlockDist = [1..n, 1..n];
var Array: [Dom] real;

実はMyBlockDistの型は宣言しなくても推論される。

BlockDistの概念

ブロック分割というのは誰しもが最初に思い付きさうな分割である。

BoundingBoxとは

マニュアルをまず和譯してみる。

標準的なブロック分割はbounding boxに依つてインデックスの聚合をブロック状に分割するもので、BlockDistモジュールで定義されてゐる。rank*2とインデックスの型*3をパラメータとして持つ。即ちこれらが異なるドメイン間では異なるBlockDistを用いる必要がある。
まず、rankがdであるようなブロック分割に対して、bounding boxl_1..h_1, \dots, l_d..h_dと、ドメイン全体で定義された対象となるロケールの配列（謎）0 .. n_1 - 1, \dots, 0 .. n_d - 1が与えられているとする。
この時、このブロック分割はiの第k成分からjの第k成分を計算することでロケールへの割り当てを決定する。完全に意味不明です本当にありがとうございました。j_k = \begin{case}0 & i_k < l_k \\ \left\lfloor \displaystyle \frac{n_k (i_k - h_k)}{h_k - l_k + 1} \right\rfloor & l_k \le i_k \le h_k \\ n_k - 1 & i_k > h_k\end{case}

でもなんだかbounding boxは問題スペースと揃えといたほうが何かといい気がした。

*1:抽象化されたマシン

*2:インデックスの次元

*3:これは普通の配列だけでなく、ということなのだろうか？