IEICE TRANSACTIONS on Information
Efficient Two-Opt Collective-Communication Operations on Low-Latency Random Network Topologies
Summary :
Random network topologies have been proposed as a low-latency network for parallel computers. Although multicast is a common collective-communication operation, multicast algorithms each of which consists of a large number of unicasts are not well optimized for random network topologies. In this study, we firstly apply a two-opt algorithm for building efficient multicast on random network topologies. The two-opt algorithm creates a skilled ordered list of visiting nodes to minimize the total path hops or the total possible contention counts of unicasts that form the target multicast. We secondly extend to apply the two-opt algorithm for the other collective-communication operations, e.g., allreduce and allgather. The SimGrid discrete-event simulation results show that the two-opt multicast outperforms that in typical MPI implementation by up to 22% of the execution time of an MPI program that repeats the MPI_Bcast function. The two-opt allreduce and the two-opt allgather operations also improve by up to 15% and 14% the execution time when compared to those used in typical MPI implementations, respectively.
- Publication
- IEICE TRANSACTIONS on Information Vol.E103-D No.12 pp.2435-2443
- Publication Date
- 2020/12/01
- Publicized
- 2020/07/03
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2020PAP0004
- Type of Manuscript
- Special Section PAPER (Special Section on Parallel, Distributed, and Reconfigurable Computing, and Networking)
- Category
- Fundamentals of Information Systems
Authors
Ke CUI
SOKENDAI
Michihiro KOIBUCHI
SOKENDAI
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Ke CUI, Michihiro KOIBUCHI, "Efficient Two-Opt Collective-Communication Operations on Low-Latency Random Network Topologies" in IEICE TRANSACTIONS on Information,
vol. E103-D, no. 12, pp. 2435-2443, December 2020, doi: 10.1587/transinf.2020PAP0004.
Abstract: Random network topologies have been proposed as a low-latency network for parallel computers. Although multicast is a common collective-communication operation, multicast algorithms each of which consists of a large number of unicasts are not well optimized for random network topologies. In this study, we firstly apply a two-opt algorithm for building efficient multicast on random network topologies. The two-opt algorithm creates a skilled ordered list of visiting nodes to minimize the total path hops or the total possible contention counts of unicasts that form the target multicast. We secondly extend to apply the two-opt algorithm for the other collective-communication operations, e.g., allreduce and allgather. The SimGrid discrete-event simulation results show that the two-opt multicast outperforms that in typical MPI implementation by up to 22% of the execution time of an MPI program that repeats the MPI_Bcast function. The two-opt allreduce and the two-opt allgather operations also improve by up to 15% and 14% the execution time when compared to those used in typical MPI implementations, respectively.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2020PAP0004/_p
Copy
@ARTICLE{e103-d_12_2435,
author={Ke CUI, Michihiro KOIBUCHI, },
journal={IEICE TRANSACTIONS on Information},
title={Efficient Two-Opt Collective-Communication Operations on Low-Latency Random Network Topologies},
year={2020},
volume={E103-D},
number={12},
pages={2435-2443},
abstract={Random network topologies have been proposed as a low-latency network for parallel computers. Although multicast is a common collective-communication operation, multicast algorithms each of which consists of a large number of unicasts are not well optimized for random network topologies. In this study, we firstly apply a two-opt algorithm for building efficient multicast on random network topologies. The two-opt algorithm creates a skilled ordered list of visiting nodes to minimize the total path hops or the total possible contention counts of unicasts that form the target multicast. We secondly extend to apply the two-opt algorithm for the other collective-communication operations, e.g., allreduce and allgather. The SimGrid discrete-event simulation results show that the two-opt multicast outperforms that in typical MPI implementation by up to 22% of the execution time of an MPI program that repeats the MPI_Bcast function. The two-opt allreduce and the two-opt allgather operations also improve by up to 15% and 14% the execution time when compared to those used in typical MPI implementations, respectively.},
keywords={},
doi={10.1587/transinf.2020PAP0004},
ISSN={1745-1361},
month={December},}
Copy
TY - JOUR
TI - Efficient Two-Opt Collective-Communication Operations on Low-Latency Random Network Topologies
T2 - IEICE TRANSACTIONS on Information
SP - 2435
EP - 2443
AU - Ke CUI
AU - Michihiro KOIBUCHI
PY - 2020
DO - 10.1587/transinf.2020PAP0004
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E103-D
IS - 12
JA - IEICE TRANSACTIONS on Information
Y1 - December 2020
AB - Random network topologies have been proposed as a low-latency network for parallel computers. Although multicast is a common collective-communication operation, multicast algorithms each of which consists of a large number of unicasts are not well optimized for random network topologies. In this study, we firstly apply a two-opt algorithm for building efficient multicast on random network topologies. The two-opt algorithm creates a skilled ordered list of visiting nodes to minimize the total path hops or the total possible contention counts of unicasts that form the target multicast. We secondly extend to apply the two-opt algorithm for the other collective-communication operations, e.g., allreduce and allgather. The SimGrid discrete-event simulation results show that the two-opt multicast outperforms that in typical MPI implementation by up to 22% of the execution time of an MPI program that repeats the MPI_Bcast function. The two-opt allreduce and the two-opt allgather operations also improve by up to 15% and 14% the execution time when compared to those used in typical MPI implementations, respectively.
ER -
English
