Gebali F. Analysis Of Computer And Communication Networks

Подождите немного. Документ загружается.

14.6 Crossbar Network 511

14.6 Crossbar Network

Crossbar switches have not been well represented in the literature, with the excep-

tion of [7], perhaps due to the original article by Clos [8], in which he claimed that

a crossbar network is very expensive to implement. With the current state of VLSI

technology, it is possible to place several switching elements and their state registers

on a single chip with the only limitation being the number of I/O pins and pad size

[2]. Happily, several companies already produce high-speed network switches built

around a crossbar network [9–11].

An N × N crossbar network consists of N inputs and N outputs. It can connect

any input to any free output without blocking. Figure 14.2 shows a 6 × 6 crossbar

network. The network consists of an array of crosspoints (CP) connected in a grid

fashion. CP(i, j) lies at the intersection of row i with column j. Each CP operates

in one of two configurations as shown in Fig. 14.3. The X-configuration is the de-

fault configuration where the SE allows simultaneous data flow in the vertical and

horizontal directions without interference. If CP(3,5) was in the X-configuration,

then data flowing horizontally originates at input 3 and is sent to all the intersection

points at this row. Data flowing vertically in column 5 could have originated from

any input above or below row 3.

In the T-configuration, the CP allows data flow in the horizontal direction and

interrupts data flow in the vertical direction. Data flowing vertically at its output is a

copy of the horizontal data. For example, if CP(3,5) was in the T-configuration, then

data flowing horizontally originates at input 3. Data flowing downward at the output

Fig. 14.2 A6×6 crossbar

interconnection network

23456

Outputs

Inputs

Fig. 14.3 States of the

crosspoint (CP) in a crossbar

network

X-configuration T-configuration

512 14 Interconnection Networks

is a copy of the horizontal data coming from row 3. This way, output at column 5

sees a copy of the data that was moving in row 3.

A crossbar network supports high capacity due to the N simultaneous connec-

tions it can provide. This comes at the expense of the number of CPs that grows as

. This is one reason why a crossbar network is used mainly for demanding appli-

cations that requires a relatively small values of N (about 10). However, advances

in VLSI technology and electro-optics make crossbar switches a viable switching

alternative.

Data multicast in a crossbar network can be easily accomplished. Suppose that

input 3 requests to multicast its data to outputs 1, 3, and 5. Input 3 would then

request to configure CP(3,1), (3,3), and (3, 5) into the T -configuration and all other

CPs in row 3 would remain in the default X-configuration.

14.6.1 Crossbar Network Contention and Arbitration

Suppose that two or more inputs request access to the same output. In that case,

contention arises and some arbitration mechanism has to be provided to settle this

dispute. In fact, we have to provide N arbiters such that each one is associated with

a column in the crossbar network. For example, when input 1 requests to commu-

nicate with output 3, it requests to configure CP(1,3) into the T -configuration and

must wait until the arbiter in column 3 issues a grant to that input. At the same time,

the arbiter in column 3 must inform all other inputs that they cannot access column

3 in that time step. This happens only after the arbiter checks to see if there are

any requests coming from other inputs demanding access to output 3. These arbiters

slow down the system especially for large networks where signal propagation up

and down the columns takes a substantial amount of time.

Arbitration was necessary because access to the crossbar network was input

driven where the inputs issue the requests to configure the crosspoint switches. In

an output-driven crossbar network, the outputs initiate issuing of requests for data

from the inputs and this eliminates the need for the arbiters. Needless to say, this

mode of operation leads to much faster switch operation and was first proposed by

the author in references [12–14].

14.6.2 Analysis of Crossbar Network

The crossbar switch can be considered as a collection of N shared media, viz., the

columns of the crossbar network, since each column is associated with an output

link or channel. All N columns operate in parallel and each output accepts traffic

from all N inputs (rows). Thus the traffic arriving at each output port is a fraction of

the traffic arriving at the inputs.

