成蹊大学理工学研究報告
J. Fac. Sci. Tech., Seikei Univ.
Vol.44 No.1 (2007) pp.17-23

通信遅延を考慮したタスクスケジューリングのためのタスク粒度解析
尾高 輝*1，甲斐宗徳*2

Task Granularity Analysis for Task Scheduling Taking Account of Communication Overhead
Akira ODAKA*1, Munenori KAI*2
ABSTRACT ： Task scheduling problems belong to the class of strong NP-hard combinatorial
optimization problem. Taking account of communication overhead into task graphs makes theseproblems more difficult to solve by any search algorithms because the search spaces become larger. Inthis paper, we propose a task granularity analysis method in order to make the search spaces narrower
and to shorten the search time by task fusion. Some basic patterns and their conditions of partial taskgraphs to be merged into a single task are proposed. In order to shorten the schedule length as possible, atask duplication method is also proposed. We examine both methods to our search algorithm for
randomly generated task graphs and practical task graphs for the applications, such as robot control,
sparse matrix multiplication and SPEC fpppp, and obtain good effectiveness.
Keywords：task scheduling, task fusion, task duplication, heuristic algorithm, combinatorial optimization
problem（Received March 26, 2007）

１．はじめに信時間が無視できないほど，大きくかかってくるケースもある。通信遅延を考慮しない最適スケジュールにそのプロセッサの処理能力は年々向上しているが，ユーザまま通信を加えても最適解になっているとは限らないのの処理内容はより複雑化，大規模化している。従って単で，通信遅延を考慮したスケジューリングは非常に重要

一プロセッサによる処理では時間が掛かりすぎる場合がになってくる。しかし，タスク間の通信を考慮すると，ある。そこで処理速度を向上させるためにマルチプロセタスクの組み合わせが多くなり，探索空間は以前よりもッサシステムの研究が進められている。

さらに広大化することになる。つまりタスク数が少し増

マルチプロセッサシステムで効率よく高速に処理をさえるだけでも探索数は激増してしまう。そこで抽出されせるためには，マシンが持つ性能を十分に引き出す必要たタスクグラフの無駄な並列性をあらかじめ取り除くたがある。そこで並列実行可能なタスクを抽出し，そのタめにタスク融合を行い，探索空間を削減することで，効スク集合をスケジューリングすることが重要なキーポイ率の良い探索を行うことができる。このような理由からントとなる。しかし，このスケジューリング問題は，強スケジューリング前にスケジューリングアルゴリズムにNP 困難なクラスに属す組み合わせ最適化問題であり，す都合の良い粒度を決定することは非常に効果的である。

べてのケースで最適解を求める方法を得ることは，事実またタスクの粒度解析は，どんなスケジューリング手法上不可能であることが知られている。この問題に対して，の組み合わせに対しても有効である。

従来の優良なスケジューリング結果を求めるとされているスケジューリング手法がいくつかあるが，これらはタ２．タスクスケジューリング問題

スク間の通信時間を考慮していない。しかし実際には通タスクを節点，タスク間の先行制約を有向辺で表すこ*1：工学研究科情報処理専攻修士学生：情報処理専攻教授 (kai@st.seikei.ac.jp)*2とで，並列計算をモデル化したものがタスクグラフであ－17－

４．計算機モデルの定義

る。タスクグラフは閉路のない重み付き有向グラフである。タスク間の先行制約は，タスク間にデータ依存が存在することにより生じる。タスクの重みはタスクの実行

本研究の対象とする計算機モデルは，任意の方法で相にかかる時間を表す。図１にタスクグラフの例を示す。

互結合された均一のプロセッサにより構成される並列計

タスクスケジューリング問題とは，図 1 のようなタス算機である。プロセッサはそれ自身のプライベートメモ

クグラフを能力の等しい m 個のプロセッサに，先行制約リを持ち，共有メモリを持たない。プロセッサ間の通信のある n 個のタスクを，処理割り込みなしで割り当てるはすべて相互結合網を通して一台のプロセッサから一台という条件の下で，各タスクを与えられたプロセッサにのプロセッサに明示的にメッセージを送ることで行われ並列処理時間を最小にすることを目的にして割り当てをる。同じプロセッサ上で実行されるタスク間においてメ決定する最適化問題である。

ッセージの交換が必要な場合，データはローカルメモリから直接読み込まれる。先行制約を持つ２つのタスクが３．従来のスケジューリング手法異なるプロセッサで処理されるとき，プロセッサ間で生じる通信は並列処理に起因するオーバヘッドであり，

3．1

