Stay In Your Lane: A NoC With Low-overhead Multi-packet Bypassing

Table I: Comparison of different deadlock freedom solutions.ProposedSolutionsTurn Restrictions [7]Escape VCs [8]–[10], [14]Virtual Networks [23]SPIN [31]SWAP [26]DRAIN [24]Pitstop [13]Our Method: FastPassNoDetectionProtocol DeadlockFreedomNetwork DeadlockFreedomFull sroutingXXX7XXXX77X77XXXXX7XXXXX77 7XXXXX7777777X7 7 7 7 7 7 XX7 XX7 X7 7 XXXXX77XX* Must use multiple VNs to avoid protocol-level deadlock.** No full path diversity within the escape VC.*** DRAIN can work with no VNs; however, it requires a large amount of buffer which is non-minimal [13].**** Cannot support adaptive routing.***** As the network size increases, the time for detecting/resolving deadlock increases. FastFlow: A new flow control scheme allowingFastPass-Packets to make forward progress bufferlesslyevery cycle regardless of credit availability.Regular Pass: A credit-based flow control which isused when packets do not use the FastFlow control.Regular Packets: Packets using regular pass to makeforward progress.B. FastFlowThe goal of this work is to design a high-throughput andlow-cost solution to minimize the head of line blockingand provide network- and protocol-level deadlock freedom in NoCs. To this end, we propose an efficient flowcontrol called FastFlow. Packets are routed using eitherFastFlow or regular pass flow (i.e., credit-based) control.A FastPass-Packet traversing via FastFlow takes precedenceover regular packets. A FastPass-Packet reaches its destination bufferlessly using a minimal path; no misrouting isemployed. As a result, buffer turnaround time is eliminatedincreasing throughput. To maximize throughput, FastPassallows multiple FastPass-Packets to traverse the networkat any given time. However, to guarantee no collisionsbetween FastPass-Packets, FastPass creates multiple nonoverlapping paths (FastPass-Lanes) allowing a single routeraccess to each partition in a time-multiplexed way. Thuslinks of each partition only propagate one FastPass-Packetin a given slot time. Section III-C1 demonstrates howFastPass guarantees multiple FastPass-Packets with nonoverlapping paths.C. Detailed Algorithm1) TDM-based Non-overlapping FastPass-Lanes:FastPass allows multiple FastPass-Packets to traverse thenetwork simultaneously to maximize throughput. However,since the FastPass-Packets traverse bufferlessly, they mustnot collide with each other. To guarantee no collisionbetween FastPass-Packets, FastPass creates multiplepre-defined non-overlapping paths in the network, calledFastPass-Lanes. This problem is similar to maintainingnon-interference in NoCs. Non-interference means thatpackets from one application should have no effect on thedelivery of packets from other applications [36]. Here primerouters are equivalent to the applications. The goal is toimplement such a non-interference approach that guaranteesno collision between FastPass-Packets.To this end, FastPass breaks the topology into P separate partitions; there is one prime router in each partition.This spatial partitioning provides the foundation for ourcollision-free FastPass-Packet traversals. Assuming a meshtopology, P could be the number of columns/rows. An efficient way to support multiple FastPass-Lanes with no overlap is by time-multiplexing the physical links. FastPassprovides recurrent fixed time slots during which the linksof each partition are only permitted to propagate a singlepacket from one prime router. When the time slot elapses,the links of each partition handle the FastPass-Packets ofa different prime. This rotation continues until each primerouter has a FastPass-Lane with every other router. The timeneeded for a such coverage is called a phase. Each phaseconsists of multiple time slots. In other words, there existsa fixed time slice for each phase where every prime routerwould have the opportunity to have a FastFlow with everyother router in the network. In the next phase, the next setof prime routers follow the same procedure. Note that allrouters along a single partition are possible destinations sothe number of FastPass-Lanes a prime router has to rotatethrough is very limited and scales gracefully.This time-multiplexing scheme guarantees that the pathused by each prime router is completely independent of theother primes’ paths. As a result, the packets of each primecannot collide with others providing collision-free traversal.As an example, Fig. 1 demonstrates the non-overlappingFastPass-Lanes in a 3 3 mesh network.The prime router within each partition is chosen contiguously meaning that the prime ability is given to thenext adjacent router within the partition after finishing eachphase. If the current prime is located in the last row, therouter in the first row of the partition will be the next primerouter. Note that the current prime router in the last row

