Performance of Multistage Bus Networks for a Distributed Shared Memory Multiprocessor.
AbstractA Multistage Bus Network (MBN) is proposed in this paper to overcome some of the shortcomings of the conventional multistage interconnection networks (MINs), single bus, and hierarchical bus interconnection networks. The MBN consists of multiple stages of buses connected in a manner similar to the MINs and has the same bandwidth at each stage. A switch in an MBN is similar to that in a MIN switch except that there is a single bus connection instead of a crossbar. MBNs support bidirectional routing and there exists a number of paths between any source and destination pair. In this paper, we develop self routing techniques for the various paths, present an algorithm to route a request along the path with minimum distance, and analyze the probabilities of a packet taking different routes. Further, we derive a performance analysis of a synchronous packet-switched MBN in a distributed shared memory environment and compare the results with those of an equivalent bidirectional MIN (BMIN). Finally, we present the execution time of various applications on the MBN and the BMIN through an execution-driven simulation. We show that the MBN provides similar performance to a BMIN while offering simplicity in hardware and more fault-tolerance than a conventional MIN.
Introduction
In order to achieve significant performance in parallel computing it is necessary to keep the communication
overhead as low as possible. The communication overheads of a multiprocessor system depend
to a great extent on the underlying interconnection network. An interconnection network (IN) can be
either static or dynamic. Dynamic networks can connect any input to any output by enabling some
switches. They are applicable to both shared memory and message passing multiprocessors. Among
such dynamic INs, the hierarchical buses or rings [1], [2] and Multistage Interconnection Networks
(MINs) [3], [4] have been commercially employed.
In a strictly hierarchical bus architecture [1], there are a number of buses connected in the form of
a tree between the processors and the memories. The use of multiple buses makes the hierarchical
bus-based systems more scalable compared to the popular single bus multiprocessors. However, the
bandwidth of this interconnection decreases as one moves toward the top of the tree. Thus, the
scalability of a hierarchical bus system becomes limited by the bandwidth of the topmost level bus.
The bandwidth problem can be alleviated through the fat tree design [5]. The simplicity of the bus
based designs and the availability of a fast broadcasting mechanism are factors that make bus-based
systems very attractive.
The MINs, on the other hand, offer a uniform bandwidth across all stages of the network. The
bandwidth of the network increases in proportion to the increase in system size, making the MIN
a highly scalable interconnection. The switches in a MIN are made up of small crossbar switches.
When the system size grows, bigger switches can be used to keep the number of stages and, hence, the
memory latency low [6]. However, the complexity of a crossbar switch grows as the square of its size,
and therefore, the total network cost becomes predominant in larger systems. We have observed that
the traffic in the network is very low making the crossbar based MIN switches highly underutilized.
In a system using private caches, which is common in today's shared memory multiprocessors, the
effective traffic handled by the switches in the network is further reduced.
A novel interconnection scheme, called the Multistage Bus Network (MBN), is introduced in this
paper that combines the positive features of hierarchical buses and MINs. The MBN consists of several
stages of buses with equal number of buses at each stage. This provides a uniform bandwidth across the
stages and forms multiple trees between processors and memories. Unlike hierarchical bus networks,
the MBNs comprise multiple buses at higher levels reducing the traffic at higher levels. Maintaining
cache coherence is a major problem in shared memory multiprocessors. Unlike MINs, the snoopy cache
coherence protocols can be applied to the MBN [7], which can improve the performance by a large
extent. Also, the MBN provides much better fault tolerance and reliability compared to a conventional
MIN [8].
It is known that a distributed shared memory organization has better scalability than a centralized
organization [2], [3]. In such an organization, a request or response packet can make U-turns in the
network and reach a destination quickly since the intermediate levels of an MBN consist of buses
and bidirectional connections. Four different routing techniques [8] are presented here in this paper.
We also develop equations for probabilities of taking each path based on the memory requests. In
order to do a realistic comparison with MINs, we introduce the design and analysis of a corresponding
Bidirectional MIN (BMIN) in this paper. The BMIN allows U-turns and a packet can be routed based
on the same techniques presented in this paper for the MBN. Recently, Xu and Ni [9] have discussed
a U-turn strategy for bidirectional MINs as applicable to the IBM SP architecture [4]. However, the
MIN employed in SP architectures is cluster-based and works differently than the proposed MBN or
BMIN.
In this paper, we analyze the performance of an MBN for distributed shared memory multiprocessors
based on different self routing techniques. Unlike the previous analysis [8], the present analysis is based
on routing along the minimum of the four paths for a given source and destination pair. The MBN has
some inherent fault tolerance capabilities due to a number of switch disjoint paths between any source
and destination pair. In this paper, we only concentrate on the routing and performance evaluation
IN
Router
Fig. 1. A distributed shared memory multiprocessor
using queueing analysis and execution-driven simulations of various applications. Our execution-driven
simulator is an extended version of Proteus [10] that simulates the behavior of a cache coherent
distributed shared memory multiprocessor for various applications.
The rest of the paper is organized as follows. We present the structure and introduce four types of
self routing techniques for the MBN in Section 2. We define the routing tags required to implement the
four routing strategies in Section 3 and present an algorithm for the most optimal path in the network
for a given source-destination pair in the same section. A performance analysis of the MBN and
BMIN is then presented in Section 4. Results and comparison with the conventional and bidirectional
MINs are presented in Section 5. Section 6 presents the execution-driven simulation specifications and
results. Finally Section 7 concludes the paper.
II. Structure of the MBN
We will consider a distributed shared memory (DSM) architecture throughout this paper. In such an
environment, the memory modules are directly connected to the corresponding processors, as shown
in

Figure

