The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
병렬 계산에서는 노드 간 통신이 필수적입니다. 병렬 처리의 성능은 계산과 통신의 효율성에 따라 달라지므로 통신 비용은 무시할 수 없습니다. 병렬 응용 프로그램에는 계산 노드 간의 데이터 교환에 의해 결정되는 논리적 통신 구조가 포함됩니다. 때로는 논리적 통신 구조가 실제 병렬 시스템의 구조와 일치하지 않는 경우도 있습니다. 이러한 불일치로 인해 통신 비용이 많이 발생합니다. 본 논문에서는 노드의 논리적 위치를 재배열하여 불일치 정도를 줄이는 노드 매핑 문제를 다룬다. 이 문서에서는 병렬 프로그램이 특정 트래픽 패턴을 따르는 하나 이상의 집단 통신을 실행한다고 가정합니다. 적절한 노드 매핑은 높은 통신 성능을 달성합니다. 본 논문에서는 노드 매핑 문제를 해결하기 위한 강력한 휴리스틱 방법을 제안하고 이 방법을 유전 알고리즘에 적용합니다. 평가 결과는 제안된 방법이 상당히 높은 성능을 달성한다는 것을 보여주었다. 8.9×4.9 토러스 네트워크의 단일(32) 트래픽 패턴 사례에서 평균 32(XNUMX)배의 속도 향상을 달성합니다. 특히, 소규모 네트워크의 일부 트래픽 패턴에 대해 제안된 방법은 이론적으로 최적화된 솔루션을 찾습니다. 또한, 본 논문에서는 유전자 알고리즘을 적용한 제안 방법의 유전자 집단, 세대 수, 트래픽 패턴 등 다양한 문제에 대해 심도 있게 논의한다. 또한 이 문서에서는 향후 실제 사용을 위한 대규모 시스템에 대한 적용 가능성에 대해서도 논의합니다.
Takashi YOKOTA
Utsunomiya University
Kanemitsu OOTSU
Utsunomiya University
Takeshi OHKAWA
Utsunomiya University
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.
부
Takashi YOKOTA, Kanemitsu OOTSU, Takeshi OHKAWA, "Genetic Node-Mapping Methods for Rapid Collective Communications" in IEICE TRANSACTIONS on Information,
vol. E103-D, no. 1, pp. 111-129, January 2020, doi: 10.1587/transinf.2018EDP7386.
Abstract: Inter-node communication is essential in parallel computation. The performance of parallel processing depends on the efficiencies in both computation and communication, thus, the communication cost is not negligible. A parallel application program involves a logical communication structure that is determined by the interchange of data between computation nodes. Sometimes the logical communication structure mismatches to that in a real parallel machine. This mismatch results in large communication costs. This paper addresses the node-mapping problem that rearranges logical position of node so that the degree of mismatch is decreased. This paper assumes that parallel programs execute one or more collective communications that follow specific traffic patterns. An appropriate node-mapping achieves high communication performance. This paper proposes a strong heuristic method for solving the node-mapping problem and adapts the method to a genetic algorithm. Evaluation results reveal that the proposed method achieves considerably high performance; it achieves 8.9 (4.9) times speed-up on average in single-(two-)traffic-pattern cases in 32×32 torus networks. Specifically, for some traffic patterns in small-scale networks, the proposed method finds theoretically optimized solutions. Furthermore, this paper discusses in deep about various issues in the proposed method that employs genetic algorithm, such as population of genes, number of generations, and traffic patterns. This paper also discusses applicability to large-scale systems for future practical use.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2018EDP7386/_p
부
@ARTICLE{e103-d_1_111,
author={Takashi YOKOTA, Kanemitsu OOTSU, Takeshi OHKAWA, },
journal={IEICE TRANSACTIONS on Information},
title={Genetic Node-Mapping Methods for Rapid Collective Communications},
year={2020},
volume={E103-D},
number={1},
pages={111-129},
abstract={Inter-node communication is essential in parallel computation. The performance of parallel processing depends on the efficiencies in both computation and communication, thus, the communication cost is not negligible. A parallel application program involves a logical communication structure that is determined by the interchange of data between computation nodes. Sometimes the logical communication structure mismatches to that in a real parallel machine. This mismatch results in large communication costs. This paper addresses the node-mapping problem that rearranges logical position of node so that the degree of mismatch is decreased. This paper assumes that parallel programs execute one or more collective communications that follow specific traffic patterns. An appropriate node-mapping achieves high communication performance. This paper proposes a strong heuristic method for solving the node-mapping problem and adapts the method to a genetic algorithm. Evaluation results reveal that the proposed method achieves considerably high performance; it achieves 8.9 (4.9) times speed-up on average in single-(two-)traffic-pattern cases in 32×32 torus networks. Specifically, for some traffic patterns in small-scale networks, the proposed method finds theoretically optimized solutions. Furthermore, this paper discusses in deep about various issues in the proposed method that employs genetic algorithm, such as population of genes, number of generations, and traffic patterns. This paper also discusses applicability to large-scale systems for future practical use.},
keywords={},
doi={10.1587/transinf.2018EDP7386},
ISSN={1745-1361},
month={January},}
부
TY - JOUR
TI - Genetic Node-Mapping Methods for Rapid Collective Communications
T2 - IEICE TRANSACTIONS on Information
SP - 111
EP - 129
AU - Takashi YOKOTA
AU - Kanemitsu OOTSU
AU - Takeshi OHKAWA
PY - 2020
DO - 10.1587/transinf.2018EDP7386
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E103-D
IS - 1
JA - IEICE TRANSACTIONS on Information
Y1 - January 2020
AB - Inter-node communication is essential in parallel computation. The performance of parallel processing depends on the efficiencies in both computation and communication, thus, the communication cost is not negligible. A parallel application program involves a logical communication structure that is determined by the interchange of data between computation nodes. Sometimes the logical communication structure mismatches to that in a real parallel machine. This mismatch results in large communication costs. This paper addresses the node-mapping problem that rearranges logical position of node so that the degree of mismatch is decreased. This paper assumes that parallel programs execute one or more collective communications that follow specific traffic patterns. An appropriate node-mapping achieves high communication performance. This paper proposes a strong heuristic method for solving the node-mapping problem and adapts the method to a genetic algorithm. Evaluation results reveal that the proposed method achieves considerably high performance; it achieves 8.9 (4.9) times speed-up on average in single-(two-)traffic-pattern cases in 32×32 torus networks. Specifically, for some traffic patterns in small-scale networks, the proposed method finds theoretically optimized solutions. Furthermore, this paper discusses in deep about various issues in the proposed method that employs genetic algorithm, such as population of genes, number of generations, and traffic patterns. This paper also discusses applicability to large-scale systems for future practical use.
ER -