グリッド上でのパラメータ・スウィープ計算を対象として消費余剰計算力の最小化をねらった動的タスクスケジューリングのための近似アルゴリズム

• Item type: Trans(1)
• 公開日: 2005-06-15
• タイトル: グリッド上でのパラメータ・スウィープ計算を対象として消費余剰計算力の最小化をねらった動的タスクスケジューリングのための近似アルゴリズム
• タイトル / 言語: en
• タイトル: An Approximation Algorithm for Dynamic Task Scheduling to Minimize Spare Computing Power Consumed by a Parameter Sweep Application on a Computational Grid
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: シンポジウム特集論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 大阪大学大学院情報科学研究科
• 著者所属: 大阪大学大学院情報科学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology Osaka University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology Osaka University
• 著者名: 藤本, 典幸; 萩原, 兼一
• 著者名(英): Noriyuki, Fujimoto; Kenichi, Hagihara
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: タスクスケジューリング問題の目的関数として最も一般的なものはメイクスパンである．しかし計算グリッドを対象とする場合，計算グリッドを構成する各計算機の余剰計算力は時間の経過につれて変化するため，2 番目に小さいメイクスパンは最適メイクスパンよりいくらでも大きくなりうる．このため，スケジュールの評価基準をメイクスパンとする場合は，計算グリッドを対象とするタスクスケジューリング問題に近似アルゴリズムは一般には存在しない．本論文では，スケジュールの新しい評価基準として，余剰計算力の消費量を用いることを提案する．さらに本論文では，この評価基準の最小化を目的として，同じサイズのn 個の独立粗粒度タスクをm プロセッサの計算グリッドに動的にスケジューリングする問題に対して，(1 + m(loge(m?1)+1)n )?近似アルゴリズムを提案する．提案アルゴリズムは計算グリッドの性能予測をまったく必要としない．提案アルゴリズムの近似率は，プロセッサ数を固定してタスク数を大きくしていくと急激に最適値に近づいていく．この結果は，プロセッサ数にくらべてタスク数が相応に大きい場合は，各プロセッサの負荷が動的にどのように変動しようとも，その予測なしに，パラメータ・スウィープ型アプリケーションが消費する余剰計算力をほぼ最適に抑えられることを示している．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The most common objective function of task scheduling problems is makespan. However, on a computational grid, the 2nd optimal makespan may be much longer than the optimal makespan because the computing power of a grid varies over time. So, if the performance measure is makespan, there is no approximation algorithm in general for scheduling onto a grid. In this paper, a novel criterion of a schedule is proposed. The proposed criterion is called total processor cycle consumption, which is the total number of instructions the grid could compute until the completion time of the schedule. Moreover, for the criterion, this paper gives a (1 + m(loge(m竏驤€1)+1) n )-approximation algorithm for scheduling n independent coarsegrained tasks with the same length onto a grid with m processors. The proposed algorithm does not use any prediction information on the performance of underlying resources. This result implies a non-trivial result that the computing power consumed by a parameter sweep application can be limited in such a case within (1+ m(loge(m竏驤€1)+1) n ) times that required by an optimal schedule, regardless how the speed of each processor varies over time.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464803
• 書誌情報: 情報処理学会論文誌数理モデル化と応用（TOM）; 巻 46, 号 SIG10(TOM12), p. 1-9, 発行日 2005-06-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7780
• 出版者 / 言語: ja
• 出版者: 情報処理学会