1, but the address space is shared. An example of hierarchical bus interconnection with two
levels of buses is shown in Figure 2a [1]. In this example, there are 16 processors, 4 memories, four
level 1 buses and one level 2 bus. Naturally, the top level bus is the bottleneck in the system. In order
to improve the performance, a number of buses must be connected at the top level with interleaved
memory design. Such a connection is shown in Figure 2b for a 16*16 system with two levels of buses.
M: MEMORY, P: PROCESSOR
(a) A 16 Processor Hierarchial Bus System
(b) A 16*16 MBN Based System using 4*4 switches
M: MEMORY, P: PROCESSOR LEVEL 1 BUS
Fig. 2. Hierarchical Bus Interconnection and the MBN
We propose that each bus along with its controller be placed in a switch analogous to a MIN switch.
Such a network is called a Multistage Bus Network (MBN).
In an N   N multistage network using k   k switches, there are l = log k N stages of switches, numbered
from stage 0 to stage l \Gamma 1, as shown in Fig. 3a. Every switch has a set of left connections closer to
the processor side and a set of right connections closer to the memory side. The construction of a 4*4
MBN switch incorporating a bus, a bus access controller and output buffers is shown in Figure 3b.
There are control lines associated with each port to carry arbitration information to the bus access
controller. Suzuki et al. have studied a similar bus structure in [11]. We also propose a Bidirectional
MIN (BMIN) structure for comparison. The difference between the switch architectures of BMIN and
MBN is evident from Figs. 3b and c. The BMIN switch is a crossbar whereas the MBN switch is a
bus. For both the networks, a packet from a stage i is passed on to the stage vice versa, using
the destination tag digits. For a k   k MBN switch there will be 2k packets (k inputs from either side)
potentially competing for the bus in a cycle. When there is more than one such packet, the bus access
controller chooses any one of them at random. Others are queued to be transmitted later. On the
other hand, in a k   k BMIN switch all the 2k inputs can be connected to the 2k outputs if the requests
are to different destinations. The k   k MBN and BMIN switches support forward, backward, turn
BUFFER
Stage
CONTROL LINES
(a) A 16*16 Multistage Network
CONTROLLER
BUS
ACCESS
BUS
LINES
LINES
CONTROL
OUTPUT
INPUT
OUTPUT
INPUT
OUTPUT
INPUT
LINES
(b) 4*4 MBN switch architecture
CROSSBAR
CONTROLLER
(c) 4*4 BMIN switch architecture
Fig. 3. Comparing Switch Architectures
around connections, as explained in the next section. We describe the structure of the MBN below.
The structure of the BMIN is similar.
The processors P are connected to the left connections of the MBN switches at stage
are connected to the right connections at stage l \Gamma 1. Memory
module M i is also directly connected to processor P i and is called the local memory of P i . A source is
assigned a tag a destination is assigned a destination tag
are digits in the k \Gamma ary system. The digits s 0 and d 0 are the most significant and s
and d l\Gamma1 are the least significant digits. The connection between stages in the MBN is a k-shuffle [6]
which means the right connection at position a 0 a 1 :::a l\Gamma1 of stage i is connected to the left connection
at position a 1 :::a l\Gamma1 a 0 of stage 2. A memory request is satisfied internally by
the local memory when the source tag and the destination tag of a request are the same, If the tags
are different, the request travels to a remote memory through the MBN.
As an example, a 16*16 MBN with 2*2 switches is shown in Figure 4. There may or may not be a
shuffle interconnection before the first stage of switches. Our routings are developed based on Figure 4
where there is no shuffle before the 1st stage. Hence, a set of processors with their memories are
connected to one switch at the first stage and to another switch at the same position at the last stage.
If there exists a k-shuffle connection before the first stage a different set of processors will be connected
to the first stage and last stage switches. In Figure 4, a request travels in the forward direction when
it starts from the processor side and passes through stages 0; 1:::(l \Gamma 1), in that order. It travels in the
backward direction when it starts from the memory side and passes in the reverse direction through
stages (l \Gamma 1):::1; 0, as shown in Figure 5. A packet can also travel from left to right and make a U-turn
in an intermediate stage, as shown in Figure 6. This is called routing. Similarly

Figure