Oliver らは文献 3) において，図 2 のように取り扱うべきCP（Critical Path）法，CP/MISF(Critical Path/Most Immediate Successors First )法1)と述べている。図２はタスク A とタスク B が異なったプロセッサに割り当てられた時に生じる通信オーバヘッド

処理時間

タスクを表したもので，図中の各パラメータは以下の通りである。
0エッジ

T : タスクの処理時間

1eAB : タスク B とタスク B の間で必要とされるデー
1

5

2

4

タ授受のための通信時間
L : 通信リンク

654

7

Os : 送信準備のオーバヘッド
Or : 受信準備のオーバヘッド

6436

P : プロセッサ
Os と Or はシステムに依存する値で，eAB は送受信デー7

図１0

タの量に依存するものである。本研究では簡単のため
Os+eAB+Or を通信オーバヘッドとして取り扱うものとし，タスクグラフ

タスク A とタスク B が同じプロセッサに割り当てられたCP 法は通信を考慮していないヒューリスティックア

場合，通信時間は０とする。

ルゴリズムで，各タスクから最終タスクまでかかる処理時間の下限値（プライオリティレベル）を求め，これの大きいタスクほど実行優先順位を高くする。このプライP１

オリティレベルを基に，リストスケジューリングを行う。
CP/MISF 法は CP 法を改善したもので，同じプライオリサに割り当てる。

DF/IHS(Depth First/Implicit Heuristic Search)法

P２
L

P２

A

eAB

い方のプライオリティを高くし，先にアイドルプロセッ

3．2

P１

A TA

ティレベルが複数存在する時は，直接後続タスク数の多L

os

B TB

eAB
or1)

DF/IHS 法とは，
CP/MISF 法による優れたヒューリステ

B

ィック効果を取り入れた，分枝限定法(Branch＆Bound)timeによる，探索アルゴリズムである。分枝限定法は，現在求められている暫定解よりも良い解が得られそうな枝を図２探索し，良い解が得られそうにない部分木は下限値を使用し切り落としていく。

－18－

タスク間の通信

５．通信を考慮したスケジューリング

おける送受信パターンの削減法で，これは各タスクをプロセッサへ割り当てを行うにあたって，通信における送5．1

通信オーバヘッド受信パターンが格段に増大するので，効果的にスケジュタスク間での通信時間は無視できないほど大きいケーーリングを行うために，割り当てタスクの通信を受け取スがあるが，従来のスケジューリング手法ではタスク間る時間に注目し，スケジューリング結果が重複する確率の通信時間を考慮していない。通信遅延を考慮しない最の高い探索を行わない手法である。

適スケジュールにそのまま通信時間を加えても最適解に６．タスク粒度解析によるタスク融合なっているとは限らないので，本研究では，このような通信遅延を考慮したスケジューリングを行うためにDF/IHS 法の拡張を行った。

タスク融合を行うねらいは，タスク数を減らし，タス

図１のタスクグラフにおいて，先行制約のあるタスクク割り当ての組み合わせを減らすことで，探索空間を減間でデータ通信が行われる必要があるため，その通信時少させることによりヒューリスティック探索，全探索の間が各有向エッジに新しく付加されることになる。本研

両探索においてより早く有用な暫定解を求めることであ

究では，図３(a)に示すように，１つのプロセッサから他る。またプロセッサ資源の無駄を省くこともできる。のプロセッサへの通信は同時に行うことができず，図３(b)のように逐次的に通信しなければならないようなプ

6．1

タスク融合の概念

ロセッサ間の相互結合網を仮定する。ただし，送信元と図４のタスクグラフのように直接先行後続関係にある受信先のペアが異なる通信は同時に行なうことができる

タスク，または並列関係にあるタスク間においてタスクものとする。の融合はなされる。この処理時間は融合される前の２つのタスクの処理時間の和であり融合後のタスクの先行後続関係は崩れない。

AA

B

CCB

図３

マルチプロセッサ相互結合網と通信オーバヘッド(a)並列関係にあるタスク間の融合

図４5．2

3S(Shrinking Search Space)法(b)先行関係にあるタスク間の融合

タスク融合の仕方2)

通信遅延を考慮して全探索を行う際，各深さで割り当

6．2

通信時間の扱いてタスクの組み合わせだけでなく，通信によってスケジ

図５においてタスク A, B 間の送受信データとタスク

ューリング結果が異なるプロセッサへの割り当てに関す

A, C 間の送受信データに重複がある可能性があるので，る順列も考慮に入れなくてはならない。そのため探索空

タスク融合により通信時間を融合後の通信時間にどのよ間が以前よりも広大化することになる。そこで，スケジうに反映させるかで３種類の方法を用意した。

