Multiprocessor Interconnection Networks Networks How do we move data between processors Design Options Topology Routing CS 740 November 13 2002 Physical implementation Topics Network design issues Network Topology Slides from TCM CS 2 Page 1 CS 740 F 01 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 01 4 Page 2 CS 740 F 01 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 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 Examples KSR machine Hector CS 740 F 01 6 Page 3 P Ring P P P CS 740 F 01 Trees Cheap Cost is O N 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 For random permutations root can become bottleneck Also called binary n cubes To avoid root being bottleneck notion of Fat Trees used in CM5 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 Fat Tree 7 of nodes N 2 n CS 740 F 01 8 Page 4 CS 740 F 01 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 00 0 001 00 1 010 011 01 0 01 1 100 10 0 101 10 1 110 111 11 0 11 1 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 01 10 Page 5 CS 740 F 01 Butterfly Network k ary n cubes But t er f l y Net w or k 00 0 00 0 00 1 00 1 01 0 01 1 01 0 01 1 10 0 10 0 10 1 10 1 11 0 11 1 spl i t on MSB 4 ary 3 cube 11 0 11 1 spl it 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 01 12 Page 6 CS 740 F 01 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 01 14 Page 7 CS 740 F 01 Embeddings in two dimensions Routing Recall routing algorithm determines which of the possible paths are used as routes how the route is determined R N x N C which at each switch maps the destination node nd to the next channel on the route Issues Routing mechanism arithmetic source based port select table driven general computation Properties of the routes Deadlock free 6x3x2 Embed multiple logical dimension in one physical dimension using long wires 15 CS 740 F 01 16 Page 8 CS 740 F 01 Routing Mechanism Routing Mechanism cont need to select output port for each input packet P3 P1 P0 Source based in a few cycles Reduce relative address of each dimension in order Dimension order routing in k ary d cubes e cube routing in n cube 17 P2 message header carries series of port selects used and stripped en route CRC Packet Format CS 2 Myrinet MIT Artic Table driven message header carried index for next port at next switch o R i table also gives index for following hop o I R i ATM HPPI CS 740 F 01 18 Page 9 CS 740 F 01 Properties of Routing Algorithms Deadlock Freedom How can it arise Deterministic necessary conditions shared resource incrementally allocated non preemptible think of a channel as a shared resource that is acquired incrementally source buffer then dest buffer channels along a route route determined by source dest not intermediate state i e traffic Adaptive route influenced by traffic along the way Minimal only selects shortest paths How do you avoid it Deadlock free constrain how channel resources are allocated ex dimension order no traffic pattern can lead to a situation where no packets mover forward 19 How do you prove that a routing algorithm is deadlock free CS 740 F 01 20 Page 10 CS 740 F 01 Proof Technique Examples Why is the obvious routing on X deadlock free Resources are logically associated with channels Messages introduce dependences between resources as they move forward Need to articulate possible dependences between channels Show that there are no cycles in Channel Dependence Graph butterfly tree fat tree Any assumptions about routing mechanism amount of buffering What about wormhole routing on a ring find a numbering of channel resources such that every legal route follows a monotonic sequence no traffic pattern can lead to deadlock 2 1 Network need not be acyclic only channel dependence graph 0 3 7 4 5 21 CS 740 F 01 22 Page 11 6 CS 740 F 01
View Full Document
Unlocking...