An Analytical Model of Multistage Interconnection Networks Darryl L. Willick Derek L. Eager Department of Computational Science University of Saskatchewan ABSTRACT Multiprocessors require an interconnection network to connect processors with memory modules. The performance of the interconnection network can have a large effect upon overall system performance, and, therefore, methods are needed to model and compare alternative network architectures. This paper is concerned with evaluating the performance of multistage interconnection networks consisting of k X s switching elements. Examples of such networks include omega, binary n- cube and baseline networks. We consider clocked, packet switched networks with buffers at switch output ports. An analytical model based on approximate Mean Value Analysis is developed, then validated through simulations. 1. Introduction As the need for computational power has grown, multiprocessor systems have become a promising means of providing high performance at reasonable cost. A common architecture for these systems consists of a number N of processors and memory modules connected via some form of interconnection network. There is a very wide range of interconnection networks that have been proposed. On the one extreme is the crossbar interconnection, where N connections can be made simultaneously but where the number of switches and therefore cost rises as the square of N. At the other extreme is the single global bus which is very inexpensive but does not allow scaling of systems to large sizes. Between these two extremes there are a number of possibilities including meshes, hypercubes and multistage networks [4]. This paper concerns multistage interconnection networks. These networks have received considerable attention and several classes of multistage networks have been proposed and investigated in the literature [1, 6, 111. Several machines have been designed using this type of interconnection network including the NYU Ultracomputer [7], the IBM RP3 [15], the BBN Butterfly [17], and the Illinois Cedar system [5]. * This material is based upon work supported by the Nattml Sciatccs and Engineering Rcscarch Council of Canada. Authors’ cup~lt address: Department of Cmpuwional Science, University of Saskatchewan, Saskatoon, Saskatchewan, Canada, S7N OWO. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission. 0 1990 ACM 089791-359-O/90/0005/0192 $1.50 Multistage interconnection networks connect processors (PEs) to memory modules through stages of switches. The switches are k-input, s-output (k x s) devices which can route data arriving on any input port to any output port. Fig. 1 shows an example multistage interconnection network, termed an omega network [ 111, constructed from 2 x 2 switches. An omega network consisting of k x k switches corrects N processors to N memory modules through log, N stages with N/k switches in each stage. The routing of memory requests and replies through multistage interconnection networks is a distributed process. Each network switch can route an incoming request/reply to the appropriate output port by examining a single digit of the destination address, as specified in base k. Fig. 1. 3 stage, 2 x 2 omega network. Multistage networks may employ either circuit-switching, packet-switching or some hybrid strategy (such as virtual cut- through). With circuit switching, a circuit must be established between a processor and memory before data can be transferred. With packet-switching, packets of fixed size are transferred in a store-and-forward fashion through the stages of the network. Packet-switching networks may be either synchronous, in which case switches transfer packets only at times defined by discrete clock cycles, or asynchronous, in which case packet transfers may occur at arbitrary points in time. When two or more packets on different switch inputs concurrently require the same output port, a “conflict” is said to occur. There are two main approaches to handling such conflicts. The first is to simply discard all but one of the conflicting packets. The second approach is to supply buffers at switches so that packets will only be delayed rather than lost. In this paper, we are only interested in those multistage interconnection networks that are synchronous (clocked) packet- switching networks, and that utilize buffers to resolve conflicts. There have been a considerable number of studies investigating the performance of multistage interconnection networks (see [2, 3, 8. 9, 10, 13, 141, among others). These studies have employed both analytical and simulation models. 192Of major importance in the analytical modeling of clocked, buffered packet-switched networks has been the work of Kruskal and Snir [9], whose analytical model of interconnection network performance has seen use in &sign studies of the IBM RP3 [15] and the NYU Ultracomputer [7]. In this paper, we develop an analytical model for clocked, buffered, packet-switched multistage interconnection networks that is based on queueing network models (QNM) and approximate Mean Value Analysis [12]. Our goal is to increase the range of applicability of analytical models in systems &sign. Previous models, although very useful, typically rely on a number of simplifying assumptions, including those of constant memory request generation rates at the network input ports (i.e., wholely nonblocking processors), and uniform memory reference patterns. (If non-uniform patterns are permitted,