タスクグラフの階層的マクロタスク化とそのタスクスケジューリング手法の提案

タス クグ ラ フの階層 的 マク ロタス ク化 とその タスクス ケ ジュー リング手法 の提 案

長 谷 川

幹*1,甲

斐

宗 徳*2

Detecting

Hierarchically

Structured

Macro-tasks

within

a Task Graph

and Its Task Scheduling

Method

Motoki HASEGAWA

*', Munenori

KAI * 2

ABSTRACT

: One of the key methods

for the optimized

parallel

processing

of any program

is task

scheduling.

This intends to minimize

the execution

time of the entire program

by determining

an optimal

schedule

for allocating

all tasks, which

are processing

units

comprising

the program,

onto available

processor

elements

into pieces.

Due to complexity

of calculation

and being

a large-scale

problem,

the

optimization

problem

is extremely

challenging

to solve with the current algorithms

in a practical

amount of

time. Authors

have studied the method of partially

optimizing

task graph as a technique

of task scheduling

for large-scale

problems.

This paper reports on scheduling

method that supports hierarchical

macro for task

groups.

Keywords

: Task scheduling,

Combinatorial

optimization

problems,

High performance

search method

(KeCeivedNOvember5り,2り16) 1.は じ め に マ ル チ コ ア や マ ル チ プ ロ セ ッ サ と い っ た 現 代 の 並 列 コ ン ピ ュ ー テ ィ ン グ に お い て 、 効 率 よ く 高 速 に 処 理 を 行 う た め の 方 法 の1つ と して タ ス ク ス ケ ジ ュ ー リ ン グ が あ る 。 タ ス ク ス ケ ジ ュ ー リ ン グ は 、 並 列 処 理 環 境 で 計 算 資 源 (ProcessorElement:PE)に 最 適 な タ ス ク の 割 り 当 て を 決 定 し 処 理 パ フ ォ ー マ ン ス を 最 大 限 に 引 き 出 す 技 術 で あ る 。 こ の タ ス ク ス ケ ジ ュ ー リ ン グ は 、 組 み 合 わ せ 最 適 化 問 題 の 計 算 複 雑 度 の ク ラ ス の 中 で 強NP困 難 と い う ク ラ ス に 属 す る[1]。 こ の 強NP困 難 に 属 す る 問 題 は 、問 題 の 規 模 が 大 き く な る ほ ど 、 最 適 解 を 得 る の に 必 要 と な る 探 索 時 間 が 指 数 関 数 的 に 増 大 し て し ま う。 従 っ て 、 大 規 模 な タ ス ク 集 合 で の ス ケ ジ ュ ー リ ン グ は 、 実 用 的 な 時 間 内 に 最 適 解 を 得 る こ と は 不 可 能 に 近 い 。 過 去 の 代 表 的 な タ ス ク ス ケ ジ ュ ー リ ン グ ア ル ゴ リズ ム で あ る 、 リ ス トス ケ ジ ュ ー リ ン グ[2]、CP法[3]、CP/MISF 法[4]や 、DF/IHS法[4]な ど は 、 各 マ シ ン 間 の 通 信 時 間 を

考 慮 して い る もの で は な い。 実 際 の 並 列 実 行 時 に は 各 マ

シ ン 間 で のデ ー タ通 信 に か か る通信 時 間 に よ る影 響 が 大

き い 可能 性 もあ り、 通信 遅 延 を 考 慮 した ス ケ ジ ュー リン

グ アル ゴ リズ ム が 重 要 とな る。 この 通信 遅延 を考 慮 した

ス ケ ジ ュ ー リ ング は 、組 み合 わせ 最適 化 問題 に お け る探

索 の 回数 を さ らに増 や し、 よ り困難 な もの とす る。

この よ うな 背 景 か ら大 規模 な タス ク集 合 で も短 時 間 で

最 適 解 、ま た は それ に近 い解 を求 め られ る通 信 遅延 を考 慮

したス ケ ジ ュ ー リン グアル ゴ リズ ム が 必要 とされ て い る。

大 規 模 な タ ス ク集 合 を 実 用 的 な 時 間 内 に ス ケ ジ ュー リ

ン グ を行 う方 法 と して 、部 分 最適 化 を 用 い た 階 層 的 ス ケ

ジ ュ ー リン グ に よ るタ ス クス ケ ジ ュー リ ン グの 高 速解 法

につ い て研 究 を行 っ た。 特 に 、 汎 用 的 な プ ロ グ ラム に 対

応 す る た め にベ ンチ マ ー ク プ ロ グ ラム か らな る タス ク グ

ラ フ に対 して有 効 な 階層 的 ス ケ ジ ュー リ ン グア ル ゴ リズ

ム の構 築 を行 っ た。

2.タ

ス ク ス ケ ジ ュ ー リ ン グ

*1:理 工 学 専 攻 博 士 前 期 課 程 学 生 *2:理 工 学 研 究 科 理 工 学 専 攻 教 授(kai@st _{.seikei.ac.jp)} 2.1タ ス ク グ ラ フ タ ス ク ス ケ ジ ュ ー リ ン グ で は 、問 題 を 表 現 す る た め に 、

タ ス ク を ノ ー ド、 タ ス ク 間 の 先 行 制 約 を 有 向 エ ッ ジ で 表 し た 、タ ス ク グ ラ フ と 呼 ぶDAG(DirectedAcyclicGraph)を 用 い る。 処 理 の 開 始 と 終 了 を 明 確 に す る た め 、 タ ス ク グ ラ フ に は 、 コ ス トが0の ダ ミー ノ ー ド と して ス タ ー トノ ー ド と エ ン ド ノ ー ドが 必 要 に 応 じ て 追 加 さ れ て い る_{。 図} 2.1は 、 ス タ ー トノ ー ドを タ ス クS、 エ ン ドノ ー ドを タ ス クEと し た サ ン プ ル タ ス ク グ ラ フ で あ る 。

