权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

データ転送遅延を考慮したパラメータ・スウィープ型GRID計算のスケジューリング

考虑数据传输延迟的调度参数扫描型GRID计算

基本信息

批准号：
16016262
负责人：
藤本典幸
金额：
$ 4.67万
依托单位：
Osaka University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research on Priority Areas
财政年份：
2004
资助国家：
日本
起止时间：
2004 至 2005
项目状态：
已结题

项目摘要

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

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 is solved by minimizing the motion of the TPCC in response to the TPCC in response to the motion of the TPCC in response to the TPCC in response to the motion of the TPCC in response to the motion of the TPCC in response to the motion in response to the TPCC in response to the motion in response to the TPCC in response 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 are as follows: the size of TPCC and the running time are consistent; especially, the size of TPCC is small and the running time is large; the running time is large and the running time is large. The results of this study are: the problem of minimizing the running time.

项目成果

期刊论文数量（8）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Prediction-Aware Experimental Evaluation of Dynamic Task Scheduling Algorithms for Parametric Study on a Desktop Grid

用于桌面网格参数研究的动态任务调度算法的预测感知实验评估

DOI：
发表时间：
2005
期刊：
Proceedings of the 2005 international Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA 2005)
影响因子：
0
作者：
Takanori Mori;Akio Nakata;Teruo Higashino;藤本典幸
通讯作者：
藤本典幸

A comparison among grid scheduling algorithms for independent coarse-grained tasks

DOI：
10.1109/saintw.2004.1268711
发表时间：
2004-01
期刊：
2004 International Symposium on Applications and the Internet Workshops. 2004 Workshops.
影响因子：
0
作者：
N. Fujimoto;K. Hagihara
通讯作者：
N. Fujimoto;K. Hagihara

進化戦略のためのグリッド計算に関する一考察

进化策略网格计算研究