Transcription
Interconnection networks1) Large switch structures built fromsmaller switchesA 2x2 switchor router2) Topology-induced switchingstructuresA 5x5 switchor router2x2A processorand/or memory5x5A processor memory1Common PCrossbarMultistageTreeFat tree2
Buses and crossbars CostLatencyBandwidthScalabilityEach switch is a 2x2 switch thatcan be set to one of 2 settings3Multistage networksA 2x2 switchor router2x2Circuit switching: circuits are establishedbetween inputs and outputs – arbitrateentire circuits.Packet switching: packets are buffered atintermediate switches – arbitrateindividual switches. NxN Omega network: log N stages, with N/2, 2x2 switches. A blocking network: some input-output permutations cannot be realized dueto path conflicts.4
Evaluating Interconnection Network topologies Diameter: The distance between the farthest two nodes in the network. Average distance: The average distance between any two nodes in thenetwork. Node degree: The number of neighbors connected to any particularnode. Bisection Width: The minimum number of wires you must cut todivide the network into two equal parts. Cost: The number of links or switches (whichever is asymptoticallyhigher) is a meaningful measure of the cost. However, a number ofother factors, such as the ability to layout the network, the length ofwires, etc., also factor in to the cost.52-D torus Diameter? Bisection bandwidth? Routing algorithms x-y routing Adaptive routing 2D mesh (without the wraparound connections) Variants– 1-D (ring), 3-D.6
Hypercube interconnections An interconnection with low diameter and large bisection width. A q-dimensional hypercube is built from two (q-1)-dimensional hypercubes.00Dimension 00100100011000101-dimensionbinary hypercube2-dimensionbinary hypercube11111011110101100201103-dimensionbinary hypercube7A 4-dimension Hypercube (16 1011100010101002101010114-dimensionbinary hypercube Can recursively build a q-dimension network – has 2q nodes8
Common interconnection topologiesN 1024TypeDegree Diameter Av DistN/3BisectionDiamAv. D1D mesh2N-12D mesh42(N1/2 - 1) 2N1/2 / 3N1/263213D mesh63(N1/3 -N2/3 30 10Ring2N/2N/422D torus42N1/21)3N1/31/3N1/2N1/2 / 2k-ary n-cube 2n(N kn)n(N1/n)nk/2nN1/n/2nk/4Hypercuben LogN n/2n3216158 (3D)1052kn-1N/29Multistage ionMultistagenetwork networkMemorybanksbanks (or processors)Memory0011.p-1Stage 1.Stage 2.Stage n.b-1The schematic of a typical multistage interconnection network.If 2x2 switches are used to build an pxp switch (to connect p processors to pmemory banks – p being a power of 2), we need at least log p stages – why?.10
Examples of MINs connecting 2q inputs to 2q outputs(using q stages of 2x2 switches)01010101232323234545454567676767A butterfly networkAn Omega network(multiple shuffle/exchange)11Multistage Omega NetworkA pxp Omega network consists of: q log p stages, each having p/2, 2x2 switches Perfect shuffle connection between stagesi connects to 2ifor i 0, , p/2-1i connects to 2i 1-pfor i p/2, , p-1- Formally, Shuffle(xq-1 , xq-2 , , x0) xq-2 , , x0 , xq-100000000 left rotate(000)00111001 left rotate(100)01022010 left rotate(001)01133011 left rotate(101)10044100 left rotate(010)10155101 left rotate(110)11066110 left rotate(011)11177111 left rotate(111)12
Multistage Omega NetworkAn 8x8 omega change? Exchange? Exchange?Shuffle(xq-1 , xq-2 , , x0) xq-2 , , x0 , xq-1Exchange(xq-1 , xq-2 , , x0) xq-1 , xq-2 , , x013Routing in an OMEGA network(Unique route between a source and a 0111110111The destination d2 d1 d0 iscoded in message headerExample: to route from source 101 to destination 110 (101 xor 110 011)101 011 011 110 111 111 110shuffleshuffleexchange shuffle exchangestraightcrosscross14
Routing in an OMEGA 10111Example: to route from source 010 to destination 100010 xor 100 110 (cross, cross, straight)Route: cross at first level, cross at second level, straight at last level15Routing in an OMEGA networkTo get from sq-1 , sq-2 , , s0 to dq-1 , dq-2 , , d0 Do q shuffles After each shuffle, do an exchange to match the correspondingdestination bit16
The Omega Network is 01110111Example: one of the messages (010 to 111 or 110 to 100) isblocked at link AB.Only a fraction of the p! permutations can be realized inan omega network (can you formally prove?).17Capabilities for realizing arbitrary permutations Blocking networks: cannot realize an arbitrary permutation withoutconflict -- for example, Omega can realize only pp/2 permutations. Non-blocking networks: can realize any permutation on-line -- forexample, cross-bar switches. Re-arrangeable networks: can realize any permutation off-line -for example, a Benes network can establish any connection in apermutation if it is allowed to re-arrange already establishedconnections.The Benes networkCan be built recursively -- an pxp Benes is built from two(p/2 x p/2) Benes networks plus two columns of switches.18
0101Upper p/2 Benes23234545Lower p/2 Benes67A 2x2 Benes network67A 4x4 Benes network190011223344556677An 8x8 Benes network20
A 16x16Benesnetwork21To realize a permutation (i , oi , i 0, , p-1) in an pxp Benesnetwork: For each connection (i , oi ), determine whether it goes throughthe upper or lower p/2 Benes. Repeat this process recursively for each of the p/2 networks. Start with k 0 and (k, ok ) going through the upper Benes, If ok shares a switch at the last column with om , then route (m,om ) through the lower Benes. If j shares a switch at the first column with m, then route (j, oj )through the upper Benes. Continue until you get an input that shares a switch with input 0. If there are still unsatisfied connections, repeat the looping.22
Example for establishing a permutation:(0,4), (4,2), (3,6), (1,0), (2,3), (6,5), (5,7), (7,1)0101Upper n/2 Benes23234545Lower n/2 Benes67(0,4) upper,(6,5) lower,(7,1) upper,(1,0) lower, 67(2,3) upper,(4,2) lower,(5,7) upper,(3,6) lower,23Set the upper n/2 network to satisfy (0,2), (1,1), (2,3), (3,0)Set the lower n/2 network to satisfy (0,0), (1,1), (2,3), (3,2)0100112322334500116722330123456724
Set the upper n/2 network to satisfy (0,2), (1,1), (2,3), (3,0)Set the lower n/2 network to satisfy (0,0), (1,1), (2,3), (3,2)01230012UL067212334510UL1233Setting the upper n/2 network(0,2) U,(2,3) L,(3,0) U,(1,1) L01234567Setting the lower n/2 network(0,0) U,(1,2) L,(2,3) U,(3,2) L25Fat tree networksEliminates the bisection bottleneck of a binary tree26
A 16-node fat tree network1023 stage01012323454567678989101110111213121314151415A fat tree networksusing 2x2 bidirectionalswitches27Routing in a fat tree0123 stage0123456789101112131415sourcesq-1 , sq-2 , , s0destination xq-1 , xq-2 , , x0-Find smallest k such that si xi , i k 1, ,q-1(if no such k exists, then k q-1 )- Route arbitrarily up the tree to a switch in stage k- Route down the tree as follows:at stage i, i k, , 0if xi 0, route to upper portelse route to lower portExamples (q 4):0011 1110 (k 3)1000 1100 (k 2)28
Other networks(a)A completely-connectednetwork(b)A star connectednetwork(a)with no wraparoundlinks(b)with wraparoundlink (ring).Linear arrays29Enhanced ring networks00111102910384576 11129384576Cords (in a chordal ring) may bypass any given number of nodesMay have more than one set of chordsWhat is the diagonal of a chordal ring?How do you route?30
Two- and Three Dimensional Meshes(a)(b)(c)Two and three dimensional meshes: (a) 2-D mesh with nowraparound; (b) 2-D mesh with wraparound link (2-D torus); and(c) a 3-D mesh with no wraparound.31Hypercube 0000100001101110001010100101010113For a q dimension hypercube, calculate The number of nodes and the number of edges The node degree The diameter The bisection bandwidth32
001010100101010113 Each node in a q-dimension hypercube has a q-bits identifier xq-1 , . . . , x1 , x0 Identifiers of nodes across a dimension j differ in the jth bit (have a unitHamming distance) How do you find the route between a source, s, and a destination, d?33Routing Algorithm Routing algorithms define the path taken by a packet between source anddestination. One goal is to prevent deadlock, livelock, and starvationo Deadlock: packets waiting for each other in a cycle.o Livelock: packets circulating the network without making any progresstowards their destination.o Starvation: packets being blocked in buffer as the output channel isalways allocated to other packets. Adaptive routing provides alternative paths for packets that encounterunfair channel allocation, faulty hardware, or hot spots in trafficpatterns. Routing algorithms can be classified intoo Non-adaptive: one unique, predetermined path.o Partially adaptive: can route by multiply paths, but not every paths.o Fully adaptive: can route along any shortest path in the network34
Routing on a 000010000110111000101010023A message from a source, sq-1 , . . . , s0, to a destination xq-1 , . . , x0 has to cross any dimension, b, for which xb sbHow many distinct routes there are between any source anddestination?35Dimension-order 1011100010101002101010113When a node, nq-1 , . . . , n0, receives a message for destinationnode xq-1 , . . . , x0 , it executes the following If xk nk for k 0, , q-1, , keep the message Else { Find the largest k such that xk nk ;Send the message to the neighbor across dimension k }36
5 Evaluating Interconnection Network topologies Diameter: The distance between the farthest two nodes in the network. Average distance: The average distance between any two nodes in the network. Node degree: The number of neighbors connected to any particular node. Bisection Width: The minimum number of wires
