Page 1 1 CS6810 School of Computing University of Utah Routing Algorithms Today’s topics: Deterministic, Oblivious Adaptive, & Adaptive models Problems: efficiency livelock deadlock 2 CS6810 School of Computing University of Utah Review • Network properties are a combination topology topology dependent routing algorithm switch micro-architecture » plus a bunch of things that are “sub-influences” • virtual channels • packet size • error recovery protocol • internal switch data- and control-path • Huge variation of approaches in the research literature goal = cover the breadth » depth is Pandora’s box • specialist expertise requires years not a semester • Terminology phit – physical unit – a per clock transfer flit – flow control unit packet – logical unit of transfer 3 CS6810 School of Computing University of Utah Addressing Modes • Routing model is dependent upon address spec’s source-routed » at each hop – packet field determines exit port • not dissimilar from ethernet table based routing • dynamic congestion independent possible » routing algorithm is simple – do what the source says absolute » topology dependent definition of the destination • topological basis for the address – e.g. NEWS • which way to go? – topology dependent – simple or complex calculation – twisted torus – complex – 2D mesh – simple relative » topology dependent • relative path based on where I am now – GPS like (calculate here – destination) difference – simple example is 2D mesh – NEWS offset 4 CS6810 School of Computing University of Utah Routing Models • Note terminology varies over the years » this one is Dally-speak • from the excellent text by Dally & Towles • Deterministic fixed route between source-destination pairs » problem • no dynamic congestion avoidance • Oblivious dynamic path choice BUT – independent of load » e.g. static load balancing at source • Adaptive load based routing » TRICK: can local observation of load = global optimum?Page 2 5 CS6810 School of Computing University of Utah Routing Model Issues • Deterministic what happens if something fails » need to determine failure point • how? – timeout – how long should you wait? » update routing tables • depending on topology – request/reply traffic may conflict • Oblivious & Adaptive same request/reply conflict alternate paths provide opportunity » topology dependent however • consider – quad mesh – fat-tree/folded Clos – n-dimensional networks 6 CS6810 School of Computing University of Utah Adaptive vs. Non-Adaptive • Deterministic routing guarantees in order packet delivery delivery • Oblivious and Adaptive routing packets may arrive out of order • Out of order issues reassembly required at end point packet header overhead » packet #, total packets this message fields required » packet overhead is an issue • look at ethernet – min packet size = 64 bytes – 48 byte header for IP – 48/64 = 75% overhead – max packet size = 1518 bytes – 48/1518 = 3% overhead » BUT packet latency is an issue • route around congestion = out of order – tradeoffs? 7 CS6810 School of Computing University of Utah Routing Models II • At each hop = flow control dependent Store and forward » flow-control: packet based » receive entire packet, check correct, route » latency non-optimal but minimize occupancy Wormhole » flit != packet • digest header & route » packet may now occupy multiple switches • head of line blocking problem now has greater “extent” Virtual cut-through » packet based flow control » route decision doesn’t need to wait for entire packet to arrive 8 CS6810 School of Computing University of Utah Time/Space Viewpoint Time-Space diagrams H B B B T H B B B T H B B B T Channel 0 1 2 3 Channel H B B B T H B B B T H B B B T 0 1 2 3 Store & Forward Virtual Cut-throughPage 3 9 CS6810 School of Computing University of Utah Routing Properties • Key issues deliver the packet to the prescribed destination » functional correctness issue deadlock avoidance » break • incremental claim & circular dependence • e.g. 5 philosophers problem livelock avoidance » avoid lots of action – no progress situation • harder to detect w/ local view • hence packet must carry history – e.g. ethernet “time to live” + end to end protocol capability – OR route without livelock possibility avoid hop specific “head of line blocking” » previous packet goes to destination X » next packet goes to destination Y • but can’t get through the current hop since X packet holds the buffer 10 CS6810 School of Computing University of Utah Head of Line Blocking • Enter virtual channels Jose Duato (UPC) book – definitive source basic idea » create packet dependent flow – call it a VC » each VC • separately buffered and routed • one flow blocked to different destination – let other flow proceed – still in order delivery unless adaptively routed • VC’s serve multiple purposes head of line blocking priority – may be age based » express channel for control packets deadlock avoidance » special “last VC” deterministic 11 CS6810 School of Computing University of Utah Classic Stages • Route determine where packet is destined • VC allocation decide which VC packet is assigned to » how? • bump VC at ever hop – buffering overhead • bump when HOL blocking indicated – better • Switch allocation arbitrate for route through the datapath » switch µarch dependent • Switch traversal move packet to output port » output buffered? • speed matching • link retry 12 CS6810 School of Computing University of Utah Deadlock Avoidance • Critical needs avoid cycles » packet can’t come back to the same place avoid request reply
View Full Document
Unlocking...