In: Performance Evaluation 47 (2-3), pages 105-129. February 2002.
Abstract: The analysis, design and evaluation of the interconnection subsystem for massively parallel architectures is normally carried out using computer simulation tools, requiring elevated computational costs. Moreover, in some cases, these simulation processes show serious difficulties when both experiments and results have to be reproduced by other research or design teams. This work shows the suitability of the use of formal representation methods, like DSPN (stochastic Petri nets with deterministic and exponential firing times), for the description of the message routers, focusing on two important features. Firstly, the possibility of obtaining network performance indicators through the simulation of the obtained models with a lower computational cost than using conventional techniques; in some cases, analytical results can also be obtained. And secondly, making the basic parameters of the network design relatively independent of the router implementation features, thus simplifying the method of establishing the behavior of new router structures. This approach has been successfully applied to the analysis of both symmetrical torus and asymmetrical mesh interconnection topologies, with virtual cut-through flow control, oblivious routing and random traffic. It should be noted that most modern parallel computers employ a local buffer space big enough to store at least a complete packet. Two different functional router structures have been used in each case: transit buffers located at the input or at the output router links.
Keywords: Interconnection subsystem; Massively parallel computers; Stochastic Petri nets; Hardware message router; Performance evaluation; Simulation.