大規模高速データ転送並列処理システムに対するスケジューリングアルゴリズム

概要

論文の詳細を見る
近年、並列処理技術の進歩に伴い、システムは大規模化され、また、バスの高速化等によりデータ転送能力も大幅に向上している。本報告では、大規模高速データ転送システムにおける、データ転送時間を考慮した実行時間最小マルチプロセッサタスクスケジューリング問題について議論する。具体的には、本問題に対する実用的な近似アルゴリズムとして、D/CP/G法(Dynamic Critical Path Greedy algorithm)を提案する。大規模高速データ転送システムについては、1. m≧m_<opt> 2.任意のT及びeに対して,w(T)≧d(e)という制約が付加されるのが自然と思われる。ただし、mはプロセッサ数、m_<opt>は最適プロセッサ数、また、ΓはタスクグラフG上のタスク集合、w(T)はタスクTの処理時間、Eはデータ集合、d(e)はデータe=(T,T')のデータ転送時間とする。以上のような制約のもとでは、本問題は、設計変数がx(T,T')である以下のような{0,1}整数計画問題として表すことができる。[numerical formula] (1) ただし、Pは、Gにおける始点から藤点までのバス上の点集合、Γ_<is>(T)は、Tの直接後続タスク集合、Γ_<ip>(T)は、Tの直接先行タスク集合、x(T,T')は、TとT'を同一プロセッサにスケジューリングするとき1、そうでないとき0とする変数とする。また、xよりタスクの割り当てプロセッサは多項式時間で求めることができるので、xのみに注目する。実行時間最小マルチプロセッサタスクスケジューリング問題に関する基本的な用語は文献[1]に、また、グラフに関する基本的な用語は文献[2]を参照されたい。参考文献[1]笠原博徳:並列処理技術,コロナ社(1991). [2]伊藤正夫,白川功,梶谷洋司,篠田庄司:演習グラフ理論基礎と応用,コロナ社(1983).
社団法人電子情報通信学会の論文
1995-09-05

大規模高速データ転送並列処理システムに対するスケジューリングアルゴリズム

スポンサーリンク

概要

著者

関連論文

スポンサーリンク