Routing direction determination in regular networks based on configurable circuits

Abstract

We consider the problem of finding short paths in a regular network such as a k-ary n-cube. This problem is a basic aspect of routing and has to be implemented with a very high performance for cluster and parallel computer networks. To achieve this, a scalable reconfigurable circuit is proposed that covers many popular topologies at acceptable cost. As a demonstration, the application to a modestly complex topology is shown in detail ("Multi-Mesh" introduced by Das et al. [D. Das, M. De, B.P. Sinha, A network topology with multiple meshes, IEEE Transactions on Computers 48 (5) (1999) 536-551]). The achieved flexibility is much higher than that of previously reported reconfigurable circuits for the same purpose such as interval routing [R.B. Tan, J. van Leeuwen, Compact routing methods: a survey, in: Proceedings of the Colloquium on Structural Information and Communication Complexity (SICC94), School of Computer Science, Carleton University, Ottawa, 1995, pp. 99-109] or bit-pattern-associative routing [D.H. Summerville, J.G. Delgado-Frias, S. Vassiliadis, A flexible bit-pattern-associative router for interconnection networks, IEEE Transactions on Parallel and Distributed Systems 7 (5) (1996) 477-485]. The proposed circuit extends the domain of application-specific reconfigurable circuits beyond the areas of signal processing and cryptography, where most work is currently done. © 2004 Elsevier B.V. All rights reserved.