Design and analysis of heterogeneous nanoscale on-chip communication networks

https://doi.org/10.1016/j.nancom.2012.12.002Get rights and content

Abstract

With a continuing downscaling of the physical feature sizes, an increase in complexity and the number of on-chip devices, and an increase in their heterogeneity, the traditional on-chip communication infrastructure needs to be revisited. It has previously been shown that multi-hop communication suffers from high latency and power consumption and that networks with long-range, high-bandwidth, and low power communication links significantly improve the system performance. Yet, it is an open problem what level of heterogeneity and what link type characteristics represent an optimum for on-chip communication networks. In this paper we design and analyze optimal heterogeneous networks by considering different cost and performance trade-offs in a technology-agnostic framework. We show that there is an optimal number of different link types for each set of constraints and that the heterogeneous network performance allows for a higher throughput at a lower cost compared to 2D regular mesh and homogeneous networks. From our results it follows that the link types available with current technology are non-optimal in a heterogeneous setup. We show that the main results are robust against certain model assumptions. In addition, the proposed heterogeneous networks scale up significantly better in terms of both cost and performance. The results are relevant for the design of emerging nanoscale communication fabrics and will help to drive the development of new technology.

Introduction

As the number of cores (or IP blocks) integrated on a single chip increases, the communication between them becomes increasingly important. Traditional Systems-on-Chips (SoCs) interconnect architectures are based on a shared bus structure, which can carry only one communication transaction at a time. This limits the communication bandwidth and scalability [22]. Such an architecture is therefore not suitable for future nanoscale SoCs, which may have orders of magnitude more components. In recent years, Network-on-Chip (NoC) were proposed as a promising solution for designing large and complex on-chip communication problems [2], [19]. The NoC paradigm provides better scalability and reusability for future SoCs. Despite these benefits, conventional metal wire interconnects limit the communication performance of NoCs because of their multi-hop nature for long-range on-chip communication. Multi-hop communication causes high latency and power dissipation [15], which can lead to the interconnect consuming 80% of the total chip power [16]. The ITRS roadmap also states that “[i]t is now widely conceded that technology alone cannot solve the on-chip global interconnect problem with current design methodologies”.

To solve this problem, we need new interconnect fabrics that can support single-hop communication across an entire chip. In the last few years, several new interconnect technologies, such as photonic interconnects [29], multi-band RF NoC [5], Carbon NanoTubes (CNTs) [9], [18], and millimeter wave wireless (mmWave) [11] were proposed and evaluated. However, these new technologies were evaluated and used with specific performance metrics, such as throughput, latency, or power, while in reality, trade-offs are the key. What may be optimal for one metric may not be optimal for all the others. For example, one can obtain high performance by adding more wires to a NoC, but this will increase the wiring cost and power consumption. How to use these new NoC interconnect technologies in an optimal way is an open problem [25].

In this paper, we propose to design and analyze optimal nanoscale NoCs with a much larger link library to answer the following questions:

  • How many heterogeneous link types are optimal?

  • Is that optimum different from the number of link types allowed by current technology?

  • What are an optimal heterogeneous link type distributions for a given traffic scenario?

  • What is an optimal placement of the different link types for a given traffic scenario?

  • Do heterogeneous link type networks scale better than mesh networks?

We answered these questions by developing a comprehensive software framework for the design, optimization, and evaluation of complex heterogeneous nanoscale NoC networks. The framework can optimize networks according to any number and combination of the common network performance metrics, such as the wiring cost, the average shortest path length (latency), the throughput, and the energy. Once an optimal heterogeneous NoC architecture has been obtained, we evaluated the network under different realistic traffic models and showed that our proposed heterogeneous architectures outperform homogeneous architectures in performance, energy, and throughput. We compared the results with heterogeneous link type networks with less than ten different link types and showed that they do not represent an optimal solution. In addition, we also demonstrated that our proposed interconnect architectures scale better than regular 2D mesh networks.

The main contributions of this work are as following:

  • (1)

    We introduce a library of heterogeneous link types in nanoscale NoCs to solve the current NoC multi-hop wired communication problems and significantly improve the network performance at a low cost. To the best of our knowledge, no one has thoroughly evaluated hybrid networks with three or more different kinds of interconnect technologies in a comprehensive framework that can deal with several design constraints.

  • (2)

    We present algorithmic methods to evaluate each different type of link and find the best solutions, such as the optimal number of heterogeneous link types, the optimal wire-length distributions, and an optimal placement of the heterogeneous links. This allows us to obtain optimal networks for a broad range of current and future nanoscale NoC interconnect technologies.

  • (3)

    We present evolutionary optimization techniques to obtain optimal NoC topologies. Our networks significantly outperform current three link type networks, homogeneous, and regular mesh networks.

The results presented in this paper are relevant for a broad set of nanoscale NoC and SoC applications, which rely increasingly on different communication channels. Note that we do not make any statement whether our ten link types can actually be implemented in some technology at this point in time. The current study takes a technology-agnostic approach and investigates heterogeneous networks from an abstract perspective in order to obtain fundamental results that are broadly applicable.

Section snippets

Related work

