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

概要

論文の詳細を見る
MIMD型並列処理機械は最も一般的な並列処理システムと考えられるが, プログラムの並列化の問題, メモリアクセス競合の問題の外に同期のオーバヘッドの問題があり, 高多重並列処理は困難であるとされている. 本論文ではまずMIMD型並列計算機における同期の問題について考察し, 同期問題が, 並列実行されるオペレーションの実行時間と同期操作の実行時間との相対的な問題であることを明らかにする. 次に, オペレーションを点, 制御の移動を枝とする木構造グラフで表現される待ちなし並列プログラム(SPP)の概念を示す. SPPは各プロセッサが先着順(FCFS)で各オペレーションを実行するとき, 自然に同期がとれる並列プログラムになっている. FCFSはFIFOメモリを使用して簡単にハードウェアで実現でき, SPPはMIMD型並列処理において同期手段を高速化する一つの方法となる. SPPを実行する並列計算機は通常の機械語命令の外に並列分岐(parallel branch)命令およびタスク切換(exchange task)命令をもつ. ここではさらにこのような計算機のハードウェアの構成を示し, その上で動く幾つかの並列プログラムの例を示す.
一般社団法人情報処理学会の論文
1983-03-15