計算資源の有効利用を目的としたタスククラスタリング

全文

(1)情報処理学会論文誌. コンピューティングシステム. Vol. 4. No. 1. 111–146 (Feb. 2011). 計算資源の有効利用を目的としたタスククラスタリング金. 光. 永煥†1 李星合隆成†2. 吉憲†1 浦野. 中里義頼†2. 秀. 則†2. clustering algorithm which performs clustering each task until every cluster size exceeds δopt for minimizing schedule length. Experimental results by simulation show that our proposed task clustering under δopt condition can suppress schedule length with the small number of clusters.. 1. はじめにプロセッサがネットワーク上で分散された並列処理環境において，タスク間の先行関係を. 限られた数の計算資源でタスクスケジューリングを行う際，少ないプロセッサ数でスケジュール長をできるだけ短縮する方針が重要である．タスククラスタリングによって得られたタスク集合（クラスタ）数がプロセッサ数よりも大きくなれば，従来手法では生成されたクラスタどうしを集約する方針がとられてきた．しかしながら，この手法により同時実行が可能なタスク数が減少し，タスククラスタリング後よりもスケジュール長が大きくなる可能性がある．そこで本論文では，事前にプロセッサ数を限定するために各クラスタサイズ（クラスタに属するタスク実行時間の和）の下限値を設け，この条件の下でスケジュール長を短縮することを目的としたクラスタサイズ δopt の算出手法を示す．そして，各クラスタサイズが δopt 以上となるようにタスクどうしを集約するタスククラスタリングを提案する．シミュレーションの結果，δopt というクラスタサイズを決めることにより，従来手法よりも少ないプロセッサ数でスケジュール長が短縮できるという結果が得られた．. A Task Clustering for Utilizing Computational Resources Hidehiro Kanemitsu,†1 Gilhyon Lee,†1 Hidenori Nakazato,†2 Takashige Hoshiai†2 and Yoshiyori Urano†2 When we perform scheduling every task in a distributed environment where the number of processors is limited or unknown, it is important to decide a policy for suppressing both the required number of processors and its schedule length. If the number of processors (clusters) which has been derived by one of task clustering heuristics is too large with compared to the actual number of processors, a policy for merging several clusters to generate a larger one, has been adopted by conventional approaches. However, degree of task parallelism can be decreased and then schedule length by those approaches becomes larger than that of a task clustering. In this paper, we present a method for deriving the lower bound of each cluster size (δopt ) in order to suppress the number of processors as well as to minimize schedule length. We also present a task. 111. 考慮した様々なタスクスケジューリングが提案されてきた1) ．互いに先行関係が定義されたタスク集合は，一般に有向非循環グラフ（DAG: Directed Acyclic Graph）のタスクグラフとして定義され，DAG に属する各タスクをスケジュールする問題は DAG スケジューリング問題として知られている．DAG スケジューリングは，さらにプロセッサ数があらかじめ与えられている問題と，そうでない問題に分類される．前者の問題に対し，従来は各タスクの優先度に応じてスケジュールする手法が多く用いられてきた．後者においては，タスククラスタリングがある3),4),6),9),11)–15) ．タスククラスタリングでは，タスクどうしを集約してタスク間のデータ転送時間を局所化し，クラスタ（タスクの集合）を生成することによって各クラスタを各プロセッサへの割当て単位とする．タスククラスタリングによるスケジュール長が最小となるプロセッサ数を決定できる．しかしながら，タスククラスタリングではプロセッサ数を制限しないため，DAG によっては得られるクラスタ数が実際のプロセッサ数よりも大きくなる可能性がある．そこで従来，タスククラスタリングの後にクラスタどうしを集約する（本論文ではクラスタ集約と記す）ことにより，クラスタ数を制限するための発見的な手法が提案されている7),8) ．文献 7) では，タスククラスタリングの後に各クラスタサイズ（クラスタに属するタスク実行時間の和）の均一化という基準でクラスタ数を減少させる手法を提案している．また文献 8) では，先行関係を持つクラスタどうしに着目しつつ，各クラスタサイズの均一化を目的とした Load Balancing（LB）と，データ転送時間の最小化を目的とした Communication Traffic Minimizing（CTM）について述べている．しかしながら，これらのクラスタ集約手法では同時実行が可能なタスク数が減少してしまい，スケジュール長がタスククラスタリング後よりも大きくなる可能性がある．特に CTM †1 早稲田大学大学院国際情報通信研究科 Graduate School of Global Information and Telecommunication Studies, Waseda University †2 早稲田大学国際情報通信研究センター Global Information and Telecommunication Institute, Waseda University. c 2011 Information Processing Society of Japan .

(2) 112. 計算資源の有効利用を目的としたタスククラスタリング. の場合は CASS-II 11) によるタスククラスタリング後のスケジュール長よりも最大で 55%，. LB の場合は最大で 19%増加している．すなわち，同時実行が可能なタスク数を考慮せずに. のマルチプロセッサシステム17) で適用されてきた．次に，実行モデルについて述べる．入力として与えられるアプリケーションを Gorg = (V, E). クラスタ集約を行うとスケジュール長が短縮されない場合がある．さらに，最終的に得られ. と表し，DAG（Directed Asyclic Graph）とする．ここで V をタスクの集合，E をタスク. るクラスタ数によってもスケジュール長が異なってしまうため，スケジュール長をできるだ. 間の通信の集合とする．Gorg は単一実行プログラムを指し，タスクは 1 つの分割できない. け短縮させるときの適切なプロセッサ数が分からないという問題がある．. 処理単位（関数，サブルーチン）とする．一方，E に属する任意の通信は，1 つのタスクの. そこで本論文では，クラスタ集約は行わずに必要プロセッサ数を減少させ，かつスケジュー. 処理結果をネットワーク上で転送しなければならないことを指す．また，各プロセッサの処. ル長を最小にすることを目的とした，各プロセッサへ割り当てる仕事量とプロセッサ数の決. 理速度，プロセッサ間通信速度は均一であるとし，w(ni ) を ni ∈ V のタスクサイズ，すな. 定手法を提案する．まず，タスククラスタリングとスケジューリングを行う前に，各クラス. わち各プロセッサでの処理時間とする．ei,j = (ni , nj ) ∈ E を ni から nj へのメッセージの. タサイズをどのようなサイズにすべきかを考察する．このとき，スケジュール長がとりうる. 通信，c(ei,j ) を ei,j の転送時間とする．タスクサイズ同様，ここでは c(ei,j ) を ei,j のデー. 値のうち，各タスクの実行開始時刻をできるだけ遅らせた場合の値（4.2 節で sl w (Gscls ) と. タサイズと呼ぶことにする．. 定義する）を最小とするときのクラスタサイズを算出する．さらに算出されたクラスタサイズを満たしつつ，sl w (Gscls ). をできるだけ減少させるためのタスククラスタリングを提案. nj は ni からのメッセージが到着しないと実行が開始できないものとする．また，ni の直接先行タスク集合を pred (ni ), 直接後続タスク集合を suc(ni ) とし，pred (ni ) = ∅ であるタスクを START タスク，suc(ni ) = ∅ であるタスクを END タスクとする．. し，その有効性をシミュレーションによって示す1 ．本論文の構成は次のとおりである．2 章では本提案で想定するシステムの定義および用途の定義を行い，3 章では従来手法の問題点と本論文の解決対象について述べる．4 章ではク. 任意の ni ，nj ∈ V において ni から nj への経路が存在するとき ni ≺ nj と表す．本論文ではクラスタを 1 つまたは複数のタスク集合と定義し，特にクラスタ i を cls(i) と表す．. ラスタサイズの算出を行い，5 章では提案するアルゴリズムについて述べる．そして 6 章. 2.2 タスククラスタリング. ではシミュレーションによる従来手法との比較結果について述べる．最後に 7 章では，ま. タスククラスタリングとは，複数のタスクを集約して 1 つのクラスタを生成し，データ転送時間の局所化によってスケジュール長（2.3 節で定義）を最小化しようとする手法である．. とめと今後の課題について述べる．. 2. 準. 本論文では，タスク集約を「2 クラスタ内の全タスクを，いずれか一方のクラスタへ含める. 備. ための手続き」と定義する．また，タスククラスタリングを「複数のタスク集約が行われ，. 2.1 想定システム. ある終了条件を満たせば終了する手続き」と定義する．. まず，本論文で想定する環境について述べる．本論文で想定する環境は，能力（処理速. s ) とし，s をタスククラスタリングの入力として与えられる DAG を Gscls = (Vs , Es , Vcls. 度）が等しく，タスク実行とデータ送受信を独立して行うことができる，完全結合型のプロ. タスク集約回数とする．Vs に属するタスク集合を {ns1 , ns2 , . . .} とし3 ，Es に属する辺集合. セッサ環境である．各プロセッサは実行プログラムおよび実行に必要なデータを保持するた. を {. . . , esk,l , . . .} とする．すなわち Gscls は，Gorg に対して s 回のタスク集約が行われた後. めの局所メモリを持ち，データ送信にはメッセージパッシングモデルを用いるものとする．. の DAG である．初期状態では s = 0 とし，V0 ← V ，E0 ← E とする．さらに初期状態で. また，メッセージパッシングモデルにおいて，一定の通信速度で複数のデータを同時に送受. 0 ← {cls 0 (1), cls 0 (2), . . .} とする．は cls 0 (1) = {n01 }, cls 0 (2) = {n02 }, . . . とし，Vcls. 信できるといった古典的なモデルを想定する2 ．このような環境は，従来から分散メモリ型. cls s (i) のタスクサイズの和を w(cls s (i)) とし，本論文では w(cls s (i)) を cls s (i) のクラスタサイズと呼ぶことにする．cls s (i) と cls s (k) とのタスク集約を merge(cls s (i), cls s (k)) と. 1 文献 5) において，我々はタスククラスタリングの方針のみをあげているが，本論文では詳細を述べる． 2 本論文ではこの古典的モデルに従った DAG スケジューリングにおけるタスク集約上の問題点を明らかにし，その解決法を提案する．そのため，タスク間の複数のデータ送信をまとめて 1 度で行うモデル22) や，データ受信側タスクでは 1 度に 1 つの通信データしか受信できないというモデル23) は，本論文では想定しないものとする．. 情報処理学会論文誌. コンピューティングシステム. Vol. 4. No. 1. 111–146 (Feb. 2011). 3 タスク自体の情報（タスクサイズ，直接先行タスクの集合および直接後続タスクの集合）は，タスク集約回数 s によらず不変である．しかしながら，クラスタおよび辺の情報は，タスク集約によって変わりうるため s を付与している．そこで，表記の統一性から，各タスクに対してもクラスタおよび辺と同様，s を付与している．. c 2011 Information Processing Society of Japan .

