Accelerating Large-Scale Interconnection Network Simulation by Cellular Automata Concept

Takashi YOKOTA; Kanemitsu OOTSU; Takeshi OHKAWA

doi:10.1587/transinf.2018EDP7131

Accelerating Large-Scale Interconnection Network Simulation by Cellular Automata Concept

Takashi YOKOTA, Kanemitsu OOTSU, Takeshi OHKAWA

Full Text Views

0

Cite this

Summary :

State-of-the-art parallel systems employ a huge number of computing nodes that are connected by an interconnection network. An interconnection network (ICN) plays an important role in a parallel system, since it is responsible to communication capability. In general, an ICN shows non-linear phenomena in its communication performance, most of them are caused by congestion. Thus, designing a large-scale parallel system requires sufficient discussions through repetitive simulation runs. This causes another problem in simulating large-scale systems within a reasonable cost. This paper shows a promising solution by introducing the cellular automata concept, which is originated in our prior work. Assuming 2D-torus topologies for simplification of discussion, this paper discusses fundamental design of router functions in terms of cellular automata, data structure of packets, alternative modeling of a router function, and miscellaneous optimization. The proposed models have a good affinity to GPGPU technology and, as representative speed-up results, the GPU-based simulator accelerates simulation upto about 1264 times from sequential execution on a single CPU. Furthermore, since the proposed models are applicable in the shared memory model, multithread implementation of the proposed methods achieve about 162 times speed-ups at the maximum.

Publication: IEICE TRANSACTIONS on Information Vol.E102-D No.1 pp.52-74

Publication Date: 2019/01/01

Publicized: 2018/10/05

Online ISSN: 1745-1361

DOI: 10.1587/transinf.2018EDP7131

Type of Manuscript: PAPER

Category: Computer System

Authors

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

Keyword

interconnection networks, simulation, GPGPU, multithreading

Cite this

Copy

Takashi YOKOTA, Kanemitsu OOTSU, Takeshi OHKAWA, "Accelerating Large-Scale Interconnection Network Simulation by Cellular Automata Concept" in IEICE TRANSACTIONS on Information, vol. E102-D, no. 1, pp. 52-74, January 2019, doi: 10.1587/transinf.2018EDP7131.
Abstract: State-of-the-art parallel systems employ a huge number of computing nodes that are connected by an interconnection network. An interconnection network (ICN) plays an important role in a parallel system, since it is responsible to communication capability. In general, an ICN shows non-linear phenomena in its communication performance, most of them are caused by congestion. Thus, designing a large-scale parallel system requires sufficient discussions through repetitive simulation runs. This causes another problem in simulating large-scale systems within a reasonable cost. This paper shows a promising solution by introducing the cellular automata concept, which is originated in our prior work. Assuming 2D-torus topologies for simplification of discussion, this paper discusses fundamental design of router functions in terms of cellular automata, data structure of packets, alternative modeling of a router function, and miscellaneous optimization. The proposed models have a good affinity to GPGPU technology and, as representative speed-up results, the GPU-based simulator accelerates simulation upto about 1264 times from sequential execution on a single CPU. Furthermore, since the proposed models are applicable in the shared memory model, multithread implementation of the proposed methods achieve about 162 times speed-ups at the maximum.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2018EDP7131/_p

Copy

@ARTICLE{e102-d_1_52,
author={Takashi YOKOTA, Kanemitsu OOTSU, Takeshi OHKAWA, },
journal={IEICE TRANSACTIONS on Information},
title={Accelerating Large-Scale Interconnection Network Simulation by Cellular Automata Concept},
year={2019},
volume={E102-D},
number={1},
pages={52-74},
abstract={State-of-the-art parallel systems employ a huge number of computing nodes that are connected by an interconnection network. An interconnection network (ICN) plays an important role in a parallel system, since it is responsible to communication capability. In general, an ICN shows non-linear phenomena in its communication performance, most of them are caused by congestion. Thus, designing a large-scale parallel system requires sufficient discussions through repetitive simulation runs. This causes another problem in simulating large-scale systems within a reasonable cost. This paper shows a promising solution by introducing the cellular automata concept, which is originated in our prior work. Assuming 2D-torus topologies for simplification of discussion, this paper discusses fundamental design of router functions in terms of cellular automata, data structure of packets, alternative modeling of a router function, and miscellaneous optimization. The proposed models have a good affinity to GPGPU technology and, as representative speed-up results, the GPU-based simulator accelerates simulation upto about 1264 times from sequential execution on a single CPU. Furthermore, since the proposed models are applicable in the shared memory model, multithread implementation of the proposed methods achieve about 162 times speed-ups at the maximum.},
keywords={},
doi={10.1587/transinf.2018EDP7131},
ISSN={1745-1361},
month={January},}

Copy

TY - JOUR
TI - Accelerating Large-Scale Interconnection Network Simulation by Cellular Automata Concept
T2 - IEICE TRANSACTIONS on Information
SP - 52
EP - 74
AU - Takashi YOKOTA
AU - Kanemitsu OOTSU
AU - Takeshi OHKAWA
PY - 2019
DO - 10.1587/transinf.2018EDP7131
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E102-D
IS - 1
JA - IEICE TRANSACTIONS on Information
Y1 - January 2019
AB - State-of-the-art parallel systems employ a huge number of computing nodes that are connected by an interconnection network. An interconnection network (ICN) plays an important role in a parallel system, since it is responsible to communication capability. In general, an ICN shows non-linear phenomena in its communication performance, most of them are caused by congestion. Thus, designing a large-scale parallel system requires sufficient discussions through repetitive simulation runs. This causes another problem in simulating large-scale systems within a reasonable cost. This paper shows a promising solution by introducing the cellular automata concept, which is originated in our prior work. Assuming 2D-torus topologies for simplification of discussion, this paper discusses fundamental design of router functions in terms of cellular automata, data structure of packets, alternative modeling of a router function, and miscellaneous optimization. The proposed models have a good affinity to GPGPU technology and, as representative speed-up results, the GPU-based simulator accelerates simulation upto about 1264 times from sequential execution on a single CPU. Furthermore, since the proposed models are applicable in the shared memory model, multithread implementation of the proposed methods achieve about 162 times speed-ups at the maximum.
ER -