ュール候補をとる必要のない探索空間を分析して除外す

送受信データに重複がない場合

eAD= eAB+eAC

ることにより，実行時間の短縮をはかる。
３S 法においてキーとなる方法は３つある。１つめは，送受信データが完全に重複している場合

eAD= max{eAB,eAC}

必要なアイドルタスクの抽出法で，これはすべてのプロセッサへの割り当てを考慮した時に，必ずしもアイドル送受信データにいくらかの重複がある場合タスクが必要だとは限らないので，不要なアイドルタス

例えば eAB＞eAC で，20%の重複があると仮定する

クを割り当てない手法である。２つめは，タスク割り当とeAD= eAB+(eAC*0.8)て制限法で，これは各プロセッサへタスクを割り当てたときに，明らかに通信を無意味に行っている割り当てを見つけ，探索を行わない手法である。３つめは，通信に－19－いタスクを生成する。図７にこの手法が適用される基本パターンを示す。

AAeAB

eAC

BC
図５eAD
D
(a)

融合時の通信時間

図７6．3(b)タスク融合の基本パターン

タスク融合による通信オーバヘッドの軽減

タスク融合によって，複数回に分けて通信されていたこの手法では，タスクグラフ中で図 7 の様な部分タスデータが１回の通信にまとめられることで，通信回数をクグラフを取り出し，その最小並列処理時間が逐次処理削減し，オーバヘッドを軽減することができる。一般的時間より大きい場合にそれらのタスクを融合する。これに，通信オーバヘッドは無視できない大きさであるため，を融合条件とする。例えば図７(a)の様な部分タスクグラスケジューリングモデルにオーバヘッドを考慮すること

フにおいて，融合条件を満たした場合，図８のように部は精度の良い並列プログラムを生成するのに重要である。

分タスクグラフの最適なタスク割り当てを見て，同じプ

図６(a)は，３台のプロセッサ PE0，PE 1，PE 2 でタスクロセッサに割当てられているタスク同士を融合する。図

A，B，C を含む処理を実行する並列プログラムを模式化７(b)の場合も基本的に図７(a)と同じである。

したものである。タスク A，B を別のプロセッサで実行するため，PE1 への通信を２回行う。しかし，図 6(b)のA TAように，タスク B を PE 0 で実行することで，通信を１eAN回にまとめることができ，オーバヘッドの軽減につながM TM

B TB

eBNeMN

N TNる。タスク融合により，タスク A，B の処理が完了してから通信を開始することになるため，送信開始時刻が遅くなるが，この例では，受信オーバヘッド Or が１回でPE 0済むので，PE 1 で実行する他のタスクの実行時刻を遅れPE 1させることなく，タスク C の開始時刻を早めることができる。

図８ＰＥ0ＰＥ1A

ＰＥ2ＰＥ0Or

並列関係の融合

ることにより，図９のような木構造を持つタスクは，タOsスク間の通信時間に対するタスク処理時間の割合に応じOsLLて複数のあるいは１つの粗いタスクに融合される。

OrOr
CCtime

図９(b)融合後(a)融合前

図６N

この単純な方法を部分タスクグラフに繰り返し適用すA,BL

B
eAN eBN
M

ＰＥ1

B

Os

6．4

A

通信の一括化

ヒューリスティックタスク融合法

タスク融合の適用例

７. タスク複製
7. 1

複製の条件

本手法では生成されたタスクが細かすぎた場合に，ヒタスク複製のねらいは，タスクを複製することによりューリスティックなタスク融合手法を用いて並列性をあ

複製元タスクの後続エッジを分散させ，後続タスクの処まり犠牲にすることなく複数のタスクを融合し１つの粗理開始時間を早めることである。しかし，タスクを複製－20－

することで複製元の先行タスクからの通信が増え，逆に[実行環境]スケジュール長が伸びてしまう可能性がある。そこで本手法では局所的には，その複製によってスケジュール長ＣＰＵ:PentiumD(2.79GHz)，メモリ:1GB[指標]が伸びない場合のみ，その該当タスクを複製対象タスクタスク融合・複製を行う前後においてとした。タスク複製の条件は，複製対象タスクとその直① スケジュール長(初期解)

接後続タスクを部分タスクグラフとし，複製を行った結② スケジュール長(一定時間探索後の暫定解)

果複製前よりも部分タスクグラフの最小並列処理時間が③ タスク数短くなる場合にタスクの複製を行う。図 10 の部分タスクを比較する。