/

Processing Time Communication /Time2】 図2.1タ ス ク グ ラ フ1 ノ ー ド内 の 数 字 は タ ス ク 番 号(TaskNumber)、 ノ ー ド横 の 数 字 は タ ス ク の 処 理 コ ス ト(ProcessingTime)を 表 し て い る。 本 研 究 で は 先 行 後 続 関 係 に あ る タ ス ク 同 士 が そ れ ぞ れ 別 のPEに 割 り 当 て られ た 際 に 、実 際 の 並 列 実 行 時 の デ ー タ の 転 送 時 間 と し て 、 マ シ ン 間 の 通 信 遅 延 を 考 慮 す る。 エ ッ ジ 横 の 角 括 弧 で 囲 ま れ た 数 字 は そ の 際 に か か る 通 信 コ ス ト(CommunicationTime)を 表 し て い る 。 2.2ガ ン トチ ャ ー ト タ ス ク ス ケ ジ ュ ー リ ン グ の 割 り 当 て 結 果 を 可 視 化 す る た め に 、 縦 軸 にPE、 横 軸 に 処 理 時 間 を 取 っ た 時 系 列 チ ャ ー ト と し て ガ ン トチ ャ ー ト を 用 い る_{。 本 研 究 で は 、 こ の} 他 に 縦 軸 に 各PEの デ ー タ の 送 受 信 の タ イ ミ ン グ と し て Send,Recvの2つ を 追 加 し た ガ ン トチ ャ ー トを 用 い る。図 2,2は 、 図2,1の タ ス ク グ ラ フ1の ス タ ー トノ ー ドS、 タ ス ク1、 タ ス ク2の3つ の タ ス ク を2つ のPEに 割 り 当 て

PE(0)

Send

Recv

PE(1)

Send

Recv

0 23 Communication Overhead 図2.2ガ ン トチ ャ ー ト 5Time た 様 子 を 表 し た ガ ン トチ ャ ー トで あ る。 各 タ ス ク は 、 自身 の 全 て の 先 行 タ ス ク の 処 理 が 終 了 し て か ら で な け れ ば 、 処 理 を 開 始 す る こ と が で き な い 。 ま た 、エ ッ ジ で 結 ば れ た タ ス クjと そ の 先 行 タ ス ク で あ る タ ス クiが 異 な るPEに 割 り 当 て ら れ た 場 合 は 、 通 信 遅 延 (CommunicationOverhead)を 考 慮 し、 エ ッ ジ に 付 加 さ れ た 通 信 コ ス トc(i,j)を払 う必 要 が あ る 。

2.3タ

ス ク の 下 限値 と プラ イ オ リテ ィ レベ ル

タ ス ク の 下 限値 とは 、 そ の タ ス クか らエ ン ドノー ドま

で に最 低 で もか か る処 理 時 間 の合 計値 で あ る。 本研 究 で

は 、 この 下 限値 の 大 き さに よっ て タ ス クの割 り当て優 先

度(プ ラ イ オ リテ ィ レベ ル)を 持 たせ 、探 索 に利 用 す る。

3.ス

ケ ジ ュ ー リ ン グ ア ル ゴ リズ ム

組 み 合 わ せ 最 適 化 問 題 を 解 く ア ル ゴ リズ ム は 大 き く2 つ に 分 け られ る 。一 つ 目 は 、人 間 の 経 験 則 に 基 づ い て 構 築 され 、短 時 間 で 近 似 解 を求 め る こ と が 目的 の 「ヒ ュ ー リス テ ィ ッ ク ア ル ゴ リズ ム 」 で あ る。 二 つ 目 は 、問 題 の 最 適 解 を 求 め る こ と が 目的 の 「最 適 化 ア ル ゴ リズ ム 」 で あ る 。 3.1ヒ ュ ー リ ス テ ィ ッ ク ア ル ゴ リ ズ ム 代 表 的 な ヒ ュ ー リ ス テ ィ ッ ク ア ル ゴ リ ズ ム と し て 、 リ ス ト ス ケ ジ ュ ー リ ン グ[2]、CP(CriticalPath)法[3]、 CP/MISF(MostImmediateSuccessorsFirst)法[4]な ど が あ る。 リ ス トス ケ ジ ュ ー リ ン グ は 、 ス ケ ジ ュ ー リ ン グ ア ル ゴ リ ズ ム の 基 盤 と な る ア ル ゴ リ ズ ム で あ る。 実 行 可 能 な タ ス ク(レ デ ィ タ ス ク)を 処 理 が 終 了 し て い るPE(ア イ ド ルPE)に 割 り当 て る。 レデ ィ タ ス ク 数 が ア イ ドルPEを 上 回 る 時 の タ ス ク の 割 り 当 て 順 序 は 、 タ ス ク番 号 の 順 番 に 選 択 され る 。 CP法 は 、レデ ィ タ ス ク 数 が ア イ ドルPE数 を 上 回 る 場 合 に プ ラ イ オ リ テ ィ レベ ル の 高 い レ デ ィ タ ス ク か ら ア イ ド ルPEに 割 り 当 て を 行 う。 CP/MISF法 は 、CP法 に お い て プ ラ イ オ リテ ィ レ ベ ル が 等 し い タ ス ク 同 士 の 割 り 当 て 順 序 を 後 続 タ ス ク 数 で 比 較 し て 決 定 す る 方 法 で あ る。 3.2最 適 化 ア ル ゴ リ ズ ム 代 表 的 な 最 適 化 ス ケ ジ ュ ー リ ン グ ア ル ゴ リズ ム で あ る DF/IHS(DepthFirst/lmplicitHeuristicSearch)法[4]は 、 組 み 合 わ せ 最 適 化 問 題 に 最 も効 果 の あ る 最 適 化 手 法 と さ れ て い る 分 枝 限 定 法(Branch&Bound)にCP/MISF法 の ヒ ュ ー リ ス テ ィ ッ ク 効 果 を 取 り入 れ た 探 索 ア ル ゴ リズ ム で あ る 。

