Kyosun Kim
email: kkim@incheon.ac.kr

Kaijie Wu
email: kaijie@ece.uic.edu

Ramesh Karri
email: ramesh@india.poly.edu

Towards Designing Robust QCA Architectures in the Presence of Sneak Noise Paths

Quantum-dot Cellular Automata (QCA) is attracting a lot of attentions due to their extremely small feature sizes and ultra low power consumption. Up to now there are several designs using QCA technology have been proposed. However, we found not all of the designs function properly. Further, no general design guidelines have been proposed so far. A straightforward extension of a simple functional design pattern may fail. This makes designing a large scale circuits using QCA technology an extremely time-consuming process. In this paper we show several critical vulnerabilities in the structures of primitive QCA gates and QCA interconnects, and propose a disciplinary guideline to prevent any additional plausible but malfunctioning QCA designs.

Introduction

Scaling of CMOS devices is being aggressively pursued by shrinking transistor dimensions, reducing power supply voltages and increasing operating frequencies. Such aggressive scaling adversely results in a series of non-ideal behaviors such as high leakage current and high power density levels. These issues will eventually become road blocks and slow down the scaling trend that exists for years [1]. Quantum-dot Cellular Automata (QCA) is attracting a lot of attention due to their extremely small feature sizes (at the molecular even atom level) and ultra low power consumption [START_REF] Lent | Quantum cellular automata[END_REF]. A quantum cell shown in Figure 1 (a) consists of four dots at the corners with two excess electrons that can tunnel between the dots. Due to Coulomb repulsion the two excess electrons always occupy diagonally opposite dots. There are two configurations with energetically equivalent polarizations designated as +1 and -1. Tunneling out of a cell is suppressed due to high inter-cell barriers. In a second type of QCA cells, the dots are located at the middle of the sides of cells as shown in Figure 1 (b). The basic logic element in QCA logic is a majority gate and shown in Figure 1 (c). Cells A, B and C serve as drivers or input cells. F is the output cell and is polarized according to the polarization of the majority of the driver cells. In this example since polarization of 2-out-of-3 input cells are -1, the polarization of the output cell is -1. The cell arrangement in Figure 1 (d) implements an inverter since the polarization of the output Out is the opposite of the polarization of input In. The wires This work is partially supported by the Korea Science and Engineering Foundation (KOSEF) through the Multimedia Research Center at University of Incheon constructed using the two types of cells are shown in Figure 1 (e) and Figure 1 (f). When an input is applied to the input cell, the binary information propagates from left to the right due to the Coulomb repulsion between the electrons of neighboring cells. When all cells in a wire settle down to their ground states, they have the same polarization. In Figure 1 (f), when all cells settle down each cell has a different polarization than its neighbors in the wire array. (e) A QCA wire using 90-degree cells and a (f) QCA wire using 45-degree cells Polarization switch of a cell is caused by electron tunneling between neighboring dots within the cell. However, when the inter-dot barrier is high, the cell will remain its polarization and will not react to polarization changes of its neighbors. The inter-dot barrier of a cell can be modulated as a clock to allow or deny the polarization changes by the environment. Usually one clock cycle is divided into four phases, namely, switch, hold, release, and relax. During the switch phase, the inter-dot barrier is raised and the cell gradually settles down to its ground state. During the hold phase, the inter-dot barrier remains high, thus suppressing electron tunneling and freezing the cell at its current ground state. During the release and relax phases, the inter-dot barriers are lowered down while the electrons gain mobility gradually. The cell becomes un-polarized and can react to polarization changes of its neighbors. Therefore, the polarization of a cell is determined during the switch phase by the neighbors that are currently in the hold phase, or being newly polarized in the switch phase. The un-polarized neighbors in the release and relax phases do not affect the polarization of the switching cell.

In general, a clocked QCA design uses four pipeline clocks 1 , 2 , 3 and 4 . Each of the clocks has a 90-degree phase delay to its previous clock. Each cell in a QCA design is assigned one of the pipeline clocks. A cell that is assigned a clock i is polarized during the switch phase mostly by its neighbor cells that are assigned the same clock. Since this cell also contributes to the polarization of its neighbors that are assigned the same clock, the information flows bidirectionally and forms a feedback among the cells with the same clock. The neighbor cells that are assigned clock i-1 (in the hold phase) also contribute to the polarization of the cell (in the switch phase of i ). However, the cell that is assigned clock i , does not affect the polarization of its neighbors that are assigned clock i-1 . This property allows only unidirectional signal flow at the interface between cells that are assigned different pipeline clocks.

