成 腰 大 学 理 工 学 研 究 報 告 J,Fac,Sci,Tech.,Sei/keiUniv. Vol.49No.1(2012)pp.1-12
タ ス ク ス ケ ジ ュ ー リ ン グ に お け る 過 剰 な 通 信 遅 延 の 排 除 と
通 信 可 能 域 の 走 査 に 関 す る 経 験 則 の 導 入
宇都宮
雅彦*1,甲 斐
宗徳*2
Applying heuristics using scanning of communication term and elimination of ineffective commu-nication overhead to Task Scheduling
Masahiko Utsunomiya*', Munenori KAI*2
ABSTRACT : Task scheduling is one of core technologies to improve the efficiency of parallel processing. A schedule is a solution of task scheduling problem, and make to cooperate the performance of parallel machines. The shorter length of schedule (makespan) is reduced, the more efficient parallel machines run. But, task scheduling problem is combinatorial optimization problem that has strongly NP hard computational complexity. Accordingly, it is necessary that to design algorithm taking account of more unforeseeable disposition in order to reduce makespan. Concerning to solve the problem, the disposition is considered with communication overhead between machines. In this paper, the authors propose new heuristic algorithms to optimize communication overhead. These are applied the focus to critical path of dependences and earliest allocation pattern of communications. The authors describe characteristics and processes of these algorithms, and our experiments show the effectiveness of them
Keywords : Task scheduling, Combinatorial optimization problem, Strongly NP hard, Communication
overhead (Received March 31 , 2012) 1.は じ め に タス クス ケ ジ ュー リン グは,並 列 処 理 環 境 にお け る タ ス ク並 列 の 中核 とな る最 適 化 技 術 の 一 つ で あ る。 並 列 化 技 術 の 普 及 に 伴 い,実 行 時 間 最 小 化 を 目的 と し た タス クス ケ ジ ュー リン グア ル ゴ リズ ム の 需 要 が 高 ま っ て い る。 タス ク並 列 は,大 規 模 で 計 算 量 の 多 い 処 理 を複 数 の 計 算 装 置 に 分 割 す る こ とで 並 列化 を行 うが,そ の ス ケ ジ ュー一一ル を 求 め る問題 は 強NP困 難 な 計 算 複 雑 度 を持 つ こ とが 知 られ て お り,任 意 の 問 題 に 対 し多 項 式 時 間 で 最 小 の 優 越 解 集 合 を得 る こ とは 不 可 能 に近 い[1]。 そ こ で,性 能 限 界 を持 つ 理 論 的 手 法 か ら実 装 ベ ー ス の 手 法 ま で,多 く の近 似 ア ル ゴ リズ ム が提 案 され て い る[6][7]。 *1・ 理 工 学 研 究 科 理 工 学 専 攻 博 ± 前 期 学 生 *2・ 理 工 学 研 究 科 理 工 学 専 攻 教 授(kai@st ,seikei.acjp) タス クス ケ ジ ュー リン グ問題 に お い て最 も複 雑 な 条件 の1つ に,タ ス ク問 の 実 行順 序 に 制約 を 与 え る依 存 関係 が 存在 す る。 タ ス ク ス ケ ジュ ー一一リ ング 問題 の 強NP困 難 な 計算 複 雑 度 を 持 つ性 質 か ら,問 題 に 最 も強 い複 雑 性 を 与 える 依存 関係 を最 適 化 す る こ とが,組 み 合 わせ の 結果 で あ る スケ ジュ ール の 長 さ と算 出 時 間 に 大 き く影 響 を与 え る と考 え られ る。 しか し,依 存 関係 に よ る通 信 の組 み 合 わせ は 高 い計 算複 雑度 の部 分 問題 とな る こ とが 多 く, ア ル ゴ リズ ム が 通信 を 考 慮す る際 に は,そ の計 算 量 を充 分 に 考 慮 しな け れ ば な らな い。 本稿 で は,依 存 関係 に 着 目 した仮 説 とそ の検 証 実 験 か ら,計 算 量 を抑 えて 依存 関係 の最 適 化 を 図 る2つ の ヒ ュ ー リス テ ィ ック アル ゴ リズ ム を提 案す る。 これ らの アル ゴ リズ ム を 用 い て,問 題 規模 の増 加 に 伴 う組 み 合 わせ 爆 発 を抑 えつ つ,よ り最適 化 され た ス ケ ジュ ール の 導 出 が 可 能 とな る こ と を示 す。
成 践 大 学 理 工 学 研 究 報 告 Vol.49No.1(2012.6) 2.タ ス ク ス ケ ジ ュ ー リ ン グ 2.1.タ ス ク ス ケ ジ ュー リ ング 問 題 の 定 義 筆者 は,タ ス クス ケ ジ ュー リン グ問 題 を"性 能 の 等 し いM個 の処 理 装 置(ProcessingElement,以 下PE)を 用 い て,任 意 の 順 序 依 存 と任 意 の 処 理 時 間 を持 つN個 の タ ス クの 全 て を割 り込 み 無 しで 処 理 す る と き,各PEが 一 度 に 高 々 一 つ ま で の 処 理 ・依 存 情 報 の 送 信 ・受 信 を 可 能 と す る条 件 下 で,依 存 間 の 通信 の 組 み 合 わ せ が 生 じ る遅 延 を考 慮 した 実 行 時 間 の 最 小 化 を 目的 関 数 と した,組 み 合 わ せ 最 適化 問題"と 定 義 し,短 時 間 に 良 質 な 近 似 解 を 導 出 す る近似 ア ル ゴ リズ ム の研 究 を行 っ て い る。 本 章 の 以 降 で は,上 記 の 各 定 義 に 関 して 解 説 を 行 う。 2.2.タ ス ク タ ス ク は,ス ケ ジ ュ ー リ ン グ 問 題 に お け る 分 割 不 可 能 な 処 理 単 位 で あ る。 任 意 の タ ス ク を ス ケ ジ ュ ー ル の 中 に 割 り当 て る た め に は,そ の タ ス ク ご と に 定 め ら れ た コ ス トに 基 づ い て 係 数 倍 し た 単 位 時 間 を 払 い,1つ のPEを 占 有 す る 必 要 が あ る 。 2.3.依 存 関 係 任 意 の タス ク間 の 依 存 関係 と して 定 め られ た 通信 は, 先 行 依 存側 の タス クが 終 了 して か ら後 続 依 存側 の タス ク が 実行 を 開 始 す るま で の 任 意 の 時 間 に 割 り当 て る必 要 が あ る。 タス クは 自身 の 先 行 関 係 に 相 当 す る全 タス クの 処 理 が 完 了 す るま で 処 理 が 開 始 で きな い 。 依 存 関 係 を解 決 す る とき に は,先 行 タ ス ク を処 理 したPEの 送 信 ポ ー ト と後 続 タス ク を処 理 す るPEの 受 信 ボ ー一一トが,同 時 か つ 通 信 の コス ト以 上 の 時 間 ア イ ドル 状 態 で な け れ ば な らな い 。 た だ し,依 存 関 係 を持 つ タ ス クの ペ ア が 同 一 のPE で 処 理 され る場 合,先 行 タス クの 処 理 結 果 に 相 当 す る情 報 は既 に 対 象 のPEが 保 持 して い るた め,依 存 関 係 に 定 め られ た コス トを 支 払 う必 要 が な い もの とす る。 2.4.処 理 装 置 処 理 装 置PEは タ ス ク を消 費 す る主 体 で あ る。各PEの 性 能 は 等 しい も の とす る。 本 稿 で は 依 存 解 決 の 逐 次 性 (2フ節 参 照)を 考 慮 して い る た め,あ る 時刻 に お け る, あ るPEの 稼 動 状 態 と して は,1つ の タス クの 処 理,1っ の 依 存 情 報 の 受 信 及 び,1つ の 依 存 情 報 の 受 信 の み が 可 能 で あ る。 終 点 の ノ ー一一ドを 各 々1つ とす るDirectedAcyclicGraphで 表 現 で き る 。 こ の 条 件 は 元 の 問 題 の 始 点 と 終 点 に コ ス ト が0の ダ ミ ー一一ノ ー ドを 付 与 す る こ と で 達 成 で き,一 般 性 を 失 わ な い 。 本 研 究 の 対 象 と す る タ ス ク グ ラ フ の 例 を Figurelに 示 す 。 ノ ー ド内 の 数 字 が タ ス ク番 号,ノ ー一一ド の 左 側 の 数 字 が タ ス ク の 処 理 時 間,エ ッ ジ 横 の くx>が 依 存 間 で 要 す る通 信 コ ス トxを 示 し て い る。 な お,グ ラ フ 中 の ノ ー ド,エ ッ ジ の 各 コ ス トは 非 負 整 数 とす る。 ,ノlask＼unTber 〃0
tL
lll.c
Pnw・ ・mgI川 摯c Figure1タ ス ク 数6の タ ス ク グ ラ フ の 例 2.6.ス ケ ジ ュ ー ル タ ス ク ス ケ ジ ュ ー リ ン グ 問 題 の 解 を ス ケ ジ ュ ー ル と 呼 ぶ 。 ま た,あ る ス ケ ジ ュ ー ル に お い て 最 も 実 行 の 遅 い タ ス ク の 完 了 時 刻 を そ の ス ケ ジ ュ ー一一ル のmakespanと 呼 ぶ 。実 行 時 間 の 最 小 化 が 目 的 の タ ス ク ス ケ ジ ュ ー リ ン グ 問 題 で は, こ のmakespanの 値 が 最 も小 さ く な る ス ケ ジ ュ ー一一ル が 厳 密 解 に 相 当 す る 。 2.7.依 存 解 決 の 遂 次 性 通 信 遅 延 を 考 慮 す る モ デ ル は 複 数 存 在 す る が,最 も汎 化 さ れ た モ デ ル は,通 信 の 重 複 に 制 限 の な いFully CoupledModelで あ る 。 しか し,情 報 の 転 送 の た め の 通 信 ポ ー トが 無 制 限 に 用 意 さ れ て い る こ と は 現 実 的 で は な い た め,本 研 究 で は よ り 実 用 的 な モ デ ル と し て,各PEが 情 報 の 送 信 ボ ー一一ト と受 信 ボ ー一一トを1つ ず つ 用 意 され た LooselyCoupledModelを 用 い る。LooselyCoupledModel で は,通 信 順 序 の 組 み 合 わ せ が 生 じ,最 適 化 の た め に は 複 数 の 組 み 合 わ せ を 考 慮 す る 必 要 が あ る。 し た が っ て, 問 題 の 計 算 複 雑 度 は 強NP困 難 か ら 更 に 複 雑 化 す る 。 3.ス ケ ジ ュ ー ル の 改 善 に 向 け た 戦 略 ∼ 通 信 の 最 適 化 ∼ 本 章 よ り後 で 示す 具体 的 な 最適 化 ア ル ゴ リズ ム の構 築 に 向 け て,本 稿 が 採 っ た依 存 関 係 の 最 適 化 の 方 針 を示 す 。 2.5.タ ス ク グ ラ フ 本 稿 で 取 り扱 う タ ス ク ス ケ ジ ュ ー リ ン グ 問 題 は 始 点 と 3.1.既 存 手法 の分 類 タ ス クス ケ ジ ュー リン グ問題 は組 み合 わせ 最 適 化 問題成 践 大 学 理 工 学 研 究 報 告 Vol.49No.1(2012.6) で あ る た め,そ の 計 算 量 と解 の 厳 密 性 に は ト レー ドオ フ の 関 係 が 存 在 す る 。 問 題 の 計 算 複 雑 度 は 強NP困 難 に 分 類 さ れ て い る こ と か ら,こ の トレ ー ドオ フ の 関 係 は 通 信 の 組 み 合 わ せ を 考 慮 し た 各 ア ル ゴ リズ ム の 計 算 量 に 応 じ た 指 数 関 数 に よ っ て 表 す こ と が で き る 。 各 ア ル ゴ リズ ム 次 第 で そ の レ ー トは 変 動 す る が,計 算 を 行 う ほ ど 考 慮 す る 組 み 合 わ せ が 増 え る た めmakespanは 短 く な る 傾 向 に あ る 。 一 方 で,計 算 量 は 各 ア ル ゴ リズ ム の 考 慮 す る 組 み 合 わ せ に よ っ て 指 数 的 に 増 加 し て し ま う。こ の 関 係 か ら, 各 ス ケ ジ ュ ー リ ン グ ア ル ゴ リズ ム は 計 算 量 と 厳 密 性 の ど ち ら に 重 き を 置 い て い る か で 分 類 が 可 能 で あ る 。 計 算 量 を 重 視 し,タ ス ク や 通 信 の 割 り 当 て 時 に 考 慮 す る 組 み 合 わ せ を 可 能 な 限 り減 ら し た ア ル ゴ リズ ム と し て は,CP(CriticalPath)[8]やCPIDTLMISF(CriticalPath/ DataTransfer/MostImmediateSuccessorsFirst)[2]と い っ た ア ル ゴ リズ ム が 過 去 に 提 案 さ れ て い る 。 こ れ ら は リス トス ケ ジ ュ ー一一リ ン グ[3]に 基 づ く 手 法 で あ る 。 makespanの 質(厳 密 性)を 重 視 し た ア ル ゴ リズ ム と し て は,ECT(EarliestCompletionT㎞e)に 基 づ くHLFET (HighestLevelsFirstwithEstimatedTimes)[5]やETF (EarliestTaskFirst)[4]な ど の 手 法 が 提 案 さ れ て い る 。 ECTで は 最 も 早 期 に 完 了 で き る タ ス ク とPEの 組 み 合 わ せ を 考 慮 す る た め,ス ケ ジ ュ ー リ ン グ 中 に 元 の 問 題 規 模 に 応 じ た 探 索 問 題 が 生 じ る 。 3.2.方 針 の 策 定 前 章 で 述 べ た タ ス クス ケ ジ ュー リン グ問 題 の 定 義 及 び 前 節 で 述 べ た トレー ドオ フの 関係 か ら,通 信 を考 慮 した ス ケ ジ ュー リン グの 性 能 向 上 の た め の 方 針 と して,通 信 の 最 適 化 を挙 げ る。 解 の 厳密 性 に 重 きを 置 い た ア ル ゴ リズ ムで は,複 雑 な 計 算 を伴 う探 索 が発 生 して い る こ とか ら,こ れ らの ア ル ゴ リズ ム で は 計 算 量 が 問 題 規 模 に 応 じて 指 数 的 に 増 加 し て しま う。 通信 を 考 慮 した ス ケ ジ ュー リン グ に と って の 複 雑 さは,最 適 な ス ケ ジ ュー ル に 要 す る通 信 を予 測 し き れ な い 点 に あ る こ とか ら,通 信 を最 適 化 す る手 法 をス ケ ジ ュー リン グの 流 れ の 一 部 に 加 え る こ とで,解 の 厳 密 性 の 向 上 を試 み る とい う方 針 を採 っ た 。 ス ケ ジ ュー ル 上 の 通信 を 最 適 な 状 態 とす るた め には, 組 み 合 わ せ の 選 択,な い し割 り当て の 過 程 で 通 信 の 総 量 を操 作 す る こ とが 必 要 とな る。 た だ し,通 信 の 発 生 を 操 作 す る機 構 は 通 信 の 発 生 量 の バ ラ ンス を 考 慮 す る必 要 が あ る。 以 上 よ り,筆 者 は 通信 の 最 適 化 を 「よ りス ケ ジ ュー ル が 短 くな る よ うに 通 信 の 発 生 を 操 作 す る こ ど と捉 え, 通 信 を 最適 化す るた め の 経験 則 を 前処 理 とス ケ ジ ュ ール へ の割 り当 て に加 え る こ とで厳 密 性 の 向 上 を行 うア ル ゴ リズ ム の構 築 を行 っ た。 4.過 剰 な 通 信 遅 延 の 排 除 を行 うア ル ゴ リズム の 設 計 と開発 本 章 で は,前 処 理 に お い て通 信 の 最適 化 の た め に有 効 な 手 段 を 実験 に基 づ い て考 察 し,特 定 の 通信 を組 み合 わせ か ら排 除す るた め の 「仮 割 り 当て 」機 構 と,依 存 の ク リ テ ィカ ルパ ス に 着 目 した 新 た な ス ケ ジ ュー リン グア ル ゴ リズ ムCPDを 提案 す る。 4.1.通 信 に 関 す る 仮説 の提 案 通信 の組 み合 わせ の探 索 は 強NP困 難 な 計 算複 雑 度 を 持 つ部 分 問題 とな る た め,可 能 な 全 て の組 み合 わせ を探 索 した 場合,ス ケ ジ ュー リン グに 要す る時 間 は 問題 規模 に 指数 的 に 比例 して しま う。 この 部分 問題 を解 く こ とで 得 られ る組 み合 わせ に近 い解 を よ り少 な い 計算 量 で 得 ら れ れ ば,通 信 を 考慮 した ス ケ ジュ ー リ ング に対 し,従 来 よ り も解 の 相対 性 能 を 著 し く低 下 させ ず に 計算 量 を 抑 え た 手 法 を 与 える こ とが 可 能 とな る。 探 索 に よっ て 求 め た い組 み合 わせ は,探 索 の候 補 とな る 実行 可能 タス クの集 合 とPEの 組 み合 わせ で 生 じ る通 信 コス トの 総 量 が よ り少 な い もの で あ るか ら,相 対 的 に コス トの 大 き い 通信 は探 索 の 結果 得 られ る組 み 合 わせ に 含 まれ に くい と考 え られ る。 そ こで,タ ス クグ ラフ 中 の 相 対 的 に コス トの 大 き い 依存 関係 に対 し 「ス ケ ジュ ー リ ン グに お い て組 み合 わせ を 冗 長 に 増や す もの の,よ り良 質 な解 で あ るほ ど,通 信 と して コス トを支 払 う場合 が少 な い 」 とす る仮 説 を 立 て,検 証 実 験 を行 っ た。 4.2.検 証 実 験 前 節 の 仮 説 に 基 づ き,ECTに よ る 探 索 を 行 うHLFET に 対 し て,タ ス ク グ ラ フ 中 の 相 対 的 に コ ス トの 大 き い 通 信 が ス ケ ジ ュ ー ル の 生 成 に 与 え る 影 響 を 調 査 し た 。 ス ケ ジ ュ ー リ ン グ 中 の 部 分 問 題 の 探 索 時 に 探 索 候 補 か ら 除 く タ ス ク とPEの 組 み 合 わ せ を,通 信 の コ ス トの 降 順 に0 ∼10%ま で ,1%ず つ 変 化 さ せ て 計 測 を 行 っ た 結 果 を Figure2に 示 す 。 グ ラ フ の 値 に は タ ス ク 数300,CCR (CommunicationtoComputationRatio,グ ラ フ 上 の 通 信 遅 延 の 総 コ ス ト を タ ス ク の 総 処 理 時 間 で 除 算 し た 比)を 1.0と し た180種 の 異 な る タ ス ク グ ラ フ に 対 し て 計 測 し た 平 均 値 を 用 い た 。
成 踵 大 学 理 工 学 研 究 報 告 Vol.49No.1(2012.6)
薫
Figure2通 信 の 排 除 率 に 伴 う 性 能 調 査 実 験 結 果 か ら,考 慮 す る組 み 合 わ せ の 減 少 に 伴 う makespanの 増 加 は緩 や かで あ る の に対 し,計 算 量 は 急 激 に 減 少 して い る傾 向 が確 認 され た 。 特 に 通 信 の コス トが 上 位10%を 占め る組 み合 わせ を考 慮 しな い場 合 で は,全 て の 組 み 合 わ せ を 考 慮 す る場 合 と比 較 して,1.ll倍 程 度 のmakespanの 増 加 に対 し4.10倍 以 上 の 大 幅 な 実 行 時 間 の 短 縮 が 得 られ て い る。 4.3.仮 割 り当 て 前 項 の 実 験 結 果 か ら,ア ル ゴ リズ ム に 対 して 特 定 の 通 信 の組 み 合 わせ を 強 制 す る こ とで,計 算 量 と相 対性 能 が 効 率 的 な レー トで トレー ドで き る と考 え られ る。そ こで, ア ル ゴ リズ ム に よ る タス クやPEの 選 択 に依 存 せ ず に 通 信 の組 み 合 わ せ を省 略 す るた め の 前 処 理 と して,「仮 割 り 当 て 」 操 作 を 提 案 す る。 ま ず,ス ケ ジ ュー リン グ を行 う前 の 段 階 で,通 信 コス トとそ の 評 価 指 標 に 基 づ き,通 信 を省 略 す る と判 断 した タス クの 先 行 依 存 に 相 当 す るタ ス クの 番 号 を 該 当 タス ク の 付加 情 報 と して 与 えて お く。 そ して,ス ケ ジ ュー リン グ時 に 該 当 タ ス クが 選 択 され た とき,ア ル ゴ リズ ムに よ るPEの 選 択 を行 わ ず に,事 前 に与 え られ た 付 加 情 報 に 基 づ き先行 タ ス クの 割 り当 て られ たPEに 該 当 タス ク を 割 り当 て る。 従 っ て,割 り当 て 前 の タス クは 割 り当て 先 のPEが 一 意 に決 定 され るが ス ケ ジ ュー リン グは 行 わ れ て い な い 状 態 とな る。 以 降 で は この 手 法 を仮 割 り当て と 定 義 す る。 4.4.CPDア ル ゴ リ ズ ム 仮 割 り当 て に よ っ て 排 除 す る 通 信 の 選 択 を,任 意 の 問 題 に 対 し て 効 果 的 に 適 用 す る た め に,依 存 関 係 の ク リテ ィ カ ル パ ス を 応 用 し た ヒ ュ ー リス テ ィ ッ ク ア ル ゴ リズ ム CPD(CriticalPathofDependences)を 提 案 す る 。 依 存 関 係 の ク リテ ィ カ ル パ ス と は,元 の 問 題 の タ ス ク グ ラ フ か ら 通 信 コ ス トの み を 抽 出 し た 状 態 の グ ラ フ 構 造 か ら 算 出 す る 最 長 コ ス ト経 路 を 指 す 。 タ ス ク数7の タ ス ク グラ フを 例 に と り,依 存 関係 の ク リテ ィカル パ ス の例 をFigure3に 示 す 。 依 存 関係 の ク リテ ィカル パ ス は,対 象 の 問題 を ス ケ ジ ュ ー ル した 際 に最 も通 信 コス トを必 要 とす る,ス ケ ジ ュー ル に とっ て ボ トルネ ック とな る依 存 関係 の パ ス を示 して い る。 従 っ て,こ の 依存 関係 の ク リテ ィカ ルパ ス に 対 し て仮 割 り当 て を行 うこ とで,少 な く と も最 長 コス ト分 の 通 信 が発 生 す る ケ ー ス を排 除 す る こ とが 可 能 とな る。 そ の た め,依 存 関係 の ク リテ ィカル パ ス を仮 割 り当 て の判 断 基 準 と して用 いれ ば,タ ス クの優 先 順 序 を変 更す る こ とな く非効 率 な タス ク割 り当 て の組 み合 わせ を 自動 的 に 回避 す る こ とが 可能 と考 え られ る。 <3><1>6
-・ ■,■C「iticalpathofdcpcndellccs Figure3依 存 関 係 の ク リ テ ィ カ ル パ ス の 例 以 下 にCPDの 計 算 手 順 を 示 す 。 な お,リ ス トス ケ ジ ュ ー一一 リ ン グ に 基 づ く ヒ ュ ー リ ス テ ィ ッ ク ス の 計 算 量 の 少 な さ を 活 か す た め,タ ス ク の プ ラ イ オ リ テ ィ の 決 定 に はCP と 同 様 に 優 先 順 序 付 け を 用 い た 。 1 II. III. IV 元 の 問題 の タス クグ ラフ か ら,依 存 関係 の ク リテ ィ カ ルパ ス を 算 出 す る 依 存 関係 の ク リテ ィカル パ ス の経 路 上 に あ る全 て の タ ス ク を,経 路 上 の 直接 先行 タ ス クに 従 っ て仮 割 り 当 て 割 り当 て の優 先 順 序 を決 定す るた め に タ ス クの プ ラ イ オ リテ ィを ス タテ ィ ッ ク レベル か ら算 出 し,タ ス ク の プ ライ オ リテ ィ リス トを 作成 す る 割 り当 て先 のPEの 選 択 に仮 割 り当 て を 用 い て,リ ス トス ケ ジ ュー リン グを行 う 4.5.CPDの 単 体 評 価 の方 法 本 章 で提 案 したCPDの 性 能 を 評価 す るた め に,関 連 す る 従来 手 法 との 比較 に よっ て 計算 量 と解 の厳 密 性 の トレ ー ドオ フに 関す る評 価 実 験 を行 っ た。 関連 す る 従 来 手 法 に は,CPDに お け る タ ス クの プ ラ イ オ リテ ィの 決 定 の べ 一 ス とな っ て い るCP ,及 び4.3節 の仮 割 り当 て の 有 効性 を調 査 す る 検証 実験 で用 い たHLFETを 選 択 した 。成 践 大 学 理 工 学 研 究 報 告 Vol.49No.1(2012.6) 実 験 に 用 い る タ ス ク グ ラ フ は,タ ス ク ス ケ ジ ュ ー リ ン グ 分 野 の ベ ン チ マ ー ク と し て 提 案 さ れ て い る 標 準 タ ス ク グ ラ フ セ ッ ト[9]を 用 い,タ ス ク 数50,100,300と し,通 信 コ ス トをCCR=1.0と し て 各 依 存 関 係 に ラ ン ダ ム に コ ス トを 与 え た 。 実 験 値 に は,各 試 行 に お け る180種 類 の タ ス ク グ ラ フ に よ る 実 行 結 果 の 平 均 値 を 用 い た 。 各 問 題 を 解 く 際 のPE数 は,事 前 に2∼20ま で のPEで ス ケ ジ ュ ー一一リ ン グ を 行 い,最 も 良 いmakespanが 得 られ た 値 を 使 用 し た 。 実 験 環 境 を 以 下 に 示 す 。 OS:Fedoral5(Lovelock) Memory:2GB CPU:[email protected]×2 の 縦 軸(実 行 時 間 の 比)は,各 問 題 の 規 模 ご と にCPを 用 い て ス ケ ジ ュ ー一一リ ン グ し た 際 の 実 行 時 間 を 基 準 点(1.0) と し,同 じ 規 模 の 問 題 に 対 し て ア ル ゴ リ ズ ム を 変 え て ス ケ ジ ュ ー リ ン グ を 行 っ た 場 合 の 結 果 を 比 で 表 す 。 0 0 0 0 0 0 0 0 0 6 4 ユ O S 6 4 2 0 ﹂ り 唱 O 層 O ㈲ " 盈 O 雷 呂 一 ﹄ O O 醤 駆 匡 ■CPCPD■HLFET 50100300 Graphs匝7e(thcnumbcrorlas.ks) Figure5CPDと 従 来 手 法 の 実 行 時 間 の 比 較 4.6.CPDの 単 体 評 価 の 実 験 結 果 CP,CPD,HLFETの3種 の ア ル ゴ リズ ム を 用 い て, タ ス ク 数50,100,300の 規 模 の ス ケ ジ ュ ー一一リ ン グ を180 種 類 ず つ 解 い た 際 のmakespanの 比 較 を 行 っ た 実 験 の 結 果 をFigure4に 示 す 。図 の 横 軸 は 問 題 の 規 模(タ ス ク 数) を 表 す 。 図 の 縦 軸(makespanの 比)は,各 問 題 の 規 模 ご と にCPを 用 い て ス ケ ジ ュ ー一一リ ン グ し た 際 のmakespanを 基 準 点(1.0)と し,同 じ規 模 の 問 題 に 対 して ア ル ゴ リズ ム を 変 え て ス ケ ジ ュ ー リ ン グ を 行 っ た 場 合 の 結 果 を 比 で 表 す 。 口 ﹂ U ω = O 8 0 6 0 4 0 つ 層 0 0 恩 O 鵠 儒 盈 雷 5 島 め O ど 儒 一自 ﹄ O O = 儒 匡 ■CPCPD■HLFET 50100300 Graphsize(thenumberoftasks) Figure4CPDと 従 来 手 法 のmakespanの 比 較 各 タ ス ク 数 でCPに よ る ス ケ ジ ュ ー一一ル のmakespanを 基 準 と し たCPDの 相 対 性 能 は,タ ス ク数50の と き 約85%, タ ス ク 数100の と き 約90%,タ ス ク数300の と き 約93% と な り,い ず れ の 問 題 規 模 の 実 験 に お い て もmakespan が 改 善 さ れ た 。 提 案 し たCPDは,makespanの 性 能 に つ い て,い ず れ の 問 題 規 模 に お い て もCPとHLFETの 中 間 程 度 の 結 果 と な っ た 。 同 条 件 で 実 行 時 間 の 比 較 を行 っ た 実 験 の 結 果 をFigure5 に 示 す 。 図 の横 軸 は 問題 の 規 模(タ ス ク数)を 表 す 。 図 各 タ ス ク 数 の 問 題 規 模 で,CPに よ る ス ケ ジ ュ ー一一リ ン グ の 実 行 時 間 を 基 準 と し たCPDの 相 対 性 能 は,タ ス ク数 50の と き 約16%,タ ス ク 数100の と き 約12%,タ ス ク 数300の と き 約2%と な り,平 均 で10%程 度 計 算 量 が 増 加 し た 。 HLFETを 含 む3種 の ア ル ゴ リズ ム の 対 比 と し て は,提 案 し たCPDは,計 算 量 の 性 能 に つ い て,い ず れ の 問 題 規 模 に お い て もCP以 上HLFET未 満 の 計 算 量 を 要 す る 結 果 と な っ た 。 4.7.CPDの 評 価 実 験 に 対 す る 考 察 makespanの 実 験 に お い て,makespanの 推 移 がCP,CPD, HLFETの 順 に 短 縮 傾 向 に あ る 点 に つ い て 考 察 を行 う。タ ス ク の 選 択 順 序 を 静 的 な 解 析 情 報 か ら一 意 に 決 定 す る CPで は,通 信 が 考 慮 し た ヒ ュ ー一一一リ ス テ ィ ッ ク が 用 い ら れ て い な い た め,CPDが 依 存 関 係 の ク リ テ ィ カ ル パ ス を 仮 割 り 当 て で 排 除 し た こ と に よ る影 響 がCPと のmakespan の 差 と し て 現 れ て い る も の と 考 え ら れ る 。 一 方 で, HLFETと の 対 比 で は,CPDが 仮 割 り当 て に よ っ て 通 信 を 最 適 化 し た 場 合 の 組 み 合 わ せ を 含 む 全 て の 組 み 合 わ せ を 探 索 し て い る た め,よ り厳 密 に ス ケ ジ ュ ー ル が 短 く な る タ ス ク とPEの 組 み 合 わ せ が 算 出 さ れ,CPDと の makespanの 差 を 生 じ る 要 因 に な っ て い る と考 え ら れ る 。 makespanに 関 し て 以 上 の 結 果 が 得 られ た 一 方 で,実 行 時 間 に つ い て は,CPDの 計 算 量 が ほ ぼCPと 変 わ ら な い 結 果 と な っ た 。 した が っ て,CPDは,よ り 計 算 量 の 少 な いCPや,計 算 量 を 多 く 払 っ て で も よ り厳 密 な ス ケ ジ ュ ー ル を 求 め よ う とす るHLFETに 対 し,ス ケ ジ ュ ー リ ン グ の 計 算 量 と厳 密 性 の バ ラ ン ス に 関 す る 比 較 で,非 常 に 効 率 的 な ス ケ ジ ュ ー リ ン グ が 行 わ れ て い る と言 え る 。
成 践 大 学 理 工 学 研 究 報 告 Vol.49No.1(2012.6) 5.通 信 の 割 り当 て を高 速 に 行 うア ル ゴ リズ ム の 設 計 と開 発 本 章 で は,ア ロケ ー シ ョンの 工 程 に お い て 通 信 の 最 適 化 の た め に 有 効 な 手 段 を考 察 し,通 信 の 割 り当て 先 を 効 率 的 に 走 査 す るた め の 割 り当 て ア ル ゴ リズ ムCEAを 提 案 す る。 対 象 の 通 信 が 割 り当 て 可 能 な領 域 は 暫 定 の ス ケ ジ ュー ル 上 に 複 数 存在 す る場 合 が あ り,特 定 の 組 み 合 わ せ で 生 じ る最 適 な 割 り当 て 位 置 を よ り少 な い 計 算 量 で 算 出 し, 計 算 量 を 抑 えた うえで厳 密性 の 向 上 が 可 能 とな る こ と を 示 す。 5.1.割 り当 て ス テ ッ プの 最 適 化 の 必 要 性 タス クの 割 り当 て 以 上 に,通 信 の 割 り当 て は 複 雑 で あ る。 な ぜ な ら,通 信 の 割 り当 て は,タ ス クの 割 り当て と 同 様 に 依 存 関係 を 考 慮 す るだ け で な く,割 り当て の 度 に 依 存 情 報 の 送信 側 と受信 側 で 共 通 した 時 間 帯 に 目的 の 通 信 コス ト分 の ア イ ドル 時 間 が 各 々 の ス ロ ッ トで 連 続 して い る こ と を検 査 す る必 要 が あ るた め で あ る。 既 存 の ア ル ゴ リズ ム の 多 くは,タ ス ク及 び 通 信 が ス ケ ジ ュー ル に 割 り当 て られ る際 の 割 り当 て の タイ ミ ン グ を 一 意 に 決 定 して い る。 そ の 割 り当 て タイ ミ ン グに は,割 り当 て 先 のPEの 対 象 ス ロ ッ トが 最 後 に ア イ ドル 状 態 と な っ た 時刻 以 降 で,依 存 関係 の整 合1生を満 た す 最 短 の 時 刻 が 選 択 され て い た 。 この 選 択 方 法 を取 るメ リッ トと し て は,タ ス ク及 び 通 信 の ス ケ ジ ュー ル へ の 割 り当て 処 理 に お け る計 算 量 を 最 小 限 に 抑 え られ る,と い うこ とが 考 え られ る。 しか し,通 信 を 考 慮 した ス ケ ジ ュー リン グ に お い て この 割 り当 て 方 法 を 用 い た 場 合,ス ケ ジ ュー ル に 冗 長 な ア イ ドル 時 間 が 多 く発 生 し,結 果 と してmakespan も長 くな っ て しま うとい う深 刻 な 問題 が あ る。 前 述 の 検 査 を用 い て,通 信 の 割 り当 て 可 能 か つ 最 短 の 実 行 開 始 時 刻 を保 証 す る ア イ ドル 領 域EAIT(Earliest AllocatableIdleTe㎜)を 特 定 す るに は,暫 定 解 の ス ケ ジ ュー ル に既 に 割 り当て られ た タス ク及 び 通 信 の 間 にあ る ア イ ドル領 域 を逐 次 に 走 査 す る必 要 が あ る。 通 信 の 発 生 量 は 問 題 規 模 の 増加 に 比 例 す るた め,こ の 走 査 に 要 す る 計 算 量 は ス ケ ジ ュー リン グに お け るボ トル ネ ッ ク とな る こ とが 予想 され る。 した が っ て,こ の 走 査 に 関 す る計 算 量 を 可 能 な 限 り低 減 させ るた め に は,効 率 的 な 割 り当 て ア ル ゴ リズ ム が 必 要 とな る。 5.2.共 通 ア イ ドル 時 間 の 導 入 最 小 の 計 算 量 で 対象 の 通 信 の 最 適 な割 り当 て 先EAIT を 特 定 す る た め に,新 た な 定 義 を 導 入 す る 。 先 行 タ ス クTpと 後 続 タ ス クTsを 順 序 付 け る 依 存 関 係 Dpsが コ ス ト α を 持 ち,Tpを 処 理 し た 処 理 装 置PEpとTs を 処 理 す る 処 理 装 置PEsが 異 な る と き,Dpsに よ る 通 信 の 割 り 当 て 走 査 対 象 と な る ア イ ドル 領 域 は,Tpの 処 理 が 完 了 し た 時 刻 よ り も 後 で,PEpの 送 信 ス ロ ッ ト とPEsの 受 信 ス ロ ッ トが 同 時 に 単 位 時 間 以 上 の 連 続 し た ア イ ドル 時 間 を 持 つ 全 て の ア イ ドル 領 域 に 相 当 す る 。 こ こ で,割 り 当 て 対 象 の 通 信 の 先 行 依 存 タ ス ク の 実 行 完 了 後 に,2 つ の ス ロ ッ トが 同 時 に ア イ ドル 状 態 と な る タ イ ミ ン グ と そ の 連 続 す る ア イ ドル 時 間 を 持 つ ア イ ドル 領 域 を,PEp か らPEsへ の 通 信 の 「共 通 ア イ ドル 領 域(SharedIdle Te㎜)」 と 定 義 し,SITpsと 表 記 す る。 5.3.共 通 ア イ ドル 時 間 を 用 い たEAITの 特 定 前 述 の 定 義 に よ っ て 対 象 の 通 信 のEAITが 高 速 に 導 出 可 能 と な る こ と を,PEpとPEsの 送 受 信 ス ロ ッ トの 具 体 例 を 用 い て 示 す 。 PE (PrcdcCc PE 〔Succc ThcSctof intersection 一 TLme 唱 tof .ldlcTcrmP・ ,/■ ゆ 1/一}TLmc EAITps〔andOncofSllarcdIdloTcnllP∼)α Figure6共 通 ア イ ドル 領 域 の 抽 出 Figure6の 上部 は,コ ス トαを 持 つ 依 存 関係DPSの 通 信 を割 り当 て る とき,そ の先 行 依 存 タ ス ク の 実 行 完 了 以 降 の,PEpの 送信 ス ロ ッ トとPEsの 受信 ス ロ ッ トの ア イ ドル 領 域 を表 して い る。 これ らの ス ロ ッ ト内 の 矢 印 は DPS以 外 の 依存 に よっ て発 生 した 通信 の た め に ス ロ ッ ト が使 用 で き な い 状態 を示 して お り,斜 線 の 帯 の 部分 が 現 在 の各 ス ロ ッ トの ア イ ドル領 域 で あ る。 これ らの ア イ ドル 領 域 の積 か ら抽 出 され る,共 通 ア イ ドル領 域 の集 合 をFigure6の 下部 に示 す 。Dpsに よ る通信 の割 り当 て の た め に 走査 が行 われ る際 は,共 通 ア イ ドル 領 域 を 時刻 の早 い もの か ら順 に コス トα以 上 の ア イ ドル 時 間 を 持 つ か判 定 して い く。 発 見 され た コス トα以 上 の ア イ ドル 時 間 を持 っ アイ ドル 領 域 の 集 合 が,Dpsの 割 り 当 て 可 能 な ア イ ドル 領 域 の集 合 とな る。 割 り当 て 可能 な ア イ ドル領 域 の集 合 の うち最 も開 始 時 刻 の 早 い ア イ ドル領 域EAITは,抽 出 され た 共 通 ア イ ド ル 領 域 の集 合 を 走査 す る こ とで 取 り出 しが 可能 で あ る。
成 踵 大 学 理 工 学 研 究 報 告 Vol.49No.1(2012.6) 任 意 の ス ロ ッ トに お け るア イ ドル領 域 の 集 合 が 時 系 列 順 に リス ト化 され た 状 態 を保 つ こ とか ら,共 通 ア イ ドル 領 域 の 集 合 は 時 系 列 順 に リス ト化 され て い る。 ま た,全 て の 共 通 ア イ ドル領 域 は 依 存 上 の 割 り当 て 開 始 時 刻 の 条 件 を満 た して い る。 した が っ て,時 系 列 順 に 整 理 され た 共 通 ア イ ドル領 域 の リス トを順 方 向 に 走 査 す れ ば,最 小 の 計 算 量 でEAITを 得 られ る。 5.4.CEAア ル ゴ リ ズ ム 共 通 ア イ ドル 領 域 を 用 い た 通 信 の 割 り当 て 候 補 の 限 定 操 作 を 応 用 し,EAITを 高 速 に 導 出 す る 割 り 当 て ア ル ゴ リズ ムCEA(mostCompactandEarliestAllocation)を 提 案 す る。 CEAは,依 存 情 報 の 送 信 側 の 送 信 ス ロ ッ トと 受 信 側 の 受 信 ス ロ ッ トが 同 時 期 に 必 要 な 通 信 コ ス ト以 上 の 時 間 に 連 続 し て ア イ ドル 状 態 と な る 部 分 に し か 割 り 当 て られ な い,と い う通 信 の 特 性 を 利 用 し,両 ス ロ ッ トの ア イ ドル 領 域 が 重 複 し て い る 部 分 だ け を 走 査 対 象 と し て 通 信 の 割 り当 て ス テ ッ プ の 効 率 化 を 実 現 し て い る 。 加 え て,CEAを 用 い た 割 り 当 て で は,通 信 の 組 み 合 わ せ の 選 択 が 同 一 で あ っ て も,従 来 の 割 り当 て タ イ ミ ン グ の 算 出 方 法 か ら 得 ら れ る ス ケ ジ ュ ー ル 以 上 に 良 質 で あ る (makespanが 短 い)こ と が 保 証 さ れ る 。 以 下 にCEAの 割 り 当 て ア ル ゴ リ ズ ム を 示 す 。 . I I I III. IV V. 割 り当て る通信 を任 意 の 方 法 で1つ 選 択 す る 先 行 タス クの 処 理 が 完 了 した 時刻 以 降 に 存 在 す る, 先 行 タス クを 処 理 したPEの 受 信 ス ロ ッ トと後 続 タ ス ク を処 理 す る こ とに な るPEの 送 信 ス ロ ッ トの ア イ ドル 領 域 の積 集 合 を 取 り,共 通 ア イ ドル 領 域 の 集 合 を 得 る ア イ ドル 状 態 の 開 始 時刻 の 昇 順 に 共 通 ア イ ドル 領 域 を1つ 選 択 す る 選 択 した ア イ ドル領 域 の ア イ ドル 時 間 の 長 さが 手 順 1で 選 択 した 通 信 の コス ト以 上 な らば,手 順VIヘ ア イ ドル 時 間 が 通信 コス ト未 満 の 場 合,開 始 時 刻 の 昇 順 に 次 の ア イ ドル 領 域 を 選 択 し,手 順IVに 戻 る 選 択 した 共 通 ア イ ドル領 域 がEAITに 相 当 し,そ の ア イ ドル領 域 の 開 始 時刻 に 対 象 の 通信 を 割 り当て 価 実 験 を 行 う。 CEAは 割 り 当 てPE数 の 変 化 に よ っ て 大 き く性 能 が 変 化 す る 事 が 予 想 され る た め,PE数 は2∼12PEま で,2っ ず つPEの 数 を 増 や しな が ら,CPにCEAを 適 用 し た 場 合 と適 用 し な か っ た 場 合 の 実 行 時 間 とmakespanの 比 較 を 行 っ た 。 実 験 に 用 い る タ ス ク グ ラ フ は,タ ス ク ス ケ ジ ュ ー リ ン グ 分 野 の ベ ン チ マ ー ク と し て 提 案 され て い る標 準 タ ス ク グ ラ フ セ ッ ト[9]を 用 い,通 信 コ ス トをCCR=1,0と し て 各 依 存 関 係 に ラ ン ダ ム に コ ス トを 与 え た 。 実 験 値 に は, 各 試 行 に お け る180種 類 の タ ス ク グ ラ フ に よ る 実 行 結 果 の 平 均 値 を 用 い た 。 実 験 環 境 は4.5節 と 同 様 で あ る 。 5.6.CEAの 単 体 評 価 の 実 験 結 果 以 下 の 実 験 結 果 で は,従 来 の 通 信 の 割 り 当 て 方 法 を 用 い た 場 合 のCPを 「CP」,CEAを 適 用 し たCPを 「CP+CEA」 と 表 記 す る 。 CP,及 びCP+CEAを 用 い て,タ ス ク 数100,300の 規 模 の ス ケ ジ ュ ー リ ン グ を180種 類 ず つ 解 い た 際 の makespanの 比 較 を 行 う実 験 の 結 果 をFigure7に 示 す 。 図 の 横 軸 は 問 題 の 規 模(タ ス ク 数)を 表 す 。 図 の 縦 軸 (makespanの 比)は,PE数 を2と し てCPで ス ケ ジ ュ ー一 リ ン グ し た 際 のmakespanを タ ス ク数 の 規 模 別 の 基 準 点 (1,0)と し,同 じ 問 題 に 対 し て ア ル ゴ リ ズ ム な い しPE 数 の 異 な る ス ケ ジ ュ ー一一リ ン グ を 行 っ た 場 合 のmakespan を 比 で 表 す 。 6 4 , 暫 0 8 '0 4 } 冒 O ∩ [ し 巨 を ヨ ﹄ 己 & 乙 葦 ∈ し ︻ : ξ 慨 生 CP 100 ■PE2P￡4■PE6■PE8■PElOPLI2
1■1
(■P・ClA CP Graphsve(thenuniberot'taskb) 30{1■
⋮
1
VI. VII.手 順1で 選 択 し た 通 信 の 割 り当 て が 完 了 と な る 5.5.CEAの 単 体 評 価 の 方法 本 章 で 提 案 したCEAの 性 能 を評 価 す る た め に,既 存 ア ル ゴ リズ ム で あ るCPの 通 信 の 割 り当て タイ ミン グに, 従 来 の 方 法 を 用 い た 場 合 とCEAを 用 い た 場 合 の 比 較 に よっ て,計 算 量 と解 の厳 密性 の トレー ドオ フ に関 す る評 Figure7CPとCP+CEAのmakespanの 比 較 い ず れ のPE数 い ず れ の タ ス ク数 の 問 題 で も,CEA を 適 用 し た 場 合 にmakespanの 短 縮 傾 向 が 得 られ た 。短 縮 傾 向 が 最 も 強 か っ た の は,PE数12で タ ス ク 数300の 問 題 に 対 し てCP+CEAで ス ケ ジ ュ ー一一リ ン グ を 行 っ た 場 合 で,同 じ 問 題 を 解 い たCPのmakespanと 比 較 し て 約76% 短 縮 さ れ たmakespanを 得 た 。短 縮 傾 向 が 最 も 弱 か っ た の は,同 じ場 合 のPE数12の 試 行 で,同 じ 問 題 を 解 い た成 踵 大 学 理 工 学 研 究 報 告 Vol.49No.1(2012.6) CPのmakespanと 比 較 し て 約10%短 縮 さ れ たmakespan を 得 た 。 PE数 の 増 加 に 伴 う変 化 で は,CP+CEAはPEの 数 が 増 え る 毎 にmakespanを 短 縮 す る ス ケ ジ ュ ー ル を 算 出 し た 。 一 方,CPで はPEの 数 が 増 え る 毎 にmakespanが 長 く な る 冗 長 な ス ケ ジ ュ ー ル が 算 出 さ れ た 。 同 条 件 で 実行 時 間 の 比 較 を行 っ た 実 験 の 結 果 をFigure 8に 示 す。 図 の 横 軸 は 問 題 の 規模(タ ス ク数)を 表 す 。 図 の 縦 軸(実 行 時 間 の比)は,PE数 を2と してCPで ス ケ ジ ュー リン グ した 際 の 実行 時 間 を タス ク数 の 規 模 別 の 基 準 点(1.0)と し,同 じ問 題 に 対 して ア ル ゴ リズ ムな い しPE数 の 異 な るス ケ ジ ュー一リン グ を行 った 場 合 の 実 行 時 間 を比 で 表 す 。 ■PI.2Pト4■PI6■PI・S■P卜1〔,P}」1ユ 6 4 2 0 罵 6 4 ユ O ー ー ー ー 0 0 0 0 0 ( 口 り 雷 0 = O 鳴 鶉 ￡ 2 ヒ = ﹂ O O 冒 謂 二 CP 100 cP・ClA cP (量r3,h、17c(監hc訂1ulnbcr軋,ft;1、ks) lov cp・Cl八 Figure8CPとCP+CEAの 実 行 時 間 の 比 較 い ず れ の タ ス ク数 の試 行 に お い て も,PEの 増 加 に従 っ てCP+CEAの 実 行 時 間 に短 縮 傾 向 が得 られ た。 た だ し, 同 じPE数 で 行 うCPの 実 行 時 間 よ り短 くな る こ とは な か っ た。 一 方 でCPを 用 い た 結 果 で は 実 行 時 間 の 増 加 に 従 っ て 実 行 時 間 が 長 くな っ た。 同 じ規模 の 問 題 を同 じPE数 で解 い た と き,CPに 対 す るCP+CEAの 実行 時 間 の差 が最 も小 さか っ た の は,タ ス ク数300の 問題 をPE数12で 解 い た場 合 で あ り,こ の と き同 じ問題 を解 い たCPに 対 し14%程 度 実 行 時 間 が 長 く な っ た 。 ま た,平 均 で は約19%実 行 時 間 が 長 い 結 果 とな っ た。 5.7.CEAの 実 験 結 果 及 び 設 計 に 関 す る 考 察 makespanに 関 す る 全 て の 実 験 で,CEAに よ っ て ス ケ ジ ュ ー一一ル が 改 善 さ れ た こ と に つ い て 考 察 を 行 う。CEAは 従 来 の 割 り当 て 方 法 以 上 のmakespanを 生 成 す る こ と が 理 論 上 保 証 さ れ て お り,実 験 で も こ の 性 質 が 確 認 さ れ た 。 特 にmakespanが 短 く な っ た ケ ー ス で は,従 来 の 割 り当 て 手 法 と 比 較 し て 約76%も のmakespanの 短 縮 に 成 功 し て い る こ と か ら,makespanの 改 善 に 関 し てCEAが 有 効 で あ る とい え る。 実行 時 間 の 比 較 実 験 の 結果 か ら,CEAの 相 対 的 な 計 算 量 に つ い て 考察 を行 う。これ らの 実験 結 果 に お い てCEA は,タ ス ク 数 の 増加 に伴 う計 算 量 の爆 発 的 増加 を起 こ さ ず,PE数 の 増加 に対 して は 計 算 量 の 低 下 が 見 られ た こ と か ら,非 常 に少 な い 計算 量 でEAITを 発 見 で き て い る と い える。 した が っ て,ア イ ドル領 域 に よる ス ロ ッ ト情報 の 管理,及 びTEAに 通信 を割 り当 て る ヒュ ー一一一リス テ ィ ッ ク が通 信 を 考慮 した タ ス クス ケ ジ ュー リン グの 通信 の割 り当 て に対 して 有効 で あ る と考 え られ る。 加 え て,実 行 時 間 の 比 較 実 験 で 生 じた,PE数 の 増加 に 伴 うCP+CEAの 計 算 量 の低 下 現 象 につ い て考 察 す る。対 象 の計 算 量 低 下 現象 は,PE数 の 増加 に伴 う共 通 ア イ ドル 領 域 の 変化 に 要 因 が あ る と考 え られ る。PE数 を2と して ス ケ ジ ュー一一リン グを行 う場合,一 方 のPEの 送信 ス ロ ッ トと も う一 方 のPEの 受 信 ス ロ ッ トは 全 く同 一 の割 り当 て 状態 とな る。 この 場合,こ れ らのPEの い ず れ が 依 存 情 報 を 送信 ・受 信 して も,そ の 共 通 ア イ ドル領 域 に は各 ス ロ ッ トの ア イ ドル 領 域 の全 て が相 当 して しま う。 した が っ て,PE数 が少 な い試 行 で は,相 対 的 に 計 算 量 が 増加 して い る と考 え られ る。各PEの ス ロ ッ トの 状 態 はPEの 増 加 に伴 っ て,そ の他 の よ り多 くのPEと 関 連 を持 つ こ と に な る た め,共 通 ア イ ドル 領 域 が絞 りこ まれ,EAIT を 走査 す る 計算 量 が 少 な くな る傾 向 に あ る と考 え られ る。 以 上 の 実 験結 果 と考察 か ら,CEAは,そ の 特徴 と して 適 用 対 象 の アル ゴ リズ ム を 幅 広 く選 択 可能 で あ る と考 え られ る。CEAは 通 信 の 選 択 順 序 を規 定 して いな いた め, 既 存 の 多 くの ス ケ ジ ュー リン グア ル ゴ リズ ム との併 用 が 可 能 で あ る。 割 り当 て処 理 が 従 来 の割 り当 て方 法 以 外 の ア ル ゴ リズ ム で 規 定 され て い る場 合 に は,そ の アル ゴ リ ズ ム との 間 で,厳 密 性 と計 算 量 の トレー ドオ フ を考 慮 し, 割 り当 て ア ル ゴ リズ ム の選 択 を行 うこ とが 有効 で あ る。 CEAを 用 い る こ とで,既 存 の アル ゴ リズ ム の タ ス ク や通 信 の選 択 に 関す る特 性 を 生 か した ま ま,ス ケ ジ ュー ル の み を 前倒 しにす る こ とでmakespanの 短縮 効果 が得 られ る た め,CEAと 処理 が 重複 しな い ス ケ ジ ュー一一リン グア ル ゴ リズ ム に とっ て非 常 に 有効 な手 段 で あ る と考 え られ る。 6.複 合 評 価 6.1.提 案 手 法 本 章 で は,前 述 の2つ の ヒ ュ ー一一リ ス テ ィ ッ ク ス を 用 い た ス ケ ジ ュ ー リ ン グ ア ル ゴ リ ズ ム を 提 案 手 法 と 呼 称 し (図 中 で はCPD+CEAと 表 記),既 存 手 法 と の 比 較 に よ る 評 価 実 験 と考 察 を 示 す 。
成 践 大 学 理 工 学 研 究 報 告 Vol.49No.1(2012.6) 6.2.評 価 方 法 提 案 手 法 の 評 価 は,計 算 量 と厳 密 性 の トレ ー ドオ フ に 着 目 し,実 行 時 間 と 解 の 相 対 性 能 を 比 較 す る こ と で 行 っ た 。 実 行 時 間 は 各 手 法 が ス ケ ジ ュ ー ル を 求 め る ま で に 要 す る 時 間 で あ る 。解 の 相 対 性 能 は 各 手 法 に よ るmakespan をCPと の 比 に よ っ て 示 す 。 比 較 対 象 と し て 選 択 し た 既 存 手 法 は,CP,CPIDTLMISF, HLFET,ETFの4種 の ス ケ ジ ュ ー一一リ ン グ ア ル ゴ リズ ム で あ る。 提 案 手 法 は ア ロ ケ ー一一シ ョ ン の 工 程 でCEAを 用 い る た め に,割 り当 てPE数 の 変 化 に よ っ て 大 き く 性 能 が 変 化
す る と 予 想 し,PE数 は2∼12PEま で2つ ず っPEの 数 を
増 や し な が ら,実 行 時 間 とmakespanの 計 測 を 行 っ た 。 実 験 に 用 い る タ ス ク グ ラ フ は,タ ス ク ス ケ ジ ュ ー リ ン グ 分 野 の ベ ン チ マ ー ク と し て 提 案 さ れ て い る 標 準 タ ス ク グ ラ フ セ ッ ト[9]を 用 い て,通 信 コ ス トをCCR=1.0と し て 各 依 存 関 係 に ラ ン ダ ム に コ ス トを 与 え た 。実 験 値 に は, 各 試 行 に お け る180種 類 の タ ス ク グ ラ フ に よ る 実 行 結 果 の 平 均 値 を 用 い た 。 実 験 環 境 は45節 と 同 様 で あ る 。 6.3.複 合 評 価 の 実 験 結 果 提 案 手 法 を は じ め と す る 各 手 法 を 用 い て,PE数 を2∼ 12ま で2PEず つ 変 化 させ た 際 に,各 ア ル ゴ リズ ム が タ ス ク 数300の 規 模 の ス ケ ジ ュ ー一一リ ン グ 問 題 を180種 類 ず つ 解 い た 実 行 時 間 を 計 測 し た 結 果 をFigure9に 示 す 。 図 の 横 軸 は 各 ア ル ゴ リズ ム を 表 す 。図 の 縦 軸(実 行 時 間 の 比) は 相 対 グ ラ フ と な っ て お り,CPで ス ケ ジ ュ ー一一リ ン グ し た 際 の 実 行 時 間 をPE数 別 の 基 準 点(1.0)と し,同 じPE 数 の 同 じ 問 題 に 対 し て 異 な る ア ル ゴ リズ ム を 用 い て ス ケ ジ ュ ー リ ン グ を 行 っ た 場 合 の 実 行 時 間 を 比 で 表 す 。 256 ←128 64 32 16 一 CPD+CEACPDT・MISFHLFET AIgerithm 同 条 件 のCPで 計 測 し た 時 間 と比 べ て 約1.07倍 の 計 算 時 間 を 要 し た 。 最 も 実 行 時 間 比 が 大 き か っ た の はPE数12 で ス ケ ジ ュ ー リ ン グ し た 場 合 で,CPと 比 べ 約1.62倍 の 計 算 時 間 を 要 し た 。 CPIDTLMISF,HLFET,ETF及 び 提 案 手 法 の4種 の 手 法 で,CPと 比 較 し た と き の 実 行 時 間 の 加 速 度 が 最 も 小 さ い の は 提 案 手 法 で あ っ た 。 ス ケ ジ ュ ー リ ン グ 中 に 組 み 合 わ せ の 探 索 を 行 うHLFETやETFは,問 題 規 模 やPE数 が 増 え る こ と で 実 行 時 間 が 大 幅 に 増 加 し,そ の 増 加 の 加 速 度 が 最 も 大 き い の はETFで あ っ た 。 特 に,ETFを 用 い て タ ス ク数300の 問 題 をPE数12で 解 い た と き,CPと 比 較 し て195.30倍 の 実 行 時 間 を 要 し た 。 同 条 件 でmakespanを 計 測 し た 結 果 をFigurelOに 示 す 。 図 の 横 軸 は 各 ア ル ゴ リ ズ ム を 表 す 。 図 の 縦 軸(実 行 時 間 の 比)はCPで ス ケ ジ ュ ー リ ン グ し た 際 のmakespanを PE数 別 の 基 準 点(1.0)と し,同 じPE数 の 同 じ 問 題 に 対 し て 異 な る ア ル ゴ リ ズ ム を 用 い て ス ケ ジ ュ ー リ ン グ を 行 っ た 場 合 のmakespanを 比 で 表 す 。 L2 1.0 0,8 06 04 も02 0.0 Figure10各 ア ル ゴ リ ズ ム の 平 均makespanの 比 較 HLFET,ETF,及 び 提 案 手 法 はPE数 の 増 加 に 伴 い, makespanの 改 善 傾 向 が み ら れ た 。 こ の 改 善 傾 向 は 提 案 手 法 で 最 も 強 く,HLFETで 最 も 緩 や か な 傾 向 で あ っ た 。 ま た,上 記 の3つ の ア ル ゴ リ ズ ム の うち,提 案 手 法 は 問 題 規 模(タ ス ク 数)の 増 加 に よ っ て もmakespanの 改 善 傾 向 が み ら れ た 。 全 て の 試 行 で 提 案 手 法 が 最 も 良 いmakespanを 算 出 し た 。 最 もmakespanが 短 縮 さ れ た の は 提 案 手 法 を 用 い て PE数12で 解 い た 場 合 で,同 条 件 のCPのmakespanと 比 較 し て 約18.60/。 ま で 短 縮 され た 。 Figure9各 ア ル ゴ リズ ム の 平 均 実 行 時 間 の 比 較 提 案 手 法 は,CPと の 比 較 に お い て 最 も計 算 量 の 増 加 が 緩 や か で あ っ た 。 最 もCPと の 実 行 時 間 比 が 小 さか っ た の はPE数2で ス ケ ジ ュー一一リン グ した 場 合 で,こ の と き 6.4.考 察 PE数 の 増 加 に伴 う提 案 手 法 の計 算 量 の 増 加 速 度 が, CP以 外 の 比 較 対 象 の うち最 も少 な い 点 につ い て考 察 を 行 う。 提案 手 法 で は 通信 を最 適化 す るた め にCPD及 び
成 践 大 学 理 工 学 研 究 報 告 Vol.49No.1(2012.6) CEAの ア ル ゴ リズ ム を ス ケ ジ ュー一一リン グ 中 に用 い て い る こ とか ら,問 題 規 模 の 増加 に 伴 う計 算 量 の 爆 発 的 な 増 加 を抑 え る こ とに 成 功 して い る と考 え られ る。 ま た,こ の 結 果 と考 察 か ら,少 量 の 計 算 量 で 通 信 の 最 適 化 を実 現 す るCPDとCEAを 組 み 合 わ せ た こ とで,提 案 手 法 は 問 題 規模 に 依 らず 少 な い 計 算 量 を 維 持 して い る と考 え られ る。 CPと 提 案 手法 の計 算 量 の差 につ い て は,CEAに よ る ア ロケ ー シ ョンの 工 程 の 計 算 量 が 主 な 要 因 と して 考 え ら れ る。 そ の 理 由 と して は,一 度 の ス ケ ジ ュー リン グに お け るCPDとCEAの 使 用 回 数 の 違 い が 挙 げ られ る。 一 度 の ス ケ ジ ュー一一ル に お い て,CPDは 一 度 だ け使 用 され, CEAは ア ロ ケー シ ョン の 工 程 で 発 生 す る通 信 の 量 に 応 じて複 数 回 使 用 され る。 こ こで,CPDとCEAの 個 別 の 評 価 実 験 に お い て 計 算 量 へ の 影 響 はCEAが よ り強 か っ た こ とか ら,CEAに よ る通 信 の割 り当 て処 理 がCPと 提 案 手 法 の 計 算 量 の 差 を 生 じ る主 な 原 因 と して 考 え られ る。 makespanに 関 して は,提 案 手 法 のmakespanの 推 移 が PE数 の 増 加 に 伴 っ て 最 も強 い短 縮 傾 向 を示 した 点 に 着 目 し,考 察 を行 う。PE数 の 増 加 に と もな うmakespanの 短 縮傾 向 は,暫 定解 の ア イ ドル領 域 の 発 生 量 に影 響 を 受 け て い るの で は な い か と考 え られ る。PE数 とア イ ドル 領 域 の発 生 量 の 関 係 に つ い て の 考 察 はCEA法 の 評 価 の 際 に も述 べ た が,提 案 手 法 に つ い て は,そ れ に 加 えて タス クの 処 理 と通信 時 間 の バ ラ ンス に よ る影 響 が 考 え られ る。 提 案 手 法 で は,CEAに よ る割 り当て の 前 にCPDに よ る 前 処 理 が加 え られ て い るた め,依 存 関 係 の ク リテ ィカ ル パ ス 上 に 存 在 す る通 信 が 排 除 され て い る。 パ ス 上 の タ ス クは 仮 割 り当 て に よっ て 同 一 のPEに 割 り当 て られ るた め,対 象 のPEの タス ク処 理 ス ロ ッ トは ほ ぼ 無 駄 な く使 用 され て い る状 態 とな り,通 信 コス トの 支 払 い の た め に ス ケ ジ ュー ル が 伸 び る,と い う組 み 合 わ せ の 発 生 を減 少 させ て い る もの と考 え られ る。 ま た,仮 割 り当て に よ っ て 通信 の発 生 総 量 が 減 少 す るCPD単 体 の 特 性 も,提 案 手 法 のmakespanの 短 縮 に寄 与 して い る と考 え られ る。 以 上 の 考 察 と,makespanを 調 査 す る全 て の 試 行 で,提 案 手 法 が 最 良 の ス ケ ジ ュー ル を 生 成 した こ とか ら,提 案 手 法 が 用 い る通 信 の 最 適 化 は 問題 規模 に 依 らず 機 能 して い る と考 え られ る。 した が っ て,CPDとCEAの 組 み 合 わ せ はmakespanの 改 善 につ い て相 乗 効 果 を もた ら し,提 案 手 法 のmakespanに 関 す る性 能 を 高 く維 持 す る要 因 に な っ て い る と考 え られ る。 7.お わ り に 本稿 で は,依 存 関係 を 最適 化す る2つ の ヒ ュー リス テ ィ ック スCPDとCEAを 提案 し,そ の 評価 実験 の結 果 と 考 察 に つ い て報 告 した。 過 剰 な コス トを持 つ依 存 関係 に 対 して は,仮 割 り 当て とい う前処 理 を 導入 す る こ とで,対 象 の通 信 を ス ケ ジュ ー ル 上 に発 生 させ な い た め の 「仮 割 り当 て 」 とい う機 構 を 提案 した。 さ らに,依 存 関係 を任 意 の タ ス ク グラ フか ら抽 出 す る アル ゴ リズ ムCPDを 構 築 し,対 象 の 通信 が発 生 す る組 み 合 わせ を排 除 す る こ とで,計 算 量 とmakespan の トレー ドオ フ を非 常 に 低 い レー トに 抑 え た。 通信 の割 り当 て ス テ ップ に お け るmakespan短 縮 の た め の探 索処 理 に 対 して,割 り当 て候 補 領 域 の 管 理方 法 と 処 理装 置確 定後 の 走 査対 象 を 限 定 す るCEAを 構 築 し,計 算 量及 びmakespanの 改 善 を図 った 。結 果,対 象 の 通信 が 割 り当 て 可 能 な 最短 時刻 を非 常 に 少 な い 計 算 量 で算 出 可 能 とな っ た。 さ らに,こ れ らの複 合 利 用 につ い て も評 価 実 験 を行 い, 計 算 量 及 び厳 密 性 の 両 面 か らそ の 有用 性 を 示 した。 今後 は,よ りmakespanを 短 縮 す るた め の ヒ ュー リス テ ィ ック の発 見 と応 用 が 望 まれ る。 謝 辞 本研 究 の 一部 は,文 部 科 学省 戦 略 的研 究 基盤 形成 支援 事 業 の 補助 を受 け て行 っ た こ とを こ こに記 し,謝 意 を表 します 。 参 考 文 献 [1]Bemstein,D.Rodeh,andM.Gertner,1,"Onthe complexityofschedul血gproblemsforparal-lel/ pipelinedmachiles",IEEETrans,Vol.38No.9 pp.1308-1313,1989. [2]H.Kasahara,H.Honda,andS.Narita,"Parallel process血gofnearfinegraintasksusingstatic schedulilgonoscar",IEEESupercomputing'90,1990. [3]EdwardG.Coffman,`℃omputerandJob-shop SchedulingTheory",JolmWileyandSons,1976. [4]J.J.Hwang,YC.Chow,F.D.Anger,andC.YLee, c`Schedulilgprecedencegraphsilsystemswith in-terprocessorcommunicationtimes",SIAMJoumalof Computingl8(2),1989. [5]Kwok,Y-K.andA㎞ad,1."Benchniarkingthetask graphschedul血galgorithms'ラ,IPPSISPDP,1998.
成 践 大 学 理 工 学 研 究 報 告 Vol.49No.1(2012.6) [6] [7] [8] [9] MasahikoU.,RyujiS.,MunenoriK.,"Heuristicsearch basedonbranchandboundmethodfbrtaskschedulilg consider血gcommunicationove血ead",IEEEPacific RimCon.,2011. XiaohongK.,JunS.,BinYandW6nboX.,"AnEfficient Quan加m-BehavedParticlesw㎜opt㎞izationtbr MultiprocessorSche血ling",ICCS2007,Volume 4487/2007pp278-285,2007. T,C.Hu,``Parallelsequencingandassemblyline problems",OperationsResearch,Novem-ber/December l961vol.9no.6PP.841-848,1961. StandardTaskGraphSet, http:〃wwwkasahara.elec,waseda.acjp/schedule/, KasaharaLab.,WasedaUniv.,24January2012.
