疎結合並列計算機上でのOR並列問題に適した動的負荷分散方式とその評価

• Item type: SIG Technical Reports(1)
• 公開日: 1989-11-20
• タイトル: 疎結合並列計算機上でのOR並列問題に適した動的負荷分散方式とその評価
• タイトル / 言語: en
• タイトル: An Efficient Dynamic Load Balancing Scheme for OR - Parallel Problems on Loosely - Coupled Multiprocessor and its Evaluation
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 三菱電機株式会社情報電子研究所
• 著者所属: （財）新世代コンピュータ技術開発機構
• 著者所属: （財）新世代コンピュータ技術開発機構
• 著者所属(英): en
• 著者所属(英): Computer Systems Development Dept. Information Systems and Electronics Development Lab. Mitsubishi Electric Corporation
• 著者所属(英): en
• 著者所属(英): Institute for New Generation Computer Technology
• 著者所属(英): en
• 著者所属(英): Institute for New Generation Computer Technology
• 著者名: 古市, 昌一; 瀧, 和男; 市吉, 伸行
• 著者名(英): Masakazu, Furuichi; Kazuo, Taki; Nobuyuki, Ichiyoshi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 疎結合並列計算機上でのOR並列型全解探索問題に適した動的負荷分散方式とその評価について述べる．負荷分散で一番重要なのは，負荷の均等化である．密結合並列計算機上ではこれまでに幾つかの動的負荷均等化方式が成功しているが，疎結合並列計算機上ではプロセッサ間の通信がオーバヘッドとなるために，動的な負荷の均等化は難しい．ここでは，OR並列型全解探索問題一般に適用可能な動的負荷分散方式を提案する．本方式は，動的に検出した暇なプロセッサに対して仕事を割り付けるものである．また，プロセッサをグループ化してプロセッサグループに対する負荷分散とグループ内での負荷分散を行なう事により，階層的に負荷の均等化を行ない，更に階層を増やす事も可能なため，プロセッサの台数拡張性が高い．本方式をICOTで開発した並列推論マシン・マルチPSI/V2上に実現し，詰込みパズルの全解探索問題に適用して評価を行なったところ，32台プロセッサで28.4倍，64台で50倍の台数効果が得られた．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Good load balancing is a key to derive maximal performance from multiprocessors. Several successful dynamic load balancing techniques on tightly-coupled multiprocessors have been developed. However, load balancing is more difficult on loosely-coupled multiprocessors because inter-processor communication overheads takes more cost. We have developed a dynamic load balancing scheme which is applicable to OR-parallel programs in general. Processors are grouped, and work loads of groups and processors are balanced hierarchically. Moreover, it is scalable to any number of processors because of this multi-level hierarchical structure. The scheme is tested for the all-solution exhaustive search Pentomino program on the mesh-connected loosely-coupled multiprocessor Multi-PSI/V2, and speedups of 28.4 with 32 processors and 50 with 64 processors have been attained.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10096105
• 書誌情報: 情報処理学会研究報告計算機アーキテクチャ（ARC）; 巻 1989, 号 99(1989-ARC-079), p. 73-81, 発行日 1989-11-20
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会