(3) 113. 計算資源の有効利用を目的としたタスククラスタリング. 表し，この処理手順を. cls s+1 (i) ← cls s (i) ∪ cls s (k); I(nsj , k) =. s+1 s Vcls ← Vcls − {cls s (k)}, Es+1 ← Es ;. c(es+1 p,q ). ← 0 for. ∀ns+1 , p. ns+1 q. ∈ cls s+1 (i),. es+1 p,q. ∈ Es+1 ;. return cls s+1 (i);. ⎧ 0, if ⎪ ⎪ ⎪ ⎨. max. . s ns i ∈pred(nj ), ∈cls (k) ns s i. . tf (nsi ) ≥. max. . s ns i ∈pred(nj ), ∈cls / (k) ns s i. . tf (nsi ) + c(esi,j ) ,. (4) ⎪ max s tf (nsi ) + c(esi,j ) − s max s tf (nsi ) , otherwise. ⎪ s ⎪ n ∈pred(n ), n ∈pred(n ), ⎩ i j i j ∈cls / s (k) ns i. (1). ∈cls s (k) ns i. tdr (nsj ) が決まっても，同一クラスタ内に nsj と先行関係のないタスクがあると，実行. とする．そして 1 つのクラスタは 1 つのプロセッサへの割当て単位とする．. cls s (i) に属する任意の 2 タスクの間に先行関係が存在するとき，cls s (i) は linear である. 順（スケジュール方針）によって nsj がスケジュールされる時刻が変動する．したがって. という6) ．cls s (i) が linear であれば，cls s (i) 内の各タスクの実行順は一意に決定される6) ．. tdr (nsj ) ≤ ts (nsj ) が成り立つ2),23) ．すなわち各タスクの実行完了時刻もスケジュール方針に. 2.3 スケジュール長の定義. よって変動する．本論文では Gscls のスケジュール長を sl (Gscls ) とし，以下に定義する．. 各タスクは，直接先行タスクからのデータをすべて受信すると実行開始できる可能性がある．まず，nsj の実行開始時刻（スケジュールされる時刻）を ts (nsj )，実行完了時刻を tf (nsj ) とし，tf (nsj ) を以下に定義する． tf (nsj ) = ts (nsj ) + w(nsj ). (2) s s nj の直接先行タスクからのデータが到着すると，nj は即座に実行開始できる可能性がある．一方，nsj と同一クラスタに属するタスク nsm がある場合を考える．nsj の直接先行タスクからのデータがすべて到着しても，nsm が実行中であれば nsj の実行は nsm の実行完了まで待たされる．本論文では，任意のタスクに対して直接先行タスクからのデータがすべて受 2),23). 信完了となる時刻を Data Ready Time（DRT）を. tdr (nsj )，nsj tdr (nsj ). =. と定義する．ここでタスク. nsj. の DRT. ∈ cls s (k) とし，以下に定義する． max. ns ∈pred(ns ) i j. . tf (nsi ). ⎧ ⎪ ⎨. = max. max. s s ⎪ ⎩ nis ∈pred(nj ),. +. ni ∈cls s (k). max. s ns ∈cls s (k),cls s (k)∈Vcls j. {tf (nsj )}.. (5). 式 (5) 中，最初に実行される START タスクの実行開始時刻を 0 と仮定している．. 2.4 クラスタ集約タスククラスタリングによって生成されたクラスタ数が，実在するプロセッサ数以下である場合，各クラスタを各プロセッサへ割り当てればよい．しかしながら，クラスタ数が存在するプロセッサ数よりも大きくなれば，クラスタ集約7),8) といった，クラスタ数を減らすための手法が必要である．本論文では，クラスタ集約を「タスククラスタリングによって生成されたクラスタどうしを集約する手続き」と定義する．図 1 に，タスククラスタリングとクラスタ集約の例を示す．初期状態の DAG のスケジュー. . ル長はクリティカルパス長，すなわち n01 → n03 → n05 → n07 の経路長で 23 である．図 1 (b). c(esi,j ). {tf (nsi )},. sl (Gscls ) =. ⎫ ⎪ ⎬. max. s ns i ∈pred(nj ),. {tf (nsi ) + c(esi,j )}. ⎪ ⎭. ∈cls / s (k) ns i. は，タスククラスタリング後の DAG を示す．図 1 (b) では各クラスタが linear となっているため，各タスクのスケジューリングは必要ない．したがって図 1 (b) におけるスケジュー. .. (3). ル長は一意に決まり，20 である．また，クラスタ数を 2 へと減らす（たとえばプロセッサ数が 2 であるという理由で）場合は，図 1 (c)，(d)，(e) のようなクラスタ集約が必要であ. 式 (3) より，tdr (nsj ) は nsj の直接先行タスク nsi のうちで，nsj と同一クラスタに属してい. る．図 1 (b) で生成された各クラスタについて，クラスタ 1（cls 4 (1)）を基点として LB 8). るものの完了時刻とそうでないもののデータ到着時刻から決定される．前者は同一クラスタ. による集約基準でクラスタ 2（cls 4 (2)）を集約すると，図 1 (c)，(d)，(e) のような n52 と. に属しているのでデータ転送時間は 0 である．一方，後者はデータ転送時間 c(esi,j ) だけ要. n53 ，および n52 と n55 のような先行関係のないタスクどうしが存在することになる．その結. する．一方，同一クラスタ内の直接先行タスクはすべて実行完了しているが，他クラスタの. 果，図 1 (c) の cls 5 (1) のように n52 → n53 → n55 の実行順ではスケジュール長が 23，図 1 (d). 直接先行タスクからのデータをまだ受信していない場合は，データ受信待ち時間が存在す. の cls 5 (1) のように n53 → n52 → n55 の実行順では n52 の実行開始時刻が増加することによっ. る．本論文では，クラスタ k に属する nsj がすべての直接先行タスク完了直後にスケジュー. て e52,7 の n57 における到着時刻が遅れ，スケジュール長が 24 となっている．さらに図 1 (e). ルされる場合のデータ受信待ち時間を. 情報処理学会論文誌. I(nsj , k). とし，以下に定義する．. コンピューティングシステム. Vol. 4. No. 1. 111–146 (Feb. 2011). では，n52 を cls 5 (2) において最後にスケジュールすることにより，図 1 (c)，(d) よりもスケ. c 2011 Information Processing Society of Japan .

(4) 114. 計算資源の有効利用を目的としたタスククラスタリング. 法に基づくもの13),15) がある．これらはいずれも生成されるクラスタ数に制限を設けておらず，DAG によっては得られるクラスタ数が膨大なものとなる場合がある．タスククラスタリングの目的がスケジュール長の最小化であれば，生成されたクラスタ数が多くなればなるほど，各プロセッサのスピードアップ率（= 1 プロセッサでのスケジュール長/生成されたクラスタによるスケジュール長）への寄与が小さいことにつながる．クラスタ集約については，文献 7) では Cluster Merging（CM）を行う手法について述べている．CM ではプロセッサ数と同数のクラスタが生成されるまでクラスタサイズを均等化するという基準でクラスタ集約を行うが，タスク間の先行関係は無視している．その結果，互いに先行関係のないタスクどうしが 1 クラスタに属することになり，図 1 (c)，(d)，(e) のようにスケジュール長が大きくなる．また，文献 8) で述べられている Load Balancing （LB），Communication Traffic Minmizing（CTM）は，タスククラスタリングアルゴリズムである CASS-II 11) の後に行われるクラスタ集約手法である．この 2 手法では，クラスタ間で少なくとも先行関係を持つタスクが存在するときに，クラスタどうしを集約する．しかしながら，LB および CTM はタスククラスタリング後の処理であるため，複数タスクが属するクラスタどうしを集約することになる．その結果，互いに先行関係のないタスクが 1 つのクラスタに属する場合があり，図 1 (c)，(d)，(e) のようにスケジュール長が大き図 1 タスククラスタリングとクラスタ集約によるスケジュール長の決定（SL：スケジュール長） Fig. 1 Derivation of schedule length by task clustering and cluster merging (SL: schedule length).. くなる場合がある．そのため，DAG に対する実行プロセッサ数の決定を目的とした従来手法には，以下の 2 つの問題がある．. • タスククラスタリングにより，膨大な数のプロセッサが必要となる．ジュール長が大きくなってしまう．これらの例から，タスククラスタリングの後にクラスタ. • クラスタ集約によるスケジュール長の増分を最小化する（またはスケジュール長を短縮. 集約を行うと同時実行が可能なタスク数の減少によりスケジュール長が大きくなる可能性がある．その一方で，図 1 (c)，(d)，(e) のように，同じクラスタ構造（各クラスタに属するタスク集合が同一）であっても，タスク実行順によってスケジュール長が変動することが分. させる）ための基準がない．. 3.2 提案内容本論文では任意の DAG のスケジュール長を短縮し，かつ少ないプロセッサ数でスケジュールするために，以下の 2 つを述べる．. かる．. (1). 3. 問題定義. スケジュール長が短縮しうるクラスタサイズの下限値 δopt の算出図 1 (c)，(d) により，クラスタ集約を行うと互いに先行関係のないタスクが同一クラ. 3.1 従来手法とその問題点. スタに含まれスケジュール長が短縮しない場合があるため，少ないクラスタ数ででき. 従来のタスククラスタリング3),4),6),9),11)–15) では，主にスケジュール長を最小化できる. るだけスケジュール長を短縮させるための基準が必要である．本論文ではクラスタ数. ときのクラスタ数の算出を目的としている．タスク集約基準としてはタスク集約によってス. を制限するために各クラスタサイズの下限値 δ を設け，δ がどのような値であればス. ケジュール長が増加すれば集約せず，そうでなければ集約は受け入れられるという発見的ア. ケジュール長を短縮できる可能性があるかを考察する．そして，スケジュール長が短. ルゴリズム4),9),11),12) や，集約対象となるタスク組を特定して集約するもの14) ，最適化手. 縮しうるクラスタサイズの下限値 δopt を決定する．. 情報処理学会論文誌. コンピューティングシステム. Vol. 4. No. 1. 111–146 (Feb. 2011). c 2011 Information Processing Society of Japan .

