| 講演名 | 2003/11/18 異種並列計算環境における分割可能なデータの収集操作スケジューリング 大下 福仁, 松前 進, 増澤 利光, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | さまざまな種類のプロセッサを通信リンクで接続した異種並列計算環境が並列計算に利用されている.並列計算の多くは集合通信を利用しており,効率のよい並列計算を実現するには効率のよい集合通信操作が必要である.本報告では,代表的な集合通信操作である収集操作について,データを自由に分割可能であるという仮定のもとで,異種並列計算環境に適したアルゴリズムの考察を行う.本報告では,収集操作の実行時間を最小化するスケジュールを求める問題(GSP),収集操作を繰り返し実行する場合にスループットを最大化するスケジュールを求める問題(GSSP)について考察する.本報告の結果は以下の通りである.1)GSSPに対する(3/2+ε)-近似アルゴリズムを与える(εは0<ε<1なる任意の定数),2)GSSPに対するα-近似スケジュールからGSPに対するα+ε近似スケジュールを作成できることを示す(εは0<ε<1なる任意の定数). |
| 抄録(英) | A heterogeneous parallel computing environment consisting of several types of workstations plays an important role in parallel computing. In many applications on the system, collective communications are commonly used as communication primitives. Thus, design of the effecient collective communications is the key to achieve high-performance parallel computing. But the heterogeneity of the system complicates the design. In this paper, we consider design of an efficient gather operation, which is one of the most important collective operations, under the assumption that we can divie data arbitrarily. We consider two problems, the GSP and the GSSP. The GSP is the problem to to find a schedule that minimizes the execution time of the gather operation, and the GSSP is one to find a schedule that maximizes the throughput of the gather operations when the gather operations are repeatedly executed. For the GSSP, we propose the algorithm that finds a (3/2+ε)-approximate schedule for any constant ε (0<ε<1). For the GSP, we show that, when given an α-approximate schedule for the GSSP, we can construct an (α+ε)-approximate schedule for any constant ε(0<ε<1). |
| キーワード(和) | 異種並列計算環境 / 収集操作 / 集合通信 / 分割可能なデータ / スケジューリングアルゴリズム |
| キーワード(英) | collective communication / scheduling algorithm |
| 資料番号 | COMP2003-57 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2003/11/18(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 異種並列計算環境における分割可能なデータの収集操作スケジューリング |
| サブタイトル（和） | |
| タイトル（英） | Efficient Gather Operation in Heterogeneous Parallel Computing Environments with Divisible Data |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 異種並列計算環境 / collective communication |
| キーワード(2)（和/英） | 収集操作 / scheduling algorithm |
| キーワード(3)（和/英） | 集合通信 |
| キーワード(4)（和/英） | 分割可能なデータ |
| キーワード(5)（和/英） | スケジューリングアルゴリズム |
| 第 1 著者 氏名（和/英） | 大下 福仁 / Fukuhito OOSHITA |
| 第 1 著者 所属（和/英） | 大阪大学大学院情報科学研究科 Graduate School of Information Science and Technology, Osaka University |
| 第 2 著者 氏名（和/英） | 松前 進 / Susumu MATSUMAE |
| 第 2 著者 所属（和/英） | 鳥取環境大学環境情報学部 Faculty of Environmental and Information Studies, Tottori University of Environmental Studies |
| 第 3 著者 氏名（和/英） | 増澤 利光 / Tsohimitsu MASUZAWA |
| 第 3 著者 所属（和/英） | 大阪大学大学院情報科学研究科 Graduate School of Information Science and Technology, Osaka University |
| 発表年月日 | 2003/11/18 |
| 資料番号 | COMP2003-57 |
| 巻番号（vol） | vol.103 |
| 号番号（no） | 468 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |