数理解析研究所講究録 1325 巻 2003 年 185-190

185
タスクスケジューリングに関する新しい近似アルゴリズムについて

ANew Approximation Algorithm for Task Scheduling
砂坂 明宏 大山口 通夫 太田 義勝( 三重大学 工学部)
SUNASAKA,Michio OYAMAGUCHI and Ybshikatsu OHTA
Kenji KATAYANAGI, Akihiro(Faculty of Engineering, Mie University)
片柳 賢二時間) であり、 $c\leq L$ を満たす。

概要
Papadimitriou ら (1990) は、 タスク複製を許す通信完全であること
遅延のあるスケジューリング問題がを示すとともに、近似精度 2 のアルゴリズムを与えた。
坂上ら (2001) は、 最適解の下界として Papadimitriou
らが提案した -value を用い、 与えられたタスクの依存関係を表す DAG の高さを $L(L\geq 3)$ としたときに、を持つ近似アルゴリズムを示した。
近似精度
本研究では、 -value による下界よりも良い、 新たなに
下界 l $ow(v)$ を定義すると共に、 近似精度を改善したアルゴリズムが存在することを示す。 ここで、
( は通信遅延時間) であり、 $c\leq L$ を満

2$2-3\cdot\neg 2^{\overline{l}}-s1$$\mathrm{e}$$2- \frac{1}{3c}$$c= \lfloor\frac{low(v)}{\tau+1}\rfloor$$\tau$たす。

1

準備
有向非循環グラフ (DAG) $G=(V, E)$ に対して、$\mathrm{N}\mathrm{P}$を $G$$(u, v)\in E$ となる頂点 $u$ が存在しないとき、$G$のレベルとはの根から への根という。 $v\in V$
$v$

$v$

の最大パス長で、 level(v) と表記し、 DAG の高さを

inax{level(u)lu\in V} と定義する。本研究では、(1) 等しい機能を持つプロセッサを無限個使用できる(2) 各タスクの実行時間は 1(3) 各プロセッサ間の通信遅延時間は整定数(4) タスクの複製を許すという [1] $-[3]$ と同じ条件を前提としている。
の DAG $G=(V, E)$ をス
この前提の下で、 高さ
ケジューリングの対象とする。 ここで、 $V$ はタスクの集合、 $E$ はタスク間の依存関係を表す有向辺の集合での頂点はただ一ある このとき (1) $(4)$ より、 レベルとする。
つとしても一般性を失わず、 その頂点を$\tau(\tau\geq 1)$

$L$

はじめに

並列処理システムでは、 タスクのプロセッサ上での実際の処理時間の他に、 タスクを異なるプロセツサに割り当てることで、 通信遅延時間が発生する。 システ
ムの性能を最大限に発揮し、 タスク全体の処理時間の短縮を図るためには、 このような通信遅延を考慮に入れた良いタスクスケジューリングアルゴリズムが必要である。 しかし、通信遅延を考慮したタスクスケジュ
完全 [1] であり、従って、効率リング問題は一般にの良い近似アルゴリズムが求められている。
[1] では、 タスクの複製を許したときに、 この問題の完全性と、近似精度 2 を持つ近似アルゴリズムを示–$\mathrm{N}\mathrm{P}$$\mathrm{N}\mathrm{P}$

