並列数値シミュレーションの静的負荷分散法の拡張について Enhancements on Static Load - balancing Scheme for Parallel Numerical Simulations

この論文にアクセスする

この論文をさがす

著者

    • 藤村 佳克 FUJIMURA YOSHIKATSU
    • 豊橋技術科学大学 工学研究科 知識情報工学専攻 Department of Knowledge-based Information Engineering, Toyohashi University of Technology
    • 市川 周一 ICHIKAWA SHUICHI
    • 豊橋技術科学大学 工学研究科 知識情報工学専攻 Department of Knowledge-based Information Engineering, Toyohashi University of Technology

抄録

並列数値シミュレーションの静的負荷分散問題を組合せ最適化問題として定式化し,分枝限定法を用いて最適解を求める方法を示す.この問題は通信と計算の双方を考慮した一種の箱詰め問題である.この問題は計算困難であるが,計算量と通信量に基づいた適切な優先度関数を利用すると,短時間で精度の良い近似解を求めることができる.また再帰的近傍探索も解の改良に有効であった.これらの近似アルゴリズムを分枝限定法で求めた最適解と比較して評価した結果,プロセッサ数4,ブロック数32までの範囲で,誤差10%以下であった.提案する近似解の求解時間は,現状の計算機でも数秒と充分実用的である.An enhanced static load-balancing scheme for parallel numerical simulation is presented. This problem is modeled as a combinatorial optimization problem, which can be solved by branch-and-bound method. As this problem is hard to solve, some approximation algorithms are described and evaluated quantitatively. Simulations show that an algorithm based on priority function which considers both computation and communication gives good approximation, the error of which is less than 10 % with 4 processors and 32 blocks. Iterative improvement method is also effective. The execution time of this algorithm is a couple of seconds with a state-of-the-art computer.

An enhanced static load-balancing scheme for parallel numerical simulation is presented. This problem is modeled as a combinatorial optimization problem, which can be solved by branch-and-bound method. As this problem is hard to solve, some approximation algorithms are described and evaluated quantitatively. Simulations show that an algorithm based on priority function which considers both computation and communication gives good approximation, the error of which is less than 10 % with 4 processors and 32 blocks. Iterative improvement method is also effective. The execution time of this algorithm is a couple of seconds with a state-of-the-art computer.

収録刊行物

  • 情報処理学会研究報告ハイパフォーマンスコンピューティング(HPC)

    情報処理学会研究報告ハイパフォーマンスコンピューティング(HPC) 1999(66(1999-HPC-077)), 185-190, 1999-08-02

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

参考文献:  6件中 1-6件 を表示

被引用文献:  1件中 1-1件 を表示

各種コード

  • NII論文ID(NAID)
    110002932400
  • NII書誌ID(NCID)
    AN10463942
  • 本文言語コード
    JPN
  • 資料種別
    Technical Report
  • ISSN
    09196072
  • NDL 記事登録ID
    5338270
  • NDL 雑誌分類
    ZM13(科学技術--科学技術一般--データ処理・計算機)
  • NDL 請求記号
    Z14-1121
  • データ提供元
    CJP書誌  CJP引用  NDL  NII-ELS  IPSJ 
ページトップへ