(5) 115. 計算資源の有効利用を目的としたタスククラスタリング. 各クラスタサイズが δopt 以上となるまでタスク集約を行う，タスク集約方針. (2). δopt を決定しても，タスク集約方針（各クラスタに属するタスクの組合せ）およびタスク実行順によってもスケジュール長が変動する．本論文では，各クラスタサイズが. δopt となるまでタスク集約を行いつつ，スケジュール長を短縮させることを目的としたタスククラスタリングについて述べる．. 4. クラスタサイズの下限値算出. について，以下の条件を満たしているものとする．. w(cls S (i)) ≥ δ for ∀cls S (i) ∈. Parameter top s (i). Definition {nsk | ∀nsl ∈ pred(nsk ) s.t., nsl ∈ / cls s (i)} ∪ START Tasks ∈ cls s (i).. in s (i). {nsk | ∃nsl ∈ pred(nsk ) s.t., nsl ∈ / cls s (i)} ∪ START Tasks ∈ cls s (i).. out s (i). {nsk | ∃nsl ∈ suc(nsk ) s.t., nsl ∈ / cls s (i)} ∪ END Tasks ∈ cls s (i).. btm s (i). {nsk | ∀nsl ∈ suc(nsk ), s.t., nsl ∈ / cls s (i)} ∪ END Tasks ∈ cls s (i).. desc(nsk , i). 3.2 節 ( 1 ) の詳細について述べる．まず，Gorg に対して S 回のタスク集約を行った状態 GS cls. Table 1. 表 1 sl w (Gscls ) に関する定義（nsk ∈ cls s (i) とする） Parameter definition which is related to sl w (Gscls ) (nsk ∈ cls s (i)).. S(nsk , i) tlevel(nsk ). S Vcls .. (6). 式 (6) では，全クラスタサイズが δ 以上となっている状態である．また，S 未満のタスク集約回数では，少なくとも 1 つのクラスタサイズは δ 未満である状態とする．以降，2.2 節で用いた s の範囲を，0 ≤ s ≤ S と仮定する．ここでは，δ がどのような値であればスケジュール長が短縮されうるのかを考察する． s Vcls については，各クラスタ内のタスク実行順によってスケジュール長が変わりうる．ま. た，スケジュール方針を決めたとしても各クラスタに属するタスクの組合せによってスケジュール長は変わりうる（いずれの問題も NP 困難. 9). ⎧ ⎨ ⎩. {nsl | nsk ≺ nsl , nsl ∈ cls s (i)} ∪ {nsk } s s ns ∈cls s (i) w(nl ) − ns ∈desc(ns ,i) w(nl ) l. max. l. blevel(nsk ) level(nsk ). LVs (i) sl w (Gscls ). k. {tlevel(nsl ) + w(nsl ) + c(el,k )}, where nsk ∈ top s (i),. ns ∈pred(ns ) l k. T Ls (i) + S(nsk , i), otherwise.. T Ls (i). BLs (i). 4.1 クラスタサイズの下限値を決めるための方針. . max. ns ∈top s (i) k. . max. ns ∈suc(ns ) k l. {tlevel(nsk )}. w(nsk ) + c(esk,l ) + blevel(nsl ). . tlevel(nsk ) + blevel(nsk ) max. {S(nsk , i) + blevel(nsk )}. ns ∈out s (i) k. T Ls (i) + BLs (i) = max. max. ns ∈cls s (i) k. cls s (i)∈V s cls. {level(nsk )}. {LVs (i)}. である）だけでなく，クラスタサイズ. の下限値が決まらないとクラスタは生成できない．すなわちタスククラスタリング前では各クラスタ内のタスクの組合せ，タスク実行順，各タスクにおけるデータ受信待ち時間（式 (4). か（top s (i)），cls s (i) においてどのタスクが他クラスタとのデータ通信を要するか（in s (i)，. で定義）は不明であるので，クラスタサイズの下限値を決定する段階ではスケジュール長が. out s (i)），cls s (i) においてどのタスクが最後に実行されるか（btm s (i)）を定義する．top s (i). 不明である．そのため，クラスタサイズの下限値を変動させることによってスケジュール長. を cls s (i) に属するタスクのうち，その直接先行タスクがすべて他のクラスタに属するものと. に影響を及ぼすような指標を決める必要がある．そこで各タスクについて，先行関係のない. する．すなわち cls s (i) で最も先に実行されるタスクは，top s (i) に属するタスクとなる．ま. タスクを先に実行させることによってできるだけ遅くスケジュールし，かつ他クラスタから. た，in s (i)，out s (i) をそれぞれ少なくとも 1 つの直接先行タスクが他クラスタに属するタス. のデータ受信待ち時間（式 (4) で定義）を無視した場合の，START タスク開始から END. ク，少なくとも 1 つの直接後続タスクが他クラスタに属するタスクとする．そして btm s (i). タスク完了までの所要時間を sl w (Gscls ) とする（4.2 節で定義）．そして，sl w (GS cls ) の上限. をすべての直接後続タスクが他クラスタに属するようなタスクとする．. 値が最小化されるときのクラスタサイズの下限値を δopt （4.7 節で定義）とする（S は式 (6) で定義）．さらに 4.8. 節において，sl w (GS cls ). の増減がスケジュール長に対してどのような. 4.2. 次に，各タスクが cls s (i) においてできるだけ後にスケジュールされる時刻 tlevel (nsk ) を. の定義. 表 1 に各種変数の定義を示す．まず，cls s (i) においてどのタスクが最も先に実行される. 情報処理学会論文誌. コンピューティングシステム. とする．さらに S(nsk , i) を，cls s (i) において nsk の実行順をできるだけ後にした場合の，nsk より先に実行可能なタスクサイズの和とする．. 影響を及ぼすのかを示す．. sl w (Gscls ). desc(nsk , i) を，cls s (i) の中で nsk の後に必ず実行されるタスクの集合と nsk 自身の和集合. Vol. 4. No. 1. 111–146 (Feb. 2011). 定義する．nsk ∈ top s (i) のとき，直接先行タスクはすべて他クラスタに属しているため，こ. c 2011 Information Processing Society of Japan .

