Article Preview
Top1. Introduction
Systems on Chip (SoC) grow in complexity with the advancement of semiconductor technology enabling integration of dozens of cores on a chip. The continuously increasing number of cores calls for a new communication architecture as traditional architectures are inherently nonscalable, making communication a bottleneck. System architectures are shifting towards a more communication centric methodology. Network on Chip (NoC) has emerged as the design paradigm for design of scalable on-chip communication architectures, providing better structure and modularity than its predecessors (De Michel & Benini, 2006; Rantala, Lehtonen, & Plosila, 2006).
Figure 1 illustrates the implementation of the system d695 from the ITC’02 SoC Test benchmarks suit in SOCIN topology (Marinissen, Iyengar, & Chakrabarty, 2002). This is also a topological aspect of a 4×4 mesh NoC, which shows a model of global level on-chip communication. Instead of busses and dedicated point-to-point links, a more general scheme is adopted by employing a grid of routing nodes spread out across the chip and connected by communication links. Such regular and parallel structures are very attractive because they can offer well-controlled electrical parameters which enable high-performance circuits by reducing latency and increasing bandwidth. From this perspective, the SoC design will resemble more the creation of large scale communication networks rather than traditional IC design practice.
The simple 4×4 mesh NoC in Figure 1 consists of Network Interfaces (NIs), Cores, Routers and Links. One Network Interface (NI) is needed to connect each IP core to the NoC. Network Interfaces are converting the transaction request/response into packets and vice versa. For example, in ×pipes (Bertozzi & Benini, 2004; Dall'Osso, Biccari, Giovannini, Bertozzi, & Benini, 2003), two separate NIs are defined for system master and system slaves. The NIs implement the interface by which the cores are connected to the NoC, decoupling computation (the cores) from communication (the network). Links are connected between the nodes with either static or dynamic bandwidth. They may consist of one or more logical or physical channels. The routing methods can be applied either after NoC topology mapping and design or during the mapping process itself. Routing nodes are required to route the data according to chosen protocols, implementing the desired routing strategies.
The general routing schemes in the NoC are either static or dynamic. In static routing, bandwidth and the traffic flows are fixed. On the other hand, in the case of dynamic routing, the paths are selected based on the current bandwidth and traffic flow characteristics of the network. In most of the NoC designs the bandwidth and data width are fixed. Creating a NoC based system requires selection of cores for various purposes and efficient mapping of the cores on the platform. Design choices include binding between core ports and network ports, communication between cores, and allocation of network channel capacity. In most of the NoC designs the bandwidth and data width are fixed, because frequent dynamic changes in traffic flows and routing paths would mean dynamic hop counts and a complex on-chip system implementation. Therefore, in this paper, we concentrate on static routing only.
This paper is organized as follows: A brief review of routing algorithms is given in the next section. Section 3 gives some basic definitions and notations and shows a mathematical model for our problem. In Section 4, we focus on the path selection procedure and its existence. A multi-dimensional flow algorithm for minimizing the data packet transmission is discussed in Section 5. Our experimental results are given in Section 6. Finally, we draw some conclusions in Section 7.
Top2. Previous Work
General single path routing algorithms are well studied by many authors (Anido & Seeto, 1988; Banner & Orda, 2007; Faloutsos, 1999; Wang, Jin, Kim, & Malik, 2002). Current routing schemes typically focus on discovering a single or multiple optimal paths for routing from one source to one destination (Banner & Orda, 2007; Bjerregaard & Mahadevan, 2006).