Parameter Sweep型GRID計算のスケジューリングに関する研究

参数扫描型GRID计算调度研究

• 批准号: 15017260
• 负责人: 藤本 典幸
• 金额: $ 1.15万
• 依托单位: Osaka University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research on Priority Areas
• 财政年份: 2003
• 资助国家: 日本
• 起止时间: 2003 至 无数据
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-15017260/
• 关键词: グリッド・コンピューティング; タスクスケジューリング; Parameter Sweep; 近似アルゴリズム; 計算グリッド

計算グリッドを対象に,グリッド中の各マシンの計算パワーの動的変動を考慮したParameter Sweepアプリケーションの動的スケジューリング問題に対して以下の結果を得た:実行時間の最小化問題に対する近似アルゴリズムは一般には存在しないことの証明;実行時間に代わるスケジュールの評価基準として,アプリケーションが消費するグリッドの計算パワー(TPCC)を用いることの提案;各タスクが粗粒度で,かつ,大きさが等しい場合に,TPCCを最小化する動的スケジューリング問題に対する$1+m(\log_e(m-1)+1)/n$-近似アルゴリズム($m$はグリッドのマシン数,$n$はタスク数).またタスクグラフが一般の場合に対して提案アルゴリズムの拡張を行い,TPCCを最小化する動的スケジューリング問題に対する$1+L_{cp}(n)\cdot m(\log_e(m-1)+1)/n$-近似アルゴリズム($L_{cp}(n)$はタスクグラフのクリティカルパス長)を得た.上記の近似率は$n$が$m$に対して十分大きいならば,ほとんど最適(すなわち$1$)となる.提案アルゴリズムは計算パワーの動的変動の予測なしに上記の近似率を必ず達成する.本研究の成果である上記の近似アルゴリズムは,グリッドのスケジューリング問題に対する世界で最初の近似アルゴリズムである.TPCCと実行時間の間には以下の強い関係がある:TPCCの大小と実行時間の大小は一致する;特に,TPCC最小のスケジユールの集合と実行時間最小のスケジュールの集合は一致する;TPCCが小さくとも実行時間が大きい場合,その実行時間の大きさは使用し得たグリッドの総計算パワーに対して適性である.このため本研究の成果は,実行時間最小化問題に対しても有効であると考えられる.

对于参数扫描应用程序的动态调度问题获得了以下结果，这些应用程序考虑了电网中每台机器的计算能力的动态变化，并考虑了计算网格的目的：证明没有一般近似算法来最小化执行时间；提出使用应用程序消耗的电网的计算能力作为评估时间表代替执行时间的标准； $ 1+m（\ log_e（M-1）+1）/n $ - 动态调度问题的近似算法，当每个任务都是粗粒且相等的幅度时，将TPCC最小化（$ m $是网格中的机器数量，$ n $是任务的数量）。另外，对于任务图是常见的情况，并且$ 1+l_ {cp}（n）\ cdot m（\ log_e（m-1）+1）/n $ -approximation算法（$ l_ {cp}（cp}（n）$是任务图的关键路径长度），则提出的算法是扩展的。上述近似率几乎是最佳的（即$ 1 $），如果$ n $对于$ m $足够大。所提出的算法始终达到上述近似率，而无需预测计算能力的动态变化。上述近似算法是这项研究的结果，是世界上第一个解决网格调度问题的问题。大约算法。 TPCC和执行时间之间存在牢固的关系：TPCC的大小和执行时间与TPCC的大小和TPCC的大小相匹配；特别是，最低TPCC计划匹配的一组时间表；如果TPCC很小，但执行时间很长，则执行时间的大小适用于可以使用的网格的总计算能力。因此，这项研究的结果被认为对运行时间最小化的问题有效。

项目成果

N.Fujimoto: "A Comparison among Grid Scheduling Algorithms for Independent Coarse-Grained Tasks"SAINT 2004 Workshop on High Performance Grid Computing and Networking. 674-680 (2004)

N.Fujimoto：“独立粗粒度任务的网格调度算法的比较”SAINT 2004 高性能网格计算和网络研讨会。

N.Fujimoto: "Near-Optimal Dynamic Task Scheduling of Precedence Constrained Coarse-Grained Tasks onto a Computational Grid"The 2^<nd> International Symposium on Parallel and Distributed Computing (ISPDC 2003). 80-87 (2003)

N.Fujimoto：“计算网格上优先级约束粗粒度任务的近乎最优动态任务调度”第二届并行和分布式计算国际研讨会 (ISPDC 2003)。

N.Fujimoto: "Near-Optimal Dynamic Task Scheduling of Independent Coarse-Grained Tasks onto a Computational Grid"The 32^<nd> International Conference on Parallel Processing (ICPP-03). 391-398 (2003)

N.Fujimoto：“计算网格上独立粗粒度任务的近乎最优动态任务调度”第 32 届国际并行处理会议 (ICPP-03)。

N.Fujimoto: "An Approximation Algorithm for Dynamic Task Scheduling of Independent Coarse-Grained Tasks onto a Computational Grid"Symposium on Problem Solving by Parallel and Distributed Procedure (SPSPDP 2003). 82-89 (2003)

N.Fujimoto：“计算网格上独立粗粒度任务动态任务调度的近似算法”并行和分布式程序解决问题研讨会（SPSPDP 2003）。

N.Fujimoto: "Experimental Evaluation of an Approximation Algorithm for Scheduling Independent Tasks onto a Computational Grid"WSEAS Transactions on Computers. Vol.3. 335-340 (2004)

N.Fujimoto：“在计算网格上调度独立任务的近似算法的实验评估”计算机上的 WSEAS 事务。