The search functionality is under construction.
The search functionality is under construction.

Genetic Node-Mapping Methods for Rapid Collective Communications

Takashi YOKOTA, Kanemitsu OOTSU, Takeshi OHKAWA

  • Full Text Views

    0

  • Cite this

Summary :

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.

Publication
IEICE TRANSACTIONS on Information Vol.E103-D No.1 pp.111-129
Publication Date
2020/01/01
Publicized
2019/10/10
Online ISSN
1745-1361
DOI
10.1587/transinf.2018EDP7386
Type of Manuscript
PAPER
Category
Computer System

Authors

Takashi YOKOTA
  Utsunomiya University
Kanemitsu OOTSU
  Utsunomiya University
Takeshi OHKAWA
  Utsunomiya University

Keyword