著者

有田 五次郎 荒木 啓二郎

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.24, no.2, pp.230-237, 1983-03-15

被引用文献数

2

---

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