配列処理言語を利用した並列プログラム開発

2.2.1 配列処理に特化したアルゴリズム記述言語

本配列処理言語では、図 2.1 に示すラプラシアンフィルタプログラムのように、配列デ ータの処理を配列演算を組み合わせた抽象度の高い記述でプログラミングできる。本配列 処理言語の最大の特長は、C 言語で多重ループで記述していた処理が、2 つの配列切り出し 関数 MExtract()(繰返し切り出し関数)と Extract()(単一切り出し関数)、および、引数の 配列の要素ごとに関数を適用する高階関数であるマップ関数呼び出し Map()を使うことで ループレスに記述することができる点である。

関数 MExtract()は、図 2.2 に示すように、引数の配列 M から部分配列を繰返し切り出し、

切り出した部分配列を要素とする配列 N を作成する多重配列切り出し関数である。パラメ タ base に最初の部分配列の切り出し開始位置、step に切り出し位置の行方向および列方向 のずらし幅、size に切り出す配列の行方向および列方向の個数、esize に切り出す個々の 配列のサイズを指定する。これらのパラメタは、配列のインデックスやサイズを表す行と 列を示す整数値のペアを [ と ] で囲んで表記する。

19

% 関数の定義

function img = laplacian(m) c = [1 1 1;

1 -8 1;

1 1 1];

p = abs(Sum(m .* c));

end

% トップレベルの関数の定義 function img = lap(M)

% 入出力変数の型指定

Type({[0,0], ‘uint8’}, M);

Type({[0,0], ‘uint8’}, img);

img = Map(@laplacian, MExtract(M, [-1, -1], [1, 1], Size(M), [3, 3]));

end

図 2.1. ラプラシアンフィルタプログラム

図 2.2. 繰返し切り出し関数 MExtract()

図 2.3. MExtract()と高階関数 Map()の組み合わせ

esize base

step N(1,1 )

N(2,1) N(1,2)

N(2,2)

・・・

・・・

・ ・

・ ・ ・ ・

M

esize base

step N(1,1)

N(2,1)

N(1,2)

N(2,2)

・・・

・・・

・ ・

M

(A) Normal case (B) Overlapped case

・ ・

N= MExtract(M, base, step, size, esize)

Map(@f, MExtract(M, base, step, size, esize))

=

N(1,1)

N(2,1)

N(1,2)

N(2,2)

・・・

・ ・・・

・ ・ ・ ・ ・ f

f f

f

20

図 2.4. 単一切り出し関数 Extract()

関数 MExtract()で作成した配列を引数にして関数を呼び出す場合、関数名の前に’@’を 付けると配列の要素毎に関数が適用される。このように MExtract()と Map()を組み合わせ て利用することで、C 言語の多重ループに相当する処理が記述できる。このようにして、性 能に影響を及ぼしやすいループを陽に記述させず、対象アーキテクチャに適したループを 処理系で生成するのが本配列処理言語の大きな特長である。

関数 Extract()は、既存の配列から部分配列を 1 つ切り出す関数である。切り出し開始 位置をパラメタ base に、部分配列のサイズを size に指定する。このように、アルゴリズ ムレベルの情報である配列のサイズや切り出し間隔を配列関数のパラメタとしてアプリケ ーションプログラム開発者に明示させることで処理系が最適化に必要な情報が取得しやす い言語設計になっている。

MExtract()、Extract()ともに元の配列をはみ出す部分配列の指定が可能である。はみ出 した部分には不定値が入っていると解釈する。これにより、画像処理や信号処理によく現 れる配列の境界付近の例外処理の記述を簡略化している。

また、高階関数は Map()以外にも、逐次的な配列処理を記述するための高階関数として Scan()、Reduction()を提供している。

2.2.2 近傍処理プログラムの記述例

本配列処理言語の主な対象は、画像処理や信号処理アルゴリズムにおける近傍処理であ る。近傍処理は、データ局所性が高いため、マルチコア上での並列処理に向いている。近 傍処理では、近傍画素を使った同じ処理を画像の全画素に対して繰返し適用する。このた め、これまでに説明した配列処理関数を使ってシンプルに記述することができる。

