Evaluation of Packet Latency on a 2D Mesh Network-on-Chip

Organisation:	STMicroelectronics and CEA-Leti (FRANCE)
Method:	Continuous-Time Markov Chains (CTMC)
Tools used:	CADP (Construction and Analysis of Distributed Processes)
Domain:	Hardware Design.
Period:	2009-2010
Size:	n/a
Description:	The high cost of iterative design of System-on-Chip (SoC) communication systems and the need to reduce time-to-market have led to increased interest in mathematical and formal methods for fast and exhaustive validation of design and performance evaluation in the early stages of design, replacing simulation-based methods that are time-consuming and not exhaustive. Networks-on-Chips (NoCs) are new interconnecting solutions between different modules of nowadays complex SoCs. A vast number of parameters, such as topology, routing algorithm, switching strategy and flow control mechanism, make NoC architectures different from each other and influence the NoC performance. In addition to architectural parameters, the traffic pattern (application) also influences the performance of NoCs. A NoC can be regarded as a system with stochastic characteristics that can be explored using various performance evaluation methods, including Continuous-Time Markov Chains (CTMCs). This case study considers a CTMC-based method for determining the mean latency of end-to-end communication via a NoC. The analytical method proposed aims to obtain the mean latencies of crossing each node of a given path, and by adding them achieves the mean latency of the entire path. The method is supported by a tool flow, which takes as input parameters the NoC dimensions, a source/destination pair, an offered-load and the packet length. The NoC is then modeled as a CTMC, which is subsequently analyzed using the BCG_TRANSIENT and BCG_STEADY tools of CADP. The method is illustrated on a 5x5 2D-mesh NoC. The analytical results obtained were close (less than 5%) to those produced using a corresponding SystemC CABA simulation platform.
Conclusions:	The CTMC methodology described, supported by specific tools, such as those provided by CADP, was successfully used to analyse packet latency, and can be expanded to a NoC of any dimension without encountering the state space explosion problem. It can also be used to determine the saturation threshold. Compared with other methods, it is rapid, simple and accurate.
Publications:	[Foroutan-Thonnart-Hersemeule-Jerraya-09] Sahar Foroutan, Yvain Thonnart, Richard Hersemeule, and Ahmed Jerraya. "Analytical computation of packet latency in a 2D-mesh NoC". Joint IEEE North-East Workshop on Circuits and Systems and TAISA Conference, 2009. NEWCAS-TAISA '09. IEEE, July 2009. Available on-line at: http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5290419 or from the CADP Web site in PDF or PostScript [Foroutan-Thonnart-Hersemeule-Jerraya-10] Sahar Foroutan, Yvain Thonnart, Richard Hersemeule, and Ahmed Jerraya. "A Markov chain based method for NoC end-to-end latency evaluation". IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum (IPDPSW). IEEE, April 2010. Available on-line at: http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5470788 or from the CADP Web site in PDF or PostScript
Contact:	Sahar Foroutan STMicroelectronics/CEA-Leti Email: sahar.foroutan@cea.fr
Further remarks:	This case study, amongst others, is described on the CADP Web site: http://cadp.inria.fr/case-studies

Back to the CADP case studies page