10.5 有向非巡回グラフとスケジューリング

MIT の情報科学科で開講される科目には、図 \(\text{10.6}\) に示すように必須科目が指定されている。この図の科目 \(s\) から科目 \(t\) への有向辺は、\(t\) の直接的な必須科目に \(s\) が指定されていることを意味する。もちろん、実際に \(t\) を受講するには \(s\) だけではなく、\(s\) の必須科目、そして \(s\) の必須科目の必須科目、などの単位を全て取得する必要がある。この事実は正歩道関係を使うと正確に表現できる: 直接的な必須科目を表す科目上の二項関係を \(D\) とすれば、「科目 \(u\) の単位を取得しないと科目 \(v\) を受講できない」は「\(u\ D^{+}\ v\)」と同値である。

当然ながら、直接的な必須科目を表す有向グラフに長さが正の閉歩道が含まれると誰も MIT を卒業できなくなる。よって閉歩道は禁止する必要がある。補題 10.2.6 より、これは閉路を禁止しても同じことである。つまり、必須科目グラフは次の意味で非巡回でなければならない:

DAG は情報科学で特別な重要性を持つ。タスクのスケジューリングや並列処理の解析で DAG は中心的な概念として使われる。例えばプログラムを複数のプロセッサに分散させるとき、生成されていない出力が必要とされることがあってはならない！ 本節では DAG とスケジューリングの関係を詳しく見ていく。

10.5.1 スケジューリング

スケジューリングの問題では、タスクの集合と、それぞれのタスクを開始する前に完了させなくてはならないタスクを指定する制約の集合が与えられる。この二つの集合は、頂点がタスクを、辺が直接的な依存関係を表す有向グラフで表現できる。

例えば、図 \(\text{10.7}\) に示す DAG は男性が正装に着替えるために必要なタスクを表す。この有向グラフの頂点は一つの衣服に対応し、辺は特定の衣服を身に着ける前に身に着けておく必要がある衣服を表す。

こういった依存関係が与えられたとき、最も基本的な疑問として「タスクを一つずつ実行するとき、依存関係に従いながら全てのタスクを完了させる順序は存在するか？」がある。こういった順序をトポロジカルソートと呼ぶ。

図 \(\text{10.7}\) が表す制約に従いながら衣服を一つずつ身に着ける方法は多く存在する。この制約を表す有向グラフのトポロジカルソートの例を図 \(\text{10.8}\) に示す。実は、全ての有限 DAG にはトポロジカルソートが存在する。これは毎朝問題なく衣服を身に着けられることの数学的証明である。

有限 DAG のトポロジカルソートは極小要素から始めると簡単に構築できる:

有向グラフの概念を使って定義される性質が「最小」「極小」と呼ばれるのは奇妙に思える。これらの言葉は、辺の始点を終点より「小さい」と捉える解釈から来ている。この解釈は次節で見るので、ここでは慣習的にそう呼ばれていると理解してほしい。

この定義が持つ変わった特徴として、最小の頂点を持たない DAG が極小の頂点を多く持つことがあり得る。例えば図 \(\text{10.7}\) の DAG は最小の頂点を持たないものの、極小の頂点を \(4\) 個 (左の靴下・右の靴下・パンツ・シャツ) 持つ。

衣服を身に着ける正しい順序を構築する手続きは次の通りである。まず、極小の要素を一つ選択する ── 例えばシャツを選んだとする。すると、有向グラフの残りの部分における極小の頂点の集合が更新される: 選択しなかった \(3\) 個は極小のままであり、シャツを選択したことでネクタイが新たに極小になる。この中から極小の要素を一つ選択し、同じ処理を頂点が全て選択されるまで繰り返す。この手続きが終了するとき、頂点を選択された順番で並べた列がトポロジカルソートとなる。

この構築から次の事実が分かる:

トポロジカルソートを構築する方法は多くある。例えば、限界まで長くした路の始点となる極小の頂点を選んでいくのではなく、そういった路の終点となる極大の頂点を選んでいって最後に反転する方法でも構築できる。実は、有限 DAG のトポロジカルソートは条件を満たす頂点を一つずつ選んでいけば必ず構築できる¹。

10.5.2 並列タスクのスケジューリング

タスクの依存関係を表す有向グラフのトポロジカルソートは、依存関係を守りつつタスクを一つずつ実行する順序を与える。しかし、複数のタスクを同時に実行できる場合はどうするべきだろうか？ 例えばタスクがプログラムを表し、DAG がデータの依存関係を表すとき、多くのプロセッサを持つ並列マシンを使えばタスクを一つずつではなく複数個同時に進行できる。このシナリオでは、タスクをどのようにスケジュールすべきだろうか？ ここでの目標は全てのタスクを完了させる時間を最小化することである。議論を簡単にするため、全てのタスクには同じだけの時間がかかり、全てのプロセッサは同一だと仮定する。

タスクの有限集合とそれらの依存関係が与えられたとき、最適な並列スケジュールの長さを求める問題を考えよう。この問題は DAG の歩道関係を使うと解析できる。図 \(\text{10.7}\) の設定を例として説明する。

