Time-Driven Parallel Simulation of Multistage Interconnection Networks
Qing Yu, Don Towsley, Philip Heidelberger · 1988
MULTISTAGE INTERCONNECTION NETWORKS (MINS), AN IMPORTANT CLASS OF NET- WORKS ARISING IN HIGHLY PARALLEL COMPUTER SYSTEMS, ARE EXCELLEND CANDIDATES FOR PARALLEL TIME-DRIVEN SIMULATIONS ON SHARED MEMORY COMPUTER BECAUSE: 1) THEY ARE NATURALLY DISCRETE TIME SYSTEMS, 2) THEY (AND HENCE THEIR MODELS) ARE INHERENTLY PARALLEL AND MANY PACKETS ARE PROCESSED IN PARALLEL, AND 3) IT IS POSSIBLE TO EXPLOIT THEIR TOPOLOGICAL REGULARITY. IN THIS PAPER WE REPORT RESULTS ON THE PERFORMANCE OF SUCH SIMULATIONS ON AN 8 PROCESSOR SEQUENT SYMMETRY SYSTEM. WE SIMULATE BOTH INFINITE BUFFER AND FINITE BUFFER MINS. IN THE FORMER CASE WE CONSIDER SEVERAL MECHANISMS TO SYNCHRONIZE THE PROCESSORS AND FIND THAT A SIMPLE MULTIBARRIER MECHANISM THAT REQUIRES ALL PROCESSORS TO SYNCHRONIZE AFTER SIMULATING EACH MIN STAGE PROVIDES THE BEST PERFORMANCE. WE OBSERVE THAT TRAFFIC LOAD HAS LITTLE EFFECT ON SPEEDUP. ON THE OTHER HAND THE SIZE OF THE MIN BEING SIMULATED HAS A SIGNIFICANT EFFECT ON SPEEDUP. SPEEDUPS TYPICALLY RANGE FROM 4 WHEN THE MIN HAS 4 STAGES TO JUST OVER 7 WHEN THE MIN HAS 9 STAGES.