Accelerating Large-Scale Interconnection Network Simulation by Cellular Automata Concept

Takashi YOKOTA  Kanemitsu OOTSU  Takeshi OHKAWA  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E102-D   No.1   pp.52-74
Publication Date: 2019/01/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2018EDP7131
Type of Manuscript: PAPER
Category: Computer System
Keyword: 
interconnection networks,  simulation,  GPGPU,  multithreading,  

Full Text: PDF(3.5MB)>>
Buy this Article



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.