バルク同期スケジューリング問題の近似アルゴリズムの開発

批量同步调度问题的近似算法的开发

• 批准号: 14780213
• 负责人: 藤本 典幸
• 金额: $ 2.56万
• 依托单位: Osaka University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2002
• 资助国家: 日本
• 起止时间: 2002 至 2004
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-14780213/
• 关键词: 並列処理; タスクスケジューリング; BSPモデル; 近似アルゴリズム; バルク同期スケジュール; タスケスケジューリング; バルク同期; 近似不可能性

バルク同期スケジューリング問題(以降BSP問題)に対する近似アルゴリズム開発のための研究を行った。その結果,タスクの実行時間がすべて単位時間であり,かつ,通信遅延が一定の場合に(BSP問題でない)通常の通信遅延を考慮したタスクスケジューリング問題(以降SP問題)のスケジュールを効率よくバルク同期スケジュールに変換する手法を開発した.この手法はSP問題のα-近似スケジュールを対応するBSP問題の2α-近似のバルク同期スケジュールに変換するものである.この手法をSP問題の既存の近似アルゴリズムと組み合わせれば,BSP問題の近似アルゴリズムが得られる.SP問題は古くからよく研究されており,効率の良い近似アルゴリズムが多数知られているため,本研究で開発した変換手法は,BSP問題に対する効率のよい近似アルゴリズムを多数与える有益なものである.さらに本研究では,この提案する変換手法が最適な変換手法である(SP問題のα-近似スケジュールからBSP問題の2α-近似スケジュールより良い近似精度を持つバルク同期スケジュールを生成するアルゴリズムは一般には存在しない)ことの証明も与えた.これらの結果は以下のIEEEの論文誌に採録された:Noriyuki Fujimoto and Kenichi Hagihara,"On Approximation of the Bulk Synchronous Task Scheduling Problem",IEEE Transactions on Parallel and Distributed Systems, Vol.14,No.11,pp.1191-1199,2003

In order to reduce the BSP problem, we need to discuss the issue of health care (in order to reduce the number of problems). The results show that the communication delay is limited (BSP problem is a problem). Usually, the communication delay is related to the failure rate of the SP problem. The SP problem α-approximate to the BSP problem 2 α-the approximate to the same time to the BSP problem. The existing method of SP problem is similar to that of problem, and the problem of SP problem is similar to that of SP problem. The rate of success is similar to that of the majority of people who know about it. In this study, we have done some research on this topic. The BSP problem is similar to that of the majority and the benefit of the problem. In the course of this study, we proposed that the most accurate method (SP problem α-approximate to BSP problem 2 α-approximate to BSP problem 2 α-approximate accuracy in the same period of time). The results are as follows: Noriyuki Fujimoto and Kenichi Hagihara, "On Approximation of the Bulk Synchronous Task Scheduling Problem", IEEE Transactions on Parallel and Distributed Systems, Vol.14,No.11,pp.1191-1199, 2003.

项目成果

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.
• 作者: N. Fujimoto;K. Hagihara

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

一种动态任务调度的近似算法，旨在最小化网格上参数扫描计算所消耗的剩余计算能力。

• 发表时间: 2005
• 期刊: 情報処理学会論文誌:数理モデル化と応用 (印刷中)
• 作者: 藤本典幸

N.Fujimoto, K.Hagihara: "Near-Optimal Task Scheduling of a Complete K-ary Tree with Communication Delays"Proc. 6th WSEAS Int'l Conf. on Computers. 6. 7491-7496 (2002)

N.Fujimoto、K.Hagihara：“具有通信延迟的完整 K 叉树的近乎最优任务调度”Proc。

Y.Kawasaki: "High Performance Computing Service over the Internet for Intraoperative Image Processing"IEEE Transactions on Information Technology in Biomedicine. (発表予定). (2004)

Y. Kawasaki：“用于术中图像处理的互联网高性能计算服务”IEEE 生物医学信息技术汇刊（即将出版）。

河村一史: "最小値関数を用いて適合度を算出するNRA検索アルゴリズムの改善"情報処理学会論文誌:データベース. Vol.44 No.SIG12. 74-85 (2003)

Kazushi Kawamura：“使用最小值函数计算适应度的 NRA 搜索算法的改进”日本信息处理学会交易：数据库第 44 卷第 74-85 号。