このDF/IHS法 は 、探 索 木 を構 成 しな が ら分 枝 限 定 法 の 限

定 操 作 を行 い 、深 さ優 先 探 索 に よっ て 暫 定 解 を更 新 しな

が ら全 探 索 を行 っ て 問題 の 最 適解 を 求 め る。

3.3通 信 遅 延 を 考 慮 した ス ケ ジ ュ ー リ ン グ ア ル ゴ リズ ム こ れ ま で に 紹 介 し たCP法 、CP/MISF法 、DF/IHS法 は 、 全 てPE間 の 通 信 遅 延 を 考 慮 し な い ス ケ ジ ュ ー リ ン グ ア ル ゴ リズ ム で あ る。 本 研 究 で はDF/IHS法 に 、 各 タ ス ク か ら 限 定 さ れ た 範 囲 の 後 続 タ ス ク ま で の 通 信 遅 延 を 考 慮 し た 下 限 値 を 求 め るREDIC(RemainingDistanceIncluding CommunicationOverhead)法[5]を 加 え た ア ル ゴ リ ズ ム[6] を 用 い る。 も の と 定 義 す る。 図3.1で は 、 タ ス ク{1,3,4,5}が 部 分 タ ス ク グ ラ フ に 該 当 す る。 前 述 の 手 順 ① の タ ス ク グ ラ フ の 中 か ら タ ス ク 群 を 探 索 し 、 部 分 タ ス ク グ ラ フ を 検 出 す る 手 法 は 、 上 記 の 部 分 タ ス ク グ ラ フ の 定 義 に 該 当 す る タ ス ク 群 を 任 意 に 手 動 で 決 定 す る。

4.2階

層 的 ス ケ ジ ュー リ ング

改 め て 、 階層 的探 索 手法 の 手順 を 以 下 に示 す 。

①

タ ス ク グ ラ フ か ら部 分 タ ス ク グ ラ フ を検 出

②

部 分 タ ス ク グ ラフ に つ い て 部 分 ス ケ ジ ュー リン グ を

行 う

③

全 体 タ ス ク グ ラフ に つ い て全 体 ス ケ ジ ュー リン グ を

行 う

4.タ

ス ク グ ラ フ の 階 層 的 探 索 手 法

大 規模 な タ ス ク集 合 を 実 用 的 な 時 間 内 に タス クス ケ ジ

ュ ー リン グす る方 法 と して 、 タス ク グ ラ フ を複 数 回 に分

け て ス ケ ジ ュ ー リン グす る階 層 的 な ス ケ ジ ュー リン グ方

法 の研 究 を 行 っ た 。 階 層 的 探 索 手 法 は 、 タス ク グ ラ フの

中 か ら部 分 的 に 最 適 化 可 能 な タス ク群 を探 索 して 検 出 す

る 「

部 分 タ ス ク グ ラ フの 検 出 」 と、 部 分 タス ク グ ラ フ と

元 の 全 体 タ ス ク グ ラ フ を 複 数 回 ス ケ ジ ュ ー リ ン グす る

「

階 層 的 ス ケ ジ ュ ー リング 」 を 行 う。

以 下 に 、 階層 的 探 索 手 法 の 手 順 を 示 す 。

①

タ ス ク グ ラフ の 中か ら部 分 最 適 化 可 能 な タス ク群 を

検 出 す る。

②

検 出 した タ ス ク群 に つ い て の み ス ケ ジ ュー リン グ を

行 い 、PEへ の割 り当 て を決 め る。

③

元 の タ ス ク グ ラフ の 中で 、 ② で ス ケ ジ ュー リン グ し

た タ ス ク 群 を1つ の タス ク と して み な し、 タス ク グ

ラフ 全 体 に つ い て ス ケ ジ ュ ー リング を 行 う。