Assume a is the packet arrival probability at an input port of an N × N crossbar

switch. Let us study the activity of a certain output port. We call this the tagged

14.6 Crossbar Network 513

output port. The probability that a packet arrives at any input port such that it is

destined to the tagged output port is given by



(14.1)

This is because an arriving packet has an equal probability of requesting one of

N output ports. Essentially, each output port deals with N users but the probability

of packet arrival is reduced to a/N. The probability that i requests arrive at a time

slot addressed to the tagged output port is given by

p(i) =











1 −



N−i

(14.2)

The input traffic N

(in) that is destined for the tagged output port per time slot is

given by

(in) = E

[

(

)

]



i=0

(

)

= a (14.3)

The throughput of the tagged output port is equal to the output traffic of the

tagged output port and is given by the expression

Th =



i=1

p(i) = 1 − p(0) (14.4)

After substituting the value for a



we could write

Th = N

(out)

= 1 −



1 −



packets/time step (14.5)

The second term in the RHS is simply the probability that no packets are destined

to the tagged output port. For light loading, we get Th ≈ a which indicates that most

of the arriving packets are transmitted.

In the limit for large networks (N →∞), we get

Th = lim

N→∞



1 −



1 −





= 1 −e

−a

packets/time step (14.6)

For very large crossbar network at very light loads a  1, we get Th → a which

indicates that almost all the arriving packets make it through the switch due to the

light loading.

514 14 Interconnection Networks

What is really exciting is the performance of very large crossbar networks under

extremely heavy loading. The maximum throughput Th(max) occurs at very heavy

traffic (a = 1):

Th(max) = 1 −e

−1

= 63.21% packets/time step (14.7)

Thus the crossbar network is characterized by very high throughput even at the

highest load and for large networks.

From (14.3) and (14.5), the packet acceptance probability is given by

a(out)

a(in)



1 −



1 −





(14.8)

For light traffic (a  1), we get p

≈ 1 which indicates very high efficiency. In

the limit for large networks, we get

= lim

N→∞



1 −



1 −





1 −e

−a

(14.9)

The minimum acceptance probability p

(min) occurs at very heavy traffic

(a = 1):

(min) = 1 −e

−1

= 63.21% (14.10)

Thus the crossbar network is characterized by very high acceptance probability

even at the highest load and for large networks.

The delay of the network is defined as the average number of attempts to access

the desired output. The probability that the packet succeeds after k tries is given by

the geometric distribution

p(k) = p

(

1 − p

)

(14.11)

The average delay time is

∞



k=0

kp(k)

∞



k=0

(

1 − p

)

1 − p

time steps (14.12)

14.7 Multistage Interconnection Networks 515

0.2

0.4

0.6

0.8

Throughput

0 0.5 1

0.2

0.4

0.6

0.8

Input traffic

Acceptance probability

0 0.5 1

0.2

0.4

0.6

0.8

Input traffic

0 0.5 1

Input traffic

Delay

Fig. 14.4 Variation of the throughput, the packet acceptance probability, and the delay with the

input traffic for the crossbar network when N = 8(solid line)andN = 16 (dotted line)

For light traffic (a ≈ 0), we get n

≈ 0 which indicates that arriving packets get

through on their first attempt. For heavy traffic, a = 1 and the maximum number of

attempts becomes 0.582 on the average.

Example 14.1 Plot the throughput (Th), the access probability (p

), and the average

delay (n

) versus the input traffic for the crossbar network when the size of the

network is N = 8 and N = 16.

We evaluate the expressions for throughput, packet acceptance probability, and

delay when N has the values 8 and 16 and a is varied. Figure 14.4 shows the vari-

ation of throughput, the packet acceptance probability, and the delay with the input

traffic when N = 8 (solid line) and N = 16 (dotted line). We see that the minimum

throughput is around 63.66% and occurs at a = 1. What is striking is the good

