An empirical performance analysis of minimal and non-minimal routing in cube-based OTIS multicomputers

Article type: Research Article

Authors: Najaf-abadi, Hashem Hashemi | Sarbazi-Azad, Hamid^;

Affiliations: IPM School of Computer Science, Tehran, Iran | Sharif University of Technology, Tehran, Iran E-mail: azad@{ipm.ir, sharif.edu}

Abstract: In this study, the performance of virtual cut-through switching in the cube-based OTIS architecture, an optoelectronic interconnection architecture for multicomputer systems, is empirically analyzed. Deadlock-free deterministic and adaptive minimal path routing algorithms for this architecture are introduced, and the effects of different network and traffic parameters on average message latency are investigated. This analysis presents a relatively more realistic view of the OTIS architecture than that presented in previous work by considering issues related to a lower level of abstraction (the routing and switching of messages). Among other results, the analysis indicates that depending on the traffic pattern, minimal path routing in these architectures may cause extreme congestion to occur over certain channels of the network, resulting in severe performance degradation. Alternative non-minimal path routing schemes are therefore suggested and their performance compared. One of the non-minimal approaches suggested is found to be able to sustain at least half the maximum possible bandwidth under all studied traffic patterns. Yet determining a single routing algorithm that is capable of attaining the highest possible throughput for all different traffic patterns remains an open problem. A constraint-based analysis of the effect of dimensionality on performance is also conducted.

Keywords: Multicomputers, interconnection network, optoelectronic interconnection, OTIS-hypercube, hypercube, performance analysis, simulation

Journal: Journal of High Speed Networks, vol. 16, no. 2, pp. 133-155, 2007