最も素早く衣服を身に着けるには、最初のステップに全ての極小なタスクに取り掛かる: 左の靴下、右の靴下、パンツ、シャツを身に着ける²。そして次のステップにズボンとネクタイを身に着ける。この時点ではズボンを履いていないので、靴を履くことはできない。次のステップで左の靴、右の靴、ベルトを身に着け、最後のステップでジャケットを身に着ける。このスケジュールを図 \(\text{10.9}\) に示す。

このスケジュールは \(4\) 単位の時間で全てのタスクを完了する。これより短い時間が不可能なことは、一つずつ完了させる必要がある \(4\) 個のタスクの列が存在する事実から分かる: シャツを着て、パンツを履き、ベルトを締めてからでなければジャケットは身に着けられない。このようなタスクの列を鎖 (chain) と呼ぶ:

無限個のプロセッサが利用可能だとしても、並列スケジュールで全てのタスクを完了させるには最低でも最大の鎖の要素数と同じだけの時間がなる。なぜなら、もし任意の鎖の要素数より短い時間で全てのタスクが完了するなら、その鎖の二要素が同時に実行されており、それは鎖の定義に反するからである。このため、要素数最大の鎖はクリティカルパス (critical path) と呼ばれる。例えば図 \(\text{10.9}\) でクリティカルパスは赤く示されている。

この例では、クリティカルパスの要素数と同じステップ数でタスクを完了させる並列スケジュールが構築できている。DAG が持つ優れた特徴として、この性質を持つ並列スケジュールは必ず構築できる！ 言い換えれば、与えられた DAG が表す依存関係を守る並列スケジュールであって、クリティカルパス (要素数最大の鎖) の要素数と同じだけのステップで全てのタスクを完了させるものが存在する。

一般に、タスクを実行するスケジュール (schedule) とは、各ステップで実行すべきタスクの集合を並べた列である。任意のタスク \(a\) は何らかのステップにスケジュールされる必要があり、\(a\) が開始される前に完了させなければならない全てのタスクは \(a\) より前にスケジュールされる必要がある。スケジュールを正確に定義しよう:

例えば、集合 \(\left\{ a, b, c, d, e \right\}\) は次に示す \(3\) 個のブロックに分割できる:

\(a\) で終わる最も長い (要素数の多い) 鎖を、\(a\) のクリティカルパス (critical path) と呼ぶ。\(a\) のクリティカルパスで \(a\) より「小さい」要素の個数を \(a\) の深さ (depth) と呼び、\(\operatorname{depth}(a)\) と表記する。この定義から、可能な全ての並列スケジュールにおいて \(a\) がスケジュールされるのは \(\operatorname{depth}(a)\) 以降のステップだと分かる。また、極小な要素は深さが \(0\) の要素に等しい。

全てのタスクを最小のステップ数で完了させる非常に単純な並列スケジュールが存在する: 各ステップで実行可能なステップを全て実行する「貪欲どんよく (greedy)」な戦略である。この貪欲なスケジュールでは、深さ \(k\) の任意の要素がステップ \(k\) にスケジュールされる。上述の最適な衣服の身に着け方も貪欲な方法で構築された。

この定理が与える \(A_{0}\), \(A_{1}\), \(\ldots\) が定義 10.5.7 の意味で並列スケジュールであることの証明は練習問題 (問題 10.25) とする。この定理は次のように言い換えられる: 同時に利用できるプロセッサの個数が制限されないとき、全てのタスクを並列実行で完了させるのにかかる時間はクリティカルパスの要素数に等しい:

プロセッサの個数が制限されるとき問題は複雑になる。問題 10.26 に例を示してある。

10.5.3 Dilworth の補題

スケジューリングに関する上述の結果から、次の反鎖に関する性質が分かる:

証明 \(A_{k} ::= \left\{ a \in V(D) \; | \; \operatorname{depth}(a) = k \right\}\) と定めると、容易に分かる (問題 10.25) ように \(A_{0}\), \(A_{1}\), \(\ldots\) は反鎖からなる \(V(D)\) の分割である。 ■

系 10.5.11 からは DAG に関する次の有名な結果が導かれる:

証明 要素数が \(t\) より大きい鎖が存在しないと仮定する。\(\ell\) を要素数最大の反鎖とする。系 10.5.11 の証明で示した方法で並列スケジュールを作成すると、最も大きい鎖の要素数と同じ個数の反鎖が作成できる。仮定より、この反鎖の個数は \(t\) 以下である。この並列スケジュールにおいて任意の頂点はちょうど一つの反鎖に含まれ、任意の反鎖の要素数は \(\ell\) 以下なので、頂点の個数は \(t \ell\) 以下と分かる。つまり \(\ell t \geq n\) であり、両辺を \(t\) で割れば \(\ell \geq n/t\) を得る。 ■

証明 補題 10.5.12 で \(t = \sqrt{n}\) とすれば得られる。 ■