上 記 の 手 順 に お い て 、 ① で 検 出 し た タ ス ク 群 を 「部 分 タ ス ク グ ラ フ 」、② で 部 分 タ ス ク グ ラ フ に つ い て 行 うス ケ ジ ュ ー リ ン グ を 「部 分 ス ケ ジ ュ ー リ ン グ 」、部 分 タ ス ク グ ラ フ に 対 し て 元 の タ ス ク グ ラ フ を 「全 体 タ ス ク グ ラ フ 」、 全 体 タ ス ク グ ラ フ に つ い て の ス ケ ジ ュ ー リ ン グ を 「全 体 ス ケ ジ ュ ー リ ン グ 」、③ で 全 体 タ ス ク グ ラ フ の 中 で 部 分 タ ス ク グ ラ フ を1つ の タ ス ク と して み な す も の を 「マ ク ロ タ ス ク 」、 とそ れ ぞ れ 定 義 す る 。 4.1部 分 タ ス ク グ ラ フ の 検 出 手 法 部 分 タ ス ク グ ラ フ と は 、「入 ロ ノ ー ド」、「出 ロ ノ ー ド」、 そ の 中 間 に 存 在 す る 「中 間 ノ ー ド群 」 の 三 要 素 か ら 構 成 さ れ る タ ス ク 集 合 が1つ の タ ス ク グ ラ フ と して 成 り立 つ 階 層 的 ス ケ ジ ュ ー リ ン グ と は 、4.1で 検 出 し た 部 分 タ ス ク グ ラ フ に 対 し て の み 行 う 「部 分 ス ケ ジ ュ ー リ ン グ 」と 、 全 体 タ ス ク グ ラ フ の 中 で 部 分 タ ス ク グ ラ フ を1つ の 「マ ク ロ タ ス ク 」 と し て み な し て 行 う 「全 体 ス ケ ジ ュ ー リ ン グ 」 と に タ ス ク ス ケ ジ ュ ー リ ン グ を 分 割 し て 行 う方 法 で あ る 。 タ ス ク 数 が 少 な い ス ケ ジ ュ ー リ ン グ に 分 割 す る こ と に よ り 、 ス ケ ジ ュ ー リ ン グ に か か る 時 間 を減 少 させ る こ と が 目 的 で あ る。 次 の 図4.1は 、 図2.1の タ ス ク グ ラ フ1か ら 部 分 タ ス ク グ ラ フ を 検 出 し た 様 子 で あ る。 PartialTask Graph MacroTask 図4.1部 分 タ ス ク グ ラ フ と マ ク ロ タ ス ク 部 分 ス ケ ジ ュ ー リ ン グ は 、 部 分 タ ス ク グ ラ フ の 内 部 タ ス ク{1,3,4,5}に つ い て の み 最 適 化 を 行 うス ケ ジ ュ ー リ ン グ の こ と を 言 う。 こ こ で 、 全 体 の タ ス ク グ ラ フ の 中 で 部 分 タ ス ク グ ラ フ を1つ の 「マ ク ロ タ ス ク(M)」 と し て み る 。全 体 ス ケ ジ ュ ー リ ン グ は 、マ ク ロ タ ス ク(M)を 含 む タ ス ク{S,M,2,6,E}に つ い て ス ケ ジ ュ ー リ ン グ を 行 う。 4.2.1階 層 的 ス ケ ジ ュ ー リ ン グ に よ る ス ケ ジ ュ ー リ ン グ 時 間 の 減 少 階 層 的 ス ケ ジ ュ ー リ ン グ に 対 し て 、 従 来 の 最 適 化 ス ケ

ジ ュ ー リ ン グ 手 法 を 「フ ラ ッ トス ケ ジ ュ ー リ ン グ 」 と 定 義 す る。 タ ス ク グ ラ フ の タ ス ク 数 をn、部 分 タ ス ク グ ラ フ の 内 部 タ ス ク 数 をmと す る と 、 上 記 の 階 層 的 ス ケ ジ ュ ー リ ン グ は 次 の 条 件 下n>m>1で 行 わ れ る こ と が 前 提 と な る 。 タ ス ク 数nで 行 わ れ る フ ラ ッ トス ケ ジ ュ ー リ ン グ に 対 し 、 階 層 的 ス ケ ジ ュ ー リ ン グ は 、 タ ス ク 数mで の 部 分 ス ケ ジ ュ ー リ ン グ と タ ス ク 数(n-m+1)で の 全 体 ス ケ ジ ュ ー リ ン グ に 分 割 さ れ る。 タ ス ク 間 の 先 行 制 約 を 考 慮 し な い 環 境 下 で の 、 フ ラ ッ トス ケ ジ ュ ー リ ン グ と 階 層 的 ス ケ ジ ュ ー リ ン グ に お け る 探 索 回 数 の 比 較 を 表4.1に 示 す 。 表4.1 ス ケ ジ ュ ー リ ン グ 方 法 フ ラ ッ トス ケ ジ ュ ー リ ン グ 部 分 ス ケ ジ ュ ー リ ン グ 全 体 ス ケ ジ ュ ー リ ン グ 階 層 的 ス ケ ジ ュ ー リ ン グ

ス ケ ジ ュー リング 方 法 と探 索 回 数 の 比 較

探 索 回 数 n! m! (n-m+1)! (n-m+1)!+m! 表4.1の フ ラ ッ トス ケ ジ ュ ー リ ン グ の 探 索 回 数 と 階 層 的 ス ケ ジ ュ ー リ ン グ に よ る 探 索 回 数 を 比 較 した と き 、 乗 算 の 方 が 明 ら か に 大 き く な る た め 、 n!〉(n-m+1)!+m! が 成 り立 つ 。 タ ス ク 間 の 先 行 制 約 、 分 枝 限 定 法 に お け る 分 枝 限 定 操 作 を 考 慮 し て も 上 記 の 式 の 大 小 関 係 は 成 り 立 っ こ と が 分 か っ て お り[7]、階 層 的 ス ケ ジ ュ ー リ ン グ に よ っ て 探 索 回 数 が 削 減 さ れ る こ と が 分 か る 。 よ っ て 階 層 的 ス ケ ジ ュ ー リ ン グ に よ っ て ス ケ ジ ュ ー リ ン グ 時 間 を 減 少 させ ら れ る こ と が 分 か る 。 4.3部 分 ス ケ ジ ュ ー リ ン グ 方 法 部 分 ス ケ ジ ュ ー リ ン グ は 、 検 出 した 部 分 タ ス ク グ ラ フ に 対 し て 行 うス ケ ジ ュ ー リ ン グ で あ る 。 こ の 方 法 は 、 単 純 に タ ス ク 数 が 少 な い タ ス ク ス ケ ジ ュ ー リ ン グ で あ る た め 、 従 来 の 最 適 化 手 法 を 用 い て ス ケ ジ ュ ー リ ン グ を 行 っ た 。 4.4全 体 ス ケ ジ ュ ー リ ン グ 方 法 全 体 ス ケ ジ ュ ー リ ン グ は 、 実 体 が タ ス ク グ ラ フ で あ る 「マ ク ロ タ ス ク 」 を 割 り当 て 対 象 に 含 む た め 、 従 来 の 最 適 化 手 法 で は 実 現 で き な い 。 な ぜ な ら ば 、 従 来 の 最 適 化 手 法 は 、 「1つ の タ ス ク は1つ の 計 算 資 源(PE)に の み 割 り 当 て る 」 こ と が 前 提 条 件 で あ っ た 。 しか し、 マ ク ロ タ ス ク は 内 部 に 複 数 の タ ス ク を 持 ち 、 そ の タ ス ク を 並 列 実 行

