Scheduling for Gather Operation in Heterogeneous Parallel Computing Environments
スポンサーリンク
概要
- 論文の詳細を見る
A heterogeneous parallel computing environment consisting of different types of workstations and communication links plays an important role in parallel computing. In many applications on the system, collective communication operations are commonly used as communication primitives. Thus, design of the efficient collective communication operations 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, one of the most important collective operations. We show that an optimal gather schedule is found in O(n^<2k-1>) time for the heterogeneous parallel computing environment with n processors of k distinct types, and that a nearly-optimal schedule is found in O(n) time if k=2.
- 社団法人電子情報通信学会の論文
- 2003-04-01
著者
-
OOSHITA Fukuhito
Graduate School of Information Science and Technology, Osaka University
-
MASUZAWA Toshimitsu
Graduate School of Information Science and Technology, Osaka University
-
MASUZAWA Toshimitsu
the Graduate School of Information Science and Technology, Osaka University
-
松前 進
鳥取環境大学環境情報学部
-
松前 進
佐賀大学理工学部知能情報システム学科
-
Masuzawa Toshimitsu
Graduate School Of Information Science Nara Institute Of Science And Technology
-
Masuzawa Toshimitsu
Nara Institute Of Sciences And Technology
-
Masuzawa Toshimitsu
Graduate School Of Engineering Science Osaka University
-
Masuzawa Toshimitsu
Department Of Computer Science Graduate School Of Information Science And Technology Osaka Universit
-
MATSUMAE Susumu
Faculty of Environmental and Information Studies,Tottori University of Environmental Studies
-
Matsumae S
Tottori Univ. Environmental Studies Tottori‐shi Jpn
-
Ooshita Fukuhito
Graduate School Of Information Science And Technology Osaka University
関連論文
- Fault-Tolerant and Self-Stabilizing Protocols Using an Unreliable Failure Detector
- 教員の作業効率向上を目指した授業支援システムの構築と運用
- (135)教員の作業効率向上を目指した授業支援システムの構築と運用(セッション39 教育システムA(講義・演習)IX)
- (148)Javaを導入言語としたプログラミング教育(第39セッション 教育研究指導(III))
- A Self-Adaptive Routing Protocol in Wireless LANs Based on Attractor Selection
- A Biologically Inspired Self-Adaptation of Replica Density Control
- A Message-Efficient Peer-to-Peer Search Protocol Based on Adaptive Index Dissemination
- An Efficient Index Dissemination in Unstructured Peer-to-Peer Networks
- Self-Adaptive Mobile Agent Population Control in Dynamic Networks Based on the Single Species Population Model(Distributed Cooperation and Agents)
- Timed Uniform Atomic Broadcast in Presence of Crash and Timing Faults(Foundations of Computer Science)
- Wait-Free Linearizable Distributed Shared Memory
- Parallel Algorithms for the All Nearest Neighbors of Binary Image on the BSP Model
- High-Level Synthesis for Weakly Testable Data Paths(Special Issue on Test and Diagnosis of VLSI)
- A Simple Parallel Algorithm for the Medial Axis Transform (Special Issue on Architectures Algorithms and Networks for Massively parallel Computing)
- Timed Atomic Broadcast Resiliet to Multiple Timing Faults
- 固定サイズの再構成メッシュ上で凸包を求めるアルゴリズム
- 問題のサイズより小さい再構成メッシュ上でのソーティングアルゴリズム
- 固定サイズの再構成メッシュ上で凸包を求めるアルゴリズム
- 問題のサイズより小さい再構成メッシュ上でのソーティングアルゴリズム
- 固定サイズの再構成メッシュ上で凸包を求めるアルゴリズム(並列・分散)
- 問題のサイズより小さい再構成メッシュ上でのソーティングアルゴリズム(並列・分散)
- 固定サイズの再構成メッシュ上で任意個の値をソートするアルゴリズム
- SOMによる道路標識の形状判定方式の検討
- Timed Atomic Broadcast Resiliet to Multiple Timing Faults
- A Parallel Method for the Prefix Convex Hulls Problem
- Distributed Leader Election on Chordal Ring Networks
- 異種並列計算環境におけるブロードキャストスケジューリング(LAシンポジウム(計算機科学基礎理論ワークショップ)論文小特集)
- 異種クラスタシステムにおけるブロードキャストスケジューリングについて
- D-1-8 数値シミュレーションにおける多重格子法を応用した収束時間の改善(D-1. コンピュテーション,一般セッション)
- B-8-30 教育機関における情報コンセントの不具合とメンテナンスの検討(B-8.通信方式,一般講演)
- Scheduling for Independent-Task Applications on Heterogeneous Parallel Computing Environments under the Unidirectional One-Port Model(Parallel and Distributed Computing,Foundations of Computer Science)
- An Efficient Scaling-Simulation Algorithm of Reconfigurable Meshes by Meshes with Statically Partitioned Buses(Foundations of Computer Science)
- Scheduling for Gather Operation in Heterogeneous Parallel Computing Environments
- A Self-Stabilizing Spanning Tree Protocol that Tolerates Non-quiescent Permanent Faults
- Fault-Tolerance of Distributed Algorithms : Self-Stabilization and Wait-Freedom(Special Issue on Algorithm Engineering : Surveys)
- Hierarchical Composition of Self-Stabilizing Protocols Preserving the Fault-Containment Property
- Distributed Construction Protocols of Probabilistic Degree-Weighted Peer-to-Peer Overlays
- Self-Stabilization in Dynamic Networks
- A Non-scan DFT Method at Register-Transfer Level to Achieve 100% Fault Efficiency (特集:システムLSIの設計技術と設計自動化)
- Parallel Selection Algorithms for CGM and BSP Models with Application to Sorting (特集 並列処理) -- (並列・分散アルゴリズム)
- Efficient Linearizable Implementation of Shared FIFO Queues and General Objects on a Distributed System(Special Section on Discrete Mathematics and Its Applications)
- Self-Stabilizing Agent Traversal on Tree Networks(Distributed Cooperation and Agents)
- SOMによる道路標識認識の一検討
- Simulating a Mesh with Separable Buses
- Simulation Algorithms among Enhanced Mesh Models
- 異種並列計算環境における分割可能なデータの収集操作スケジューリング
- 異種並列計算環境における分割可能なデータの収集操作スケジューリング
- 動的再構成可能な行/列方向バスを複数の静的バスを用いて模倣する最適アルゴリズム
- 区分バス付メッシュ結合型計算機による分割可能バス付メッシュ結合型計算機のScaling-Simulationアルゴリズム
- 異種クラスタシステムにおける収集操作スケジューリング
- 佐賀大学JABEE認定プログラムの取り組み : 系統的な教育プログラム構築と教員間の連携促進 (特集 大学教育の質保証)
- Time-Optimal Gathering Algorithm of Mobile Robots with Local Weak Multiplicity Detection in Rings
- A Method of Parallelizing Consensuses for Accelerating Byzantine Fault Tolerance