overall performance of the crossbar network and the little dependence on N.

14.7 Multistage Interconnection Networks

As Fig. 14.5 shows, an N × N multistage interconnection network consists of n

stages with stage i connected to stages i − 1 and i + 1 through some pattern of

connection lines. Each stage has w crossbar switching elements (SE) that vary in

516 14 Interconnection Networks

Fig. 14.5 A4×4 MIN with

three stages and four switches

per stage

Stage: 0

Connection

Links

Switching

Element (SE)

Inputs

Outputs

size from 2 × 2 and up. The SEs in each stage are numbered starting at the top as

shown. For the MIN in the figure, we have N = 4, n = 3, and w = 4. The labeling

of the stages and switches is also shown in the figure. Typically, the number of

stages

n = lg N. The design parameters for a MIN are the size of the network

N, the number of stages n, the number of switches per stage w, and the size of

each switch. These four factors determine the MIN complexity. Another important

measure of the cost of a MIN is the number and length of the wires in the connection

links between the stages. This last factor determines the required number of pins or

connections at every level of integration or packaging. MINs are classified into three

classes according to the ability of the network to establish a path between an input

and an output [4, 15]:

Blocking MIN: A connection between a free input/output pair cannot be estab-

lished due to conflicts with already-existing connections. This blocking is

called internal blocking since the internal wiring of the network prevented

path establishment. This type of MIN usually has a single path connecting

any input/output pair which leads to hardware economy at the cost of reduc-

ing the fault tolerance and the throughput due to internal blocking.

Nonblocking MIN: A connection between a free input/output pair can be es-

tablished independent of already-existing connections. This type of MIN has

many alternative routes connecting any input/output pair which makes them

expensive to implement although they are not as expensive as a crossbar

network.

Rearrangeable MIN: Any input can be connected to any free output port by

rearranging existing connections. Rearrangeable networks should not be con-

fused with nonblocking networks that do not rearrange existing paths to

establish new connections. Rearrangeable networks are less expensive than

nonblocking or crossbar networks.

We use Knuth’s [11] notation “lg N” to denote the base-2 logarithm log

14.7 Multistage Interconnection Networks 517

14.7.1 Definitions

We start our study of MINs by defining some functions that are commonly used in

the field of multistage interconnection networks:

Shuffle function: Assume the label for a row in the MIN is represented as binary

number A. The perfect shuffle function S performs a circular left shift on the

bits of A:

A = a

n−1

n−2

··· a

S(A) = a

n−2

n−3

··· a

n−1

Inverse shuffle function: The inverse perfect shuffle function S

−1

performs a

circular right shift on the bits of A:

A = a

n−1

n−2

··· a

−1

(A) = a

n−1

··· a

Exchange function: The exchange function E

i, j

exchanges the bits at positions

i and j leaving all other bits intact:

A = a

n−1

··· a

i, j

(A) = a

n−1

··· a

Butterfly function: The butterfly function B

exchanges the least significant bit

) and the ith bit (a

) of the binary number leaving all other bits intact:

A = a

n−1

··· a

i+1

i−1

··· a

(

)

= a

n−1

··· a

i+1

i−1

··· a

Cube function: The cube function C

complements the ith bit (a

) of the binary

number leaving all other bits intact:

A = a

n−1

··· a

i+1

i−1

··· a

(

)

= a

n−1

··· a

i+1

i−1

··· a

Plus–Minus 2

(PM2I) function: The plus–minus 2

(PM2I) function adds ±2

to the row address of a packet. The result is reduced using the modulo func-

tion as follows:

PM2

(

)



A +2



mod N

PM2

−i

(

)



A −2



mod N

518 14 Interconnection Networks

where i varies between 0 and n = lg N. Notice that the C

function could be

implemented using the PM2I function:

(

)

= A +

PM2

(

)

−a

PM2

−i

(

)

Below we show examples of several MINs that were proposed for applications

in communications.

