Formalized QoS Analysis Model For NoCs Based On Network Calculus

With the numbers of transistors and cores integrated on a single chip growing rapidly,the Network-on-Chip architecture has become a promising alternative interconnection fabric for on-chip communication to the classic bus-based or point-to-point ones,since it is featured with par-allel communication,better scalability,modularity and better control of power consumption.The performance of the communication sub-system is as important as those of the computing and stor-age sub-systems,in order to get a predictable high-performance system.From the practical per-spective of view,applications running on both data centers and embedded systems are demanding more real-time guarantees.Therefore,it has long been a major concern for researchers to provide the performance guarantee for the on-chip interconnection networks.Typically,there are two approaches to provide the performance analysis for Network-on-Chips:simulation approach and formalized theoretical approach.Compared with the simulation approach,the formalized theoretical approach,which uses the mathematical methods to model and analyze the systems and relates the performance with its system status,avoids the otherwise inevitable time-consuming simulation experiments.Further,it eliminates the design exploration space to a more reasonable range,which largely accelerates the design process,and gives the de-signers more insight about the implicit relationship between system status and its performances.In this thesis,we propose a formalized performance analysis model for the performance bounds based on a functional formal verification model and network calculus theory,which is called network calculus graph.It involves both the micro-architecture and system configurations,delivering not only the bounds,but also a complete set of methodology to provide quality-of-service guarantees.From the theoretical aspect,the difficulties in getting accurate performance bounds lie in the resource-sharing scenarios which are very common on chip.There are a variety of resource-sharing types,including link-sharing,buffer-sharing,control-loop-sharing or their combinations.Moreover,the diversified behaviours of the flows and service nodes add up to the difficulties in obtaining an accurate bound.In this thesis,we first detail the classic equivalent service curve analysis method,by introducing two different arrival curve models,and two different properties for getting equivalent service curves.Based on these different models and properties,we discuss how to analyze and get the closed-form formula for delay bound and backlog bound,and which model or property can give the most exact description of the injection traffic or service behaviour thus delivering a tighter performance bound prediction.We also propose an arrival-curve-centric method,called local arrival curve method,so as to solve the complexity and scalability problems which the equivalent service curve method suffers from.On the other hand,in order to verify and evaluate the theoretical bounds obtained by the above methods,we define tightness,an argument indicating how much the worst-case delay or backlog observed in simulation can reach its theoretical bound.To make the network most congested in the experiments,in other words,the worst case occur and is easy to observe,we revise our algorithms in implementing different traffic or service behaviours for our network calculus graph simulation platform.We formalize the tightness study into a optimization problem with large configuration exploration space.Then the heuristic algorithm is introduced in guiding the configurations,to-gether with an automated analysis tool.Aided by the automated tightness analysis platform for performance bounds,we discuss how different parameters from the tag flow,interference flows and service nodes,can affect tightness and the network performance.This gives a helpful hint for the designers to understand the system better when making design decisions.