プロセッサ間通信遅延を考慮した完全2分木状タスク依存グラフのスケジューリングアルゴリズム

藤本 典幸  柘植 宗俊  萩原 兼一  首藤 勝  

誌名
電子情報通信学会論文誌 D   Vol.J80-D1   No.4   pp.369-379
発行日: 1997/04/25
Online ISSN: 
DOI: 
Print ISSN: 0915-1915
論文種別: 論文
専門分野: ソフトウェア基礎
キーワード: 
並列計算,  通信遅延,  スケジューリング,  

本文: PDF(687.7KB)>>
論文を購入




あらまし: 
任意のプロセッサ間通信遅延時間を単一のパラメータτで抽象化した並列計算モデル上でタスクスケジューリング問題の最適解を求める問題は,利用するプロセッサ数を任意に設定でき,かつ,すべてのタスクの処理時間が単位時間である場合にNP困難であり,近似精度2倍以内の一般のdagに対する近似アルゴリズムが知られている.本論文では,任意の形状のdag(derected acyclic graph)に対してスケジュールの実行時間の既知の下界を改良し,完全2分木状のdagを対象としたスケジューリングアルゴリズムを示す.更に改良した下界を用いて提案するアルゴリズムの近似精度をより正確に評価し,少なくとも2から300の範囲のτと,ノード数100万以内の完全2分木に対して,提案するアルゴリズムにより最適スケジュールの平均1.1倍から1.3倍以内程度の実行時間のスケジュールを得ることを示す.更に,本論文で提案するもう一つのアルゴリズムが,プロセッサ割当てが非常に単純であるにもかかわらず,最適スケジュールの平均1.1倍から1.4倍以内程度のスケジュールを生成することを示す.