7 shows Backward \Gamma U(BU) routing where a message enters the network from the right and
makes a U-turn. These four routings provide four distinct paths between a source and a destination
in the MBN. As a result, the fault tolerance and reliability of the MBN are much better than that of
a conventional MIN. Exact expressions for the MBN reliability are derived in [8]. They are also valid
for BMINs introduced in this paper.
In conventional MINs like the Omega, Delta and GSN [6], the destination tag is used for the purpose
of self routing of a request only in the forward direction. In case of the MBN, the destination tag can
also be used for self routing in the forward direction. Since the stage 0 connections are straight instead
of a k-shuffle, the destination tag itself can not be used for self routing in the backward direction.
As explained later, the routing tag in the backward routing case is obtained by reverse shuffling the
destination tag by one digit. In order to determine where to take a turn in the above two routing
techniques involving U-turns, we need to combine the source tag and the destination tag to form a
combined tag. The following definitions are needed to develop exact routing algorithms later.
The Forward Routing Tag (FRT) is the same as the destination tag of a memory
request, i.e.,
(BRT) The Backward Routing Tag (BRT) is the destination tag reverse shuffled by one
digit. If d 0 d 1 :::d l\Gamma1 is the destination, then BRT b 0 b 1 :::b (j \Gamma1)mod(l) .
Definition 3 (CT) The Combined Tag (CT) is the digit-wise exclusive-or of the source tag and the
destination tag i.e.,
. The operation
J means c
. Note that although the digits in S and D are k \Gamma ary, the digits in the
CT are binary.
Definition 4 (RCT) The Rotated Combined Tag (RCT) is the Combined Tag (CT) reverse shuffled
or right rotated by one digit, i.e., RCT r 0 r (j \Gamma1)mod(l) .
Definition 5 (FTS) The Forward Turning Stage (FTS) is defined as the rightmost nonzero position in
the Rotated Combined Tag(RCT). That is, m, such that r
Definition 6 (BTS) The Backward Turning Stage (BTS) is defined as the leftmost nonzero position
in the Combined Tag (CT). That is,
The routing tags FRT and BRT are used for self routing in case of the forward and backward
directions respectively. The tags RCT and CT are used to find the U-turn stages FTS and BTS
respectively. The U-turn stages FTS and BTS are used to determine where to take forward and
backward turns during U-turn routings. The various routing schemes possible in an MBN are described
below.
III. Routing Algorithms for MBN
In this section, we first present the four routing techniques for the MBN and then present an algorithm
that chooses the path with minimum distance. Although these techniques are described for the MBN,
they are equally valid for the BMIN.
A. Routing Techniques
A. Forward Routing : In Forward (FW) routing, a request from source processor S moves
from stage 0 through stage l \Gamma 1 through the MBN to the destination memory D. An example of FW
routing for source 0011 to destination 1011 is shown in bold line in Figure 4. The jth digit of the
forward routing tag (FRT) is used by a switch at stage j for self-routing. Thus, a request that started
Fig. 4. Forward (FW) routing in MBN
at position at the left of stage 0, is switched to position s 0 s 1 :::s j :::s l\Gamma2 d 0 at the right
of stage 0, then undergoes a k-shuffle and reaches at position s 1 s 2 :::s j :::s l\Gamma2 d 0 s 0 at the input of stage 1
and gets switched to s 1 s 2 :::s j :::s l\Gamma2 d 0 d 1 at the output of stage 1. In general, when a request arrives at
position at the left of stage j, it is switched to position s j :::s l\Gamma2 d 0 d 1
at the right of stage j, goes through a k-shuffle (except at the last stage, and arrives at
position s j+1 :::s l\Gamma2 d 0 d 1 :::d j s j at the left of stage j + 1. Finally it reaches the destination d 0 d 1 :::d j :::d
at the output of the last stage of the MBN.
B. Backward (BW) Routing : In Backward (BW) routing, a request from source node S moves
backward from stage l \Gamma 1 through stage 0 to the destination node D. An example of BW routing for
0011 to 1011 is shown using bold line in Figure 5. The jth digit of the backward routing tag (BRT) is
used by a switch at stage j for self-routing. Thus, a request that started at position
at the right of stage l \Gamma 1, is switched to position s 0 s 1 :::s j :::s l\Gamma2 d l\Gamma2 at the left of stage l \Gamma 1, then
undergoes a reverse k-shuffle and reaches at position d l\Gamma2 s 0 s 1 :::s j :::s l\Gamma2 at the right of stage l \Gamma 2.
In general, when a request arrives at position d j d j+1 :::d l\Gamma2 s at the right of stage j, it is
switched to position d j d j+1 :::d l\Gamma2 s (j \Gamma1)mod(l) (the jth digit of BRT, b at the
Fig. 5. Backward (BW) routing in MBN
left of stage j. Then it goes through a reverse shuffle (except at the last stage, and arrives at
position at the left of stage
C. Forward-U Routing : In Forward-U routing, the request starts from source S at stage
0, follows the FW routing (using FRT) up to stage FTS-1 and reaches at the left of stage FTS
at position s FTS s FTS+1 :::s l\Gamma2 d 0 d 1 :::d FTS \Gamma1 s FTS \Gamma1 . At FTS, it takes a U-turn, instead of getting
switched to the right of stage FTS. The request is switched to the left of stage FTS at position
routing (using BRT) up to stage 0. Finally
it reaches at position d 0 d 1 :::d FTS \Gamma1 s FTS :::s l\Gamma2 d l\Gamma1 at the left of stage 0. An example of FU routing
for 0010 to 0110 is shown in bold line in Figure 6.
D. Backward-U (BU) Routing : In Backward-U routing, the request starts from source S at
stage l \Gamma 1, follows the BW routing (using the BRT) up to stage BTS+1 and reaches at position
at the right of stage BTS. At stage BTS, it takes a U-turn, instead
of getting switched to the left of stage BTS. The request gets switched to the right of stage BTS at
position dBTS dBTS+1 :::d l\Gamma2 s routing(using FRT) up to stage l \Gamma 1.
Finally the request reaches at position s in the right of stage l \Gamma 1. An
Fig. 6. Forward-U (FU) routing in MBN
example of BU routing for 0010 to 0110 is shown in Figure 7.
B. Optimal Path Algorithm
The distance between a source and destination in an MBN is defined as the minimum number of
switches that the packet has to travel. For a conventional MIN, this distance is always equal to l, or
the number of stages in the network. In case of an MBN, however, the distance may be less than l if
FU or BU routing is chosen. The FU and BU (Forward-U and Backward-U) routings are used when
the turning stage happens to be less than the center stage of the network. Therefore, there will be
net savings in terms of distances between a given source and all the destinations. Detailed expressions
for the overall savings in distances for such an MBN are given in Section 4. We present below an
algorithm to choose the most optimal routing for a given source-destination pair.
Optimal Path Algorithm
1.
Stage
Fig. 7. Backward-U (BU) routing in MBN
2.
3.
4.
5. d l = bl=2c, d
7. THEN request is to local memory
8. ELSE
9. Find FTS and BTS (based on the tags RCT and CT respectively)
10. IF
11. THEN select forward-U (FU) routing OR backward-U (BU) routing
12. ELSE IF
13. THEN select forward-U (FU) routing
14. ELSE IF (BTS - d u
15. THEN select backward-U (BU) routing
16. ELSE
17. select forward (FW) routing OR backward (BW) routing
The optimal path algorithm chooses a route that has a minimum path length. Given a source
and a destination algorithm computes the tags described earlier
in this section. It then uses a comparison of these tags to decide which of the four routings would give
the minimum path length through the network. In the algorithm d is defined as the center stage of
the MBN. It must be pointed out here that the optimal routing between two nodes is fixed in a given
network. Hence the optimal path can be precomputed and stored in a table that can be read when a
request is issued. There is no need to execute the algorithm every time a message is sent out.
If the source and the destination are the same, then the request is for the local memory. In this case
no traversal through the MBN is required. All other requests pass through at least one stage of the
MBN. The memories that are connected to a processor through the first or last stage of the MBN are
called cluster memories. Similarly processors that are one switch away from the memories are called
cluster processors of those memories. Requests to cluster memories require that only one switch be
traversed. Thus when routing is taken to serve this purpose.
If this is not satisfied then we should check for FU or BU routing because these would be the next
possible minimum path. If FTS ! bl=2c or BTS - dl=2e we have turning stages in the MBN before
or after the center stage. This would reduce the total path length to less than l and thus FU or BU
routing is selected. If none of the above conditions is true, we have FTS - bl=2c and BTS ! dl=2e.
In this case, forward (FW) routing or backward (BW) routing are the only options. The actual path
lengths in terms of the number of switches traversed are presented below:
ffl Local memory: 0 switches (MBN is not traversed)
ffl Forward routing or Backward routing: l switches
Destination i FW/BW routing FU routing BU routing


I
The path lengths for each of the routings given source=0 and different destinations
ffl Forward-U routing:
1.
2. Other memories: 2 \Theta FTS
ffl Backward-U routing:
1.
2. Other memories: 2 \Theta (l
These path length equations can be used to form a table for a given source and destination. As
an example, Table 1 shows the path lengths from source 0 to different destinations in a 1024*1024
network for i - 1023. The path length for each routing is quite different and thus a routing algorithm
is required to route the request through the most optimal path. For example, if the destination is 2
then Backward-U routing will result in the optimal path length. On the other hand, if the destination
is 256, then Forward-U routing will result in the optimal path length. The other two requests should
use forward or backward routing strategies.
IV. Performance of the MBN
The Multistage Bus Network (MBN) is analyzed here in a distributed shared memory environment,
shown in Figure 1. We also analyze the BMIN and compare its results with those of the MBN. In
both the cases, the memory module M i is directly connected to the processor P i and is called the
local memory of P i . Requests from a processor to its local memory are called internal requests and are
carried over the internal bus between the processor and its local memory. A memory can also receive
external requests that originate from other processors and are carried over the MBN.
A. Network operation
In a distributed memory system, there are processors that can be reached through the switch
of size k at the first stage or the last stage to which P i is connected. Thus the external request
destined to a cluster processor or memory returns from the first stage (Forward-U routing) or last
stage (Backward-U routing) without going through the whole MBN. However, if the request is neither
to a local nor to a cluster memory, the request may take one of four routings described earlier. Both
internal and external requests arrive at a memory queue. Only one of them is selected for service on
an FCFS basis while the remaining requests are queued at the buffer of the memory. After receiving a
request, a memory module will send a reply packet either directly to its local processor or to another
processor through the network, depending on whether the request is internal or external.
We will compare the performance of the MBN with that of a BMIN. The transmission of request
and reply packets goes through the network following the routings given earlier in the paper. We shall
assume a synchronous and packet switched system for analyzing the multistage networks. Since a
buffer size of four or more gives the same effect as an infinite buffer [12], [13], for simplicity, we shall
assume an infinite buffer for MBN and BMIN. The analysis can be extended to finite buffers, but the
equations will be fairly complicated [13]. Since our aim here is to analyze the routing schemes, we
prefer to give the basic infinite buffer analysis. The bus service time (for MBN) or the link service
time (for BMIN) to transfer a message forms one system cycle time. The service times of the memory
modules are assumed to be integral multiples of this system cycle time. A processor is represented
by a delay center; in a given cycle, it submits a memory request with some given probability if it is
busy in computation. Once it sends the memory request, the processor becomes idle until the memory
response packet (in case of a read) or acknowledgment (in case of write) is obtained. The various
system parameters are defined below:
size of the MBN or MIN switches
number of processors or memories in the system
number of stages in the IN
probability that a processor submits a memory request in a given cycle provided it
is busy
probability that a processor requests its local memory provided it has made a
memory request
Probability that a request passes through stage i
of switch at stage i,
number of local requests by a processor per cycle
number of remote requests from a processor per cycle
delay in the network (considering all stages)
length in a memory module
delay in a memory module
utilization (fraction of time the processor is busy)
The performance analysis of the MBNs and BMINs will be carried out under the following assumptions
[12], [13]. Packets are generated at each source node by independent and identically distributed
random processes. At any point of time a processor is either busy doing some internal computations
or is waiting for the response to a memory request. If there is no pending request, each busy processor
generates a packet with probability p at each cycle. The probability that this request is to the local
memory (internal request) is m, and the probability to any other memory module (external request)
is
A reply from memory travels in the opposite direction through the same path in the MBN or BMIN. It
may be noted that in case of a MIN like Butterfly [3], a reply has to traverse in the same direction (i.e.,
from processor to memory side) to reach the requesting processor because the MIN has unidirectional
links. In [9], bidirectional links are used between stages and hence the requesting and reply messages
may travel in the forward and backward directions respectively.
The messages from processor to memory are generated using probabilities as specified below:
Request Probability (p): The request probability is defined in Section 3 and is used as a means
of estimating the processor behavior in terms of memory requests. When a processor is busy in
computation, i.e., no request is outstanding in switches or a memory module, it can send a memory
request. At each cycle, the processor decides whether or not a message is to be sent based on this
probability. On an average, it takes 1=p cycles to send out a request from the processor.
ffl Local memory request probability (m): Given that a request is to be made to memory, a probability
(m) is used to decide whether the request is for local or external memory.
Though simple, the above probabilities play an important role and are the only inputs to the analysis.
After each request to memory, the processor waits for an acknowledgment. Once an acknowledgment is
received, the processor does useful computation for one cycle and then based on the above probabilities
decides whether to continue or to send another request to the memory.
Processor utilization: The processor utilization, P u , defined as the fraction of time a processor is
busy, will be determined by the waiting time and service time faced by a request at various service
centers. In a number of applications, a large portion of the requests are made to the cluster processors.
In [8], we studied the performance of the MBN with varying probabilities for cluster requests. In the
study forward-U and backward-U routings were allowed only at the first and last stages. All other
requests were routed by forward (FW) routing. The processor utilization for such a case is given by
the following equation:
In this paper, a message in MBN or BMIN will be sent along the minimum distance. In such a case,
(2)
where,
ffl ff corresponds to the expected delay for a local memory request to be served.
ffl fi corresponds to the expected delay for serving requests to cluster memories.
ffl fl corresponds to the expected delay for serving all requests, except cluster memories, that follow
FU or BU routing.
corresponds to the expected delay for serving all requests that folllow Forward routing (FW ) or
Backward routing (BW ).
The derivation of terms, ff, fi, fl, and j, is presented below. These terms depend on (a) the routing
probabilities along each path, (b) the amount of traffic in the network, and (c) the service demand
at individual service centers. Thus we get a non-linear equation with P u as the single variable that is
solved by using iteration techniques.
B. Routing probabilities and path delays
The routing probabilities and path delays are derived here for MBN and BMIN under the assumption
that all the non-local memories are equally addressed by a processor. These equations can be modified
in case of nonuniform remote memory references. Since the path length of Backward Routing (BW )
is the same as that of the FW routing, we derive the term j based on FW routing and multiply it by
2 to include BW routing. A similar method is used for FU and BU routing as well.
Local memory requests (ff): A local memory request does not involve switch traversal. Thus the
only delay is that in servicing the request in the memory module (d m ). Given that the probability for
a processor to request a memory is p and that to request a local memory is m, we can deduce that
routing (fi): Requests to cluster processors travel to the first or last stage switch and take
a FU or BU routing to the destination processor. All those source-destination pairs where all bits
except the least significant log 2 k bits of the CT are zero entail this type of routing. Thus the number
of cluster memories for a given source is k is the size of an MBN or BMIN switch.
The switch at stage 0 is traversed once for reaching the cluster memory and once for sending back
the acknowledgment. Here, given that an external memory is requested, the probability for requesting
cluster memories can be expressed as
Thus we have 2 \Theta r 0 delay for the switch traversals and dm for the memory service delay. We get
the following equation,
m) \Theta
Non-cluster FU or BU routing (fl): In forward-U and backward-U routing, the request traverses
in one direction up to a particular stage (as explained in Section 2) and makes a U-turn to reach
the destination processor. Thus given the turning stage, FTS, the path length can be said to be
2 \Theta FTS + 1. This is because the FTS is traversed only once while all stages to the left of FTS are
traversed twice but not necessarily through the same switch. We should have a FTS ! bl=2c for path
length optimization. and BTS - dl=2e for optimal path length. As we have already covered cluster
memories 2.
Consider FTS ! bl=2c. A similar derivation can be done for BTS - dl=2e also.
We know that the number of destinations in total is N \Gamma 1. For a given turning stage 1
FTS is defined as the rightmost bit in the tag, we can have all bits to the left of this position as 1 or
This gives us k i number of ways. As discussed in Section 3, the Rotated Combined Tag (RCT) is
defined as the digit-wise EX-OR of the source and destination tags. Thus the RCT is a tag made up
of 1's or 0's i.e the RCT tag is bitwise regardless of the source and destination tags. The number of
ways in which a bit in the RCT can be 1 is k \Gamma 1. Thus, given that an external memory is requested,
we have the equation for probability of non-cluster FU and BU routing as,
The delay in such a routing is dependent on the stage at which the U-turn is going to take place.
Thus within the summation of the above equation we should include the delay for each switch traversed
in that particular path. As discussed above for a turning stage FTS we traverse through all stages to
the left of FTS twice. Thus the delay except for that in the turning stage is (2 \Theta (
This term is multiplied by two because it considers the acknowledgment packets also. The request and
acknowledgment also traverse the turning stage and the memory module with delay r i +dm . Including
this delay, (2 \Theta (
with the probability gives us the equation for fl as,
Forward routing (j): Finally, for all those source-destination pairs which don't fall into the above
Routing Size of the MBN
FU or BU routing
FW or BW routing


II
Number of destinations for different network sizes using different routings
routing categories, the forward routing path is taken. Since forward routing or backward routing is the
last choice for any other type of source-destination pairs, we can simply express j as
In this type of routing all switches are traversed, thus giving a summation of all switch response times
for d
. Thus the expected delay for all such routings can be expressed as,
where,
where fi p and fl p are given by equations 4 and 6 respectively.
The equations 0 through 9 are valid when the local memory is accessed with a probability of m and
all other memories are addressed with equal probabilities i.e. 1). In an actual case, there
will be more interaction between the tasks within a cluster. The equations can be easily extended to
include such cases.

Table

2 shows the number of destinations that can be reached from processor 0 with each of the
routings as a function of network size. The switch size of the network is 2 \Theta 2. It can be observed
from the table that a significant number of connections benefit from the routings other than FW or
BW that is commonly adopted today. Also the same number of processors use FU or BU routing in
two successive network sizes. We can explain this behavior by an example. Consider
corresponding to network sizes of 64 and 128 respectively. The networks, though of different sizes,
have the same number of destinations for FU routing because the addition of one stage introduces a
true center stage while there is no true center stage in l = 6. Since the
center bit in the CT tag has to be 0 for FU or BU routing, it is apparent that the addition of the
center stage will not increase the number of possible FU or BU routings.
The delays, r 0 , r i , d n and dm , will depend on (a) the amount of traffic in the network, which in
turn is a function of P u itself and (b) the service demand at individual service centers. The queueing
analysis for the delays is given next.
C. Queueing delays in switches
In order to make the analysis simpler, each stage in the network is considered in isolation from the
other stages. Consider a queueing center with n inputs. Let the probability that there is a packet at
one of the inputs at any given cycle be q, and the service demand of a packet at the service center be
cycles. The number of requests coming to the queue during the service time of any previous request
will form a Binomial distribution with number of q. The mean
number of arriving requests, and the variance, q). The average queue length Q
at the queueing center can be found using the Pollaczek-Khinchine (P-K) mean value formula [14],
E)
The throughput of these requests is E=t. Hence by using Little's law, the mean response time of the
center, r, can be derived as,
l
l
BUS
(a) MBN Switch Queue (b) BMIN Switch Queue
Fig. 8. Queues at the BMIN and MBN switches
Queueing models of an MBN switch and a BMIN switch are shown in Figure 8. For an MBN switch
there is contention for the bus by packets from k right ports and k left ports. For a switch at stage i,
is the probability that a packet visits stage i. We can
calculate mean switch response time, r i , for any of these MBN switches using the following equation :
The network delay, d n , will be a sum of the response times of the stages a packet visits while routed
through the network.
In case of the BMIN, there are 2k inputs and 2k outputs in a switch. The request probability at an
input or output of a BMIN switch at stage i will be P u Following the model shown in Fig. 8b,
we can calculate the response time of a BMIN switch by using
The total network delay d n will be the sum of the response times of switches at different stages.
In both networks, the mean number of arriving requests at a memory module,
are the internal and external requests for that memory module, respectively. The variance
Hence average memory queue length,
and the mean memory response time or delay,
A packet (or request) takes the optimal path from a source to the destination. The number of
switches traversed would depend on the nature of CT and RCT. The delays derived here are inserted
into the equations 3,5,7 and 8 which in turn are plugged into equation 2 to obtain the processor
utilization and response time of the network. Then we get a nonlinear equation with P u as the single
variable that is solved by using iteration techniques.
The iteration technique used to compute processor utilization, P u , can be presented as follows:
1. Initialize P u with a guess of the expected processor utilization. The better the guess, lesser is the
number of iterations for the computation.
2. Calculate the request probabilities at each stage of the network and at the memory module. An
intermediate step might be to calculate the static values for p i (the probability that a stage in the
network is traversed).
3. Calculate the mean switch response times and the memory response time, r i and r m respectively.
4. Based on the above values, calculate the network delay and memory delay using equations provided
for ff; fi; fl and j.
5. Based on these values, calculate a new processor utilization, P u .
6. Repeat steps 2-5 until the new P u is within some tolerance of the last P u .
An initial value of 0.5 for P u and an accuracy of 0.00001 were used to generate the analytical results,
presented in the next section.
V. Results and Discussions
We performed extensive cycle-by-cycle simulations to verify that the proposed routings work and
measured the routing probabilities and network delays [16]. The simulation was done using a synchronous
packet-switched distributed memory environment. The simulation specifications are the
same as the analysis and are detailed below with a view to making the network operation more clear.
Processor
Utilization
Request Probability
"simulation_mbn_m=0.1"
"analysis_mbn_m=0.1"
"simulation_mbn_m=0.9"
"analysis_mbn_m=0.9"
Fig. 9. Comparison of analysis and simulation for processor utilizations of the MBN, varying m
In our simulations each cycle was considered to be the time required for the transmission of a packet
from one output buffer of a switch to the next stage output buffer. This includes the transmission of
the packet through the link and the time a switch takes to route it to the corresponding destination
buffer. The minimum time taken for a packet to reach memory is based on the number of switches
that the routing covers.
All four routings discussed in Section 2 are used in the simulations. The simulation compares each
source and destination by running the optimal routing algorithm and then chooses the proper routing.
The choice between backward or forward routing is made as follows . All memory requests that could
use either forward (FW) or backward (BW) routing use forward routing. All acknowledgements packets
use backward routing to keep the load distribution same on both routings. Apart from these differences
the routing decisions are based solely on the tags generated by the optimal routing algorithm. The
probabilities are fed to the simulation as input parameters. All the memories except for the
local memories are equally likely to be addressed upon a memory request.
In this section we present the relative performance of BMIN and MBN. We start by comparing the
Response
Time
Request Probability
"simulation_mbn_m=0.1"
"analysis_mbn_m=0.1"
"simulation_mbn_m=0.9"
"analysis_mbn_m=0.9"
Fig. 10. Comparison of analysis and simulation for response time of the MBN, varying m0.10.30.50.70
Processor
Utilization
Request Probability
"mbn_m=0.1"
"bmin_m=0.1"
"cmin_m=0.1"
"mbn_m=0.9"
"bmin_m=0.9"
"cmin_m=0.9"
Fig. 11. Comparison of processor utilizations, varying m
Response
Time
Request Probability
"mbn_m=0.1"
"bmin_m=0.1"
"cmin_m=0.1"
"mbn_m=0.9"
"bmin_m=0.9"
"cmin_m=0.9"
Fig. 12. Comparison of response time, varying m
results from the simulation versus those obtained from the analysis of the MBN. Many simulation
experiments were run to verify the analytical models developed in this paper. The simulation results
closely matched the analysis under all varied parameters. Here we present some results for a 64 \Theta 64
system with 2 \Theta 2 switches. Memory service time is assumed to be 4 cycles. Processor utilization, P u
is defined as the average amount of useful work the processor does in a given cycle. Response time is
defined as the average difference between the time when a processor submits a memory request and
the time when it gets the reply back.

Figures

show a comparison of analysis and simulation results for the processor utilization
and response time of the MBN. In both the figures, the analytical results match very closely with
those of simulation indicating that the independence of queues assumed during the analysis does not
cause much of an error. The plots show the results from the analysis and simulation as a function
of the memory request probability, p. In this plot the memory request probability (p) is varied from
0.1 to 1.0 and two values for the local memory request probability m (0.1 and 0.9) are chosen. For
larger values of m, more requests are satisfied without going through the MBN. Thus, for
Processor
Utilization
Number of Processors
"p=0.1_mbn"
"p=0.1_bmin"
"p=0.5_mbn"
"p=0.5_bmin"
Fig. 13. Processor Utilization: Scalability of MBN vs BMIN, varying p
is much higher in Fig 9 and response time is much lower in Fig. 10. As p gets larger, more requests
are generated and the response time increases due and the processor utilization reduces to a higher
amount of traffic and queueing delays.

Figures

11 and 12 show a comparison of the performance of the MBN to that of the conventional
MIN (CMIN) and the proposed bidirectional MIN (BMIN). Conventional MIN is similar to the network
employed in the Butterfly machine [3], where both the request and the response packets travel in one
direction from processor to the memory side. On the other hand, BMINs allow all the four routings
proposed for the MBN. The two plots show the processor utilization and the response time of the three
networks for two different values of m. The MBN behaves exactly similar to the CMIN and the BMIN
in terms of processor utilization. The response time is also same for all the networks for 0:9. For
0:1 the BMIN performs better than the MBN and the MBN performs better than the CMIN.

Figures

13 and 14 show the processor utilization and response times for various system sizes. The
results were obtained with a local memory request probability, m, fixed at 0:5 and for two different
values of p (0.1 and 0.5). We can see from the figures that, even as the system size grows, the
Response
Time
Number of Processors
"p=0.1_mbn"
"p=0.1_bmin"
"p=0.5_mbn"
"p=0.5_bmin"
Fig. 14. Response Time: Scalability of MBN vs BMIN, varying p
performance of the MBN remains close to that of the BMIN. The curves for the CMIN are left off
for clarity, but it is observed that the MBN always performs better than the CMIN. It can also be
seen from the figures that as the system size doubles the reduction in performance is not that big,
indicating that the MBN is highly scalable for the given traffic load. The range of the processor
utilization remains approximately between 0:5 and 0:4 as the system size changes from 32 to 1024 with
switches, but the request probability, p, has a much greater effect on the performance.
Finally we present the processor utilization and the response time of the MBN obtained for different
switch sizes and different number of processors in Table III. Some places in the table are left empty
because an N \Theta N MBN cannot be built using only those k \Theta k switches. Both the request probability
(p) and the local memory request probability (m) are fixed at 0.5. For there is a decrease in
is increased from 4 to 8. This is because MBN is less efficient due to increased contention
and delay in an 8x8 bus-based switch. On the other hand, in a 512 \Theta 512 system, when k is increased
from 2 to 8, there is a good improvement. The number of switches in the entire network is still quite
high, keeping the contention low enough to gain in performance.
#Procs. Different Switch Sizes
MBN BMIN MBN BMIN MBN BMIN MBN BMIN MBN BMIN MBN BMIN


III
Processor Utilization and Response Time of the MBN & BMIN varying k and N
If we compare the MBN's performance to that of the BMIN's, we can see that as the switch size
increases, the BMIN gives a higher processor utilization and a lower response time. This increase in
performance is due to a lower contention in the crossbar switch. However, the BMIN gives this increased
performance at the expense of cost. In [8], a cost parameter based on the number of connection points
in a switch is presented. The number of connections is k 2 for a k \Theta k switch, where as for a bus, the
number of connections is 2k. Thus, the total cost of BMIN and MBN are kN log k N and 2N log k N
respectively. If we include these parameters along with the processor utilization and the response time,
the cost-effectiveness of the MBN is higher than that of the BMIN, as shown in [8]. A 4 \Theta 4 switch
size works out to be most cost-efficient for different network sizes and workload inputs.
VI. Execution-driven Simulation and Results
The execution time of an application on a multiprocessor architecture is the ultimate parameter that
indicates the performance. In order to show that the MBN performs similar to the Bidirectional MIN
(BMIN), we study their performance by using an execution-driven simulation of various applications.
Our simulator is based on Proteus [10], originally developed at MIT. However, this original simulator
modeled the indirect interconnection networks based on an analytical model. We have modified the
simulator extensively to exactly model the BMIN and the MBN using 2 \Theta 2 switches and packet-switching
strategy. The system considered in this paper has private cache memories that operate
based on a directory-based cache-coherence protocol [15]. The node configuration and the network
Cache Memory
Network Interface
Proc
Fig. 15. The node configuration and network interface
interface in the simulator are modeled as shown in the Figure 15. Both the cache controller (CC) and
memory controller (MC) are connected to the network interface so that they can directly communicate
with the other nodes. The system parameters used for the simulation, are given in Table IV. Further
details on the simulation can be found in [16], [17].
A. The Benchmark Applications
We have selected some numerical applications as the workload for evaluating the network performance
in a cache-coherent shared-memory environment. These applications are multiplication of two
2-D matrix (MATMUL), Floyd-Warshall's all-pair-shortest-path algorithm (FWA), blocked LU factorization
of a dense 2-D matrix (LU), 1-D fast Fourier transform (FFT), and simulation of rarefied
flows over objects in a wind tunnel (MP3D).
The matrix multiplication was done between two 128 \Theta 128 double precision matrices. The principal
data structures are four shared two-dimensional arrays of real numbers: two input matrices, a transpose
matrix, and one output matrix. The shared data size is about 512 Kbytes.
For Floyd-Warshall's algorithm, we used a graph of 128 nodes with random weights assigned to the
edges. The principal data structures are two shared two-dimensional arrays of integers: one distance
matrix and another predecessor matrix. The shared data size is about 128 Kbytes. The program
goes through as many iterations as the number of vertices, and during an iteration a particular row of
distance and predecessor matrix is read by all the processors. Each iteration is followed by a barrier.
Parameter Value
Number of processors 64
Shared memory size per node 32 Kbytes
Cache size 8 Kbytes
Cache line size 32 bytes
Cache access time 1
Memory access time 8
Switching delay 1
Link width 16 bits
Flit length 16 bits
Packet size 8 bytes


IV
Simulation parameters
The blocked LU decomposition application was done on a 256 \Theta 256 matrix using 8 \Theta 8 blocks. The
principal data structure is a two-dimensional array in which the first dimension is the block, and the
second contains all data points in that block. In this manner, all data points in a block (which are
operated on by the same processor) are allocated contiguously, and false sharing and line interference
is eliminated.
We implemented the Cooley-Tukey 1-D FFT algorithm. The simulations are done on an input of
points. The principal data structures are two 1-D arrays of complex numbers. There is no data
sharing during first log 2 stages, where N is the number of data points and P is the number
of processors. In rest of the log 2 P stages, every data point is shared by two processors. During these
stages, instead of using two separate input and output arrays, we interleave these arrays to avoid large
number of conflict misses.
MP3D is a three-dimensional particle simulator used in rarefied fluid flow simulation. We used 16000
molecules with the default geometry provided with SPLASH [18] which uses a 14 \Theta 24 \Theta 4 (2646-cell)
space containing a single flat sheet placed at an angle to the free stream. The simulation was done for 5
time steps. The shared data set size is about 800 Kbytes. The work is partitioned by molecules, which
are statically scheduled on processors. A clump size of 8 was used. Further details on the benchmarks
Application Memory references Cache misses Messages generated
MATMUL 9,215,571 743,258 1,474,220
LU 112,270,761 706,579 1,671,854


Characteristics of the applications used in the evaluation.
Application BMIN Latency MBN Latency CMIN Latency
Matmul 224.48 231.25 538.48


VI
Average Message Latencies using different networks
and the simulation environment can be found in [17].
B. Simulation Results
The characteristics of the applications, as measured in the simulation, are given in Table V. The
table shows the number of shared memory references, the cache misses on the shared memory references
and the total number of messages generated during the execution. We begin by presenting the average
message latencies experienced when the above applications are run in this shared memory environment.
The values shown in Table VI show that the response time of messages do not significantly differ by
the use of MBN as opposed to BMIN. However, the response time of the CMIN is significantly higher
than that of the MBN or BMIN for all applications. Thus the time taken for serving cache misses is
higher using the CMIN than the MBN.
The use of the U-turn routing strategies is one of the factors in reducing the average latencies in
both the interconnection networks. The introduction of U-turns not only reduces the response times
of the messages but also distributes the messages throughout all the switches in the IN. The use of
Application Stage 0,5 Stage 1 Stage 2 Stage 3 Stage 4 No Turn % U-turns
Matmul 79327 185033 343747 313942 157439 3996773 21.3
MP3D 138163 295884 752859 684434 345831 7664693 22.44


VII
Number of U-turns taken at different stages in the MBN
Write stall time
Read stall time
Parallel execution and synchronization time
Execution
time in
million
cycles
Execution
time in
million
cycles
Execution
time in
million
cycles
Execution
time in
million
cycles
Execution
time in
million
cycles4MBN
MATMUL4MBN
MBN
of Packet Buffers per link = 64 bytes.
MBN
CTFFT2MBN48
MP3D
CMIN CMIN CMIN
BMIN
BMIN
BMIN
BMIN
BMIN CMIN CMIN
Fig. 16. Execution-Based Simulation Results
FU and BU strategies is shown in Table VII which lists the number of packets that made a U-turn at
each stage in the MBN or BMIN. The network model does not allow U-turns in the last stage of the
network since a turn at the last stage is similar to a turn at the first stage and both are counted as the
same. There are six stages of 2 \Theta 2 switches in a 64 \Theta 64 network. The turns at the first or last stage
(0 or 5) constitute the messages sent to cluster memories. The last column in the table shows the
percentage of packets taking U-turns for each application. The number of U-turns is quite significant.
An evaluation based on the execution time of these applications gives the performance of the inter-connection
networks in a more realistic environment. The simulator gives the execution time of an
application in millions of cycles. Also, we measured times for different activities, as shown in Fig. 16.
The timings are shaded differently for the following activities.
ffl The time spent in computation and synchronization.
ffl The read stall time: This is the maximum read stall time experienced by any processor.
ffl The write stall time: This is the maximum write stall time experienced by any processor.
The graph in Fig. 16 is divided into 5 sets of 3 bars each. Each set is for a different application
and shows the execution time using MBN vs. BMIN vs. CMIN. The figure shows that the BMIN and
MBN give a much better performance than the CMIN. The improvement in overall execution time
is mainly due to the reduction in read stall time and write stall time which is directly related to the
network latency.
It can be seen from the results that the MBN performance is very similar to the BMIN performance.
It can be further observed that, for all the applications considered, the write stall time is lower than
the read stall time because of fewer write misses.
VII. Conclusions
The paper presented a multistage bus network (MBN) that offers better performance and reliability
than a conventional multistage interconnection network (MIN). An equivalent Bidirectional MIN
(BMIN) was also presented for performance comparison. Self routing schemes for different paths were
developed based on routing tags. An algorithm was presented to find the path of minimum distance
between a source and a destination. Probabilities of taking these different paths were derived and
a queueing analysis was presented for evaluating the performance of the MBN and the BMIN. The
analysis was verified by simulations and comparisons of results with the MIN were made. It was shown
that the performance of the MBN was very similar to the BMIN in terms of response time and processor
utilization, but much better than a conventional MIN. To emphasize the potential of the MBN, an
execution-based evaluation was also presented in a cache-coherent shared memory multiprocessor environment
that use a directory-based cache coherence protocol. The performance of the MBN in such an
environment is also shown to be almost equal to the BMIN in terms of message latency and execution
time of five applications. This fact along with simplicity in hardware and better fault-tolerance makes
the MBN a viable alternative to the existing MIN.



--R

"Hierarchical cache/bus architecture for shared memory multiprocessors,"
Technical Summary,"
"Butterfly Parallel Processor Overview, version 1,"
"The SP1 high-performance switch,"
"The Network Architecture of the Connection Machine CM-5,"
"Design and performance of generalized interconnection networks,"
"Multistage bus network (MBN) : An interconnection network for cache coherent multipro- cessors,"
" Performance and Reliability of the Multistage Bus Network,"
"Optimal Software Multicast in Wormhole-Routed Multistage Networks,"
" PROTEUS: A High-Performance Parallel Architecture Simulator,"
"Output-buffer switch architecture for asynchronous transfer mode,"
"The performance of multistage interconnection networks for multiprocessors,"
"Finite Buffer Analysis of Multistage Interconnection Networks,"
Queueing Systems Volume
"A New Solution to Coherence Problems in Multicache Systems,"
"Distributed Shared Memory Multiprocessors using Multistage Bus Networks,"
"Evaluating virtual channels for cache coherent shared memory multiprocessors,"
"SPLASH: Stanford Parallel Applications for Shared-Memory,"
--TR

--CTR
L. N. Bhuyan , H. Wang , R. Iyer, Impact of CC-NUMA Memory Management Policies on the Application Performance of Multistage Switching Networks, IEEE Transactions on Parallel and Distributed Systems, v.11 n.3, p.230-246, March 2000
Kenneth Hoganson, Mapping Parallel Application Communication Topology to Rhombic Overlapping-Cluster Multiprocessors, The Journal of Supercomputing, v.17 n.1, p.67-90, Aug. 2000
Ravishankar R. Iyer , Laxmi N. Bhuyan, Design and Evaluation of a Switch Cache Architecture for CC-NUMA Multiprocessors, IEEE Transactions on Computers, v.49 n.8, p.779-797, August 2000
A. Chadi Aljundi , Jean-Luc Dekeyser , M-Tahar Kechadi , Isaac D. Scherson, A universal performance factor for multi-criteria evaluation of multistage interconnection networks, Future Generation Computer Systems, v.22 n.7, p.794-804, August 2006
Ravishankar Iyer , Hujun Wang , Laxmi Narayan Bhuyan, Design and analysis of static memory management policies for CC-NUMA Multiprocessors, Journal of Systems Architecture: the EUROMICRO Journal, v.48 n.1-3, p.59-80, September 2002
routing;performance analysis;interconnection network;packet-switching;execution-driven simulation;queuing model