Multiprocessor Interconnection Networks Networks How do we move data between processors Design Options Topology Todd C Mowry 15 740 October 18 2007 Routing Physical implementation Topics Network design issues Network Topology 2 CS 740 F 07 Evaluation Criteria Buses Latency P P P Bisection Bandwidth Contention and hot spot behavior Bus Partitionability Simple and cost effective for small scale multiprocessors Cost and scalability Not scalable limited bandwidth electrical complications Fault tolerance 3 CS 740 F 07 4 Page 1 CS 740 F 07 Crossbars Rings Crossbar P Each port has link to every other port Cheap Cost is O N P P Low latency and high throughput Point to point wires and pipelining can be used to make them very fast P M M M M Cost grows as O N 2 so not very scalable High overall bandwidth Difficult to arbitrate and to get all data lines into and out of a centralized crossbar P P 6 P CS 740 F 07 Trees Hypercubes H Tree Latency is O logN Easy to layout as planar graphs e g H Trees 0 D 1 D 2 D 3 D 4 D Also called binary n cubes of nodes N 2 n Latency is O logN Out degree of PE is O logN Minimizes hops good bisection BW but tough to layout in 3 space Popular in early message passing computers e g intel iPSC NCUBE Used as direct network emphasizes locality For random permutations root can become bottleneck To avoid root being bottleneck notion of Fat Trees used in CM5 Fat Tree 7 P Ring Examples KSR machine Hector CS 740 F 07 Cheap Cost is O N P High latency O N Used in small scale MPs e g C mmp and as building block for other networks e g Omega 5 P CS 740 F 07 8 Page 2 CS 740 F 07 Multistage Logarithmic Networks Omega Network Omega Net w or k Key Idea have multiple layers of switches between destinations Cost is O NlogN latency is O logN throughput is O N Generally indirect networks Many variations exist Omega Butterfly Benes 000 000 001 001 010 011 010 011 100 100 101 101 110 111 110 111 All stages are same so can use recirculating network Used in many machines BBN Butterfly IBM RP3 Single path from source to destination Can add extra stages and pathways to minimize collisions and increase fault tolerance Can support combining Used in IBM RP3 9 CS 740 F 07 10 Butterfly Network CS 740 F 07 k ary n cubes But t er f l y Net w or k 000 000 001 001 010 011 010 011 100 100 101 101 110 111 4 ary 3 cube 110 111 spl i t on MSB spl i t on LSB Equivalent to Omega network Easy to see routing of messages Generalization of hypercubes k nodes in a string Also very similar to hypercubes direct vs indirect though Total of nodes N k n Clearly see that bisection of network is N 2 channels k 2 reduces of channels at bisection thus allowing for wider channels but more hops Can use higher degree switches to reduce depth 11 CS 740 F 07 12 Page 3 CS 740 F 07 Real World 2D mesh Advantages of Low Dimensional Nets What can be built in VLSI is often wire limited LDNs are easier to layout more uniform wiring density easier to embed in 2 D or 3 D space mostly local connections e g grids Compared with HDNs e g hypercubes LDNs have shorter wires reduces hop latency fewer wires increases bandwidth given constant bisection width increased channel width is the major reason why LDNs win 1824 node Paragon 16 x 114 array LDNs have better hot spot throughput more pins per node than HDNs 13 CS 740 F 07 14 Embeddings in two dimensions 6x3x2 Embed multiple logical dimension in one physical dimension using long wires 15 CS 740 F 07 Page 4 CS 740 F 07
View Full Document
Unlocking...