(6) 116. 計算資源の有効利用を目的としたタスククラスタリング. の場合の tlevel (nsk ) は直接先行タスクからすべてのデータが到着する時刻である．そして. T Ls (i) を nsk ∈ top s (i) における，tlevel (nsk ) の最大値とする．すなわちある nsk ∈ top s (i) について T Ls (i) = tlevel (nsk ) とすると，top s (i) に属するタスクのうちで nsk 以外のものは，nsk の実行完了までは実行されずに待たされるという状況を意味する．. / top s (i) である場合の tlevel (nsk ) について述べる．式 (4) より，各タスク nsk に次に，nsk ∈ ついて，そのデータ受信待ち時間 I(nsk , i)（式 (4) で定義）はスケジュール方針（すなわち全タスクの実行順）によって決まる．すなわち，タスククラスタリング前では I(nsk , i) は不明である．そこで，top s (i) に属さないタスク nsk においては tlevel (nsk ) = T Ls (i) + S(nsk , i) とする．blevel (nsk ) を，nsk から END タスクまでの経路長の最大値とする．すなわち blevel (nsk ) は，nsk から END タスクまでに実行されるタスクのうち，先行関係のあるもののみを実行させた場合の所要時間の最大値である．BLs (i) を，cls(i) のあるタスクの実行開始時刻から. END タスク実行完了までの所要時間，すなわち S(nsk , i) と blevel (nsk ) との和の最大値とす図 2 各種定義の例 Fig. 2 Example of each defined symbols.. る．そして LVs (i) を T Ls (i) と BLs (i) の和とする．level (nsk ) = tlevel (nsk ) + blevel (nsk ) とすれば，. LVs (i) = T Ls (i) + BLs (i) = T Ls (i) +. max. {S(nsk , i) + blevel (nsk )}. ns ∈out s (i). タ受信待ち時間（図 1 (e) で，9 − 8 = 1 単位時間）だけ無視しているので，sl w (G5cls ) = 28. k. = =. {T Ls (i) + S(nsk , i) + blevel (nsk )}. max s. である．. nk ∈out s (i). max {level (nsk )} ns ∈cls s (i). (7). 4.3 sl w (Gscls ) の解析のための準備 sl w (GS ，タスククラス cls ) は S 回のタスク集約後に決まる値のため（S は，式 (6) で定義）. k. タリング前では sl w (GS cls ) の値は不明である．そこで，タスククラスタリング後のクラスタの. である． s について，LVs (i) の最大値を sl w (Gscls ) とする．どのクラスタ各クラスタ cls s (i) ∈ Vcls. 構造（クラスタ内のタスク間の先行関係，タスク集合）に応じて sl w (GS cls ) の上限値，すなわ. のどのタスクを最後に実行すれば各クラスタの LV 値が最大値をとるかを決定することに. ち sl w (GS cls ) − sl w (Gorg ) の上限値がどのような値となるのかを調べる．この値が最小化され. より，sl w (Gscls ) を算出できる．. るときのクラスタサイズの下限値を δopt を求める．さらに sl w (GS cls ) の値をどうすれば（短. 例 4.2.1. 図 2. に，sl w (G5cls ). 導出の例を示す．この図で示されている DAG は，図 1 (c)，. (d)，(e) と同一である．この場合 LV5 (1) はすなわち，cls 5 (1) では. n52. level (n52 ). であり，LV5 (4) は. level (n54 ). である．. が最も後にスケジュールされる場合，スケジュール長が大きく. なるということである．一方，cls 5 (4) は linear であるので cls 5 (4) 内のタスク実行順は一意である．さらに LV5 (1) = 28，LV5 (4) = 20. であるから，sl w (G5cls ). = LV5 (1) となって. ことにより，タスククラスタリングの目的を決める．そこで，まずは sl w (GS cls ) − sl w (Gorg ) の上限値算出に用いる各種定義について述べる．表 2 に，各種変数の定義を示す．まず，s（s ≤ S ）回のタスク集約の後，sl w (Gscls ) を規定する実行経路に含まれるタスク集合を seq max ,s とする（S は，式 (6) で定義）．すなわち. が後にスケ. S S sl w (Gscls ) = LVS (i) = level (nS k ) を満たす nk について，tlevel (nk ) を決定するタスク集合. ジュールされるときが最大のスケジュール長となることがいえる．このことは図 1 (e) に該. と，blevel (nS k ) を決定する経路に属するタスク集合との和集合である（例 4.3.1 で，具体例. いる．データ受信待ち時間（式 (4) で定義）を無視すれば，cls 5 (1) の中で当する．図 1 (e) では. 情報処理学会論文誌. sl (G5cls ). = 29. であるのに対し，sl w (G5cls ). コンピューティングシステム. Vol. 4. No. 1. では n5 が. n52. 縮するのか，それとも大きくなるのか）スケジュール長が短縮されうるのかを明らかにする. n54. からのデー. 111–146 (Feb. 2011). をあげる）．さらに，seq max ,s 内のタスク集合の中で先行関係にあるものはどの経路 p（タ. c 2011 Information Processing Society of Japan .

(7) 117. 計算資源の有効利用を目的としたタスククラスタリング表 2 sl w (Gscls ) の解析に用いる定義（0 ≤ s ≤ S とする） Table 2 Parameter definitions which are used in analysis on sl w (Gscls ) (0 ≤ s ≤ S).. Parameter seq max ,s. Definition Set of tasks by which sl w (Gscls ) is derived. One path of G0cls , i.e., {n00 , n01 , n02 , . . . , n0k } ∪ {e00,1 , e01,2 , . . . e0k−1,k },. p. by which a sequence <n00 , n01 , n02 , . . . , n0k > is constructed, where e0l−1,l ∈ E0 , n00 is a START task and n0k is an END task. p. One subpath of G0cls , i.e., {n00 , n01 , n02 , . . . , n0k } ∪ {e00,1 , e01,2 , . . . e0k−1,k },. by which a sequence <n00 , n01 , n02 , . . . , n0k > is constructed, where e0l−1,l ∈ E0 , n00 is not a START task or n0k is not an END task. seq ≺ max ,s seq ≺ max ,s (i). One path in which every task belongs to seq max ,s . Set of subpaths in each of which every task in cls(i) belongs to. wmax φ. max. cls S (i)∈V S cls. gmax (nsk ). ⎧ ⎪ ⎪ ⎪ ⎨ min. min n0 ∈pred(n0 ) j k. . max. j. k. ⎪ min ⎪ ⎪ ⎩ n0 ∈pred(n0 ) j. ΔLi. . c(e0 ) j,k. ,. ,. k. . . ⎫. . . max n0 ∈suc(n0 ) l k. max n0 ∈suc(n0 ) l k. . . An upper bound of Δsl w . w(nsk ) +. ns ∈seq ≺ max ,s (i) k. . w(n0 ) l. c(e0 ) k,l. w(n0 ) l. ⎪ ⎪ ⎪ ⎬ . ⎪ ⎪ ⎪ ⎭. ⎫. c(e0 ) k,l. ns ∈seq ≺ max ,s k. . ns ,ns ∈seq ≺ max ,s (i), k l e0 ∈E0 k,l. w(nsk ) +. nS ∈cls S (i)∩seq max ,S k. . ns ,ns ∈seq ≺ max ,s , k l e0 ∈E0 k,l. . ≺ sl w (GS cls ) − len(seq max ,S ).. ΔLw,up. An upper bound of ΔLw .. たす部分経路 p （表 2 で定義）のうち，その中の要素 nsk ，nsl が以下の条件を満たすもの s ≺ s s nsk ∈ seq ≺ max ,s , nl ∈ seq max ,s , nk ∈ pred (nl ), nk , nl ∈ cls(i).. ⎪ ⎪ ⎪ ⎭. 0 seq ≺ max ,s (i) も複数存在する．Gorg ，すなわち Gcls のスケジュール長はクリティカルパス長. であり，cp と表す．また，各経路 p においてタスクサイズの総和をそれぞれ算出し，その中の最大値を cp w とする．gmax (n0k ) を n0k の粒度6) の最大値，gmin を G0cls 内のタスク粒度の最小値6) とする． 5 例 4.3.1. seq max ,s ，seq ≺ max ,s の意味を例をあげて述べる．図 2 において，sl w (Gcls ) =. ⎪ ⎪ ⎪ ⎬ .. c(e0k,l ).. c(e0k,l ).. ≺ w(nS k ) − len(seq max ,S (i)).. ΔLw. ≺ 辺との和集合とする．すなわち seq ≺ max ,s (i) は，1 つの seq max ,s における，以下の条件を満. ≺ ≺ seq ≺ max ,s について，seq max ,s (i) は 1 つのみ存在する．また，seq max ,s が複数存在すれば，. min n0 ∈suc(n0 ) l k. min n0 ∈suc(n0 ) l k. nsk ∈ seq max ,s , nsl ∈ seq max ,s , nsk ∈ pred (nsl ). ≺ seq max ,s に属するのは互いに先行関係のあるタスクとこれらタスク間の辺であるので，seq max ,s s s s s に属するタスクのうち，seq ≺ max ,s は複数存在しうる（たとえば seq max ,s を {n1 , n2 , n3 , n4 } とすると，{ns1 , ns2 , ns4 } ∪ {es1,2 , es2,4 } と {ns1 , ns3 , ns4 } ∪ {es1,3 , es3,4 } といった 2 つの経路が存．在すれば，これら 2 経路がそれぞれ seq ≺ max ,s である） ≺ ≺ seq max ,s (i) を seq max ,s に属するタスクの中で，cls s (i) に属するものとそれらタスク間の. ≺ seq ≺ max ,s (i) は部分経路の集合であり，seq max ,s の部分集合でもある．そのため，1 つの. S sl w (GS cls ) − sl w (Gorg ) = sl w (Gcls ) − cp.. Δsl w,up. len(seq ≺ max ,s ). w(n0 ) j. . ⎪ max c(e0 ) ⎪ ⎪ j,k ⎩ n0 ∈pred(n0 ) j k 0 ⎧ ⎪ max w(n ) ⎪ j ⎪ n0 ∈pred(n0 ) ⎨. n0 ∈V 0 k cls. Δsl w len(seq ≺ max ,s (i)). k. . で，その中の要素 nsk ，nsl および esk,l が，下記の条件を満たすものである．. の和集合である（すなわち部分経路の和集合）．. Critical path length of G0cls . ⎫ ⎧ ⎪ ⎪ ⎬ ⎨ 0 max w(nk ) . ⎪ p∈G0 ⎪ 0 ⎭ ⎩ n ∈p cls. cp w. gmin. {w(cls S (i))} − δ. of clusters in which at least one task belongs to seq ≺ max ,s .. cp. 2),6). seq ≺ max ,s .. ≺ スク集合と辺の集合で，表 2 で定義）か（seq ≺ max ,s ）を定義する．seq max ,s は 1 つの経路 p. level (n52 ) である．cls 5 (1) 内で n52 の前に実行され，かつ n52 と先行関係にあるタスク集 5 5 5 5 合は {n51 } であるから，seq ≺ max ,5 (1) = {n1 , n2 } ∪ {e1,2 } である．また，blevel (n2 ) = 5 w(n52 ) + c(e52,7 ) + blevel (n57 )，seq ≺ max ,5 (4) = {n7 } である．よって， 5 5 5 5 5 seq ≺ max ,5 = {n1 , n2 , n7 } ∪ {e1,2 , e2,7 }. である．一方，cls 5 (1) 内で n52 よりも先に実行できるのは {n51 , n53 , n55 } である．そして，前述のように blevel (n52 ) = w(n52 ) + c(e52,7 ) + blevel (n57 ) であるから，seq max ,5 = {n51 , n52 , n53 , n55 , n57 } である．例 4.3.2. 図 3 に，seq max ,s ，seq ≺ （1）では cls s (i) およ max ,s 算出のさらなる例を示す．（2）では cls s (i) および cls s (i + 1) が linear であり，sl w (Gscls ) = level (ns3 ) の場合，び cls s (i + 1) がいずれも linear でなく，sl w (Gscls ) = level (ns9 ) である場合のクラスタ構成を示す．また，破線矢印は sl w (Gscls ) を構成するタスクの実行順である．（1）では. 情報処理学会論文誌. コンピューティングシステム. Vol. 4. No. 1. 111–146 (Feb. 2011). c 2011 Information Processing Society of Japan .

