組合せ最適化による並列数値シミュレーションの静的負荷分散

• Item type: Journal(1)
• 公開日: 1998-06-15
• タイトル: 組合せ最適化による並列数値シミュレーションの静的負荷分散
• タイトル / 言語: en
• タイトル: Static Load Balancing for Parallel Numerical Simulation by Combinatorial Optimization (Special Issue on Parallel Processings)
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 特集：並列処理
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• その他タイトル / その他のタイトル: スケジューリング・負荷分散
• 著者所属: 豊橋技術科学大学知識情報工学系
• 著者所属: 名古屋大学大学院工学研究科
• 著者所属: 名古屋大学大学院工学研究科
• 著者所属(英): en
• 著者所属(英): Department of Knowledge - based Information Engineering Toyohashi University of Technology
• 著者所属(英): en
• 著者所属(英): Graduate School of Engineering, Nagoya University
• 著者所属(英): en
• 著者所属(英): Graduate School of Engineering, Nagoya University
• 著者名: 市川, 周一; 川合, 隆光; 島田, 俊夫
• 著者名(英): Shuichi, Ichikawa; Takamitsu, Kawai; Toshio, Shimada
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 並列数値シミュレーション用高水準言語NSLのための静的負荷分散手法について検討する．計算領域を複数のブロックに分割し，計算量と通信量を考慮して各ブロックに適切なプロセッサを割り当てることにより，シミュレーションの実行時間を最小化する．この負荷分散法を組合せ最適化問題として定式化し，分枝限定法を用いて最適解を求めた．規模の大きな問題では計算量の問題から最適解を求めることができないが，本論文で提案する近似アルゴリズムにより短時間で精度の良い近似解が求まることを数値実験で示す．近似による誤差は妥当な条件下では最適値から15％以下であった．また，数値実験の実行時間から最適解の求解時間を見積もる近似式を求めた．本手法は評価関数の変更によって広範囲の並列処理応用に適用可能である．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: A static load balancing scheme is discussed for parallel numerical simulation language NSL.NSL partitions computational domain into multiple blocks,and allocates processors optimally for each block in accordance with computation and communication cost.This allocation problem is formulated as a combinatorial optimization problem,and solved by branch-and-bound method.Though large problems cannot be solved by this method because of combinatorial explosion,an effective approximation algorithm is presented and evaluated by numerical simulation.The error of this approximation algorithm is less than 15% under reasonable condition.The execution time for this optimization is also measured in numerical simulation to induce the estimation equatin.The allocation method presented here is widely applicable by adapting evaluation function for each purpose.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 39, 号 6, p. 1746-1756, 発行日 1998-06-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764