高位プログラム変換を用いた自動チューニング(2)

図 2.15 に、信号処理の記述例として、レーダ信号処理の一つである CFAR 処理を本配列

36

処理言語で記述したプログラムを示す。CFAR 処理とは、クラッタと呼ばれる目標物以外か らの不要な反射波を抑圧して、目標物からの反射波を抽出する処理である。

function ret = cfar(M)

Type({[2048], 'single'}, M);

Type({[2048], 'single'});

n = 16;

function r = f(p, near, far) d = Sum(near) + Sum(far);

r = single(10.0) * log10(single(32.0) * p / d);

end

ret = Map(@f, M,

MExtract(M, [-(n + 1)], [1], Size(M), [n]), MExtract(M, [2], [1], Size(M), [n]));

end

図 2.15. CFAR 処理プログラム

受信信号 M の注目点に対し、近距離側 near と遠距離側 far のサイズが n の部分配列の総 和を求め、注目点の値を総和で割る処理を、受信信号全体に対しておこなう。

図 2.15 のように MExtract()と Map()を組み合わせることで、アルゴリズムを直観的 に記述できる。同時に、Map()により各注目点に対する関数 f を並列に実行可能である ことが暗黙に記述されるので、処理系で並列性を容易に抽出することができ、データ並 列処理レベルでの高位プログラム変換をしやすいという利点がある。

我々の自動チューニング方式の最大の特長は、最適化の調整ポイントを変化させたプロ グラムを高位プログラム変換で複数生成することで、多様性のある広い探索空間が得られ る点である。MExtract()と Map()の組み合わせで記述したアルゴリズムは、高位プログラム 変換により構造が大きく異なるパラメタ化された複数の候補 C プログラムに変換される。

これらに自動チューニングを適用することで、最適な並列 C プログラムを得ることができ る。

様々な局面で高位プログラム変換を可能にするためには、言語に簡潔で高い表現力が要 求される。本配列処理言語では、配列の各要素に対して指定された関数を実行する際に、

各要素の実行結果を次の要素の実行時の引数に渡すことで逐次的な処理をする高階関数 Scan()や、切り出す領域が元の配列からはみ出た場合の Overlay()関数による例外処理など

37

を備えており、プログラム変換に利用することができる。

高位プログラム変換の例として、図 2.15 の CFAR アルゴリズムに適用可能なものを 2 つ 以下に示す。

(1) 計算量を削減する MExtract2Scan 変換

MExtract2Scan 変換は、計算結果を再利用することで計算量を削減する。同変換を適用し た結果を図 2.16 に示す。変換前は部分配列の総和は毎回独立に計算されていたが、変換後 は総和を計算する際に、前の注目点の計算結果を基に差分を足し引きして次の注目点を計 算する Scan()処理に変換している。近傍処理では、MExtract2Extract で基本的には効率良 い並列プログラムが生成できるが、計算量を削減する最適化がより有効性である境界条件 が存在する可能性もある。

(2) ベクトル化を促す MExtract2Extract 変換

MExtract2Extract 変換は、ベクトル化に適したプログラム構造へ変換することで、処理 系でベクトル化されたプログラムを生成しやすくする。変換前は MExtract()で切り出す小 さい不連続データに対する処理なのでベクトル化には不向きだが、これを Extract()で切り 出す連続した大きな部分配列を組み合わせたベクトル化向きの処理に変換する。

i.MX515(ARM Cortex-A8)プロセッサ上で 2 つの高位プログラム変換を比較した結果を図 2.17 に示す。配列サイズ n が小さい場合、ベクトル化の効果で MExtract2Extract 変換版の 性能が高い。しかし、n に比例して計算量が増加した場合は、計算結果の再利用の効果で n に依らず計算量が一定である MExtract2Scan 変換版の性能が高いことが分かる。この結果 から応用によって異なる最適なプログラム構造を高位プログラム変換で作成する本方式の 有効性が確認できる。

MATLAB 上のデータ並列処理レベルでの高位プログラム変換と自動チューニングを組み合 わせることで、直観的に記述されたアルゴリズムから対象アーキテクチャの性能を引き出 す並列 C プログラムを自動生成できる可能性を示した。

今後は、様々な高位プログラム変換のパタンを蓄積して匠の技の自動化を進めていく。

38 function r = f(p, d)

r = single(10.0) * log10(single(32.0) * p / d);

end

function r = g(init, near_old, near_new, far_old, far_new) r = init - near_old + near_new - far_old + far_new;

end

init = Sum(Overlay(Extract(M, [-(n + 2)],[n]),0)) + Sum(Extract(M, [1], [n]));

D = Scan(@g, init,

Overlay(Extract(M, [-(n + 2)], Size(M)),0), Overlay(Extract(M, [-2], Size(M)),0), Extract(M, [1], Size(M)), Extract(M, [1+n], Size(M)));

ret = Map(@f, M, D);

図 2.16. MExtract2Scan 変換後の CFAR 処理プログラム

図 2.17. 2 つの高位プログラム変換の性能比較

39