(8) 118. 計算資源の有効利用を目的としたタスククラスタリング. sl w (Gorg ) = sl w (G0cls ) =. . max. cls 0 (i)∈V 0. . {LV0 (i)}. . cls. . = max level (n0k ) = max tlevel (n0k ) + blevel (n0k ) n0 ∈V0 k. n0 ∈V0 k. (8). S S である．表 1 の tlevel (nS k )，(nk ∈ top S (i)) と blevel (nk ) の定義により，式 (8) において. sl w (Gorg ) = cp = sl (Gorg ). (9). が成り立つ．したがって，sl w (GS ， cls ) と sl w (Gorg ) との差を Δsl w とすると（表 2 で定義） S Δsl w は sl w (Gcls ) と cp との差と等しい（表 2 で定義）．しかしながら，4.3 節で述べたように各クラスタ内のタスク組はタスク集約方針によって決まるので，タスククラスタリング前では Δsl w は算出できない．そこで，Δsl w の上限値 Δsl w,up （表 2 で定義）を算出する．まず，seq max ,S 内のタスクが属する 1 つのクラスタを cls S (i) とする．cls S (i), w(cls S (i)) ≥. δ である cls S (i) が生成されることによって，cls S (i) の中で，seq max ,S に属するが seq ≺ max ,S (i) には属さないタスクのタスクサイズ和と，seq ≺ max ,S (i) で局所化された通信のデータサイズ和との差を ΔLi とする（表 2 で定義）．すなわち ΔLi は，cls S (i) において，seq ≺ max ,S (i) 内のタスクと先行関係のないタスクの. sl w (Gscls ). 図3 に関する定義の例 Fig. 3 Concept of upper bound of sl w (Gscls ).. タスクサイズの和と，局所化された seq ≺ max ,S (i) 内のデータサイズとの差によって得られる．そして，seq ≺ max ,S (i) に属するタスクのタスクサイズ和と，それらタスク間の，Gorg におけ. cls s (i) および cls s (i + 1) が linear のため，これら 2 つのクラスタ内タスクの実行順は. ≺ る通信のデータサイズ和との総和を len(seq ≺ max ,S (i)) とする．さらに，seq max ,S に属する. s s s s s 一意である．その結果，seq max ,s と seq ≺ max ,s には，いずれも {n1 , n2 , n3 , n4 , n5 } が属す. タスクのタスクサイズ和と，それらタスク間の，G0cls における通信のデータサイズ和との. る．（2）では，破線矢印および破線枠内のタスクが seq max ,s に属していることを示す．こ. ≺ 総和を len(seq ≺ max ,S ) とする．4.3 節で述べたように，seq max ,S は複数存在しうる．すなわ. こで sl w (Gscls ) = level (ns9 ) とすると，tlevel (ns9 ) = tlevel (ns5 ) + w(ns6 ) + w(ns8 ) + w(ns7 )，. ち，seq ≺ max ,S は Gorg におけるクリティカルパスとは限らないので，. = + + blevel (ns11 ) である．ns4 は破線枠内にある ns2 ，ns3 の後に実行させることによってできるだけ ns4 の開始時刻を遅らせている（つまり tlevel (ns4 ) = tlevel (ns1 ) + w(ns2 ) + w(ns3 )）．また，ns1 ，ns2 ，ns4 が先行関係にあるため，seq ≺ max ,s (i) は s s s s s {n1 , n2 , n4 } ∪ {e1,2 , e2,4 } である．cls s (i + 1) において seq max ,s 上にあり，かつ先行関係の s s s s s あるものは ns5 ，ns7 ，ns9 であるので，seq ≺ max ,s (i + 1) = {n5 , n7 , n9 } ∪ {e5,7 , e7,9 } である． blevel (ns9 ). w(ns9 ). c(es9,11 ). 4.4 δ と sl w (GS cls ) の関係 2.1 G0cls. 節で述べたように，G0cls. (10). ≺ が成り立つ．そして ΔLw を sl w (GS cls ) と len(seq max ,S ) との差（表 S S Δsl w = sl w (Gcls ) − cp ≤ sl w (Gcls ) − len(seq ≺ max ,S ) = ΔLw ,. 2 で定義）とすると，. ⇔ Δsl w ≤ ΔLw. (11). が成り立つ．ΔLw の上限値を ΔLw,up （表 2 で定義）とすれば，ΔLw,up は Δsl w の上限値でもある．そこで，ΔLw,up を求め，そして Δsl w,up = ΔLw,up とする．次に，ΔLw,up の算出方針について述べる．まず，ΔLi の上限値を求める．この値を seq max ,S. においては各クラスタに 1 タスクのみが属しているので，. = Gorg のスケジュール長は cp である．さらに. G0cls. = Gorg では. {n0k }. = cls 0 (i) ∈. コンピューティングシステム. 0 Vcls. 内のタスクが属するクラスタ数分だけ加算することにより，ΔLw,up を求める方針とする．クラスタ内で先行関係のないタスク数が増加すればするほど，top S 以外のタスクの tlevel 値が大きくなりうる．その結果，seq ≺ max ,S 内のタスクが属する各クラスタが linear である. であるから，式 (7) より，. 情報処理学会論文誌. len(seq ≺ max ,S ) ≤ cp. Vol. 4. No. 1. 111–146 (Feb. 2011). c 2011 Information Processing Society of Japan .

(9) 119. 計算資源の有効利用を目的としたタスククラスタリング. か否かで ΔLi の上限値が異なるものと考えられる．そのため，seq ≺ max ,S 内のタスクが属する各クラスタのうち，linear であるクラスタ cls S (i) について ΔLi の上限値と，linear でない各クラスタ cls S (j) について ΔLj の上限値をそれぞれ求める．そして，seq max ,S 内のタスクが属するクラスタ数のうち，linear であるクラスタ数とそうでないクラスタ数分だけ. ΔLi の上限値および ΔLj の上限値を加算して，ΔLw,up を求める．例 4.4.1. 図 3 (1) において s = S とすると， s s ΔLi = w(ns1 ) + w(ns2 ) + w(ns3 ) − len(seq ≺ max ,s (i)) = −(c(e1,2 ) + c(e2,3 )), s ΔLi+1 = w(ns4 ) + w(ns5 ) − len(seq ≺ max ,s (i + 1)) = −c(e4,5 ).. である．一方，図 3 (2) において s = S とすると，. ΔLi =. 4. s s s w(nsk ) − len(seq ≺ max ,s (i)) = w(n3 ) − (c(e1,2 ) + c(e2,4 )),. 図 4 nsEND(i) と nsSTART (i) の例 Fig. 4 An example of nsEND(i) and nsSTART (i) .. k=1. ΔLi+1 =. 9. s s s s w(nsk ) − len(seq ≺ max ,s (i + 1)) = w(n6 ) + w(n8 ) − (c(e5,7 ) + c(e7,9 )).. ΔLi は. k=5. である．. ΔLi = −. 4.5 ΔLi の上限値の算出. seq ≺ max ,S 内のタスクが属する 1 クラスタ cls S (i) が linear であるとき cls S (i)，w(cls S (i)) ≥ δ を生成することにより，seq ≺ max ,S (i) に属するタスク間のデー. −ΔLi =. S S ≺ ψi = seq ≺ max ,S (i) ∪ {nSTART (i+1) | nEND(i) ∈ seq max ,S (i),. =. S S ≺ nS END(i) ⊀ nk for ∀nk ∈ seq max ,S (i),. / seq ≺ eS END(i),START (i+1) ∈ max ,S (i), (12). ≺ と定義する．すなわち式 (12) において，nS END(i) は seq max ,S (i) 内のタスクで最後に実. と. nS START (i+1). は局所化されていないことを意味する（たとえば図. =. 情報処理学会論文誌. ns9. 間の通信 eS END(i),ST ART (i+1) 4 の場合では，nsEND(i) = ns6 ，. c(eS m,n ) ≥. ≺ S nS m ,nn ∈seq max ,S (i),. w(nS n) gmax (nS m). S nS n ∈suc(nm ). nS ∈seq ≺ (i), k max ,S nS ∈ψi ,nS ∈suc(nS ) l l k. ≺ S S nS START (i+1) ∈ seq max ,S (i + 1), nSTART (i+1) ∈ suc(nEND(i) ),. eS / seq ≺ END(i),START (i+1) ∈ max ,S (i + 1)}. ≺ eS m,n ∈seq max ,S (i). タ転送が局所化される．また，. nsSTART (i+1). (13). となる．また，表 2 の gmax (nS k ) を式 (13) に適用すると，. おける ΔLi の上限値を求める．. 行されるタスクである．また，nS END(i). c(eS m,n ). ≺ eS m,n ∈seq max,S (i). まず，以下の ( 1 )，( 2 ) の場合に分けて，linear であるクラスタとそうでないクラスタに. (1). w(nS w(nS START (i+1) ) l ) − S gmax (nk ) gmax (nS END(i) ). (14). となる（式 (14) の ψi は，式 (12) で定義）．したがって，以下が成り立つ．. ΔLi ≤. w(nS START (i+1) ) gmax (nS ) END(i). −. w(nS l ) . gmax (nS k). nS ∈seq ≺ (i), k max ,S. (15). nS ∈ψi ,nS ∈suc(nS ) l. l. k. である）．. コンピューティングシステム. Vol. 4. No. 1. 111–146 (Feb. 2011). c 2011 Information Processing Society of Japan .

