Designing Nonblocking Networks With a General Topology

Abstract

Conventional theory for designing strictly nonblocking networks, such as crossbars or Clos networks, assumes that these networks have a centralized topology. Many new applications, however, require networks to have a distributed topology, like 2-D mesh or torus. In this paper, we present a new theoretical framework for designing such nonblocking networks. The framework is based on a linear programming formulation originally proposed for solving the hose-model traffic routing problem. The main difference, however, is that the link bandwidths in our problem must be discrete. This makes the problem much more challenging. We show how to apply the developed theorems to tackle the problem of designing bufferless NoCs (networks-on-chip). The proposed bufferless NoCs are deadlock/livelock-free and consume significantly less power than their buffered counterparts. We also present a multi-slice technique to reduce node capacity variations. This can make the proposed NoC architecture more cost efficient in a VLSI (very large-scale integration) implementation. In addition, we offer a detailed delay/throughput performance evaluation of the proposed bufferless NoC in the paper.

Keywords

• Nonblocking networks
• networks-on-chip (NoCs)
• bufferless
• hose model