ｽﾗｲﾄﾞﾀｲﾄﾙなし

通信遅延を考慮したタスクスケジューリングの
近似アルゴリズムに関する研究
三重大学大学院工学研究科情報工学専攻
計算機ソフトウェア研究室
坂上知英
はじめに
• 並列処理システムの性能を最大限に発揮
– タスクスケジューリングが重要
• スケジューリング問題のNP完全性
– 近似アルゴリズムが重要
タスク間の依存関係
レベル
・ DAG（非循環有向グラフ）
G=（V,E)で表現
0
T1
T2
T3
頂点：タスク
有向辺：依存関係
1
2
T4
T5
T6
レベル2のDAG
通信遅延とは
・異なるプロセッサ間の通信時間
T1
プロセッサ
時刻 P1
0
T1
1
T2
T2
（通信遅延τ＝２）
2
プロセッサ
時刻 P1
0
P2
T1
1
2
通信遅延なし
3
T2
4
通信遅延あり
通信遅延とは
0
T1
T2
T4
T3
T5
T6
（通信遅延τ＝２）
P1
P2
P3
T１
T２
T３
1
0
P1
P2
T1
T3
1
2
2
3
3
T2
T4
T４
T５
4
4
5
5
T5
T6
通信遅延を考慮した場合
6
T６
7
通信遅延を考慮しない場合
タスクの複製
0
T1
1
2
P1
T３
T４
0
1
通信遅延τ＝1
2
P3
T3
T4
T1
T2
3
T２
P2
複製なし
P1
P2
P3
T1
T1
T1
T2
T3
T4
複製あり
本研究の前提
① 使用できるプロセッサ数は無制限
② タスクの実行時間は１
③ 各プロセッサ間の通信遅延時間は整数τ（τ≧１）
④ タスクの複製を許す
これまでの研究結果
（Papadimitriou、Yannakakis、1990）
・一般のDAGについてNP完全
・一般のDAGに対して近似精度２のアルゴリズム
・近似精度２より良いアルゴリズムがあるかどうかを未解決
問題として提示
（河田ら、2001）
・ DAGのレベルを2に限ってもNP完全
・ DAGのレベルが2、3のとき、それぞれ近似精度1.5、 1.7
のアルゴリズム
・任意のレベルのDAGについては未解決
本研究の結果

DAGのレベルが L （3以上）のとき、
1
近似精度 2 
M
(M  3  2
L 3
)
の多項式時間近似アルゴリズムを考案
各手法の近似精度
レベル
3
4
5
2
・・・
L
1.7
1.67
1.84
1.92
・・・
2  1M
ＰＹ
河田ら
本研究
• e-valueを用いたときの近似精度の限界は
1
 k2 1
k
アルゴリズムの概要
DAG、通信遅延τ
e-valueの計算
スケジューリング
スケジュール
e-valueについて
・タスクvは時刻e(v)より前にスケジュールできない
vの開始時刻の下界として利用
・スケジューリングに利用
（Papadimitriou、Yannakakis、1990）
本研究ではe-valueを変形して利用
e-valueの計算
T1
T２
T４
T３
e(v)  0
T５
帰納的に計算
T６
e-valueの計算
・先祖をe-valueの降順にソート
e(u1)  e(uk )  e(u p)
u
u
u
k  min(p,  1)
p：先祖の数
τ：通信遅延時間
p
k
1
e(v)  e(u k )  k
v
e(v)  max (e(u i )  i )
1i  k
スケジューリングの概要
 p   1
①
 p   1
M

k  e(v )
M 1
M
 k  e(v ) 
k
M 1
②
③
 p : vの先祖の数
 : 通信遅延
 L : vのレベル
 M  3  2 L 3
 k  min(p,  1)
 e(v)  max (e(ui )  i )
1i  k
スケジューリングの概要
 p   1
①
 p   1
M

k  e(v )
M 1
M
 k  e(v ) 
k
M 1
②
③
 p : vの先祖の数
 : 通信遅延
 L : vのレベル
 M  3  2 L 3
 k  min(p,  1)
 e(v)  max (e(ui )  i )
1i  k
スケジューリング① ( p    1)
プロセッサ
0
u
p
u
• すべての先祖を同一プロセッサ
にスケジュール
時刻
u
1
v
最適スケジュール
スケジューリングの概要
 p   1
①
 p   1
M

k  e(v )
M 1
M
 k  e(v ) 
k
M 1
②
③
 p : vの先祖の数
 : 通信遅延
 L : vのレベル
 M  3  2 L 3
 k  min(p,  1)
 e(v)  max (e(ui )  i )
1i  k
 M

k

e
(
v
)


スケジューリング②  M  1

u
k 1 ～
u
p
u
u
•
p を別のプロセッサ
k 1 ～
にスケジュール
u
u
• 通信を待って、 1 ～ k を
同一プロセッサにスケジュール
u
u
k
1
v
1 

e(v) 以下
vの開始時刻は  2 
M

スケジューリングの概要
 p   1
①
 p   1
M

k  e(v )
M 1
M
 k  e(v ) 
k
M 1
②
③
 p : vの先祖の数
 : 通信遅延
 L : vのレベル
 M  3  2 L 3
 k  min(p,  1)
 e(v)  max (e(ui )  i )
1i  k
M


k
 k  e(v) 
スケジューリング③ 
M 1 
0
τ＋１
レベル0
1
u～u
1
2
u
a 1
・ vのレベルは L
 M 1 
a
k
 M

a
L-1
v
1 

時刻  2 
e(v) 以下ならばOK
M

スケジューリング③
0
0
1
u
a 1
2
いくつか別のプロセッサにスケジュール
L‐1
v
1 

e(v)
時刻  2 
M

スケジューリング③
L-1
0
u
2
L-2
2
a 1
2
3
L-1
L‐1
v
v


時刻  2 
1 
e(v)
M
スケジューリング③
L-1
0
u
2
L-2
2
a 1
2
3
L-1
L‐1
v
v


時刻  2 
1 
e(v)
M
M


k
 k  e(v) 
スケジューリング③ 
M 1 
li : vと同一プロセッサに残っているレベルiのタスクの個数
L2
li 
e(v)

M
i 2
L 1
M  L 1
e(ua 1 )  k   li 
e(v)
M
i 2
L 1
1 

  2  e(v)
M

( L  3)
計算量
・ e-valueの計算
O| V || E |
・スケジューリング
O |V |2
全体で O| V || E |


近似精度の限界
• 下界にe-valueを使用
k2 
近似精度
1
 k2 1 が限界
k
k2 
u 
u
k
2
1
v
e(v)  k
最適解： k 
  1
k
2
e(v)  k
近似精度の限界

最適解： k 

k
2
k
2
  1
レベル 0
u 
u
レベル 1
k
2
1
レベル L-1
v
k
2
おわりに
• 本研究では、 Papadimitriouらが提示した未解決問
題に取り組み、任意のレベルのＤＡＧに対するスケ
ジューリングアルゴリズムの近似精度を改善した。
近似精度：
1
2
L 3
3 2
L : DAGのレベル
• Papadimitriouら、本研究で定義したe-valueを下界
として使用した場合の近似精度の限界を示した。
近似精度の限界：
1
 k2 1
k
おまけ

Download Report