(10) 120. (2). 計算資源の有効利用を目的としたタスククラスタリング. seq ≺ max ,S 内のタスクが属する 1 クラスタ cls S (i) が linear でないとき. を満たすクラスタの添え字を i = 1, 2, . . . , φ − y ，式 (16) を満たすクラスタの添え字を. ここでクラスタサイズの最大値を δ + wmax として（wmax は表 2 で定義），ΔLi の. j = φ − y + 1, φ − y + 2, . . . . , φ とすると，. 上限値を算出する．seq ≺ max ,S (i). ⎛. に属するタスク以外がすべて先行関係のないタスク. とすると，式 (15) の結果の導出と同様にして，以下が成り立つ．. ΔLi ≤ (δ + wmax ) −. w(nS k). −. nS ∈seq ≺ (i) max ,S k. ≤ (δ + wmax ) −. gmax (nS END(i) ). φ−y ⎜. ⎜ w(nSSTART (i+1) ) ⎜ − ⎜ gmax (nS END(i) ) i=1 ⎝. w(nS k). k. +. ΔLw ≤. c(eS p,q ). ≺ eS p,q ∈seq max ,S (i). nS ∈seq ≺ (i) max ,S. w(nS START (i+1) ). −. nS ∈seq ≺ (i), k max ,S. ⎞. w(nS l ) . gmax (nS k). nS ∈seq ≺ (i), k max ,S l. l. k. (16). ⎛. ⎞. ⎜ ⎜ w(nSSTART (j+1) ) ⎜ − + ⎜ gmax (nS END(j) ) j=φ−y+1 ⎝ φ. 4.6 ΔLw ,up の算出は互いに先行関係のあるタスク集合，すな. ΔLw ≤. φ. w(nS START (i+1) ) i=1. を φmax とすると，. φ≤. w. δ. (17). とできる．ここで cp w は 1 経路に属するタスクサイズ和の最大値（表 2 で定義）である．一方，任意の. seq ≺ max ,S (i). について，seq ≺ max ,S (i). に属するタスクサイズの和が δ 未満である. 場合を考える．seq max ,S に属するタスク（かつタスクサイズが δ 未満）がすべて別クラスタに属する場合，seq max ,S には 1 経路内のタスクが属することになる．したがって，φmax （a）まず，seq ≺ max ,S (i) に属するタスクのサイズ和が δ 以上であることが任意の cls S (i) で成り立つ場合を考える．. えられた上限値を y 個分加算したものとの総和で抑えられる．便宜上，ここで式 (15). コンピューティングシステム. Vol. 4. No. 1. 111–146 (Feb. 2011). k. −. φ. w(nS l ) + y(δ + wmax ) gmax (nS k). i=1 nS ∈seq ≺ (i), k max ,S. ∈ψi ,nS ∈suc(nS ) nS l l k. w(nS k). (19). k. である．式 (19) において φ. w(nS START (i+1) ) i=1. min. gmax (nS END(i) ). p∈G0 cls. ⎧ ⎪ ⎪ ⎪ ⎨. ⎪ ⎪ 0 0 ⎪ ⎩ nkS,nl ∈p, S. ≤ φmax max. l. y. maxnS ∈V S l. k. ⎫ ⎪ ⎪ ⎪ ⎬. w(nS l ) ≤ S gmax (nk ) ⎪ ⎪ ⎪ ⎭. k. w(nS k). . w(nS l ). φ. ,. w(nS l ) , gmax (nS k). i=1 nS ∈seq ≺ (i), k max ,S. nS ∈ψi ,nS ∈suc(nS ) l. ≥0. cls. gmax (nS k). nS ∈VS. n ∈suc(n ). linear であるクラスタ数を φ − y ，linear でないクラスタ数を y とする（y は 0 以上の整数）と，ΔLw は式 (15) で得られた上限値を φ − y 個分加算したものと，式 (16) で. l. nS ∈seq ≺ (j) max ,S. は 1 経路に属するタスク数の最大値となる．. 情報処理学会論文誌. gmax (nS END(i) ). −y. cp ≤ w = φmax δ. (18). である．式 (18) の右辺を整理すると，. で成り立つ場合，seq ≺ ，φ の上限値 max ,S 内のタスクが属するクラスタ数を φ（表 2 で定義）.

(11) cp . ⎟ w(nS l ) ⎟ ⎟ gmax (nS ) k ⎠. nS ∈seq ≺ (i), k max ,S l. わち 1 つの経路に属するタスク集合である．そのため，まずは 1 経路上のクラスタ数の上限値を求める．seq ≺ max ,S (i) に属するタスクサイズの和が δ 以上であることが任意の cls S (i). ⎟. nS ∈ψi ,nS ∈suc(nS ). 次に ΔLw,up を求める．そのためには，seq max ,S 内のタスクが属するクラスタの個数を求める必要がある．表 2. k. w(nS k). nS ∈seq ≺ (j) max ,S. nS ∈ψi ,nS ∈suc(nS ) l l k. の定義より，seq ≺ max ,S. ⎟ w(nS l ) ⎟ + y(δ + wmax ) S ⎟ gmax (nk ) ⎠. nS ∈ψi ,nS ∈suc(nS ). −y. ⎟. l. k. (20). nS ∈seq ≺ (j) max ,S k. c 2011 Information Processing Society of Japan .

(12) 121. 計算資源の有効利用を目的としたタスククラスタリング. であるから，. ΔLw ≤ φmax max. nS ∈VS k. ⎧ ⎫ w(nS ⎪ l ) ⎪ ⎨ nSmax ⎬ ∈V S l. ⎪ ⎩. cls. gmax (nS k). ⎪ ⎭. − min. p∈G0 cls. ⎧ ⎪ ⎪ ⎪ ⎨. ⎪ ⎪ 0 0 ⎪ ⎩ nkS,nl ∈p, S. φ. w(nS START (i+1) ) gmax (nS END(i) ) i=1. ⎫ ⎪ ⎪ ⎪ ⎬. w(nS l ) gmax (nS k)⎪ ⎪. ⎧ ⎪ ⎪ ⎪ ⎨. ⎪ ⎭. nl ∈suc(nk ). min. + y(δ + wmax ) = ΔLw,up. (21). Δsl w,up. cp = w max δ nSk ∈VS ⎪ ⎩. l. cls. gmax (nS k). ⎪ ⎭. cls. ⎪ ⎪ 0 0 ⎪ ⎩ nkS,nl ∈p, S. nS ∈VS k. ⎫ ⎪ ⎪ ⎪ ⎬. l. − min p∈G0. cls. ⎧ ⎪ ⎪ ⎪ ⎨. ⎫ ⎪ ⎪ ⎪ ⎬. ⎪ ⎪ 0 0 ⎪ ⎩ nkS,nl ∈p, S. w(nS l ) gmax (nS k)⎪ ⎪. ⎪ ⎭. l. (22). w(nS l ) , gmax (nS k). i=1 nS ∈seq ≺ (i), k max ,S. nS ∈ψi ,nS ∈suc(nS ) l. l. k. (25). k. であるから，. Δsl w,up = Tmax max. nS ∈VS k. とする．式 (22) において，第 2 項は G0cls の 1 経路上に存在するデータサイズの下限値. ⎧ ⎫ w(nS ⎪ l ) ⎪ ⎨ nSmax ⎬ S ∈V l. ⎪ ⎩. cls. gmax (nS k). ⎪ ⎭. − min p∈G0. cls. ⎧ ⎪ ⎪ ⎪ ⎨. ⎫ ⎪ ⎪ ⎪ ⎬. ⎪ ⎪ 0 0 ⎪ ⎩ nkS,nl ∈p, S. n ∈suc(n ). の総和の最小値であるから，δ に依存しない．このことをふまえて式 (22) を δ につい. l. + y(δ + wmax ). て微分すると，. ⎧ ⎫ ⎧ ⎫ max {w(nS {w(n0l )}⎬ l )}⎬ ⎨ ⎨nmax S S 0 ∈V 0 nl ∈Vcls l cls δ = cp w max = cp w max 0 gmax (nS ⎭ n0 ∈V0 ⎩ gmax (nk )y ⎭ nS ∈VS ⎩ k )y k k. ,. nS ∈seq ≺ (j) max ,S. k. + y(δ + wmax ). ⎪ ⎭. w(nS k) ≥ 0. ⎪ ⎭. n ∈suc(n ). cls. gmax (nS k). φ. k. y. l. ⎪ ⎩. w(nS l ) ≤ gmax (nS ) k ⎪ ⎪. n ∈suc(n ). である．よって式 (11) と式 (17) の φmax の定義より，. ⎧ ⎫ w(nS ⎪ l ) ⎪ ⎨ nSmax ⎬ ∈V S. p∈G0. ≤ Tmax max. ⎧ ⎫ w(nS ⎪ l ) ⎪ ⎨ nSmax ⎬ ∈V S. w(nS l ) gmax (nS k)⎪ ⎪. ⎪ ⎭. k. (26). である．すなわちこの場合は，δ の増加にともない，Δsl w,up が増加することになる．. (23). 4.7 δopt の決定以上の結果より，seq max ,S 内のタスクが属するクラスタ cls(i) について，任意の seq ≺ max ,S (i) 内のタスクのサイズ和が δ 以上か否かで Δsl w,up の振舞いが異なることが分かった．4.6 節. のときに Δsl w,up は極小値をとる．式 (23) より，y > 0 であれば，δ については Δsl w,up. （a）のとき，y > 0 かつ wmax が固定であれば，Δsl w,up は極小値をとる．しかしながら. に極小値が存在する．しかしながら δ を固定させて wmax を増加させると，Δsl w,up も. 4.6 節（b）の場合では，δ の増加にともなって Δsl w,up も増加する．このことから，s 回. 増加する．. のタスク集約後において seq ≺ max ,s (i) 内のタスクと先行関係のないタスクを集約することは，. （b）次に，少なくとも 1 つの seq ≺ max ,S (i) に属するタスクサイズ和が δ 未満である場合を 0 考える．seq ≺ max ,S 上に存在するクラスタ数を φ，Gcls の各経路 p に属するタスク数の. Δsl w,up の増加につながりうる．式 (23) において，y = 0 のときは seq ≺ max ,S 内のタスクが属するクラスタがすべて linear. 最大値を Tmax とすると，φ ≤ Tmax となる．Tmax は Gorg で決まり，δ に依存しない．. の場合に相当し，Δsl w,up は単調減少である．しかしながら，少なくとも 1 クラスタが linear. したがってこの場合は. でなくなるのは δ がどの値であるときかは，タスク集約前では分からない．y

