Multiprocessor Interconnection Networks Todd C Mowry CS 740 November 19 1998 Topics Network design space Contention Active messages Network s Design Options Topology Routing Direct vs Indirect Physical implementation Evaluation Criteria Latency Bisection Bandwidth Contention and hot spot behavior Partitionability Cost and scalability Fault tolerance 2 CS 740 F 98 Buse s P P P Bus Simple and cost effective for small scale multiprocessors Not scalable limited bandwidth electrical complications 3 CS 740 F 98 Crossbar s Each port has link to every other port Crossbar P P Low latency and high throughput P P Cost grows as O N 2 so not very scalable M M M M 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 4 CS 740 F 98 Rings Cheap Cost is O N Point to point wires and pipelining can be used to make them very fast High overall bandwidth P P P Ring High latency O N P P P Examples KSR machine Hector 5 CS 740 F 98 Trees 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 channels are wider as you move towards root Fat Tree 6 CS 740 F 98 Hypercube s 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 7 CS 740 F 98 Multistage Logarithmic Networks 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 8 CS 740 F 98 Omega Network Omega Networ k 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 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 98 Butterfly Network Butter fly Networ k 000 000 001 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 Used in BBN machines 10 CS 740 F 98 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 11 CS 740 F 98 Routing Strategies and Latency Store and Forward routing Tsf Tc D L W L msg length D of hops W width Tc hop delay Wormhole routing Twh Tc D L W of hops is an additive rather than multiplicative factor Virtual Cut Through routing Older and similar to wormhole When blockage occurs however message is removed from network and buffered Deadlock are avoided through use of virtual channels and by using a routing strategy that does not allow channel dependency cycles 12 CS 740 F 98 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 Factors that limit end to end latency LDNs number of hops HDNs length of message going across very narrow channels LDNs have better hot spot throughput more pins per node than HDNs 13 CS 740 F 98 Performance Under Contention Types of Hot Spots Module Hot Spots Lots of PEs accessing the same PE s memory at the same time Possible solutions suitable distribution or replication of data high BW memory system design Location Hot Spots Lots of PEs accessing the same memory location at the same time Possible solutions caches for read only data updates for R W data software or hardware combining 15 CS 740 F 98 NYU Ultracomputer IBM RP3 Focus on scalable bandwidth and synchronization in presence of hot spots Machine model Paracomputer or WRAM model of Borodin Autonomous PEs sharing a central memory Simultaneous reads and writes to the same location can all be handled in a single cycle Semantics given by the serialization principle as if all operations occurred in some unspecified serial order Obviously the above is a very desirable model Question is how well can it be realized in practise To achieve scalable synchronization further extended read write operations with atomic read modify write fetch op primitives 16 CS 740 F 98 The Fetch Add Primitive F A V e returns old value of V and atomically sets V V e If V k and X F A V a and Y F A V b done at same time One possible result X k Y k a and V k a b Another possible result Y k X k b and V k a b Example use Implementation of task queues Insert myI F A qi 1 Q myI data infinite full myI 1 Q Delete myI F A qd 1 while full myI full qd qi data Q myI full myI 0 17 CS 740 F 98 The IBM RP3 1985 Design Plan 512 RISC processors IBM 801s Distributed main memory with software cache coherence Two networks Low latency Banyan and a combining Omega Goal was to build the NYU Ultracomputer model P Mem Map unit Cac he NI interleave main memory L G NETWORKS moveable boundary between local and global storage P Mem Map unit Cac he NI interleave main memor y Interesting aspects L G Data distribution scheme to address locality and module hot spots Combining network design to address synchronization bottlenecks 18 CS 740 F 98 Combining Network Omega topology 64 port network resulting from 6 levels of 2x2 switches Request and response networks are integrated together Key observation To any destination module the paths from all sources form a tree Omega Network 19 000 000 001 001 010 010 011 011 100 100 101 101 110 110 111 111 CS 740 F 98 Combining Network Details Requests must come together locationally to same location spatially in queue of same switch and temporally within a small time window for combining to happen B combining queue M forward requests B queue M queue insert wait buffer reverse replies 20 combining queue M …
View Full Document
Unlocking...