2R0 R0 R0R1 R1 RR1 2R0 R0 R01 R1 R21R2 R2 R0R2 R R02R0 RR0 1R0 RR01R1 RR12R1 RR12R2 R2 R0R2 R R02R0 RR0 1R0 RR01R1 RR12R1 RR12R2 R2R2 R2R3 R3 R3R4 R4 RR45R3 R3 R34 R4 RR54R5 R5 R3R5 R R35R3 RR34R3 RR34R4 RR45R4 RR45R5 R5 R3R5 R R35R3 RR3 4R3 RR34R4 R45R4 RR45R5 R5R5 R5R6 R6 R6R7 R7 RR78 R8 R8 R6 R6R6 R6 R67 R7 RR87 R8 R8R6 R6P0 P0 P0 P1 P1 PP1 2 P2 P2P0 P0P0 P0 PP0 1 P1 P21 P2 PP2 0 P0(a) T KRR6 7RR67P0P1P0P1(b)R7 RR78R7 RR78P1 PP12P1 PP1T 2 K2R8R8P2P2R8 R6R8 R6P2 P0P2 P0R6R6P0P0RR67RR6 7P0P1P0P1R7 R78R8 R8R7 RR7R8 R88P1 PP12P2 P2P1 PP1P2 P22(c) T 3 KR0 R0 R0R1 R1 RR1 2R0 R0 R01 R1 R21R2 R2 R0R2 R2R0R0 RR0 1R0 RR01R1 RR12R1 RR12R2 R2 R0R2 R2 R0R0 RR0 1R0 RR01R1 RR12R1 RR12R2 R2R2 R2R3 R3 R3R4 R4 RR45R3 R3 RR34 R4 RR54R5 R5 R3R5 R5RR3 RR34R3 RR34R4 RR45R4 RR45R5 R5 R3R5 R5 R3R RR3 4R33 RR34R R45R44 RR45R R5R55 R5R7 RR78R7 RR78P1 PP12P1 PP12T 5 KR8 R8 R6R8 R8 R6P2 P2 P0P2 P2 PR RR67R66 RR67P P0P1P00 P0P1R RR78R R8R77 RR7R88 R88P PP12P P2P11 PP1P22 P22(f) T 6 KR6 R6 R6R7 R7R6 R6 RR67 R7P0 P P0 P1 P01P0 P0 PP0 1 P13RR78 R8 R8 R6 R6RR87 R8 R8R6 R6PP1 2 P2 P2P0 P0P1 P2 P2P2P0 P0RR6 7RR67P0P1P0P1(e)(d) T 4 K0R0R1R2R0R1R2R0R0R1R1 R2R2R0R0 R1R1 R2R2R0R0 R1R1 R2R2R3R4R5R3R4R5R3R3R4R4 R5R5R3R3 R4R4 R5R5R3R3 R4R4 R5R5R6R7R8R6R7R8R6R6 R7R7 R8R8R6R6 R7R7 R8R8R6R6 R7R7 R8R8P0P1P2P0P1P2P0P0P1 P2P2P0P0P1 P2P2P0P0P1 P2P2(g) T 7 KP1P1(h) T 8 KP1(i) T 9 KFigure 1: TDM-based non-overlapping paths: To ensure no collisions between packets, FastPass breaks the topology into P separate partitions (i.e., 0,1 and 2) each of which has one prime router (i.e., green, orange and blue); First phase (a, b, c): (a) In the first K cycles, the green prime router can coverthe routers located in P0 : R0 , R3 , and R6 ; the orange one has access to the P1 routers: R1 , R4 , and R7 ; the blue prime router has an isolated path tothe P2 routers: R2 , R5 , and R8 . When the first time slot elapses, the links of each partition switches to handle the packets of other primes; (b) Links ofP0 , P1 , and P2 propagate the packets from blue, green and orange primes, respectively. (c) In this step, the links of P0 , P1 , and P2 handle packets fromorange, blue and green primes, respectively. this switching continues until each prime has covered all the routers in the network, indicating the completionof the phase. Second phase (d, e, f) and third phase (g, h, i) follow the same approach.must send the signal N cycles ahead of the phase schedulefor a N N mesh to account for the N hops needed for thesignal to reach the first row from the last row. This switchingcontinues to give each router the opportunity to be the prime.Thus, the completion of each phase requires a fixed numberof steps which depends on the number of partitions. Eachstep also needs a fixed number of cycles (K) to complete.This time slot is set at design time.12) FastPass for throughput enhancement: Each primerouter has multiple chances to provide FastFlow traversalfor its packets over the FastPass-Lanes. Each FastPass-Laneprovides an isolated path from each prime router to therouters of one single partition. For each FastPass-Lane, eachprime router examines each input buffer in a round-robinfashion (e.g., injection buffers, South, N orth, East andW est) to see if there is a packet at the head of inputbuffer destined for a router located in the correspondingpartition. Once such a packet is found for the input buffer,1 Qn5 discusses how this value is pre-computed.Req. QRes. QEjection BufferReq. QRes. QInjection BufferThe prime routerselects A as the FastPass-PacketA2R01Request QueueResponse QueueR13R24A Req. QRes. QEjection BufferReq. QRes. QInjection Buffer1APrime RouterRegular RouterFastPass-LaneReturning PathSequence NumberFastPass-PacketFigure 2: The prime router (i.e., R0 ) upgrades a request packet (A) to aFastPass-Packet so that it can traverse the current FastPass-Lane to reachthe intended destination (i.e., R2 ). On the arrival, the packet can be ejectedto the respective ejection queue.the prime router upgrades it to the FastPass-Packet bysending it through FastFlow to reach the destination. Uponarrival at the destination, the FastPass-Packet is ejected bythe network interface assuming the respective ejection queue