す る た め 、複 数 のPEに 割 り当 て な けれ ば な らな い。 正 し

く階層 的 ス ケ ジ ュ ー リ ング を行 うた め に 、 タス クが 必 要

とす るPE数 に 対 応 した 割 り当 て を す る よ うな ア ル ゴ リ

ズ ム を導 入 した。

4.4.1必 要PE数 に 対 応 した タ ス ク の 割 り 当 て 複 数 のPEに 割 り 当 て る マ ク ロ タ ス ク に ス ケ ジ ュ ー ラ が 対 応 す る た め 、 ス ケ ジ ュ ー リ ン グ の 手 順 の 中 で 割 り 当 て 可 能 な タ ス ク を 選 ぶ 時 に 、 タ ス ク の 必 要PE数 を 見 て そ の 数 だ け 割 り 当 て る よ う に す る。 ま ず 、 タ ス ク に 自分 が い くつ のPEに 割 り 当 て る 必 要 が あ る の か と い う情 報 を 追 加 し た(必 要PE数)。 そ し て 、割 り 当 て 可 能 な タ ス ク を 選 択 す る と き に 、 選 択 し た タ ス ク を 格 納 す る キ ュ ー に 必 要PE数 が2以 上 の と き は 、 そ の 数 だ け 増 や す 作 業 を 追 加 し た 。 こ れ に よ り、 タ ス ク が 必 要 とす るPE数 に 正 し く 割 り 当 て る こ と が 可 能 に な っ た 。

5.階

層 的 ス ケ ジ ュ ー リ ン グ ア ル ゴ リ ズ ム の 拡 張

5.1複 数 の 部 分 タ ス ク グ ラ フ に 対 応 し た 階 層 的 ス ケ ジ ュ ー リ ン グ ア ル ゴ リ ズ ム こ こ ま で 説 明 した 階 層 的 探 索 手 法 で は 、図5.1の よ うな 部 分 タ ス ク グ ラ フ(マ ク ロ タ ス ク)同 士 が 続 い て い る よ う な タ ス ク グ ラ フ に お い て 、そ れ ぞ れ の マ ク ロ タ ス ク の 先 行 後 続 関 係 が 正 し く 認 識 で き て い な い 。 こ れ は 、従 来 手 法 で は タ ス ク の 先 行 タ ス ク と な り う る も の は1つ の タ ス ク で あ る こ と が 前 提 で あ っ た た め で あ る 。 しか し 、マ ク ロ タ ス ク 同 士 に 先 行 後 続 関 係 が あ る 場 合 、た だ 単 に お 互 い を 先 行 タ ス ク 、後 続 タ ス ク と す る だ け で な く 、そ の 内 部 の ど の タ ス ク と エ ッ ジ が つ な が っ て い た の か を認 識 す る 必 要 が あ る 。 こ れ は 、ス ケ ジ ュ ー リ ン グ で は マ ク ロ タ ス ク と い う タ ス ク の ま と ま り を 扱 うが 、実 際 の 並 列 実 行 時 に は そ の 内 部 の タ ス ク 間 で 通 信 が 行 わ れ る か ら で あ る 。 図5.1を 例 に し て 、 タ ス ク{1,2,3,4}か ら な る マ ク ロ タ ス ク をMl、 タ ス ク{5,6,7,8}か ら な る マ ク ロ タ ス ク をM2 とす る 。 ま た 、MlとM2は そ れ ぞ れ 必 要PE数 が2で あ る とす る 。 こ の 時 、 実 際 の 並 列 実 行 時 に 通 信 が 必 要 な タ ス ク は 、 タ ス ク4と タ ス ク5の 間 で あ る 。M1がPE(0)と PE(1)に 割 り 当 て られ て お り 、M2の 割 り 当 て 先 を 探 索 し て い る とす る 。 こ こ で 、M2の 先 行 タ ス ク がM1で あ る と す る と 、M2か ら見 た 時 に タ ス ク5の 先 行 タ ス ク で あ る タ ス ク4がPE(0)とPE(1)の ど ち ら に 割 り当 て ら れ て い る の か が 分 か ら な い 。 そ の た め 、 マ ク ロ タ ス ク の 先 行 タ ス ク が マ ク ロ タ ス ク で あ っ た 時 に 探 索 が 正 し く行 わ れ な い と い う課 題 が あ っ た 。

PartialTask Graph1 PartialTask Graph2 ウ 図5.1複 数 の 部 分 タ ス ク グ ラ フ こ の 問 題 を 解 決 す る た め に 、 マ ク ロ タ ス ク 内 部 の ス タ ー ト ノ ー ド と エ ン ド ノ ー ドに 対 し て_{、 マ ク ロ タ ス ク に す} る 前 の 先 行 タ ス ク と 後 続 タ ス ク を 記 憶 さ せ た 。 図5.1で は 、 マ ク ロ タ ス クM1の エ ン ド ノ ー ドで あ る タ ス ク4の 後 続 タ ス ク をM2で は な く タ ス ク5と し、 マ ク ロ タ ス ク の ス タ ー ト ノ ー ドで あ る タ ス ク5の 先 行 タ ス ク をM1で は な く タ ス ク4と した 。 こ れ に よ り、 マ ク ロ タ ス ク 同 士 が 先 行 後 続 関 係 で あ っ た と し て も 、 正 しい 割 り 当 て が 可 能 と な る。 以 上 の ア ル ゴ リズ ム の 導 入 に よ り、 複 数 の 部 分 タ ス ク グ ラ フ を 持 つ タ ス ク グ ラ フ に 対 し て も 階 層 的 ス ケ ジ ュ ー リ ン グ を 行 う こ と が 可 能 と な る 。 5.2マ ク ロ タ ス ク 内 の ア イ ドル 時 間 の 活 用 タ ス ク ス ケ ジ ュ ー リ ン グ に よ っ て 、PEへ の タ ス ク の 割 り当 て が 求 ま っ た と き 、PEは す べ て の 時 間 に お い て タ ス ク 処 理 を 行 うわ け で は な く 、 タ ス ク の 処 理 と 処 理 の 間 に 空 き 時 間 が 存 在 す る。 こ の 空 き 時 間 を 、PEの ア イ ドル 時 間 と 呼 ぶ 。 図5.2の 両 矢 印 が そ の 例 で あ る 。 PE(0) Send Recv lIlll l slll3囹51216

