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

うさぎさんでもわかる並列言語 Chapel
Tutorial: Parallel Programming Language Chapel
無線部開発班
2015 年 3 月 4 日
1
introduction
Chapel*1 は PGAS により共有メモリから分散メモリまでスケーラブルに扱える高生産性並列言語です。
2
setup
インストール
2.1
Cray 社が公開している最新版を入手して、tar ファイルを展開します。
$tar xvzf chapel -1.10.0. tar . gz
タスク並列処理系に MassiveThreads を利用するように環境変数を設定します。
$export CHPL_TASKS = massivethreads
README の説明に従って、make コマンドでビルドします。
$make
コンパイラをシェルから叩けるように設定します。bash の場合は.bashrc に以下の数行を追記します。
cd ~/ chapel -1.10.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 オプションを付けることで最適化が有効になります。
$chpl -o foo foo . chpl -- fast
プログラムの FLOPS 値が異常に低いと思われる場合は、試してみる価値があります。
*1
http://chapel.cray.com
2
3
3.1
lexical structure
コメント
コメントの書き方は C++ や Java と同じです。
// 1 - line comments
/*
multiline comments
or block comments
*/
3.2
空白文字
半角空白、水平タブ、改行 (LF)、キャリッジリターン (CR) は区切り文字として扱われます。
3.3
トークン
識別子は半角英字か半角アンダースコアで始まる文字列で、2 文字目以降は半角数字と半角ドル記号も
使用できます。大文字と小文字は区別されます。
4
4.1
expressions
型システム
Chapel は強い静的型付け言語で、式の型はコンパイル時に決定されます。データ型の中でも予め言語
仕様で定義されている型をプリミティブ型と呼び、有意な値がないことを表現する void 型や真偽値を
表現する bool 型、符号付き整数値を表現する int 型と符号なし整数値を表現する uint 型、実数値を
表現する real 型や虚数値を表現する imag 型や複素数を表現する complex 型、文字列の string 型が
該当します。他にも列挙型やクラス型、レコード型、タプル型、レンジ型、ドメイン型、配列型などが
あります。型には別名を付けることもできます。例えば、int 型に integer という別名を付けるには、
type integer = int ;
と書きます。
4.2
リテラル
true と false は真偽値で、bool 型の値です。また、接頭辞 0x(0X) で始まる整数は 16 進数、接頭辞
0b(0B) の整数は 2 進数、それ以外の整数は 10 進数で、いずれも int 型です。また、小数点を含んだ
有効数字部と指数部で構成される 10 進数の実数値は real 型で、指数部は省略可能ですが、省略しない
場合は e(E) の後に 10 を底とした指数を記入します。実数の直後に虚数単位 i を追記すると imag 型に
なります。また、半角ダブルクォートか半角シングルクォートで囲んだ文字列は string 型の値です。
" This is ’ single - quote ’"
’ This is " double - quote " ’
3
4.3
演算子
Chapel で利用できる演算子とその結合性を優先順位が高い順に表 1 に掲載します。
表1
4.4
演算子の一覧
演算子
結合性
意味
.
左結合
フィールドアクセス
()
左結合
関数呼び出し
[]
左結合
関数呼び出し
new
右結合
インスタンス生成
:
左結合
型変換
**
右結合
指数関数
reduce
左結合
リダクション演算
scan
左結合
スキャン演算
dmapped
左結合
ドメインマップ適用
!
右結合
論理否定
~
右結合
ビット否定
* / %
左結合
乗算除算剰余
+ -
右結合
正負の符号
<< >>
左結合
シフト演算
&
左結合
論理積
^
左結合
排他的論理和
|
左結合
論理和
+ -
左結合
加算減算
..
左結合
レンジ
<= >= < >
左結合
不等号
== !=
左結合
等しい等しくない
&&
左結合
短絡論理積
||
左結合
短絡論理和
if 演算子
条件式の値によってどちらの式を評価するかを制御したい場合には if 演算子を使います。
if 2 > 1 then " 2 is bigger than 1 " else " 2 is lesser than 1 "
4.5
for 演算子
式を繰り返し評価してその値をイテレータとして返したい場合には for 演算子を使います。
for i in 1..100 do i * 2
4
5
5.1
variables
変数
Chapel は、破壊的代入が可能な変数を持ちます。Chapel は強い静的型付けを行うので、全ての変数の
型はコンパイル時に決定され、他の型の値は代入できません。例えば int 型変数 foo を宣言するには、
var foo : int ;
と記述します。変数は宣言と同時に初期値を代入することも可能です。例えば、
var foo : int = 12;
変数を明示的に初期化する場合は、以下のように型を省略することができます。
var foo = 12;
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;
初期化式は省略できませんが、型は省略できます。
5
const bar = 12;
クラス型の動的定数ではインスタンスへの参照が固定され、初期化時に代入されたインスタンスを終生
参照しますが、当然ながらそのフィールドへの破壊的代入は何ら制限されません。なお、定数宣言時に
config 修飾子を付けることで、値を起動時オプションで変更できるようになります。
config const bar = 12;
定数 bar はデフォルトでは 12 ですが、起動時にオプション bar を付けることで変更できます。
./ foo -- bar =12321
というように起動すると、動的定数 bar は 12321 になります。なお、起動オプションの一覧は
./ foo -- help
というように help オプションで確認できます。
6
statements
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 を省略することができます。
6
if language == " Kotlin " {
writeln ( " I love Kotlin " );
}
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 文を使います。
7
for i in 1..100 {
if i == 10 then break ;
}
脱出対象の繰り返し構文は後述のようにラベルで指定することができます。
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 {
break LABEL ;
}
}
}
ラベルの付け方は簡単で、繰り返し構文の直前に label 文で識別子を付記するだけです。
7
7.1
functions
関数の基本
int 型の引数 x、y を取って、その合計値をコンソールに出力する foo 関数を定義してみましょう。
proc foo ( x : int , y : int ): void {
writeln ( x + y );
}
Chapel では引数の型は引数名の後にコロンを挟んで指定します。返り値の型も同様に引数宣言の後に
コロンを挟んで指定します。引数が複数ある場合は引数宣言をカンマで並べます。引数がない場合は、
proc hoge (): void {
writeln ( " hoge " );
}
というように引数なしで宣言しますが、この場合、
8
proc fuga : void {
writeln ( " fuga " );
}
と引数の宣言そのものを括弧ごと省略することもできます。
7.2
関数の呼び出し
先ほど定義した関数を呼び出すには、関数名の後に実引数を並べます。
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.3
可変長引数
関数の引数の個数は可変とすることができます。これを可変長引数と言います。
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.4
関数の返り値
関数は終了時に値を返すことができます。関数を終了して値を返すには return 文を使います。
9
proc foo ( x : int , y : int ): int {
return x + y ;
}
また、返り値の型に void を指定した場合は、返り値なしで return 文を書きます。
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.5
型推論
Chapel は型推論を備えており、変数や引数、戻り値の型は省略可能です。先述の foo 関数の例では、
proc foo ( x : int , y : int ): int {
return x + y ;
}
は
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 (1);
bar ( " string " );
というように呼び出すと
10
1 is int
string is not int
と出力されます。これは以下のように記述するのと同等です。
proc bar ( x ) {
if ( x . type == int ) {
writeln (x , " is int " );
} else {
writeln (x , " is not int " );
}
}
Chapel では予約語 type で型を取り出すことができます。
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 ! " );
}
}
のように quack というメソッドを持つ Duck クラスを定義します。そして、Duck 型の引数を取って
quack を呼び出す duck 関数を定義します。
proc duck ( x : Duck ) {
x . quack ();
}
引数 x の型宣言を省略してみましょう。duck 関数に Duck クラスのインスタンスを渡して呼び出せば
引数 x は自動的に Duck 型として解釈されます。従って、
11
proc duck ( x ) {
x . quack ();
}
duck ( new Duck ());
としても問題なくコンパイルできます。ただし、duck 関数の引数には quack という名前のメソッドを
持つという制約が課されています。例えば、Kamo クラス
class Kamo {
proc quack () {
writeln ( " quack ! " );
}
}
のインスタンスを duck 関数に渡しても問題ありません。引数 x が Kamo 型と解釈され、Kamo クラスの
quack 関数が呼び出されるためです。しかし、Cat クラス
class Cat {
proc myaa () {
writeln ( " myaa ! " );
}
}
のインスタンスを duck 関数に渡すとコンパイルエラーになります。Cat クラスには quack という名の
メソッドがないためです。こうした Chapel の型推論の動作を逆手に取ると、関数内でどのような名前
や実引数のメソッドを呼び出しているかによって引数の型が暗黙に指定される、と見ることもできます。
duck ( new Duck ()); // OK
duck ( new Kamo ()); // OK
duck ( new Cat ()); // NG
つまり、duck 関数の例で言えば、引数 x は必ず quack というメソッドを持たなければならず、逆に
quack というメソッドさえ持っていればどんな値でも引数にできます。これは動的型付け言語で言えば
ダックタイピング、静的型付け言語で言えば構造的部分型の一例と言えます。
7.8
リンケージ修飾子
関数のコンパイル時のリンケージ動作を指示するには、表 2 のリンケージ修飾子を使います。
表2
リンケージ修飾子の一覧
修飾子
意味
inline
コンパイル時にインライン展開する
export
関数がプログラムの外に公開される
extern
関数の実体が外部で実装されている
例えば関数をインライン展開したい場合は、
12
inline proc foo (): string {
return " bar " ;
}
と書きます。リンケージ修飾子は互いに排他的なので、複数指定することはできません。
7.9
引数の修飾子
関数の引数の扱い方を指示するには、表 3 の修飾子を使います。
表3
修飾子
引数の修飾子の一覧
意味
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 is 1
a is 1
引数 x に変数 a の値が格納されますね。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 );
13
引数 x に out 修飾子を付けています。実行してみると、
x is 0
a is 12
foo 関数とは逆に、引数 x には変数 a の値が渡されず、一方、foo 関数で引数 x に 12 を代入した操作
が変数 a にも反映されます。続いて、param と type 修飾子の例を見てみましょう。これらの修飾子は
コンパイル時の部分評価のために用いられます。例えば、
proc foo ( param x , param y : int ) {
const tuple : y * x . type ;
return tuple ;
}
のように foo 関数を定義して、
foo ( int , 3);
のように呼び出すと、(int, int, int) 型のタプルが生成されます。あるいは、
proc foo ( type x , param y : int ) {
const tuple : y * x ;
return tuple ;
}
と記述しても同じ結果になります。
7.10
返り値の修飾子
関数の返り値の扱い方を指定するには、表 4 の修飾子を使います。
表4
返り値の修飾子の一覧
修飾子
var
意味
返り値は左辺値
const
返り値は動的定数
param
返り値は静的定数
type
返り値は型の情報
このうち param と type については引数の修飾子と用途はほぼ同じでしょう。
proc nought () param {
return 0;
}
proc integer () type {
return int ;
}
一方、var を使うと興味深い挙動が見れます。具体例を見てみましょう。
14
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.11
関数呼び出しの条件
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 関数を呼び分けることができます。
7.12
部分評価
C++ では、テンプレートを利用することで、計算の一部をコンパイル時に済ませることができます。
例えば、フィボナッチ数をコンパイル時に計算するには、テンプレートを使って、
15
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
int
int
int
fib2
fib3
fib4
fib5
=
=
=
=
fib <2 >:: value ;
fib <3 >:: value ;
fib <4 >:: value ;
fib <5 >:: value ;
と書きます。これはコンパイル時にプログラムを書き換えている、つまり自分自身を入力に取って自分
自身を出力するプログラムを書いているので、メタプログラミングと呼ばれる技法の簡単な例になって
います。同様のことは 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 1;
param
param
param
param
fib2
fib3
fib4
fib5
=
=
=
=
fib (2);
fib (3);
fib (4);
fib (5);
静的な式はコンパイル時に評価され、定数に置き換えられることになっていますが、この最適化は関数
呼び出しについても適用され、引数が静的な式で返り値も静的な式になる関数は、コンパイル時に実行
されるのです。通常の関数の形で自然に記述することができるのでスマートです。
8
8.1
iterators
イテレータの基本
Chapel では、イテレータと称する事実上のコルーチンを定義することができます。コルーチンとは
いったん処理を中断してから再開することができる関数です。例えば、呼び出すごとに 1 から 3 までの
整数値を順次返すイテレータを定義してみましょう。
iter foo () {
yield 1;
yield 2;
yield 3;
}
iter キーワードを使用する以外は通常の関数と同等です。ただし、値は return 文ではなく yield 文
で返します。さっそく foo イテレータを使ってみましょう。
16
for i in foo () {
writeln ( i );
}
for 文のインデックス変数 i には foo イテレータの返り値として 1,2,3 が順番に渡されます。ところで、
イテレータはリテラルを使って簡単に書くこともできます。
for i in 1..3 {
writeln ( i );
}
プログラマが自らイテレータを実装する機会があるとすれば、既存のイテレータを組み合わせる必要が
生じた場合でしょう。例えば、木構造を再帰的に辿って全ノードを返すイテレータを実装するには、
iter bar ( node : Node ): Node {
for child in bar ( node . child1 ) do yield child ;
for child in bar ( node . child2 ) do yield child ;
yield node ;
}
というように、自らを再帰的に呼び出すイテレータを実装することになります。
8.2
イテレータ型
紛らわしいことに、単にイテレータと呼んだ場合は、イテレータとしての役割を果たすコルーチン自体
ではなく、そのコルーチンを保有する第一級オブジェクトを指す場合が多いでしょう。例えば 1..10 は
イテレータと呼ばれます。これはあくまでレンジ型のオブジェクトであって、コルーチンそのものでは
ありません。しかし、イテレータの役割を持つコルーチンを実装しています。厳密ではありませんが、
iter record . these () {
yield numbers ;
}
というように実装されています。この these というイテレータには特別な意味があり、実は、for 文は
these を実装したいかなるオブジェクトをもイテレータ型と見なします。つまり、構造的部分型として
扱われます。自作のデータ型にイテレータの機能を持たせるには these を実装すれば十分でしょう。
9
9.1
classes
クラスの基本
クラスは構造的なデータ型です。具体的には、自身の内部にフィールドと呼ばれる変数を宣言できます。
class Sample {
var x : int , y : int ;
var name : string ;
}
クラス型 Sample は int 型の変数 x,y と string 型の変数 name をフィールドに持っています。
17
var a : Sample = new Sample ();
a . name = " This is sample " ;
writeln ( a . name , a .x , a . y );
ドット演算子を用いることでフィールドにアクセスできます。フィールドの型には制限はなく、例えば、
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 文を使って消去します。
18
var a = new Sample ();
delete a ;
delete 文はメモリ領域を消去する命令で、C 言語の free に相当します。インスタンスが消去された
後の変数 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
コンストラクタ
インスタンスを生成する際には、暗黙的に初期化用のメソッドが呼び出されています。これをクラスの
コンストラクタと呼び、プログラマが自ら明示的にコンストラクタを定義することも可能ですが、定義
されていない場合はデフォルトのコンストラクタがコンパイラによって自動的に補足定義されます。
19
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 () return " I am foo " ;
}
Foo というクラスを定義しておきます。続いて Bar というクラスを定義します。
class Bar : Foo {
proc bar () return " I am bar " ;
}
今までの例にない「:Foo」という記述があります。これはクラス Bar がクラス Foo を継承するという
宣言で、この宣言によって、クラス Bar はクラス Foo の持っているフィールドやメソッドを継承する
ことになります。つまり、クラス Foo で定義されたフィールドやメソッドがクラス Bar でも使えます。
var b = new Bar ();
b . bar ();
b . foo ();
9.8
メソッドのオーバーライド
継承元クラスのメソッドと同名のメソッドを定義して上書きすることをオーバーライドと呼びます。
20
class Foo {
proc foo () {
writeln ( " foo ! " );
}
}
class Bar : Foo {
proc foo () {
writeln ( " bar ! " );
}
}
var b = new Bar ();
b . foo ();
実行してみると、foo!ではなく bar!と出力され、動作が変更されていることがわかります。
9.9
アクセサメソッド
Chapel では、フィールドへのアクセスは暗黙的な左辺値メソッドの呼び出しに変換されます。例えば、
class Language {
var name : string ;
}
というクラスを定義してみます。フィールド name にアクセスするには、
var lang = new Language ();
writeln ( lang . name );
などと記述します。しかし、このフィールドアクセスは、コンパイラによって自動的に
proc Language . name var {
return name ;
}
というメソッドの呼び出しに変換されるのです。フィールドと同名で、引数が 0 個の左辺値関数です。
lang . name = " Chapel " ;
フィールドと同じ名前で、左辺値を返す関数をアクセサと呼び、コンパイル時に自動的に定義されます。
興味深いことに、アクセサをプログラマが明示的に定義することで、動作を変更することができます。
proc Language . name var {
if name != " Scheme " {
name = " Scheme " ;
}
return name ;
}
上の例では、name メソッドを変更することで、フィールド name の値が常に Scheme になります。
21
10
10.1
records
レコードの基本
レコードは、メモリ確保が静的に行われるという違いを除いて、クラスと同じ機能を持つデータ型です。
record Sample {
var x : int , y : int ;
var name : string ;
}
クラスと同様にフィールドやメソッドを定義することができます。レコード定義の構文はクラスとほぼ
同じで、レコード型 Sample は予約語 record を class に変更するだけでクラスに早変わりすることが
できます。クラスと同様に、レコードのフィールドの型には言語仕様上の制限はありません。ただし、
record List {
var value : int ;
var next : List ;
}
というように自身と同じ型のフィールドを持つことはできません。とは言ってもコンパイルエラーにな
るわけでもなく、コンパイラが segmentation fault で自滅するだけなので実用上も注意が必要です。
10.2
静的なメモリ確保
レコードは静的なメモリ管理を行うデータ型で、どのようにメモリを割り当てるかはコンパイラが決定
します。従ってクラスのように new 演算子でインスタンスを生成する必要も、delete 文でメモリ解放
する必要もありません。変数宣言そのものがメモリ割り当ての命令になっていると見なしても差し支え
ありません。扱いはプリミティブ型とほぼ同等であり、しかし、フィールドを持っている分だけ多くの
メモリ領域を消費する大きな変数であると見なせます。自身と同じ型のフィールドを持つレコード型で
変数宣言するとコンパイラが異常終了する理由はメモリ割り当て処理の無限ループで説明できます。
10.3
レコード自身の参照
レコードは静的にメモリが確保されるデータ型であるため、不都合も生じます。
record Record {
var value : int ;
}
proc foo ( a : Record ) {
a . value = 123;
}
var b : Record ;
b . value = 321;
foo ( b );
writeln ( b . value );
22
上のサンプルを実行すると b.value の値は foo 関数呼び出し後も 321 のまま変化しません。なぜなら
レコード Record の実体はスタック上にあり、関数の引数として渡される際には参照ではなく、値自体
がコピーされて渡されるためです。仮に Record がクラスであるならば、foo 関数の呼び出しによって
フィールドの値は更新されるはずです。これが、レコードとクラスの実用上の違いであり、使い分ける
際のポイントなのです。しかし、このままでは this を参照する際に大きな障害となります。なぜなら
this はレコード自身ではなく、レコードのコピーということになるからです。例えば、
record Record {
proc setValue ( value ) {
this . value = value ;
}
}
上のサンプルでは、setValue を呼び出してもフィールド value の値が変更されることはありません。
もちろんこのままでは非実用的なので、予約語 this に限っては、参照が渡されることになっています。
11
11.1
modules
名前空間
関数や変数を宣言するには名前が必要です。しかし、もし互いに同じ名前を持つクラスや関数があれば
コンパイルエラーになるでしょう。頻繁に使用される名前は後から使えないのが普通で、不便に感じる
ことも多いでしょう。そこで、名前が有効となる範囲を名前空間として定義しておき、プログラム内を
別々の名前空間に分割することで衝突を回避します。名前空間を区切るには module 文を使います。
module Module1 {
const piyo = 1;
proc hoge () {
return " foo " ;
}
}
module Module2 {
const piyo = 2;
proc hoge () {
return " bar " ;
}
}
モジュール内にはクラスやレコード、関数や変数、定数などを含めることができます。
11.2
暗黙的なモジュール
どのモジュールにも属さない文がソースファイル内にある場合は、そのソースファイル自体が暗黙的な
モジュールになります。暗黙的なモジュールの名前はファイル名の拡張子.chpl を除いた文字列です。
11.3
入れ子のモジュール
モジュールは入れ子にすることができます。
23
module Module1 {
module Module2 {}
}
モジュールはレキシカルスコープを形成するので、内側のモジュール B は外側のモジュール A の関数や
変数にアクセスできます。反対に、外側から内側にアクセスするためにはドット演算子が必要です。
module Module1 {
module Module2 {
var x : int ;
}
}
writeln ( Module1 . Module2 . x );
ただし、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 関数が自動的に補われています。
24
module Module1 {
proc main () {
writeln ( " This is Module1 " );
}
}
module Module2 {
proc main () {
writeln ( " This is Module2 " );
}
}
Chapel ではプログラムの開始位置を複数定義することはできません。例え別々のモジュール内に配置
したとしても、main 関数がプログラム全体で複数存在すれば、コンパイルエラーになります。
$chpl modules . chpl
error : Ambiguous main () function ( use -- main - module to disambiguate ):
modules . chpl :2: note : in module Module1
modules . chpl :8: note : in module Module2
コンパイルを通すためには、どの main 関数を使用するかをコンパイル時に指定する必要があります。
$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
と表示されます。
25
12
12.1
tuples
タプル
タプルとは、複数の値を並べた組を表すデータ型です。例えば、
(12 , 13 , 14.0 , true , " tuple " )
というように、カンマ区切りで値を並べて括弧で括ることでタプルになります。配列に似ていますが、
構成要素の型を揃える必要がない点で配列とは異なります。タプルの個別の要素にアクセスするには、
const tuple = ( " a " , " b " , " c " );
writeln ( tuple (2)); // " b "
というように、1 から始まるインデックス番号を添えてアクセスします。タプルの型を表現するには、
( int , int , int )
というように、カンマ区切りで型を並べて括弧で括ります。また、構成要素の型が揃っている場合は、
3 * int // ( int , int , int )
というように、個数と型の掛け算でタプル型を表現できます。この例は (int, int, int) と等価です。
12.2
タプルのイテレータ
タプルは these を実装しているので、イテレータとしても使えます。
for a in ( " a " , " b " , " c " ) do writeln ( a );
ただし、タプルの構成要素の型が揃っている場合に限られます。揃っていない場合、例えば、
for a in ( " 1 " , 2 , 3.0) do writeln ( a );
はコンパイルエラーになります。以下のようなエラーメッセージが表示されるはずです。
foo . chpl :1: error : Cannot iterate over non - homogeneous tuples .
実は、要素の型が揃っているタプル型と揃っていないタプル型を区別するための便利な関数があります。
const tuple = ( " a " , " b " , " c " );
if isHom og en eo us Tu pl e ( tuple ) {
writeln ( " homogeneous tuple " );
}
タプルに限らず、言語仕様書には様々なデータ型で便利に使える関数が紹介されています。ただ、言語
仕様書の記載は不十分なので、コンパイラに付属するソースコードを読んだ方が理解が深まるでしょう。
12.3
タプルによる変数宣言
興味深いことに、変数宣言はあたかもタプルのように記述することができます。
26
const (a , b ): ( string , int );
変数名がタプルになっていますが、正しいプログラムです。意味としては、
const a : string ;
const b : int ;
と同等です。複数の変数への代入をタプルを用いてまとめることもできます。
(a , b ) = ( " John " , 24)
これは他の言語の流儀では多重代入やアンパック代入などと呼ばれる機能です。
13
13.1
ranges
レンジ
レンジは数直線上の範囲を表現するデータ型です。例えば、区間 [1, 5] を表現するには、
const from1to5 = 1..5;
というように.. の両側に最小値と最大値を並べます。どちらかを省略すると無限区間になります。
const from1toInf = 1..;
const fromInfTo5 = ..5;
レンジの長さは#演算子で、周期は by 演算子で、0 近傍の値は align 演算子で指定します。例えば、
const from10to30 = 10..30 by -7 align 13 # 3;
は数列 27, 20, 13 です。レンジは these を実装しているのでイテレータとして使えます。
for i in 1..5 do writeln ( i );
13.2
レンジ型
レンジの型は、点の型 idxType と、不連続性 stridable、範囲の有界性 boundedType を指定して、
range ( idxType = int , stridable = false , boundedType = BoundedRangeType . bounded )
というように記述します。BoundedRangeType は列挙型で、表 5 に示す列挙子を持ちます。
表 5 BoundedRangeType の列挙子
列挙子
意味
bounded
最小値と最大値の両方とも有限値の有限区間
boundedLow
最小値が有限値で最大値が無限大の半開区間
boundedHigh
最小値が無限小で最大値が有限値の半開区間
boundedNone
最小値と最大値の両方とも無限値の無限区間
とはいえ、Chapel には型推論の機能があるため、さほど細かく意識する必要はありません。
27
14
domains
14.1
ドメイン
ドメインは空間の広がりを表現するデータ型です。レンジよりも多次元に一般化された矩形領域を表現
する矩形ドメイン型と、連想配列の定義域を表現する連想ドメイン型に大別されます。
14.2
矩形ドメイン
矩形ドメインは、幾何的な空間を表現します。例えば、
{0..10 , -20..20}
というように各座標軸のレンジをカンマで区切って並べると矩形ドメインになります。矩形ドメインは
these を実装しているため、イテレータとしても使えます。例えば、
for p in {0..1 , 0..1 , 0..1} do writeln ( p );
を実行すると、
(0 ,
(0 ,
(0 ,
(0 ,
(1 ,
(1 ,
(1 ,
(1 ,
0,
0,
1,
1,
0,
0,
1,
1,
0)
1)
0)
1)
0)
1)
0)
1)
と出力されます。
14.3
連想ドメイン
連想ドメインは連想配列の定義域を表現します。例えば、
{ " foo " , " bar " }
というように集合に含まれる値をカンマで区切って並べると連想ドメインになります。連想ドメインも
these を実装しているため、イテレータとして使えます。
14.4
矩形ドメイン型
矩形ドメイン型は座標軸の個数を指定する rank、座標の型を指定する idxType、不連続性を指定する
stridable の 3 個のプロパティを指定して、
domain ( rank = 3 , idxType = int , stridable = false )
というように表現します。int 型の連続したドメインの場合は、
domain ( rank = 3)
というように略記することも可能です。
28
14.5
連想ドメイン型
連想ドメイン型には、集合に含まれる値の型を指定します。例えば、
domain ( idxType = string )
は文字列の集合を表す型です。
14.6
レンジのタプルとの相互変換
矩形ドメインをレンジのタプルに変換するには、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}
ドメインの仕様は言語仕様書では言及が不十分なので、ソースコードを解読することを推奨します。
15
15.1
arrays
配列
Chapel の配列は単なる値の集合ではなく、定義域から値域への写像の集合です。定義域はドメインで
指定します。矩形ドメインを定義域に持つ配列は矩形配列として、連想ドメインを定義域に持つ配列は
連想配列として動作します。
15.2
配列型
配列型は、ドメインを角括弧で括った後に値域の要素の型を記入することで表記します。例えば実数の
二次元配列 A と文字列から実数への連想配列 B の変数宣言は、
var A : [{1..10 , 1..10}] real ;
var B : [{ ’ foo ’ , ’ bar ’ }] real ;
となります。ドメインをリテラルで直接記入する場合はドメインの括弧を省略することができます。
var A : [1..10 , 1..10] real ;
var B : [ ’ foo ’ , ’ bar ’] real ;
配列の実体はレコードなので、変数宣言さえすればメモリが確保されています。
29
15.3
配列リテラル
多次元配列のリテラルは、
[1 , 2 , 3 , 4 , 5]
のようにカンマで区切って値を並べます。連想配列のリテラルは、
[1 = > " one " , 10 = > " ten " , 1+2 = > " three " ]
のようにカンマで区切って定義域から値域への対応関係を並べます。
15.4
配列の要素
配列の要素には、角括弧または丸括弧でインデックスを囲んでアクセスします。例えば、
A [1 , 2] = 1.2;
A (3 , 4) = 3.4;
というように代入します。インデックスにはタプルを使うこともできます。
A ((5 , 6)) = 5.6;
Chapel は、不正な位置へのアクセスを監視する安全な配列を提供します。定義域を外れたアクセスは
実行時エラーになります。また、配列は these を実装しているのでイテレータとしても使えます。興味
深いことに配列の these は実装が特殊で、左辺値関数として定義されているので、例えば、
for val in A {
val *= 2;
}
を実行すると、インデックス変数に代入した値が配列に書き戻されるという面白い挙動が楽しめます。
15.5
算術論理演算
配列の演算は直観的に記述することができます。例えば、配列 B と配列 C の和や積は、
const sum = B + C
const prod = B * C
のように記述します。代入も直観的で、例えば、配列 A に配列 B と配列 C の和を代入するには、
A = B + C;
と記述するだけです。これは、zip イテレータを用いて、
for (a , b , c ) in zip (A , B , C ) {
a = b + c;
}
というように繰り返し処理によって代入するのと同等です。
30
15.6
部分配列
配列のインデックスにドメインを指定することで、部分配列を取得することができます。例えば、
const B = A [1..3 , 1..3];
と書くだけで配列 A の部分配列を取り出すことができます。実際の動作を確認してみましょう。
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 ( " array A is ... " );
writeln ( A );
writeln ( " array B is ... " );
writeln ( B );
このプログラムを実行すると、以下のように出力されます。
array A
1.1 1.2
2.1 2.2
3.1 3.2
4.1 4.2
5.1 5.2
array B
1.1 1.2
2.1 2.2
3.1 3.2
is ...
1.3 1.4
2.3 2.4
3.3 3.4
4.3 4.4
5.3 5.4
is ...
1.3
2.3
3.3
1.5
2.5
3.5
4.5
5.5
配列 B が配列 A の部分配列になっていることが確認できます。
15.7
配列のポインタ渡し
配列の実体はレコードなので、関数の引数にする際はコピーが渡されるのが自然です。しかし、配列の
用途から考えるとコストが高すぎるため、配列に限っては特別にポインタ渡しになります。ドメインも
同様にポインタ渡しです。ただし、変数への代入ではコピーが行われます。例えば、
var A : [1..3] real ;
var B = A ;
for i in A . domain {
A ( i ) = i * 2.0;
}
writeln ( " A = " , A );
writeln ( " B = " , B );
を実行すると、
31
A = 2.0 4.0 6.0
B = 0.0 0.0 0.0
となることから、代入はあくまでも値渡しであることがわかります。ポインタ渡しにしたい場合は、
const B = > A ;
=>演算子を使います。ドメインによる部分配列の抽出と組み合わせると面白いことができます。
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
15.8
配列とタプルの使い分け
配列は定義域を表現するためにドメインを指定する必要がありますが、タプルでは要素数を示す情報は
タプル型そのものに含まれています。というのも、タプルは単に関連性のあるデータをまとめてペアに
しただけのデータ型であり、空間に分布するデータを表現する配列とは用途が異なるためです。
proc foo ( a : int ) {
return (a , a + 1);
}
このように、複数の値を返す関数を定義したい場合などにタプルは威力を発揮します。不用意に配列を
使用することはプログラムを低速にし、まさに、鶏を割くのに牛刀を用いるようなものでしょう。
16
16.1
parallelism
並行処理
並列処理とマルチスレッドの混同はしばしば散見されます。しかし、マルチスレッド自体は並行処理に
過ぎません。並行処理とは、複数の処理を同時進行で進めることを意味します。必ずしも複数の命令が
同時に実行されることを意味するものではありません。例えるなら、勉強しつつゲームもするのが並行
処理です。真の意味で両方同時にこなすのは困難ですが、時間を細かく区切れば擬似的に両立できます。
16.2
並列処理
並列処理は複数の処理が文字通り同時に実行されることを意味します。従って複数のプロセッサに処理
を割り当てるスケジューラが必要です。または、命令レベルで複数の演算を同時に実行する工夫が必要
です。しかし、低水準な並列処理の詳細をプログラマ自ら記述する場面は少なく、むしろ、並列実行が
許容される部分をコンパイラに教える構文を駆使しつつ並行処理を記述する場面の方が多いでしょう。
32
16.3
逐次処理
並列処理の基本的な戦略は、実際のところ、並列でない逐次処理のプログラムの高速化とほぼ同じです。
並列処理はあくまでも個々の逐次処理を束ねて高速化するものに過ぎないため、逐次処理の速度を犠牲
にしてまで並列化するのは本末転倒と言えます。逐次処理の高速化のために必要な工夫とは、私たちが
コンピュータアーキテクチャの先生から学んだように、典型的にはメモリの読み書き速度の改善です。
16.4
記憶階層
主記憶はプロセッサに比べ鈍足なので、効率を改善するためにキャッシュと呼ばれる小容量だが高速の
記憶装置を挟むことで主記憶に毎回アクセスしないで済むように工夫されています。実際にはさらに
キャッシュのキャッシュが用意されていて、一次、二次、三次と呼ばれるキャッシュの階層構造を構成
します。プロセッサは一次、二次、三次、主記憶の順番に検索して、目的のメモリ番地を発見します。
16.5
参照局所性
高水準言語では、メモリへのアクセスのように低水準な操作はコンパイラ側で自動的に最適化するもの
とされているためプログラマが詳細に調整することは困難です。しかし、コーディングの工夫によって
性能を劇的に改善できる余地はあります。それは、参照局所性と呼ばれるプログラムの一般的な傾向に
よるものです。通常、ある短期間にアクセスするメモリ番地は小さな範囲に集中する傾向にあります。
これを参照局所性と呼びます。配列を繰り返し構文で操作する場合を考えれば理解しやすいでしょう。
16.6
キャッシュの動作
プロセッサは主記憶にアクセスする直前に、目的のメモリ番地がキャッシュにコピー済みか否かを確認
します。キャッシュにコピーがなかった場合は主記憶にアクセスしますが、このとき目的のメモリ番地
の近傍もまとめて一斉に主記憶からキャッシュにコピーします。これはプログラムの参照局所性を期待
した回路設計上の工夫で、次回以降のアクセスがキャッシュにヒットしやすくなることを狙っています。
16.7
タイリング
参照局所性を意識したコーディングについて 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 ];
}
}
}
行列積の定義通りのプログラムですが、メモリ効率が悪いことに気付きましたか。ここです。
C [ i ][ j ] += A [ i ][ k ] * B [ k ][ j ];
C 言語の多次元配列は単なるポインタ演算に過ぎません。B[k][j] は*(B + k * N + j) の糖衣構文
です。従って、このままでは、メモリアクセスが不連続になってしまいます。つまり、キャッシュに
33
ヒットしにくくなり、場合によっては毎回主記憶にアクセスする可能性すらあります。これこそ我々が
撲滅すべき悪しきプログラムなのですが、対策としては行列の転置でごまかす手法が最も効果的です。
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 ];
}
}
}
}
}
}
イテレーション空間全体を一度に処理するのではなく、小さなブロックに分割して、まずはブロック内
で処理を進めることで局所性を高め、キャッシュの効率を高めることができます。
16.8
並列性の発見
タイリングの考え方は並列処理と親和性が高いことに気付いたでしょうか。各ブロックをプロセッサに
ひとつずつ割り当てることで、行列の積を並列計算することができます。革新的なアイデアがあるので
もない限り、並列化とは、逐次処理をうまく設計した上で、並列化できる場所を探す作業になります。
16.9
タスクの並列性
自宅を出発して肉屋と魚屋に買い物に行く場合、移動時間を考えれば、仕事を両方同時にこなした方が
効率的です。加えて、数人で手分けをして買い物できるなら、単位時間あたりにこなせる仕事が増えて
効率的です。これは、タスク並列化の基本的な考え方です。
16.10
分岐合流モデル
肉屋の買い物と魚屋の買い物は同時に完了することはまずないため、先に終えた方が買い物中の仲間を
待つことになります。これが分岐合流モデルです。もちろん合流せずにばらばらに家に帰ることもでき
ますが、タクシーを頼むならなるべく待ち合わせした方が良いでしょう。このように、同時に遂行する
必要があり、かつ並列実行が可能な仕事は、分岐合流モデルによって高効率に処理できます。
16.11
タスクの依存性
以上は、肉屋での買い物と魚屋での買い物のどちらを先に済ませても構わないという前提での話です。
つまり、双方のタスクには依存関係がありません。しかし、仮に、手持ちが万札だけで、しかも魚屋は
34
万札を喜ばない場合、先に肉屋で小銭に替えてから魚屋に行くべきでしょう。このように、タスク間に
依存関係があると、並列実行は不可能か、少なくとも大いに困難となります。
16.12
データの並列性
行列の和を計算する例で考えてみましょう。要素間には依存関係がなく、部分行列に分割して部分行列
同士を足し算すれば元の行列の和に帰結するので、行列の和は並列計算可能です。これをデータ並列性
と呼びます。要素間に依存関係がなければ、部分行列に対する演算に互いの依存関係がないことは明白
なので、データの並列性からタスクの並列性が導出されることになります。
16.13
並列化の階層性
計算の並列化は様々なレベルにおいて試みられており、例えば、命令レベルで複数の演算を同時に実行
する手法もあれば、複数のプロセッサにメモリを共有させて並列化する手法もあれば、複数のマシンで
ネットワークを介した通信によって並列化する手法もあります。
16.14
命令レベルでの並列化
命令の実行プロセスを複数のステップに分割して各ステップを並列実行することで効率を高める工夫を
命令パイプラインと呼び、現代的なプロセッサでは標準的に実装されています。パイプラインの効率を
高めるために命令の並び替えや分岐予測、ループ展開等の最適化がなされますが、近年のコンパイラは
優秀なので、プログラマ自らアセンブラプログラムを書いて最適化する必要性は薄いと言われています。
16.15
共有メモリでの並列化
プロセッサ間レベルで並列化するためには、プロセッサ間の通信手段の確保が必要です。例えば、どの
プロセッサからでもアクセスできるメモリ空間を用意しておき、メモリを介してデータを読み書きする
ことで通信する手法が多用されます。これを共有メモリと呼びます。典型的には、プロセッサとそれに
付随する局所メモリとのペアをバスを介して複数束ねて接続する NUMA と呼ばれるアーキテクチャで
構成されています。メモリの読み書き速度は場所によって差があり、自分に近い位置にあるメモリほど
高速に読み書きできるので、参照局所性を十分に意識する必要があります。
16.16
分散メモリでの並列化
共有メモリ環境単体ではメモリバスの競合から、接続できるプロセッサ数も数十コア程度に限定される
のが普通です。それ以上のプロセッサを接続して並列化するためには、共有メモリ環境を複数用意して
それらの間をネットワークを介して接続する分散メモリ環境が不可欠です。ただ、ネットワーク通信の
方が共有メモリを介した通信よりも低速なので、局所性を高めて通信の頻度を下げる努力が必要です。
16.17
区分化大域アドレス空間
抽象度の低い分散メモリ実装では煩雑な通信処理をプログラマ自ら記述する必要があり、分散メモリの
利用を敬遠させる原因になります。そこで、プログラマには共有メモリに似た単なるメモリアクセスと
して見えているが、背後では必要に応じて通信が行われる区分化大域アドレス空間と呼ばれるモデルが
考案されました。Chapel は区分化大域アドレス空間を備える数少ないプログラミング言語の仲間です。
35
17
17.1
task parallelism
begin 文
begin 文は、指定された文を実行するためのタスクを分岐生成します。例えば、
begin writeln ( " parallel executed ! " );
というように記述すると、writeln 関数が並行に実行されます。
17.2
sync 文
sync 文は分岐合流モデルを記述する文です。begin 文と組み合わせて使います。例えば、
sync {
begin writeln ( " parallel executed ! " );
begin writeln ( " parallel executed ! " );
begin writeln ( " parallel executed ! " );
}
というように記述すると、begin 文の内容が並行実行され、全て完了するまで待機します。
17.3
cobegin 文
cobegin 文はブロック化された並行処理を記述する文で、sync 文と等価です。例えば、
cobegin {
writeln ( " parallel executed ! " );
writeln ( " parallel executed ! " );
writeln ( " parallel executed ! " );
}
というように記述すると、cobegin 文内の各文が並行実行され、全て完了するまで待ち合わせします。
なお、cobegin 文内で変数に代入する場合は注意が必要です。
var a : int ;
var b : int ;
cobegin with ( ref a , ref b ) {
a = funcA ();
b = funcB ();
}
cobegin 文内部で変数代入を行う場合は代入する変数名を with 節で指定する必要があります。
17.4
atomic 文
atomic 文は、その文が他のプロセッサから見て不可分に実行されることを保証します。例えば、
atomic a += 1;
と記述すると、変数 a が他のプロセッサからも同時に参照される危険を排除できます。他のプロセッサ
からの参照はこの atomic 文が完了するまで自動的に待機します。
36
17.5
serial 文
serial 文は条件式が true の場合に do 節内の並列タスク生成を禁止する構文です。
serial dom . size < 16 do forall i in dom do yield i ;
18
18.1
loop parallelism
coforall 文
coforall 文はタスク並列型の繰り返し構文です。for 文の並列バージョンですが、cobegin 文の糖衣
構文として動作し、イテレーションが個別に完全に独立して並行実行されます。
coforall i in 0..10 do writeln ( " my number is " , i );
18.2
forall 文
forall 文はデータ並列型の繰り返し構文です。for 文の並列バージョンですが、coforall 文では全
てのイテレーションが完全に独立して並行実行されるのに対して、forall 文はイテレーション空間を
部分空間に分割して並行処理し、各部分空間内のイテレーションは逐次実行する点が異なります。
forall i in 1..10 do writeln ( " my number is " , i );
並列処理においては並列化による性能上の無駄を考慮する必要があり、また将来的に SIMD 命令を採用
した並列化手法と連携する際には、coforall 文の性能が必ずしも良いとは限りません。
18.3
並列イテレータ
forall 文で使用するイテレータは、部分空間の分割とプロセッサへの割当て戦略をカスタマイズする
ために、リーダーイテレータとフォロワーイテレータという 2 種類の派生バージョンを実装する必要が
あります。例えば、以下の逐次型のイテレータを並列化してみましょう。
iter foo ( rng : range ( int )) {
for i in rng do yield i ;
}
まず、イテレーション空間を部分空間に分割するリーダーイテレータを実装します。
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 ;
}
37
この実装例では、リーダーイテレータはイテレーション空間を再帰的に分割しつつ cobegin 文で並列
化します。続いて末端部での逐次処理を担当するフォロワーイテレータを実装します。
iter foo ( param tag , rng , followThis ) where tag == iterKind . follower {
for i in followThis do yield i ;
}
引数の followThis には末端で逐次処理する部分イテレーション空間が渡されます。この部分空間内の
イテレーション座標を取り出して forall 文にひとつずつ渡すのがフォロワーイテレータの役割です。
19
19.1
reduction
リダクション演算
足し算や掛け算のように多数の値を少数の値に変換する操作をリダクション演算と呼びます。途中結果
の読み込みと書き戻しが並行実行されるため、リダクション演算を並列処理する場合、タイミングに
よっては古い途中結果を誤って読み込んでしまい、古い途中結果に対して演算を事項してしまう危険が
あります。こうした計算間違いを防ぐために reduce 演算子が利用できます。例えば、1 から 1000 まで
の整数の足し算を計算する場合、reduce の左に並列化対象の演算子 + を、右にイテレータを書きます。
const sum = + reduce (1..1000);
利用可能な演算子は + * && || & | ^
min max minloc maxloc です。このうち min は最小値、max は
最大値を求める演算子です。また、minloc と maxloc は最小値・最大値の場所を求める演算子ですが、
var ( min , index ) = minloc reduce zip (A , A . domain );
というように、使い方が特殊です。
19.2
スキャン演算
スキャン演算はリダクション演算に似ていますが、途中結果が順次格納されたイテレータを返します。
for sum in + scan (1..100) {
writeln ( sum );
}
使用できる演算子はリダクション演算と同じです。
20
locales
locale は分散メモリ環境の個々の計算ノードを抽象化したデータ型です。利用可能なノードの一覧は
Locales という配列に自動的に格納されます。
const myLocale : locale = Locales (0);
writeln ( myLocale . id );
writeln ( myLocale . name );
writeln ( myLocale . numCores );
on myLocale do writeln ( myLocale . id );
on 文は指定したノードに処理を実行させる命令です。文がブロックの場合は do を省略できます。
38

Download Report