しているが、 2 未満の近似精度を持つアルゴリズムが存在するかどうかを未解決問題としていた。ここで、近似
アルゴリズムの近似精度を、と定義する。 [2] では、タスクの DAG の高さを 2 に限定してもこの問題が NP完全であることと、 高さ 2 のとき近似精度 を持つア
ルゴリズムを示している。 さらに、 [1] で提案された、最適解の下界を与える -value を用いる限り、近似精度を以下に改善することは出来ないことが示された。
また、 [3] では、 与えられた DAG の高さを $L(L\geq 3)$を持つ近似アルゴとしたときに、 近似精度
リズムを示している。
本研究では [1] $-[3]$ と同じ条件の下で、 タスクのDAG から再構或される二部グラフの最大マツチングの辺の本数に着目することにより、従来の -value を改善
した、 最適解の下界 low(v) を新たに定義すると共に、を持つ近似アル[3] の結果を改善した、近似精度
9 リズムを示す ここで、」 ( は通信遅延$\frac{3}{2}$$L$$\text{。}$$v^{*}$

定義 1 $v\in V$ の最適スケジュール時刻を oPt(v) と表
記する。

定義 2

のスケジュール時刻の下界 e-$([\mathit{2}Jf\mathit{3}f)v\in V$

value $e(v)$ を次のよう (こ定義する。
(1) が根であるとき、 $e(v)=0$ とする。
(2) が根でないとき、 のすべての先祖 を $e(u)$ の降
$v$

$)$

$u$

$v$

$v$

H}こソートし、$e(u_{1})\geq e(u_{2})\geq\ldots\geq e(u_{p(v)})$とする.

ここで $p(v)$ は、 $v$ の先祖の数。 $k(v)= \min(p(v), \tau+1)$

として、 $e(v)=$$\max$$(e(u_{\iota})+i)$とする$\text{。}$$1\leq i.\leq k.(v)$

がスケジュール時亥りの下界、即ち、 $e(v)\leq\varphi t(v)$であることは [1J の証明と同様に証明できる
参照)$e(v)$$([\mathit{2}Jf\mathit{3}]$

。

定義 3

タスク $u$ の先祖の集合 pred(u) を次のように定義す$\mathrm{e}$る。

.

$\frac{3}{2}$pred.(u)=$\{$$\emptyset\bigcup_{(u’.u)\in E}(pred(u’)\cup\{u’\})$(level(u)=0 の場合)$(\mathrm{f}\theta)\mathrm{f}\mathrm{f}\mathrm{l}a)*_{\mathrm{D}}^{\mathrm{A}})$$2- \frac{1}{3\cdot 2}\overline{\prime-}\mathrm{d}$$\mathrm{e}$$2- \frac{1}{3\mathrm{c}}$$c=\mathrm{t}\fallingdotseq\ovalbox{\tt\small REJECT} P$$\circ$$\tau$

また、 タスクの集合 $S$ (こ対し、 pred(S)
とする。

定義 4

$= \bigcup_{u\in S}$

pred(u)かつ $U_{1}\cap U_{2}=\phi$ とする そのとき、 二部グラフ $f_{G}(U_{2}\mathrm{x}U_{1})=(V’, E’)$ を次のよ
$U_{1},$$U_{2}\subseteq V\backslash \{v^{*}\}$$\circ$

うに定義する。
$V’=U_{1}\cup U_{2\text{、}}E’=\{(u, u’)\in U_{2}\mathrm{x}U_{1}|u\in pred(u’)\}$

186
3$y=\lfloor \mathrm{z}\cdot+0.01k\rfloor$$|_{arrow\text{、}^{}\vee}$$v\in V$ に対して、本研究で提案する新しい下界 l $ow(v)$を以下のように定義する。 $(p(v),k(v)$ については定義..

とする。 (i) が成立しない場合、
即ち $e(u_{y})<0.01k\dashv- i$ のとき(ii) または (iii) が或立することを示す。

証明)

下界 l $ow(v)$2 を参照)$U_{1}=\{u_{1}, \cdots, u_{y}\},$ $U_{2}=\{u_{y+1}, \cdots, \cdot u_{p}\}$$p(v)\leq\tau+1$のとき、 low(v) $=e(v)$ $(=p(v))$$\mathrm{J}\cdot I$$p(v)>\tau+1$ のとき、 $k(v)=\tau+1$ で、-$k(v) \leq e(v)<\frac{3}{2}k(v)$のとき、 low(v) は次節で述べるスケジューリングアルゴリズムから求められ、 $e(v)\leq low(v)$ $\leq e(v)+\frac{1}{2}k(v)$ を
満たす。
-

-

$\frac{3}{2}k(v)\leq e(v)<2k(v)$のとき、 low(v) $=e(v)$$e(v)\geq 2k(v)$ のとき、 $v$ のすべての先祖 $u$

を l $ow(u)$ の降順にソートし、$low(u_{2})\geq\ldots\geq_{-}low(u_{\mathrm{p}}(v))$$\mathrm{l}\leq\dot{\iota}\leq k\mathrm{m}\mathrm{a}\mathrm{x}(low(u_{i})+i)$

を $G’=fc(U_{2}\cross U_{1})$ の最大マッチングとする。 (図1 参照)$low(u_{1})\geq$

として、 l $ow(v)$$=$$\mathrm{J}/I_{p}=\{u|(u, u’)\in\Lambda f\},$ $\Lambda I_{c}=\{u’|(u, u’)\in\Lambda I\}$$|\mathrm{J}\cdot f|=rn,$ $B=U_{1}\backslash \mathrm{A}I_{c}$すべての $u\in pred(B)$ [こ対して u\not\in \Delta l。 となるように、必要なら $B$ との要素を入れ換えることにより、とする。
pred(B)$N$ をの最大マツチングとする。 (図 1 参照)$\Lambda.f_{c}$$\subseteq M_{p}\cup B$$G”=f_{G}((U_{2}\backslash \Lambda/I_{p})\mathrm{x}\Lambda I_{c})$とする。

$N_{p}=\{u|(u, u’)\in N\},$ $N_{c}=\{u’|(u, u’)\in N\}$$k(v) \leq e(v)<\frac{3}{2}k(v)$ のとき、 l $ow(v)$ はの最適ス
ケジュール時刻の下界であることを次節で示す。従って. $l\sigma w(v)\leq opt(v)$ であることは、 [1] の証明と同様
t こ証明できる。 $e(v)\leq l\sigma w(v)$ より、 l $ow(v)$ は $e(v)$ よ
り良い下界を与える。 $e(v)$ を下界として用いた場合の近似精度の限界は である ([3]) が、 この下界を用いることで高さ 2 の DAG に対し 4+\epsilon (但し、 は任意の正の値) の近似精度を持つスケジューリングが可能になることから、 $e(v)$ よりも真に良い下界を与えるもの$|N|=n$ , c=\Lambda /Ic\N。

$v$

すべての $u\in pred(C)$ (こ対して u\not\in N。 となるようの要素を入れ換えることにより、に、必要なら $C$ と$N_{c}$$pred(C)\subseteq\Lambda/I_{p}\cup N_{p}\cup B\cup C$とする。

$\frac{3}{2}$$\epsilon$

である。

4

近似アルゴリズム
本節では近似精度
タスク$v^{*}$$2- \frac{1}{3c}$の近似アルゴリズムを示す。

をスケジュールするプロセッサをメインプ

ロセッサ、 それ以外のプロセッサを外部プロセッサとよぶ。以下では、 タスクの集合 $X$ をプロセッサにスケの値のジュールするとは、 $X$ の全ての要素を下界.

$l\sigma w$

小さい順にプロセッサにスケジュールすることを表す。

$u_{y}$$\cup B$

補題 1 $[lf$(1) $p(v^{*})\leq\tau+1$ ならぼ、 は時刻 $p(v^{*})$ でスケジュ
ルでき、最適スケジュールとなる。
(2) $e(v^{*})<\tau+1$ ならぼ、 は時亥り $e(v^{*})$ でスケジュルできる。

-$v^{*}$のとき、補題 1-2 より以降のタスクは時刻 $e(u_{y})$ でスケジュールできる
ので、 $u_{y+1}$ 以降のタスクを外部ブロセッサにス
ケジュールし、 メインプロセッサには時刻 0 からをスケジューノレし、通信を待ってpred(B)をスケジューノレすれぼ、 $|pred(B)\cup B|\leq e(u_{y})+k$であることから、 のスケジュール時刻の上界は$e(u_{y})+k+m \leq\frac{5}{3}\varphi t$ となりが成立$m \leq(\frac{2}{3}-\mathrm{O}.\mathrm{O}1)k+\frac{2}{3}i$$M_{c}$$v$$\int^{\iota}\mathrm{E}\mathit{2})_{\text{、}}(iii)$

する。

$v^{*}$

以下では、 $p(v^{*})>\tau+1$ の場合について述べる。 このとき $k(v‘)$ $=\tau+1$ である。 また opt(v*)$k(v^{*})$ , opt(v*) を以下では単である。 また、$\geq k(v^{\mathrm{r}})$$[]_{arrow}\sim$$v^{*},p(v^{\mathrm{r}}),$

opt と表記する。 のすべての先祖を -value のとする。
降順}こソートしたものを$v,p,$ $k$ ,$v$$u_{1},$ $u_{2},$ $\cdots,$ $u_{p}$補題 2 $k\leq e(v)<1.5k$ のとき、 すべての$i\leq 0.45k)$

とすべての

$x$

$i$

$(0\leq$$(( \frac{2}{3}-\mathrm{O}.\mathrm{O}1)k+\frac{2}{3}i\leq_{-}x\leq$($N$ : 自然数の集合) に対して、$opt\geq k+i$ かつ $e(u_{x})\geq 0.01k+i$ ならば、次の $(i)\sim$(iii) のいずれかが成立する。
(i) $e(u\lfloor x+0.01k\rfloor)\geq 0.01k+i$(ii) $opt\geq 1.01k+i$
でスケジュール可能。 (このとき、(侑) 近似精度
low(v)=max(e(v), $k+i$ ) と定義する。)$k-\lfloor 0.01k\rfloor\wedge x\in N)$$\frac{5}{3}$

図.

$m>( \frac{2}{3}-0.01)k+\frac{2}{3}i$-$m-\lfloor 0.02k$のとき、十月 $+x\geq 1.\mathrm{O}1k+i$ ならぼ、 どのようにスケジュールしたとしても のスケ
ジュール時刻が $1.\mathrm{O}1k+i$ 以降になることを以下に示す。即ち、 (ii) が成立する。
$v$

187
のうち 1 個以上のタスクをタト
部 7 ロセッサ (こスケジュ-) すると、.l) のスケジューノレ H 寺亥 」は $e(u_{x})+k>1.01k+i$以降となる。
$*\{u_{1}, \cdots, u_{x}\}$ を全てメインプロセッサにス
ケジュールし、$*r \iota>(\frac{2}{3}-0.04)k-\frac{1}{3}i$$*\{u_{1}, \cdots, u_{\mathrm{a}}\}$のとき、 $y+m+n<1.06k+3i=$$1$.

$\Lambda.I_{p}$のとき、. $m[perp]_{\mathrm{I}}n-2\lfloor 0.02k+i\rfloor+x<1.01k+i$$\circ$$\frac{5}{i)i)3}(k’\cdot+(1.06-\frac{5}{\text{て}3})k+\frac{4}{3}i\leq(k++.06-+\frac{4}{3}\cdot 0.45)k^{\wedge}=\frac{\frac{5}{\xi}}{)3}(k+-\frac{+i)(11}{150}k<\frac{\frac{5}{\S}}{3}opt^{*}\text{あり_{、}}(iii\mathrm{B}\backslash ^{\backslash }\backslash \text{成}$立する。

のうち $\lfloor 0.02k+i\rfloor+1$ 個以上のタ. $rn+n-2\lfloor 0.02k$ 十月十

スクを外部プロセッサにスケジュルすると、 マッチングにおいて対応
している
の要素を
$\lfloor 0.01k+i\rfloor+1$ 個以上通信を待って-$x\geq 1.\mathrm{O}1k+i$のとき、 どのようにスケジュールしたとしても のスケジュール時刻が$v$$\Delta I\text{。}\cap\{u_{1}, \cdots, u_{x}\}$以降になることを以下に示す。即ち (ii) が成立する。
$1.\mathrm{O}1k+i$

メインプロセッサにスケジュールすることになり、 のスケジュール時刻
は $1.\mathrm{O}1k+i$ 以降となる。 (図 3 参照)のうち 1 個以上のタス
クを外部プロセッサにスケジュルすると、 のスケジュール時刻は$e(u_{\mathrm{a}}.)+k>1.01k+i$ 以降となる。
を全てメインプロセッ$v$$\circ\{u_{1}, \cdots, u_{x}\}$–$v$$\circ\{u_{1}, \cdots, u_{x}\}$

サにスケジュールし、のうち $\lfloor 0.02k+$ 利 +1 個以上、のうち $\lfloor 0.02k+i\rfloor+1$個以上のタスクを外部プロセッサにスケジュールすると、 マッチン
またグにおいて対応しているは N。の要素を個+1
十月
以上通信を待ってメインプロセッ
サにスケジュールすることになり、$-\lambda/I_{p}$または$N_{\mathrm{p}}$$\Lambda f_{c}$$\lfloor 0.01k$.

$hI_{p}$のうち $m-\lfloor 0.02k$ 十月個以上のタスクをメインプロセッサにスケ
ジュールすると、 メインプロセッサ$v$にスケジュールするタスクの個数が以上となり、のスケジュール時刻は $1.\mathrm{O}1k+i$ 以降$n\mathrm{r}-\lfloor 0.02k+i\rfloor+x$-$v$$m-\lfloor 0.02k$

のとき、

. 従っ
-

$u_{y+1}$

以降のタスクを外部プロセッサにスケジュールし、 メインプロセッサには時刻 0 から pred(B)\cup B,(Pred(C)\cup C)\(Pred(B)\cup B)

を順にスケジュールし、 通信を待って N。をスケジュールすれぼ、 のスケジュール時刻の上界は $y+m+n$ となり
4九$v$$\eta^{\iota}\mathrm{E}$個以上,$n-\lfloor 0.02\mathrm{k}$

十月個以上の口$1.\mathrm{O}1k+i\leq 1.46k$$u_{y}$

からそれぞれ $m-\lfloor 0.02k+$$v$て、 $i>0.425k$ であり、 $m+y>2 \{(\frac{2}{3}$$\mathrm{O}.\mathrm{O}1)k+\frac{2}{3}i\}+\lfloor 0.01k\rfloor>1.88k$ と $k+e(u_{y})<$より、 $k+e(u_{y})<m+y$以降のタスである。 また、 補題 1-2 よりクは#寺亥り $e(u_{y})$ でスケジューノレできるので、

時亥りは $1.01k+i$

サにスケジュールするタスクの個数が $m+n-2\lfloor 0.02k+i\rfloor+x\geq$$1.\mathrm{O}1k+i$ 以上となり、のスケジ
ュール時刻は 101k 伯以降となる。

$2\{(\ovalbox{\tt\small REJECT}$$\mathrm{O}.\mathrm{O}1)k+\frac{2}{3}i\}<m+x<1.03k+2i$$-l\triangleright$

タスクをメインプロセッサにスケ
ジュールすると、 メインプロセツ

十月十 x<l.0lk+i、即ち $m+$$x<1.\mathrm{O}1k+i+\lfloor 0.02k+i\rfloor$$l1\prime I_{p},N_{p}$$i\rfloor$

となる。
-

のスケジュ

以降となる。

$k\leq e(v)<1.5k$ かつ $opt\geq k$ のと
補題 3
き、 以下のいずれかが成立する。
$k\geq 1\mathrm{O}\mathrm{O},$$opt\geq 1.46k$

.

近似精度

.

証明)

$\frac{5}{3}$でスケジュール可能。

補題 2 より、 $i=0,$$x= \lceil(\frac{2}{3}-\mathrm{O}.\mathrm{O}1)k\rceil$$e(u_{x})<0.01k$ のとき、補題 1-2 より

のとき、

以降。タ
スクは時亥り $e(u_{x})$ でスケジューノレできるので、$u_{x}$$u_{x}$

以降のタスクを外部プロセッサにスケジュールし、通信を待って残りの $x-1$ 個のタスクをメインプロのスケジュール時刻の上界は $e(u_{x})+k+x-1<1.01k \cdot+(\frac{2}{3}k-\mathrm{O}.\mathrm{O}1)k=$

セッサにスケジュールすると.
$*n \leq(\frac{2}{3}-0.04)k-\frac{1}{3}i$のとき、 $m+y<$$\frac{5}{3}k\leq\frac{5}{3}$

なる。

$v$

opt となり、 近似精度$\frac{5}{3}$のスケジュールと$(\mathbb{H}\mathit{5})$$e(u_{x})\geq 0.01k$のとき、棹題 2 の $(i)\sim(iii)$ のいずれかが成立する。 (i) が成立する場合には、

$x$

の値

を \lfloor 0.01k」増やして補題 2 を繰り返し適用すること (こより、 $e(u_{k})\geq 0.01k,$ $(ii),$ $(iii)$ の ずれかが$\mathrm{A}\backslash$$1.04k+2i$ より、 $y+m+n \leq\frac{5}{3}(k+i)\leq$$\frac{5}{3}\varphi t$となるので、 (iii) が成立する。

成立する。 $e(u_{k})\geq 0.01k$ のときは、 どのようにス

188以降のタスクを外部ブロセッサにスケジュールし、通信を待って残りの $a-1$ 個のタスクをメインプのスケジュール
ロセッサにスケジュールすると
時亥りの上界は $e(u_{a})+k+a-1 \leq 2.4\dot{3}k\leq\frac{5}{3}$ opt となり、 近似精度 のスケジュールが得られる。 (図$v$$\frac{5}{3}$$\theta)$

ケジュールしたとしても$v$のスケジュール時刻がl.Olk 以降になることを以下に示す。即ち、 (ii) が成立する。
-のうち 1 個以上のタスクを外部
プロセツサにスケジュールすると、 のスケ
ジュ–\sim 時亥|」は $e(uk)+k\geq 1.01k$ 以降となる。

$\{u_{1}, \cdots, u_{k}\}$$v$-

を全てメインプロセツサ (こスケ
ジュールすると、時刻 00 話以降にメインプ$\{u_{1}, \cdots, u_{k}.\}$.

.

$e(u_{x})\leq i+0.01k$ のとき、 補題 1-2 よりならば、で以降のタスクは時刻
補題 1-2 よりスケジュールできるので u\mapsto 」以降のタスクを外$e(u_{\lfloor\frac{\mathrm{A}}{2}\rfloor}.)$部プロセッサにスケジュールし、通信を待って残りの個のタスクをメインプロセツサにス
ケジュールすると、 のスケジュール時刻の上界はopt となり、$\lfloor\frac{k}{2}\rfloor-1$

よって、 $e(u_{x})\geq 0.01k$. かつ $opt\geq 1.01k$ のときが
$x= \lceil(\frac{2}{3}-\mathrm{O}.\mathrm{O}1)k+\frac{2}{3}i\rceil$$\leq 0.9\dot{3}k+1$$\text{、}$

$v$

残る。
一般 (こ、 opt(v) $\geq k+i,$する。但し、 O.Olk $\leq i\leq 0.45k$ .

$e(u_{\lfloor_{2}^{L}\rfloor}.)$$u_{\lfloor\frac{k}{2}\rfloor}$

ロセッサにスケジュールするタスクの個数が以上になるので、 のスケジュール時刻はl.Olk 以降となる。

$k$$e(u_{a})>0.5k$ かつ$v$$e(u_{\lfloor\frac{\iota}{2}\rfloor}.)+k+ \lfloor\frac{k}{2}\rfloor-1\leq 2.4\dot{3}k\leq\frac{5}{3}$

近似精度

と

$\frac{5}{3}$のスケジュールが得られる。 (図 7)以降のタスクは時亥 」 $e(u_{x})$ でスケジューノレできるので、$u_{x}$$\mathrm{I}$以降のタスクを外部プロセツサにスケジュール
し、通信を待って残りの $x-1$ 個のタスクをメインのスケジュ
プロセッサにスケジュールするとノレ時刻の上界は $k+e(u_{x})+x-1\leq k+i+\mathrm{O}.\mathrm{O}1k+$$( \frac{2}{3}-0.01)k+\frac{2}{3}i=\frac{5}{3}(k+i)$ となり、 近似精度のスケジュールとなる。 (図 5)$u_{x}$-$v$$\frac{5}{3}$.

$e(u_{x})>i+0.01k$ のとき、補題 2 の $(i)\sim(iii)$ のい

ずれかが成立する。 (i) が成立する場合には、 の増やして補題 2 を繰り返し適用する値をことにより、 $e(u_{k})\geq 0.01k+i,$ $(ii),$ $(iii)$ のいずれ
$x$$\lfloor 0.01k\rfloor$

かが成立する。 $e(uk)\geq 0.01k+i$ のときは、 どのよ
うにスケジュールしたとしても のスケジュール
時刻が $1.\mathrm{O}1k+i$ 以降になるので (ii) が成立する。
$v$

よって、 $i=0.45k$ のとき、 $opt\geq 1.46k$ または近似

精度$\frac{5}{3}$

補題 4のスケジュールが得られる。
$k\geq 1\mathrm{O}\mathrm{O}$,.

$e(u_{a}.)>0.5k$ かつ$U_{1}=\{u_{\lfloor\frac{k}{2}\rfloor+1}., \cdots, u_{a}\},$

$M$

のとき、

$e(u_{\lfloor_{2}^{\mathrm{A}}\rfloor})>0.9\dot{3}k+1$$U_{2}=${u。+l,$\cdot$.., }$u_{\mathrm{p}}$を $G’=f_{G}(U_{2}\mathrm{x}U_{1})$ の最大マツチングとする。

(図 1 参照)$\Lambda f_{\rho}=\{u|(u, u’)\in M\},$ $M_{c}=\{u’|(u,u’)\in M\}$$\square$$|M|=m,$$k\leq e(v)<1.5k$ かつ $opt\geq 1.46k$のとき、以下のいずれかが成立する。
(このとき、 low(v) $=1.5k$ と定義$opt\geq 1.5k$$B=U_{1}\backslash \mathrm{A}\ovalbox{\tt\small REJECT}$

すべての $u\in pred(B)$ !こ対して u\not\in M。となるの要素を入れ換えることにより、ように、 $B$ ととする。 $N$ を $G”=fc\cdot((U_{2}\backslash$pred(B)の最大マツチングとする。 (図 1 参照)$\Lambda f_{c}$$\subseteq\Lambda I_{p}\cup B$する。)

でスケジュール可能。 (このとき、近似精度low(v)=mae く e(v), $1.46k)$ と定義する )$kI_{p})\cross M_{\mathrm{c}})$$\frac{5}{3}$$\text{。}$証明)とする。 $a+e(u_{a})\leq e(v)<1.5k$
より、 $e(u_{a})<0.5\dot{6}k$ である。

.

$a=\lceil 0.9\dot{3}k\rceil$$e(u_{a})\leq 0.5k$

ならぼ、 補題 1-2 より u。以降のタスクは時亥 」 $e(u_{a})$ でスケジューノレできるので、 u。
$\mathrm{I}$$N_{p}=\{u|(u, u’)\in N\},$ $N_{c}=\{u’|(u, u’)\in N\}$$|N|=n,$$C=M_{\mathrm{c}}\backslash N_{\mathrm{c}}$すべての $u\in pred(C)$ (こ対して u\not\in N。 となるように、 $C$ と N。の要素を入れ換えることにより、$pred(C)\subseteq M_{p}\cup N_{p}\cup B\cup C$ とする。

189$, \gamma\gamma+|B|=|U_{1}|=a-\lfloor\frac{k}{2}\rfloor$$(a-\lfloor\underline{\frac{k^{\mathit{0}}}{9}}\rfloor)-7n,$である。 ここで $|B|=$

$*$

が成り

$|B|+|C|=(a- \lfloor\frac{k^{\wedge}}{2}\rfloor)-n$, u。} のうち 1 個以上のタスクを外{部プロセッサにスケジュールすると、 のスケジューノレ H 寺刻は e(u。)+k $>1.5k$ 以$u_{1},$$\cdots$

$v$

立つ。

降となる。
-

ならば、 補題 1-2 より u。以降のタスクは時刻 $e(u_{o})$ でスケジュールでき$|B|\geq a-0.8\dot{6}k$を全てメインフ ロセツサ (こスケジュールし、.
のうち個以上、または個以上のタスのうち$\circ$$*\{\cdot u_{1}, \cdots, u_{a}\}$るので、 $u_{a+1}$ 以降のタスクを外部プロセツ
サにスケジュールし、 メインプロセッサには
時亥 」 0 から pred(B)\cup B をスケジューノレし、$\lfloor 0.0\dot{6}k\rfloor+1$$\mathbb{J}.I_{p}$$\lfloor 0.0\dot{6}k\rfloor+1$$N_{p}$$\mathrm{I}$

クを外部プロセッサにスケジュールすると、マッチングにおいて対応していまたは N。の要素をる
個以上通信を待ってメインプロセツ

通信を待って残り $a-|B|$ 個のタスクをスケ
ジュ-\sim すれば、 $|pred(B)\cup B|\leq e(u_{a})+k$のスケジュール時刻のであることから、
上界は $e(u_{a})+k+a-|B| \leq 2.4\dot{3}k\leq\frac{5}{3}$optのスケジュールとなる。
となり、 近似精度\sigma 閃 8)$\lfloor 0.0\dot{6}k\rfloor+1$$\mathrm{A}I_{\mathrm{c}}$$v$

サにスケジュールすることになる。
より、 メイン$\frac{5}{3}$$e(u_{\mathrm{L}_{2}^{\mathrm{A}}\rfloor}.)>0.9\dot{3}k+1$

以降
プロセッサに時刻にスケジュールするタスクの個数が個以上 [こなり (..
$\lceil 0.9\dot{3}k\rceil+1$$\cdot$$0.5\dot{6}.k-\cdot 1$$\lfloor 0.5k\rfloor+$$\lfloor 0.0\dot{6}k\rfloor+1\geq 0.5\dot{6}k-1)_{\text{、}}v$のスケジュール時刻は 1 話以降となる。
.
個以
のうち
のうち
上のタスクと、$\lceil 0.3\dot{6}k\rceil-\lfloor 0.0\dot{6}k\rfloor$$M_{p}$$\lceil 0.3\dot{6}k\rceil$$N_{p}$-

k」個以上のタスクをメインプロ$\lfloor 0.\mathrm{O}\dot{6}$

セッサにスケジュールすると、 メイ
ンブロセッサにスケジュールするタ
スクの個数が$2(\lceil.0.3\dot{6}k\rceil-\lfloor 0.0\dot{6}k\rfloor)+$$\lceil 0.9\dot{3}k\rceil\geq 2(0.36k-0.0\dot{6}k)+0.9\dot{3}k=$$1.5\dot{3}k\geq 1.5k$-$|B|<a-0.8\dot{6}k$ならば、 補題 1-2 より u。以降のタスクは時
亥 e(u。) でスケジューノレできるので、:$\mathrm{I}\mathrm{J}$$u\text{。}+1$以降のタスクを外部プロセッサにスケジュ
ルし、 メインプロセッサには時刻

0

–

から

pred(B)\cup B, (Pred(C)\cup C)\(Pred(B)\cup B)
を順にスケジュールし、 通信を待って残り$a-(|B|+|C|)$ 個のタスクをスケジュ.- ル
すれば、$|pred(B)\cup B|+|(pred(C)\cup)C\backslash$$(pred(B)\cup B)|\leq e(u_{a})+k$ であることから、のスケジュール時刻の上界は $e(u_{a})+k$ 十となり、 近のスケジュールとなる。 (図 9)
似精度

$v$

$a-(|B|+|C|) \leq 2.4\dot{3}k\leq\frac{5}{3}opt$

となり、

$v$

のスケジュ–

ル時刻は $1.5k$ 以降となる。

かつ $|B|+|C|\geq a-0.8\dot{6}k$$\overline{\mathrm{i}}$口

捕題 5 $1.5k\leq low(v)<2k$ のとき、 近似精度
ケジュール可能。

証明)$\frac{5}{3}$でス

定義より $k+e(u_{k})\leq e(v)\leq low(v)$ なので.

6(uk)<k^。補題 1-2 より $uk$ 以降のタスクは時亥 」 $e(u_{k})$$|$でスケジュールできるので、$uk+1$ 以降のタスクを外部プ
ロセッサにスケジュールし、通信を待って残りの 個の$k$

タスクをメインプロセッサにスケジュールすると、

$v$

のス

ケジューノレ時亥 U の上界は $e(u_{k})+k+k \leq e(v)+\frac{2}{3}e(v)=$のスケジュールとなる。 (図となり、近似精度$\frac{5}{3}e(v)$$\frac{5}{3}$10)口$\frac{5}{3}$

補題 1\sim 補題 5 から、 次の系が得られる。
-$|B|<a-0.8\dot{6}k$ かつ $|B|+|C|<a-0.8\dot{6}k$のとき、 $m>0.3\dot{6}.k,n>0.3\dot{6}k$ であり、 どしたとしても のスケのよう (こスケジュ
ジュール時刻が $1.5k$ 以降になることを以下に示す。即ち $opt\geq 1.5k$ が成立する。
$-\mathrm{K}\mathrm{s}$$v$*1$\frac{5}{3}$$k\geq 1\mathrm{O}\mathrm{O}$かつ $k\leq low(v)<2k$ のとき、近似精度でスケジュール可能。

定理 1 $k\geq 100$ かつ、 ある自然数
もlow(v)
でスケジュール可能。
度$<(c+1)k_{\text{、}}\ovalbox{\tt\small REJECT} \mathbb{I}$$2- \frac{1}{3\mathrm{c}}$$c$$c=\lfloor^{l\mathrm{o}wv}+\rfloor$について $ck\leq$のとき、 近似精

190

.

証明)

.

$c$

に関する帰納法で証明する。

$c=1$ のとき、即ち $k\leq low(v)<2k$ のとき (こついては、 系 1 より成立する。
$( \frac{5}{3}=2-\frac{1}{3\cdot 1})$

$c\geq 2$のとき、定義より $k+low(uk)\leq low(v)$ 、即

ち low(u\kappa -)<ck 。帰納法の仮定により、
以降のタスクはでスケジュール可能朔$u_{k}$

2-3 \pm ll u’)である。 $u_{k+1}$ 以降のタスクを外部プロセッサにス
ケジュールし、通信を待って残りの 個のタスクのをメインプロセッサにスケジュールすると、スケジュール時刻の上界は以下のようになり、 或立する。 (図 11)
$k$

$v$

$(2- \frac{1}{3(c-1)})low(u_{k})+k+k$$=$$(2- \frac{1}{3c}.

$\leq$$(2- \frac{1}{3\mathrm{c}}\cdot\frac{\mathrm{c}}{\mathrm{c}-1})low(v)+\frac{1}{3c}$5\frac{c}{c-1-})(low(u_{k})+k)+\frac{1}{3c}\cdot\frac{c}{c-1}\cdot k$.

$\frac{1}{c-1}\cdot$

本手法の計算量

本手法の計算量について述べる。
まず、 -value の計算は $O(|V||E|)[3]$ ででき、 の先祖
を -value の降順にソートするのは $O(|V|^{2})$ でできる。
をスケジュ-) レするとき、 $e(v)<2k$ の場合、タスク
DAG から二部グラフを構或するのは $O(|V|^{2})$ ででき、二部グラフの最大マッチングを計算するのは $O(|V||E|)$
ででき、 スケジュールは $O(k|V|)$ でできる。 $k\leq|V|\leq$$|E|$ なので、全体で $O(|V||E|)$ となる。 よって、 \leftarrow value
が $2k$ 未満である全てのタスクのスケジュールは合計で$O(|V|^{2}|E|)$ となる。残りのタスクはそれぞれ $O(k)$ でスケジュールできるので、 合計で $O(|V|^{2})$ となる。
よって、本手法の計算量は全体で $O(|V|^{2}|E|)$ となる。
$v$$\mathrm{e}$low(v)$\mathrm{e}$$v$$(2- \frac{1}{3c})low(v)$

$=$

口

6

おわりに
本研究では、 通信遅延を考慮したタスクスケジュ-

リング問題に対して、新たな下界め w(v) を定義し、そ$[4]\backslash$

る

、で ]

れを用いて近似精度 2ゴ$\text{、}$$\grave{1}\mathbb{E}_{\frac{\Downarrow\backslash l}{\mathrm{p}}}\text{精度}2-\text{と}\prod*\yen \text{の}\neq_{\grave{l}\yen}$$\mathrm{f}\mathrm{f}\mathrm{l}^{\mathrm{A}\backslash \text{て}のア}\mathrm{K}\triangleright$$\acute{k}\rceil\mathrm{r}$一$\frac{1}{3c}$のアルゴリズムを与えた。

$\text{理}1\text{を}\ovalbox{\tt\small REJECT}^{-}\iota_{\sim}^{\mathrm{r}}\text{改善すス^{}*}\text{ム}\phi_{\overline{\prime \mathrm{T}\backslash }}^{\dot{\grave{\mathrm{a}}}}\text{されて}\mathrm{A}\backslash$

$4$

謝辞

ることができる。
定理 2 $k\geq 100$ かつ、 ある自然数$c$について $ck\leq$-kl -\emptyset - alcと\mbox{\boldmath $\tau$}*gス FE#‘/‘*bn c-=) 可–l\S oBwk(vf)\brev 」.

$low(v)<(c\text{き_{}\backslash \grave{1}\mathrm{E}\Downarrow \mathit{1}\mathrm{f}\mathrm{f}\mathrm{l}\mathrm{f}\mathrm{f}}\text{、} 2+- 1)$$.-\llcorner \text{のと_{、}}$

この研究の一部は栢森情報科学振興財団の助或を受けて遂行された。

$\circ$

参考文献$a=. \frac{3k}{k-3}$

.

証明)

