FIFOキューを同期手段とする並列プログラムについて(II) : 並列プログラムの待ちなし変換

概要

論文の詳細を見る
オペレーションを点, 制御の移動を枝とする非巡回定向グラフで表現される並列プログラムのあるクラスは, 各プロセッサが先着順(FCFS)で各オペレーションを実行するとき, 自然に同期がとれる. 木構造グラフとなるこのような並列プログラムを待ちなし並列プログラム(SPP)と呼ぶ. FCFSはFIFOメモリを用いてハードウェアで容易に実現でき, SPPはMIMD型高多重並列処理における同期問題を解決する一つの手段となる. 本論文ではまず並列プログラムをグラフ表現し, 確定性, 同値性等の幾つかの性質について論じる. ここで用いる定義は並列プログラムの物理的性質, すなわちセグメンテーションやプロセッサ割当てを含んでいる. 次に木構造グラフで表現されるSPPを定義してその性質について考察し, 最後に一般の並列プログラムをそれと同値なSPPに変換する手順を与える. SPPはデータ依存関係に基づいて構成されており, 一種のデータ駆動型プログラムとみなすことができる. しかしこれらはオペレーションとその間のコントロールフローで表現されており, FIFOキューをハードウェアでもったマルチプロセッサシステムによって効率よく実行できる.
一般社団法人情報処理学会の論文
1983-03-15