A Memory-Efficient Algorithm and Its Implementation of Variable-Size All-to-All Communication
スポンサーリンク
概要
- 論文の詳細を見る
This paper proposes a memory-efficient algorithm of variable-size all-to-all communication based on bitonic sort and in-place merge. The algorithm takes O(N log2 P) computation and communication time and requires merely O(P) extra space for the communication among P processes having N elements of data to be exchanged for each. We also discuss another algorithm which takes O(MP log P) time where M is the size of the largest chunk which a process must send to another process and thus is expected to be O(N/P) in most practical applications to make the time complexity O(N log P). We implemented the first sort-based algorithm to show it works with reasonable efficiency.
- 一般社団法人情報処理学会の論文
- 2009-07-28
著者
-
Bingbing Zhuang
Graduate School of Informatics, Kyoto University
-
Hiroshi Nagamochi
Graduate School of Informatics, Kyoto University
-
Nagamochi Hiroshi
Kyoto Univ.
-
Hiroshi Nagamochi
Graduate School Of Informatics Kyoto University
-
Bingbing Zhuang
Graduate School Of Informatics Kyoto University
-
Hiroshi Nakashima
ACCMS, Kyoto University
-
Hiroshi Nakashima
Accms Kyoto University
関連論文
- Constant Time Generation of Trees with Degree Bounds
- A Memory-Efficient Algorithm and Its Implementation of Variable-Size All-to-All Communication
- k-Edge and 3-Vertex Connectivity Augmentation in an Arbitrary Multigraph
- Augmenting Edge-Connectivity and Vertex-Connectivity Simultaneously
- Enumerating Colored and Rooted Outerplanar Graphs
- BI-CRITERIA FOOD PACKING BY DYNAMIC PROGRAMMING(the 50th Anniversary of the Operations Research Society of Japan)
- APPROXIMATING MINIMUM COST MULTIGRAPHS OF SPECIFIED EDGE-CONNECTIVITY UNDER DEGREE BOUNDS(the 50th Anniversary of the Operations Research Society of Japan)
- An Efficient Vector Transfer for Sparse Matrix-Vector Multiplication on Distributed Memory Systems
- Orthogonal Drawings for Plane Graphs with Specified Face Areas
- Efficient Representation of Constraints and Propagation of Variable-Value Symmetries in Distributed Constraint Reasoning
- Symmetry Breaking by Dominance Detection in Distributed Environments
- Around the Constructive Orbit Problem in Distributed Constraint Programming
- The Next-to-Shortest Path in Undirected Graphs with Nonnegative Weights
- FOREWORD (Special Section on Discrete Mathematics and Its Applications)
- GRAPH ALGORITHMS FOR NETWORK CONNECTIVITY PROBLEMS(Network Design, Control and Optimization)
- Accelerating A* algorithms by sweeping out small-degree nodes
- CONSTANT FACTOR APPROXIMATION ALGORITHMS FOR REPETITIVE ROUTING PROBLEMS OF GRASP-AND-DELIVERY ROBOTS IN PRODUCTION OF PRINTED CIRCUIT BOARDS
- A Simulation-Based Analysis for Worst Case Delay of Single and Multiple Interruptions
- Multilingualization Based on RPC for Job-level Parallel Script Language, Xcrypt
- Breadth-first Search Approach to Enumeration of Tree-like Chemical Compounds
- Breadth-first Search Approach to Enumeration of Tree-like Chemical Compounds
- CONSTANT FACTOR APPROXIMATION ALGORITHMS FOR REPETITIVE ROUTING PROBLEMS OF GRASP-AND-DELIVERY ROBOTS IN PRODUCTION OF PRINTED CIRCUIT BOARDS