グラフでは，タスク 2 を複製することによりタスク 5 の探索時間については，タスクの規模や通信を考慮して開始を早めることができ，結果としてこの部分タスクグいる点から，現実的な時間内ですべての探索を終えるこラフのスケジュール長が短くなることがわかる。このよとは困難であるため，ランダムタスクグラフでは 60 秒，うな場合にタスク複製を適用する。

アプリケーションプログラムのタスクグラフでは 300 秒１で探索を打ち切り，その時点での暫定解を評価の対象と１した。
222‘8. 13PE0PE1PE24213

図 10535PE0PE1PE244215

乱数によって様々な形状のタスクグラフを作成したものを評価用タスクグラフとして用いた。乱数の発生方法

352’

ランダムタスクグラフによる評価は一様乱数である。

4タスク複製の適用例

・

サンプルタスクグラフ数：100

・割り当てプロセッサ数：16－各タスクグラフのパラメータ－
7. 2

後続エッジの分散・各タスクグラフのタスク数：50

複製を行った際，後続タスクへのエッジをどのよう・直接先行タスク数：1～3に分散するかについて説明する。小規模なタスクグラフ

・直接後続タスク数：1～3における最適解のタスク割り当てを観察すると，プライ・タスク処理時間：1～100

オリティレベルの高いタスクは通信を行わず，逐次処理・通信時間：1～100されることが多いことがわかる。そこで本手法では，図・並列度(処理時間の和/クリティカルパス)：1～511 のように，タスク 1 が複製条件を満たすとき，その複製をタスク 1’とすると，後続タスク 2～5 はプライオリ

8. 1. 1

スケジュール長(初期解)の比較

ティレベルが高いものから順に，タスク 1 とタスク 1’交ランダム生成された 100 通りのタスクグラフはいずれ互にその後続タスクとなるようにエッジを分散する。

もタスク数が 50 であるが，6.で述べたタスク融合を適用したところ，平均してタスク数が 17.1%減少した。そし11てすべてのタスクグラフについてタスク融合前後におけ1’るスケジューリング初期解の比較を行った。ここで，初2

3

4

5

2

43

5

LV(10)

LV(7)

LV(5)

LV(3)

LV(10)

LV(5)

LV(7)

LV(3)

図 11 後続エッジの分散期解とは 5.2 で述べた 3S 法が探索の中で最初に求める解候補であり，CP/MISF 法でタスクの割り当て時刻に通信による遅延を考慮しながら決定されたスケジュールと一致するものである。図 12 は各タスクグラフの融合前後のスケジュール長の伸縮率を融合前のスケジュール長を１８．評 価として散布図で表したものである。図から分かるように，融合後のスケジュール長(初期解)と，融合前のスケジュタスク融合とタスク複製の効果を調べるために，ランール長(初期解)を比較すると 7 割以上のタスクグラフでダム生成されたタスクグラフといくつかのアプリケーシスケジュール長が改善され，全体平均でスケジュール長ョンプログラムのタスクグラフを用いて評価を行った。

を 5.1%削減することができた。

－21－

8. 1. 3

融合後のスケジュール長(初期解)の伸縮率
スケ
ジ

1.1

ュー

ル長の伸縮率

タスク融合とタスク複製を同時に適用した場合

100 タスクグラフ中３つのタスクグラフでタスク複製1.2が適用された。適用された数が少ないのは，複製によっ1てスケジュール長が悪化することのないように，本手法

0.90.8では複製の条件を厳しくしているからである。タスク複0.7製が行われた３例において，融合のみを行った場合の初0.6期解・暫定解と比較してスケジュール長の変化はなかっ0.50.4100た。

図 12 融合前後のスケジュール長(初期解)の比較

8. 20102030405060708090

タスクグラフ番号

標準タスクセットによる評価

早稲田大学笠原研究室で公開されている標準タスクセ
8. 1. 24)

スケジュール長 (一定時間探索後の暫定解)ット(アプリケーションプログラム)の比較

ラフとして用いた場合の評価を示す。

を評価用タスクグ

タスクグラフの概要は以下のようである。

融合前後におけるスケジュール長（60 秒探索後の暫定解）の比較を行った。図 13 は各タスクグラフの融合前後

・Robot control(タスク数 88，エッジ数 131)のスケジュール長の伸縮率を融合前のスケジュール長を・Sparse matrix solver(タスク数 96，エッジ数 67)１として散布図で表したものである。図から分かるよう

・SPEC fpppp(タスク数 334，エッジ数 1145)に，融合後のスケジュール長(60 秒探索後の暫定解)は，しかしこれらのタスクグラフには通信時間が含まれてい融合前のスケジュール長(60 秒探索後の暫定解)より平均ないため，CCR(communication to computation ratio)で 5.9%削減することができた。

