In this survey, we address the concept of network in three different contexts representing the deterministic, probabilistic, and statistical physics-inspired design paradigms. More precisely, we start by considering the natural representation of networks as graphs and discuss the main deterministic approaches to Network-on-Chip (NoC) design. Next, we introduce a probabilistic framework for network representation and optimization and present a few major approaches for NoC design proposed to date. Last but not least, we model the network as a thermodynamic system and discuss a statistical physics-based approach to characterize the network traffic. This formalism allows us to address the network concept in the most general context, point out the main limitations of the proposed solutions, and suggest a few open-ended problems.
The Chip Is the Network: Towards a Science of Network-on-Chip Design reviews the major design methodologies that have had a profound effect on designing future Network-on-Chip (NoC) architectures. More precisely, it addresses the problem of NoC design in the deterministic context, where the application and the architecture are modeled as graphs with worst-case type of information about the parameters of the components influencing the network traffic. Rather than simply enumerating the proposed approaches, it takes a formal approach and also discusses the main features of each proposed solution. It then goes one step further by considering the design of NoCs with partial information available (primarily under the Markovian assumption) about the application and the architecture. Similarly to the deterministic context, it discusses various probabilistic approaches to NoC design and points out their advantages and limitations. Last, but not least, it looks at emerging approaches inspired from statistical physics and information theory. The formal approach adopted means the network concept is addressed in the most general context, pointing out the main limitations of the proposed solutions, and suggesting a few open-ended problems. The Chip Is the Network: Towards a Science of Network-on-Chip Design is an invaluable reference for the NoC research community and, indeed anyone from CAD/VLSI academe or industry with an interest in this emerging paradigm.