Multiprocessor Interconnection Networks Todd C Mowry CS 740 November 3 2000 Topics Network design issues Network Topology Networ ks How do we move data between processors Design Options Topology Routing Physical implementation 2 CS 740 F 00 Evaluation Criteria Latency Bisection Bandwidth Contention and hot spot behavior Partitionability Cost and scalability Fault tolerance 3 CS 740 F 00 P P Bus es P Bus Simple and cost effective for small scale multiprocessors Not scalable limited bandwidth electrical complications 4 CS 740 F 00 Crossba rs Each port has link to every other port Crossbar P P P Low latency and high throughput P M M Cost grows as O N 2 so not very scalable Difficult to arbitrate and to get all data lines into and out of a centralized crossbar Used in small scale MPs e g C mmp and as building block for other networks e g Omega 5 CS 740 F 00 M M Rin gs Cheap Cost is O N Point to point wires and pipelining can be used to make them very fast High overall bandwidth P P High latency O N Ring P Examples KSR machine Hector 6 P P P CS 740 F 00 Tree s Cheap Cost is O N H Tree Latency is O logN Easy to layout as planar graphs e g H Trees For random permutations root can become bottleneck To avoid root being bottleneck notion of Fat Trees used in CM 5 Fat Tree 7 CS 740 F 00 Hypercub es 0 D 1 D 2 D 3 D Also called binary n cubes 4 D 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 8 CS 740 F 00 Multistage Logarithmic Networks 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 Used in many machines BBN Butterfly IBM RP3 9 CS 740 F 00 Omega Network Omega Networ k 000 001 000 001 010 011 010 011 100 100 101 101 110 111 110 111 All stages are same so can use recirculating network 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 10 CS 740 F 00 Butterfly Network Butter fly Networ k 000 001 0 00 001 010 011 010 011 100 100 101 101 110 111 110 111 split on MSB split on LSB Equivalent to Omega network Easy to see routing of messages Also very similar to hypercubes direct vs indirect though Clearly see that bisection of network is N 2 channels Can use higher degree switches to reduce depth 11 CS 740 F 00 k ary ncubes 4 ary 3 cube Generalization of hypercubes k nodes in a string Total of nodes N k n k 2 reduces of channels at bisection thus allowing for wider channels but more hops 12 CS 740 F 00 Real World 2D mesh 1824 node Paragon 16 x 114 array 13 CS 740 F 00 Advantages of LowDimensional 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 LDNs have better hot spot throughput more pins per node than HDNs 14 CS 740 F 00 Embeddings in two dimensions 6x3x2 Embed multiple logical dimension in one physical dimension using long wires 15 CS 740 F 00 Routi ng 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 16 CS 740 F 00 Routing Mechanism need to select output port for each input packet 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 CS 740 F 00 Routing Mechanism cont P3 P2 P1 P0 Source based 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 18 CS 740 F 00 Properties of Routing Algorithms Deterministic route determined by source dest not intermediate state i e traffic Adaptive route influenced by traffic along the way Minimal only selects shortest paths Deadlock free no traffic pattern can lead to a situation where no packets mover forward 19 CS 740 F 00 Deadlock Freedom How can it arise 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 How do you avoid it constrain how channel resources are allocated ex dimension order How do you prove that a routing algorithm is deadlock free 20 CS 740 F 00 Proof Technique 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 find a numbering of channel resources such that every legal route follows a monotonic sequence no traffic pattern can lead to deadlock Network need not be acyclic only channel dependence graph 21 CS 740 F 00 Exampl es Why is the obvious routing on X deadlock free butterfly tree fat tree Any assumptions about routing mechanism amount of buffering What about wormhole routing on a ring 2 1 0 3 7 4 5 22 6 CS 740 F 00
View Full Document
Unlocking...