The prime routerdrops C making a room for AAThe prime routerReq. Q C6 selects A as the FastPass-PacketRes. Q1R0Ejection BufferA5Req. QThe request queue is2Res. Qreserved for AR1Injection Buffer4B Req. Q3Res. QR2Ejection BufferReq. QRes. QInjection BufferRequest QueueResponse Queue1ABPrime RouterRegular RouterFastPass-LaneReturning PathSequence NumberFastPass-PacketRegular PacketFigure 3: When the ejection queue of the destination router is full: Theprime router (i.e., R0 ) selects a request packet (A) as a FastPass-Packet.However, it faces a full ejection queue when it reaches the destination (i.e.,R2 ). In this step, the destination router reserves the intended queue for A.A goes back to the prime router to reside in the request injection queue ofthe prime. However, the queue is full with an injection packet (i.e., C). Theprime router drops C to make a room for the rejected FastPass-Packet (A).Note that if the request injection queue is not full, no dropping is required.is not full (Fig. 2).2 Thereafter, the prime router examinesthe remaining input buffers in a round-robin manner for thecurrent FastPass-Lane. Note that the time slot (K) to useof each FastPass-Lane is fixed and large enough to give theprime router sufficient time for checking all the input buffersand sending out the FastPass-Packets over the path.3 In thenext time slot, when the prime router has access to anotherFastPass-Lane, the router follows the same procedure. Wheneach phase elapses, the prime status moves to the next setof pre-defined routers. Since the time slot (K) is fixed,all the new prime routers are enabled simultaneously. Thisprocedure continues indefinitely through every router.Qn1: Does a packet need to wait for the desired FastPassLane to be available? As mentioned in Sec. III-C1, eachprime router eventually covers all routers in the networkduring each phase. If the current FastPass-Lane does notcover the intended destination for a packet, the packet needseither to wait until the intended FastPass-Lane becomesavailable or can traverse the router through the regular pass.Note that the regular traversal is always available unlessthere is a deadlock. In the case of deadlock, the intendedFastPass-Lane eventually becomes available making forwardprogress for the deadlocked packet. Note that in the absenceof deadlocks during low load, packets do not wait for aFastPass-Lane to become available; FastPass kicks in asload increases.3) FastPass as Deadlock Removal with No Virtual Networks: Apart from the throughput enhancement,FastPass provides both protocol- and network-level deadlock freedom. Deadlock freedom is guaranteed because of2 Sec.III-C4 and Qn 4 discuss when ejection queues is full.3 See Qn 5 for more details.the following: (1) eventually each router gets a chance tobe upgraded to a prime router, (2) a prime router canupgrade the packet at the head of each input buffer to aFastPass-Packet, regardless of its message type, (3) wheneach time slot elapses, the prime router has access to adifferent FastPass-Lanes until it covers all routers in thenetwork. As a result, the movement of all packets along thedesired FastPass-Lane is guaranteed. Therefore, FastPassensures that any packet of any message class will eventuallyhave the opportunity to reach its destination router throughthe FastPass. Sec. III-D provides a detailed proof ofcorrectness. In addition, FastPass allows multiple primerouters in the network–one per partition. Allowing multipleprime routers results in resolving multiple protocol-leveldeadlocks simultaneously.4) Dynamic Bubble: Although the prior work has shownthat the ejection queues are significantly underutilized andthe ejected packets are consumed almost immediately [13],we need to consider what would happen if the ejection queueis full. When the FastPass-Packet arrives at the destinationrouter, it is possible that the respective ejection queue is full,preventing the FastPass-Packet from being ejected. Sincethe main goal of this work is increasing throughput, aprime router increases the credit for the upstream router(i.e., indicating available slot) as soon as a FastPass-Packetdeparts the router. Therefore, it is not possible for a FastPassPacket facing a full ejection queue (at the destination) toreturn to its prime router and reoccupy its previous bufferentry. To handle this challenge, we use a subtle droppingapproach providing a bubble within the prime router. In thisapproach, some packets are potentially droppable.To make the bubble, the prime router drops the injection request packet residing in the request injection queue,making an empty entry for the rejected FastPass-Packet(Fig. 3).4 Note that if the request injection queue is not full,no dropping happens. Thus the FastPass-Packet is routedback to its prime router through the minimal returningpath and then resides in the recently created, available slot.Note that collision is not possible between the FastPassLanes and the returning paths as shown in Fig. 4. Also thedestination router pro-actively reserves the intended queueof the ejection buffer for the rejected FastPass-Packet oncethe intended ejection queue gets free space.5 Not until the rejected FastPass-Packet resides in the intended ejection queueat the destination router, are other packets allowed to use it.Therefore, using the dropping and reservation approaches,the FastPass-Packet is eventually guaranteed to be acceptedby the intended destination router. The proposed droppingapproach has the following distinctive characteristics settingit apart from other methods [17], [33]:4 If the rejected FastPass-Packet is a data packet, then multiple requestinjection packets might be dropped.5 Qn 4 discusses that the ejection queues can never be full indefinitely.