El

Hll

Ill lIr→ 闘 1ll PE(1) Send Recv 1 ()14 1

「

「「H

■lll l→ll lp…ess・ ・Idl・Tim・1 0357891215Tim 図5.2PEの ア イ ドル 時 間 図5.2で は 、PE(1)の 時 間0か ら 時 間5が ア イ ドル 時 間 と な っ て い る が 、 実 際 に は 、 こ の ア イ ドル 時 間 に タ ス ク 2を 処 理 可 能 で あ る 。 こ の よ うに 、 階 層 的 ス ケ ジ ュ ー リ ン グ に よ っ て 最 適 解 を 求 め る た め に は 、 マ ク ロ タ ス ク 内 に 存 在 す る ア イ ドル 時 間 を マ ク ロ タ ス ク 外 の タ ス ク の 割 り 当 て に 活 用 す る 必 要 が あ る。 図5.3は 、PE(1)の ア イ ドル 時 間 ヘ タ ス ク2を 割 り当 て た 結 果 で あ る 。 こ の よ うに 、 ア イ ドル 時 間 ヘ タ ス ク を 割 り 当 て る こ と に よ っ て 、 問 題 の 最 適 解 が 求 ま る こ と が あ る 。 PE(0) Send Recv 1 7 1 ■

_!

II l 二 → ■ ■ ■ ■ i

sl

1 3

_囹5

盈 l I I 目 l l-一 →i ■ 1 ■

目l

l■ ll l■ ll ■1→ ll PE(1) Send Recv ■ ( ) 2 4 6

El

■ 冒 ■ ■ ■ → ■ 1 1 ・

H

1-一 一 「 一 一一一11 ■ 1■ 卜 一 一 一 〉 ■ 璽 1■ 1■ _. , 0 23 5 78910Time 図5.3ア イ ドル 時 間 へ の タ ス ク の 割 り 当 て

しか し、全 て の ア イ ドル 時 間 に 対 して どの タス クが 割

り当 て 可能 か ど うか全 探 索 す る こ とは 、 ス ケ ジ ュー リン

グ 時 間 を増 や す こ とに な っ て しま う。 そ こで 、 ア イ ドル

時 間へ の割 り当 て探 索 を有 効 か つ 限 定 的 に す るた め に 、

探 索 を行 う条 件 をPE側 と タス ク側 に対 して2つ の 制 約 を

考 案 した。

5.2.1PEの タ ス ク 占 有 率 に よ る 制 約 PEの タ ス ク 占 有 率 と は 、 マ ク ロ タ ス ク の 割 り 当 て ら れ たPEの 処 理 時 間 の 内 、 実 際 に タ ス ク 処 理 を行 っ て い る 時 間 の 割 合 で あ る 。 あ るPEに 割 り 当 て られ た マ ク ロ タ ス ク の 実 行 開 始 時 間 をt1、 実 行 終 了 時 間 をt2と す る と 、 時 間t1か らt2 の 内 、 実 際 に タ ス ク が 割 り 当 て ら れ て い る 時 間 の 割 合 を そ のPEの タ ス ク 占 有 率 と す る 。例 え ば 、図5.2のPE(1)の タ ス ク 占有 率 は 、8÷9×100≒88.9%、PE(2)の タ ス ク 占 有 率 は 、2÷7×100≒28.6%で あ る 。 ア イ ドル 時 間 へ の 割 り 当 て 探 索 に よ る ス ケ ジ ュ ー リ ン グ 時 間 の 増 加 を 最 低 限 に す る た め に 、 探 索 を試 み る 条 件 と し て 、 「マ ク ロ タ ス ク が 割 り 当 て られ たPEの タ ス ク 占 有 率 が50%で あ る 」 こ と を 階 層 的 ス ケ ジ ュ ー リ ン グ ア ル ゴ リ ズ ム に 適 用 し た 。 5.2.2タ ス ク の プ ラ イ オ リテ ィ レベ ル に よ る 制 約 ア イ ドル 時 間 へ の 割 り 当 て 探 索 を 行 う際 の タ ス ク側 の 条 件 と し て 、 ア イ ドル 時 間 の 前 後 に 割 り当 て ら れ て い る タ ス ク の プ ラ イ オ リ テ ィ レベ ル の 範 囲 に 収 ま る プ ラ イ オ リ テ ィ レベ ル を 持 つ タ ス ク の み を 探 索 対 象 に し た 。 図5.2で は 、PE(1)に お け る ア イ ドル 時 間 は 時 間{0-5}

