成 腰 大 学 理 工 学 研 究 報 告 J,Fac,Sci,Tech.,Sei/keiUniv. Vol.50No.1(2013)pp.17-28
通 信 遅 延 を含 む タ ス クス ケ ジ ュー リング問 題 の
並 列 分 枝 限 定 法 に基 づ く探 索 解 法
栗 田 浩 一*1,甲 斐 宗 徳*2A Parallelized Branch-and-Bound Search Method for Task Scheduling Problem with Consideration of Communication Overhead
Kohichi KURITA *1, Munenori KAI * 2
ABSTRACT : Since the task scheduling problems in the multiprocessor environments belong to the class of strong NP hard combinatorial optimization problem, the depth first search algorithms based on branch and bound(B&B) method are most effective to find an optimal solution. In order to reduce the search time with B&B method, it is the most important key to construct search algorithms with the way to bound many branches in the search space by more accurate lower bounds. However, it seems that there are no algorithms to create such lower bounds with consideration of processing system environments. In this paper, we propose three algorithms to create the lower bounds with consideration of number of processors, the lower bounds with consideration of processing time of successive tasks, and the lower bounds re-calculated in search process. Our experiments show that these algorithms give more accurate lower bounds and improve efficiency of search.
Keywords : Task scheduling, Combinatorial optimization problem, Branch and bound
(Received March 31, 2013) 1.は じ め に タ ス ク ス ケ ジ ュ ー リ ン グ は,並 列 処 理 環 境 で 各 マ シ ン に 最 適 な タ ス ク の 割 当 て を 決 定 し 処 理 パ フ ォ ー マ ン ス を 最 大 限 に 引 き 出 す 技 術 で あ る 。 現 在 ま で に グ リ ッ ド コ ン ピ ュ ー テ ィ ン グ や ク ラ ス タ 計 算 機 の 普 及 か ら,タ ス ク 間 の 依 存 関 係 に よ り生 じ る ノ ー ド/プ ロ セ ッ サ 間 の 通 信 遅 延 を 考 慮 し た ス ケ ジ ュ ー リ ン グ 手 法 の 需 要 が 高 ま っ て い る 。 こ の タ ス ク ス ケ ジ ュ ー一一リ ン グ は,強NP困 難 な 組 合 せ 最 適 化 問 題 に 属 す る[1]。 従 っ て 最 適 解 を 得 る に は 本 質 的 に 分 枝 限 定 法 に よ る 探 索 解 法 が 必 要 に な る 。 筆 者 は,通 信 遅 延 を 考 慮 し な い タ ス ク ス ケ ジ ュ ー リ ン グ 問 題 で 既 に 有 効 性 が 証 明 さ れ て い る 逐 次 最 適 化 解 法DMHS(Depth First/1mplicitHeuristicSearch)法 に 通 信 遅 延 の 組 合 せ を 足 *1:理 工 学 研 究 科 理 工 学 専 攻 博 ± 前 期 学 生 *2:理 工 学 研 究 科 理 工 学 専 攻 教 授(kai@st ,seikei.acjp) し 合 わ せ,そ れ を 複 数 コ ア で 並 列 処 理 す る 並 列 最 適 化 解 法 の 研 究 を 行 っ て い る[2]。DMHS法 は,分 枝 限 定 法 に よ る 解 法 を 行 うた め,分 枝 操 作 に 各 タ ス ク の プ ラ イ オ リ テ ィ を 使 用 し た 部 分 ス ケ ジ ュ ー リ ン グ と 限 定 操 作 に 下 限 値 を 使 用 し た 枝 切 り を 行 う。 こ の プ ラ イ オ リ テ ィ と 下 限 値 に は タ ス ク の 処 理 時 間 の み を 考 慮 し,当 該 タ ス ク か ら エ ン ド ノ ー ド ま で に 最 低 限 必 要 と さ れ る 経 路 長(以 下 CP:CriticalPath長)が 使 用 され て き た 。 し か し,通 信 遅 延 の 有 無 は,こ のCP長 に 変 化 を 与 え て し ま う場 合 が あ る 。 従 っ て こ の ま ま 使 用 し て も こ の 下 限 値 に 本 来 の 性 能 を 望 む こ と は で き な い 。昨 年 度 ま で の 本 研 究 室 の 研 究 成 果 で, 暫 定 的 に 通 信 遅 延 を 算 入 し たREDIC(RemainingDistance IncludingCommunicationOverhead)法 が 考 案 され た[3]。 こ の 手 法 は 下 限 値 を 求 め る 際 に 該 当 す る タ ス ク か ら 限 定 さ れ た 範 囲 内 の タ ス ク を 考 慮 に 入 れ る も の で あ っ た 。 そ の た め,ま だ 発 展 の 余 地 が あ る 。 従 っ て,本 稿 で はREDIC 法 を 改 良 す る こ と で 探 索 効 率 の 向 上 を 図 っ た 。
成 践 大 学 理 工 学 研 究 報 告 Vol50No.1(2013.6) 2.問 題 定 義 タ ス ク と は,実 行 プ ロ グ ラ ム を 並 列 処 理 す る た め に 分 割 さ れ た 部 分 処 理 で あ る 。タ ス ク 集 合 は タ ス ク を ノ ー ド, 依 存 関 係 を 有 向 エ ッ ジ で 表 し,入 口 と 出 口 に ダ ミ ー ノ ー ド を 設 置 し た タ ス ク グ ラ フ と 呼 ぶDAG(DirectedAcyclic Graph)で 表 現 す る こ と が で き る(図1)。 タ ス クiの 処 理 に 要 す る 時 間 をVViと 表 す 。 こ れ を 同 一 の 処 理 能 力 を 所 持 し たm(〉=1)台 の プ ロ セ ッ サ(以 下PE:ProcessorElement)に 割 当 て,タ ス ク 毎 に 並 列 実 行 さ せ る 。 さ ら に 本 研 究 で は, 直 接 先 行 後 続 関 係 に あ る タ ス ク 同 ± が 異 な るPEに 割 当 て ら れ た 場 合,デ ー タ 依 存 解 決 に 必 要 な 通 信 に と も な う 遅 延 時 間 を 考 慮 す る 。 そ の た め,エ ッ ジ に 通 信 遅 延 時 間 を 付 加 す る 。 こ の 場 合,通 信 遅 延 時 間 は タ ス クiと そ の 親 タ ス ク の タ ス クjが 互 い に 異 な るPEに 割 当 て られ た 場 合, エ ッ ジ に 付 加 さ れ た 通 信 遅 延C(1,1)の コ ス トを 支 払 う。 も し 同 一 のPEに 割 当 て られ た 場 合 は,通 信 遅 延 は ゼ ロ と な る。 図1を 例 に す る と,タ スTa∼kNumbe「 Communlc日tlon ク4の 処 理 時 間 はw4=1を 支 払 い,タ ス ク4と そ の 親 タ ス ク の タ ス ク2が 互 い に 異 な るPEに 割 当 て ら れ た 場 合,エ ッ ジ に 付 加 さ れ た 通 信 遅 延C(4,2)=2の コ ス トを 支 払 う。 Computation Tlme 図1サ ン プ ル タ ス ク グ ラ フ 3.ス ケ ジ ュ ー リ ン グ ア ル ゴ リズ ム 3.1遂 次 最 適 化 解 法DF/IHS法 厳 密 解 を 求 め る た め の 実 用 的 な 最 適 化 ア ル ゴ リズ ム と し て は,DFAHS法 が 笠 原 ら に よ り提 案 さ れ て い る[7]。 DFAHS法 は,分 枝 限 定 法 に よ る 逐 次 最 適 化 ア ル ゴ リズ ム で あ る 。 図2は,図1の タ ス ク グ ラ フ で2PEに 割 り 当 て る ス ケ ジ ュ ー一一リ ン グ 問 題 を 実 際 にDMHS法 で 探 索 し た 場 合 の 探 索 空 間 で あ る 。RT(ReadyTask)は そ の 時 点 で ア イ ドル PEに 割 り 当 て 可 能 な タ ス ク の 集 合 を 表 す 。TS(Task Selection)は,RTか ら 実 際 に ア イ ドルPEに 割 当 て た タ ス ク の 集 合 を 示 す 。 こ ち ら は,RTか らCPIMISF(CPIMost ImmediateSuccessorsFirst)法[7]の ヒ ュ ー リス テ ィ ッ ク 的 に 優 先 順 位 の 高 い タ ス ク の 順 序 で 割 当 て る 。IdleTaskの 割 り 当 て は,PEを ア イ ドル 状 態 に す る こ と を 意 味 す る 。 DMHS法 は 図2の よ うな 探 索 空 間 を 左 端 か ら 右 端 に か け て 深 さ 優 先 探 索 を 行 う。 IdleTo8k RT(R?adyT量 憾 》 {1,2,3,01 Ta目kSdecnon_一 t4,の} {Eレ ￠}
薗
曲
蚤
一画
△
図2DF/IHS法 の 探 索 空 間 筆 者 は,こ の 手 法 に割 当てPEの 選 択 と通信 の 送 受信 の 組 合せ を加 える こ とで,通 信 遅延 を考 慮 して い る。 これ は組 合 せ 最 適 化 問題 の計 算複 雑 度 を増 や し,最 適 解 の発 見 を よ り困 難 に す る。 DMHS法 はCPMSF法 よ り,各 タス クか らエ ン ドノー一一 ドま で のCP長 を算 出 し,そ の値 を 下 限値 とす る こ とで枝 切 りが 効 率 的 に 行 わ れ る。 しか し,通 信 遅 延 の 有無 は, この 経 路 長 を 伸 ば して し ま う場 合 が あ る。 そ の た め, CPLMISF法 に よ っ て求 め られ た 下 限 値 で は,限 定操 作 に お い て過 小 評価 され て しま う可能 性 が あ る。 従 っ て,こ の 下 限値 の 精度 を 向 上 させ る こ とで枝 切 り効果 を 上 げ, 探 索効 率 の 向 上 が期 待 で き る。 4.下 限 値 4.1ス ケ ジ ュ ー リ ング 手法 に お ける 下 限 値 ス ケ ジ ュー リン グ手 法 にお け る下 限値 は,ス ケ ジ ュー リ ン グを行 う問題 対象 に とっ て 最低 限必 要 とな る メイ クス パ ンを 表す 。 これ は,問 題 に 対す る有 用 な メイ クス パ ン の 目安 と,同 時 に最 適 化 解 法 を行 う際 の最 適解 の 目安 に もな る。 本 研 究 室 で は,こ の 下限 値 にREDIC法[3]の 値 が 使 用 され て き た。 4.2REDIC法 REDIC法 は 下 記 の 条 件 下 で 算 出 す る 。 ● 直 接 後 続 タ ス ク の 通 信 遅 延 の み を 考 慮 ● 処 理PE数 は 無 制 限 更 に 、 計 算 を 行 う上 で 下 記 の 定 義 を 導 入 す る。 ●A:最 早 完 了 時 間 を 決 定 す る タ ス ク●PA:タ ス クAを 処 理 す るPE
●RA:タ ス クAを 処 理 し な いPE
●E:タ ス クAの 直 接 後 続 タ ス ク 群
●PA(E):PAに 割 り当 て られ た タスクAの 直 接 後 続 タス ク群
●RA(E):RAに 割 り当 て られ た タスクAの 直 接 後 続 タス ク
群
成 践 大 学 理 工 学 研 究 報 告 Vol50No.1(2013.6)
●ecA:タ ス クAの 最 早 完 了 時 間(earliestCompletion time)
●ctA]タ ス クAの 完 了 時 間(Completiontime)
eCAは,θ 。Aに1,VAを足 し合 わ せ た も の を 示 す 。 計 算 は エ ン ド ノ ー ドか ら ス タ ー トノ ー ドに 向 か っ て 計 算 を 行 う。 下 記 は 下 限 値 を 求 め る 当 該 タ ス ク で の 計 算 方 法 で あ る 。 こ の と き,エ ン ド ノ ー ドの θ。A,eCAは 共 に 自身 の 処 理 時 間 と す る。 ① 直 接 後 続 タ ス ク を 最 早 開 始 時 間 の 昇 順 でPAに 割 当 て る 。 max(cti),cti=e。i+△,PAL= i∈PA(E) △一{ct・ 一・許if(ct・ 一・>e・i)のSき ②PA(E)の 数 が1で あ れ ば 計 算 を 終 了 。そ うで な け れ ば, 最 早 完 了 時 間 に 通 信 遅 延 を 足 し合 わ せ た も の が 最 小 と な る タ ス ク を 取 り 出 し,P.Aに 最 早 完 了 時 間 の 昇 順 で 割 当 て る 。 max(eCi+C(A,i))P∼AL= i∈P∼A(E) ③PALとP.ALを 比 較 しP.ALの 方 が 大 き け れ ば 計 算 を 終 了 。 そ う で な け れ ば ① に 戻 る 。 最 終 的 に 計 算 終 了 時 のPALま た はP..ALの 大 き い 値 が タ ス クAの 最 早 開 始 時 間 を 示 し,1,VAを 足 し た 値 が 最 早 完 了 時 間 と 下 限 値 に な る。 既 にREDIC法 に よ る 下 限 値 の 有 効 性 は 証 明 さ れ て い る [3]。 し か し,こ の 下 限 値 はPE数 を 考 慮 し な い 環 塊 を 条 件 に タ ス ク の 処 理 時 間 と 互 い に 結 ば れ た エ ッ ジ の 通 信 遅 延 の み し か 考 慮 し て い な い 。 こ れ は,分 枝 限 定 法 に よ る 探 索 を 行 う際 に 任 意 の 問 題 に 対 し て 十 分 な 下 限 値 の 精 度 を 所 持 で き て い な い 。 従 っ て,別 の 要 素 を 追 加 す る こ と で こ の 下 限 値 の 精 度 向 上 を 目 指 し た 。 4.3プ ロ セ ッ サ 数 を 考 慮 した 下 限 値 PE数 を 考 慮 し た 下 限 値 は 現 在 ま で に い く つ か 考 案 さ れ て い る[4],[5],[6]。現 存 の 中 で 最 も 効 果 が 高 い と さ れ て い る の が,Fernandezら に よ る 下 限 値[6]で あ る 。 これ はPE 数 を 限 定 し な い 環 塊 で 各 タ ス ク の 活 動 範 囲 を 算 出 し,CP 長 内 の 各 イ ン タ ー バ ル に お け る タ ス ク の 重 み を 計 算 す る 。 そ こ か ら,PE数 が 限 定 さ れ た 環 境 に お い て イ ン タ ー一一バ ル 内 で 処 理 し き れ な い タ ス ク の 重 み を 算 出 す る も の で あ る 。 今 回 導 出 す る 下 限 値tLは 下 記 の 式 か ら 求 め られ る 。 亡L=亡REDκ+「q1 ・ 一 、購 一(・・ 一 ・・)+圭 Σm・ ・[ei(…e・)・li(e・ …)] i∈N mi・[・i(θ、,θ、),li(θ、,θ、)] =min[(eci一 θ1),W`,(θ2一 θ1),(θ2 -z 。i)] た だ し,こ こ でtREDIcはREDIC法 に よ り 計 算 され た 下 限 値 で あ る 。qはPE数 が 限 定 され た 環 境 に お い て イ ン タ ー一一バ ル 内 で 処 理 し き れ な い タ ス ク の 重 み で あ る。CP長 内
の 各 イ ン タ ー一一バ ル はel,θ2で 表 す 。 更 に,1。iは タ ス クi の 最 遅 開 始 時 間(lateststartt㎞e)を 表 す 。[6]が 提 供 し た 下 限 値 に は こ の 最 早 完 了 時 間,最 遅 開 始 時 間 の 各 々 に 通 信 遅 延 が 含 ま れ な い 。 従 っ て こ れ ら に 通 信 遅 延 を 算 入 し, 前 述 し た 式 を 適 用 す る こ と でPE数 を 考 慮 し た 下 限 値 を 生 成 し た 。 4.3.1通 信 遅 延 を 考 慮 した 最 早 完 了 時 間 ・最 遅 開 始 時 間 通 信 遅 延 を 考 慮 し た 最 早 完 了 時 間 と 最 遅 開 始 時 間 は REDIC法 か ら計 算 で き る 。 最 早 完 了 時 間 は,REDIC法 を ス タ ー ト ノ ー ドか ら エ ン ドノ ー ドに 掛 け る こ と で 求 ま る 。 最 遅 開 始 時 間 は,REDIC法 で 求 め られ た 各 タ ス ク の 下 限 値 を ス タ ー トノ ー ドの 下 限 値 か ら 引 い た 値 が 各 タ ス ク の 最 遅 開 始 時 間 と な る 。 下 記 に 式 を 示 す 。 lsiニRes-Rei こ こ で,Re。 は ス タ ー一一トノ ー ドの 下 限 値 をREDIC法 に よ
っ て 計 算 し た 値,Reiは タ ス クiの 下 限 値 をREDIc法 に よ
っ て 計 算 し た 値 とす る。 更 に,こ の 最 早 完 了 時 間 と 最 遅 開 始 時 間 は タ ス ク グ ラ フ か ら ス タ テ ィ ッ ク に 求 め ら れ る 値 と ス ケ ジ ュ ー リ ン グ 中 に 先 行 タ ス ク の ス ケ ジ ュ ー ル 状 況 か ら 求 め ら れ る 値 の 2つ が あ る 。 ス ケ ジ ュ ー リ ン グ 中 に 最 早 完 了 時 間 と 最 遅 開 始 時 間 を 更 新 し,そ こ か ら 前 述 し た 式 を 適 用 す る こ と で,算 出 され たqか ら よ り積 極 的 な 枝 切 りが 行 え る 。 し か し,前 述 し た 式 は 計 算 量0(V・Re。2)を 費 や す た め,ス ケ ジ ュ ー リ ン グ 中 に こ の 下 限 値 を 求 め る 場 合,こ の 計 算 量 が 常 に 必 要 と され る 。 こ こ でVは タ ス ク グ ラ フ の タ ス ク 数 とす る。 こ の 問 題 に 対 し て 下 記 の 式 を 使 用 す る。 タ ズク の迦 理 碍脅グの霧請称 並 列 度 para=[9]CP長 並 列度paraは 任 意 の タ ス ク グ ラ フ に対 してCP長 内 で処 理 を 終 え るた め の 必 要 なPE数 の 概 算 値 とな る。 この値 を閾 値 と し,並 列 度paraよ り も小 さい 値 を 割 当てPE数 とす る ス ケ ジ ュ ー リン グ 問題 で は 探 索 中 にPE数 を考 慮 した 下 限値 生成 を 行 う。 も しそ うで な け れ ば,探 索 中 にPE数 を 考 慮 した 下 限値 生成 を行 わ な い。
成 踵 大 学 理 工 学 研 究 報 告 Vol50No.1(2013.6) 4.3.2プ ロセ ッサ 数 を 考 慮 し た 下 限 値 の 評 価 PE数 を 考 慮 し た 下 限 値 を 用 い てREDIC法 に よ る 下 限 値 と の 比 較 評 価 を 行 う。 評 価 関 数 を 以 下 に 示 す 。 ● ス タ ー トノ ー ドの 下 限 値 と最 適 解 と の 近 似 率 評 価 を 行 う タ ス ク グ ラ フ の パ ラ メ ー一一タ は,タ ス ク 数:20, タ ス ク の 処 理 時 間:1∼30の 一 様 乱 数,通 信 遅 延 時 間:CCR=1,0,直 接 先 行 ・後 続 タ ス ク 数1∼3の 一 様 乱 数 と し た 。 こ こ でCCR(CommunicationtoComputationRatio)は グ ラ フ 上 の 通 信 遅 延 の 総 時 間 を タ ス ク の 総 処 理 時 間 で 除 算 し た 比 と な っ て い る 。 こ の パ ラ メ ー タ を 所 持 し た タ ス ク グ ラ フ を60題 用 意 し て 評 価 を 行 う。使 用 し た マ シ ン は, CPU:lntel(R)Xeon(R)[email protected]×2,0S:Linux, RAM:50GB,Compiler:gcc4.1,2で あ る 。 4.3.3評 価 結 果
REDIC法 とPE数 を 考 慮 し た 下 限 値 と で 評 価 を 行 う。PE
数 が 関 係 し て く る 評 価 に な る た め,60題 の タ ス ク グ グ ラ フ をPE数2-4に 割 り当 て る 各 々 の ス ケ ジ ュ ー一一リ ン グ 問 題 を 解 き,平 均 値 を 取 る 。 結 果 を 以 下 に 示 す 。
1蹴
驚 雛
語 ・
・%
0% < PE(2)PE(3)PE(4) NumberofProcessorElement 図3PE数 を考 慮 した下 限 値 生 成 の 評 価 図3は,最 適 解 に ど の 程 度 各 値 が 近 似 して い る か を 示 す 。 図 の 横 軸 はPE数 を 表 し,縦 軸 は 最 適 解 と の 近 似 率 を 表 し て い る 。Opt㎞alは 最 適 解 を 表 す た め,近 似 率 は 常 に 100%と な る。Considering#ofPEはPE数 を 考 慮 し た 下 限 値 と な っ て い る 。 最 も 顕 著 な 違 い を 示 し た の はPE数 を2台 と した 場 合 で あ る。REDICで は 最 適 解 と の 近 似 率 に 平 均 で77.35%,最 大 で95.70/。 と な っ た 。 対 し てPE数 を 考 慮 した 場 合 は,平 均 で94,8%,最 大 で98.1%と 非 常 に 最 適 解 に 近 い 下 限 値 を 生 成 す る こ と が で き た 。PE数 が3,4台 の 場 合 は ど ち ら の 下 限 値 も 顕 著 な 違 い は 見 ら れ な か っ た が,下 限 値 は 最 適 解 に ど れ だ け 近 似 で き る か で そ の 有 用 性,有 効 性 が 劇 的 に 異 な る た めREDICよ り も 近 似 し た 値 を 算 出 で き た だ け で も メ イ ク ス パ ン の 有 用 性,限 定 操 作 の 有 効 性 と 共 に 効 果 が あ る と 考 え ら れ る 。 4.4後 続 タ ス ク の 処 理 時 間 を考 慮 した 下 限 値 計 算 依 存 解 決 に お け る通 信 遅 延 の 値 が 多 大 で あ る場 合(図 4),最 適 な ス ケ ジ ュ ール は 通 信 の 発 生 を抑 え て,あ る程 度 のPEに タ ス ク を ま とめ た 形(図5)と な る場 合 が 多 い。 この場 合,最 適 解 とREDIC法 に よっ て 求 め られ た 下 限値 に 大 き な差 が 生 じて しま う。 これ は,REDIC法 の計 算 目 的 が通 信 遅 延 を 下 限値 に組 み 込 む と して い るた め で あ る。 も し,図5の 各 タス クを 逐 次 に 実行 す る よ うな ス ケ ジ ュ ー ル長 に 下 限値 を近 づ け る場 合 ,当 該 タス クか ら全 ての 後 続 タ ス クのPEに 対 す る割 当 て を 考 慮 して 求 め る必 要 が あ る。 しか し,全 て の 後続 タス クを 下 限値 計 算 の 要 素 に加 え る こ とは組 合 せ の 考慮 か ら探 索 を必 要 と し,後 々 の 最適 解 発 見 の こ と も考 える と,探 索 の探 索 とな っ て し ま う。 従 っ て,今 回 は後 続 タ ス ク が依 存解 決 に 通信 を必 要 と しな い,直 接 先 行 タ ス ク と同PEに 割 当 て られ る組 合 せ を 取 る場 合 に 後続 タス クの 処理 時 間 をREDIC法 の 計算 の 要 素 に入 れ る こ とで 下 限値 の 向 上 を 目指 した。 4 1,卜;tI-rec 1,印1 Pr頓 Sl;郵4E smd 1.1 1,,ll R.・ぐv 1:1, 孕 、i㌧ 阿 砧Tlmo 一 1幽 1脚 Prα s壁・員【露コ コ
R.T、 一 匪ヤ㏄陣
Send : R蝦 、一
,
伽 L14 =iTime 図4サ ンプル タスクグラフ 図5ス ケ ジ ュー ル例 4.4.1計 算 方 針 REDIC法 の 計 算 で は,各 タ ス ク の 下 限 値,最 早 開 始 時 間,最 早 完 了 時 間 は 図4を 例 に す る と 表1の よ うに な る。 表1各 タ ス ク のREDIC法 に よ る 値 ■画 ■ 巨杢==一 コ■ ■盟 ■■ ■■■■=團■■■ S888 ■404 22■2 34■4 4■0■ EOOO 表1よ りス タ ー トノー ド以 外 の タ ス クは エ ン ドノー ド ま で の 経 路 長 に 通信 遅延 は入 れ られ な い た め,各 値 は1E しい もの とな っ て い る。 従 っ て,ス タ ー トノー ドの 下 限 値 を 向 上 させ る こ とで 図4の 逐 次 実行 に よ る最 適 解9に 下 限値 を合 わせ る必 要 が あ る。 ス タ ー トノー ドの 下 限値 をREDIC法 に よっ て 計算 す る 場 合,計 算 に加 わ る要 素 は タス ク1,タ ス ク2,タ ス ク3 の み とな る。 こ こに タ ス ク4を 加 え て 計 算 して もREDIC 法 の ア ル ゴ リズ ム で は 下 限値 と して値 を算 出す る こ とが で き な い。 この 問題 に対 して 直接 後続 タ ス クの 下 限値, 最 早 開 始 時 間,最 早 完 了 時 間 を 再 帰 的 に 更 新 しな が ら値 を 求 め る方 法 を 提案 す る。成 践 大 学 理 工 学 研 究 報 告 Vol50No.1(2013.6) 4.4.2ダ ミー エ ッ ジ の 挿 入 本 来,ス タ ー一一トノ ー一一ドの 下 限 値 を 最 適 解9と 算 出 で き な い 理 由 は,タ ス ク2,タ ス ク3をREDIC法 で 計 算 す る 際 に タ ス ク1の 要 素 を 取 り込 め な い た め で あ る 。 図6に 例 を 示 す 。 図6は エ ン ドノ ー ドか ら ス タ ー一一トノ ー一一ドに 向 け て 時 刻8の 間 に 各 タ ス ク が 最 早 開 始 時 間 で 存 在 す る 図 を 表 し て い る。 図6よ り,タ ス ク2,タ ス ク3,タ ス ク4 は 実 際 にPEに 割 当 て を 行 う と タ ス ク1の 存 在 か ら 表1の 最 早 開 始 時 間 か ら 実 行 す る こ と は で き な い 。 仮 に タ ス ク 2,タ ス ク3,タ ス ク4を 先 に 割 当 て て も タ ス ク1が 表1 の 最 早 開 始 時 間 か ら 実 行 す る こ と は で き な い 。タ ス ク1, 4の 間 で ど ち ら を 先 に 実 行 し た 方 が い い の か は こ の 時 点 で は 決 定 す る こ と が で き な い 。 し か し,タ ス ク1,2,3, の 間 で 考 え た 場 合,タ ス ク1は タ ス ク2,3よ り も 最 早 開 始 時 間 が 早 い た め,タ ス ク1を 先 に 実 行 す れ ば ス タ ー ト ノ ー ドの 最 早 開 始 時 間 が 冗 長 に 延 び る こ と は な い 。 従 っ て,タ ス ク2,タ ス ク3の 下 限 値 計 算 を す る の に タ ス ク1 の 要 素 を 取 り込 ん で お け ば,結 果 と し て ス タ ー トノ ー ド は 全 て の 後 続 タ ス ク の 処 理 時 間 を 考 慮 で き る 。 1
固
EI1
.II [コi円
甲
1.i ,124 8Tim 図6表1の 最 早 開 始 時 間 の 各 タ ス ク の 存在 図 タス ク2,タ ス ク3の 下 限 値 計 算 に タス ク1の 要 素 を 取 り込 む に は疑 似 的 な 依 存 情 報(ダ ミー エ ッジ)を 持 た せ る こ とで解 決 で き る。図5に 例 を 示す 。 図5で は タス ク 2の 直 接 後 続 タス クに 疑 似 的 に タ ス ク1を 加 えて, タ ス ク2の 下 限 値 を REDIC法 で 計 算 す る こ と で,タ ス ク1の 処 理 時 間 を計 算 の 要 素 に 加 え る こ とが 出 来 る。 更 に,ダ ミ ー エ ッジ の 通信 遅延 時 間 を無 限 大 とす れ ば,通 信 DummyEdge 〈40> 図7ダ ミ ー エ ッ ジ の 挿 入 遅 延 を 下 限 値 の 経 路 長 に 含 む こ と も な い 。 タ ス ク2の 下 限 値 をREDIC法 で 再 計 算 す る と 下 限 値 は6,最 早 開 始 時 間 は5,最 早 完 了 時 間 は6と な る 。 こ の と き,ス タ ー一一ト ノ ー ドの 下 限 値 を よ り正 確 に す る た め に タ ス ク2と タ ス ク1に 依 存 関 係 を 持 た せ て い る。 本 来 こ の タ ス ク2か ら エ ン ド ノ ー ドま で の 経 路 に タ ス ク1は 存 在 し な い た め, ス ケ ジ ュ ー リ ン グ を 行 う際 の タ ス ク2の 下 限 値 は 表1の 値2が 正 し い 。 4.4.3後 続 タス クの 処理 時 間 を考慮 す る アル ゴ リズム ダ ミー エ ッジ を設 け る こ とで,後 続 タ ス クの 処理 時 間 を 下 限値 計 算 に組 み 込 む アル ゴ リズ ム を 下 記 に 示す 。 ①Pへ に割 り当 て られ た タ ス ク の 中 で 、当該 タ ス ク よ り も 先 に 同PEに 割 り当 て られ た タ ス ク と先行 依 存 の 有 無 を判 定 す る。有 れ ば 、次 の タ ス ク の判 定 に移 る。全 て の タス ク判 別 を終 えれ ば終 了 。 ② 先 行 依 存 が な けれ ば ダ ミー エ ッ ジ を設 け 、エ ッ ジの 通 信 遅 延 時 間 を・・に設 定 す る。 ③ ダ ミー エ ッ ジ を設 け た 状 態 で 当 該 タ ス クの 下 限値 を 再 度REDIC法 に よ って 再 計 算 す る。 ④ ③ の 再 計 算 に よ り当該 タス クの 最 早 開始 時 間 、 最 早 完 了 時 間 を更 新 し① に戻 る。 上記 の ア ル ゴ リズ ム を 用 い て,実 際 に 図4の グ ラ フか ら下 限値 を 求 め る。 まずREDIC法 の計 算 ア ル ゴ リズ ム か ら当 該 タ ス ク と直 接 後 続 タ ス ク は 同PEに 割 当 て られ る組 合 せ を 下 限 値 と して持 つ。 この グラ フの 場合,上 記 の アル ゴ リズ ム が適 用 され るの は ス ター トノー ドの 下 限値 を 計 算す る とき で あ る。 ス タ ー一一トノー一一ドの 下 限値 はREDIC法 の ア ル ゴ リズ ム か ら図8の ス ケ ジ ュー一一ル を 持 っ。 Proc Send Recv o 1 1 11
2 3 S 1 1 : : 巳 : 3 … : 3 … 0 4 5 8 Tim 図8REDICに よ る ス タ ー トノ ー ドの 組 合 せ 図8の 場 合,タ ス ク2を 当 該 タ ス ク と し た 場 合,当 該 タ ス ク よ り も先 に 同PEに 割 当 て られ て い る タ ス ク1と 依 存 関 係 を 所 持 し て い な い の で こ こ に 図5と 同 様 の ダ ミ ー エ ッ ジ を 設 け る 。 ダ ミ ー一一エ ッ ジ を 設 け た 状 態 で タ ス ク2 の 下 限 値 を 再 計 算 す る。 再 計 算 し た 結 果 を 用 い る と ス ケ ジ ュ ー一一ル は 図9と な る。 1 1 1 1 Proc Send Recvコ
1
21
3lsI
: : o : : 1 : : 1 : : 1 04 5 6 gTime 図9タ ス ク2の 下 限 値 を再 計 算 した結 果 図9か ら ス タ ー ト ノ ー ドの 下 限 値9を 得 る こ と が 出 来 る 。 勿 論 ア ル ゴ リ ズ ム の 流 れ に 従 え ば,次 に タ ス ク3 と タ ス ク2の 間 に 依 存 関 係 が あ る か を 判 別 す る。 こ の 場成 踵 大 学 理 工 学 研 究 報 告 Vol50No.1(2013.6) 合 ダ ミ ー一一エ ッ ジ を 設 け る 条 件 に 入 る の で タ ス ク2,タ ス ク3の 間 に ダ ミ ー一一エ ッ ジ を 設 け タ ス ク3の 下 限 値 を 再 計 算 す る 。 結 果 と し て は,図9と 同 じ ス ケ ジ ュ ー一一ル を 得 ら れ る。 こ の ア ル ゴ リズ ム は 直 接 後 続 タ ス ク の 下 限 値 を 再 計 算 し て い く 流 れ と な る 。 従 っ て,当 該 タ ス ク か らエ ン ド ノ ー ドま で の 後 続 タ ス ク 全 て の 下 限 値 を 再 計 算 す る こ と が 最 も性 能 を 良 く す る が,計 算 量 が 増 え る た め,ト レー ド オ フ と な る 。 4.4.4後 続 タ ス ク の 処 理 時 間 を 考 慮 した 下 限 値 の 評 価 後 続 タ ス ク の 処 理 時 間 の 考 慮 に よ る 下 限 値 を 用 い て REDIC法 に よ る 下 限 値 と の 性 能 差 を 示 す 。 評 価 関 数 は 以 下 と す る 。 ● ス タ ー トノ ー ドの 下 限 値 と最 適 解 と の 近 似 率 評 価 を 行 う タ ス ク グ ラ フ の パ ラ メ ー タ は,タ ス ク 数: 10,タ ス ク 処 理 時 間:1∼20の 一 様 乱 数,直 接 先 行 ・後 続 タ ス ク 数:1∼3の 一 様 乱 数 と した 。 こ の パ ラ メ ー一一タ を 所 持 し た タ ス ク グ ラ フ を60題 用 意 した 。実 験 環 境 は4.3.2 項 と 同 様 で あ る 。 4.4.5評 価 結 果 後 続 タ ス ク の 処 理 時 間 の 考 慮 に よ る 下 限 値 とREDIC法 に よ っ て 求 め ら れ た 下 限 値 と で 最 適 解 と の 近 似 率 を,タ ス ク グ ラ フ60題 か ら 平 均 値 を 読 み 取 っ て 評 価 し た 。こ の 評 価 は 通 信 遅 延 時 間 の 変 動 に よ り,ど の 程 度 下 限 値 が 最 適 解 に 近 似 す る か が 重 要 に な る 。従 っ て,CCR=1.0,2.0, 3.0,5.0,10,0と 値 を 変 え て 評 価 を 行 っ た 。 結 果 を 図10 に 示 す 。 図10は,横 軸 をCCR値,縦 軸 を 最 適 解 と の 近 似 率 と し て い る。 更 に,後 続 タ ス ク の 処 理 時 間 を 考 慮 し た ア ル ゴ リズ ム は 下 限 値 を 決 定 す る 当 該 タ ス ク か ら エ ッ ジ 何 本 先 ま で の 後 続 タ ス ク を 考 慮 す る か で 性 能 に 変 化 が で る た め,当 該 タ ス ク か ら エ ッ ジ2本 目ま で の 後 続 タ ス ク を 考 慮 し た 場 合 をPath2,当 該 タ ス ク か ら エ ッ ジ3本 目 ま で の 後 続 タ ス ク を 考 慮 し た 場 合 をPath3,同 様 の 意 で Path4,Path5,Path6ま で を 評 価 し た 。 従 っ て,Pathlは REDIC法 に よ る 計 算 と 等 価 に な る 。 ■Optlmal■Path6■Path5■Path4■Path3■Path2REDIC -100% 8 .日80% 860% oqH40%
身茎2:鞠
CCR=20CCR=30CCR=50 CCRValue 図10後 続 タス クの処 理 時間 を考 慮 した下 限値 生成 の評 価 図10で は,最 適 解 に ど の 程 度 各 下 限 値 が 近 似 し て い る の か を 示 す 。 そ の た め,最 適 解 と な るOptimalは 近 似 率 100%を 示 す 。 タ ス ク グ ラ フ の 通 信 遅 延 時 間 をCCR=1,0と し た 場 合, REDICと 最 適 解 の 近 似 率 は90.97%,後 続 タ ス ク の 処 理 時 間 を 考 慮 し た 場 合,Path2∼6全 て 同 値 と な る91.28%と な っ た 。 これ は,通 信 遅 延 時 間 が 各 タ ス ク の 処 理 時 間 と 比 べ る と 全 体 的 に 低 く 設 定 され て い る た め ,各 タ ス ク はPE に 並 列 に 割 当 て られ,通 信 遅 延 を あ る 程 度 許 可 し た ス ケ ジ ュ ー ル が 最 適 解 と な っ て い る た め だ と考 え ら れ る 。 CCR=2.0,3.0で も各 下 限 値 に 顕 著 な 違 い は 見 ら れ な か っ た 。CCR=2.0と し た 場 合,REDICに よ る 最 適 解 と の 近 似 率 は81.00%,後 続 タ ス ク の 処 理 時 間 を 考 慮 した 場 合 は, 最 大 でPath3∼6が82.64%を 示 し た 。CCR=3,0で は,REDIC に よ る 最 適 解 と の 近 似 率 は76.31%,後 続 タ ス ク の 処 理 時 間 を 考 慮 し た 場 合 は,最 大 でPath4∼6が79.65%を 示 し た 。 CCR=5.0,10.0と した 場 合 は 各 下 限 に 変 化 が 見 られ た 。 CCR=5.0で は,REDICに よ る 最 適 解 と の 近 似 率 は70.31%, 後 続 タ ス ク の 処 理 時 間 を 考 慮 し た 場 合,Path2で は,74,40%,Path3で は,76,81%,Path4で は,77.410/o,Path5
で は,77.67%,Path6で は,77,82%と な っ た 。CCR=10.0
で は,REDICに よ る 最 適 解 と の 近 似 率 は65.61%,後 続 タ
ス ク の 処 理 時 間 を 考 慮 し た 場 合,Path2で は,71.62%,
Path3で は,77.19%,Path4で は,80.33%,Path5で は,
8255%,Path6で は,83,08%と な っ た 。 最 も顕 著 な 違 い が 見 ら れ たCCR=10.0で は,通 信 遅 延 時 間 が 各 タ ス ク の 処 理 時 間 よ り も 全 体 的 に 非 常 に 高 く な る た め,最 適 解 が 図5の 逐 次 実 行 に 近 い 割 当 て ス ケ ジ ュ ー一一ル と な っ て い る た め と 考 え られ る。 CCR値 の 上 昇 に つ れ て 下 限 値 と 最 適 解 と の 差 は 大 き く 開 い て し ま う。 特 に,REDICと 最 適 解 と で はCCR=10.0 で 比 較 し た 場 合,34%も の 差 が 出 て し ま う。 こ の 問 題 に 対 し て,後 続 タ ス ク の 処 理 時 間 を 考 慮 す れ ば,最 適 解 と の 差 を17%ま で 縮 め る こ と に 成 功 し た 。 CCR=1.0の 場 合,通 信 遅 延 時 間 が 全 体 的 に 低 く 設 定 さ れ て い る為,後 続 タ ス ク を 当 該 タ ス ク と 同PEで 処 理 せ ず 別PEに 並 列 に 処 理 す る ス ケ ジ ュ ー一一ル が 最 適 解 と 成 り易 い た め 両 下 限 値 に 大 き な 違 い は 見 られ な か っ た 。しか し, 60個 の タ ス ク グ ラ フ の 内,6個 の タ ス ク グ ラ フ が,Path2 と し た 場 合 で も 後 続 タ ス ク の 処 理 時 間 を 考 慮 し た 方 が 下 限 値 の 向 上 を 図 れ た 。 改 善 さ れ た 下 限 値 はREDICと 比 較 し た 場 合,最 大 で5.360/。,平 均 で3.ll%向 上 し て い る。 従 っ て,通 信 遅 延 時 間 が 低 い 問 題 で も 効 果 が あ る と 考 え ら れ る 。
成 蹟 大 学 理 工 学 研 究 報 告 Vol50No.1(2013.6) 4.5探 索 中 の 下 限 値 更 新 通信 遅延 を 考 慮 したCP長 を生 成 す る場 合,PE数 を限 定 しな い 環 境 で,全 て の 通 信 の 発 生 を 考 慮 しな けれ ば な ら な い。 これ は,そ れ 自身 が 組 合 せ 最 適 化 問 題 とな って し ま い,有 効 時 間 内 で求 め る こ とは不 可能 で あ る。しか し, 現 在 の 通 信 遅 延 を考 慮 し た 下 限 値 を よ り正 確 なCP長 に 近 づ け る場 合,通 信 の発 生 を考 慮 した探 索 が必 要 とな る。 従 っ て,探 索 中 にRTか らそ の 直 接 後 続 タス ク を処 理 す る の に 最 低 限 必 要 な 通 信 遅 延 を発 見 し,そ れ をRTの 下 限 値 に 組 み 込 む 。 この 場 合,REDIC法 と同 じ,直 接 後 続 タス クの 通 信 遅 延 の み とな っ て しま うた め,あ ま り改 善 が 見 込 め る とは 思 えな い 。 しか し,REDIC法 で 発 見 で き る通 信 遅延 は 図llの よ うなfork型 のtree構造 の 場 合 で あ り, 図12の よ うなjoin型のtree構造 で 必 要 な 通 信 遅 延 は 発 見 す る こ とが で きな い 。 更 に,探 索 中 に 下 限 値 を更 新 す る こ とは そ の 時 点 の ス ケ ジ ュー ル か らエ ン ドノー ドまで の よ り1E確 な 最 低 限 必 要 と され る経 路 長 を発 見 す る こ とが で き,こ れ を タス クの プ ライ オ リテ ィ と して 用 い れ ば, 経 路 長 の 長 い タス ク か ら優 先 的 にPEへ 割 当 て る こ と を 可 能 に す る。 これ は 暫 定 解 が 更 新 され る確 率 の 高 い 分 枝 操 作 が 行 え る。 従 っ て,RTの 下 限 値 を更 新 す る こ とを 試 み る。 図11forktree 図12jointree 4.5.1探 索 中 の下 限値 更新 アル ゴ リズム 下 限値 更 新 はDMHSのRT内 の タ ス ク に 対 し て行 わ れ る。RTの 更 新 後,RTの 直 接 後 続 タス クを 実 行 す る際 に 最 低 限 必 要 な 通信 遅延 を 取 り込 む こ とで 下 限 値 更 新 を行 う。 下 記 に ア ル ゴ リズ ム を 示 す 。 ①RT内 の 各 タス クの 最 早 開始 時 間 を決 定 す る。 この 値 は全 て のPEに 割 り当 て る組 合 せ を 考 慮 す る こ とで 算 出す る。 ②RT内 の 各 タ ス ク の 直接 後 続 タ ス ク の最 早 開始 時 間 を求 め る。こ の値 は各 直 接 後 続 タ ス ク をREDIC法 に 掛 け る こ とで算 出す る。 ③ 発 生 した通 信 遅 延 を組 込 む こ とで 下 限値 を更 新 す る。 この ア ル ゴ リズ ム で 図13を 用 い て 下 限値 更 新 を行 う。 ま ず 全 て のRTの 最 早 開 始 時 間 と最 早 完 了 時 間 を 算 出 す る。 こち らは,REDIC 法 に よ る算 出 で は な く,現 在 ま で の ス ケ ジ ュー ル を反 映 させ るた め,全 て のPEに 図13部 分 タ ス ク グ ラ フ 割 当 て た場 合 に,実 際 に 最 早 開始 時 間 ・最 早完 了 時 間 は どの タ イ ミン グか を決 定す る。 図13の グ ラ フ を例 にす る と タス ク3,タ ス ク4の 最 早 開始 時 間 ・最 早完 了 時 間 は 図14の よ うに な る。 PE(0)Send Pl・1(1)
口
Time 図14部 分 ス ケ ジ ュ ー リ ン グ 図14よ り,タ ス ク3の 最 早 開 始 時 間 は 時 刻5,タ ス ク 4は 時 刻3と な る。 こ こ か らRTの 直 接 後 続 タ ス ク の 最 早 開 始 時 間 ・最 早 完 了 時 間 を 求 め る 。 こ れ に はREDIC法 に よ る計 算 か ら 求 め る 。 こ れ は,当 該 タ ス ク(図13で は タ ス ク5)に と っ て 最 も 早 く 処 理 を 開 始 す る た め に 必 要 な 通 信 遅 延 を 算 出 す る。図14の タ ス ク4か ら タ ス ク5に 発 生 す る通 信 遅 延 が タ ス ク5を 最 も 早 く 処 理 を 開 始 す る た め に 必 要 な 通 信 遅 延 と な る 。 こ こ か ら 下 記 の 評 価 を 行 い, タ ス ク4の 現 在 の 下 限 値 よ り 右 辺 の 方 が 大 き け れ ば,タ ス ク4の 下 限 値 を 更 新 す る。 Re4<w4十C(5,4)十Re5 仮 に タ ス ク5を 実 際 の 割 当 て でPE(1)に 割 当 て,タ ス ク 4か ら タ ス ク5の 通 信 遅 延 が 発 生 し な く と も,そ の 割 り 当 て 方 は タ ス ク5に と っ て 最 も 早 く 処 理 を 開 始 で き る タ イ ミ ン グ で は な い 。 従 っ て,タ ス ク5を 経 由 し エ ン ド ノ ー ドに 至 る パ ス 長 は 伸 び て し ま うた め,最 低 限 必 要 な パ ス と は な ら な い 。 こ こ で,タ ス ク3,タ ス ク4の 割 当 て 方 が 各 々 最 早 開 始 時 間 ・最 早 完 了 時 間 で な い 場 合 を 考 え る 。 ま ず 図15 を 例 に と る 。 PE(0》S鯉nd PE(1) ■9■ lI .1● ●, oo● ,, Pr⊂ ⊃cコi
4 5 S{⊇nd ■-001 ■ 「 31 1, r一 一 一'∼`㌔,昌 一 001 31 Recv一
〇9,
H Proc=Σコi国
:, ooI 腫 ■ S吐 ・nd F-一 一一一一一r-一 一一一一 や● 、γ{一
09, ■9, `1(r,.:1) Recv一
1, Ol3 ,, o■ 013s19Time 図15部 分 ス ケ ジ ュ ー リ ン グ 図15よ りRTで あ る タ ス ク3,タ ス ク4が 最 早 開 始 時成 践 大 学 理 工 学 研 究 報 告 Vol50No.1(2013.6) 間 ・最 早 完 了 時 間 に 割 当 て を受 けて い な けれ ば,少 な く と も タス ク5は 図14の 時 刻 よ りも早 く処 理 を開 始 で き る こ とは な い 。 この 下 限 値 更 新 は 先行 タス クの ス ケ ジ ュー ル に 依 存 す るた め,先 行 タス クの 割 当て 方 が 変 更 され る毎 に 必 要 と され る通信 遅延 が 変 更 され る。 従 っ て そ の 都 度 下 限 値 を 更 新 す る必 要 が あ る。 4.5.2探 索 中 の下 限値 更新 の評 価 探 索 時 の 下 限 値 更 新 を行 うス ケ ジ ュー ラ と下 限 値 更 新 を行 わ な い ス ケ ジ ュー ラ とで 性 能 差 を示 す 。 評 価 関 数 は 以 下 とす る。 ● 最 適 解 発 見 ま で の探 索 時 間 削減 率 評価 を行 うタ ス ク グ ラ フのパ ラメ ー一一タ は,タ ス ク数:20, タ ス ク 処 理 時 間:1∼20の 一 様 乱 数,通 信 遅 延 時 間:CCR=1.0,直 接 先 行 ・後 続 タス ク数:1∼3の 一様 乱 数 と した。 このパ ラ メー一一タ を所 持 した タ ス ク グ ラ フを40題 用 意 した。この タ ス ク グラ フ を4PEに 割 当 て るス ケ ジ ュー リン グ 問題 を解 い た。 実 験環 境 は43.2項 と同様 で あ る。 探 索 時 の 下 限値 更 新 はRTが 更 新 され る毎 に行 われ る。 従 っ て,下 限 値 更 新 を行 っ て 枝 切 りが 行 わ れ な い 限 り, 下 限 値 更 新 の 計 算 自体 が 無 駄 な 計 算 時 間 とな り,探 索 時 間 を延 ば して しま う場 合 が あ る。 この 問 題 に 対 して,評 価 用 ス ケ ジ ュー ラの 限 定 操 作 の 評 価 手 順 を利 用 す る こ と で 無駄 な 計 算 を減 らす 工 夫 を行 う。 評 価 用 ス ケ ジ ュー ラ はRTが 更 新 され る毎 に 枝 切 りを行 うか 評 価 す るが,ま ず 未 割 当 て タス クの 下 限値 を使 用 した枝 切 り,未 割 当て タ ス ク の 処 理 時 間 の 総 数 をPE数 で 除 算 した 値 に よ る枝 切 りの 評 価 を行 う。 この 評 価 は 非 常 に 少 な い 計 算 量 で 行 え るた め,こ の 時 点 で 枝 切 り可 能 な 場 合 は 下 限 値 更 新 を 行 わ な い 。 も し この2つ の 評 価 で 枝 切 りが 行 えな い 場 合, 次 にREDIC法 を使 用 す る こ とで未 割 当 て タス クの 最 早 開 始 時 間 を 算 出 し,そ の 値 か ら再 度 枝 切 りの 評 価 を 行 う。 下 限 値 更 新 は この未 割 当 て タス クの 最 早 開 始 時 間 を求 め る計 算 と同 時 に 行 う。こ の場 合,RTの み全 て のPEに 割 当 て た 場 合 の 組 合 せ を考 慮 す る こ とで 最 早 開 始 時 間 を求 め RT以 外 の 未 割 当 て タ ス ク は 全 てREDIC法 の計 算 か ら最 早 開 始 時 間 を 求 め る。従 っ て,4.5.1.項 で 示 した 下 限 値 更 新 ア ル ゴ リズ ム の ① の み と下 限 値 を 更 新 す るか 否 か の 評 価 式 を評価 用 ス ケ ジ ュー ラに 加 え るだ け で 良 く,非 常 に 少 な い 計 算 量 で 下 限 値 更 新 を行 うこ とが 出来 る。 4.5.3評 価 結 果 探 索 時 の 下 限 値 更 新 を 行 うス ケ ジ ュ ー ラ と 下 限 値 更 新 を し な い ス ケ ジ ュ ー ラ と で 評 価 を 行 っ た 。 ど ち ら の ス ケ ジ ュー一一ラ も元 の 下 限値 の値 はREDIC法 に よっ て 求 め られ た値 とな っ て い る。 この評 価 で は,下 限値 更新 を行 うこ とで最 適解 発 見 ま で の探 索 時 間 が どの 程度 削減 され るの か を評 価 した。 縦軸 を探 索 時 間 削 減 率,横 軸 を タ ス クグ ラ フ番 号 と して い る。 結 果 を 図16に 示 す 。 暫日 自 泪 旧据 国 目 ℃ の TaskGraphNumber 図16探 索時 の 下限値 更 新 にお け る探 索時 間削 減率 の 評価 図16の 結 果 よ り,平 均 で21,85%,最 大 で94,68%の 探 索 時 間 を 削 減す る こ とに 成功 した。 問題 ご とに 削減 率 に 差 が あ るの は タ ス ク グラ フの構 造 に よ りREDICの 精 度 に 差 が 出 て しま うこ とや 下 限値 更新 が あ ま り行 わ れ な か っ た た め だ と考 え られ る。 この 下 限値 更新 は 通信 遅延 の み しか 下 限値 に組 み込 め な い た め,通 信 を発 生 させ ず 各 タ ス ク を 特 定 のPEで 逐 次 に 実 行 す る よ うな ス ケ ジ ュー ル を とる 場合,下 限値 更新 は あ ま り行 わ れ な い。 更 に,図 12のjoin-tree型 が 少 な い タス ク グ ラ フ で も同様 にREDIC よ り も優 れ た 下 限値 を発 見す る こ とは難 しい。 しか し, 今 回評 価 した全 て の タス クグ ラフ で探 索 時 間 を 削減 す る こ とが で き た。 これ は,少 な か らず どの タ ス ク グラ フで も下 限値 を 更新 す る こ とで,新 た に枝 切 りを行 えた こ と と,下 限値 更新 自体 の計 算 を 非 常 に少 な い 時 間 で行 うこ とが 出 来 た た め だ と考 え られ る。 従 っ て,下 限値 更 新 を 行 うこ とで ス ケ ジ ュ ー リ ング 効 率 を 向 上 させ る こ とが で き た と考 え られ る。 5.通 信 遅 延 を考 慮 した 最 適 化 ス ケ ジ ュー ラ の 構 築 前 章 ま で の 下 限値 生成 を最 適 化 ス ケ ジ ュ ー ラ に組 込 む。 下 限値 生成 は,探 索 を行 う前 処理 の 工 程 と探 索 時 の 工程 の2つ に分 け て 行 う。 ま ず 前 処理 の 工 程 で は,REDIC法 に加 え てPE数 を考 慮 した 下 限 値 生 成,後 続 タ ス クの 処 理 時 間 を 考慮 した 下 限値 生 成 を行 う。 探 索 時 の 工 程 で は, 探 索 時 の 下 限 値 更 新 と並 列 度paraを 用 い たPE数 を 考 慮 し た 下 限値 生 成 を行 う。 これ は,昨 年 度 ま で はREDIC法 に よ る探 索 前 の ス タテ ィ ッ クな 下 限値 生成 の み で あ っ た の に 対 し,新 た に 改 良 され た 下 限値 生成 を用 いれ ば,常 に 探 索 時 の 下 限値 更新 とい うダ イ ナ ミ ッ クな 下 限値 生 成 要 素 も加 え られ る。 更 に,下 限値 更 新 で使 用 され る元 の 下
成 蹟 大 学 理 工 学 研 究 報 告 Vol50No.1(2013.6) 限 値 はREDIC法 に 加 え,PE数 と 後 続 タ ス ク の 処 理 時 間 も 考 慮 さ れ た 値 と な る た め,REDIC以 上 の 値 が 使 用 され る 。 6.実 験 本 章 で は,前 述 した3つ の ア ル ゴ リズ ム を追 加 した ス ケ ジ ュー ラ と昨 年 度 ま で の ス ケ ジ ュー ラ とで 評 価 を行 う。 評 価 関 数 を次 に 示 す 。 ① 最 適 解 発 見 ま で の探 索時 間削 減 率 の評 価 ② 指 定 実 行 時 間 内 の 探 索 で の 初 期 解 か ら の暫 定 解 向 上 率 ① で は,最 適 解 を発 見 す るま で に 費 や した 探 索 時 間 が どの 程 度 削 減 す る こ とが で き るか を 評 価 す る。 この 評 価 を行 うタス ク グ ラ フの パ ラメ ー タは,タ ス ク数:20,タ ス ク処 理 時 間:1∼30,直 接 先行 ・後 続 タ ス ク数:1∼3 と した 。 この タス ク グ ラ フか ら2,3,4PEに 割 当て るス ケ ジ ュー リン グ問題 を20個 解 き評 価 を行 う。 ② は,大 規模 問題 を 指 定 実 行 時 間 内 で 探 索 を行 うこ と で 初 期 解 か ら暫 定解 が どの 程 度 良 くな るの か を評 価 す る。 この 評 価 を行 うタス ク グ ラ フパ ラメ ー タは,早 稲 田大 学 笠 原研 究 室 の標 準 タス クセ ッ ト[8]のタ ス ク数50と し, CCR=1.0と 設 定 した。 この パ ラ メー一一タ を所 持 した タス ク グ ラ フを30題 用 意 し,3PEに 割 当て るス ケ ジ ュー一一リン グ 問 題 を解 く。 指 定 実 行 時 間 内 で の 探 索 で は,下 限 値 を 使 用 した 枝 切 りの 精 度 を 上 げ る以 外 に 分 枝 操 作 で 使 用 す る 各 タス クの 割 当 て優 先 度 も重 要 とな る。 これ は探 索 枝 の 順 序 に 変化 を 与 え,探 索PEが 指 定 実 行 時 間 内 に解 け る子 問 題 に どれ だ け優 良 解 を集 め られ るか に 繋 が る。従 っ て, この 評 価 で は 新 しい 下 限 値 生 成 を追加 した ス ケ ジ ュー ラ に この 下 限 値 を各 タス クの 割 当 て 優 先 度 に用 い る。 使 用 した マ シ ンは4.3.2項 と同様 とな っ て い る。この 環 境 よ り12コ ア に よる並 列 探 索 を行 う。 7.評 価 7.1最 適 解 発 見 ま で の 探 索 時 間 削 減 率 の 評 価 昨 年 度 ま で の ス ケ ジ ュー ラ と今 回 新 しい 下 限 値 生 成 を 追 加 した ス ケ ジ ュー ラ とで 探 索 時 間 削 減 率 の 評 価 を行 っ た 。 縦 軸 に探 索 時 間 削 減 率,横 軸 を 割 当 てPE数 と した。 20個 の タ ス ク グ ラ フ にPE数2,3,4と した ス ケ ジ ュー一一リ ン グ問 題 を解 き,各 々 の 結 果 を 示 す 。 一自 酋 幽 旧憾 国 暮 ℃ の 9000% 8000% 7000% 6000% 5000% 4000% 3000% 2000% 1000% 00% -1000% -2000% -3000% 図17割 当 てPE数 を2と した 問題 の最 適 解 発 見 ま で の探 索 時 間 図17は 割 当 てPE数2と した場 合 の 評価 結果 で あ る。 平 均 で10.70%,最 大 で83.270/。の 探 索 時 間 を 削 減す る こ とが で きた。 探 索 時 間 が延 び て しま っ た 問題 は,探 索 中 にPE数 を考 慮 した 下 限 値 生 成 を行 っ たが,そ れ が枝 切 り に 繋 が らな か っ た た め だ と考 え られ る。PE数 を 考 慮 した 下 限 値 生 成 を探 索 時 に 行 う場 合,RTが 更 新 され る 毎 に 0(V・Re。2)の 計 算 量 が費 や され て しま う。 この 計 算 時 間 を 払 っ た 上 で枝 切 りへ と繋 が れ ば 探 索 時 間 を 削 減 で きる 可 能性 が 高 ま る が,も しで き な け れ ば 無駄 な計 算 時 間 と な り,探 索 時 間 を 単 純 に延 ば して しま う。 しか し,こ こ で 最 も高 い 探 索 時 間 削減 率 を算 出 した タ ス ク グ ラ フ20 番 を例 に 取 り,探 索 時 にPE数 を 考 慮 した 下 限値 生成 を行 うか行 わ な い か で 実 験 を して み る。 こ の実 験 で は単 一PE で 探 索 を行 う。 結果 を表2に 示す 。 表2で は,SearchT㎞eは 実 際 の 探 索 時 間,BranchNum は 探 索 した 探 索枝 の数 とな っ て い る。 この 結果 か ら探 索 時 にPE数 を 考 慮 す る こ とで 劇 的 な ス ケ ジ ュー一一リン グ効 率 の 向 上 を確 認 で き る。 表2探 索時 のPE数 を考 慮 した下 限値 生成 に よ る性能 評価 ア ル ゴ リズ ム 探 索 時 間(秒) 分枝数 探 索 時 にPE数 を考 慮 した 下 限 値 生 成 を行 わ ない 5.lll5 5252051 探 索 時 にPE数 を考 慮 した 下 限 値 生 成 を行 う 0,874 122749 次 に割 当 てPE数3と した場 合 の 探 索 時 間 削減 率 の 評価 結 果 を 示す 。
成 踵 大 学 理 工 学 研 究 報 告 Vol50No.1(2013.6) % % % % % % % % % % % % % 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 8 7 6 5 4 3 2 1 1 2 ① d日 首 調 O ﹄ 邸 ① の } O O 刺 縛邸 国 儲 O 祠 榊 O 肇 ℃ ① 図 ■ ■ ■ ■ ■ ・1 ■ ■ ■ ■ ■1.■.■ ■ ■ ■ ■ ■ ⊥Zこ54bb1と5U⊥U⊥ ⊥⊥2⊥3⊥4⊥b⊥6⊥1⊥8⊥92U 11askし}raph」Number 図18割 当 てPE数 を3と した 問題 の最 適 解 発 見 ま で の探 索 時 間 削 減 率 の 評 価 結 果 図18は,割 当 てPE数3と した 場 合 の 評 価 結 果 で あ る。 平 均 で21.31%,最 大 で9494%の 探 索 時 間 を 削 減 す る こ とが で き た 。 探 索 時 間 が 延 び て しま っ た 問 題 は,割 当 て PE数2と した 場 合 の 考 察 と同 様 だ と考 え られ る。 図18 の 中 で 棒 グ ラ フが 出 て い な い もの は ミ リ秒 単 位 の 誤 差 と な っ た た め,こ の レベ ル だ と平 均 値 に 冗 長 な 変 化 を与 え て しま うの で0%と した。 次 に 割 当 てPE数4と した 場 合 の 探 索 時 間 削 減 率 の 評 価 結 果 を示 す 。 か し,下 限値 更 新 に よ り この 通信 遅延 を 下 限値 に組 込 む こ とで枝 切 り効 果 を 上 げ る こ とが で き る。図19の 結 果 か ら も下 限値 更新 に よ り枝 切 りの精 度 が 向 上 した と考 え ら れ る。 ▼日 自 謂 旧憾 国 目 ℃ の 7.2初 期 解 か らの 短縮 率 昨年 度 ま で の ス ケ ジ ュー ラ と今 回新 しい 下 限値 生 成 を 追 加 した ス ケ ジ ュー ラ とで 大 規模 問題 を指 定 実行 時 間 内 で解 い た場 合 の 初期 解 か ら どの程 度 暫 定解 が 向 上 され る の か を 評価 した。 探 索 時 間 は600秒 間 と した。 縦 軸 に 暫 定解 向 上 率,横 軸 を タ ス クグ ラフ 番 号 と した。 % 0 0 8 % % % % % 0 0 0 0 0 0 0 0 0 0 6 4 2 0 2 謂 温 8 口 ① ヨ ℃ ① 壱 の 舶 o o お 邸 国 q o お 0 5 ℃ ① 国 % 0 0 4 ■ 1■ 璽 ■ ■ 1■1■ ・3'与;紬 ・5・吟 ・〕歯2325↓ 歯 TaskGraphNumber 図19割 当 てPE数 を4と した 問題 の最 適 解 発 見 ま で の探 索 時 間 削 減 率 の 評 価 結 果 図19は,割 当 てPE数4と した 場 合 の 評 価 結 果 で あ る。 平 均 で30.00%,最 大 で84,86%の 探 索 時 間 を 削 減 す る こ とが で きた 。図19の 中 で 棒 グ ラ フが 出て い な い もの は 割 当 てPE数3と した場 合 の考 察 と同様 で あ る。 割 当 てPE数3,4と した 場 合 は,実 験 で使 用 した20題 の タス ク グ ラ フに とっ て 十 分 な 並 列 処 理 性 能 を期 待 で き る。 こ の場 合,PE数 を考 慮 した 下 限 値 生 成 に よ る下 限 値 向 上 は 望 め な い が,後 続 タス クの 処 理 時 間 を 考 慮 した 下 限 値 生 成 と探 索 時 の 下 限 値 更 新 に よ る枝 切 り効 果 が 期 待 で き る。割 当 てPE数4と した 場 合 は,PE数 を 十 分 以 上 に 所 持 して しま っ て い る可 能性 が 高 く,冗 長 な 組 合 せ を 生 成 して しま うこ とが あ る。 この よ うな 場 合 は 探 索 時 の 下 限 値 更 新 に よ る枝 切 り効 果 が 高 く結 果 に 反 映 され る。 通 信 遅延 を 考 慮 した 最 適化 ス ケ ジ ュー ラは よ り並 列 性 能 が 得 られ る組 合 せ か ら優 先 して 探 索 を 行 う。 これ は 割 当 て PE数 を十 分 以 上 に所 持 して い る場 合,冗 長 な 通 信 を発 生 させ る組 合 せ を優 先 して 探 索 す る こ とに 繋 が る。従 っ て, ス ケ ジ ュー リン グ効 率 を落 と して し ま うこ とが あ る。 し 図20指 定 実 行 時 間 内 の 探 索 で の 初 期 解 か らの 暫 定 解 向 上 率 図20よ り,最 大 で6.630/。,平均 で0.81%と な っ た。 タ ス クの優 先 度 の 変化 に よ り短 縮 率 が 下 が っ て しま っ た 問 題 もあ るが,全 体 平 均 で は ス ケ ジ ュー リン グ効 率 の 向 上 を確 認 で き る。 大規 模 問題 か ら最 適 解 を得 る場 合,有 効 な 下 限値 を使 用 した枝 切 り以 外 に,分 枝 操 作 に よっ て探 索 の 早期 に ど れ だ け 最適 解 に よ り近 い 暫 定解 を 算 出 で き るか が 重 要 と な る。 分枝 限 定 法 は 分枝 操 作 に よっ て 生成 され た子 問題 を 全 て 探 索 しな い 限 り,別 の 子 問題 の 探 索 を 開 始す る こ とが 出 来 な い。 大規 模 問題 の 場合,探 索 空 間 の 初期 で 下 限値 に よ り近 い 上 限値 を 得 られ な い と,枝 切 りが 進 まず, 優 良解 を発 見 で きそ うに な い 子 問題 か ら抜 け 出せ な くな る。DMHS法 で は この 問 題 に対 して,CPLMISFの ヒ ュー一一 リス テ ィ ッ クを 各 タ ス ク の プ ライ オ リテ ィ レベ ル と し, この優 先度 に従 っ た 探 索 を行 うこ とで 探 索 初期 の空 間 に 優 良解 を集 め る 手 法 を 取 っ て い る。 しか し,こ れ に 通信 遅 延 を 考 慮 した 場 合,CPLMISFの ア ル ゴ リズ ム 自体 が通 信 遅延 を考 慮 して い な い た め,こ の優 先度 に従 っ て 探 索 を す る と通 信 遅 延 を 考慮 す る 前 と同様 の期 待 を 得 る こ と は で き な い。今 回の 実 験 で は この 優 先 度 にREDICとPE数 を 考慮 した 下 限値 生 成 と後続 タス クの 処理 時 間 を考 慮 し た 下 限値 生成 に よっ て算 出 され た 下 限値 を使 用 した。 更 に,探 索 時 の 下 限値 更新 を行 い レデ ィタ ス クの 下 限値 が
成 践 大 学 理 工 学 研 究 報 告 Vol50No.1(2013.6) 変 更 され た 場 合 は,下 限 値 の 降 順 に優 先 度 を 変 更 して い る。結 果 と して は,実 験 に使 用 した30題 の タス ク グ ラ フ の 内15題 が暫 定 解 を 更新 す る こ とに成 功 して い る。勿 論, も う半 分 の15題 は 昨 年 度 ま で の ス ケ ジ ュー一一ラの 方 が 指 定 実行 時 間 内 に よ り良 い 解 の 探 索 に 成 功 して い るが,こ ち らは 今 回 下 限 値 生 成 を追加 した ス ケ ジ ュー ラが 下 限 値 生 成 の 時 間 に 手 間 取 り探 索 が 上 手 く進 ま な か った の で は な く,新 し く設 定 した 各 タス クの プ ライ オ リテ ィ レベ ル で は 探 索 空 間 の 初 期 に優 良解 を発 見 で そ うな 子 問 題 を 生 成 で きな か っ た た め だ と考 え られ る。 今 回 設 定 した プ ラ イ オ リテ ィ レベ ル で は 各 タス クに エ ン ドノー ドま で の 経 路 上 に 存在 す る全 て の 通 信 を考 慮 した わ けで はな い の で, 本 来 下 限 値 に加 え るべ き通信 遅延 時 間 を無 視 した 値 とな り,間 違 っ た優 先 度 情 報 を 与 えて しま っ た た めで あ る。 従 っ て,今 後 は この 各 タス クの プ ライ オ リテ ィ レベ ル を 向 上 させ る こ とで ス ケ ジ ュー リン グ効 率 を上 げ られ る と 考 えて い る。 8.考 察 今 回 追 加 した 下 限 値 生 成 ア ル ゴ リズ ム に よ り,ど ち ら の 評価 関 数 で もス ケ ジ ュー リン グ効 率 を 向上 させ る こ と が 出 来 た と考 え られ る。 これ は,探 索 前 の ス タテ ィ ッ ク に 求 め られ る下 限 値 が 常 にREDIC以 上 の 値 を 算 出 で き, そ れ を探 索 時 の 下 限 値 更 新 に 使 用 す る こ とで 昨 年 度 ま で の ス ケ ジ ュー ラ よ りも枝 切 りの 精 度 を落 とす こ とが な い た め だ と考 え られ る。 従 っ て,今 回 追 加 した 下 限 値 生 成 自体 の 計 算 時 間 が 探 索 時 に影 響 を与 えな い 限 りス ケ ジ ュ ー リン グ効 率 を向 上 させ る こ とが 出 来 る。 9.お わ り に 本 稿 で は分 枝 限 定 法 で 使 用 す る下 限 値 に対 して,PE数 を考 慮 した 下 限 値 生 成,後 続 タス クの 処 理 時 間 を 考 慮 し た 下 限 値 生 成,探 索 時 の 下 限 値 更 新 とい う3つ の 下 限 値 生 成 ア ル ゴ リズ ム を 提 案 した 。 こ れ を 昨 年 度 ま で の REDICと 併 用 す る こ とで,分 枝 限 定 法 の 探 索 効 率 を向 上 させ る こ とに 成 功 した。
