うさぎさんでもわかる並列言語 Chapel

うさぎさんでもわかる並列言語 Chapel
Tutorial of Chapel – the Parallel Programming Language
無線部開発班
2015 年 8 月 6 日
はじめに
1
Chapel*1 は PGAS により共有メモリから分散メモリまでスケーラブルに扱える高生産性並列言語です。
2
開発環境
2.1
インストール
Cray 社が公開している最新版を入手して、.tar ファイルを展開します。
$ tar xvzf chapel -1.11.0. tar . gz
並列スケジューラに MassiveThreads を利用するように環境変数を設定します。
$ export CHPL_TASKS = massivethreads
README の説明に従って、make コマンドでビルドします。Python2 と g++ が必要です。
$ make
コンパイラを呼び出せるように設定します。bash の場合は.bashrc に以下の 1 行を追記します。
cd ~/ chapel -1.11.0/ && source ./ util / setchplenv . bash && cd -
環境変数はコンパイル時や実行時に必要なものもあるので設定ファイルに追記すると良いでしょう。
2.2
Hello, world!
テキストエディタで以下の 1 行だけのプログラムを打ち込み、hello.chpl と名前を付けて保存します。
writeln ( " Hello , world ! " );
シェルを起動して chpl コマンドでコンパイルしましょう。
$ chpl -o hello hello . chpl
実行ファイル hello が生成されるので、起動してみましょう。
$ ./ hello
Hello , world !
ごく単純なプログラムならば、面倒な main 関数は不要で、たった 1 行でもプログラムが完結します。
2.3
最適化オプション
コンパイル時に fast オプションを付けることで最適化が有効になり FLOPS 値が大幅に改善します。
$ chpl -o foo foo . chpl -- fast
*1
http://chapel.cray.com
2
3
字句の構造
3.1
コメント
コメントの書き方は C 言語 (C99) や Java と同じです。
// 1 - line comments
/*
multiline comments
or block comments
*/
3.2
空白文字
半角空白、水平タブ、改行 (LF)、キャリッジリターン (CR) は区切り文字として扱われます。
3.3
トークン
識別子は半角英字か半角アンダースコアで始まる文字列で、2 文字目以降は半角数字と半角ドル記号も
使用できます。大文字と小文字は区別されます。
4
式の評価
4.1
型システム
Chapel は強い静的型付け言語で、式の型はコンパイル時に決定します。言語仕様で組み込まれた型を
特にプリミティブ型と呼び、有意な値がないことを示す void や真偽値の bool、符号付整数の int と
無符号整数の uint、実数の real や虚数の imag、複素数の complex、文字列の string が該当します。
4.2
リテラル
true と false は真偽値で、bool 型の値です。writeln 関数でコンソールに出力してみましょう。
writeln ( true );
writeln ( false );
接頭辞 0x(0X) の整数は 16 進数、接頭辞 0b(0B) の整数は 2 進数、それ以外の整数は 10 進数です。
writeln (0 x12 );
writeln (0 b11 );
writeln (1234);
小数点を含む有効数字部と指数部で構成される 10 進実数は real 型です。指数部は省略可能です。
writeln (10.0 e2 );
writeln (10.0);
3
実数の直後に虚数単位 i を追記すると imag 型になります。
writeln (1.0 i );
半角ダブルクォートか半角シングルクォートで囲んだ文字列は string 型の値です。
writeln ( " This is ’ single - quote ’" );
writeln ( ’ This is " double - quote " ’ );
4.3
型変換
整数から実数へ、あるいは、文字列から整数へ型変換したい場合には型変換演算子を用います。
writeln (1234: real );
writeln ( " 321 " : int );
4.4
算術演算
算術演算子としては加減乗除の四則演算の他に累乗演算子**が定義されています。
writeln (1.0 + (2 - 3) * 4.0 / 5 ** 2);
4.5
ビット演算
整数に対するビット演算子としては論理和、論理積、排他的論理和をサポートしています。
writeln (1000 | 1001);
writeln (1011 & 0101);
writeln (0011 ^ 0101);
4.6
シフト演算
整数に対するシフト演算子としては左シフト、右シフトをサポートしています。
writeln (1 << 3);
writeln (8 >> 2);
4.7
関係演算
整数や実数、虚数に対する関係演算としては各種の不等号をサポートしています。
writeln (0 < 1.0);
writeln (1.0 > 2);
writeln (2 <= 30);
writeln (30 >= 2);
また、等価性と不等価性を調べる演算子として==と!=が定義されています。
4
writeln ( " hello " == " world " );
writeln (1234567 != 7654321);
4.8
論理演算
真偽値に対する演算としては論理和、論理積、排他的論理和をサポートしています。
writeln ( true && false );
writeln ( true || false );
writeln ( false ^ false );
論理和と論理積は短絡評価演算子のため、左側の式で結果が決まる場合は右側の式は評価されません。
4.9
条件演算
条件式の値によってどちらの式を評価するかを制御したい場合には if 演算子を使います。
if 2 > 1 then " 2 is bigger than 1 " else " 2 is lesser than 1 "
4.10
反復演算
式を繰り返し評価してその値をイテレータとして返したい場合には for 演算子を使います。
for i in 1..100 do i * 2
4.11
文字列の結合
+ 演算子は文字列の結合にも利用できます。また、文字列と他の値との結合も可能です。
5
変数と定数
5.1
変数
Chapel は、破壊的代入が可能な変数を持ちます。Chapel は強い静的型付けを行うので、全ての変数の
型はコンパイル時に決定され、他の型の値は代入できません。例えば int 型変数 foo を宣言するには、
var foo : int ;
と記述します。変数は宣言と同時に初期値を代入することも可能です。例えば、
var foo : int = 12;
変数を明示的に初期化する場合は、以下のように型を省略することができます。
var foo = 12;
5
5.2
静的定数
言語仕様書には parameter と表記されていますが、関数の仮引数と紛らわしいので本稿では静的定数と
呼びます。param は静的定数を宣言する予約語です。静的定数はコンパイル時に値が決定される定数で
プリミティブ型及び列挙型のみが使用できます。例えば値が 12 の int 型定数 foo を宣言するには、
param foo : int = 12;
初期化式は省略できませんが、型は省略できます。
param foo = 12;
初期化式はコンパイル時点で値が確定する式のみが使用でき、初期化済みの定数は再代入できません。
後述するように、静的定数は Chapel のジェネリクスにおいて必須となる重要な言語仕様です。なお、
定数宣言時に config 修飾子を付けることで、値をコンパイルオプションで変更できるようになります。
config param foo = 121;
定数 foo はデフォルトでは 12 ですが、コンパイル時にオプション s を付けることで変更できます。
chpl foo . chpl -s foo =12321;
上のようにコンパイルすると、静的定数 foo は 12321 になります。
5.3
動的定数
言語仕様書には constants と表記されていますが、静的定数と明確に区別するため本稿では動的定数と
呼んでおきます。動的定数は単に再代入できない変数で、静的定数のような型の制限はなく、いかなる
型の値でも代入できます。例えば、値が 12 の int 型定数 bar を宣言するには、
const bar : int = 12;
初期化式は省略できませんが、型は省略できます。
const bar = 12;
クラス型の動的定数ではインスタンスへの参照が固定され、初期化時に代入されたインスタンスを終生
参照しますが、当然ながらそのフィールドへの破壊的代入は何ら制限されません。なお、定数宣言時に
config 修飾子を付けることで、値を起動時オプションで変更できるようになります。
config const bar = 12;
定数 bar はデフォルトでは 12 ですが、起動時にオプション bar を付けることで変更できます。
./ foo -- bar =12321
上のように起動すると、動的定数 bar は 12321 になります。なお、起動オプションの一覧は
./ foo -- help
上のように help オプションで確認できます。
6
5.4
型定数
Chapel では型に別名を付けることができます。
type integer = int ;
この別名は変数宣言や関数の引数・返り値の型宣言などあらゆる場所で利用できます。
var a : integer ;
型の別名は実質的には静的定数です。例えば、静的定数と同様にコンパイルオプションで変更できます。
config type foo = int ;
6
文の構造
6.1
式文
式文とは、式の直後に半角セミコロンを追記した文で、単に式が評価されるだけの文です。
6.2
ブロック
ブロックは複数の文の並びをまとめて括弧で括った文で、ブロック内の文を先頭から順に実行します。
ブロックは固有のスコープを持ち、ブロック内の変数や関数に外側からアクセスすることはできません。
{
var a = 12;
writeln ( a );
}
writeln ( a );
例えば、上のサンプルプログラムでは、ブロックの中の writeln 関数は変数 a にアクセスできますが、
ブロック外の writeln 関数は変数 a のアクセスが禁止されているので、コンパイルエラーになります。
このように、構文上の包含関係によりアクセス可能な範囲が決定される流儀を静的スコープと呼びます。
6.3
if 文による条件分岐
if 文は条件式によって処理を分岐する文です。
if age < 20 then writeln ( " Adult Only " ) else writeln ( " Welcome " );
条件式は bool 型である必要があります。else 以下は不要ならば省略できます。条件式を括弧で括る
必要がないことに注意してください。条件式を括弧で括らないがゆえに、then で条件式の終了位置を
明示する必要があります。ただし、then 節がブロックである場合は、then を省略することができます。
if language == " Kotlin " {
writeln ( " I love Kotlin " );
}
7
6.4
select 文による条件分岐
select 文は C 言語の switch 文のような多分岐を行う文です。
select animal {
when " cat " do writeln ( " meow " );
when " dog " do writeln ( " bowwow " );
otherwise writeln ( " gobblegobble " );
}
まず条件式が評価され、続いて、その値に等しい式の when 文が実行されます。比較に用いる演算子は
==です。該当する when 節がない場合は otherwise 文を実行します。otherwise 文は select 文内の
任意の位置に 1 個だけ記述できます。when 文と otherwise 文はそれぞれ固有のスコープを持ちます。
6.5
while 文による反復
while 文は C 言語の while 文と同様の繰り返し構文です。
while i < 1024 do i *= 2;
条件式には bool 型の式のみ指定できます。まず条件式が評価され、その値が true である限り do 節を
反復実行します。条件式を括弧で括る必要はありませんが、do 節がブロックの場合 do を省略できます。
6.6
do while 文による反復
do while 文は C 言語の do while 文と同様の繰り返し構文です。
do i *= 2 while i < 1024;
条件式には bool 型の式のみ指定できます。do 節を実行した後で条件式を評価する動作を条件式の値が
false になるまで繰り返します。従って、条件式の値にかかわらず最低 1 回は do 節が実行されます。
6.7
for 文による反復
for 文はイテレータから取り出される個々の値に対する処理を実行する構文です。
for i in 1..100 do writeln ( i );
C 言語の for 文は単なる繰り返し構文ですが、Chapel の for 文は一般に foreach 文などと呼ばれる
構文であり、単なる繰り返しというよりもイテレータの要素に対する処理を記述するための構文です。
6.8
break 文による大域脱出
繰り返し構文から大域脱出するには break 文を使います。
for i in 1..100 do if i == 10 then break ;
脱出対象の繰り返し構文は後述のようにラベルで指定することができます。
8
6.9
continue 文によるスキップ
繰り返し構文の処理を一度だけスキップするには continue 文を使います。
for i in 1..100 {
if i == 10 then continue ;
writeln ( i );
}
スキップ対象の繰り返し構文は後述のようにラベルで指定することができます。
6.10
繰り返し構文のラベル
繰り返し構文が入れ子になっている場合、break 文や continue 文は最も内側の繰り返し構文を脱出・
スキップします。外側まで一気に脱出するには、ラベルを用いて脱出対象の繰り返し構文を指定します。
label LABEL for i in 1.. n {
for j in 1.. n {
if A [i , j ] == findVal {
writeln (i , j );
break LABEL ;
}
}
}
ラベルの付け方は簡単で、繰り返し構文の直前に label 文で識別子を付記するだけです。
7
関数
7.1
関数の基本
int 型の引数 x、y を取って、その合計値をコンソールに出力する foo 関数を定義してみましょう。
proc foo ( x : int , y : int ): void {
writeln ( x + y );
}
Chapel では引数の型は引数名の後にコロンを挟んで指定します。返り値の型も同様に引数宣言の後に
コロンを挟んで指定します。引数が複数ある場合は引数宣言をカンマで並べます。引数がない場合は、
proc hoge (): void {
writeln ( " hoge " );
}
この場合、以下のように引数宣言そのものを括弧ごと省略することもできます。
proc fuga : void {
writeln ( " fuga " );
}
9
定義した関数を呼び出すには、関数名の後に実引数を並べます。
foo (1 , 2);
hoge ();
ただし、引数宣言を省略した場合は、関数名を書くだけで関数呼出しになります。
fuga ;
実引数は名前を指定して渡すこともできます。例えば、foo 関数の例では、
foo ( x = 1 , y = 2);
foo ( y = 2 , x = 1);
上のように呼び出せば x に 1、y に 2 が渡されます。引数にはデフォルト値を設定することもできます。
proc foo ( x : int = 1 , y : int = 2): void {
writeln ( x + y );
}
デフォルト値を設定した引数は呼び出し時に省略でき、省略時はデフォルト値が渡されます。つまり、
foo ( x = 3 , y = 2);
foo ( x = 3);
上の関数呼び出しはどちらも x に 3 が、y に 2 が渡されます。
7.2
可変長引数
関数の引数の個数は可変とすることができます。これを可変長引数と言います。
proc foo ( x : int ...): void {
for param i in 1.. x . size do writeln ( x ( i ));
}
実体はタプルで、引数 x にはタプルが渡されます。可変長引数の代わりにタプルを渡すことも可能です。
foo (1 , 2 , 3);
foo ((1 , 2 , 3 , 4 , 5));
7.3
関数の返り値
関数は終了時に値を返すことができます。関数を終了して値を返すには return 文を使います。
proc foo ( x : int , y : int ): int {
return x + y ;
}
また、返り値の型に void を指定した場合は、返り値なしで return 文を書きます。
10
proc bar ( x : int , y : int ): void {
if ( x == y ) then return ;
writeln ( " x is not y ! " );
}
なお、関数の内容が return 文だけである場合は、括弧を省略することができます。
proc foo ( x : int , y : int ): int return x + y ;
7.4
型推論
Chapel は型推論を備えており、変数や引数、戻り値の型は省略可能です。foo 関数を思い出しましょう。
proc foo ( x : int , y : int ): int return x + y ;
上の foo 関数は以下のように書き直しても同じです。
proc foo (x , y ) return x + y ;
引数の型は関数呼出しの式から決定されます。例えば、
foo (1 , 2);
上のように呼び出すと、x も y も int 型になります。また、
foo (1.0 , 2 i );
上のように呼び出すと、x は real 型で、y は imag 型になります。引数の型を取り出すには、
proc bar ( x : ? typeofx ) {
if ( x == int ) {
writeln (x , " is int " );
} else {
writeln (x , " is not int " );
}
}
上のように定義すると、引数 typeofx に自動的に型が渡されます。bar 関数を呼び出してみましょう。
bar (1);
bar ( " string " );
上のプログラムを実行すると、以下のように出力されます。
1 is int
string is not int
Chapel では予約語 type で型を取得できるので、以下のように記述しても同じように動作します。
11
proc bar ( x ) {
if ( x . type == int ) {
writeln (x , " is int " );
} else {
writeln (x , " is not int " );
}
}
7.5
匿名関数
Chapel はラムダ式に対応しており、関数を匿名関数として記述することができます。
const add = lambda ( x : int , y : int ) return x + y ;;
変数に代入した匿名関数は、通常の関数と同様に引数を与えて呼び出すことができます。
writeln ( add (12 , 3));
7.6
第一級関数
Chapel は第一級関数に対応しており、関数を変数に代入したり、高階関数を定義したりできます。
proc add ( x : int , y : int ): int {
return x + y ;
}
add 関数を定数に代入してみましょう。
const op : func ( int , int , int ) = add ;
関数の型は引数の型と戻り値の型を順番に並べて func 関数を呼び出すことで表現します。
writeln ( op (57 , 73));
定数 op に代入した関数 add を呼び出せば、57 + 73 が評価されて 130 と出力されます。
7.7
構造的部分型
Chapel は関数の実引数の型を元に型推論するので、構造的部分型の恩恵を受けられます。まず、
class Duck {
proc quack () {
writeln ( " quack ! " );
}
}
上掲の Duck クラスを定義します。Duck 型の引数を取り quack を呼び出す duck 関数を定義します。
12
proc duck ( x : Duck ) {
x . quack ();
}
引数 x の型宣言を省略してみましょう。duck 関数に Duck クラスのインスタンスを渡して呼び出せば
引数 x は自動的に Duck 型として解釈されます。従って、以下の記述でも問題なくコンパイルできます。
proc duck ( x ) {
x . quack ();
}
duck ( new Duck ());
ただし、duck 関数の引数には quack というメソッドを持つという制約が課されています。従って
class Kamo {
proc quack () {
writeln ( " quack ! " );
}
}
Kamo クラスのインスタンスを duck 関数に渡しても問題ありません。引数 x が Kamo 型と解釈され、
Kamo クラスの quack 関数が呼び出されるためです。しかし、Cat クラスではエラーになります。
class Cat {
proc myaa () {
writeln ( " myaa ! " );
}
}
Cat クラスには quack という名のメソッドがないためです。こうした Chapel の型推論の挙動を逆手に
取ると、関数内でどのような名前や実引数のメソッドを呼び出しているかによって仮引数の型が暗黙に
指定される、と見ることもできます。
duck ( new Duck ()); // OK
duck ( new Kamo ()); // OK
duck ( new Cat ()); // NG
つまり、duck 関数の例で言えば、引数 x は必ず quack というメソッドを持たなければならず、逆に
quack というメソッドさえ持っていればどんな値でも引数にできます。これは動的型付け言語で言えば
ダックタイピング、静的型付け言語で言えば構造的部分型の一例と言えます。
7.8
演算子の定義
Chapel は演算子のオーバーロードに対応しており、既存の演算子を新たな引数に適用できます。
proc !( a : string ) return a + " ! " ;
writeln (! " Hello , World " );
当然ながら演算子の場合は引数の型を省略できません。2 項演算子の場合は引数を 2 個取ります。
13
7.9
リンケージ修飾子
関数のコンパイル時のリンケージ動作を指示するには、表 1 のリンケージ修飾子を使います。
Table 1 リンケージ修飾子の一覧
修飾子
意味
inline
コンパイル時にインライン展開する
export
関数がプログラムの外に公開される
extern
関数の実体が外部で実装されている
例えば、C 言語で書かれた sched_getcpu 関数を呼び出す際には、以下のように宣言します。
extern proc sched_getcpu (): c_int ;
ただし、関数の実体を定義したヘッダファイルをコンパイル時に読み込ませる必要があります。
7.10
引数の修飾子
関数の引数の扱い方を指示するには、表 2 の修飾子を使います。
Table 2 引数の修飾子の一覧
修飾子
意味
in
引数の初期値に実引数の値が渡される
out
引数の最終値が実引数に書き戻される
inout
引数の初期値と最終値が受け渡される
ref
引数に実引数自体への参照が渡される
param
引数は静的定数
type
引数は型定数
具体例を見てみましょう。
proc foo ( in x : int ) {
writeln ( " x is " , x );
x = 12;
}
var a = 1;
foo ( a );
writeln ( " a is " , a );
引数 x に修飾子 in を付けています。実行してみると、引数 x に変数 a の値が格納されます。
x is 1
a is 1
14
foo 関数で x の値が 12 に変更されますが、変数 a の値は 1 のままです。out の例も見てみましょう。
proc bar ( out x : int ) {
writeln ( " x is " , x );
x = 12;
}
var a = 1;
bar ( a );
writeln ( " a is " , a );
引数 x に out 修飾子を付けています。実行してみると、
x is 0
a is 12
引数 x には変数 a の値が渡されないのに対し、引数 x に 12 を代入する操作は変数 a に反映されます。
修飾子 inout は in と out 双方の性質を持ちます。最後に param と type の利用例を見てみましょう。
修飾子 param と type は、部分評価を助ける目的で利用します。部分評価とは、定数伝搬の一般化です。
proc foo ( param y : int ) {
const tuple : y * int ;
return tuple ;
}
上の foo 関数を foo(3) のように呼び出すと、(int, int, int) 型のタプルが生成されます。また、
proc bar ( type x , param y : int ) {
const tuple : y * x ;
return tuple ;
}
上の bar 関数を bar(real, 3) のように呼び出すと、(real, real, real) 型のタプルになります。
以上は、コンパイラの型付けを制御するサンプルですが、より汎用的な応用例は、7.13 節で解説します。
7.11
返り値の修飾子
関数の返り値の扱い方を指定するには、表 3 の修飾子を使います。
Table 3 返り値の修飾子の一覧
修飾子
var
意味
返り値は左辺値
const
返り値は動的定数
param
返り値は静的定数
type
返り値は型定数
このうち param と type については引数の修飾子と用途はほぼ同じでしょう。
15
proc nought () param return 0;
proc integer () type return int ;
一方、var を使うと興味深い挙動が見れます。具体例を見てみましょう。まず、
var a = (0 , 0 , 0 , 0 , 0);
proc A ( i : int ) var return a ( i );
上のようにタプルの変数 a と関数 A を定義します。そして、以下のように呼び出してみます。
writeln ( a );
A (1) = 1;
A (2) = 2;
A (3) = 3;
A (4) = 4;
A (5) = 5;
writeln ( a );
このプログラムを実行すると以下のように出力されるはずです。
(0 , 0 , 0 , 0 , 0)
(1 , 2 , 3 , 4 , 5)
関数 A の返り値があたかも代入式の左辺であるかのように動作するため、左辺値と呼ばれます。
7.12
関数呼び出しの条件
Chapel の関数は、where 節を用いることで呼び出される条件を厳しく設定することができます。
proc foo ( param x ) where x < 0 {
writeln ( " x is less than 0 " );
}
条件式にはコンパイル時に値が確定する式のみ利用できます。x < 0 が foo 関数が呼び出される際の
条件を指定する条件式です。この例では、以下のような関数呼び出しはコンパイルエラーになります。
foo (100);
where 節は Chapel のジェネリックプログラミングを支える重要なパーツです。例えば、
proc bar ( x ) where x . type == real {
writeln ( " x is real " );
}
proc bar ( x ) where x . type == imag {
writeln ( " x is imag " );
}
引数 x の型によって異なる bar 関数を呼び分けることができます。
16
7.13
部分評価
C++には強力なテンプレート機能があり、計算結果が定数になる計算はコンパイル時に実行できます。
例えば、以下に示すように fib 関数を定義すれば、フィボナッチ数の計算はコンパイル時に行われます。
template < int n > struct fib {
enum { value = fib <n -1 >:: value + fib <n -2 >:: value };
};
template < > struct fib <1 > {
enum { value = 1};
};
template < > struct fib <0 > {
enum { value = 0};
};
int fib3 = fib <3 >:: value ;
int fib4 = fib <4 >:: value ;
int fib5 = fib <5 >:: value ;
これは、低水準で具体的なプログラムを出力する、高水準で抽象的なプログラムの例になっています。
このようにプログラムを高位のプログラムで間接的に記述する流儀をメタプログラミングと呼びます。
ただ、C++のテンプレートは煩雑に過ぎます。同様のことは、Chapel でも where 節により実現します。
proc fib ( param n ) param where n >= 2 return fib (n -1) + fib (n -2);
proc fib ( param n ) param where n == 1 return 1;
proc fib ( param n ) param where n == 0 return 0;
param fib3 = fib (3);
param fib4 = fib (4);
param fib5 = fib (5);
静的な式はコンパイル時に評価され、定数に置き換えられることになっていますが、この定数折畳みは
関数呼び出しについても適用され、引数が静的な式で返り値も静的な式になる関数は、コンパイル時に
実行されるのです。通常の関数の形で自然に記述することができるのでスマートです。
8
イテレータ
8.1
イテレータの基本
Chapel では、イテレータと称する事実上のコルーチンを定義できます。コルーチンは処理を中断して
再開することができる関数です。試しに、呼び出すたびに整数を返すイテレータを定義してみましょう。
iter foo () {
yield 1;
yield 2;
yield 3;
}
17
返り値は return 文ではなく yield 文で返します。処理は前回の yield 文の直後から再開されます。
予約語 iter で宣言する以外は通常の関数と同じです。foo イテレータを for 文で利用してみましょう。
for i in foo () do writeln ( i );
変数 i に返り値 1,2,3 が順番に渡されます。レンジイテレータはリテラルで書くこともできます。
for i in 1..3 do writeln ( i );
プログラマが自らイテレータを実装する機会があるとすれば、既存のイテレータを組み合わせる必要が
生じた場合でしょう。例えば、木構造を再帰的に辿って値を回収するイテレータを実装してみましょう。
iter retrieve ( node : Node ): Node {
if node . hasChildren {
for val in retrieve ( node . child1 ) do yield val ;
for val in retrieve ( node . child2 ) do yield val ;
} else yield node . value ;
}
このように、自らを再帰的に呼び出すイテレータを実装することになります。
8.2
イテレータ型
紛らわしいことに、イテレータという語は、イテレータの役割を果たすコルーチン自体ではなく、その
コルーチンを保有する第一級オブジェクトを指す場合が多いでしょう。例えば 1..10 はイテレータと
呼ばれますが、あくまでレンジ型のオブジェクトに過ぎず、iter で宣言したコルーチンそのものでは
ありません。しかし、イテレータの役割を持つコルーチン these を実装しています。
iter range . these () yield numbers ;
コルーチン these には特別な意味があります。for 文は these を実装したいかなるオブジェクトをも
イテレータ型と見なすのです。自作データ型にイテレータの機能を持たせるには these を実装します。
9
クラス
9.1
クラスの基本
クラスは構造的なデータ型です。具体的には、自身の内部にフィールドと呼ばれる変数を宣言できます。
class Sample {
var x : int , y : int ;
var name : string ;
}
クラス型 Sample は int 型の変数 x,y と string 型の変数 name をフィールドに持っています。
var a : Sample = new Sample ();
a . name = " This is sample " ;
writeln ( a . name , a .x , a . y );
18
ドット演算子を用いることでフィールドにアクセスできます。フィールドの型には制限はありません。
class List {
var value : int ;
var next : List ;
}
従って上掲のように再帰的なクラス定義も可能です。これは、リスト構造をクラスで実装する例です。
9.2
動的なメモリ確保
クラスは動的なメモリ確保が行われるデータ型です。つまり、どの時点でメモリが割り当てられるかは
コンパイル時には確定されず、実行時に決定されます。メモリ確保は new 演算子によって行います。
new Sample ();
new 演算子はクラス型変数の実体となるメモリ領域を確保し、そのメモリ番地を返します。変数 a には
値そのものではなく、メモリ番地が格納されます。クラス型変数の実体はスタックではなく、ヒープと
呼ばれるメモリ領域に確保されます。スタックに配置されたデータは関数呼出しが終了すると自動的に
消去され、変数に割り当てられたメモリ領域が解放されますが、ヒープでは解放されません。
proc foo () {
var a = new Sample ();
return a ;
}
var b = foo ();
上のコードでは、変数 a に代入された実体は関数 foo が終了した後でも生きています。変数 a 自体は
関数の終了と同時にスタック上から消去されますが、変数が指し示したメモリ領域は消えないのです。
9.3
クラスのインスタンス
メモリ確保の観点からクラスの概念を解説しましたが、本来、クラスとは設計図であり、new 演算子に
よって生成されるメモリ領域は、設計図によって生成されたクラスの具体例であると理解してください。
class Sample {}
var a = new Sample ();
new 演算子によって生成された具体例をインスタンスと呼びます。
9.4
インスタンスの消去
インスタンスはスタック上に確保される変数とは異なり、ヒープ上に確保されるので、大量に生成して
消去することなく放置すればメモリを食い潰してしまいます。そこで、delete 文を使って消去します。
var a = new Sample ();
delete a ;
19
delete 文はクラスのインスタンスを消去する命令で、C 標準ライブラリの free 関数に相当します。
delete 文の実行後の変数 b は有効なインスタンスを参照していません。この状態を nil と呼びます。
nil はクラス型変数が有効なインスタンスを参照していないことを示す特別で唯一の値です。例えば、
クラス型変数の値はデフォルトで nil です。多くのプログラミング言語にはガベージコレクタ、即ち、
不要なインスタンスを自動的に消去する仕組みが搭載されていますが、Chapel は公式には未搭載です。
大規模並列環境でのガベージコレクタはノードを跨いだ参照の追跡が必要で技術的に困難があります。
9.5
クラスのメソッド
クラスにはフィールドだけでなく、メソッドと呼ばれる関数を内蔵することもできます。
class Point {
var x : real ;
var y : real ;
proc print () {
writeln (x , y );
}
}
クラス内の関数をメソッドと呼びます。ドット演算子を用いて外部から呼び出すことができます。
var p = new Point ();
p . print ();
ドット演算子はクラスの外側からフィールドやメソッドにアクセスする際に、インスタンスを指定する
ためのものです。クラス内で自分のフィールドやメソッドにアクセスする場合は不要です。メソッドは
クラス定義の外側に記述することも可能です。その場合は所属するクラスを明記する必要があります。
proc Point . print () {
writeln (x , y );
}
クラス内で自分を参照する際は予約語 this を使います。例えばフィールドへの代入を行うメソッドは
class Point {
var x : real ;
var y : real ;
proc setX ( x ) {
this . x = x ;
}
}
のように定義します。this を使わなければ x は引数の x として解釈されてしまいます。
9.6
コンストラクタ
インスタンスを生成する際には、暗黙的に初期化用のメソッドが呼び出されています。これをクラスの
コンストラクタと呼び、プログラマが明示的にコンストラクタを定義することも可能ですが、未定義の
場合はデフォルトのコンストラクタがコンパイラによって自動的に補足定義されます。
20
class Point {
var x : int ;
var y : int ;
proc Point ( x : int , y : int ) {
this . x = x ;
this . y = y ;
}
}
コンストラクタは通常のメソッドと同様に予約語 proc を用いて定義しますが、名前は必ずクラス名と
同じものを使用します。引数は自由に設定することができます。もしコンストラクタを定義しなかった
場合は、フィールドの初期値を引数に取るコンストラクタがコンパイラによって自動的に補足されます。
class Point {
var x : int = 0;
var y : int = 0;
}
var p1 = new Point ();
var p2 = new Point (1 , 2);
var p3 = new Point ( x = 1 , y = 2);
この場合、引数にはデフォルト値が設定され、変数宣言の初期化式の値がデフォルト値になります。
9.7
クラスの継承
ここまでは、クラスを単なるデータ構造として捉えていました。しかし、もっと面白い機能もあります。
class Foo {
proc foo () {
writeln ( " I am foo " );
}
}
Foo というクラスを定義しておきます。続いて Bar というクラスを定義します。
class Bar : Foo {
proc bar () {
writeln ( " I am bar " );
}
}
今までのサンプルにはない:Foo という記述がありますが、クラス Bar がクラス Foo を継承することを
意味します。これにより、クラス Foo のフィールドやメソッドがクラス Bar でも利用可能になります。
var b = new Bar ();
b . bar ();
b . foo ();
クラス Foo はクラス Bar の基底クラスと呼ばれ、クラス Bar はクラス Foo の派生クラスとなります。
21
9.8
メソッドの再定義
継承元クラスのメソッドと同名のメソッドを定義して上書きすることをオーバーライドと呼びます。
class Foo {
proc hoge () return " foo ! " ;
}
class Bar : Foo {
proc hoge () return " bar ! " ;
}
var b = new Bar ();
writeln ( b . hoge ());
実行してみると、foo!ではなく bar!と出力され、動作が変更されていることがわかります。
9.9
アクセサメソッド
Chapel では、フィールドアクセスは暗黙的な左辺値メソッドの呼び出しに変換されます。
class Language {
var name : string ;
}
上の Language クラスのフィールド name にアクセスするには、以下のように記述します。
var lang = new Language ();
writeln ( lang . name );
このプログラムはコンパイラによって自動的に下記のメソッドの呼び出しに変換されます。
proc Language . name var return name ;
フィールドと同名で、引数なしの左辺値関数です。このような関数をアクセサと呼び、コンパイル時に
自動的に捕捉されます。興味深いことに、アクセサを明示的に定義することで動作を変更できます。
proc Language . name var {
if name != " Scheme " {
name = " Scheme " ;
}
return name ;
}
上の例では、name メソッドを変更することで、フィールド name の値が常に Scheme になります。
9.10
ジェネリクス
クラスのフィールドには変数や動的定数だけでなく、静的定数や型定数も宣言することができます。
22
class Stack {
type eltType ;
}
上の例のように静的定数や型定数のフィールドを持つクラスではクラスの型の扱いに注意が必要です。
var a = new Stack ( eltType = uint );
var b = new Stack ( eltType = real );
a = b;
上のプログラムはコンパイルエラーになります。というのも変数 a と b は互いに異なる型の変数として
扱われるからです。実験してみましょう。Chapel では型の名前は typeToString 関数で取得します。
writeln ( typeToString ( a . type ));
writeln ( typeToString ( b . type ));
このプログラムを実行すると、以下のように出力されます。
Stack ( uint (64))
Stack ( real (64))
ここから、変数 a は Stack(uint(64)) 型、変数 b は Stack(real(64)) 型に型付けされている様子が
わかります。興味深いことに、型定数だけでなく、静的定数についても同様の挙動が確認できます。
class Student {
param age : int ;
}
var tom = new Student ( age = 12);
var ken = new Student ( age = 13);
writeln ( typeToString ( tom . type ));
writeln ( typeToString ( ken . type ));
Chapel ではクラスに静的定数や型定数のフィールドが宣言されている場合、いわゆる総称型としての
扱いを受けます。総称型の典型的な用途としては、リストや配列といったデータ構造に含まれる要素の
型を指定する際に役立つことが挙げられます。総称型は真新しい言語仕様ではありませんが、総称型に
対応した言語の大部分は Chapel で言う型定数による型の指定には対応してはいても、静的定数による
型の指定には対応していません。C++ のテンプレートにも似た強力なメタプログラミングが可能です。
10
レコード
10.1
レコードの基本
レコードは、メモリ確保が静的に行われるという違いを除いて、クラスと同じ機能を持つデータ型です。
record Sample {
var x : int , y : int ;
var name : string ;
}
23
予約語 record を使用する以外はクラスと同等で、フィールドやメソッドを定義することができます。
クラスのフィールドの型に制約がないのと同じように、レコードのフィールドの型に制約はありません。
record List {
var value : int ;
var next : List ;
}
ただし、上の List のように再帰的構造にすることはできません。後述するように、レコードは静的な
メモリ割り当てを行う型なので、再帰的構造では正常にコンパイラが動作せず、事実、異常終了します。
10.2
静的なメモリ確保
レコードは静的なメモリ管理を行うデータ型で、どの時点でメモリ領域を割り当てるかはコンパイラが
決定します。従って、クラスのように new 演算子でインスタンス化する必要も、delete 文で消去する
必要もありません。変数宣言と同時にインスタンス化されると見なして差し支えありません。この点で
扱いはプリミティブ型とほぼ同等です。しかし、フィールドの分だけ多くのメモリ領域を占有します。
10.3
レコード自身の参照
レコードは静的にメモリが確保されるデータ型であるため、クラスと異なる挙動が生じます。
record Record {
var value : int ;
}
上に定義したレコード Record の値を引数に取ってフィールドを書き換える関数 foo を定義します。
proc foo ( a : Record ) {
a . value = 123;
}
この foo 関数を呼び出す前後で実際にフィールドの値が書き変わるか確認してみます。
var b : Record ;
b . value = 321;
foo ( b );
writeln ( b . value );
上のサンプルを実行すると b.value の値は foo 関数呼び出し後も 321 のまま変化しません。なぜなら
レコード Record の実体はスタック上にあり、関数の引数に渡される際には参照ではなく、複製された
レコード値そのものが渡されるためです。Record をクラスとして定義した場合は引数にはポインタが
渡されるのでフィールドは更新されます。レコードは基本的に直接参照ですが this のみ間接参照です。
proc Record . setValue ( value ) {
this . value = value ;
}
理由は言うまでもなく、this が直接参照だと setValue が永久に value の値を更新できないからです。
24
11
モジュール
11.1
名前空間
関数や変数を宣言するには名前が必要です。しかし、もし互いに同じ名前を持つクラスや関数があれば
コンパイルエラーになるでしょう。頻繁に使用される名前は後から使えないのが普通で、不便に感じる
ことも多いでしょう。そこで、名前が有効となる範囲を名前空間として定義しておき、プログラム内を
別々の名前空間に分割することで衝突を回避します。名前空間を区切るには module 文を使います。
module Module1 {
const piyo = 1;
proc hoge () {
return " foo " ;
}
}
module Module2 {
const piyo = 2;
proc hoge () {
return " bar " ;
}
}
モジュール内にはクラスやレコード、関数や変数、定数などを含めることができます。
11.2
暗黙的なモジュール
どのモジュールにも属さない文がソースファイル内にある場合は、そのソースファイル自体が暗黙的な
モジュールになります。暗黙的なモジュールの名前はファイル名の拡張子.chpl を除いた文字列です。
11.3
入れ子のモジュール
モジュールは入れ子にすることができます。
module Module1 {
module Module2 {}
}
モジュールはレキシカルスコープを形成するので、内側のモジュール B は外側のモジュール A の関数や
変数にアクセスできます。反対に、外側から内側にアクセスするためにはドット演算子が必要です。
module Module1 {
module Module2 {
var x : int ;
}
}
writeln ( Module1 . Module2 . x );
25
use 宣言を使えば、ドット演算子を省略してモジュール内にアクセスすることも可能です。
use Module1 . Module2 ;
writeln ( x );
11.4
メイン関数
これまでのサンプルには一切登場しませんでしたが、実は、Chapel では C 言語や Java の main 関数に
相当する関数をモジュール内に定義することができます。引数はなく、返り値は int 型か void 型です。
module Foo {
proc main () {
writeln ( " Hello , World ! " );
}
}
プログラムが起動すると、main 関数が定義されたモジュールがまず初期化されます。モジュール内に
記述された文はモジュールの初期化時に実行されます。モジュールの依存関係に従って全モジュールが
初期化されると main 関数が実行され、main 関数の終了と同時にプログラムは終了します。例えば、
module Bar {
writeln ( " This is top level " );
proc main () {
writeln ( " This is main " );
}
}
上のプログラムを実行すると、以下のように出力されます。
This is top level
This is main
余談ですが、main 関数を省略しても、ここまでサンプルは正しく動作したはずです。実は main 関数を
省略した場合、空の main 関数が自動的に補われているのです。そして、トップレベルに記述した文が
モジュールの初期化処理として main 関数の前に実行されるため、見かけ上 main 関数を定義せずとも
プログラムが動いていたのです。main 関数は複数のモジュールにひとつずつ定義することもできます。
module Module1 {
proc main () {
writeln ( " This is Module1 " );
}
}
module Module2 {
proc main () {
writeln ( " This is Module2 " );
}
}
この場合は、どの main 関数でプログラムを起動するか、コンパイル時に指定する必要があります。
26
$ chpl modules . chpl -- main - module Module1
これで、Module1 の main 関数が起動時に呼び出されます。
11.5
モジュールの初期化順序
モジュールの初期化の順序は、モジュールの依存関係によって決定されます。
module Module1 {
use Module2 ;
writeln ( " This is Module1 initialization " );
proc main () {
writeln ( " This is main procedure " );
}
}
module Module2 {
writeln ( " This is Module2 initialization " );
}
上のプログラムを実行すると、以下のようにモジュールが順番に初期化される様子を観察できます。
This is Module2 initialization
This is Module1 initialization
This is main procedure
12
列挙型
列挙型は、元号や都道府県名、性別や職業など、何らかのカテゴリ集合を表す識別子の有限集合です。
enum GraduateFellow { Master , Doctor };
13
共用体
共用体はひとつのメモリ番地を複数の変数で共有することで不要なメモリ消費を抑えるデータ型です。
union
var
var
var
}
Foo {
x : uint ;
y : real ;
z : imag ;
フィールド x と y と z は同じメモリ番地に配置されます。使い方はレコードに似ています。
var foo : Foo ;
foo . x = 123;
foo . y = 1.3;
27
共用体はレコードと異なり、意味のある値を格納しているフィールドは常にいずれかひとつだけです。
どのフィールドが有意であるかは実行時の文脈によって変化します。Chapel の共用体の場合、最後に
値が代入されたフィールドのみが有意です。従って、x に整数値を代入した直後は x のみが有意ですが
y に実数値を代入すると x は無効になります。無効なフィールドを参照するとエラーが発生します。
writeln ( foo . x ); // halt
共用体のどのフィールドが有意であるかを調べるには select 文を使います。現時点では未実装です。
type select
when uint
when real
when imag
}
foo {
do writeln ( foo . x );
do writeln ( foo . y );
do writeln ( foo . z );
14
タプル
14.1
タプルの基本
タプルとは、複数の値を並べた組を表すデータ型です。実装上の実体はレコード型_tuple です。
(12 , 13 , 14.0 , true , " tuple " )
上記のようにカンマ区切りで値を並べて括弧で閉じることでタプルになります。配列に似ていますが、
要素の型を揃える必要がない点で、配列とは一線を画します。タプルの個別の要素にアクセスするには、
const boys = ( " Tom " , " Ken " , " Bob " );
const ken = boys (2);
1 から始まるインデックス番号を添えてアクセスします。タプルの型を表現するには、
( int , int , int )
カンマ区切りで型を並べて括弧で括ります。また、構成要素の型が揃っている場合は、
3 * int // ( int , int , int )
個数と型の掛け算でタプル型を表現できます。この例は (int, int, int) と等価です。
14.2
タプルの要素
タプルはイテレータ these を実装しているので for 文に渡すことができます。
for boy in ( " Tom " , " Ken " , " Bob " ) do writeln ( a );
ただし、要素の型が揃っている場合に限られます。例えば、以下の例はエラーになります。
for a in ( " 1 " , 2 , 3.0) do writeln ( a );
タプルの要素ひとつひとつにアクセスする際にはインデックスを括弧で括って指定します。
28
const boys = ( " Tom " , " Ken " , " Bob " );
const ken = boys (2);
興味深いことに boys(2) という式は左辺値関数 this の暗黙的な呼び出しになっています。
proc _tuple . this ( i : integral ) ref {
return __primitive ( " get svec member " , this , i );
}
Chapel では、this メソッドを定義したデータ型はファンクタとして機能します。例えば、
class Add {
proc this ( a : int , b : int ) return a + b ;
}
上掲の Add という加算器を定義します。そして、定数 add に代入して引数を与えます。
const add = new Add ();
writeln ( add (123 , 45));
上のプログラムを実行すると、123 + 45 が評価されて 168 と出力されます。
14.3
タプルによる変数宣言
興味深いことに、変数宣言はあたかもタプルのように記述することができます。
const (a , b ): ( string , int );
変数名がタプルになっていますが、正しいプログラムです。a と b を別々に変数宣言するのと同等です。
const a : string ;
const b : int ;
複数の変数への代入をタプルを用いてまとめることもできます。
(a , b ) = ( " John " , 24)
これは他の言語の流儀では多重代入やアンパック代入などと呼ばれる機能です。
15
レンジ
レンジは数直線上の範囲を表現するデータ型です。実装上の実体はレコード型 range です。
const from1to5 = 1..5;
上のように.. の左右に最小値と最大値を並べます。どちらかを省略すると無限区間になります。
const from1toInf = 1..;
const fromInfTo5 = ..5;
レンジの長さは#演算子で、周期は by 演算子で、0 近傍の値は align 演算子で指定します。
29
const from10to30 = 10..30 by -7 align 13 # 3;
レンジはイテレータ these を実装しているので for 文に渡すことができます。
for i in 1..5 do writeln ( i );
レンジの長さは size メソッドで取得できます。レンジ型は 3 個の型定数・静的定数を引数に取ります。
range ( type idxType , stridable : bool , boundedType : BoundedRangeType )
idxType はインデックスの型でデフォルトは int です。stridable は不連続性を表し true の場合、
インデックスが不連続です。デフォルト値は false で by 演算子を使用した場合のみ true になります。
writeln ((1..3 by 2). stridable );
boundedType は有界性を指定します。BoundedRangeType は列挙型で、表 4 に示す列挙子を持ちます。
Table 4 BoundedRangeType の列挙子
列挙子
意味
bounded
最小値と最大値の両方とも有限値の有限区間
boundedLow
最小値が有限値で最大値が無限大の半開区間
boundedHigh
最小値が無限小で最大値が有限値の半開区間
boundedNone
最小値と最大値の両方とも無限値の無限区間
デフォルトは bounded です。Chapel には型推論があるので、さほど細かく意識する必要はありません。
16
ドメイン
ドメインは空間の広がりを表現するデータ型です。実装上の実体はレコード型_domain です。
const rectangular = {1..20 , 1..30};
const associative = { " Tom " , " Ken " };
多次元の矩形領域を表す矩形ドメイン型と、連想配列の定義域を表す連想ドメイン型があります。
16.1
矩形ドメイン
矩形ドメインは、多次元の矩形領域を表現します。各軸の区間をカンマ区切りで並べて括弧で括ります。
const rectangular = {0..10 , -20..20}
矩形ドメインはイテレータ these を実装しているため、for 文に渡すことができます。
for (x , y , z ) in {0..1 , 0..1 , 0..1} do writeln (( x , y , z ));
上のサンプルコードを実行すると、以下のように出力されます。
30
(0 ,
(0 ,
(0 ,
(0 ,
(1 ,
(1 ,
(1 ,
(1 ,
0,
0,
1,
1,
0,
0,
1,
1,
0)
1)
0)
1)
0)
1)
0)
1)
矩形ドメインの型は 3 個の型定数・静的定数を引数に取ります。
domain ( rank : int , type idxType , stridable : bool )
rank は座標軸の個数を指定します。idxType と stridable はレンジ型が取る同名の引数と同じです。
idxType のデフォルト値は int、stridable のデフォルト値は false です。不要なら省略もできます。
16.2
連想ドメイン
連想ドメインは連想配列の定義域を表現します。要素をカンマ区切りで並べて括弧で括ります。
const associative = { " foo " , " bar " }
連想ドメインもイテレータ these を実装しているため、for 文に渡すことができます。
for boy in { " Tom " , " Ken " , " Bob " } do writeln ( boy );
連想ドメイン型は集合に含まれる値の型を引数に取ります。文字列集合なら以下のように記述します。
domain ( idxType = string )
16.3
レンジのタプルとの相互変換
矩形ドメインをレンジのタプルに変換するには、dims メソッドを用います。
const dom = {1..10 , 1..10};
const rangeTuple = dom . dims ();
writeln ( rangeTuple ); // (1..10 , 1..10)
各次元軸のレンジを個別に取り出すには、dim メソッドを用います。
const dom = {1..10 , 1..10};
const range1 = dom . dim (1);
const range2 = dom . dim (2);
反対に、範囲のタプルから矩形ドメインを作成するには、setIndices メソッドを用います。
const dom = {1..10 , 1..10};
dom . setIndices ((1..100 , 1..200));
writeln ( dom ); // {1..100 , 1..200}
31
17
配列
Chapel の配列は定義域から値域への写像の集合です。実装上の実体はレコード型_array です。
var A : [{1..10 , 1..10}] real ;
var B : [{ ’ foo ’ , ’ bar ’ }] real ;
矩形ドメインを定義域に持つ配列は矩形配列、連想ドメインを定義域に持つ配列は連想配列です。
17.1
配列の基本
配列はカンマ区切りのリテラルで表現することができます。
const rectangular = [1 , 2 , 3 , 4 , 5 , 6 , 7 , 8];
const associative = [1 = > " one " , 2 = > " two " ];
配列の要素にアクセスするには括弧で括ったインデックスを添えます。
const one = rectangular (1);
const two = associative (2);
配列型はドメインを角括弧で括った後に値域の要素の型を記入することで表記します。
var A : [1..10 , 1..10] uint ;
var B : [ ’ Tom ’ , ’ Ken ’] real ;
ドメインをリテラルで直に指定する場合はドメインの括弧を省略することができます。
17.2
配列の要素
配列はイテレータ these を実装しているので、for 文に渡すことができます。
for boy in [ ’ Tom ’ , ’ Ken ’ , ’ Bob ’] do writlen ( boy );
配列の these の実装は左辺値関数になっているため、要素を書き換えることもできます。
for value in A do value *= 2;
配列の要素ひとつひとつにアクセスする際にはインデックスを括弧で括って指定します。
A [1 , 2] = 1.2;
A (3 , 4) = 3.4;
インデックスにはタプルを使うこともできます。
A ((5 , 6)) = 5.6;
この A(3, 4) や A((5, 6)) といった式は左辺値関数 this の暗黙的な呼び出しになっています。
32
proc _array . this ( i : rank * idxType ) ref {
if isRectangularArr ( this ) then
return _value . dsiAccess ( i );
else
return _value . dsiAccess ( i (1));
}
配列の this メソッドは引数の型に合わせてオーバーロードされており、ドメインを引数に取るものも
用意されています。面白いことに、引数にドメインを指定すると部分配列を取得することができます。
var A : [1..5 , 1..5] real ;
for (i , j ) in {1..5 , 1..5} {
A (i , j ) = i + ( j / 10.0);
}
var B = A (1..3 , 1..3);
writeln ( B );
このプログラムを実行すると、以下のように出力されます。
1.1 1.2 1.3
2.1 2.2 2.3
3.1 3.2 3.3
配列 B が配列 A の部分配列になっていることがわかります。
17.3
配列のポインタ渡し
配列の実体はレコードなので、関数の引数にする際には複製が渡されるのが自然です。しかし、配列の
用途から考えるとコストが高すぎるため、配列に限っては特別にポインタ渡しになります。ドメインも
同様にポインタ渡しです。ただし、配列を変数に代入する際にはポインタ渡しではありません。
var A : [1..3] real ;
var B = A ;
for i in A . domain {
A ( i ) = i * 2.0;
}
writeln ( " A = " , A );
writeln ( " B = " , B );
上のプログラムを実行すると、以下のように出力されます。
A = 2.0 4.0 6.0
B = 0.0 0.0 0.0
代入はあくまでも値渡しなのです。万能ではありませんが、=>演算子を使うことで回避できます。
const B = > A ;
この=>演算子は配列のエイリアスを作成する演算子です。部分配列のエイリアスも作成できます。
33
var A : [1..10] int ;
var B = > A [2..9];
for i in B . domain {
B(i) = i;
}
writeln ( " A = " , A );
実行すると、配列 A の部分配列 B に対する操作が A にもバックフィットされることがわかります。
A = 0 2 3 4 5 6 7 8 9 0
17.4
配列とタプルの使い分け
配列は定義域を表現するためにドメインを指定する必要がありますが、タプルでは要素数を示す情報は
タプル型そのものに含まれています。というのも、タプルは単に関連性のあるデータをまとめてペアに
しただけのデータ型であり、空間に分布するデータを表現する配列とは用途が異なるためです。
proc foo ( a : int ) return (a , a + 1);
上のサンプルコードのように複数の値を返す関数を定義したい場合などにタプルは威力を発揮します。
不用意に配列を使用することは計算効率を低下させ、まさに鶏を割くのに牛刀を用いるようなものです。
18
高速計算入門
18.1
並行処理
並列処理とマルチスレッドの混同はしばしば散見されます。しかし、マルチスレッド自体は並行処理に
過ぎません。並行処理とは複数の処理を同時進行で進めることを指します。複数の命令がマルチコアで
実行されることを必ずしも意味しません。グラフィカルなソフトウェアでは、重い処理を実行している
最中もマウスやキーボードの入力に応答できる状況を維持する必要があります。マルチスレッドにより
時分割で処理を行うのはこのためです。マルチスレッドは処理速度の増強を必ずしも目的としません。
18.2
並列処理
並列処理は複数の命令がマルチコアで実行されることを意味します。あるいは、ひとつの命令で複数の
データに同じ演算を実行する SIMD 命令も並列処理の範疇です。前者は、並行実行可能な処理をコアに
分配するスケジューラにより実現します。後者は、同時に処理可能なデータを配列にまとめて配列ごと
SIMD 命令に渡すことで実現します。いずれにせよ低水準な並列処理の詳細を明示的に記述する場面は
少数です。むしろ、並行実行可能な部分を実行環境に教える構文で並列化を支援するのが一般的です。
18.3
逐次処理
並列処理の基本的な方針は逐次処理のプログラムの高速化とほぼ同じです。並列処理はあくまで個々の
コアを束ねて高速化するものに過ぎないため、コア単位での処理速度を犠牲にしてまで並列化するのは
本末転倒です。コア単位の処理速度の増強のために必要な工夫とは、典型的にはメモリ効率の改善です。
34
18.4
記憶階層
Fig. 1 multi processor and memory hierarchy.
主記憶はプロセッサに比べ鈍足なので、効率を改善するためにキャッシュと呼ばれる小容量だが高速の
記憶装置を挟むことで、主記憶に毎回アクセスしないで済むように工夫されています。実際にはさらに
キャッシュを補佐するキャッシュが用意されていて、L1・L2・L3 と呼ばれるキャッシュの階層構造を
構成します。プロセッサは L1(L1d)、L2、L3、主記憶の順番に検索して、目的のデータを発見します。
18.5
参照局所性
高水準言語ではメモリアクセスのように低水準な操作はコンパイラが自動的に最適化します。そのため
プログラマが詳細に調整することは困難です。しかし、コーディング上の工夫で性能を劇的に改善する
余地はあります。それは、参照局所性と呼ばれる性質による工夫です。通常、ある期間にアクセスする
メモリ番地は狭い範囲に集中する傾向にあります。これを参照局所性と呼びます。配列を処理する例を
考えれば理解しやすいでしょう。プロセッサはメモリにアクセスする際、目的のデータがキャッシュに
複製済みかどうかを確認します。複製済みならそのデータを使い、複製済みでなければ改めて主記憶に
問い合わせます。このとき、目的のデータだけでなく、近傍のメモリ番地もまとめて一斉に主記憶から
キャッシュに読み込みます。これは参照局所性を期待した回路設計上の工夫で、キャッシュヒット率の
改善を狙っています。参照局所性は共有メモリ環境や分散共有メモリ環境における並列計算でも重要な
意味を持ちます。これらの並列環境では多数のプロセッサがローカルな主記憶を有し、バスや通信網を
介してグローバルに共有します。プロセッサ間の通信はメモリを介して実現しますが、物理的に離れた
プロセッサの主記憶を参照する際には、バスの転送速度が律速要因になるため、参照局所性が重要です。
18.6
タイリング
参照局所性を意識したコーディングについて C 言語で行列積を計算するサンプルで解説しましょう。
for ( int i = 0; i < N ; i ++)
for ( int j = 0; j < N ; j ++)
for ( int k = 0; k < N ; k ++)
C [ i ][ j ] += A [ i ][ k ] * B [ k ][ j ];
35
行列積の定義通りの実装ですが、参照局所性が良くないことに気付きましたか。C 言語の配列は単なる
ポインタ演算に過ぎず B[k][j] は*(B + k * N + j) の糖衣構文です。従って B のメモリアクセスが
不連続になります。そのためキャッシュヒット率が低下します。配列の大きさによっては主記憶を常に
参照する可能性さえあり、致命的な律速を招く要因となります。対策としては、行列の転置が有効です。
C [ i ][ j ] += A [ i ][ k ] * B [ j ][ k ];
しかし、この方法がいつでも使えるとは限らないため、タイリングと呼ばれる手法が編み出されました。
for ( int I = 0; I < N ; I += BLOCK )
for ( int J = 0; J < N ; J += BLOCK )
for ( int K = 0; K < N ; K += BLOCK )
for ( int i = I ; i < I + BLOCK ; i ++)
for ( int j = J ; j < J + BLOCK ; j ++)
for ( int k = K ; k < K + BLOCK ; k ++)
C [ i ][ j ] += A [ i ][ k ] * B [ k ][ j ];
行列積を小さな部分行列の積に分解してブロック毎に処理することでキャッシュ効率を高めます。この
タイリングの考え方は並列処理と親和性が高いことに気付くことでしょう。各ブロックをプロセッサに
ひとつずつ割り当てることにより、分割統治式に行列積を並列計算することができます。何か革新的な
アイデアがあるのでもない限り、並列化とは、逐次処理をうまく設計した上で、並列処理できる場所を
探す作業になります。その際には、並列処理が不可能でどうしても逐次処理せざるを得ない場所が残る
ことがあります。例えば、単純なマージソートの並列化ではマージ部分はどうしても逐次実行せざるを
得ません。従って、並列処理の高効率化ではクリティカルパスを念頭に置いた改良が必要になります。
18.7
タスクの並列性
自宅を出発して肉屋と魚屋に買い物に行く場合、移動時間を考えれば、仕事を両方同時にこなした方が
効率的です。加えて、数人で手分けをして買い物できるなら、単位時間あたりにこなせる仕事が増えて
効率的です。これがタスク並列化の基本的な考え方です。肉屋と魚屋の買い物が同時に完了する確率は
低いので先に買い物を終えた方が他方を待つことになります。もちろん合流せずにばらばらに家に帰る
こともできますが、タクシーで帰るならなるべく待ち合わせした方が良いでしょう。このように同時に
遂行する必要があり、かつ並列実行が可能な仕事は、分岐合流モデルでの並列化を目指します。ただし
以上は肉屋と魚屋どちらの買い物を先に済ませても構わないという前提での話です。この場合、双方の
タスクには依存関係がありません。しかし、仮に財布の中身が万札だけで、しかも魚屋の主人が万札を
喜ばないなら、先に肉屋で崩すべきです。タスクに依存関係があると並列実行は大いに困難になります。
18.8
データの並列性
行列の和を求める例で考えてみましょう。行列の和は部分行列に分解して並列計算しても全体としての
計算結果は部分行列に分解せずに愚直に逐次計算で求めた結果と等しくなります。このようにデータと
それに対するタスクが分割統治可能である場合、そのような性質をデータ並列性ないしループ並列性と
呼びます。データ並列性は最終的にタスク並列性に帰結するので、両者の差は並列化に対する立脚点の
差異に過ぎません。むしろ、データをどのような形に分割してタスク並列化するかが重要になります。
例えば、行列積の場合は、キャッシュに収まる程度の面積の正方形に分割することが望ましいでしょう。
正方形ならば、面積辺りの時間計算量に対して空間計算量が最小になり、キャッシュ効率が改善します。
36
19
タスク並列処理
19.1
タスクの分岐合流
begin 文は、指定された文を実行するタスクを分岐生成します。
begin writeln ( " I am parallel task " );
分岐したタスクを合流させるには、sync 文を使います。sync 文は begin 文と組み合わせて用います。
sync {
begin writeln ( " parallel
begin writeln ( " parallel
begin writeln ( " parallel
}
writeln ( " task 1 , 2 , 3 are
task 1 " );
task 2 " );
task 3 " );
finished " );
上のサンプルを実行すると、全ての writeln 関数の並行実行が完了するまで sync 文内で待機します。
19.2
構造的な並列構文
cobegin 文は並列処理を記述するブロック文です。
cobegin {
writeln ( " parallel task 1 " );
writeln ( " parallel task 2 " );
writeln ( " parallel task 3 " );
}
cobegin 文は begin・sync 文の組み合わせと等価です。むしろ通常は cobegin 文だけで事足ります。
sync 文は、cobegin 文では表現しきれないような、非構造的なタスクの分岐合流に威力を発揮します。
proc showTreeValues ( node : Node ) {
if node . hasChildren {
begin showTreeValues ( node . child1 );
begin showTreeValues ( node . child2 );
} else writeln ( node . value );
}
sync showTreeValues ( node );
上のサンプルでは、begin 文を通じて関数を再帰呼び出しすることによりタスク並列化を行いますが、
関数の内部では一切の待ち合わせを行いません。代わりに最初の関数呼び出しを行っている部分で、
sync 文によりタスクを合流します。ところで、cobegin 文内に変数代入がある場合は注意が必要です。
cobegin with ( ref a , ref b ) {
a = funcA ();
b = funcB ();
}
上のサンプルのように、変数名を with 節で指定する必要があります。
37
19.3
並列ループ構文
coforall 文は for 文のイテレーションを各コアに割り当てて並列処理する構文です。
coforall i in 0..100 do writeln ( " my number is " , i );
実のところ coforall 文は以下のようなタスク並列構文の糖衣構文として動作します。
sync for i in 0..100 do begin writeln ( " my number is " , i );
19.4
不可分演算構文
atomic 文は、その文が他のプロセッサから見て不可分に実行されることを保証します。
atomic a += 1;
上のサンプルでは、変数 a への足し算の最中に他のプロセッサから a が参照される危険を排除します。
19.5
逐次実行の強制
各プロセッサが処理するタスクはスケジューラにより自動的に管理されますが、タスクの粒度が過度に
細かい場合、スケジューラそのもののオーバーヘッドが無視できなくなります。従って、分割統治法の
末端部では、それ以上の並列タスクの生成を抑制し、逐次処理を強制することが極めて重要になります。
serial isSerial do begin writeln ( " executed " );
serial 文は条件式が true の場合に do 節内の並列タスク生成を禁止し、その代わりに逐次実行します。
20
データ並列処理
20.1
並列ループ構文
forall 文は coforall 文と同様に for 文を並列処理する文です。
forall i in 1..100 do writeln ( " my number is " , i );
coforall 文がイテレーション毎に個別にタスクを生成分岐して並列処理するのに対し、forall 文は
イテレーション空間を部分空間に分割して各プロセッサに分配することで並列処理します。部分空間に
分割する際には並列化されますが、部分空間内の処理は逐次実行です。4 コアの場合は下記と同等です。
coforall coreId in 1..4 {
const idx1 = 25 * coreId - 24;
const idx2 = 25 * coreId ;
for i in idx1 .. idx2 do writeln ( " my number is " , i );
}
スケジューラそのものに少なからずオーバーヘッドが存在するため、細粒度の処理を行わせる場合は、
coforall 文よりも forall 文が有利です。特に、SIMD 命令を利用した最適化と併用したい場合には、
coforall 文は必ずしも適切な選択肢とは言えません。coforall 文は疎粒度の並列化に適しています。
38
20.2
並列イテレータ
厳密に言えば、単に細粒度の並列化に適した for 文という表現では、forall 文の説明として不足です。
forall 文とは、イテレーションの分割方法を自由に定義できる、洗練された並列ループ構文なのです。
coforall 文は、こうした特徴を持ちません。例えば、以下の for 文を並列化する場合を考えてみます。
for i in foo (1..100) do writeln ( i );
ただし、foo イテレータは以下のように定義します。
iter foo ( rng : range ( int )) {
for i in rng do yield i ;
}
coforall 文の場合、for を coforall に置き換えるだけで、並列処理することができます。
coforall i in foo (1..100) do writeln ( i );
しかし、forall 文の場合はコンパイルエラーになります。実は、forall 文は coforall 文と異なり、
並列化に関する、全ての判断をイテレータの裁量に委ねており、単体では並列化機能を持たないのです。
foo イテレータはリーダー・フォロワーの 2 種類のイテレータをオーバーロードする必要があります。
リーダーイテレータは、イテレーション空間を分割して、各プロセッサに割り当てる処理を実装します。
iter foo ( param tag , rng ): range ( int ) where tag == iterKind . leader {
if rng . size > 16 {
const mid = ( rng . high + rng . low ) / 2;
const ( rng1 , rng2 ) = ( rng (.. mid ) , rng ( mid +1..));
cobegin {
for i in foo ( iterKind . leader , rng1 ) do yield i ;
for i in foo ( iterKind . leader , rng2 ) do yield i ;
}
} else yield rng ;
}
上のリーダーイテレータの実装例は、レンジを再帰的に等分しつつ、cobegin 文で並列化しています。
分割統治が深くなり、レンジの長さが十分に短くなった場合は、レンジを分割せずにそのまま返します。
返されたレンジは、forall 文に渡されて、厳密ではありませんが、以下の仕組みで逐次処理されます。
for subrange in foo ( iterKind . leader , 1..100) {
for i in foo ( iterKind . follower , 1..100 , subrange ) do writeln ( i );
}
フォロワーイテレータはタスク並列化された分割統治の末端部での逐次処理を担当します。
iter foo ( param tag , rng , followThis ) where tag == iterKind . follower {
for i in followThis do yield i ;
}
以上をオーバーロードすることで、foo イテレータを forall 文で使えるようになります。
39
20.3
リダクション演算
足し算や掛け算のように、多数の値を集めて少数の値に変換する操作をリダクション演算と呼びます。
リダクション演算を並列化する場合、途中結果を読み込んで演算し、書き戻す処理が並行実行されます。
この時、読み込みと書き込みのタイミングが前後して、古い途中結果に対して演算する危険が生じます。
対策としては、セマフォやミューテックスなどが有効ですが、専用の演算子を利用する方法も便利です。
const sum = + reduce (1..1000);
reduce 演算子は右のイテレータに対して、左の演算子を用いて、リダクション演算を並列実行します。
演算子は + * && || & | ^ min max minloc maxloc が使えます。min max は最小値・最大値です。
minloc と maxloc は最小値・最大値の場所を求める演算子ですが、下記のように入出力がタプルです。
var ( value , idx ) = minloc reduce zip (A , A . domain );
zip はふたつのイテレータを結合します。例えば zip(1..2, 3..4) は (1, 3), (2, 4) を返します。
20.4
スキャン演算
スキャン演算はリダクション演算に似ていますが、途中結果が順番に格納されたイテレータを返します。
for sum in + scan (1..100) do writeln ( sum );
21
タスク並列処理系
21.1
スケジューラの概念
並列処理を行うためには、分岐したタスクを各プロセッサに割り当てて実行させる仕組みが必要です。
スケジューラは、各プロセッサを監視して、タスクがないプロセッサに自動的にタスクを割り当てます。
Fig. 2 に示すように、予めタスクを細粒度に分割し、FIFO に取り出して割り当てる方式が一般的です。
Fig. 2 FIFO scheduler.
例えば、coforall 文の場合は、毎回のイテレーションを task**として FIFO に割り当てて行きます。
この方式は単純ですが、任意の入れ子構造を有するアルゴリズム、殊に分割統治法の並列化は苦手です。
他方、ロードインバランスには頑健に対処可能ですが、タスク分割の粒度とのトレードオフが生じます。
そこで Chapel では、Fig. 3 に示すような分割統治型のスケジューラにより粒度の自動調整を行います。
40
Fig. 3 work stealing scheduler.
分割統治法ではタスクの粒度が再帰的に小さくなり、末端では参照データがキャッシュに収まります。
この性質を利用して、最初は大きな塊でプロセッサに分配しておき、後で必要に応じて再分配します。
ロードインバランスが生じない限り負荷の再分配は不要で、オーバーヘッドは効果的に抑制されます。
負荷を再分配する際は、最も負荷の重い処理を行っているプロセッサを選んで、タスクを回収します。
ただ、負荷の重さを有限時間で見積もる方法は自明ではないため、実装上は相手を無作為に選びます。
分割統治アルゴリズムの動作は深さ優先であり、タスクは浅い順に分岐してスタックに格納されます。
タスクを生成したプロセッサは、スタックに格納したタスクを深い順に取り出して、逐次実行します。
ただし、タスクを再分配する時のみ、なるべく大きな塊となるように、タスクを浅い順に取り出します。
21.2
スケジューラの再現
Fig. 3 に示した分割統治型のスケジューラに対する理解を深めるため、D 言語で自作してみましょう。
import
import
import
import
import
core . sync . mutex ;
std . array ;
std . parallelism ;
std . random ;
std . range ;
まず、各プロセッサに一意に割り振られた ID を coreId としてスレッドローカルに変数宣言します。
private uint coreId ;
public uint getCoreId () {
return coreId ;
}
続いて、本スケジューラの本体となる Trident クラスを定義します。
public final class Trident ( Ret , Args ...) {
alias Ret delegate ( Args ) Func ;
private shared Deque [] stacks ;
41
Ret と Args はテンプレート引数で、分割統治を行う再帰関数の返り値と可変長引数の型を表現します。
スケジューラはプロセッサ毎にタスクを保管するスタックを持ちますが、stacks がそれに該当します。
this ( uint numCores = totalCPUs ) {
foreach ( id ; 0.. numCores ) {
stacks ~= cast ( shared ) new Deque ;
}
}
配列 stacks には、スタックを表す Deque のインスタンスが、論理プロセッサの数だけ格納されます。
配列 stacks は、他のプロセッサからもアクセスされるので、shared 変数で宣言する必要があります。
shared 変数はしばしば明示的なキャストを要し不便なので、以下に示す stack メソッドを定義します。
auto stack ( uint id = coreId ) {
return cast ( Deque ) stacks [ id ];
}
ついでに、スケジューラが管理する論理プロセッサ数を返す numCores メソッドも定義しておきます。
uint numCores () {
return cast ( uint ) stacks . length ;
}
次に、Task クラスを定義します。Trident の内部クラスで、関数と引数・返り値を格納します。
public static final class Task {
private bool done ;
private Func func ;
private Args args ;
private Ret value ;
this ( Func func , Args args ) {
this . func = func ;
this . args = args ;
}
done はタスクの実行が完了したことを表現するための変数で、初期値は false です。
public bool isDone () {
return done ;
}
invoke メソッドは関数 func を呼び出して、フィールド done に true を代入します。
public void invoke () {
value = func ( args );
done = true ;
}
関数 func の返り値は value に格納されます。返り値は result メソッドで取り出します。
public auto result () {
return value ;
}
} // end of class Task
42
続いて、Task を格納するためのスタックを Deque クラスとして Trident クラス内に定義します。
private static final class Deque {
private Task [] data ;
private Mutex mutex ;
this () {
mutex = new Mutex ;
}
スタックの本尊は動的配列 data です。add メソッドで Task を配列 data の末尾に追加します。
public Task add ( Task task ) {
synchronized ( mutex ) {
data ~= task ;
return task ;
}
}
スタックへのアクセスはプロセッサ間で競合が発生する危険があるため、Mutex を用いて回避します。
逆に言えば、Mutex がボトルネックになるので、過度に細粒度なタスク生成をすべきではありません。
次に、プロセッサが自身のスタックから Task を新しい順に取り出すための pop メソッドを定義します。
public Task pop () {
synchronized ( mutex ) {
if (! data . empty ) {
Task task = data . back ;
data . popBack ;
return task ;
} else return null ;
}
}
アイドル状態のプロセッサが他のプロセッサの Task を取り出すための poll メソッドも定義します。
public Task poll () {
synchronized ( mutex ) {
if (! data . empty ) {
Task task = data . front ;
data . popFront ;
return task ;
} else return null ;
}
}
} // end of class Deque
以上で Task と Deque の実装が完了したので、スケジューラの最重要部を実装する準備が整いました。
fork メソッドは再帰関数 func とその引数 args の組を用いて Task を生成し、スタックに格納します。
public auto fork ( Func func , Args args ) {
return stack . add ( new Task ( func , args ));
}
対する join メソッドは Task の実行が完了するまで待ち合わせる関数で、タスクの合流を実現します。
43
public auto join ( Task target ) {
while (! target . isDone ) {
if (! local ) steal ;
}
return target . result ;
}
待機している間は何もしないのではなく、他に未処理のタスクがある場合には、先にそれを実行します。
join メソッドで登場する local メソッドは、自分のスタックにタスクがある場合に、逐次実行します。
public bool local () {
auto task = stack ( coreId ). pop ;
if ( task ! is null ) task . invoke ;
return task ! is null ;
}
同じく join メソッドで登場する steal メソッドは、無作為に選んだプロセッサからタスクを奪います。
public void steal ( uint victim ) {
auto task = stack ( victim ). poll ;
if ( task ! is null ) task . invoke ;
}
最後に、スケジューラを起動するエントリーポイントとなる start メソッドを定義します。
public Ret start ( Func func , Args args ) {
Task root = fork ( func , args );
auto coreIds = iota (1 , numCores , 1);
foreach ( cpu ; parallel ( coreIds , 1)) {
coreId = cpu ;
join ( root );
}
return root . result ;
}
} // end of class Trident
引数に渡される関数 func と args の組はスケジューラが掌握する分割統治の木構造の根に相当します。
最初の Task を変数 root に代入した後、プロセッサ数だけスレッドを生成し、join に後を委ねます。
以上でスケジューラが完成しました。動作確認のため、フィボナッチ数の計算手順を並列化してみます。
void main () {
auto sched = new Trident !( int , int );
int fibonacci ( int n ) {
if ( n > 1) {
auto th1 = sched . fork (& fibonacci , n - 1);
auto th2 = sched . fork (& fibonacci , n - 2);
return sched . join ( th1 ) + sched . join ( th2 );
} else return 1;
}
writeln ( sched . start (& fibonacci , 10));
}
fork 関数と join 関数の機能は、Chapel の begin 文と sync 文の機能に相当します。
44

Download Report