Network on Chip Performance Bound and Tightness

Detta är en avhandling från Stockholm : KTH Royal Institute of Technology

Sammanfattning: Featured with good scalability, modularity and large bandwidth, Network-on-Chip (NoC) has been widely applied in manycore Chip Multiprocessor (CMP) and Multiprocessor System-on-Chip (MPSoC) architectures. The provision of guaranteed service emerges as an important NoC design problem due to the application requirements in Quality-of-Service (QoS).Formal analysis of performance bounds plays a critical role in ensuring guaranteed service of NoC by giving insights into how the design parameters impact the network performance. The study in this thesis proposes analysis methods for delay and backlog bounds with Network Calculus (NC). Based on xMAS (eXecutable Micro-Architectural Speci?cation), a formal framework to model communication fabrics, the delay bound analysis procedure is presented using NC. The micro-architectural xMAS representation of a canonical on-chip router is proposed with both the data ?ow and control ?ow well captured. Furthermore, a well-de?ned xMAS model for a speci?c application on an NoC can be created with network and ?ow knowledge and then be mapped to corresponding NC analysis model for end-to-end delay bound calculation. The xMAS model e?ectively bridges the gap between the informal NoC micro-architecture and the formal analysis model. Besides delay bound, the analysis of backlog bound is also crucial for predicting bu?er dimensioning boundary in on-chip Virtual Channel (VC) routers. In this thesis, basic bu?er use cases are identi?ed with corresponding analysis models proposed so as to decompose the complex ?ow contention in a network. Then we develop a topology independent analysis technique to convey the backlog bound analysis step by step. Algorithms are developed to automate this analysis procedure.Accompanying the analysis of performance bounds, tightness evaluation is an essential step to ensure the validity of the analysis models. However, this evaluation process is often a tedious, time-consuming, and manual simulation process in which many simulation parameters may have to be con?gured before the simulations run. In this thesis, we develop a heuristics aided tightness evaluation method for the analytical delay and backlog bounds. The tightness evaluation is abstracted as constrained optimization problems with the objectives formulated as implicit functions with respect to the system parameters. Based on the well-de?ned problems, heuristics can be applied to guide a fully automated con?guration searching process which incorporates cycle-accurate bit-accurate simulations. As an example of heuristics, Adaptive Simulated Annealing (ASA) is adopted to guide the search in the con?guration space. Experiment results indicate that the performance analysis models based on NC give tight results which are e?ectively found by the heuristics aided evaluation process even the model has a multidimensional discrete search space and complex constraints.In order to facilitate xMAS modeling and corresponding validation of the performance analysis models, the thesis presents an xMAS tool developed in Simulink. It provides a friendly graphical interface for xMAS modeling and parameter con?guring based on the powerful Simulink modeling environment. Hierarchical model build-up and Verilog-HDL code generation are essentially supported to manage complex models and conduct simulations. Attributed to the synthesizable xMAS library and the good extendibility, this xMAS tool has promising use in application speci?c NoC design based on the xMAS components.