% テーマ :
KLIC処理系における
並列多次元配列の実装と評価
Implementation and Evaluation
of Parallel Multi-dimensional Arrays on KLIC
1999年度 卒論!
gzip + postscript ファイル
解凍 gzip -d ptop.ps.gz
% 概要
並行論理型言語KL1は並行論理型言語(Guarded Horn Clauses)
に基づいて専用機上で実行するように設計された言語である.
KL1は記号処理を並列に行うことに優れているが,大規模な数値演算に
関しては実行効率が低い.特に,数値演算によく使われる多次元配列を
効率よく扱えるデータ構造は実装されていなかった.
そこで大規模な数値演算を並列に効率よく実行するため 多次元配列の基本であ
る二次元配列を実装することにした.
静的解析により 全配列要素が単一参照性を持ち かつ,全配列要素が浮動小
数点数の即値であることを保証できた場合に 効率良く数値演算を
行えることを目標とした.
KL1言語の代表的な処理系であるKLIC処理系は KL1を1度C言語に変換してから
コンパイルするという仕組みにより 汎用機での実行を可能にしているため,
実行効率に関してC言語などの手続き型言語と比べて劣っている.
その一つの理由としてtag操作がある.
KL1などの並行論理型言語は もともとデータ型のない言語として設計され,
実際の処理系ではソフトウェア的にtagビットを検査しデータ型や具体化
状態を判別している.このtag操作のため,大量の数値演算を行う場合で
は実行効率が悪かった.
従来のKL1言語においてもVECTORを一次元配列として使用し 数値演算を行うことは可能
あったが,このtag操作のため 実行効率に問題があった.
同様に,多次元配列の場合も何番目のINDEXにあたるかをプログラマが計算し
VECTORに対応させ, 仮想的な多次元配列を実現することは可能ではあ
るが実行効率が優れなかった.
この対策として,プログラムを静的解析し,数値処理のtag操作を削減する
ループ最適化などの研究が進められた.その結果 メモリ使用量を抑え かつ,
高速な読み書きを可能にした数値処理向けの一次元配列データ型が逐次版,並列
版とも既に実装されている.
そこで今回は科学技術計算で多用される多次元配列
の基本である二次元配列を数値処理向けの一次元配列データ型をもとに実装す
ることにした.
結果を
浮動小数点数型を要素に持つ行列の積演算をすることで性能評価した.
逐次処理においては,従来の方式でプログラマが仮想的に二次元配列を
VECTORで実現する方法と比べ,数値演算の実行の1.25倍の高速化が図れた.
float\_array型と比べると1.06倍の高速化が図れ 従来の方法のいずれと比べて
も効率が上がった.
また,従来の仮想的な二次元配列では困難だった大型二次元
配列を扱う並列プログラミングも容易にできるようになった.
二次元配列を分割,結合できることにより 大型二次元配列を分割した後も 1つ１つの
二次元配列として扱うことが可能になった.それにより各PEに仕事を容易に割りあ
てることができる.
その結果 4個のPEで処理し 逐次処理と比較した場合,並列効果は1.91倍,9個
のPEでは3.84倍となった.
また,数値演算の記述が容易になり行列計算,微分方程式など扱える数値演算を
多様化できた.
これらの研究により浮動小数点数の数値演算を効率
よく実行することが可能になった.それにより整数や記号などの離散的なデータ処
理に優れていた並行論理型言語KL1は連続的なデータも効率的に扱えるようにな
ってきた.KL1の応用分野が 画像処理,リアルタイム処理,科学技術計算へ広がると
期待できる.
KL1 KLIC関連サイト
go to HomePage