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が小さくとも実行時間が大きい場合,その実行時間の大きさは使用し得たグリッドの総計算パワーに対して適性である.このため本研究の成果は,実行時間最小化問題に対しても有効であると考えられる.

The following results are obtained for the calculation of the motion of each element in the matrix: the minimization problem of the running time; the approximation problem; the proof of the existence of the general motion of the matrix; the proposal of the evaluation criterion of the running time; the calculation problem (TPCC); For coarse grained, coarse grained, coarse In general, the TPCC problem of minimizing the motion of the motion is solved by solving the motion of the Note that the approximation ratio is $n$$$m$, which is very large and optimal ($1$). The proposal is to calculate the approximate rate of motion of the motion and predict the motion of the motion. The results of this study show that the approximate range of TPCC is consistent with the running time of TPCC. In particular, the minimum range of TPCC is consistent with the minimum running time of TPCC. When TPCC is running for a long time, the running time of TPCC is used to calculate the suitability of TPCC. The results of this study are: the problem of minimizing the running time.

项目成果

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: "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 事务。

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）。