After the basic operations of the QCA cell were demonstrated on a hardware implementation in late 1980s, a variety of QCA designs spanning from small scale circuits like an adder to a large scale integration like a microprocessor have been reported. Tougaw and Lent first proposed the design of a QCA-based 1-bit full adder [START_REF] Tougaw | Logical devices implemented using quantum cellular automata[END_REF]. The full adder takes A, B and carry-in Cin. The Sum is generated as M(M(A', B, Cin), M(A, B', Cin), M(A, B, Cin')) where A' B' Cin' are the complementary of A B Cin respectively and M is a majority gate. Similarly the carry out Cout is generated as M(A, B, Cin). Overall this full adder takes five majority gates, three inverters and requires 192 cells in all. Another QCA full adder with fewer cells is proposed in [START_REF] Wang | Quantum-Dot Cellular Automata Adders[END_REF]. This design generates Sum by using M(Cout', Cin, M(A, B, Cin')) and the total number of cells has been reduced to 145. A bit-serial adder proposed in [START_REF] Fijany | Bit-serial Adder Based on Quantum Dots[END_REF] modifies the full adder implementation of [START_REF] Wang | Quantum-Dot Cellular Automata Adders[END_REF] to include a feedback connection between Cout and Cin. A QCA-based carry-look-ahead adder is obtained by connecting the carry out of a full adder to the carry in of the next full adder [START_REF] Vetteth | Quantum-dot cellular automata carry-look-ahead adder and barrel shifter[END_REF].A microprocessor is proposed on [START_REF] Niemier | A Design of and Design Tools for a Novel Quantum Dot Based Microprocessor[END_REF].

On the other hand, design tools and simulators have been developed to facilitate the design entry and verification. There are four types of simulation models that have been used so far [START_REF]QCA Designer[END_REF]: Coherence Vector, Bistable, Nonlinear Approximation and Digital. The Coherence Vector model calculates the timing-dependent state of a cell based on the kink energy between this cell and all the other cells. The kink energy between two cells is the energy cost of these two cells having opposite polarizations. The accuracy of Coherence Vector model depends on the granularity of the timing step and can be used to evaluate the dynamic behavior of cell's polarization switching. Bistable and Nonlinear Approximation models also use the kink energy to calculate the state of the cell in a time-independent way thus reducing the total time of simulation. Digital model works like a binary logic analyzer and is the fastest but the least accurate simulation engine.

Unlike the asserted simplicity of device and interconnect structures that are introduced in previous work, one can be easily frustrated by the failures on the simulation of the QCA designs. We have found out that most of the QCA designs that are presented in previous work are not operational. One may have managed to succeed in simulating a small circuit on a single simulation model by tweaking parameters of the simulator, and redrawing circuit parts. Unfortunately, the simulation of the QCA design using other models may fail again. We have found several critical vulnerabilities in the structures of primitive QCA gates and QCA interconnects. We will describe each of them in the rest of this paper. In order to prevent any additional plausible but malfunctioning QCA designs, a disciplinary guideline for robust QCA designs are also provided.

Sneak Noise Paths in QCA Designs

Coherence Vector model calculates the state of a cell based on accumulated kink energy. The kink energy of cell i and j represents the energy cost of cells i and j that have opposite polarizations. It is calculated from the electrostatic interaction between all the charges. For each dot in cell i, the electrostatic interaction between this dot and each dot in cell j is calculated as follows:

j i j i r j i r r q q E 0 , 4 1
where 0 is the permittivity of free space and r is the relative permittivity of the material system. This is accumulated for all i and j. The overall kink energy is the summation of the all the individual kink energy. Therefore, the state of a cell is determined by all its neighboring cells, not only the ones that deliver the desired information. While in this example signal beats the noise and Z carries the signal, it may not always be true. In this section we will identify several design patterns with hidden noise paths that will cause circuit fail. And we will analyze the reason of failures and propose appropriate design rules.

An Extended Crossover Structure

The horizontal wire of the crossover shown in Figure 2 (a) is extended by adding one more cell before output Z. The extended crossover is shown in Figure 3 (a). However, the simulation result using the coherence vector model shows that the signal input at cell C fails being transferred to cell Z.

The information carried by cell Z is actually the inversion of input at cell A.

A 1 0 C 1 0 A 2 0 A 2 -1.57e-22 A 3 0 C 2 0 X +2.10e-24 C 3 -2.10e-24 C 1 +3.48e-24 A 1 -4.20e-24 C 2 C 2 +1.17e-22 A 3 X -1.

57e-22 Table 1: The kink energy between cells in the crossover

Similarly the polarizations of cells A 2 and A 3 in the vertical array do not affect the polarization of cell C 2 . The kink energies between cells are summarized in Table 1 1 . In our design, the diameter of a dot is 5 nm and the cell size is 18 nm 18 nm. The cell distance is 5 nm and the grid space is 23 nm. The horizontal signal jumps from cell C 1 to cell C 2 crossing over cell A 2 . Unfortunately, the cell pairs {C 2 , A}, and {C 2 , X} have non-zero values of the kink energy since the dot polarization patterns are asymmetric. We call this the 1 The kink energy is obtained by printing the internal variables of QCADesigner [START_REF]QCA Designer[END_REF].

sneak noise path since it conducts the noise from the input at A to cell C 2 .

The effect that the state of one cell has on that of its neighbors can be quantified by a cell-cell response function. The nonlinearity and bistable saturation of the cell-cell response serves the same role as gain in a conventional digital circuit [START_REF] Tougaw | Dynamic Behavior of Quantum Cellular Automata[END_REF]. A very slight polarization of a cell induces a much larger polarization of its neighbor. The neighbor also feedbacks a larger polarization to the cell even before the neighbor's polarization is saturated. Such synergic effect amplifies not only the polarization of a signal, but also that of a noise which propagates through the sneak noise path. Consider the cell arrangement shown in Figure 5 (a). Two inputs are applied at A and B. From the designer's point of view, the input from A acts as signal while the input from B acts as noise. Although the kink energy between A 7 and A 8 is about 30 times stronger than the one between B 1 and A 8 , the noise from B arrives at cell A 8 earlier than the signal due to its shorter propagation path, and then propagates down to cells A 10 and A 11 . The positive polarization feedback between these cells amplifies the noise so that the signal is stuck at A 8 , and propagates no further. However, if cell A 11 is removed from the end of the wire, the noise-induced polarization is not fully amplified, and the noise disappears as shown in Figure 5 (b). This experiment shows that the noise amplification is successful when both conditions are met: noises arrive earlier than signals, and the wire segment at the noise injection point is long enough. In other words, the noise amplification can be prevented by either limiting this length or letting signal arrive first.

Majority Gate Structures

Consider a majority gate implementation shown in Figure 7 (a). Cells A, B and C serve as the inputs and cell Y is the output. All the cells are in a single phase. The simulation using Coherence Vector model, however, shows that this gate does not work as a majority gate at all as shown in Figure 8 (a). Due to the unbalanced input paths, signal from A and B arrive at gate device G earlier than signal from C. The gate device will gain its polarization from cells GA and GB, and then propagate the polarization down to C. Signal from C will lose its chance of voting at gate device G and eventually stuck at somewhere between GC and C. However, if cells O, P, Q have the same phase with cells GA, GB, GC and GY, e.g. the shape of the phase at the cross is extended toward the output as shown in Figure 7 (c), faults occur when the signals on cells A and C are all -1 at the third clock cycle, and all 1 at the sixth clock cycle as shown in Figure 8 (c). At the third clock cycle, cells GA and GC are temporarily polarized to -1. Since the placement between cells GA, GC and GY works like an inverter as shown in Figure 1 (d), this in turn polarizes cell GY to 1. Due to the synergic effect of the cell-cell response between cells GY, O, P and Q, this noise is successfully amplified, and cell GY casts a vote for 1 at the majority gate. The fault at the sixth clock cycle can be similarly explained. It is noticeable that neither Bistable nor Nonlinear Approximation models detects this dynamic behavior since they calculate the state of a cell in a time-independent way.

2.3.The Minimum Wire Length of a Phase Block

A phase block can be defined as a group of cells that are connected, and assigned the same QCA pipeline clock. Two cells are connected if their diagonal distance is less than 2 0.5 grids. A phase block may consist of a single cell. However, the simulation shows that the waveform of the signal on a single cell phase block becomes distorted, and cascading of such blocks causes functional failures. The schematic and simulation result are shown in Figure 9. While signal A 1 still keeps the waveform of signal A with a clock phase delay, signal A 2 is distorted, and signal A 3 is inverted. This vulnerability can be made up by letting the minimum length of a phase block be 2 cells so that the synergic effect of the cell-cell response amplifies the weak signal. A wire consisting of cascaded double-cell phase blocks and the simulation result are shown in Figure 10. The distortion of the waveform has disappeared, and cascading of double cell phase blocks results in no functional failures.

A A 1 A 2 A 3 A A 1 A 2 A 3

The Minimum Wire Spacing

As shown in Table 1, the kink energy is 1.16 10 -22 J and 3.48 10 -24 J when the spacing between two cells is zero grids and one grid, respectively. Since the kink energy between two cells with zero grid spacing is about thirty times larger than the one with one grid, one grid is enough for the minimum spacing between cells carrying different signals. However, since a horizontal wire sometime may cross over a vertical wire, not all the cells in horizontal wire have zero grid with their neighbors. Therefore the spacing between cells carrying different signals should be at least two grids for safety.

The Maximum Wire Length

Towards searching for the maximum wire length that can successfully propagate a signal from an end to the other end, consider an experimental setup shown in Figure 11. A wire is implemented by a phase block of 90-degree cells in a row. Signal A is injected from a phase block at the left side of the wire, and measured at a phase block on the other side. This wire is simulated at clock rates of 1 THz and 2 THz and the wire length is increased gradually until the signal fails to propagate to the other side. Also, a wire of 45 degree cells is simulated. The simulation shows that a signal can propagate up to 28 90-degree cells, or 27 45-degree cells at a clock rate of 1 THz, and 12 90-degree cells or 10 45-degree cells at a clock rate of 2 THz. The maximum length of a wire is limited by the clock rates, and should not exceed the corresponding limits. The propagation of a signal can be delayed by jogs and rippers on the interconnect wires. Towards evaluating the delay of a jog, consider a wire with five jogs as shown in Figure 12 (a). The simulation shows that the signal that is injected to cell A 1 is propagated up to cell A 23 at a clock rate of 1 THz. Notice that the number of cells that a signal is propagated to has been reduced from 28 to 23. Since the five jogs are responsible for this reduction, the delay of a jog can be calculated as 1 cell (= 5 cells / 5 jogs).

This delay can be explained in the following way. Assume that 1 is injected at cell A 1 . At the second jog, cell A

2.6.Synchronization

The phase delay of a path can be defined as the number of clock phase changes that have been experienced by a signal to propagate down the path. The input signals arriving at a gate should be synchronized. The phase delay of each path from a primary input to an input of a gate should be the same. The synchronization incurs the area overhead since additional phase blocks need to be inserted to balance the phases. Since the insertion of a phase block necessitates the phase shifts of the cells at the logic stages that follow, the design process becomes complicated. Also, the phase delay is very difficult to estimate during the logic design phase until the schematic diagram is completed since the interconnect structures also increase phase delays. This also complicates the top-down style hierarchical design.

ALU Case Study

Towards validating the proposed disciplinary rules for robust QCA designs, we redesigned the bit slice of the Simple 12 ALU which was presented in [START_REF] Niemier | A Design of and Design Tools for a Novel Quantum Dot Based Microprocessor[END_REF]. The original design was not operational mostly due to the sneak noise path in the crossover structure, and the asynchronous signal flow of the gate structure. The ALU consists of three unitsadder unit, logic unit, and complement-zero unit -as shown in Figure 13. It has three data inputs -A, B and Carry In (CI) -and three control inputs -Zero A (ZA), Invert B (IB, also used as OR/AND select), and Logic/Arithmetic select (L/A). The data outputs are Carry Out (CO) and OUT which is selected out of Logic Output (LO) and Sum (S) by a multiplexer. The QCA pipeline clocks are assigned to the cells so that the noise in crossovers can be tolerated, and the signal flows in gates can be synchronized. The control inputs that are fed at the left side of the design are extended to the right side so that an n-bit ALU can be constructed by cascading n such bit slices. These feed-through outputs are also synchronized with data outputs. This bit slice of the Simple 12 ALU is implemented in the area of 58 81 grids 2 using 1030 cells, and operates at a clock rate of 1 THz. The latency of a 1-bit operation is 34 clock phases (8.5 clock cycles). We simulated the design by using the coherence vector model, and the results are shown in Figure 14. The first two waveforms are the inputs to the logic unit and the third waveform is the output of the logic unit which performs OR and AND operations. Following the three inputs to the adder unit, the sum and carry out outputs are shown. The truth tables for the logic and add operations are also shown to be compared with the waveforms. The waveform intervals that correspond to the truth tables are highlighted by rectangles. The functional correctness of the design can be easily identified. An extensive simulation using the non-linear approximation model which is about 100 times faster than the coherence vector model showed similar results although the results are not shown here due to the limited space.

Conclusions

Most of QCA designs from previous work cannot function properly. In this paper we have identified several primitive design patterns that will fail due to noises of multiple inputs. We analyze such failures and conclude that most of failures are due to the ignorance of the sneak noise paths. A set of disciplinary rules that can effectively suppress noises is presented for making robust QCA designs. The correctness of designs which are compliant with the rules can be verified by using the time-dependent simulation model such as Coherence Vector, as well as time-independent simulation models such as bistable and non-linear approximation.

Figure 1 :

 1 Figure1: (a) Two 90-degree quantum cells with opposite polarizations (b) Two 45-degree quantum cells with opposite polarizations (c) A majority gate (d) An inverter (e) A QCA wire using 90-degree cells and a (f) QCA wire using 45-degree cells Polarization switch of a cell is caused by electron tunneling between neighboring dots within the cell. However, when the inter-dot barrier is high, the cell will remain its polarization and will not react to polarization changes of its neighbors. The inter-dot barrier of a cell can be modulated as a clock to allow or deny the polarization changes by the environment. Usually one clock cycle is divided into four phases, namely, switch, hold, release, and relax. During the switch phase, the inter-dot barrier is raised and the cell gradually settles down to its ground state. During the hold phase, the inter-dot barrier remains high, thus suppressing electron tunneling and freezing the cell at its current ground state. During the release and relax phases, the inter-dot barriers are lowered down while the electrons gain mobility gradually. The cell becomes un-polarized and can react to polarization changes of its neighbors. Therefore, the polarization of a cell is determined during the switch phase by the neighbors that are currently in the hold phase, or being newly polarized in the switch phase. The un-polarized neighbors in the release and relax phases do not affect the polarization of the switching cell.

Figure 2 :

 2 Figure 2: (a) a crossover and the simulation result (b) a crossover with input C absent and the simulation result Consider a crossover shown in Figure2 (a). The input applied to cell C crosses over the wire with an input applied to cell A, and is observed at cell Z. The simulation result confirms the functional correctness. However, input at A also participates in determining the state of cell Z, and actually all the cells on the horizontal wire. The simulation without input at C shown in Figure2(b) confirms that the state of cell Z is determined by the input at A when input at C is absent. From a designer's point of view the effect on cell Z cast by input at C is signal while the effect cast by input at A is noise. In a QCA design when multiple inputs are present, the signal of a cell is defined as the cell's logic

Figure 3 :

 3 Figure 3: (a) An extended crossover (b) Simulation result Figure 4 lists the four possible polarization patterns between A 1 and C 2 . The kink energy between A 1 and C 2 , which is calculated by combining the electrostatic interactions of all possible situations, is 0. In another word, the polarization of cell A 1 has no effect on the polarization of cell C 2 .

Figure 4 :

 4 Figure 4: The 4 polarization patterns between A 1 and C 2 i j Energy (J) i j Energy (J) A -2.10e-24 C +2.10e-24 A 1 0 C 1 0 A 2 0 A 2 -1.57e-22 A 3 0 C 2 0 X +2.10e-24 C 3 -2.10e-24 C 1 +3.48e-24 A 1 -4.20e-24

Figure 5 :Figure 6 A

 56 Figure 5: The amplification of noise due to the cell-cell response Consider again the crossover pattern shown in Figure 3. To prevent the noise amplification on cells C 2 , C 3 and Z, the signal has to arrive at cell C 2 , C 3 and Z no later than noise. This requires a clocked QCA design. The revised crossover and the simulation result are shown in Figure 6. The horizontal wire is segmented into two phases with a 90degree phase delay in between. The QCA pipeline clocks are represented by different gray levels. The states of cells

Figure 7 :

 7 Figure 7: Majority gates with (a) all cells in a phase (b) a proper clock assignment (c) noise amplification due to an improper clock assignment In order to have a fair voting, all the signals should arrive at the gate device simultaneously. A functional QCA majority gate with a proper clock assignment and its simulation are shown in Figure 7 (b) and Figure 8 (b), respectively. Cells GA, GB, GC, GY and G are in a new phase with a 90-degree phase delay than cells A, B and C. Notice that output cells O, P, Q, R, and Y are assigned to another phase with a 90degree phase delay than cell GY. Cells GA, GB and GC will gain their polarizations and vote on gate device G at the same time, no matter how unbalanced the three input paths are.

Figure 8 :

 8 Figure 8: Simulation results of the majority gates

Figure 9 AFigure 10 A

 910 Figure 9 A wire with cascaded single-cell phase blocks and the simulation result

Figure 11 :

 11 Figure 11: The maximum length of a phase block

10 Figure 12 :

 1012 Figure 12: The delay induced by jogs and rippers

Figure 14 :

 14 Figure 13: Schematic of the Simple 12 ALU bit slice

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE


Hangsheng Wang
email: hangshen@princeton.edu

Li-Shiuan Peh
email: peh@princeton.edu

Sharad Malik
email: sharad@princeton.edu

A Technology-aware and Energy-oriented Topology Exploration for On-chip Networks

As packet-switching interconnection networks replace buses and dedicated wires to become the standard on-chip interconnection fabric, reducing their power consumption has been identified to be a major design challenge. Network topologies have high impact on network power consumption. Technology scaling is another important factor that affects network power since each new technology changes semiconductor physical properties. As shown in this paper, these two aspects need to be considered synergistically.

In this paper, we characterize the impact of process technologies on network energy for a range of topologies, starting from 2-dimensional meshes/tori, to variants of meshes/tori that incorporate higher dimensions, multiple hierarchies and express channels. We present a method which uses an analytical model to predict the most energy-efficient topology based on network size and architecture parameters for future technologies. Our model is validated against cycle-accurate network power simulation and shown to arrive at the same predictions. We also show how our method can be applied to actual parallel benchmarks with a case study. We see this work as a starting point for defining a roadmap of future on-chip networks. 1

INTRODUCTION

On-chip interconnection networks have been proposed [START_REF] Dally | Route packets, not wires: On-chip interconnection networks[END_REF][START_REF] Guerrier | A generic architecture for on-chip packet-switched interconnections[END_REF] and used [START_REF] Sankaralingam | Exploiting ILP, TLP, and DLP with the polymorphous TRIPS architecture[END_REF][START_REF] Taylor | Scalar operand networks: On-chip interconnect for ILP in partitioned architectures[END_REF] in the past few years to replace buses and dedicated wires as the standard on-chip interconnection fabric. While many design methods inherited from chip-to-chip networks and computer cluster networks are performance-driven, the power impact of on-chip networks is becoming increasingly important [START_REF] Benini | Powering networks on chips[END_REF][START_REF] Hu | Energy-aware mapping for tile-based NoC architectures under performance constraints[END_REF][START_REF] Wang | Orion: A power-performance simulator for interconnection networks[END_REF][START_REF] Ye | Analysis of power consumption on switch fabrics in network routers[END_REF].

Network topologies define how nodes are connected to each other. More specifically, network topologies determine the number of hops and the wire length involved in each data transmission, both critically influencing the energy cost per transmission. At the same time, technology scaling not only leads to a globally increasing/decreasing trend of total network power, it also changes the power composition of different network components. As a result, an optimal topology at current technology may no longer be optimal after several technology generations. With rapid on-chip network adoption, arriving at the most suitable topology for the current process is not enough -it is critical for network designers to understand the impact of technology on network topologies and be able to predict the most energy-efficient topology for future technologies based on this understanding.

In this paper we provide the basis for this prediction by exploring the energy efficiency of several network topologies in a technologyaware manner. We use the average flit traversal energy as our metric to evaluate network energy efficiency. We then formulate this metric with a uniform analytical model which can be applied to a range of topologies and be used to quantitatively compare the energy efficiency of these topologies across multiple technologies.

The rest of the paper is organized as following: In Section 2 we explain the motivation to look at topologies and technology scaling. In Section 3 we describe our assumptions, models and metrics. Then in Section 4 we study the energy properties of four candidate topologies: 2-D meshes/tori, high-dimensional meshes/tori, hierarchical meshes/tori and express cubes. Next, we demonstrate the applicability and extensibility of this work with two case studies in Section 5, followed by the conclusion. 1 This work is supported by the Gigascale Systems Research Center funded by MARCO/DARPA.

MOTIVATION 2.1 Energy-oriented topology optimization

In an on-chip network using minimal routing, the average energy to transmit one single flit can be expressed in two ways:

E f lit = H avg (E R + E L ) (1) E f lit = H avg • E R + D avg • E L0 (2)
where H avg is the average hop count, D avg is the average distance from source to destination, E R is the average router traversal energy, E L0 is the average link traversal energy per unit length and E L is the average link traversal energy per channel. Among these factors, E R is determined by router microarchitecture and process technology, and E L0 is determined by signaling technique and process technology, H avg and D avg are both strongly influenced by the topology. Since the distance between two nodes is largely determined by their physical locations, little room exists for optimization. Hop count, however, varies greatly among different topologies. In this paper, we present a methodology and study that hinges on hop count to derive the inflection points at which a topology becomes more energy-efficient than another at each technology node.

Technology scaling

Semiconductor technology progress makes it feasible to build onchip networks with very high bandwidth. According to data published by the International Technology Roadmap for Semiconductors (ITRS) [START_REF]International technology roadmap for semiconductors[END_REF], 13-15 layers of metal wires are expected at 70nm, 50nm and 35nm technologies, which translates to abundant wiring resources for network channels.

Technology scaling also strongly affects network power. A CMOS circuit has three types of power dissipation: dynamic power, static power and short-circuit power. Short-circuit power is negligible compared to the other two power types. Dynamic power has two sources: transistor capacitance and metal wire capacitance. As technology scales, these power sources scale differently. Table 1 lists their scaling factors for current and future technologies expected in five years. Each row represents one source of power consumption. These scaling factors are calculated based on data from ITRS and [START_REF] Ho | The future of wires[END_REF]. All numbers are measured as per unit width/length, and normalized to 0.1µm technology. The table shows inconsistent scaling factors between dynamic power and static power, and between the two dynamic power sources. In particular, static power increases rapidly as technology scales.

The change in power composition can lead to subtle changes of network power characteristics. We use a common router component: FIFO buffer, as an example to illustrate how the optimal implementations are affected. All quantitative energy/power estimates are given by Orion's power models [START_REF] Wang | Orion: A power-performance simulator for interconnection networks[END_REF].

Buffers can be implemented as either SRAMs or shift registers. The shift register implementation is usually more expensive in terms of energy because it uses more transistors than the SRAM implementation. But shift register operations (read, write, shift) only involve occupied cells, while SRAM operations (read, write) involve all cells due to the global bitline and wordline wiring. So shift registers may consume less energy than SRAMs when the buffer utilization is below a certain threshold, and the opposite is true when the buffer utilization is above this threshold.

Figure 1 shows the threshold utilization for different buffer sizes and technologies. The shift register implementation is still viable at 0.1µm technology with relatively smaller buffer size and lower buffer utilization, but is absolutely not an option at 35nm technology. This is mainly caused by the rapidly increasing static power, so at 35nm technology, the advantage of fewer activities is completely overwhelmed by the disadvantage of more transistors.

It is clear from this example that technology scaling must be considered when energy/power is concerned. In our following sections, we study and analyze network topologies in a technology-aware manner.

METHODOLOGY DESCRIPTION

Throughout this paper, we derive and compare the energy efficiency of different topologies solely based on network size and technology. In doing this, we need low level energy estimates from Orion's power models, and we make some architecture assumptions, e.g., buffer size, to obtain these energy estimates. For a different set of architecture parameters, the exact quantitative results may differ, but relative trends will remain the same.

Assumptions

We assume that for an on-chip network, its nodes are placed as a square matrix, regardless of the topology. A network can be viewed as an N ×N matrix, and we mostly use network edge size N as a proxy for network size, rather than the number of nodes N 2 .

We also assume uniform random traffic in our discussion so as to reveal the "raw" capability of the topology. Uniform random traffic is the traffic pattern under which every node has equal probability to send data to every other node. Our methodology can be readily extended to support arbitrary traffic patterns, as shown in Section 5.

Metrics

We use the average flit traversal energy E f lit as the network energy efficiency metric. Since flit is the minimal flow control data unit, E f lit is the energy cost to transmit unit data. This metric encapsulates the energy efficiency of a network independently of its performance. For instance, a network with lower flit traversal energy and higher throughput can consume higher power than a network with higher flit traversal energy and lower throughput, as the former network can sustain more traffic.

Workload models

When using the flit traversal energy metric, handling static energy is not as straightforward as handling dynamic energy. Static energy is consumed by routers regardless of flit activities. To capture static energy with E f lit , we evenly apportion router static energy per cycle among all flits that pass through the router in that cycle. 2 2 It is only for modeling convenience to assign static energy to active flits. Two workload models are used to approximate the number of flits passing through per cycle:

• Constant load. Assume the number of flits traversing a router in each cycle does not vary with the number of router ports. This assumption models the situation where the workload is determined by application demand rather than the network capacity. • Linear load. Assume the number of flits passing a router in each cycle is linear in the number of ports. This assumption models the situation where the workload is constrained by the network capacity. These two models could lead to vastly different flit energy costs. To illustrate with a concrete example, we assume 0.1µm and 35nm technologies, 2GHz frequency, 4-flit buffer size, 128-bit flit size and an input-queuing router. Figure 2 shows E R given by both models at various port numbers. We choose the load so that the router is fully loaded when it has five ports.

The figure shows that with linear load, E R is a linear function of the number of ports, where the linear part comes from the crossbar (both dynamic and static) and the constant part comes from the buffer (both dynamic and static). But with constant load, since no more traffic is available to offset the addition of more buffers and the increase of the crossbar size, the buffer static energy becomes a linear term and the crossbar static energy becomes a quadratic term. The quadratically increasing trend is more obvious at 35nm technology.

The two models represent two extremes in workloads.

DESIGN SPACE EXPLORATION OF ON-CHIP NETWORK TOPOLOGIES

The 2-D mesh/torus is currently the most popular topology used by on-chip networks, because it perfectly matches the 2-D silicon surface and is also easy to implement. Channels of a 2-D mesh/torus only connect neighboring nodes, so while this topology supports local traffic well, it suffers large hop counts for long-distance traffic. Some more complicated topologies have been used by or proposed for other interconnection networks, such as high-dimensional meshes/tori, hypercubes, hierarchical meshes/tori [START_REF] Hauck | Mesh routing topologies for multi-FPGA systems[END_REF], express cubes [START_REF] Dally | Express cubes: Improving the performance of k-ary n-cube interconnection networks[END_REF] and fat-trees [START_REF] Leiserson | Fat-trees: Universal networks for hardware-effi cient supercomputing[END_REF]. Hyper-cubes are a subset of high-dimensional tori where each dimension has two nodes. To keep the scope manageable, in this paper we consider high-dimensional meshes/tori, hierarchical meshes/tori and express cubes.

One common feature of these topologies is that they use long wires to build express channels (channels that cross multiple hops) so that the hop count for long-distance traffic is effectively reduced. But using express channels inevitably increases router complexity, which increases E R , and some topologies increase D avg as well, so these topologies may not always reduce E f lit , and exploiting them to save energy becomes a complicated trade-off between hop count and router complexity. Intuitively, the larger the network is, the more longdistance traffic can benefit from express channels. So there exists a minimal network edge size N min for each topology beyond which the topology is more energy-efficient than a 2-D mesh/torus.

In the following sections, we first discuss the baseline 2-D mesh/torus, then investigate the other three topologies one by one with a 5-step procedure. 1. Derive the average hop count H avg for the topology based on the expected traffic pattern. 2. Derive the average flit traversal energy E f lit as a well-formed analytical function of H avg . 3. Derive the minimal network edge size N min , at which this topology becomes more energy-efficient than the 2-D torus. 4. Derive the optimal (most energy-efficient) configuration of the particular topology. 5. Discuss how N min and the optimal configuration vary with process technologies.

2-D meshes and tori

Figure 3 shows a mesh and a folded torus. The torus is folded to ensure even link latency.

For an N × N 2-D mesh, H avg = 2N 3 , so that

E M f lit = 2N 3 (E R + E L ) = 2N 3 • E R + 2N 3 • E L For an N × N 2-D torus, H avg = N
2 and it has double E L due to folding, so that

E T f lit = N 2 (E R + 2E L ) = N 2 • E R + N • E L
So a 2-D torus consumes 25% less router energy and 50% more link energy compared to an equal size 2-D mesh, and the ratio between E R and E L determines which one is more energy-efficient. Since all topologies discussed in the rest of this section have mesh variants and torus variants, we only study their torus variants in this paper, and results for the mesh variants can be similarly derived. We use their mesh variants in figures for better legibility.

High-dimensional meshes/tori

Figure 4 shows how a 9×9 network can be realized as either a 2-D 9×9 mesh (9-ary 2-mesh) or a 3-ary 4-mesh. While the 3-ary 4mesh reduces the average hop count from 9 to 6, the mapping of a 4-D topology onto a 2-D surface also doubles the average channel length, so the energy property of a high-dimensional mesh/torus is complicated by the trade-off between router energy and link energy.

In general, when an N × N network of M = N 2 nodes is realized by a n √ M-ary n-cube, the average hop count is

H avg = n √ M 4 • n
and the average channel length relatively increases by

l = 1 n • n-1 ∑ i=0 n √ M i 2 =      2 √ M-2 n( n √ M-1)
n is even

√ M n-1 n + √ M n+1 n -2 n( n √ M-1) n is odd Since √ M n-1 n + √ M n+1 n > 2 √
M always holds, we loosen the condition a little by letting

l 2 √ M -2 n n
√ M -1 in following discussion, and the subsequent results will be a little optimistic.

In

E f lit (n) = H avg (E R (n) + l • E L ) = C 4 n √ M • n + B 4 n √ M • n 2 + A 4 n √ M • n 3 + √ M -1 n √ M 2 n √ M -1 • E L = E 1 (n) + E 2 (n) + E 3 (n) + E 4 (n) Minimal network size Because d 2 E 1 (n) dn 2 = C 4 • n √ M • ln 2 M n 3 > 0 E 1 (n) is a concave function of n, similarly we can prove that E 2 (n), E 3 (n) and E 4 (n) are all concave functions of n. So E f lit (n) is concave, which has the property E f lit (3) > E f lit (2) ⇒ ∀n > 3, E f lit (n) > E f lit (2)
In other words, if the network can benefit from high-dimensional tori, it can benefit from a 3-D torus. So E f lit (3) < E f lit [START_REF] Benini | Powering networks on chips[END_REF] is the sufficient and necessary condition to determine if pursuing high-dimensional tori is beneficial for network energy.

E L is determined by the link length, which is in turn determined by the core size. To avoid making assumptions about cores and still get some approximate results, we ignore E L and only consider E R (n), and the resultant N min is a lower bound of the minimal network size.

With this simplification,

E f lit (3) < E f lit (2) is equivalent to M > 3 2 • E R (3) E R (2)
6

With E R (2) and E R (3) calculated by Orion's power models, Table 2 lists the minimal network size (lower bound) in the form of (M, N min ).

Here we use 128-bit flit size and 4-flit, 16-flit buffer sizes as representative parameters. Several insights can be extracted. A linearly loaded network requires smaller network size to benefit from high-dimensional tori due to its slower increasing of E R (n) compared to a constantly loaded network. A network with larger buffer size also requires smaller network size to benefit from high-dimensional tori due to its larger constant term in E R (n).

The effect of technology scaling is interesting. With linear load, a network at 35nm technology requires smaller network size to benefit from high-dimensional tori than at 0.1µm technology, which can be explained by the smaller slope of E R (n) at 35nm technology (Figure 2). But with constant load, the opposite is true due to higher energy cost per added port at 35nm technology (Figure 2). So at future technologies, accurate workload prediction is more important for making a correct topology decision.

Optimal dimension

The optimal dimension is the positive root of equation (E f lit (n)) n = 0. We cannot find the exact value of the root, but we prove that 3 n opt < ln M So for a network with 1000 nodes, n opt ∈ {3, 4, 5, 6}. Note that this is a technology-independent small range convenient for enumeration.

Hierarchical meshes/tori

In hierarchical meshes/tori, channels not only connect adjacent nodes, but also connect v-node away neighbors in each dimension, as shown in Figure 5. We call the longer channels express channels and call v the express interval.

Routing in an N-node hierarchical ring (one-dimensional hierarchical torus) is equivalent to first routing in a N v -node ring, then routing from the edge nodes of a v-ary 1-mesh to its inner nodes, assuming v|N. So the average hop count of an N × N hierarchical torus is

H avg = 2 N 4v + v 4 = N 2v + v 2
Because the minimal distance between any two nodes is achievable in a hierarchical torus, the link energy is not altered by the topology compared to a 2-D torus (this differs from the high-dimensional torus, in which some physically adjacent nodes have no direct connection). So we only need to compare router energy.

The average flit traversal energy is

E H f lit = N 2v + v 2 E R9 + D avg • E L0 (3)

Minimal network size and minimal express interval

A 2-D torus router has 5 ports, including the inject/eject port, and a hierarchical torus router has 9 ports. Let E Rm denote the average router traversal energy of a router with m ports. In order for a hierarchical torus to save energy, the following inequality must hold

E R9 N 2v + v 2 < E R5 • N 2 ⇒ N(vE R5 -E R9 ) > v 2 E R9 which is equivalent to v > E R9 E R5 (4) N > v 2 E R9 vE R5 -E R9 (5)
Inequality (4) determines the minimal express interval for a hierarchical torus to achieve better energy efficiency than a 2-D torus, and inequality (5) determines the minimal network size for a certain express interval. Table 3 lists the minimal express interval and corresponding minimal network size in the form of (v, N min ).

Optimal express interval

For an N × N hierarchical tori, the optimal express interval is one that leads to minimal average hop count. Let H avg = 0 and simple calculus reveals that v opt = √ N (7) and the corresponding theoretical minimal flit traversal energy is

E H opt = √ N • E R9 + D avg • E L0
This theoretical minimal value may not be achievable since √ N may not be an integer.

(4) is satisfied when ( 6) and ( 7) are true, so √ N is indeed the optimal express interval. Note that the optimal express interval is technology-independent.

Table 3 and 4 show similar trends to those for high-dimensional tori. Linear load, larger buffer size and technology progress all make networks more likely to benefit from topology improvements, but technology progress also makes networks more sensitive to workload.

Express cubes

The express cube [START_REF] Dally | Express cubes: Improving the performance of k-ary n-cube interconnection networks[END_REF] is another hierarchical topology, which provides express channels for every other v nodes (Figure 5). Although not all nodes are connected with express channels, long-distance traffic can still use express channels to bypass intermediate nodes, but the network does not pay router complexity penalty at every node.

Due to the similarity between the express cube and the hierarchical torus, we only present the results without detailed derivation.

Equations for average flit traversal energy, minimal network size and theoretical minimal flit traversal energy are

E E f lit = v • E R5 + N 2v • E R9 + D avg • E L0 (8) N min > 8 • E R9 E R5 (9) E E opt = 2N • E R5 • E R9 + D avg • E L0 ( 10
)
Table 5 lists the minimal express interval and corresponding minimal network size for several technologies, and Table 6 lists the minimal network size and corresponding express interval.

A comparison of high-dimensional tori, hierarchical tori and express cubes

Hierarchical tori vs. express cubes

We first compare the case where the two topologies have the same express interval v. From (3) and [START_REF] Hu | Energy-aware mapping for tile-based NoC architectures under performance constraints[END_REF] we have

E H f lit -E E f lit = v E R9 2 -E R5
So when E R9 E R5 > 2, the hierarchical torus has higher flit traversal energy than the express cube, and the opposite is true when E R9 E R5 < 2. We then compare their theoretical minimal flit traversal energy. Since they have identical link energy, we only need to compare the router energy part.

E H opt E E opt = E R9 2E R5
And again, the value of E R9 E R5 determines which topology is better. For hierarchical tori and express cubes, E R9 E R5 is also the minimal express interval. From Table 3 and 5, the minimal express interval switches between 2 and 3 at 35nm technology for different load models, so which topology is better depends on which load model is closer to reality.

Hierarchical tori vs. high-dimensional tori

In this section we will prove that hierarchical tori practically always have smaller flit traversal energy than high-dimensional tori. Since high-dimensional tori have longer average link length than hierarchical tori, we can back our claim by proving that high-dimensional tori always have higher or equal router energy.

Ignoring link energy, we have

E H opt = √ N • E R9
We make a practical assumption that the network has fewer than 1000 nodes, so for a high-dimensional torus, the optimal dimension n opt ∈ {3, 4, 5, 6}. For an N × N network, the flit traversal energy of a 3-D, 4-D, 5-D and 6-D torus is

E 3D f lit = 3 √ N 2 4 • 3 • E R (3) E 4D f lit = 4 √ N 2 4 • 4 • E R (4) = √ N • E R (4) E 5D f lit = 5 √ N 2 4 • 5 • E R (5) E 6D f lit = 6 √ N 2 4 • 6 • E R (6)
Since a router of an n-dimensional torus has 2n + 1 ports, E R (4) = E R9 , and E 4D f lit = E H opt . We conclude that hierarchical tori are better than 4-D tori.

For 5-D tori, if we assume

E 5D f lit < E H opt , which implies N > 5 4 • E R11 E R9
10 , then by substituting energy estimates from Orion, we have N 45. This conflicts with our assumption that the network has less than 1000 nodes. Similar reasoning can be applied to 6-D tori, and we conclude that hierarchical tori are better than 5-D and 6-D tori.

For 3-D tori, we can derive that E 3D f lit < E H opt holds when N < 19. But this requires the network to be organized as a

3 √ N 2 × 3 √ N 2 × 3 √ N 2 matrix
, which is not square when mapped to a 2-D surface. Since chips are usually square, with this constraint, the network needs to be organized as an N × √ N × √ N matrix, therefore

E 3D f lit = N 4 + √ N 4 + √ N 4 • E R (3)
and the condition to satisfy

E 3D f lit < E H opt becomes N < 4E R9 E R7 -2 2
By substituting energy estimates from Orion, we have N < 9, which is smaller than the minimal network size for hierarchical tori to save energy. This implies that when a hierarchical torus is able to save energy, it saves more than a 3-D torus. So we prove that when hierarchical tori can save energy over 2-D tori, they always have lower flit traversal energy than high-dimensional tori.

Express cubes vs. high-dimensional tori

By using the same method as used in the previous section, we conclude that when express cubes can save energy over 2-D tori, they also have smaller flit traversal energy than high-dimensional tori. In short, from an energy standpoint, high-dimensional tori should never be selected over hierarchical or express cubes.

CASE STUDIES

Topology scaling

To demonstrate how this work can help predict the right network topology for future technologies, we construct a hypothetical case study based on a real design.

The TRIPS [START_REF] Sankaralingam | Exploiting ILP, TLP, and DLP with the polymorphous TRIPS architecture[END_REF] operand network is a 5 × 5 mesh-like network connecting ALUs and memory components. To better match our presented results, we assume torus topology in this case study. TRIPS is designed at 0.1µm technology. Suppose we want to scale this design to 70nm, 50nm and 35nm technologies. According to the ITRS, the transistor count doubles for each technology transition listed above, while the chip size stays constant. To facilitate reuse of the cores as technology scales, we will build larger networks with the same cores, so the network size will be 7 × 7 at 70nm technology, 10 × 10 at 50nm technology and 14 × 14 at 35nm technology. We assume 4-flit buffer size, 128-bit flit size and E L = 0.53E R5 , as they are in the current design. We also assume uniform random traffic and linear load.

Table 7 lists the most energy-efficient topologies predicted by our analytical approach. H-v stands for "hierarchical torus with express interval v", and E-v stands for "express cube with express interval v".

Table 7: Predicted optimal topologies. technology 70nm 50nm 35nm optimal topology 2-D torus H-3 torus H-4 torus To validate the accuracy of our predictions, we use Orion to estimate the average flit traversal energy of these topologies at 70nm, 50nm and 35nm technologies, and the results are listed in Table 8. The top half of the table lists the results for high-dimensional tori, and the bottom half lists the results for hierarchical tori and express cubes. It can be seen that the simulation results match our predictions. This example demonstrates how our methodology can be applied to predict the optimal network topology. It also highlights that when current network design is scaled to future technologies, simply preserving the current topology will not optimize energy efficiency. The most energy-efficient topology should be chosen with regard to network size and the technology node.

Arbitrary traffic patterns

To handle arbitrary traffic patterns other than uniform random traffic, we only need to change the computation of the average hop count H avg based on the specific traffic pattern, then apply this new H avg to the 5-step procedure.

If the traffic pattern can be expressed by a probability matrix or some other mathematical form, then H avg can be easily computed.

For example, assume a traffic pattern which is the aggregation of an N × N global uniform random traffic and a v × v local uniform random traffic, with probability p and q respectively, then for a 2-D torus

H T avg = p • N 2 + q • v 2
and the average hop count of other topologies can be similarly derived.

For some applications, such well-formed mathematical expressions are hard to obtain, and we have to resort to network simulation to derive hop count information.

Consider the 10×10 network at 50nm technology and three SPLASH benchmarks: LU, mp3 and water [START_REF] Singh | SPLASH: Stanford parallel applications for shared-memory[END_REF]. We choose LU and water because they can be scaled to a 10×10 network. Mp3 does not have that scalability, and we choose it for comparison purpose. We use RSIM [START_REF] Pai | RSIM: An execution-driven simulator for ILP-based shared-memory multiprocessors and uniprocessors[END_REF] to simulate the benchmarks and collect traffic traces to compute the average hop count. Then we apply the hop count values numerically to a variety of topologies to find the optimal topology. Table 9 lists (H avg , E f lit ) values under these traffic patterns. We do not include high-dimensional tori due to limitations of RSIM, but it suffices for demonstration. H-3 is the optimal topology under random traffic at 50nm technology. Now H-2 becomes the optimal topology for both LU and water since these two benchmarks scale well to the large network size and can take advantage of express channels. But no energy reduction can be achieved for mp3 benchmark, since mp3 benchmark only uses a 3×3 subset of the network, hence express channels cannot be utilized. So for real applications to benefit from these energy-efficient topologies, good scalability is required.

RELATED WORK

The concept of on-chip interconnection networks was introduced fairly recently [START_REF] Benini | Networks on chips: A new SoC paradigm[END_REF][START_REF] Dally | Route packets, not wires: On-chip interconnection networks[END_REF][START_REF] Guerrier | A generic architecture for on-chip packet-switched interconnections[END_REF]. While network topologies have been extensively studied, with many topologies proposed for either performance or hardware efficiency [START_REF] Dally | Express cubes: Improving the performance of k-ary n-cube interconnection networks[END_REF][START_REF] Hauck | Mesh routing topologies for multi-FPGA systems[END_REF][START_REF] Leiserson | Fat-trees: Universal networks for hardware-effi cient supercomputing[END_REF], optimizing topologies for power/energy is more recent. In 1999, Zhang et al. exploited generalized meshes to reduce the energy dissipation of DSP interconnects [START_REF] Zhang | Interconnect architecture exploration for low-energy reconfi gurable single-chip DSPs[END_REF]. In 2003, Wang et al. proposed and explored power-efficient network architectures, and investigated the energy saving capability of express cubes through simulations [START_REF] Wang | Power-driven design of router microarchitectures in on-chip networks[END_REF]. In 2004, Jalabert et al. developed ×pipesCompiler, a tool for instantiating application-specific on-chip networks with customized topologies to reduce both power and area [START_REF] Jalabert | ×pipescompiler: A tool for instantiating application specifi c networks on chip[END_REF].

Our work differs from these prior works in several key aspects. First, our goal is to derive a criteria for prescribing the most energyefficient topology at a particular process technology. Second, we use a single analytical model to study a wide range of topologies, and our methodology can be easily applied to other topologies as well. Third, we do not rely on simulation tools and all results in this paper are mathematically provable with the support of low level power models. We consider topology customization an orthogonal direction of our work, so pursuing that direction based on the topology suggested by our method can lead to more energy savings.

CONCLUSIONS

In this paper, we perform a technology-aware and energy-oriented topology exploration for on-chip networks. We use 2-D meshes/tori as the baseline, and consider high-dimensional meshes/tori, hierarchical meshes/tori and express cubes as candidate energy-saving topologies. For each of them, we derive the minimal network size and other conditions under which that topology can save energy compared to the baseline. We also derive the criteria to compare these topologies and use a case study to demonstrate how our method can help choose the most energy-efficient topology.

Our method only requires information of network size, technology and a limited set of architecture parameters. Network simulation is usually not required, so our method can help make early-stage decisions that will guide later tasks such as placement and routing. With the advent of on-chip networking, a roadmap that guides onchip network designers just as ITRS guides circuit designers is critically needed. We are currently extending this work to derive a complete roadmap for on-chip networks, which will support more traffic distributions, topologies and other aspects of network design.

Figure 1 :

 1 Figure 1: Buffer threshold utilization vs. buffer size.

Figure 2 :

 2 Figure 2: Average router flit traversal energy at 0.1µm and 35nm technologies.Two workload models are used to approximate the number of flits passing through per cycle:• Constant load. Assume the number of flits traversing a router in each cycle does not vary with the number of router ports. This assumption models the situation where the workload is determined by application demand rather than the network capacity. • Linear load. Assume the number of flits passing a router in each cycle is linear in the number of ports. This assumption models the situation where the workload is constrained by the network capacity. These two models could lead to vastly different flit energy costs. To illustrate with a concrete example, we assume 0.1µm and 35nm technologies, 2GHz frequency, 4-flit buffer size, 128-bit flit size and an input-queuing router. Figure2shows E R given by both models at various port numbers. We choose the load so that the router is fully loaded when it has five ports.The figure shows that with linear load, E R is a linear function of the number of ports, where the linear part comes from the crossbar (both dynamic and static) and the constant part comes from the buffer (both dynamic and static). But with constant load, since no more traffic is available to offset the addition of more buffers and the increase of the crossbar size, the buffer static energy becomes a linear term and the crossbar static energy becomes a quadratic term. The quadratically increasing trend is more obvious at 35nm technology.The two models represent two extremes in workloads.

Figure 3 :

 3 Figure 3: A 5×5 folded torus (left) and a 5×5 mesh (right).

  a n √ M-ary n-cube, each router has 2n interconnection ports and one local inject/eject port. Let E R (n) denote the average router traversal energy of an n-dimensional torus. According to Section 3.3, E R (n) is a quadratic function of n E R (n) = An 2 + Bn +C where A, B and C are positive constants. So we have

Figure 4 :

 4 Figure 4: A 9-ary 2-mesh (left) and a 3-ary 4-mesh (right).

Figure 5 :

 5 Figure 5: A 5×5 hierarchical mesh (left) and a 5×5 express cube mesh (right), with express interval being 2.

Table 1 : Normalized power scaling factors.

 1

		0.1µm 70nm 50nm 35nm
	transistor capacitance 1	0.78	0.65	0.66
	wire capacitance	1	0.94	0.89	0.85
	static power	1	2.01	3.35	4.30

Table 2 : Minimal network size for high-dimensional tori, in the form of

 2

		Linear load	Constant load
	buffer size 4-flit	16-flit	4-flit	16-flit
	0.1µm	53, 8	44, 7	61, 8	51, 8
	70nm	49, 7	42, 7	64, 8	55, 8
	50nm	46, 7	39, 7	82, 10	73, 9
	35nm	46, 7	36, 6	165, 13	140, 12

(M, N min ).

Table 3 : Minimal express interval and corresponding minimal network size for hierarchical tori, in the form of

 3

		Linear load	Constant load
	buffer size 4-flit	16-flit	4-flit	16-flit
	0.1µm	2, 16	2, 13	2, 20	2, 16
	70nm	2, 14	2, 12	2, 22	2, 18
	50nm	2, 13	2, 11	2, 46	2, 32
	35nm	2, 13	2, 10	3, 28	3, 23

(v, N min ).

From

[START_REF] Dally | Route packets, not wires: On-chip interconnection networks[END_REF]

, it can be derived that when v is the integer closest to 2E R9 E R5 ,

N min > 4 E R9 E R5 2 (6)

defines the minimal network size, and Table

4

lists its value.

Table 4 : Minimal network size and corresponding express inter- val for hierarchical tori, in the form of

 4 (v, N min ).

		Linear load	Constant load
	buffer size 4-flit	16-flit	4-flit	16-flit
	0.1µm	3, 11	3, 10	3, 12	3, 10
	70nm	3, 10	3, 9	3, 12	3, 11
	50nm	3, 10	3, 9	4, 14	4, 13
	35nm	3, 10	3, 9	4, 21	4, 19

Table 5 : Minimal express interval and corresponding minimal network size for express cubes, in the form of (

 5 v, N min ).

		Linear load	Constant load
	buffer size 4-flit	16-flit	4-flit	16-flit
	0.1µm	2, 20	2, 17	2, 24	2, 20
	70nm	2, 18	2, 16	2, 26	2, 22
	50nm	2, 17	2, 15	2, 50	2, 36
	35nm	2, 17	2, 14	3, 25	3, 22

Table 6 : Minimal network size and corresponding express inter- val for express cubes, in the form of

 6

		Linear load	Constant load
	buffer size 4-flit	16-flit	4-flit	16-flit
	0.1µm	3, 13	3, 13	3, 14	3, 13
	70nm	3, 13	3, 12	3, 14	3, 14
	50nm	3, 13	3, 12	4, 15	4, 15
	35nm	3, 13	3, 12	4, 19	4, 18

(v, N min ).

Table 8 : Simulated average flit traversal energy (10 -10 J) of tori, hierarchical tori and express cubes, with the minimal energy at each technology highlighted.

 8

	torus dimension 2	3	4	5	6
	70nm	1.59 1.79 1.98 2.44 N/A
	50nm	1.98 2.14 2.21 2.67 2.83
	35nm	3.53 3.88 3.40 4.03 4.27
	topology H-2 H-3 H-4 E-2 E-3	E-4
	70nm	1.82 1.78 1.88 1.96 1.98 2.15
	50nm	2.07 1.94 1.97 2.19 2.12 2.22
	35nm	3.47 3.14 3.01 3.63 3.38 3.42

Table 9 : Average hop count and flit traversal energy under SPLASH benchmark traces.

 9

	benchmarks LU	water	mp3
	2-D torus	5.07, 201pJ 4.93, 196pJ 1.55, 61pJ
	H-2	3.05, 190pJ 2.97, 185pJ 1.55, 82pJ
	H-3	3.07, 191pJ 3.00, 186pJ 1.55, 82pJ
	H-4	3.26, 198pJ 3.20, 194pJ 1.55, 82pJ
	E-2	4.26, 212pJ 4.09, 207pJ 1.55, 65pJ
	E-3	4.81, 213pJ 4.58, 207pJ 1.55, 65pJ
	E-4	4.87, 211pJ 4.67, 205pJ 1.55, 65pJ

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)