Traditional NoC architectures are based on packet-switching networks. In the last few years, several solutions were proposed to improve the network performance. Ogras and Marculescu [26] have proposed inserting a few long-range links to standard mesh NoC topologies to improve the performance of NoCs. The results show that adding long-range links reduces the average distance between source and destination nodes, which increases the network throughput and reduces the average packet latency. The

Architectural overview

In this section, we will present the basic architecture of our framework, define measures, and introduce the methodology.

Performance evaluation

In this section, we will present the performance evaluation experiments in detail. The goal is to show the number of link types usage for optimal networks and to prove that networks with heterogeneous link types are beneficial in terms of cost, performance, and energy under three different traffic patterns.

Performance comparison between linear and non-linear cost mapping of the links

In order to show that our model is robust against certain assumptions, we have also performed additional simulations by using a non-linear (i.e., exponential) cost mapping of the links. Fig. 20 shows the non-linear cost mapping of each link type (see Fig. 1 for a comparison with the linear mapping). In order to reduced the effect of the other parameters, we decided to only change the cost function for this experiment. However, the outcome would be similar if the other relationships were changed

Performance evaluation by using the GEM5

In order to validate the results of our abstract framework, we used the GEM5 platform [3] to run a realistic benchmark with one of our evolved topologies. We used the SPLASH-2 [34], which is the most commonly used multi-threaded benchmark suite for parallel machines with shared memory in both academia and industry. As a real application benchmark, we use the Fast Fourier Transforms (FFT) [1] kernel, which is a complex one-dimensional algorithm that computes the discrete Fourier transform, to

Conclusion

In this paper, we presented the benefits of using ten heterogeneous link types in a generic nanoscale NoC architecture to solve the traditional multi-hop communication problem and to improve the overall network performance. We used an evolutionary framework to evolve optimal networks under various design constraints, traffic patterns, and injection rates. Compared to other work that has been done, we do not construct a network on top of a regular mesh topology. Instead, the evolutionary

Acknowledgments

The authors are grateful to Partha Pande and Stephan Müller for the fruitful discussions and feedback.

Haera Chung is currently a Ph.D. candidate in the Department of Electrical and Computer Engineering, Portland State University, USA. She received her B.S. and M.S. degree in Computer Science Engineering from Korea University and Ewha Women’s University, South Korea respectively. Her research interests include heterogeneous network-on-chip architectures and on-chip communications.

References (35)

  • A. Zhou et al.

    Multiobjective evolutionary algorithms: a survey of the state of the art

    Swarm and Evolutionary Computation

    (2011)
  • D. Bailey

    FFTs in external or hierarchical memory

    The Journal of Supercomputing

    (1990)
  • L. Benini et al.

    Networks on chips: a new SoC paradigm

    Computer

    (2002)
  • N. Binkert et al.

    The GEM5 simulator

    SIGARCH Computer Architecture News

    (2011)
  • S. Cahon, E. Talbi, N. Melab, ParadisEO: a framework for parallel and distributed biologically inspired heuristics, in:...
  • M. Chang, J. Cong, A. Kaplan, M. Naik, G. Reinman, E. Socher, et al., CMP network-on-chip overlaid with multi-band...
  • M. Chang et al.

    RF/wireless interconnect for inter-and intra-chip communications

    Proceedings of the IEEE

    (2001)
  • M. Chang et al.

    RF interconnects for communications on-chip

  • H. Chung, A. Asnodkar, C. Teuscher, A structural analysis of evolved complex networks-on-chip, in: Proceedings of the...
  • H. Dai

    Carbon nanotubes: synthesis, integration, and properties

    Accounts of Chemical Research

    (2002)
  • S. Deb, K. Chang, A. Ganguly, P. Pande, Comparative performance evaluation of wireless and optical NoC architectures,...
  • S. Deb, A. Ganguly, K. Chang, P. Pande, B. Beizer, D. Heo, Enhancing performance of network-on-chip architectures with...
  • K. DeJong

    Evolutionary Computation

    (2002)
  • E. Elbeltagi et al.

    Comparison among five evolutionary-based optimization algorithms

    Advanced Engineering Informatics

    (2005)
  • M. Fulgham, L. Snyder, Performance of chaos and oblivious routers under non-uniform traffic, Tech. Rep. Univ. of...
  • A. Ganguly et al.

    Scalable hybrid wireless network-on-chip architectures for multicore systems

    IEEE Transactions on Computers

    (2011)
  • International Technology Roadmap for Semiconductors, 2007 edition, Tech. Rep. 2007,...
  • Cited by (4)

    Haera Chung is currently a Ph.D. candidate in the Department of Electrical and Computer Engineering, Portland State University, USA. She received her B.S. and M.S. degree in Computer Science Engineering from Korea University and Ewha Women’s University, South Korea respectively. Her research interests include heterogeneous network-on-chip architectures and on-chip communications.

    Christof Teuscher is an Assistant Professor in the Department of Electrical and Computer Engineering (ECE) with joint appointments in the Department of Computer Science and the Systems Science Graduate Program. He also holds an Adjunct Assistant Professor appointment in Computer Science at the University of New Mexico (UNM). Dr. Teuscher obtained his M.Sc. and Ph.D. degree in Computer Science from the Swiss Federal Institute of Technology in Lausanne (EPFL) in 2000 and 2004 respectively. His main research focuses on emerging computing architectures and paradigms. For more information visit: http://www.teuscher-lab.com/christof.

    View full text