A finite automata approach to modeling the cross product of interconnection networks

This paper describes a modeling technique, finite state automata (FA) model, for the cross product of interconnection networks. The primary purpose of the proposed modeling technique is to provide a mechanism for developing efficient routing and novel embedding algorithms, which we refer to as node-independent algorithms, for product networks. In contrast to the current embedding algorithms which are node dependent (their output is a set of adjacent node labels which forms the desired topology), the embedding algorithms developed in this paper are rule-based. That is, they generate a set of rules (input sequences to the FA model of the network) which can be used by any node for mapping a desired topology into the network. Furthermore, a new interconnection topology, called Ring Connected Cycles (RCC), is introduced. The main objective of introducing RCC networks is to illustrate the use of the FA model to develop node-independent embedding as well as routing algorithms. In addition, to demonstrate the generality of the proposed technique, FA models of several popular interconnection networks (such as n-cubes and la-star graphs) are presented. The RCC networks are proposed in this paper as a possible communication network for parallel multicomputers or as an alternative to the ring topology for local area networks. An RCC network can execute grid, mesh and ring algorithms as efficiently as the grid, mesh, and ring networks. It is shown in Section 6 that this significant amount of computational versatility offered by RCC networks comes at no additional VLSI area cost over the same size ring, grid, or mesh networks. (C) 1999 Elsevier Science Ltd. All rights reserved.