Calculus Models And Performance Analysis For Networks-on-chip

With the rapid development of semiconductor technology, the number of cores ona single chip continues to increase, the global interconnects would cause severe on-chipsynchronization errors, unpredictable delays, and high power consumption. To mitigatethese effects, the Network-on-Chip (NoC) approach emerged recently as a promising al-ternative to classical bus-based and point-to-point (P2P) communication architectures.Aside from better predictability and lower power consumption, the NoC approach offersgreater scalability compared to previous solutions for on-chip communication. Perfor-mance analysis has been a major concern for NoC and plays an increasingly importantroleinbuildingpredictablecommunicationsystem, providingend-to-endQoSguaranteesand speeding up the design space exploring. This thesis employs network calculus to per-form systematic modeling and performance analysis on NoCs with focusing on per-flowend-to-end delay bound. The effects of network contentions, topologies, flow control,switching strategies and buffer size are analyzed on the communication performance inpacket-switching NoCs with best-effort services. The main contributions are:(1) Contention model for multiple flows sharing resources in NoCsIn packet-switching NoCs, network flow contention scenarios are diverse and com-plicated. The contention scenarios the tagged flow may experience can be classified intothree patterns, Nested, Parallel and Crossed. Based on these patterns, any complex con-tentionscenariocanbedecomposedintothebasicpatternsandexpressedwithacontentiontree. This contention tree model captures not only the tagged flow's contention with otherinterfering flows along its routing path but also the indirect contention experienced bythe interfering flows. We scan the tree to compute the output arrival curves of the flowstraversing each branch in the contention tree. Then we derive the equivalent service curvefor the tagged flow traversing the trunk of tree and calculate its delay bound. We proposeananalysisprocedurewhichcontainstwo mainalgorithms: 1)constructacontentiontree;2) scan the tree and compute the equivalent service curve for the tagged flow. We derivea closed-form formula to calculate the delay bound for all-to-one gather communication,which is an important collective operation for parallel processing. Experimental resultsvalidate the consistency of simulated maximum delays and our analytical bounds. Wealso perform comparative analysis on Bakhouya's model, Fidler's model and ours. (2) Comparative analysis of communication performance for 2D and 3D NoCsAdvanced integration technologies enable the construction of NoC from two dimen-sions to three dimensions. 3D NoCs can improve average communication performancebecause of the possibility of using the additional dimension to shorten communicationdistance. We study the worst-case communication performance in regular k-ary-2-meshnetworks and their 3D counterparts. Through both analysis and simulation, we show that,while the average performance in 3D NoCs is better than that of their 2D counterparts,the worst-case communication performance in 3D NoCs may be worse than that of their2D counterparts. The worst-case delay is more sensitive to the vertical link bandwidth,the network size and traffic burstiness. The 3D worst-case delay bound becomes worsethan the 2D worst-case delay bound for lower vertical link bandwidth, smaller topologysize and larger traffic burstiness. This suggests that a thorough investigation on not onlyaverage but also worst-case performance is necessary when dimensioning the networktopology from 2D to 3D.(3) Analyzing credit-based link-level flow control for on-chip networksCredit-based router-to-router flow control is one main link-level flow control mech-anism proposed for NoCs. Based on network calculus, we analyze its performance andoptimal buffer size. To model the feedback control behavior due to credits, we introducean abstract network service element called flow controller. Then we derive its servicecurve, and further the system service curve with theorematic forms. In addition, we giveand prove a theorem that determines the optimal buffer size guaranteeing the maximumsystem service curve. Moreover, assuming the latency-rate server model for routers, wegive closed-form formulas to calculate the flit delay bound and optimal buffer size. Ourexperiments with real on-chip traffic traces validate that our analysis is consistent and theoptimal buffer size is exact.(4) Analyzing wormhole switching with virtual channels in NoCsBased on network calculus, we derive per-flow worst-case flit delay bounds fordeadlock-free virtual-channel (VC) wormhole networks. In such networks, packet trans-mission may be stalled due to lack of credits, failure of switch allocation and VC alloca-tion. Webuildanalyticalmodelsforflowsunderthesestallingconditions. Bysequentiallyapplyingtheanalyticalmodelsforflowcontrolandlinksharing,wecanobtainasimplifiedanalysis model, which eliminates the feedback control and link contention. As keeping only the buffer sharing and network structure of initial model, this model is called buffer-sharing analysis network. The problem is transformed into the contention tree model, toderive per-flow end-to-end equivalent service curve which the tandem of routers provide.We propose an algorithm to construct the buffer-sharing analysis network and summarizea general analysis procedure to derive the delay bound. The derivation of delay boundand closed-form formulas are presented by supposing that the arrival curve conforms tothe affine function and the service curve follows the latency-rate function.In summary, we aim to drive per-flow end-to-end delay bound. Based on networkcalculus, we have proposed four calculus models of contention tree, comparative analysisof 2D and 3D topologies, flow control and wormhole switching, which establish a set ofcomplete deterministic approaches for NoCs'performance analysis, and develop a newapplication field for this emerging mathematical theory of network calculus.