(13) = 0 の場合，. φ ≤ Tmax = φmax. (24). となる（φ は表 2 で定義，φmax は φ の上限値）．この場合，式 (19) において. Δsl w,up が最小となるのは，δ が式 (23) の右辺と一致するときである．式 (23) の右辺において y が増加すると linear でないクラスタが多くなり，sl w (GS cls ) の上限値が増加してしまう．そのため，ここでは y = 1 として，できるだけ sl w (GS cls ) の上限値が減少している場合. 情報処理学会論文誌. コンピューティングシステム. Vol. 4. No. 1. 111–146 (Feb. 2011). c 2011 Information Processing Society of Japan .

(14) 122. 計算資源の有効利用を目的としたタスククラスタリング. を考え，δopt の値を. δopt. タ内のタスクに先行関係が存在することが必要である．この場合の sl w (GS cls ) は各タスクの. ⎧ ⎫ {w(n0l )} ⎬ ⎨ nmax 0 ∈V 0 l cls = cp w max gmax (n0k ) ⎭ n0 ∈V0 ⎩ k. データ待ち時間なしで，かつ各タスクができるだけ早く実行開始させる状況のスケジュール長である．そのため，sl w (GS cls ) を減少させることがデータ受信待ちのないという理想的な. (27). スケジュール長を短縮させることになるので，式 (31) の結果につながっている．また，seq ≺ max ,S に属する辺は局所化されたものとそうでないものが存在する．さらに，. seq ≺ max ,S に属する辺は，クリティカルパス上の辺とは限らない．したがって，以下が成り立つ．. とする．. 4.8 sl w (GS cls ) とスケジュール長との関係 S ここでは sl w (GS cls ) の変動が sl (Gcls ) にどのように影響するかを考察する．まず，文献. 2) − max. で証明されている以下の 2 つの補題をあげる．補題 1. cp ≤ (1 +. 1 gmin. p∈G0. cls. )cp w .. − cp ≤ Δsl w,up. (28). である．さらに補題 1 より，式 (28) は. . sl w (GS cls ) − 1 +. . 1 cp w ≤ sl w (GS cls ) − cp ≤ Δsl w,up gmin. − 1+. である．したがって. . 1. . gmin. sl (GS cls ). ≤. sl w (GS cls ). . − 1+. 1 gmin. ⎪ ⎪ ⎪ ⎭. (29). ⇔ − max. ⎧ ⎪ ⎪ ⎪ ⎨. ⎪ cls ⎪ 0 0 ⎪ ⎩ nk0 ,nl ∈p,. c(e0k,l ). p∈G0. n ∈pred(n0 ). . k. cp w. ≤ sl w (GS cls ) − cp.. ⎫ ⎪ ⎪ ⎪ ⎬. l. (30) S ⇔ sl (GS cls ) ≤ sl w (Gcls ) + max. (32). . S ≤ sl w (GS cls ) − sl (Gcls ). ⎪ ⎪ ⎪ ⎭ ⎧ ⎪ ⎪ ⎪ ⎨. p∈G0 cls. 1 sl (GS cls ) ≤ Δsl w,up gmin sl w (GS cls ) − Δsl w,up ⇔ sl (GS cls ) ≥ 1 1 + gmin. sl w (GS cls ) − 1 +. c(e0k,l ). S S sl w (GS cls ) − cp ≤ sl w (Gcls ) − sl (Gcls ). . となる．さらに補題 2 より，. sl w (GS cls ). ⎪ ⎪ 0 0 ⎪ ⎩ nk0 ,nl ∈p,. さらに，sl (GS cls ) ≤ cp である場合に限り，以下が成り立つ．. 次に Δsl w,up と sl (GS cls ) の関係について述べる．まず，式 (11) より. Δsl w =. ⎫ ⎪ ⎪ ⎪ ⎬. nk ∈pred(n0 ) l. 補題 2. cp w ≤ sl (GS cls ).. sl w (GS cls ). ⎧ ⎪ ⎪ ⎪ ⎨. ⎫ ⎪ ⎪ ⎪ ⎬. ⎪ ⎪ 0 0 ⎪ ⎩ nk0 ,nl ∈p,. c(e0k,l ). n ∈pred(n0 ) k. (31). ⎪ ⎪ ⎪ ⎭. , if sl (GS cls ) ≤ cp.. (33). l. S 式 (33) より，sl w (GS cls ) がクリティカルパス長以下となるという制約を課すると，sl w (Gcls ). を減少させることは sl (GS cls ) の上限値を抑えることにつながる．. となる．式 (22) において，Δsl w,up は，δ によって変動する．そのため，δopt を決めれば式 (22) における Δsl w,up は固定である．式 (31) から，δopt を決めたうえで Δsl w,up を最. 5. タスククラスタリングアルゴリズム. 小化する（または減少させる）ようにタスクを集約することは，スケジュール長の下限値を. 5.1 アルゴリズムの要件. 減少させることになるといえる．. 4 章では，sl w (GS cls ) の上限値が最小化されるときのクラスタサイズの下限値 δopt を算出. 4.2 節で定義したように，sl w (Gscls ) は，各クラスタ cls s (i) について nsk ∈ in S (i)，. し，sl w (GS cls ) を減少させるようなタスク集約を行うことによってスケジュール長がとりう. nsk ∈ / top s (i) であるようなタスク nsk について，tlevel (nsk ) の算出には nsk におけるデー. る下限値を減少させることを示した．ゆえに実際にタスク集約を行うタスククラスタリング. タ待ち時間は考慮していない．また，sl w (GS cls ) の上限値を最小化させるためには各クラス. のためには，以下の方針が必要である．. 情報処理学会論文誌. コンピューティングシステム. Vol. 4. No. 1. 111–146 (Feb. 2011). c 2011 Information Processing Society of Japan .