で あ る。 こ こ で 、 ア イ ドル 時 間 の 後 ろ に 割 り 当 て ら れ て い る タ ス ク4の プ ラ イ オ リテ ィ レベ ル を 参 照 し、 タ ス ク 4の プ ラ イ オ リテ ィ レ ベ ル よ り も 高 い 値 を 持 つ タ ス ク の み を 割 り当 て の 探 索 対 象 と す る 。 図5.4は 、 図2.1の タ ス ク グ ラ フ の 各 タ ス ク の フ.ライ オ リテ ィ レ ベ ル をCP/MISF法[4]に よ っ て 求 め 、 左 か ら 昇 順 に 並 べ た リス トで あ る。 図5.4よ り、 タ ス ク4よ り も 高 い プ ラ イ オ リテ ィ レ ベ ル で あ る の は タ ス ク2,6の 内 、 タ ス ク2の み で あ る た め 、 タ ス ク2の み を ア イ ドル 時 間 へ の 割 り当 て 探 索 対 象 と し 、 タ ス ク6は 探 索 の 対 象 外 と す る。

lSlll2131416151El

図5.4CPIMISF法[4】 に よ る プ ラ イ オ リ テ ィ リス ト 5.2.1と 上 記 の プ ラ イ オ リテ ィ レベ ル の 制 約 に よ り、ア イ ドル 時 間 へ の 割 り当 て 探 索 を 必 要 最 低 限 に す る こ と に よ り、 不 要 な 探 索 の 増 加 を 防 ぐ こ と が 可 能 に な る 。

時 点 で探 索 が完 了 して い な い 場合 は 、 そ の 時 点 で の 暫 定

解 を求 ま っ た解 と した。求 ま った 解(求 解 値)、探 索 回数 、

ス ケ ジ ュ ー リ ング 時 間(求 解 時 間)を 両 ス ケ ジ ュー ラ に

お い て比 較 した。

表6.1実 験 結 果

6.評

価 実 験

こ れ ま で に 述 べ た 階 層 的 探 索 手 法 を 実 装 し た 階 層 的 ス ケ ジ ュ ー ラ(HierarchicalScheduler:HS)と 従 来 のDF/IHS法 に よ っ て 最 適 解 を 求 め る 最 適 化 ス ケ ジ ュ ー ラ(Optimize Scheduler:OS)と で 比 較 実 験 を 行 っ た 。 実 験 環 境 を 以 下 に 示 す 。 ●CPU:Intel⑭Xeon⑭[email protected] ●OS:CentOS5.6 ●RAM:19GB 実 験 に 使 用 し た タ ス ク グ ラ フ は 、 以 下 の2種 類 の ベ ン チ マ ー ク プ ロ グ ラ ム を 基 に 、 本 研 究 室 が タ ス ク 処 理 コ ス ト ・通 信 エ ッ ジ コ ス トを 算 出 し 、 生 成 し た2種 類 の タ ス ク グ ラ フ と す る。

・MiBenchVersion1 _{.0:basicmath _large.c} ・NASParallelBenchmarks:IS(size`S') 上 記 に 加 え て 、 早 稲 田 大 学 笠 原 研 究 室 に よ っ て 公 開 さ れ て い る タ ス ク 数88個 の 標 準 タ ス ク セ ッ ト[9]の計3種 類 を 実 験 の 対 象 と す る。 こ の3種 類 の タ ス ク グ ラ フ に 対 して タ ス ク の 処 理 コ ス ト、 エ ッ ジ の 通 信 コ ス トを 以 下 の 条 件 に お い て100パ タ ー ン ラ ン ダ ム 生 成 し た<sub>。</sub> ● タ ス ク処 理 コス ト:最 大20、 最小5 ● エ ッジ 通信 コス ト:最 大10、 最 小1 ま た 、ス ケ ジ ュ ー リ ン グ 時 間 の 上 限 を60分 と し、60分 表6.1は 、OSの 結 果 を 基 準 の1.0と してHSに よ る3項 目 の 結 果 を 比 率 で 示 し て い る。 求 解 値 で は 、3種 類 の タ ス ク グ ラ フ 全 て で 比 率 の 平 均 値 が1.0を 下 回 っ て お り、HSに よ っ てOSの 求 解 値 よ り も 良 い 解 を 探 索 で き た こ と が 分 か る。 探 索 回 数 に お い て も 、3種 類 全 て で 比 率 の 平 均 値 が1.0 を 下 回 っ て お り 、HSはOSよ り も 少 な い 探 索 回 数 で 探 索 を 完 了 し た こ と が 分 か る。 求 解 時 間 に つ い て 、basicmathベ ン チ マ ー ク の 実 験 で は 、 100個 全 て で 求 解 時 間 の 上 限60分 で は 探 索 が 完 了 し な か っ た た め 、 平 均 値 ・最 大 値 ・最 小 値 い ず れ も1.0と な っ て い る 。 一 方 、NPBIS(size`S')で は 、 求 解 時 間 が 平 均 で 約47%減 少 し た 。 basicmathベンチマークの60分時点での求解値比率 埋1200 後 ●

違1:::暁

播 い 帝 噂 ㍊ へ 娩)^rや

1-1:::::

00.000 0102030405060708090100 タスク グ ラフ番 号 〔1∼100) 図6.1basicmathベ ン チ マ ー ク 結 果 の 求 解 値 比 率 図6.1は 、basicmathベ ン チ マ ー ク に 対 す る 実 験 の 求 解 値 の 比 率 を 示 し た 散 布 図 で あ る 。OSの 求 解 値 を 基 準 の 1.0と し、 各 タ ス ク グ ラ フ のHSに よ る 求 解 値 の 比 率 を 表 し て い る 。 basicmathベンチマークの探 索回数比 率 2 0 8 6 4 2 0 L 1 α α α 0 α 樹 封 蝋 回 展 腿 穀 2 割 斜 欄 梱 の O 0 0               

:く ㌦ 舜 ∫執 匝 轄 ●

●

♂♂ 、∴㌦

● ●

∴∴な

● ● ● 0 0 0 0102030405060708090100 タ ス ク グ ラ フ 番 号(1∼100) 図6.2basicmathベ ン チ マ ー ク 結 果 の 探 索 回 数 比 率