.

$c$

[1]

に関する帰納法で証明する。

$c=1$ のとき、即ち $k\leq$ め w(v) $<2k$ のとき (こついては、 系 1 より成立する。

“To.Papadimitriou and M.Yannakakis,
wards an Architecture-Independent Analysis of,
Parallel Algorithms”, SIAM J.Comput.,
no 2, PP.322-328, 1990.
$\mathrm{C}.\mathrm{H}$$\mathrm{v}\mathrm{o}\mathrm{l}.19$$( \frac{5}{3}=2-\frac{1}{k}-\frac{1}{a\cdot 1})$.

$c\geq 2$ のとき、 定義より $k+low(uk)\leq low(v)$即ち $low(u_{k})<ck$ 。帰納法の仮定により、 $uk$ 以
降のタスクはlow(uk) でスケジュル可能である。 $uk$ 以降のタスクを外部プロセッサにスケジュールし、 通信を待って残りの $k-1$ 個のタスクをメインプロセッサにスケジュールすると、のスケジュール時刻の上界は以下のようになり、 成立する。 (図 12)$2- \frac{1}{k}-\frac{a\mathrm{c}-1)1}{}$–$v$$(2- \frac{1}{k}-\frac{1}{a(c-1)})low(u_{k})+k+k-1$$=$$(2- \frac{1}{k}-\frac{1}{ac}\cdot\frac{\mathrm{c}}{c-1})(low(u_{k})+k)+\frac{1}{ac}\cdot\frac{c}{c-1}\cdot k$$\leq$$(2- \frac{1}{k}-\frac{1}{ac}\cdot\frac{c}{c-1})low(v)+\frac{1}{ac}\cdot\frac{1}{c-1}\cdot$$=$$(2- \frac{1}{k}-\frac{1}{ac})low(v)$[2] 河田俊郎, 大山口通夫, 太田義勝, 「通信遅延を考慮したタスクスケジューリングアルゴリズムについて」, 電子情報通信学会論文誌, .V0I.J85-D-I,
No.ll, pp.1088-1092,2002 年.

[3] 坂上知英, 大山口通夫, 太田義勝, 「通信遅延を考慮したタスクスケジューリングの近似アルゴリ
ズムについて」, 2001 年度電気関係学会東海支部
連合大会講演論文集、P.339, 2001.
[4] Michael A. Palis, Jing-Chiou Liou, and David. Wei, “Task Clustering and Scheduling.
for Distributed Memory Parallel Architectures” ,IEEE Transactions on Parallel and Distributed
Systems, Vol. 7, no. 1, pp.46-55, Jaxruary 1996.
$\mathrm{S}.\mathrm{L}$low(v)口