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

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

• 批准号: 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

进行了研究以开发批量同步调度问题的近似算法（以下称为BSP问题）。结果，我们已经开发了一种方法来有效地将任务计划问题的时间表（以下称为SP问题）转换为批量同步时间表，同时考虑到正常的通信延迟（而不是BSP问题），当所有任务执行时间都是单位时间的时间，而通信延迟是恒定的（不是BSP问题）。该方法将SP问题的α-及时时间表转换为相应的BSP问题的2α-附近批量同步时间表。通过将此方法与SP问题的现有近似算法相结合，可以获得BSP问题的近似算法。自古以来，SP问题就存在。由于已知许多有效的近似算法，因此本研究中开发的转换方法可用于为BSP问题提供许多有效的近似算法。此外，在这项研究中，我们还提供了证明，这种提出的转换方法是最佳转换方法（没有算法生成的批量同步时间表的近似准确性比SP问题的2α-应用程序表的近似精度更好）。 These results were collected in the following IEEE papers: Noriyuki Fujimoto and Kenichi Hagihara,"On Approximate 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

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。

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

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

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

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

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

山本, 譚, 藤本, 萩原: "一対一プロセッサ間通信の一括化を考慮したタスクスケジューリングアルゴリズム"情報処理学会論文誌:数理モデル化と応用. 43・SIG7 (TOM 6). 29-43 (2002)

Yamamoto、Tan、Fujimoto、Hagiwara：“考虑一对一处理器之间批量通信的任务调度算法”日本信息处理学会汇刊：数学建模和应用 43·SIG7 (TOM 6)。 ）