図 2.1 に、代表的な近傍処理であるラプラシアンフィルタのプログラムを示す。ラプラ シアンフィルタは、8-近傍を用いた 2 次微分値を求めるアルゴリズムである。プログラ ムでは、関数 MExtract()を使って入力画像 M の各画素の周辺の 9 画素からなる 3 行 3 列の

M N

base size

(B) Outside the boundary (A) Normal case

M base

N size

null N= Extract

(

)

1 2

21

配列からなる配列を作り、その各配列に対して関数 f をマップ関数呼び出しで適用してい る。f は、切り出した 3 行 3 列の配列 x に 3 行 3 列のフィルタ係数の配列を掛けて、9 つの 要素の総和を求める。Sum()は、配列の要素の総和を返す関数である。Sum()と同様に配列 からスカラー値やインデックスを計算する関数として、Prod()、Max()、Min()、Maxpos()、

Minpos()を提供しており(順に総積、最大値、最小値、最大値の要素のインデックス、最小 値の要素のインデックス)、これらを総称してアグリゲーション関数と呼んでいる。また、

Size(M) は配列 M のサイズを返す関数である。

2.2.3 配列処理言語の特徴

本配列処理言語のプログラミングスタイルは、入力配列から部分配列を複数切り出し独 立に計算する処理をループレスに記述可能とするものである。よって、画像処理や信号処 理で頻繁に現れる各要素データに対して近傍要素データから計算する近傍処理 [121]のよ うなデータ並列性のある画像処理アルゴリズムや信号処理アルゴリズムは記述可能で、か つ、本論文で後述する方法で効率良く動作する C プログラムへ変換可能なため本配列処理 言語に向いている。具体的には、画像処理における各種フィルタ処理、エッジ検出処理、

動画像の複数フレームを使った動き検出などである。

一方で、本配列処理言語が得意でないアルゴリズムは、逐次的な依存性のあるような処 理である。本配列処理言語では逐次的な配列処理を記述するための高階関数として Scan()、

Reduction()を提供しているが、そもそも並列化に向かない処理であり最適化は行っていな い。また、タスク並列処理などは記述することができない。

このように、本配列処理言語には得意な処理と不得意な処理があるが、配列処理言語で 記述されたプログラムは処理系により C プログラムに変換可能なので、本配列処理言語に 向くアルゴリズムは本配列処理言語で記述し、それ以外の処理は C プログラムとして記述 しリンクして実行する。本配列処理言語と C 言語を使い分けて記述する必要があるが、記 述する処理にデータ並列性があるか否かの判断はできるアプリケーション開発者を想定し ている。

また、言語の仕様を拡張し記述可能範囲を広げることは一長一短があり、記述可能にな るアルゴリズムが増える一方で、処理系で最適化が必要なポイントも増加するため処理系 の実装コストも高くなってしまう。実装コストのかけ方としては、画像処理や信号処理に ターゲットの限定を維持したままで、その範囲で記述可能なアルゴリズムの最適化を推し 進めていくことが重要である。

2.2.4 配列処理言語の処理系

本配列処理言語の処理系の構成を説明する。本処理系の入力は、本配列処理言語で記述

22

されたプログラムである。まず、フロントエンドにより、入力プログラムを中間表現に変 換する。つぎに、プログラム変換部により、中間表現に対して最適化をおこなう。そして 最後にバックエンドにより、中間表現から、それぞれの対象アーキテクチャ毎に用意する ランタイムライブラリを呼び出しながら実行する C プログラムに変換する。生成された C プログラムは、自動ベクトル化機能を有する C コンパイラによって、SIMD 命令を効率良く 利用する実行プログラムにコンパイルされる。

プログラム変換部では、C プログラムが自動ベクトル化しやすくなるように 2.3 節で述べ る高位プログラム変換を施す。