マルチPSIにおける並列処理とその評価―小粒度高並列オブジェクトモデルに基づくパラダイムについて―

瀧 和男  市吉 伸行  

誌名
電子情報通信学会論文誌 D   Vol.J75-D1   No.8   pp.723-739
発行日: 1992/08/25
Online ISSN: 
DOI: 
Print ISSN: 0915-1915
論文種別: 招待論文 (並列/分散処理論文特集)
専門分野: 応用
キーワード: 
マルチPSI,  MIMD型並列計算機,  プログラム方法論,  並列オブジェクトモデル,  負荷バランス,  通信オーバヘッド,  性能評価,  

本文: PDF(1.3MB)>>
論文を購入




あらまし: 
マルチPSIは,64台のプロセッサをもつ分散メモリ型MIMD計算機である.マルチPSIが対象とする知識処理の問題は,計算の性質が動的で均質さが低く,良好な負荷バランスを実現するためには,問題を多くの部分問題に分割することが重要である.これは一方で通信オーバヘッド増大の危険性をもつ.そこで本論文では,通信オーバヘッドを抑えつつ良好な負荷バランスを実現するための,上記問題領域向きプログラム方法論を提案する.この方法論では,問題を多数の通信し合うオブジェクトとして定式化し,負荷割付けの自由度を確保する.一方負荷割付けに際しては,システムの性能とオブジェクトの性質から通信オーバヘッドを見積もって,それを許容値に入れるよう処理の粒度を調節する.本プログラム方法論を最短経路問題,LSI配線問題,論理シミュレーションの3種のプログラム開発に適用し,いずれも高い効率を実現した.例えば,26万個の小粒度オブジェクトを64台のプロセッサ上に分散配置した最短経路プログラムでは,約75%の効率を得た.また12,000個のオブジェクト(=ゲート)からなる論理シミュレーションでは,64プロセッサで48倍のスピードアップと99 Kイベント/秒の高い絶対性能を実現した.これらの結果から,本プログラム方法論の有効性を確認できたと共に,分散メモリ構造の並列計算機においても,ある程度小粒度の並列処理で高い効率が実現できることを示した.