図6.2は 、basicmathベ ン チ マ ー ク 実 験 の 探 索 回 数 の 比 率 を 示 し た 散 布 図 で あ る。求 解 値 と 同 様 にOSの 探 索 回 数 を 基 準 の1.0と してHSの 探 索 回 数 の 比 率 を 表 し て い る。 2つ の 散 布 図 か ら 、basicmathベ ン チ マ ー ク に 対 して 階 層 的 ス ケ ジ ュ ー リ ン グ ア ル ゴ リズ ム が 特 に 有 効 で あ っ た と 分 か る。 探 索 回 数 に つ い て は 、100個 全 て の タ ス ク グ ラ フ に お い てOSよ り もHSの 探 索 回 数 の 方 が 少 な い 結 果 で あ っ た 。 7.お わ り に 大 規 模 な タ ス ク集 合 に 対 して よ り高 速 に 最 適 解 ま た は 近 似 解 を 求 め る た め の 手 法 と し て 、 階 層 的 ス ケ ジ ュ ー リ ン グ 手 法 の 研 究 を 行 っ た 。 こ れ ま で の 階 層 的 ス ケ ジ ュ ー リ ン グ 手 法 で は 、 ベ ン チ マ ー ク プ ロ グ ラ ム か ら な る タ ス ク グ ラ フ の よ うな 大 規 模 な タ ス ク 集 合 や 、1つ の タ ス ク グ ラ フ に 複 数 の 部 分 タ ス ク グ ラ フ が 存 在 す る よ うな タ ス ク 集 合 に 対 し て は 、効 果 を 発 揮 す る こ と が で き な か っ た 。 そ こ で 、 複 数 の 部 分 タ ス ク グ ラ フ へ の 対 応 や 、PEの ア イ ドル 時 間 の 活 用 法 の 構 築 に よ っ て 、 多 種 多 様 な タ ス ク グ ラ フ に 対 し て 有 効 な 階 層 的 ス ケ ジ ュ ー リ ン グ ア ル ゴ リズ ム の 構 築 を 行 っ た 。 評 価 実 験 で は 、 ベ ン チ マ ー ク プ ロ グ ラ ム2種 と 標 準 タ ス ク セ ッ トを 元 に し た タ ス ク グ ラ フ に 対 して 、 階 層 的 ス ケ ジ ュ ー ラ と 最 適 化 ス ケ ジ ュ ー ラ で 実 験 を 行 っ た 。 結 果 か ら 探 索 回 数 に つ い て 、basicmathで は 約27%減 少 、NPB IS(size`S')で は 約37%減 少 、標 準 タ ス ク セ ッ トで は 約15% 減 少 し た 。求 解 時 間 に つ い て は 、NPBIS(size`S')で 約47% 減 少 、 標 準 タ ス ク セ ッ トで 約23%減 少 した 結 果 を 得 た 。 今 後 の 課 題 に つ い て 、 評 価 実 験 の 結 果 か ら 、 タ ス ク 数 43個 のNPBIS(size`S')の 探 索 回 数 の 減 少 率 よ り も 、 タ ス ク 数88個 の 標 準 タ ス ク セ ッ トの 探 索 回 数 の 減 少 率 の 方 が 少 な か っ た 。 理 想 で は 、 タ ス ク 数 が 増 え る ほ ど 、 階 層 的 ス ケ ジ ュ ー リ ン グ に よ っ て 探 索 回 数 が 減 少 した 方 が 望 ま し い が 、 逆 に 減 少 率 が 低 い 結 果 と な っ た 。 こ の こ と か ら 、 ア イ ドル 時 間 へ の 割 り当 て 探 索 手 法 に 対 して 更 な る 最 適 化 が 必 要 で あ る と 考 え る 。 [3]T.C.Hu,"Parallelsequencingandassemblyline problems",OperationsResearch,Novem-ber/December 1961Vol.9No.6pp.841-848,1961 [4]H.KasaharaandS.Narita,"PractialMultiprocessor SchedulingAlgorithmforEfficientParallelProcessing", IEEETransactionsonComputers,Vol.33,No.ll,pp. 1023-1029,November.1985 [5]MasahikoUtsunomiya,RyujiShioda,MunenoriKai, "Heuristicsearchbasedonbranchandboundmethodfor taskschedulingconsideringcommunicationoverhead", Proc.ofIEEEPacificRimConferenceon Communications,ComputersandSignalProcessing, pp.256-261,2011. [6]渋 谷 知 則,栗 田 浩 一,甲 斐 宗 徳,"通 信 遅 延 を 考 慮 し た タ ス ク ス ケ ジ ュ ー リ ン グ 問 題 た め の 並 列 分 枝 限 定 法 と そ の 評 価",FIT2014(第13回 科 学 技 術 フ ォ ー ラ ム),第1分 冊,pp.149-154,2014 [7]柴 山 修"部 分 ス ケ ジ ュ ー リ ン グ を 活 用 し た 全 体 タ ス ク ス ケ ジ ュ ー リ ン グ 問 題 の 高 速 解 法"成 膜 大 学 理 工 学 部 卒 業 論 文,2015 [8]渋 谷 知 則,"通 信 遅 延 を 考 慮 し た タ ス ク ス ケ ジ ュ ー リ ン グ 問 題 の 並 列 解 法 一タ ス ク グ ラ フ の 部 分 最 適 化 に 基 づ く 探 索 優 先 順 位 の 改 良 一"成 践 大 学 理 工 学 研 究 科 修 士 論 文,2016 [9]http://www.kasahara.elec.waseda.ac.ip/schedule/

参考文献

[1]M.R.Garey,D.S.Johnson,"Computersandlntractability: AGuidetotheTheoryofNP-Completeness",W.H. Freeman;FirstEdition(1979). [2]EdwardG.Coffman,`℃omputerandJob-shopScheduling Theory",JohnWileyandSons,1976.