High-Performance Networks for Dataflow Architectures Pravin Bhat

High-Performance Networks for Dataflow Architectures Pravin Bhat Andrew Putnam

Overview Motivation & Design Constraints Network design Performance Adaptive Routing Conclusion

Overview Motivation & Design Constraints Network design Performance Adaptive Routing Conclusion

Motivation Signal delay on wires is more important than transistor switching speed Seriously decreased reliability in future processes Factory testing will not be possible Expect 20% of transistors to be DOA Expect 10% more to die over several months Dataflow is an answer, but the network is currently a bottleneck

Dataflow Characteristics Unpredictable traffic Highly bursty traffic Cannot pre-allocate resources Quick delivery of bursts is critical Nodes are not guaranteed to consume messages Potential for livelock & deadlock

Overview Motivation & Design Constraints Network design Performance Adaptive Routing Conclusion

Network Requirements High-Performance during bursts Area efficient Guarantee message delivery Deadlock & Livelock free Fault Tolerant Regular 2-D physical structure

Topology On-chip - must be implementable in 2-D Regular tiled structure suggests: Grid Torus Hypercube Fat Tree Hypercube is difficult to route, scale Fat Tree has a single point of failure

Routing Static routing does not provide essential fault tolerance Use a modified Virtual Channel algorithm VC guarantees deadlock free if nodes consume messages Dynamically adaptive to handle transient faults & congestion Initial studies used static routing

Flow Control Resource reservation not possible Long-latency wires prohibit handshakes Send messages assuming accept Buffer just enough to allow receiver to send reject signal on subsequent clock cycle

Deadlock-Free Operation Nodes cannot always consume messages Add a dedicated channel to and from memory Adds 8% area overhead Rotate stalled operands out of PEs to ensure forward progress Send first operand back at a faster rate to avoid livelock

Overview Motivation & Design Constraints Network design Performance Adaptive Routing Conclusion

Performance Ran network-centric simulations 20 billion instructions Spec2000, Splash2, and Dataflow benchmarks Goal is to find optimum balance of: Number of Virtual Channels Queue Length Link Bandwidth Packets per message

Virtual Channels 2.5 2 ocean (G) lu (G) fir (G) art (G) mcf (G) ocean (T) lu (T) fir (T) art (T) mcf (T) 1.5 1 Performance (Runtime) 0.5 0 0 4 8 Virtual Channels 12 16

Queue Length 2 ocean (G) lu (G) fir (G) 1.6 art (G) mcf (G) ocean (T) lu (T) 1.2 fir (T) art (T) Performance (Runtime) mcf (T) 0.8 0 4 8 12 16 20 24 28 32 36 Queue Length 40 44 48 52 56 60 64

Link Bandwidth 2 1.8 ocean (G) lu (G) fir (G) art (G) mcf (G) ocean (T) lu (T) fir (T) art (T) mcf (T) 1.6 1.4 1.2 Performance (Runtime) 1 0.8 0 4 8 Bandwidth 12 16

Link Width 1.2 1 ocean (G) lu (G) 0.8 fir (G) art (G) mcf (G) 0.6 ocean (T) lu (T) 0.4 fir (T) art (T) Performance (Runtime) 0.2 mcf (T) 0 0 8 16 24 32 40 Packets per Message 48 56 64

ASIC Model Performance must be balanced with area Developed RTL model of WaveScalar network architecture 90 nm process ASIC standard cell library Timing per link: Grid links: 2.76 ns Torus links: 6.16 ns Network switch is 11.6% of chip area

Virtual Channels 3.5 3 ocean (G) lu (G) 2.5 fir (G) art (G) 2 mcf (G) ocean (T) 1.5 lu (T) fir (T) 1 Performance / Area art (T) mcf (T) 0.5 0 0 2 4 6 8 10 Virtual Channels 12 14 16 18

Link Bandwidth 1.4 1.2 ocean (G) lu (G) 1 fir (G) art (G) 0.8 mcf (G) ocean (T) 0.6 lu (T) fir (T) 0.4 Performance / Area art (T) mcf (T) 0.2 0 0 2 4 6 8 Number of Links 10 12 14 16

Queue Length 3 2.5 ocean (G) lu (G) fir (G) art (G) mcf (G) ocean (T) lu (T) fir (T) art (T) mcf (T) 2 1.5 1 Performance / Area 0.5 0 0 8 16 24 32 Queue Length 40 48 56 64

Overview Motivation & Design Constraints Network design Performance Adaptive Routing Conclusion

Virtual Channels Flow Control In hardware only Headof-Queue can be dequeued in one clock cycle If the first message in a queue is blocked then every message behind it is blocked The network utilization suffers due to idle links

Virtual Channels Flow Channel Virtual Channels – several small queues instead of one long queue Decouples buffer resources from link resources Increase network throughput by increasing link usage

Dimension Order Routing Old WaveScalar Routing Protocol Network topology is a static grid Packets first travel to the correct xcoordinate and then to the correct ycoordinate Low network utilization from not using all available paths Not fault tolerant

Adaptive Routing Progressively chooses longer routes instead of waiting for an unavailable resource High Network Utilization Fault tolerant Can cause deadlock

Deadlock Free Adaptive Routing Some Virtual Channels are reserved for Dimension Order Routing, rest used for Adaptive routing Every time a packet is routed in the wrong direction the Dimension Reversal count incremented No packet is allowed to wait in a virtual channel with a packet that has a lower Dimension reversal count Mathematically proven to be deadlock free.

Virtual Channels 3.5 3 ocean (G) lu (G) fir (G) art (G) mcf (G) ocean (T) lu (T) fir (T) art (T) mcf (T) 2.5 2 1.5 1 Performance (Runtime) 0.5 0 0 4 8 Virtual Channels 12 16

Queue Length (Adaptive Speedup) 2 ocean (G) lu (G) fir (G) 1.6 art (G) mcf (G) ocean (T) lu (T) 1.2 fir (T) art (T) Performance (Runtime) mcf (T) 0.8 0 4 8 12 16 20 24 28 32 36 Queue Length 40 44 48 52 56 60 64

Link Bandwidth (Adaptive Speedup) 2 1.8 ocean (G) lu (G) fir (G) art (G) mcf (G) ocean (T) lu (T) fir (T) art (T) mcf (T) 1.6 1.4 1.2 Performance (Runtime) 1 0.8 0 4 8 Bandwidth 12 16

Conclusion Best performance per area with: 2 Virtual Channels 2 Links 2-4 entries per queue Torus Topology Adaptive Routing Dataflow chip networks can be highperformance at reasonable area