実行時間最小マルチプロセッサスケジューリング問題に対する実用的並列最適化アルゴリズムの性能評価

参考文献10件

書誌事項

タイトル別名
  • Evaluation of a Practical Parallel Optimization Algorithm for the Minimum Execution-Time Multiprocessor Scheduling Problem

この論文をさがす

説明

本論文では, 強NP完全な最適化問題である実行時間最小マルチプロセッサスケジューリング問題に対する実用的な並列最適化アルゴリズムPDF/IHSの性能評価を行った結果について述べる. Sun Microsystems社のマルチプロセッサシステムUltra Enterprise 3000上でタスク数50から1100の大規模問題に適用した結果, wall-clock timeで600秒以内に逐次型アルゴリズムDF/IHSで最適解が得られた問題の割合は69.3%だったのに対し, 3PEを用いたPDF/IHSでは80.8%, 6PEでは82.8%と向上し, また6PEで最適解が得られた問題の平均求解時間は1PEで平均107.5秒であったのに対し, 6PEで5.8秒となっており, 6PEを用いて1PEの平均18.5倍の速度向上を得るなど, スーパーリニアスピードアップが有効に引き出せることが確認された.

収録刊行物

参考文献 (10)*注記

もっと見る

キーワード

詳細情報 詳細情報について

  • CRID
    1573950402189168256
  • NII論文ID
    110003179840
  • NII書誌ID
    AN10013141
  • 本文言語コード
    ja
  • データソース種別
    • CiNii Articles

問題の指摘

ページトップへ