R0R1R2R0R1R2R3R4R5R3R4R5R6R7R8R7R81212Partitions: 0(a) First K CyclesR6Partitions: 0(b) Second K CyclesR0R1R2R3R4R5R6R7R8Partitions: 012(c) Third K CyclesFigure 4: The FastPass-Lanes and the returning paths when the routerslocated on the diagonal are the prime routers. Dotted lines represent thereturning paths for FastPass-Lanes. There is no overlap between theseminimal paths.1) The dropping happens when a FastPass-Packet encounters a full ejection queue at the destination routerand a full request injection queue at the prime router.The likelihood of such a sequence of events is rare.2) Since only the injection request packet is dropped, itcan simply be regenerated using the information provided by the miss status handling registers (MSHRs)without changing the coherence protocol or usingextra buffers. Note that the MSHRs keep track ofwhat misses a core is waiting for. Since the droppedpacket’s MSHR is local, the router does not have tocommunicate with a distant node to regenerate thepacket. Hence the dropped request packet can be easilyregenerated.3) Last but not least, the dropped request packet has notleft the source router yet. Therefore, this dropping willnot hurt performance.Qn2: Is it possible for the rejected FastPass-Packet,residing in the request injection queue of the primerouter, to be dropped to make a room for a new rejectedpacket? No: after that the rejected FastPass-Packet occupiesthe request injection queue of its prime router, it has twooptions to make forward progress: traverse as a regularpacket or traverse as a new FastPass-Packet. For the latter,there are two possible scenarios:1) The rejected packet was the last packet that the primerouter upgraded; thus the router is not prime during thecurrent phase. In this scenario, the packet needs to waituntil the router turns into the prime again if a regulartraversal is impossible. To ensure that we never dropa rejected FastPass-Packet, in a given FastPass-Lane,each prime router always starts examining the injection buffers first (starting with the request injectionqueue) and then moves on to the remaining inputbuffers.2) The router is still prime and is going to examineother remaining input buffers for the current FastPassLane. In other words, the prime router has checkedthe injection buffer and it is the turn of the otherinput buffers. To avoid dropping the previous rejected packet, the previous rejected packet pro-activelymoves to the empty slot which is available whenthe new FastPass-Packet departs the prime router. Toprovide such a transfer, the router microarchitectureincludes connections between the injection buffer andall input buffers.6Therefore, FastPass guarantees dropping will onlyoccur if needed for the injection request packets, which havenot left the source router yet. Both of these scenarios areshown in Fig. 5.Qn3:What if the ejection port is busy when the FastPassPacket arrives? This situation happens when the FastPassPacket arrives at the destination router while another packetis in the middle of ejection process. There are two scenariosfor this case:1) The first scenario is that the respective ejection queueof the destination router was reserved for the FastPassPacket. This means that the FastPass-Packet faced afull ejection queue at the destination router causingthe intended queue to be reserved for the packet. Thepacket reaches the destination again while anotherpacket is being ejected to a different queue (not thereserved one). In this case, the FastPass-Packet isgiven higher priority over the ongoing ejection; theongoing ejection is stalled and the FastPass-Packet isejected to the respective ejection queue. Not until theFastPass-Packet gets ejected from the network can thecurrent ejection packet use the ejection port. Sincethe intended ejection queue for the FastPass-Packetwas reserved before, it is impossible that the stalledejection packet is aiming for the same queue.2) The second scenario happens when the respective ejection queue of the destination router was not reservedbefore. In other words, this is the first time that theFastPass-Packet arrives at the router. In this case, asdiscussed in Sec. III-C4, while the FastPass-Packetgoes

NoC design guarantees a cornerstone of correctness by being free of deadlock. A deadlock happens when a set of agents sharing a set of resources wait indefinitely to acquire the resources in a cyclic dependence. Within a NoC, packets are the set of agents while buffers are the set of resources storing incoming packets as they move in the NoC to