(15) 123. 計算資源の有効利用を目的としたタスククラスタリング. INPUT: Gorg OUTPUT: GS cls Define UEX s as a set of clusters which satisfy eq. (34).; Define RDY s as a set of clusters which statisfy eq. (35).; 0 ← nk , cls 0 (k) = {n0 } and put cls 0 (k) into Vcls . For each nk ∈ V , let n0 k k 0. Derive δopt by eq. (27). 0 0 ) = ∅}; 1. E0 ← E, UEX 0 ← Vcls , RDY 0 ← {cls 0 (k) | cls 0 (k) = {nk }, pred(n0 k 2. WHILE UEX s = ∅ DO 3. pivot s ← getPivot(RDY s ); /* detailed in Sec. 5.5. */ 4. target s ← getTarget(pivot s ); /* Detailed in Sec. 5.6.2. */ 5. RDY s+1 ← clustering(pivot s , target s ); /* Detailed in Sec. 5.7. */ 6. ENDWHILE ; 7. RETURN GS cls. 図 5 タスククラスタリングの処理概要 Fig. 5 Whole procedures of our proposing task clustering.. の集合を UEX s 内で保持する．. {cls s (i) | w(cls s (i)) < δopt }. s タスク集約前では，Vcls. (34). に属する各クラスタ（このときは各クラスタには 1 タスクのみが属. している）は UEX s に属するものとする．（iii）より，タスク集アルゴリズムの主要な処理は図 5 行 2 から行 6 である．5.1 節（ii）， s+1 s ≺ 約によってできるだけ sl w (Gs+1 cls ) を減少させる（sl w (Gcls ) > sl w (Gcls )）ために，seq max ,s. 内のタスクが属し，かつクラスタサイズが δopt 未満である 2 つのクラスタを選択する．そしてそれらを 1 つのクラスタに集約することによってクラスタサイズを大きくする．ここで，RDY s というクラスタ集合（5.4 節で定義）からある優先度に従って選択された 1 クラスタを pivot s と定義する（図 5 行 3）．そして pivot s 内のタスクと先行関係を持つタスクが. （i）各クラスタサイズが δopt 以上となるまでタスク集約を行う. 属するクラスタを target s（5.6 節で定義）として選択する（図 5 行 4）．さらに，pivot s と. 各クラスタサイズが式 (27) で定義した δopt 以上となるようにタスク集約を行うことに. target s を集約して 1 つのクラスタとする（図 5 行 5）．タスク集約後，target s 内の全タス. より，少なくとも sl w (GS cls ) がとりうる上限値が最小化されるようなクラスタ集合が得. クは pivot s であったクラスタに含まれることになるので，UEX s+1 および RDY s+1（もし. target s ∈ RDY s であれば）には target s であったクラスタを含めない．図 5 行 5 ではさら. られることになる．（ii）seq ≺ max ,s 内のタスクに対し，先行関係のあるタスクを集約する. に，pivot s と target s の集約後に pivot s であったクラスタのクラスタサイズが δopt 以上と. ≺ 4.6 節（a）で得られた結果より，sl w (GS cls ) の上限値を減少させるためには，seq max ,s. なれば，UEX s+1 および RDY s+1 から pivot s を除外する．また，以降のタスク集約で必要. 内のタスクが属する任意のクラスタ cls s (i)（w(cls s (i)) < δ ）に対し，seq ≺ max ,s (i) 内の. な pivot s+1 選択優先度の更新，および RDY s+1 へ新規にクラスタを追加する（図 5 行 5 の. タスクと先行関係にあるタスクを集約することが必要である．. 処理は，5.7 節で述べる）．全クラスタのサイズが δopt 以上となると（すなわち UEX S = ∅. （iii）タスク集約により，sl w (Gscls ). のとき），アルゴリズムは終了する．このアルゴリズムによって sl w (GS cls ) を減少させるた. をできるだけ最小化する. 4.8 節で得られた結果より，タスク集約によって. sl w (GS cls ). をできるだけ減少させるこ. めの考慮点として，以下の点を決める必要がある．. とができればスケジュール長がとりうる下限値も減少する．さらに（ii）の要件を満た. (1). 計算量と性能を考慮した，タスク集約方針. S すことによって sl w (GS cls ) の上限値が減少するが，sl w (Gcls ) の実際の増分（減少分）は. (2). pivot s の選択基準（図 5 行 3）. タスク集約をしないと分からない．そのため，タスク集約においては，（ii）のように. (3). target s の選択基準（図 5 行 4）. s+1 seq ≺ max ,s 内のタスクが属するクラスタを可能な限り選択し，sl w (Gcls ) が最も減少され. (4). pivot s 選択優先度の更新方法（図 5 行 5）. 5.3 タスク集約方針. うるタスクを選択して集約する．. 5.2 アルゴリズムの概要. seq max ,s に属するタスクと先行関係のあるタスクが集約されると，sl w (Gs+1 cls ) は最大で局. 図 5 に，アルゴリズムの概要を示す．まず，初期状態の DAG を G0cls へ代入する（G0cls. ← Gorg ）．そして. 0 Vcls. ．また，所化されたタスク間の通信データサイズ分だけ減少する（sl w (Gscls ) > sl w (Gs+1 cls )）. における各タスクはそれぞれ，1 つのタスクから構成され. この集約によって先行関係のないタスクどうしが 1 クラスタに含まれると，sl w (Gs+1 cls ) が. 0 に対し，cls 0 (k) = {n0k } とするクラスタに属しているものとする．すなわち cls 0 (k) ∈ Vcls. ．そのため，seq max ,s 内のタスクが属する増加する可能性がある（sl w (Gscls ) < sl w (Gs+1 cls )）. る（cls 0 (1) = {n01 }, cls 0 (2) = {n02 }, . . .）．そして，5.1 節（i）を満たすためにはどのクラ. クラスタを pivot s としてタスク集約を行えば，sl w (Gs+1 cls ) が増減する可能性がある．各タ. スタが δopt 以上か否かを特定しなければならない．そこで，以下の条件を満たすクラスタ. スク集約の前（たとえば s + 1 回目のタスク集約前），seq max ,s 内のタスクが属するクラス. 情報処理学会論文誌. コンピューティングシステム. Vol. 4. No. 1. 111–146 (Feb. 2011). c 2011 Information Processing Society of Japan .

(16) 124. 計算資源の有効利用を目的としたタスククラスタリング. タのうち，LVs が最大のものを選択し，さらにタスク集約後の sl w (Gs+1 cls ) 値をできるだけ. る．また，たとえ seq max ,s 内のクラスタがすべて先行関係にあったとしても，上記 ( 2 ) の. 最小化できるようなクラスタを target s とする方針を考える．この場合，seq max ,s に属する. 方針では，seq max ,s 内のタスクと seq max ,s 以外のタスクの集約によって先行関係のないタ. タスクを求めるためには各クラスタの LVs 値の更新が必要であるが，次の問題がある．. スクどうしが 1 クラスタに属する可能性がある．すなわちクラスタサイズが δopt 以上とな. (1). 計算量の問題. s+1 s ．るまでタスク集約を行うことにより，sl w (Gs+1 cls ) が増加しうる（sl w (Gcls ) < sl w (Gcls )）. s−1 回目の pivot s−1 と target s−1 との集約の結果，どのタスク集合が新たな seq max ,s. そのため，アルゴリズム性能上の考慮点は，タスク集約ごとに seq max ,s や sl w (Gscls ) を決. となるかは DAG 全体を走査しないと分からない．Vs に属する各タスクの tlevel. めないという条件の下，いかにして pivot s ，target s の選択を行うことによって sl w (Gs+1 cls ). 値，blevel 値の更新にはそれぞれ |Vs | + |Es | ステップかかる．さらに 1 クラス. を減少（sl w (Gscls ) > sl w (Gs+1 cls )）させる（または増分を最小にする）ことにつなげるかと. タ cls s (i) について，T Ls (i)，BLs (i) の算出にはそれぞれ log |top s (i)| ステップ，. いうことである．. s log |out s (i)| ステップかかる．したがって Vcls 全体に対して LVs を更新するのに s |Vcls |(log |top s (i)| + log |out s (i)|). ステップかかる．そして，この処理が全クラスタサ. イズが δopt 以上となるまで繰り返される．その結果，1 度のタスク集約のみで UEX s から pivot s が除外されたとしても，DAG 全体を走査して各クラスタの LVs 値を更新するのにかかる計算量は Oall = O(|V |(|V | + |E|) + |V |2 log |V |) となる．一般に，タスククラスタリングにおいて計算量を減少させるための考慮点は，タスク集約優先度の更新処理である．従来のタスククラスタリングにおけるタスク集約優先. 以上のことをふまえて，pivot s を，以下の条件を満たすクラスタ集合から選択するものとする．. {cls s (r) | cls s (r) ∈ UEX s , pred (nsr ) = ∅, cls s (r) = {nsr }}. . ∪. cls s (r) | cls s (r) ∈ UEX s , cls s (q) ∈ / UEX s , nsq ∈ cls s (q), nsq ∈ pred (nsr ) for ∀nsr ∈ top s (r). . .. (35). 度は主にスケジュール長である．このうち，全走査によりスケジュール長の更新に. RDY s には，式 (35) の条件を満たすクラスタを保持するものとする．すなわち図 5 行 3. O(|E|(|V | + |E|)) の計算量を要するもの9) ，計算量を減少させるために走査範囲を一. のときの RDY s は，UEX s に属するクラスタのうちで 1 つの START タスクのみを要素と. 部のクラスタ集合に限定して O(|E| log |V |) または O(|V | log |V |) であるもの4) ，ス. するクラスタ集合か，またはその top s タスクの任意の直接先行タスクが属するクラスタサ. がある．全走査による LVs 値更新処理の計算. イズが δopt 以上であるものの集合である．図 5 行 5 における RDY s から RDY s+1 への更. 量 Oall は，全走査によるスケジュール長の更新処理の計算量 O(|E|(|V | + |E|)) より. 新（5.7 節で詳述）により，s + 1 回目のタスク集約前は，図 5 行 3 において RDY s+1 内. も大きいので，計算量の点では大きな問題となりうるといえる．. のすべてのクラスタサイズは δopt 未満である．すなわち図 5 行 5 の処理により，式 (35) で. sl w (Gscls ) の減少につながるとは限らないという問題. s ← s + 1 とした場合のクラスタ集合のみが RDY s+1 に属するようにしている．. 11). ケジュール長の更新は行わないもの. (2). 5.4 pivot s 選択範囲の定義とその影響. seq max ,s 内のタスクが属するすべてのクラスタのサイズが δopt 以上のとき，他のク. 図 5 行 1 では全クラスタを UEX s へ追加する．このときに RDY s へ追加されるのは，. ラスタのサイズが δopt 以上であるとは限らない．このような場合，5.1 節（i）を満. START タスクを要素に持つクラスタ集合のみである（図 5 行 1 では，各クラスタの要素. たすために seq max ,s に存在しないタスクが属するクラスタを pivot s とする必要があ. 数は 1 である）．. る．その結果，選択された pivot s と target s との集約によって seq max ,s+1 が更新さ. 次に，RDY s に属するクラスタ集合から pivot s を選択する方針が，各クラスタの LVs+1. < sl w (Gs+1 cls )）可能性がある．すなわち，つねに seq max ,s 内のタスクが属するクラスタを pivot s として選択しても，sl w (Gs+1 cls ) s+1 s が減少する（sl w (Gcls ) > sl w (Gcls )）とは限らない．. 値の増減にどう影響するかを述べる．まず，図 5 行 3 において RDY s に属するクラスタ. れ，sl w (Gs+1 cls ). が増加する（sl w (Gscls ). そこで，seq max ,s の特定および更新はせず，ある範囲内のクラスタ集合から pivot s を選. cls s (r) が pivot s として選択されたとする．そして，5.1 節（ii）の方針に従い，以下の集合に属する任意のクラスタ cls s (t) から 1 つを選択し，これを target s とする（target s の具体的な選択方針については 5.6 節で述べる）．. 択する．そして，タスク集約後は特定の範囲内のクラスタの LVs+1 の更新を行う方針とす. 情報処理学会論文誌. コンピューティングシステム. Vol. 4. No. 1. 111–146 (Feb. 2011). c 2011 Information Processing Society of Japan .