Performability analysis of Networks-on-Chips

Abstract

The rapidly increasing transistor density enables the evolution of many-core on-chip systems. Networks-on-Chips (NoCs) are the preferred communication infrastructure for such systems. Besides, NoCs have also been proposed to solve the complex on-chip communication problem in the three-dimensional systems-on-chips (3D SoCs). A downside of technology scaling is the increased susceptibility to failures in NoC resources. Ensuring reliable operation despite such failures degrades NoC performance and may even invalidate the performance benefits expected from scaling. Thus, it is not enough to analyze performance and reliability in isolation, as usually done. The goal of this thesis is to cope with the performance and reliability analysis of NoCs jointly under consideration of faults. This is achieved by the concept of the performability analysis. One of the commonly used performability methods is the Markov reward model. In this work, a generic methodology based on the Markov reward model is proposed to perform performability evaluation and analysis of NoCs under various design parameters. The introduced methodology consists of two parts. In the first part, generic Markov modeling of NoCs with consideration of different fault models is proposed. It can be applied for both 2D and 3D NoCs. As the size of NoCs increases, the size of their Markov state spaces grows as well. To perform the performability evaluation of large size NoCs, we implement tools to generate the Markov state space and to perform the long-term and transient analyses of the generated Markov model. In the second part, we introduce two performance metrics namely communication time and fault resilience. Communication time is an indicator of the ability to successfully transmit a certain number of packets. Fault resilience is an indicator of how reliable a NoC is in terms of connected paths. As the number of fault combinations of some states in the utilized Markov model is huge, it is a challenging and necessary research task to obtain performance metrics of valid states in the utilized Markov model efficiently. In this work, we present different approaches to computing the mentioned performance metrics. These approaches have been verified with simulations concerning accuracy and speedup. Finally, we utilize several case studies to demonstrate how to use our proposed methodology to evaluate and analyze the performability of NoCs. Performabilities of various topologies and routing algorithms are evaluated and compared with respect to two performance metrics. Moreover, we investigate how performability develops with scaling towards larger NoCs and explore the limits of scaling by determining the break-even failure rates under which scaling can achieve net performance increase.