著者

須田 礼仁

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告ハイパフォーマンスコンピューティング(HPC) (ISSN:09196072)

巻号頁・発行日

vol.2007, no.59, pp.1-6, 2007-06-08

被引用文献数

1

---

Multi-master divisible load は著者らが提案してきたタスク再分散のためのモデルである.本稿の第1のテーマは,これまでに提案してきた手法の性能解析である.問題は 3 つのクラスに分けられ,それぞれタスク量 $T$ に対して最適解との性能比が $1 + O(\sqrt T)$ $1 + O(\log T/T)$ $1 + O(1/T)$ となることが示された.第2のテーマはこれまでに提案してきた手法で得られたスケジュールの改良である.通信時間の定数項や必須のアイドル時間を考慮し,各プロセッサがほぼ同時に計算を終了するようにスケジュールを改良した.その結果,近似解と最適解との差を 1/2 から 1/3 にすることができた.Multi-master divisible load is a model for task redistribution. This paper first discusses a performance analysis of our scheme. The problems are classified into three classes, and the relative performance against the optimum solution is $1 + O(\sqrt T)$, $1 + O(\log T/T)$, and $1 + O(1/T)$, respectively, where $T$ is the total task size. Second the schedules are improved, where the constant terms of the communication times and inevitable idle times are considered, and the completion times of the processors becomes nearly the same. The difference of the approximation and the optimum solutions is reduced into 1/2 or 1/3.