=通信時間の総和／処理時間の総和
融合後のスケジュール長(暫定解)の伸縮率をパラメータとし，CCR を 1～3 まで変化させてランダ

1.2

ュー

ス
ケジ

ル
長の伸縮率

ムに通信時間を加えることで各タスクグラフ 30 種類の1.1

通信パターンのタスクグラフを生成した。

10.90.8

8. 2. 10.7

スケジュール長(初期解・暫定解)の比較

30 種類の通信パターンを加えた標準タスクセットに0.60.5

タスク融合を適用したところ，平均してタスク数が0.40102030405060708090100

タスクグラフ番号

図 13 融合前後のスケジュール長(暫定解)の比較21.7%減少した。そしてすべてのタスクグラフについてタスク融合前後におけるスケジュール長(初期解・300 秒間探索後の暫定解)の比較を行った結果が表１である。融前述の通り，全探索を行うことは事実上不可能である合前よりも暫定解が改善されたタスクグラフは全体の約ので，限られた時間の中で早期に，より優良な解を求め82%で，最もスケジュール長が良くなったものでは約ることが重要である。また，全探索をすれば膨大な探索32%短縮された。逆に最も悪くなってしまったものでは時間がかかる中で，探索の初期段階の実用的な時間内でスケジュール長が約 10%伸びていた。平均的には融合には，できる限り良質の解候補が存在する探索空間を対象

よってスケジュール長を十分改善できたと言える。また，として探すことが重要である。そこで融合前後におけるRobot control において，ランダムタスクグラフ同様，融60 秒間の探索で初期解からどれだけスケジュール長が合をしないで探索を行った場合よりも，融合を行ってか短縮されたかを比較すると，融合をしないで探索を行っら探索をした方がスケジュール長の短縮率が平均でた場合のスケジュール長の短縮率は平均 2.5%であった0.8%上がった。Sparse matrix solver と SPEC fpppp に関してのに対し，融合を行ってから探索をした場合のスケジュ

表1

ール長の短縮率は平均 3.3%であった。このことからタス

評価結果

融合前のスケジュール長 融合前のスケジュール長(初期解)との比較(暫定解)との比較

融合前のタスク数との比較

ク融合によって，スケジュール前に無駄な探索空間を除

robot

平均4.4%の削減

平均4.9%の削減

平均22.7%の削減

外したことで早期に優良な解を求めることができたと言sparse

平均2.9%の削減

平均2.9%の削減

平均26.9%の削減

える。

fpppp

平均10.8%の削減

平均10.8%の削減

平均15.5%の削減－22－参考文献

は初期解と暫定解が同じであった。従って，効果の度合
いはタスクグラフに依存するが，実アプリケーションにおいてもタスク融合により無駄な探索空間が削減された

1) 笠原博徳,“並列処理技術”,コロナ社, 1991

ことで，早期に優良な解を発見できたことになる。

2) 津田耕治, “通信を考慮したタスクスケジューリング
問題の探索解法” ,成蹊大学大学院工学研究科情報処

8. 2. 2

理専攻修士論文, 2004

タスク融合とタスク複製を同時に適用した

3) Oliver Sinnen,Leonel Augusto Sousa, Frode Eika Sandnes,

場合
Robot control において 5 種類のタスクグラフにタスク“Toward a Realistic Task Scheduling Model”,IEEE複製が適用された。タスク複製が適用されたタスクグラ

Transactions On Parallel And Distributed Systems,

フに関してはタスク融合のみを行った場合の暫定解よりVOL.17, NO. 3, MARCH 20064) 標準タスクセット,も，平均で 4.6%スケジュール長が削減された。またタス
ク融合のみを行った初期解・暫定解と比較して，タスク

http://www.kasahara.elec.waseda.ac.jp/schedule/index.ht

複製適用により初期解・暫定解が悪くなってしまったタml, 2007 年 3 月現在参照可

スクグラフはなかった。

９. 終わりに本研究では，通信遅延を考慮したタスクスケジューリングのための前処理としてタスク粒度解析を行い，並列ログラムに適切な粒度をスケジュール前に決定することを行った。結果，タスク融合を行う前と比較して，スケジューリング時の探索空間が削減され，実用的な時間内でより優良な解を得ることができた。またタスク複製により通信を減らすことでスケジュール長の削減を行うことができた。
今後の課題として，本手法では部分タスクグラフを取り出し，処理時間と通信時間の割合によって局所的に融合・複製の判定を行っているが，さらに精度の良い粒度解析を行うためには数値だけではなく，タスクグラフの形状などを考慮に入れた手法が必要であると考えられる。

－23－