データ転送を考慮した最適化マルチプロセッサスケジューリング・アルゴリズム

概要

論文の詳細を見る
マルチプロセッサシステム上で単一プログラムを効率良く並列処理するには、処理すべきタスク集合をプロセッサにどのように割り当て、どのような順序で実行すべきか、という問題を解決しなければならない。しかし、この問題は、実行時間最小マルチプロセッサ・スケジューリング問題と呼ばれ、特に、タスクプリエンプションが許されず、タスク間の先行制約が任意形状であり、タスク処理時間及びプロセッサ数が任意というような一般的な場合には、強NP困難となることが知られている。これに対し著者らは、データ通信時間を考慮しない場合、実用的な最適化アルゴリズムとして、タスク数数百の大規模問題の多くを汎用計算機上で数分程度で解くことができるDF/IHS(Depth First/Implicit Heuristic Search)法を提案している。しかし、特にタスク間のデータ転送時間が比較的大きい場合、データ転送を考慮したスケジューりングが必要である。このような場合に対しても著者らは、DP/DT/MISF法を提案し、その実用性に関して実マルチプロセッサシステム上で評価している。しかし、CP/DT/MISFはヒューりスティック手法であるため、必ずしも最適解を与えるものではない。そこで、本稿では、データ転送を考慮した実用的な最適化マルチプロセッサ・スケジューりング・アルゴリズム、DF/IES[DT](considering Data Transfer)を提案する。
一般社団法人情報処理学会の論文
1991-02-25

データ転送を考慮した最適化マルチプロセッサスケジューリング・アルゴリズム

スポンサーリンク

概要

著者

関連論文

スポンサーリンク