14.8 Generalized-Cube Network (GCN)

Figure 14.6 shows an 8 ×8 generalized-cube network [16, 17]. The interconnection

pattern of the network is based on the cube and shuffle functions. For an N × N

network, the number of stages is n where n = lg N and the number of SEs in

each stage is N/2. Each SE is a 2 × 2 crossbar switch and the number of links

between stages is N. This network is equivalent to many other networks that were

proposed such as the omega [18], banyan [19], delta, and baseline. The generalized-

cube network is a blocking network and provides only one path from any input to

any output. As such, it possesses no tolerance for faults.

Switching element SE(i, j) at stage i and position j is connected to SE(i +1, k)

such that k is given by

k =



j straight connection

(

)

cube connection

(14.13)

where 0 ≤ i < n and 0 ≤ j < N/2. Note that the SE row label j requires only n−1

bits for its representation. Thus when N = 8, the switch row label is composed only

of two bits.

As an example, SE(1,2) at stage 1 is connected to switches SE(2,2), the straight

connection, and switch SE(2,0), the C

(

)

connection.

Fig. 14.6 Generalized-cube

network for N = 8

Inputs

Outputs

Stage

000

14.8 Generalized-Cube Network (GCN) 519

At the last stage, output stage, switch SE(2, j) is connected to row k such that k

is given by

k =



j straight connection

(

)

cube connection

(14.14)

where 0 ≤ j < N. Note that the output row label j requires only n − 1 for its

representation. Thus when N = 8, the switch row label is composed of three bits.

As an example, SE(2,3) is connected to output rows 3 and 7 since we have j = 3

which has the binary equivalent 011 and applying the straight and cube connection

(3) gives output rows 3 and 7, respectively.

The GCN provides one unique path from any input to any output based on the

input row address and the destination address. The packet path is established by

properly configuring the connections within each SE that the packet goes through.

Figure 14.7 shows the two types of connections that could be simultaneously estab-

lished for the two inputs of an SE at stage i:

Straight connection: The packet enters and exits at the same row location.

Cube connection: The packet enters at row location R and exits at row location

(

)

Depending on the SE design, one SE input could simultaneously establish the

straight and cube connections for itself, while the other input will not be able to

access the two outputs. This situation is useful to broadcast packets to two or more

outputs.

14.8.1 Routing Algorithm for GCN Network

The routing algorithm in GCN is distributed among the SEs and is based on per-

forming a bitwise XOR operation on the source row address (S) and destination row

address D. S indicates the row location of the input port and D indicates the row

Fig. 14.7 The straight and

cube connections for each

input of an SE in a GCN

network

The straight connection for

each input

The cube connection for each

input

520 14 Interconnection Networks

location of the desired output port. The routing vector r is used to determine the

path of the packet through the network. r is obtained as follows:

r = XOR

(

S, D

)

(14.15)

where the n-bit routing vector r carries the information about the desired path. Bit i

of that vector specifies the type of connection of the SE at stage i:

⎧

⎨

⎩

0 straight connection

1 cube connection

(14.16)

For an 8 ×8 GCN network n = lg 8 = 3 and the routing vector r will have three

bits. If an incoming packet arrives at row 2 (binary 010) and is destined to row 6

(binary 110), then we have

S =



010



(14.17)

D =



110



(14.18)

r =



100



(14.19)

The path selected is explained in Table 14.1.

Figure 14.8 shows the path chosen to route a packet from input at row 2 to output

at row 6 based on binary bit pattern of routing vector r.

Table 14.1 SE settings for

path in GCN network from

input 2 to output 6

Stage i = 0 i = 1 i = 2

Bit scanned r

Bitvalue 001

Connection type Straight Straight Cube

Fig. 14.8 Path chosen in the

GCN network to route a

packet from input at row 2 to

output at row 6 based on

binary bit pattern of routing

vector r

012

Inputs

Outputs

Stage

000