Slim NoC: A Low-Diameter On-Chip Network Topology
for High Energy Efficiency and Scalability
Maciej Besta1
Syed Minhaj Hassan2
Sudhakar Yalamanchili231,3Rachata Ausavarungnirun
Onur Mutlu
Torsten Hoefler1
1 ETH Zürich

2 Georgia Institute of Technology

NoC leads to long inter-router links that may span the whole die. To
fully utilize such long links, buffers must be enlarged in proportion
to the link length. Large buffers are power-hungry [47] and they
may hinder the scalability of different workloads. Moreover, using
more ports further increases the router buffer area, leaving lessspace for cores and caches for a fixed die size. We aim to solve theseissues and preserve the advantages of high radix and low diameterto enable more energy-efficient and scalable NoCs.
In this work, we first observe that some state-of-the-art low-diameter off-chip networks may be excellent NoC candidates that caneffectively address the above area and power issues. We investigate
Dragonfly (DF) and Slim Fly (SF), two modern topologies designed
for datacenters and supercomputers. Dragonfly [39] is a high-radix
diameter–3 network that has an intuitive layout and it reduces thenumber of long, expensive wires. It is less costly than torus, Folded
Clos [42, 59], and Flattened Butterfly [38] (FBF). Slim Fly [11]1 has
lower cost and power consumption. First, SF lowers diameter andthus average path length so that fewer costly switching resources
are needed. Second, to ensure high performance, SF is based ongraphs that approximate solutions to the degree-diameter problem,
well-known in graph theory [45]. These properties suggest that SF
may also be a good NoC candidate.
Unfortunately, as we show in § 2.2, naively using SF or DF as
NoCs consistently leads to significant overheads in performance,
power consumption, and area. We analyze the reasons behind thesechallenges in § 2.2. To overcome them, and thus enable high-radix
and low-diameter NoCs, we propose Slim NoC (SN), a new family of
on-chip networks inspired by SF.
The design of Slim NoC is based on two key observations. First,
we observe that SF uses degree-diameter graphs that are challenging
to lay out to satisfy NoC constraints such as the same number ofrouters or nodes on each side of a die. To solve this problem, our key
idea is to use non-prime finite fields to generate diameter–2 graphs
for SN that fit within these constraints (§ 3.1) and thus can be used
to manufacture chips with tens, hundreds, and thousands of cores.
Second, we observe that most off-chip topologies optimize cost andlayouts in a way that does not address NoC limitations, resulting inlarge buffers. We solve this problem with NoC-optimized SN layouts
and cost models that consider average wire lengths and buffer sizes(§ 3.2). The resulting SN design outperforms state-of-the-art NoC
topologies, as our experiments show (§ 5).
To make SN even more scalable and efficient, we augment itwith orthogonal state-of-the-art router microarchitecture schemes:
central buffer routers [31] (to decrease buffer area), Elastic Links [46]and ElastiStore [60] (to increase performance and power efficiency),
and SMART links [15] (to reduce latency). Doing so leads to a lowdiameter and energy-efficient NoC that outperforms other designs,

Abstract
Emerging chips with hundreds and thousands of cores require networks with unprecedented energy/area efficiency and scalability.
To address this, we propose Slim NoC (SN): a new on-chip network
design that delivers significant improvements in efficiency and scalability compared to the state-of-the-art. The key idea is to use twoconcepts from graph and number theory, degree-diameter graphs
combined with non-prime finite fields, to enable the smallest number of ports for a given core count. SN is inspired by state-of-the-art
off-chip topologies; it identifies and distills their advantages for NoC
settings while solving several key issues that lead to significant
overheads on-chip. SN provides NoC-specific layouts, which further
enhance area/energy efficiency. We show how to augment SN withstate-of-the-art router microarchitecture schemes such as Elastic
Links, to make the network even more scalable and efficient. Our
extensive experimental evaluations show that SN outperforms bothtraditional low-radix topologies (e.g., meshes and tori) and modern
high-radix networks (e.g., various Flattened Butterflies) in area, latency, throughput, and static/dynamic power consumption for bothsynthetic and real workloads. SN provides a promising direction inscalable and energy-efficient NoC topologies.
CCS Concepts • Networks → Network architectures; Network
performance evaluation; • Computer systems organization →Parallel architectures; • Hardware → Networking hardware;
Keywords on-chip-networks; energy efficiency; scalability; manycore systems; parallel processing

1

3 Carnegie Mellon University

Introduction

Massively parallel manycore networks are becoming the base of
today’s and future computing systems. Three examples of such systems are: (1) SW26010, a 260-core processor used in the world’s
fastest (≈93 petaflops in the LINPACK benchmark [23]) supercomputer Sunway TaihuLight [28]; (2) PEZY-SC2 [54], a Japanese chipwith 2048 nodes used in the ZettaScaler-2.2 supercomputer; (3)Adapteva Epiphany [51], a future processor with 1024 cores.
To accommodate such high-performance systems, one needs highperformance and energy-efficient networks on a chip (NoCs). A
desirable network is both high-radix (i.e., its routers have many
ports) and low-diameter (i.e., it has low maximum distance between
nodes) as such networks offer low latency and efficient on-chipwiring density [38]. Yet, combining high radix and low diameter in a
Publication rights licensed to ACM. ACM acknowledges that this contribution was
authored or co-authored by an employee, contractor or affiliate of a national government. As such, the Government retains a nonexclusive, royalty-free right to publish or
reproduce this article, or to allow others to do so, for Government purposes only.
ASPLOS ’18, March 24–28, 2018, Williamsburg, US© 2018 Copyright held by the owner/author(s). Publication rights licensed to the Association for Computing Machinery.
ACM ISBN 978-1-4503-4911-6/18/03. . . $15.00
https://doi.org/10.1145/3173162.3177158

1 We consider the MMS variant of Slim Fly as described by Besta and Hoefler [11].

For details, please see the original Slim Fly publication [11].

1ASPLOS ’18, March 24–28, 2018, Williamsburg, US

M. Besta, S. M. Hassan, S. Yalamanchili, R. Ausavarungnirun, O. Mutlu, T. Hoefler

20
10

SlimNOC

0.008

0.024

0.080

Load [flits/node/cycle]

0.0015Torus
0.0010Mesh

0.00050.0000

0.005

0.004

Network structure

SlimNOC

Physical layout

SlimNOC
Flattened
Butter y

Flattened
Butter y

0.003

Torus
0.002

Mesh

0.001

Buffer models

ter

Torus

9 co

30

res/r
ou

40

res/
rou
t

Mesh

er

50

0.0020Throughput / Power [flits/J]

Flattened Butter ies(with xed bisection
bandwidth)

Throughput/Power [flits/J]

60

8 co

Average packet latency [cycles]

as shown in Figure 1. Example advantages of SN over an FBF, amesh, and a torus (all using the same microarchitectural schemes asSN) are: (1) latency is lower by ≈10%, ≈50%, and ≈64%, respectively,(2) throughput/power is higher by ≈18%, >100%, and >150% (at45nm), and ≈42%, >150%, and >250% (at 22nm).

0.000

Network

Network(a) Latency (an adversar- (b) Throughput per (c) Throughput perial traffic pattern)
power (45nm)
power (22nm)
Figure 1. Example advantages of Slim NoC over high- and low-radix NoC
topologies (1296 cores); see § 5.1 for detailed methodology. We omit performance data for points after network saturation.

The number of nodes in the whole network
The number of nodes attached to a router (concentration)
The number of channels to other routers (network radix)
Router radix (k = k ′ + p )The number of routers in the network
The diameter of a network
A parameter that determines the structure of an SN (see § 2.1)

Mxiyi
| VC |

The average Manhattan distance between connected routers
x coordinate of a router i (1 ≤ i ≤ N r ) and its attached nodes
y coordinate of a router i (1 ≤ i ≤ N r ) and its attached nodes
The number of virtual channels per physical link
A router label in the subgroup view: G is a subgroup type, a is
[G |a, b]
a subgroup ID, b is the position in a subgroup; Figure 2 shows details
The number of hops (between routers adjacent toHeach other on a 2D grid) traversed in one link cycle

δi j
δ cb
∆eb
∆cb
b
L
Ti j
W

The size of an edge buffer at a router i connected to j [flits]
The size of a single central router buffer [flits]
The total size of router buffers in a network with edge buffers [flits]
The total size of router buffers in a network with central buffers [flits]
The bandwidth of a link [bits/s]
The size of a flit [bits]
Round trip time on the link connecting routers i and j [s]The maximal number of wires that can be placed over one routerand its attached nodes

Table 1. Symbols used in the paper.

SF Structure Intuition. SF has a highly symmetric structure;
see Figure 2a. It consists of identical groups of routers (see the middle
part of Figure 2a). Every two such groups are connected with thesame number of cables. Thus, the SF network is isomorphic to a
fully-connected graph where each vertex is a collapsed SF group.
Still, routers that constitute a group are not necessarily fully-connected. Finally, each group consists of two subgroups of an identicalsize. These subgroups usually differ in their cabling pattern [11].
SF Structure Details. Routers in SF are grouped into subgroups
with the same number of routers (denoted as q). There are two typesof subgroups, each with the same pattern of intra-group links. Every
two subgroups of different types are connected with the same number of cables (also q). No links exist between subgroups of the same
type. Thus, subgroups form a fully-connected bipartite graph wherean edge is formed by q cables. Subgroups of different types can bemerged pairwise into identical groups, each with 2q routers. Groups
form a fully-connected graph where an edge consists of 2(q − 1)cables. The value of q determines other SF parameters2 , including
the number of routers Nr , the network radix k ′ , the number of nodes
N , and the concentration p.
SF vs. DF. Intuitively, SF is similar to the balanced DF [39] that
also consists of groups of routers. Yet, only one cable connects two
DF groups (see Figure 2a), resulting in higher D and a lower numberof inter-group links. Moreover, each DF group is a fully-connected
graph, which is not necessarily true for SF. Finally, SF reduces thenumber of routers by ≈25% and increases their network radix by≈40% in comparison to a DF with a comparable N [11].
As shown in past work [11], SF maximizes scalability for a fixed
k and D = 2, while maintaining high bandwidth. Other advantagesof SN (low cost, power consumption, latency, high resilience) stemfrom the properties of the underlying degree-diameter graphs. For
these, we refer the reader to the original SF work [11].

We comprehensively compare SN to five NoC topologies (2Dmesh, torus, two Flattened Butterfly variants, and briefly to hierarchical NoCs [42, 76]) using various comparison metrics (area,
buffer sizes, static and dynamic power consumption, energy-delay,
throughput/power, and performance for synthetic traffic and real applications). We show that SN improves the energy-delay product by≈55% on average (geometric mean) over FBF, the best-performing
previous topology, on real applications, while consuming up to ≈33%
less area. We also analyze SN’s sensitivity to many parameters, suchas (1) layout, (2) concentration, (3) router cycle time, (4) network size,(5) technology node, (6) injection rate, (7) wire type, (8) buffer type,(9) bisection bandwidth, (10) router microarchitecture improvement,(11) traffic pattern, and find that SN’s benefits are robust.
Our comprehensive results show that SN outperforms state-ofthe-art topologies for both large and small NoC sizes.

2

N
p
k′
k
Nr
D
q

BackgroundTo alleviate issues of SF for on-chip networks, we first provide
background on the SF topology (§ 2.1). We then analyze SF’s performance when used as an on-chip network (§ 2.2).
We broadly introduce the elements and concepts we use in Slim
NoC. For the reader’s convenience, we first summarize all symbols
in the paper in Table 1.
2.1 The Slim Fly Topology: The Main Inspiration
SF [11] is a cost-effective topology for large computing centers thatuses mathematical optimization to minimize the network diameter D
for a given radix k while maximizing the number of attached nodes
N (i.e., network scalability) and maintaining high bandwidth. There
are two key reasons for SF’s advantages. First, it lowers diameter(D = 2): this ensures the lowest latency for many traffic patterns,
and it reduces the number of required network resources (packets
traverse fewer routers and cables), lowering cost and static/dynamic
power consumption [11]. Second, it uses graphs that approach the
Moore Bound (MB) [45], a notion from graph theory that indicatesthe upper bound on the number of vertices in a graph with a given D
and k. This maximizes scalability and offers high resilience to link
failures because the considered graphs are good expanders [55].

2 q can be any prime power such that q = 4w + u ; w ∈ N, u ∈ {±1, 0} . An SF with a3q−u

given q has the number of routers N r = 2q 2 , the network radix k ′ = 2 , and theh ′inumber of nodes N = N r p . The concentration p is k2 + κ ; κ is a user-specified
parameter that determines a desired tradeoff between higher node density (larger κ )and lower contention (smaller κ ).

2

Slim NoC: A Low-Diameter On-Chip Network Topology

ASPLOS ’18, March 24–28, 2018, Williamsburg, US(a) (§ 2.1) A comparison between Slim Fly and Dragonfly [39].
(b) (§ 3.2) Labeling and indices of Slim Fly routers.
Figure 2. An illustration of the Slim Fly structure and the labeling as well as indices used in the Slim NoC design.

constraints (e.g., die dimensions or numbers of nodes) or reduce
wiring complexity. We analyze graphs resulting from non-prime
finite fields that enable Slim NoCs with at most 1300 nodes andsummarize them in Table 2. The bold and shaded configurations inthis table are the most desirable as their number of nodes is a powerof two (marked with bold font) or they have equally many groupsof routers on each side of a die (marked with grey shades).
The underlying graph of connections in Slim NoC has the samestructure based on groups and subgroups as the graph in Slim Fly(see § 2.1).3 To construct Slim NoC, one first selects (or constructs) agraph that comes with the most desirable configuration (see Table 2).
Second, one picks the most advantageous layout based either on
the provided analysis (§ 3.3), or one of the proposed particular Slim
NoC designs (§ 3.4), or derives one’s own layout using the provided
placement, buffer, and cost models (§ 3.2).

Slim Fly and Dragonfly for On-Chip Networks

3e−04

Torus

j ′k
j ′k
Network Router
Network ConcenInput
p = k2 ∗ p/ k2 ∗∗ size N count N param. q
radix k ′ tration pr(a) Wire length(b) Normalized area (c) Normalized power
Figure 3. Disadvantages of Slim Fly and Dragonfly used straightforwardly
as NoCs (analyses in Figures 3b–3c use 200 cores). i-routers anda-routers are router areas in intermediate and active layers.

Based on Figure 3, we provide two observations. First, compared
to PFBF, SF requires ≈38% longer wire length, consumes >30%
more area and power, has ≈10% higher latency (not shown), andprovides ≈35% lower throughput (not shown). Second, we find that
DF used on-chip comes with similar overheads. The reasons are asstated in § 1: both SF and DF do not optimize for NoC constraints,
use layouts and cost models optimized for rack-level systems, andminimize the use of resources such as bandwidth that are plentiful
in NoC settings.

3

Slim NoC Design and Layouts

6
6
6
12
12
12
12
12
13
13
13
13

3
3
3
6
6
6
6
6
7
7
7
7

2
3
4
4
5
6
7
8
5
6
7
8

66%
100%
133%
66%
83%
100%
116%
133%
71%
85%
100%
114%

64
96
128
512
640
768
896
1024
810
972
1134
1296

32
32
32
128
128
128
128
128
162
162
162
162

4
4
4
8
8
8
8
8
9
9
9
9

3
5
5
5
7
7
7
11
11
11
11
11

2
3
3
3
4
4
4
6
6
6
6
6

2
2
3
4
3
4
5
4
5
6
7
8

100%
66%
100%
133%
75%
100%
120%
66%
83%
100%
116%
133%

16
36
54
72
150
200
250
392
490
588
686
784

8
18
18
18
50
50
50
98
98
98
98
98

2
3
3
3
5
5
5
7
7
7
7
7

Table 2. The configurations of Slim NoC where the network size N ≤ 1300
nodes. Bold font indicates that in a particular configuration N is a powerof two. Grey shade indicates that there are equally many groups on all die
sides. Dark grey shade means that, in addition to that, the number of nodes
in a given configuration is a square of some integer number. ∗ The ideal
concentration, ∗∗ over- or undersubscription.

We first describe the core ideas in SN and how to build it (§ 3.1). Then,
we present generic SN models for router placement, sizes of routerbuffers, and the total cost of a network with a given layout (§ 3.2).
Finally, we describe and analyze cost-effective SN layouts (§ 3.3).
Detailed mathematical formulations of generating the underlying
SN graphs are in our extended technical report [10].
3.1Non-prime finite fields

F
D

M

SF

C

2000

FB
PF F
BF
T2
D

1000

Number of cores

0.01

0.00

0e+00
0

wires

M
SF
D
F

2.5

6e−04

routers
0.02

C

5.0

Power from:

wires

FB
PF F
BF
T2
D

y )
r
te th
ut id
. B ndwtayFl ll bar(fu
tte ix)Bu d
t. d ra
a
l
e
F x
(

7.5

i−routers
a−routers

Static power/node [W]9e−04

Dragon y

Area/node [cm^2]

Average wire length [hops]

Area due to:

Slim Fly

10.0

Prime finite fields

2.2

We first investigate whether SF or DF can be used straightforwardly
as NoCs (see Section 5 for our methodology). We focus on DF and SF
as they are the most effective topologies with diameter three and two,
respectively [11, 39]. They are also direct topologies (each router is
attached to equally many cores) and thus easier to manufacture as
NoCs. Figure 3 compares SF and DF to a torus (T2D), a concentrated
mesh (CM) [9], and two Flattened Butterflies: a very high-radix fullbandwidth Flattened Butterfly topology (FBF) and an alternative
design that has the same bandwidth as the SF topology (PFBF).

3.2

ModelsSN reduces diameter to two for low latency. It also minimizes radix
k to limit area and power consumption. Yet, when deploying the
network on a chip, this may require long multi-cycle links that

Key Ideas in Slim NoC Construction and Models

Our key idea related to constructing SN is to use non-prime finite
fields [11, 65] to generate the underlying Slim NoC graphs. Specifically, we discover that graphs based on such fields fit various NoC

3 We offer full mathematical formulations in our technical report [10].

3ASPLOS ’18, March 24–28, 2018, Williamsburg, US

M. Besta, S. M. Hassan, S. Yalamanchili, R. Ausavarungnirun, O. Mutlu, T. Hoefler

span a large physical distance. Thus, one needs larger buffers to
fully utilize the wire bandwidth, overshadowing the advantages ofminimized radix k. To alleviate this, we develop new placement,
buffer, and cost models for SN (§ 3.2.1–§ 3.2.3) and use them toanalyze and compare cost-effective layouts that ultimately minimize
the average Manhattan distance and the total buffer area.
3.2.1

or (x i , yi ), (x j , yi ), and (x j , y j ) (if |x i − x j | ≤ |yi − y j |), spreading
wires over routers in a balanced way.
The placed wires must adhere to certain placement constraints.
We formally describe these constraints for completeness and reproducibility (readers who are not interested in these formal constraints
can proceed to § 3.2.2). Specifically, there is a maximum numberof wires W that can be placed over a router (and attached nodes).
To count wires that traverse a router (and its attached nodes) withgiven coordinates, we use functions Φ, Ψ, ϕ, and ψ . First, for any
two routers with indices i and j, Φ(i, j) and Ψ(i, j) determine if the
distance between i and j is larger along the X or Y axis, respectively:

Placement Model

When building SN, we place routers on a chip seen as a 2D grid. To
analyze different placements, we introduce a model. The model mustassign routers their coordinates on a 2D grid, place wires between
connected routers, and be easy to use. The model consists of fourparts: assigning labels, indices, coordinates, and placing wires.
Labels. We first name each router with a label that uniquely encodes the router position in the SN “subgroup view” (see the leftmost
picture in Figure 2a). In this view, any router can be identified using
three numbers: (1) type of its subgroup (corresponds to light or darkgrey), (2) ID of its subgroup (top-most to bottom-most), and (3) its
position in the subgroup (leftmost to rightmost). Labels are based on
the subgroup view as its regular structure enables straightforward
visualization and identification of routers in any SN. Figure 2b shows
the labeling. A router is labeled as [G |a, b]. These symbols encode
the subgroup type (G ∈ {0, 1}), the subgroup ID (a ∈ {1, ..., q}), andthe position in a subgroup (b ∈ {1, ..., q}).
Indices. Second, we translate labels into indices such that eachrouter has a unique index i ∈ {1...Nr } based on its label. A formulathat ensures uniqueness is i = Gq 2 + (a − 1)q + b. Figure 2b showsdetails. We use indices derived from labels because, while labels are
straightforward to construct and use, indices facilitate reasoning
about router coordinates on a 2D grid and wire placement.
Coordinates. Indices and labels are used to assign the actual coordinates on a 2D grid; see Figure 4a. A router i ∈ {1...Nr } is assigned
coordinates (x i , yi ). These coordinates become concrete numbers
based on the labels in each layout. More details are in § 3.3. We
assume that routers form a rectangle and 1 ≤ x i ≤ X , 1 ≤ yi ≤ Y .
Wires. For two connected routers i and j, we place the connecting
link using the shortest path (i.e., using the Manhattan distance). If therouters lie on the same row or column of the grid, there is only one
such path. Otherwise, there are two such paths. We break ties by placing the first wire part (originating at router i) vertically (along the Yaxis) or horizontally (along the X axis) depending on whether thevertical or horizontal distance is smaller. Formally, we place a wire
along the points (x i , yi ), (x i , y j ), and (x j , y j ) (if |x i − x j | > |yi − y j |),Φ(i, j ) = 1 if |x i − x j | > |yi − y j |, and 0 otherwise(1)

Ψ(i, j ) = 1 if |x i − x j | ≤ |yi − y j |, and 0 otherwise.

(2)

Second, given a router pair i and j, ϕ i j (k, l ) and ψi j (k, l ) determine if a router with coordinates (k, l ) is located on one of the two
shortest Manhattan paths between i and j (ϕ is responsible for the“bottom-left” path as seen in a 2D grid while ψ is responsible forthe “top-right” part)1, if k = x i ∧ min{yi , y j } ≤ l ≤ max{yi , y j }
ϕi j (k, l ) =  1, if l = y j ∧ min{x i , x j } ≤ k ≤ max{x i , x j } 0, otherwise
1, if k = x j ∧ min{yi , y j } ≤ l ≤ max{yi , y j }
1, if l = yi ∧ min{x i , x j } ≤ k ≤ max{x i , x j }ψ i j (k, l ) =  0, otherwise.

To derive the total count of wires crossing a router with coordinates (k, l ), we iterate over all pairs of routers and use Φ, Ψ, ϕ,and ψ to determine and count wires that cross (k, l ). For a single
pair of routers i and j, the expression ϕ i j (k, l )Φ(i, j) + ψi j (k, l )Ψ(i, j)
indicates whether the Manhattan path between i and j crosses (k, l )(the first or the second product equals 1 if the path is “bottom-left”
or “top-right”, respectively). Next, we multiply the sum of theseproducts with εi j : this term determines if routers i and j are connected with a link (εi j = 1) or not (εi j = 0). Finally, for each (k, l ),we verify whether its associated wire count is lower than W , themaximum value dictated by the technology constraints:
Nr X
Nr
X

ε i j [ϕi j (k, l )Φ(i, j ) + ψ i j (k, l )Ψ(i, j )] ≤ W

i =1 j =1(a) (§ 3.2) The placement model with two example wires.
(b) (§ 3.2) Different physical SN layouts.
Figure 4. The details of the SN layout.

4(3)

Slim NoC: A Low-Diameter On-Chip Network Topology

Minimizing Wire Length. The average wire length M is

Buffer Size Model

Next, we formally model the size of buffers to provide a tool thatenables comparing different Slim NoC layouts in how they reduce
the total buffer size.
Edge Buffers. We model the size of an edge buffer integrated
witha router i and connected to a wire leading to router j as δi j =Ti j b|VC | /L. This size is proportional to the round trip time (RTT)
between i and j (Ti j ), link bandwidth (b), and virtual channel countper physical link (|VC
to the flit size (L).
j |). It is inversely proportionalk
The RTT is Ti j = 2 (|x i − x j | + |yi − y j |)/H +3 and is proportional
to the Manhattan distance between i and j. H is the number of hops
traversed in one link cycle (a hop is a part of a wire between routers
placed next to each other (vertically or horizontally) on a 2D grid). H
is 1 without wire enhancements (such as SMART [15]). We add twocycles for router processing and one cycle for serialization latency.
Lower Latency in Long Wires with SMART Links.
SMART [15] is a technique that builds on driving links asynchronously and placing repeaters carefully to enable single-cycle
latency in wires up to 16mm in length at 1GHz at 45nm. For wires
that cannot be made single-cycle this way, we assume that SMART
can be combined with EB links [46] to provide multi-cycle wires
and full link utilization. We assume SMART has no adverse effecton SN’s error rates as it achieves bit error rates < 10−9 , similarly tolinks with equivalent full-swing repeaters [15].
With SMART links, the value of H depends on the technology
node and the operational frequency (typically, 8-11 at 1GHz in45nm) [15]. RTT still grows linearly with wire length; SMART links
simply limit the growth rate by a factor of H because a packet can
traverse a larger distance on a chip (measured in the distances between neighboring routers) in one cycle. Note that this model may
result in edge buffers at different routers having different sizes. To
facilitate router manufacturing, one can also use edge buffers ofidentical sizes. These sizes can be equal to: (1) the minimum edge
buffer size in the whole network (reducing ∆eb but also potentiallylowering performance), (2) the maximal edge buffer size in the wholenetwork (increasing ∆eb but potentially improving throughput), and(3) any tradeoff value between these two.
Central Buffers. We denote the size of a CB as δcb , this number
is a selected constant independent of |VC |, b, L, or Ti j . CB size isempirically determined by an SN designer.
3.2.3

Sum of distances
M==
Number of links

All routerpairs i, j

∆cb =

sn_gr
sn_subgr

6

Layout:sn
sf_randsn
sf_basic
sf_gr
sn
sf_subgr
sn

4
2

3.3

0

500

1000

1500

2000

N [cores]

If i, j are connected(ε i j = 1), add the sizeof a buffer from i to j
(δ i j = Ti j b |V C |/L )CBR40

For N=54, CBR40
uses comparable
bu er space toedge-bu er designs

sn_basic
sn_randsn_gr
sn_subgr

CBR40
CBR20

50

CBR20

1000

1500

εi j δi j(5)

i =1 j =1

Size of a central buffer (δ cb )+ Size of I/O staging buffers = N r (δ cb + 2k ′ |V C |)(2k ′ |V C | )All routers

100

sn_subgr

500

Nr X
Nr
X

X

150

200

0

=

(6)

Cost-Effective Slim NoC Layouts

200

400

0

(4)

We now use the placement, buffer, and cost models from § 3.2 todevelop and analyze layouts that minimize the average wire lengthand the sum of all buffers sizes (see Figure 4b). For each layout, we
provide detailed coordinates as a function of router labels [G |a, b](defined in Table 1 and in § 3.2.1, paragraph “Labels”). We startfrom the basic layout (sn_basic): subgroups with identical intrasubgroup connections are grouped together and a router [G |a, b]
has coordinates (b, a + Gq). As such subgroups are not directly
connected, this layout may lengthen inter-subgroup links. To avoid
this, the subgroup layout (sn_subgr) mixes subgroups pairwise toshorten wires between subgroups. In this layout, a router [G |a, b]
has coordinates (b, 2a − (1 − G)). Both sn_basic and sn_subgr
have a rectangular shape (q × 2q routers) for easy manufacturing.
Finally, to reduce the wiring complexity, we use the group layout(sn_gr) where subgroups of different types are merged pairwise
and the resulting groups are placed in a shape as close to a squareas possible. The router coordinates are far more complex than in
the other layouts and we provide them in our technical report [10].
In sn_gr, there are q groups, each group has identical intra-groupconnections, and 2(q − 1) wires connect every two groups.
Total buffer size [flits]

Total buffer size [flits]

Average M [hops]

sn_basic
sn_rand600

8

j=1 ε i j ( |x i − x j | + |yi − y j |).
P Nr P Nr
i =1 j=1 ε i j

We calculate the size of the central buffers by a combining thesize of the central buffer itself (δcb ) with the size of the staging I/O
buffer (|VC | per port). The final sum is independent of wire latencies
and the use of SMART links.

nd
_ra
ic
sn
bas
sn_
sn_gr
sn_gr
sn_subgr

800

X

∆eb =

Cost Model

sn_basic
sn_randi =1

To obtain M, we divide the sum of the Manhattan distances between
all connected routers (the nominator in Eq. (4)) by the number ofconnected router pairs (the denominator in Eq. (4)). In Eq. (4), we
iterate over all possible pairs of routers along both dimensions, andεi j determines if routers i and j are connected (εi j = 1) or not(εi j = 0).
Minimizing Sum of Buffer Sizes. One can also directly minimize the total sum of buffer sizes (∆eb for an SN with edge buffersand ∆cb for an SN with central buffers). To derive the size of edge
buffers (∆eb ), we sum all the terms δi j

We now use the layout and buffer models to design the SN costmodel. We reduce the average router-router wire length (M) andthe sum of all buffer sizes in routers (∆eb or ∆cbr ).

10

P Nr P Nr

1500

1000

Max W

3.2.2

ASPLOS ’18, March 24–28, 2018, Williamsburg, US(22 Uppnm er btec ounhn dologLayout:
W_22nmsn
sf_basic
sf_randsn
sf_subgr
sn
sf_gr
sn

y)

500

0

2000

0

N [cores]

500

1000

1500

N [cores](a) Average wire length M .

2000

0

500

1000

1500

2000

2500

N [cores](b) Total size of all buffers in one(c) Total size of all buffers in one(d) The maximum number of wires
router (no SMART).
router (with SMART).
placed over a router W .
Figure 5. (§ 3.3) The analysis of link lengths and buffer sizes in SN with different layouts ((a)–(c)). The illustration of technological constraints from Eq. (3) (d).

5

ASPLOS ’18, March 24–28, 2018, Williamsburg, US
3.3.1

M. Besta, S. M. Hassan, S. Yalamanchili, R. Ausavarungnirun, O. Mutlu, T. Hoefler

Evaluating Average Wire Length M and Total Buffer
Size ∆eb , ∆cb

problems can be solved using optimization software such as IBM
CPLEX [33] to provide even more cost-effective layouts.

We evaluate each layout by calculating M, ∆eb , and ∆cb ; the results
are shown in Figure 5. We also compare to a layout where routers
are placed randomly in q × 2q slots (sn_rand). Figure 5a shows
M. Both sn_subgr and sn_gr reduce the average wire length by≈25% compared to sn_rand and sn_basic. This reduces ∆eb as
illustrated in Figure 5b; sn_gr reduces ∆eb by ≈18%.
Investigating Details. Figure 6 shows the distribution of wire
distances in SNs with N ∈ {200, 1024, 1296} (these SNs are describedin detail in § 3.4) for two best layouts: sn_subgr, sn_gr. The
distributions for N ∈ {1024, 1296} are similar. We find that sn_gr
uses the largest number of the longest links for N = 200, while
sn_subgr uses fewer links traversing the whole die. We use thisfor designing example ready-to-use Slim NoCs (§ 3.4) that reduce theaverage wire length the most. We analyze other SNs for 1 ≤ q ≤ 37:
Both sn_gr and sn_subgr consistently reduce the number of thelongest wires compared to sn_rand and sn_basic, lowering M
and ∆eb or ∆cb .

Examples of Slim NoC Networks

We now illustrate example SNs that use layouts from § 3 and canbe used to manufacture future massively parallel chips. They are allavailable in an exhaustive library of SNs [10].
A Small Slim NoC for Near-Future Chips. We first sketch
an SN design in Figure 7a with 200 nodes and 50 routers (denoted
as SN-S), targeting the scale of the SW26010 [28] manycores thatare becoming more common [24]. The input parameter q = 5 isprime and SN-S is based on a simple finite field {0, ..., 4}. SN-S
uses concentration p = 4 and network radix k ′ = 7, and it consistsof 10 subgroups and five groups. Thus, for a rectangular die (10 × 5
routers), we use the subgroup layout. This layout also minimizes thenumber of the longest links traversing the whole chip, cf. Figure 6.
A Large Slim NoC for Future Manycores. The next SN design(denoted as SN-L) addresses future massively parallel chips with
>1k cores. We use network radix k ′ = 13 and concentration p = 8(one router with its nodes form a square). As the input parameterq = 9 = 32 is a prime power, we use a finite field F9 that cannot bea simple set {0, ..., 8} but must be designed by hand (see our reportfor details [10]). SN-L has a regular structure with 1296 nodes and
162 routers belonging to 9 identical groups (18 × 9 routers). Thus,
we use the group layout for easy manufacturing (3 × 3 groups) thatis illustrated for this particular design in Figure 7b.
A Large Slim NoC with Power-of-Two N . We also construct
an SN with 1024 nodes and router radix 12. Its core count matches
the future Adapteva Epiphany [51] chip. This SN uses a subgrouplayout. Similarly to SN-L, it is based on a prime power q = 8.

N = 1296
For example...
...these two bars showthat the probability of
two connected routers
having a distance of 7
or 8 is around 0.06 for
sn_gr and sn_subgr

9-10
11-12
13-14
15-16
17-18
19-20
21-22

sn_subgr

1-2
3-4
5-6
7-8

sn_gr

9-10
11-12
13-14
15-16
17-18
19-20
21-22

0.0

Layout:...these two bars showthat the probability of
two connected routers
having a distance of 1
or 2 is around 0.25 for
sn_gr and sn_subgr

1-2
3-4
5-6
7-8

0.1

N = 1024

9-10
11-12
13-14
15-16
17-18
19-20
21-22

0.2

1-2
3-4
5-6
7-8

Probability density

N = 200
For example...

3.4

Distance ranges
Figure 6. (§ 3.3) Distribution of link distances in SNs. A bar associated witha distance range X illustrates the probability that, for a given layout, tworouters are connected with a link that has the distance falling within X . Barsof different colors are placed pairwise so that it is easier to compare thesubgroup and group layouts.

4

Slim NoC Microarchitecture

SN provides the lowest radix k ′ for the diameter of two, minimizing
buffer area and power consumption while providing low latency.4
In this section, we further reduce buffer space by extending SN with
Central Buffers (CBs) [31] and optimizing it with ElastiStore (ES) [60].
We first provide background information on CBs and ES (§ 4.1).
Then, we show how to combine CBs with virtual channels (VCs)
to enable deadlock-freedom (§ 4.2), describe our deadlock-freedom
mechanism (§ 4.3), and explain how to maintain full utilization oflinks when using routers with central buffers (§ 4.4).

Adding SMART. With SMART [15], our sn_subgr and sn_gr
layouts reduce ∆eb by ≈10% compared to sn_basic (Figure 5c).
Adding CBRs. We consider small CBs (δcb = 20) and large CBs(δcb = 40). As shown in Figures 5b–5c, CBs result in the lowest total
buffer size because the CB size is independent of network radix (k ′ )and the round-trip time between routers (Ti j ).
3.3.2 Verifying Constraints
We verify that SN layouts satisfy Eq. (3), i.e., the technological wiringconstraints. We assume intermediate metal layers [9], wiring densities of 3.5k/7k/14k wires/mm, and processing core areas of 4mm2 /1mm2 / 0.25mm2 at 45nm / 22nm / 11nm [13]. W is the product of thewiring density and the length of a side of a core. We assume that we
use a single metal layer (the worst-case scenario); all the remaining
available layers can be used by caches and other core components.
We present the 45nm analysis in Figure 5d (other technology nodes
are similar). No layout violates Eq. (3). We conclude that SN layouts offer advantageous wire length distributions that satisfy theconsidered technology constraints, enabling feasible manufacturing.

4.1 Techniques to Improve Slim NoC Performance
In order to enhance Slim NoC for high performance and low energy
consumption, we use two additional mechanisms: Elastic Links andCentral Buffer Routers.
Elastic Links: Lower Area and Power Consumption. To reduce the area and power consumption of a NoC, Elastic Buffer (EB)
Links [46, 60] remove input buffers and repeaters within the linkpipelines and replace them with master-slave latches. To prevent
deadlocks in Slim NoC, we use ElastiStore (ES), which is an extension
of EB links [60]. We present design details in § 4.2.
Central Buffer Routers: Less Area. To further reduce area, we
use Central Buffer Routers (CBRs) [31]. In a CBR, multi-flit edge
(input) buffers are replaced with single-flit input staging buffers anda central buffer (CB) shared by all ports. At low loads, the CB is3.3.3 Theoretical Analysis
To formalize SN layouts, we present a detailed theoretical analysis
and our proofs in a technical report [10]. We also illustrate how toformulate the minimization of the average wire length and the sumof buffer sizes as Integer Linear Programming (ILP) problems. Such

4 We use SF as the basis of our new NoC design (as SF consistently outperforms DF

as shown in Figure 3). While we select a variant of SF with diameter two as the main
design in this work [11], most of our schemes are generic and can be applied to any SF
and DF topology.

6

Slim NoC: A Low-Diameter On-Chip Network Topology

ASPLOS ’18, March 24–28, 2018, Williamsburg, US(a) The layout of SN-S, a small-scale SN with N = 200, N r = 50.
(b) The layout of SN-L, a large-scale SN with N = 1296, N r = 162.
Figure 7. (§ 3.4) Example SNs. For clarity, we only show wires connected to two subgroups (in SN-S) and omit inter-group wires (in SN-L).

bypassed, providing a two-cycle router latency. At high loads, incase of a conflict at the output port, a flit passes via the CB, taking
four cycles. A CBR employs 3 allocation and 3 traversal stages,
which increase the area and power in arbiters and allocators. Yet, it
significantly reduces buffer space and thus overall router area andpower consumption [31].

4.3

Ensuring Deadlock Freedom with CBRs

SN with D = 2 uses two VCs to avoid deadlocks: VC0 for the first and
VC1 for the second hop (assuming paths of lengths up to 2). Here,the only dependency is that of VC0 on VC1, which is not enoughto form cycles. We now extend this scheme to the CBR design. To
ensure deadlock freedom, two conditions must be met. First, CB
allocation for a packet must be atomic: it cannot happen that someflits have entered the CB and the rest are stalled in the links waiting
for the CB. Second, head flits of all the packets in different ports andVCs should always be able to compete for the allocation of output
ports and VCs. However, since we focus on deterministic routing
algorithms, this condition is not required for single deadlock-freedeterministic paths.
We satisfy the first condition by reserving the space required
for a complete packet during the CB allocation stage. Thus, once a
packet takes the CB path, it is guaranteed to move completely into
the CB (note that a packet may bypass the CB via the low-load CB
bypass path; see § 4.1). A packet in the CB is always treated as apart of the output buffer of the corresponding port and VC. Thus,
if the baseline routing is deadlock-free, it remains deadlock-freewith the CBR design. Finally, we use SMART links orthogonally to
ElastiStore, only to reduce link latency, ensuring no deadlocks. We
avoid livelocks with deterministic paths.

4.2 Combining Virtual Channels with CBs
Original CBs do not support VCs. To alleviate this, we use ElastiStore(ES) links [60] that enable multiple VCs in the EB channels. The
design is presented in Figure 8. ElastiStore links use a separate
pipeline buffer and associated control logic for each VC. The per-VC
ready-valid handshake signals independently handle the flits of each
VC, removing their mutual dependence in the pipelined link. We
only keep a slave latch per VC and share the master latch between
all VCs. This reduces the overall area and power due to ElastiStorelinks. The resulting performance loss is minimal and reaches |V1C |only when all VCs except one are blocked in the pipeline. Other
modifications (shown in dark grey) include using per-VC (instead of
per-port) I/O staging buffers and CB head/tail pointers to keep VCs
independent. The crossbar radix is k ′ (k ′ +1), like in the original CBR.
For this, we use a small mux/demux before and after the crossbar
inputs and outputs. We maintain single input and output for the CB,
which only negligibly impacts performance [31].

4.4 Maintaining Full Link Utilization with CBRs
Large edge buffers enable full utilization of the bandwidth of longwires. For CBR, we obtain the same effect with elastic links (EBs) [60].
Varying the central buffer size reduces head of line blocking.

5

EVALUATION

We evaluate SN versus other topologies in terms of latency, throughput, ∆cb , ∆eb , area, and power consumption.
5.1

Experimental Methodology

Considered Topologies. We compare SN to both low- and highradix baselines, summarized in Table 3: (1) tori [6] (T2D), (2) concentrated meshes [9] (CM), (3) Flattened Butterflies [38] (FBF). We also
consider SF and DF; their results are consistently worse than others
and are excluded for brevity. Note that, for a fixed N and for D = 2,
k and bisection bandwidth of FBF are much higher than those of SN.

Figure 8. Modifications to the CB router in § 4.

7

ASPLOS ’18, March 24–28, 2018, Williamsburg, US

M. Besta, S. M. Hassan, S. Yalamanchili, R. Ausavarungnirun, O. Mutlu, T. Hoefler

Thus, for a fair comparison, we develop a partitioned FBF (PFBF)
with fewer links to match SN’s k and bisection bandwidth; see Figure 9. We partition an original FBF into smaller identical FBFs
connected to one another by one port per node in each dimension.
PFBF has D = 4 while the Manhattan distance between any tworouters remains the same as in FBF. Finally, even though we focus
on direct topologies, we also briefly compare to indirect hierarchicalnetworks [1].

j √t2d3 3 4 7Nr
t2d4 4 4 8
j√k cm3 3 4 7
N r − 2 cm4 4 4 8
fbf3 3 14 172
fbf4 4 13 17
1
2

T2D
CM
FBF
PFBF
SN

N ∈ {192, 200}
Sym. p k ′ k Routers

D

Network

4
2

k

N

8x8
192
10x5
200
8x8
192
10x5
200
8x8
192
10x5
200
4 FBFspfbf3 3 8 11 (4x4 each) 192
2 FBFspfbf4 4 9 13 (5x5 each) 200
sn_* 4 7 11
10x5
200

N = 1296
Sym. p k ′ k Routerswith central buffers are: 1 (input buffer size per VC), 1 (output buffer
size per VC), 20 (central buffer size), 20 (injection and ejection queuesize). The corresponding sizes for routers without central buffers
are, respectively, 5, 1, 0, 20.
Buffering Strategies. EB and CBR prefixes indicate Edge andCentral Buffer Routers. We use: EB-Small and EB-Large (alledge buffers have the size of 5 and 15 flits), EB-Var-S and EBVar-N (edge buffers have minimal possible sizes for 100% link utilization with/without SMART links), CBR-x (CBs of size x), and
EL-Links (only elastic links).
Synthetic Traffic. We use 5 traffic patterns: random (RND, eachsource s selects its destination d with uniform random distribution),
bit shuffle (SHF, bits in destination ID are shifted by one position),
bit reversal (REV, bits in destination ID are reversed), and two adversarial patterns (ADV1 and ADV2; they maximize load on singleand multi-link paths, respectively). We omit the ADV2 results when
they are similar to the ADV1 results.
Real Traffic. We use PARSEC/SPLASH benchmark traces to evaluate various real workloads. We run three copies of 64-threaded versions of each benchmark on 192 cores to model a multiprogrammed
scenario. We obtain traces for 50M cycles (it corresponds to ≈5 billion instructions for SN-S) with the Manifold simulator [70], using
the DRAMSim2 main memory model [58]. As threads are spawned
one by one, we warm up simulations by waiting for 75% of the cores
to be executing. The traces are generated at L1’s back side; messages
are read/write/coherence requests. Read requests and coherence
messages use 2 flits; write messages use 6 flits (we thus test variable
packet sizes). A reply (6 flits) is generated from a destination for each
received read request.
Performance Evaluation. We use a cycle-accurate in-house
simulator (described by Hassan and Yalamanchili [31, 70]). Simulations are run for 1M cycles. For N ∈ {192, 200} we use detailed topology models (each router and link modeled explicitly). If N = 1296,
due to large memory requirements (>40GB), we simplify the models
by using average wire lengths and hop counts.
Area and Power Evaluation. We estimate general power consumption using the DSENT tool [66]. We break down area andstatic power (leakage) due to (1) router-router wires, (2) routernode wires, and (3) actual routers (RR-wires, RN-wires, androuters). We further break down area into global, intermediate, and active layers (denoted as RRg-wires, RRi-wires, andRRa-wires; RNg-wires, RNi-wires, and RNa-wires; grouters, i-routers, and a-routers, respectively). We break
down dynamic power into buffers, crossbars, and wires.
Technologies and Voltages. We use 45nm and 22nm technologies with 1.0V and 0.8V voltages.
We next present a representative subset of our results. Our extended technical report [10] contains more results and analyses.

N

t2d9 9 4 13
t2d8 8 4 12
cm9 9 4 13
cm8 8 4 12
fbf9 9 22 31
fbf8 8 25 33

12x12 1296
18x9
1296
12x12 1296
18x9
1296
12x12 1296
18x9
1296
4 FBFspfbf9 9 12 21 (6x6 each) 1296
2 FBFspfbf8 8 17 25 (9x9 each) 1296
sn_* 8 13 21
18x9
1296

Table 3. Considered configurations for two example class sizes.

Figure 9. An example partitioned FBF (1D). Nodes are not shown.

Layouts, Sizes. We compare all the SN layouts from § 3.3 fortwo size classes: N ∈ {192, 200} and N = 1296. We use both square
networks as comparison points that are close in size to SN (N = 192)
and rectangular ones with identical N (N = 200); see Table 3.
Cycle Times. We use router clock cycle times to account forvarious crossbar sizes: 0.5ns for SN and PFBF, 0.4ns for topologies
with lower radix (T2D, CM), and 0.6ns for high-radix FBF. In specified cases, for analysis purposes, we also use cycle times that are
constant across different topologies.
Routing. We focus on static minimum routing where paths between routers are calculated using Dijkstra’s Single Source Shortest Path algorithm [63]. This is because we aim to design anenergy-efficient topology. Adaptive routing would increase overall router complexity and power consumption. Our choice is similar
to what is done in many prior works that explored new topologies [8, 29, 30, 69, 74]. Moreover, various works that do not introduce
new topologies but conduct topology-related evaluations also follow
this strategy [21, 22, 37].
Yet, it is clear that the routing algorithm can be customized ordesigned for each topology to maximize performance or energy
efficiency and determining the best routing algorithm on a pertopology basis for a given metric is an open research problem. For
example, SN can be extended to adaptive routing using paradigms
such as the Duato protocol [19], UGAL [62], or up-down routing [19].
We later (§ 6) provide a discussion on adaptive routing in SN. A full
exploration of adaptive routing schemes in SN is left for future work.
Wire Architectures. We compare designs with and without
SMART links. We use the latency from § 3.2.2 and set the number ofhops traversed in one link cycle as H = 9 (with SMART links) andH = 1 (no SMART links). We fix the packet size to 6 flits (except forreal benchmark traces, see below). All links are 128 bits wide.
Router Architectures. We use routers with central buffers orwith edge buffers. An edge router has a standard 2-stage pipeline
with two VCs [53]. The CB router delay is 2 cycles in the bypass
path and 4 cycles in the buffered path. Buffer sizes in flits for routers

5.2

Analysis of Performance (Latency and Throughput)

We first examine the effects of SN layouts and various buffering
strategies on latency and throughput (§ 5.2.1); we next compare SN
to other topologies (§ 5.2.2).
5.2.1

Analysis of Layouts and Buffers

Figure 10 shows how the layouts improve the performance of SN.
All traffic patterns follow similar trends; we focus on RND. Without
SMART links, sn_basic and sn_rand entail higher overheads
8

Slim NoC: A Low-Diameter On-Chip Network Topology

ASPLOS ’18, March 24–28, 2018, Williamsburg, US

than sn_subgr and sn_gr due to longer wires. As predicted theoretically (in § 3), sn_subgr and sn_gr are the best for respectively
N = 200 and N = 1296 in terms of latency and throughput (see thetechnical report [10] for the detailed results for N = 1296).
Layout:sn_subgr has on average 5%
lower latency than sn_basic(geometric mean used)

SHF
sn_randsn_subgr

30
25

40

20

SN layout:
sn_basic

20
0.008 0.04 0.16 0.008 0.04 0.16 0.008 0.04 0.16

sn_gr

sn_subgr

0Latency [cycles]

RND
sn_basic
sn_gr

Latency [cycles]

Latency [cycles]

REV
35

bandwidth. SN’s throughput is marginally lower than that of PFBFin some cases (e.g., N ∈ {192, 200}, REV) because of PFBF’s minimum Manhattan paths. Yet, in most cases SN has a higher throughput than PFBF (e.g., >60% for N = 1296 and RND). SN’s latency isalways lower (≈6-25%) than that of PFBF due to its lower D. Finally,
without SMART links, SN’s longer wires result in higher latency
than FBF in several traffic patterns (≈%26 for RND and N = 1296).
In ADV1, SN outperforms FBF (by ≈18%). We later (§ 5.4, § 6) showthat SN also offers a better power/performance tradeoff than FBF.

s al y p et fft n. c s. ix l. s d s
rne ne sk du rr luidaean−adio radeamc vipolrenater−ba canchole de fe
f oc rv w
str

Load [flits/node/cycle](a) Synthetic traffic.
(b) PARSEC/SPLASH.
Figure 10. (§ 5.2.1) Average packet latency with different SN layouts (without
SMART links) for synthetic traffic and real applications, for N = 200.

1296−No−SMART

Buffers:40

200−No−SMART

1296−SMART
EB−SmallEB−VarEB−Large
EL−Links

0.008

0.04 0.16

0.008

CBR−40CBR−60.04 0.16

0.008

pfbf3

Random (RND)
pfbf4

sn_subgr

Shuffle (SHF)

fbf3

40
30
20
69% 85% 91% 85%
71% 86% 92% 86%
89% 89% 96% 89%
10 54% 69% 85% 72%
0.008
0.06
0.4 0.008
0.06
0.4 0.008
0.06
0.4 0.008
0.06
0.4

60

Percentages are ratios of SN's latency (load=0.008) to:
cm3, t2d3, pfbf4, fbf3 (respectively)

Network:

Reverse (REV)
cm9

t2d9

Random (RND)

pfbf9

sn_subgr

Shuffle (SHF)

fbf9

40
20
46% 63% 75% 75%

0.04 0.16

0.008

Load [flits/node/cycle]

0.06

54% 72% 90% 90%

0.4 0.008

Load [flits/node/cycle]

0.06

54% 72% 90% 90%

0.4 0.008

0.06

72% 73% 90% 90%

0.4 0.008

0.06

0.4

Percentages are ratios of SN's latency (load=0.008) to:
cm9, t2d9, pfbf9, fbf9 (respectively)

Figure 13. (§ 5.2.2) Performance of synthetic traffic with SMART links forlarge networks (N = 1296) and different cycle times for different designs.

Figure 11. (§ 5.2.1) Impact of buffers (edge buffers, central buffers, no buffers);“200”/“1296” mean N = 200/1296; all variants explained in § 5.1.

Latency [cycles]

We analyze two representative CB sizes (6 and 40 flits) in Figure 11; we also test sizes with 10, 20, 70, and 100 flits. We observe that
small CBs outperform (especially for N > 1000) both edge buffers
and EL-Links by removing head-of-line-blocking. Large CBs (e.g.,
CBR-40) can contain more packets, increasing overall latency.
We also derive the total buffer area for each buffering scheme(detailed results are in the technical report [10]): we show that SN
gives the best tradeoff of radix (hence the crossbar size) for a given
diameter and thus it ensures the lowest total buffer size for networks
with diameter two, for both edge and central buffer designs.
Impact of SMART Links. SMART links reduce the relative latency differences between Slim NoCs based on different buffering
schemes to ≈1-3% for most data points, and to up to ≈16% for high injection rates that approach the point of network saturation. SMART
links accelerate SN by up to ≈35% for the sn_subgr layout.
We conclude that: (1) group and subgroup layouts outperformdefault SN designs, (2) SN with edge buffers can have similar latency
and throughput to those of SN designs with elastic links or central
buffers, and (3) SN with small CBs has the best performance.
5.2.2

t2d3

cm3

Adverse 1 (ADV1)

200−SMART

20
0.04 0.16

Reverse (REV)

Network:

Figure 12. (§ 5.2.2) Performance of synthetic traffic with SMART links forsmall networks (N ∈ {192, 200}) and different cycle times for different
designs.

30

0.008

Adverse 1 (ADV1)

Load [flits/node/cycle]

Latency [cycles]

Latency [cycles]

Figure 11 shows the average packet latency with SN using edge
buffers. Without SMART links, small edge buffers lead to higher
latency due to high congestion and high overhead of credit-based
flow control. EL-Links improve throughput but lead to head-ofline blocking. Both edge buffers and elastic links offer comparable
performance to that of central buffers for N ∈ {192, 200}.

50

50

Adverse 1 (ADV1)

Reverse (REV)

Network:

t2d3

cm3

pfbf3

51%
65%
67%
81%

40
30

Random (RND)
sn_subgr

73%
89%
89%
110%

Shuffle (SHF)

fbf3 76%
90%

86%
89%
94%
115%

96%
110%

20
0.008

0.06

0.4 0.008

Load [flits/node/cycle]

0.06

0.4 0.008

0.06

0.4 0.008

0.06

0.4

Percentages are ratios of SN's latency (load=0.008) to:
cm3, t2d3, pfbf3, fbf3 (respectively). Here, pfbf3 pfbf4.

Figure 14. (§ 5.2.2) Performance analysis, N ∈ {192, 200}, no SMART links.

Impact of SMART Links. SMART links do not impact the latency of CM and T2D as these topologies mostly use single-cycle
wires. As expected, SMART links diminish the differences in theperformance of different networks with multi-cycle wires.
5.3

Analysis of Area and Power Consumption

We first briefly analyze area and power differences between various SN layouts. As predicted, sn_subgr outperforms others; forexample, see Figure 15a.
Figures 15b–15c present SN’s advantages for N ∈ {192, 200} without SMART and central buffers. These are gains from the proposedlayouts. SN significantly outperforms FBF in all the evaluated metrics, and PFBF in consumed power. PFBF’s area is smaller; we lateruse SMART to alleviate this.
The corresponding results for N = 1296 are included in our technical report [10]. We provide a brief summary here. Similarly toN ∈ {192, 200}, SN with N = 1296 reduces area (by up to ≈33%) andpower consumption (by up to ≈55%) compared to FBF. An exception

SN versus Other Network Designs

We show that SN outperforms other network designs from Table 3.
The results are in Figures 12–13 (SMART links) and 14 (no SMART
links). As expected, SN always outperforms CM and T2D. For example, for RND and N = 1296, SN improves average packet latency by≈45% (over T2D) and ≈57% (over CM), and throughput by 10x. Thisis a direct consequence of SN’s asymptotically lower D and higher
9

0.75
0.50
0.25

1.00
0.75
0.50

4

SN outperforms
FBF by 34%

Total static power [W]Total area [cm^2]

i-routers
a-routers
RRgwires
RNgwires

0.25
0.00

sn
_
sn ran
_b d
as
s ic
sn n_
_s gr
ub
gr

power. To calculate this metric, we divide the number of flits delivered in a cycle by the power consumed during this delivery. SN
outperforms all the designs; the lowest gain is over FBF due to its
high throughput (≈5-12%) and the highest over low-radix networks(≥50%). Thus, Slim NoC achieves the sweetspot between power
consumption and performance (for random traffic).

SN outperforms
FBF by 43%

3routers+
crossbars

2
1

N ∈ {192, 200}
N = 1296
t2d4 cm4 pfbf3 fbf3 fbf4 t2d9 cm9 pfbf9 fbf8 fbf90

fb
sn pf f4
_ s bf4
ub
g
t2 r
d
cm4
4

0.00

M. Besta, S. M. Hassan, S. Yalamanchili, R. Ausavarungnirun, O. Mutlu, T. Hoefler

fb
f4
sn pfb
_s f4
ub
g
t2 r
d4
cm
4

Total area [cm^2]

ASPLOS ’18, March 24–28, 2018, Williamsburg, US

45nm 96% 97% 17% 12% 6%
22nm 209% 199% 17% 14% 5%

Table 4. (§ 5.4) SN’s advantages in throughput/power (the RND traffic). The
percentages are SN’s relative improvements over other topologies in thethroughput delived per unit of consumed power. To calculate this metric,
we divide the number of flits delivered in a cycle by the power consumed
during this delivery.

(a) Area of various SN(b) Area of various(c) Static power conlayouts.
networks.
sumption.
Figure 15. Area/power analysis without SMART, N = 200 (§ 5.3).

0.001
0.000



f3 f4 f3 n 4 4
fb fb pfb s t2d cm

Dynamic power/node [W]Area/node [cm^2]

RNg-wires

0.02

SN outperforms
FBF by 30%

Norm. energy−delay

Energy-Delay. Figure 18 shows the normalized energy-delay
product (EDP) results (for PARSEC/SPLASH traces) with respect toFBF. SN reduces EDP by ≈55% on average (geometric mean) compared to FBF as it consumes less static and dynamic power. SN’s
EDP is also ≈29% smaller than that of PFBF due to the latter’s higher
latencies and higher power consumption. Similarly, SN reduces EDP
by ≈19% compared to CM.

192/200 22nm 192/200 45nm

0.000
0.004 i-routers
a-routers
0.003
RRg-wires

0.025 SN outperforms
FBF by 46%
0.020
routers+
0.015
crossbars
0.010
0.005
0.000
0.025 SN outperforms
FBF by 49%
0.020
0.015
0.010
0.005
0.000
f3 f4 f3 n 4 4
fb fb pfb s t2d cm

192/200−22nm 192/200−45nm



0.001

0.002

192/200 22nm 192/200 45nm

0.002

Static power/node [W]is pfbf9 as it improves upon SN in both metrics (by ≈10-15%). Yet,
SN’s higher throughput improves the power/performance tradeoffby ≈24% (more details in § 5.4). Thus, SN outperforms FBF (in areaand power consumption) and PFBF, CM, and T2D (in power/performance) in designs with N > 1000.
Impact of SMART Links. Figures 16–17 shows the effect of
SMART links on SN. SN reduces area over FBF (≈40-50%) and PFBF(≈9%) as it ensures the lowest k ′ for a given D, reducing the area due
to fewer buffers and ports as well as smaller crossbars. Low-radix
networks deliver the lowest areas but they also entail a worse power/performance tradeoff as shown in § 5.4. Finally, static/dynamic
power consumption follows similar trends as the area. For example, SN reduces static power over both FBF (≈45-60%) and PFBF(≈14-27%), as a consequence of providing the lowest k for a given D.
0.004 SN outperforms
FBF by 40%
0.003

0.00
0.02

wires
crossbars
routers

0.01
0.00

5.5

f8 f9 f9 n 9 9
fb fb pfb s t2d cm

0.00
0.04
0.03

SN outperforms
FBF by 41%

0.02
0.01
0.00
f8 f9 f9 n 9 9
fb fb pfb s t2d cm

Dynamic power/node [W]Static power/node [W]Area/node [cm^2]

0.000

0.01

0.15

SN outperforms
FBF by 46%

0.10
0.05
0.00
0.20

wires

0.15

crossbars

0.10

routers

0.05
0.00

1296−45nm

0.002

0.02

routers+
crossbars

0.20

1296−22nm

0.004

a-routers
RRg-wires
RNg-wires

SN outperforms
FBF by 44%

1296 45nm

0.006

1296 45nm

0.000
0.008 i-routers

0.03

f8 f9 f9 n 9 9
fb fb pfb s t2d cm(a) Area.
(b) Static power.
(c) Dynamic power.
Figure 17. (§ 5.3) Area/power analysis with SMART links, N = 1296.

5.6
5.4

0.3

Network:

fbf3

pfbf3

cm3

sn_subgr0.0
fft an. n−c ios. dix mcl. vips end r−s
id
ra ea
a rad
lr
te
flu ocevo wa
str

Further Analysis: A Summary

We summarize our analysis of the influence of other parameters.
Hierarchical NoCs. Although we focus on direct symmetric
topologies, we also compare SN to a folded Clos [59] that represents
hierarchical indirect networks such as fat trees or Kilo-core [1]. SN
retains its lower area benefits. For example, its area is ≈24% and≈26% smaller for N = 200 and N = 1296, respectively.
Other Network Sizes. In addition to N ∈ {200, 192, 1296}, weanalyzed other systems where N ∈ {588, 686, 1024}. SN’s advantages
are consistent.
Global vs. Intermediate Wires. Both types of wires result inthe same advantages of SN over other networks.
Injection Rate. Consumed dynamic power is proportional toinjection rates; SN retains its advantages for low and high rates.
45nm vs. 22nm. Both technologies entail similar trends; the only
difference is that wires use relatively more area and power in 22nm
than in 45nm (see Figures 16–17).
Concentration. SN outperforms other designs for various p(p ∈ {3, 4} for N ∈ {192, 200} and p ∈ {8, 9} for N ∈ {1024, 1296}).



f3 f4 f3 n 4 4
fb fb pfb s t2d cm

1296 22nm

0.0021296 22nm

0.004

0.04

0.6

Figure 18. (§ 5.4) Energy-Delay Product analysis (with SMART).

(a) Area.
(b) Static power.
(c) Dynamic power.
Figure 16. (§ 5.3) Area/power analysis with SMART links, N ∈ {192, 200}.
0.008 SN outperforms
FBF by 33%
0.006

SF is 55%, 29%, and 19% better than FBF, PFBF, and CM (geometric mean used)

0.9

s
y
p
al
et
rne ne esk dedu ferrba can chol



0.01

155% 235% 38% 54% 52%
182% 273% 43% 53% 8%

Analysis of the Performance–Power Tradeoff

Analysis of Today’s Small-Scale Designs

SN specifically targets massively parallel chips. Yet, we also briefly
discuss its advantages in today’s small-scale designs (N = 54), usedin, e.g., Intel’s Knights Landing (KNL) [64]. See Figure 19 for representative results (45nm, SMART). The power/performance tradeoff
is similar to that of higher N . SN has lower latency than T2D (byWe demonstrate that SN provides the best tradeoff between performance and power out of all the topologies.
Throughput/Power. Table 4 shows SN’s relative improvements
over other topologies in the throughput delived per unit of consumed
10

Slim NoC: A Low-Diameter On-Chip Network Topology

ASPLOS ’18, March 24–28, 2018, Williamsburg, US

25

Network
fbf
pfbf
sn
sf_subgr
t2d

Area/node [cm^2]

Latency [cycles]

30

20

0.003

Area due to:0.002

i−routers
a−routers
RRg−wires
RNg−wires

0.001

0.000

15
0.008 0.024 0.060 0.160 0.40

Dynamic power/node [W]≈15%) and PFBF (by ≈5%). It uses less power (by ≈40%) and area(by ≈22%) than FBF and has advantages over PFBF/T2D by ≈1-5%
in both metrics.
Power due to:
0.03

wires
crossbars
buffers

0.02

0.01

0.00

sn fbf pfbf t2d

sn fbf pfbf t2d

Network

Network

Load [flits/node/cycle]

for low-radix and area as well as power consumption for high-radix
topologies). SN outperforms the other networks in combined power/performance metrics, i.e., throughput/power and EDP.
The reasons for SN’s advantages are as stated in § 1. First, it minimizes k ′ (thus reducing buffer space) for fixed D = 2 (ensuring low
latency) and N (enabling high scalability). Next, it uses non-prime
finite fields (enabling more configurations). Third, it offers optimized
layouts (reducing wire lengths and buffer areas). Finally, it incorporates mechanisms such as SMART or CBR (further reducing buffer
areas). We conclude that a combination of all these benefits, enabled
by Slim NoC, leads to a highly-efficient and scalable substrate as ourevaluations demonstrate.
Adaptive Routing. We conduct a preliminary analysis of adaptive routing. For this analysis, we use the Booksim simulator [35]that provides full support for adaptive routing. Both SN and FBF
use simple input-queued routers and do not use any additional
mechanisms such as Central Buffers, SMART, or Elastic Links. The
simulations use 200 nodes. We analyze SN’s performance with the
UGAL protocol [62]. We consider two UGAL variants, local (UGALL) and global (UGAL-G). In the former, routers can only access thesizes of their local queues. In the latter, routers have access to thesizes of all the queues in the network. We compare SN to FBF thatuses two different adaptive schemes [38]: UGAL (a global variant)and an XY adaptive protocol (denoted as XY-ADAPT) that adaptively
selects one of available shortest paths [38]. For an additional comparison, we also plot the minimum static routing latency (MIN). Twotraffic patterns are used: uniform random and asymmetric, where,
for source endpoint s, destination d is (with identical probabilitiesof 12 ) equal to either d = (s mod N2 ) + N2 or d = (s mod N2 ). The
results are shown in Figure 20. For the uniform random traffic, SN’s
UGAL-G and MIN outperform their corresponding schemes in FBF
for each injection rate. UGAL-L in SN provides lower (by ≈12%)
latency for the injection rate of 1%. It is slightly outperformed by
FBF’s adaptive schemes for higher loads (by ≈1-2%). When the load
is very high (≈60%), the protocols in both topologies become comparable. SN offers negligibly higher throughput. For the asymmetrictraffic, the performance trends are similar, with the difference that
SN’s UGAL schemes have comparable or higher (by ≈10%) latency
than those of FBF but they provide higher (by >100%) throughput.
We conclude that, with the UGAL adaptive routing, SN trades
latency for higher throughput over FBF with the asymmetric traffic.
Under the random traffic, its latency is better than that of FBF undervery low (≈1%) injection rates and becomes higher for higher injection rates. Finally, in our evaluation, SN uses a general unoptimized
UGAL scheme while FBF incorporates a tuned XY-adaptive scheme.
This suggests that developing optimized adaptive routing protocols
for SN is a productive area of future research.

(a) Latency(b) Area(c) Dynamic power
Figure 19. (§ 5.6) Analysis of small-scale designs (for N = 54).

Conclusion. Slim NoC retains advantages in small-scale systems
where N is small. Slim NoC’s advantages become larger as N grows(cf. § 5). Thus, Slim NoC is likely to become an even more competitive
NoC in the foreseeable future.

6

SUMMARY OF RESULTS & DISCUSSION

We now summarize SN’s advantages for N ∈ {192, 200} at 45nm. We
use the uniform random traffic for illustrating latency and throughput, and PARSEC/SPLASH benchmarks for analyzing EDP.
SN vs. Low-Radix Networks. SN uses more area (>27%) andstatic/dynamic power (>40/60%) than T2D and CM, but significantly
lowers latency (>30%) and increases throughput (3x). Thus, SN improves throughput/power ratio and ED product of low-radix designsby >95% and ≈19%.
SN vs. High-Radix Networks. Compared to FBF, SN has lower
bisection bandwidth (≈60%) and has similar latency, but it significantly reduces area (>36%), static power (>49%), and dynamic power(>39%). Thus, it improves the throughput/power ratio (≈5%) andespecially EDP (≈55%).
SN vs. Same-Radix Networks. SN delivers a better power/performance tradeoff than PFBF that has comparable bisection bandwidth and radix. SN reduces latency (≈13%), area (>9%), static power(>25%), and dynamic power (>9%), thereby improving throughput/power (≈15%) and EDP (≈15%).
Impact of SMART, CBR. Relative differences between SN andother networks are not vastly affected by SMART/CBR. For example, without SMART, SN uses ≈42% less static power than FBF (seeFigure 15c), similarly to the difference in static power with SMART(see Figure 16b). We observe (in Table 5) that the average (geometric mean) gain from SMART in the average packet latency of eachtopology is ≈7.6% (FBF), ≈0% (CM), ≈8% (PFBF), and ≈11.3% (SN).
We conclude that SN is very synergistic with SMART and CBRs.
bar. can. cho. de. fer. fft fl.
fbf3 7.7 8.1 6.6
pfbf3 9.2 8.7 6.8
cm3 0 0 0sn13.2 11.7 9.8

oc. radio. radi. str. vip. vol. wat.

7.3 7.3 8.5 7.3 8.5 9.1
7.5 7.6 9.2 7.3 7.8 9.8
0 0 0 0 0 010.5 10.6 12.6 10.4 10.9 13.6

8.2 7.2 8 7.4 6.9
8.6 7.4 8.3 7.6 7.3
0
0 0 0 011.8 10.6 11.6 10.7 10.3

7

RELATED WORK

To our knowledge, this is the first work to design a highly scalable
and energy-efficient on-chip network topology by solving the problems of adapting state-of-the-art off-chip topologies to the on-chip
context, using key notions from graph theory and number theory.
We discuss how Slim NoC (SN) differs from major related works.
SN vs Slim Fly. SN is inspired by the rack-level Slim Fly [11] (SF)in that it approaches the optimal tradeoff between radix, network
size, and diameter by incorporating the underlying MMS graphs [11,45]. In contrast to SF, SN: (1) uses non-prime finite fields for more
viable NoC configurations, (2) provides cost models and layouts

Table 5. (§ 6) Percentage decrease in the average packet latency due to
SMART, N = 192, PARSEC/SPLASH, SN uses sn_subgr.

High-Level Key Observations. Slim NoC achieves a sweetspot
in the combined power/performance metrics. It is comparable toor differs negligibly from each compared topology in some metrics(area and power consumption for low-radix and performance (average packet latency, throughput) for high-radix comparison points).
It outperforms every other topology in other metrics (performance11

Network_Routing:
FBF_MIN
FBF_UGAL−L
FBF_XY−ADAPT
SN_MIN
SN_UGAL−G
SN_UGAL−L

98

Final datapoints
indicate when
the network
becomessaturated

Avg. packet latency [cycles]

Avg. packet latency [cycles]

ASPLOS ’18, March 24–28, 2018, Williamsburg, US

7

6

0.0

0.2

0.4

0.6

Load [fraction of maximum]

0.8

7

M. Besta, S. M. Hassan, S. Yalamanchili, R. Ausavarungnirun, O. Mutlu, T. Hoefler
the NoC setting. In particular, we introduce mathematically rigorous
router placement schemes, use non-prime finite fields to generate
underlying graphs, thereby producing feasible on-chip layouts, andshift the optimization goal to minimizing radix for a fixed core count.
Finally, we augment SN with state-of-the-art mechanisms such as
Central Buffer routers, ElastiStore, and SMART links.
We show that Slim NoC can be an effective and feasible on-chip
network design for both small-scale and large-scale future chips
with tens, hundreds, and thousands of cores. Our evaluations showthat Slim NoC significantly improves both performance and energy
efficiency for regular and irregular workloads over cutting-edge
network topologies. We believe and hope that our approach basedon combining mathematical optimization with state-of-the-art engineering will result in other highly-scalable and energy-efficient
on-chip network designs.

Network_Routing:
FBF_MIN
FBF_UGAL−L
FBF_XY−ADAPT
SN_MIN
SN_UGAL−G
SN_UGAL−L

6

5

Final datapoints
indicate when
the network
becomessaturated

4
0.0

0.2

0.4

0.6

0.8

Load [fraction of maximum](a) Uniform Random(b) AsymmetricFigure 20. Preliminary analysis of adaptive routing performance (forN = 200). Each considered position in a legend has the form “A_B”, where“A” is the network acronym while “B” is the routing scheme acronym. The
final data points in each considered combination of network and routing
scheme indicate the last evaluated scenario before network saturation.

suitable for NoC settings, (3) takes advantage of various modern
architectural optimizations such as Central Buffers [31], and (4)resolves deadlock-freedom in NoC settings. Consequently, SN exploits SF’s topological advantages and enables its adaptation to the
on-chip constraints for an effective on-chip network design.
SN vs Other NoCs. Other topologies that reduce area and power
consumption or maximize performance were proposed, both lowradix (rings [7, 8], tori [6], meshes [9]) and high-radix (Flattened
Butterflies [38], fully-connected crossbars). Yet, the former havehigh latency while the latter are power-hungry. The rack-level HyperX [4] network extends hypercubes and Flattened Butterfly; itminimizes cost for fixed bisection bandwidth and radix while SN
fixes the diameter to two, lowering latency. Indirect networks (Kilocore [1] with swizzle switches [61], CNoC [36], and hierarchical
NoCs [7, 8, 20]) differ from SN, which can be manufactured easier as
a direct and symmetric network with identical routers. Various fundamentally low-radix designs (EVCs [41], MECS [29], Kilo-NoC [30],Dodec [75], schemes for 3D networks [74], and others [34]) limit
throughput at high injection rates; SN ensures a close-to-optimal
radix and diameter tradeoff, ensuring low cost and high performancefor both low and high loads. Finally, an on-chip Dragonfly topology was only considered in the nanophotonics [52] and in-memory
processing [3] contexts.
Optimized NoC Buffers. Buffer space can be reduced in many
ways (sharing among VCs [43, 67] or ports [2, 57, 68], reducing VC
count [17, 56, 71], using bubble flow control [16, 32], using scalable
networks within switches [5], or removing buffers altogether [12, 18,
25–27, 47, 49, 50, 72, 73]). These schemes are largely orthogonal to
SN but they may decrease performance at high loads [14, 25, 47, 49,
50, 73]. Our Elastic Buffer-based Central Buffer routers eliminate thenon-determinism and extra link traversals due to deflection-based
bufferless routing.
Single-Cycle Wires. ViChaR [48], iDEAL [40], or other schemes
for long single-cycle wires [15, 44] or deadlock-free multi-VC elastic
links [46, 60] can also enhance SN.

8

Acknowledgments
We thank our shepherd, Abhishek Bhattacharjee, for his valuablecomments. We acknowledge insightful feedback from all the reviewers. We thank Hussein Harake, Colin McMurtrie, and the whole
CSCS team granting access to the Greina, Piz Dora, and Daint machines, and for their excellent technical support. We acknowledge
extensive support about the MIT-DSENT tool from Chen Sun. This
work was supported by a Google European Doctoral Fellowship.

References[1] N. Abeyratne, R. Das, Q. Li, K. Sewell, B. Giridhar, R. G. Dreslinski, D. Blaauw, andT. Mudge. Scaling Towards Kilo-Core Processors with Asymmetric High-Radix
Topologies. HPCA, 2013.
[2] T. Agerwala, J. Martin, J. Mirza, D. Sadler, D. Dias, and M. Snir. SP2 System
Architecture. IBM Systems Journal, 1995.
[3] J. Ahn, S. Hong, S. Yoo, O. Mutlu, and K. Choi. A Scalable Processing-in-Memory
Accelerator for Parallel Graph Processing. ISCA, 2015.
[4] J. H. Ahn, N. Binkert, A. Davis, M. McLaren, and R. S. Schreiber. HyperX: Topology,
Routing, and Packaging of Efficient Large-Scale Networks. SC, 2009.
[5] J. H. Ahn, Y. H. Son, and J. Kim. Scalable High-Radix Router Microarchitecture
Using a Network Switch Organization. ACM TACO, 2008.
[6] R. Alverson, D. Roweth, and L. Kaplan. The Gemini System Interconnect. HOTI,
2010.
[7] R. Ausavarungnirun, C. Fallin, X. Yu, K. Chang, G. Nazario, R. Das, G. H. Loh, andO. Mutlu. Design and Evaluation of Hierarchical Rings with Deflection Routing.
SBAC-PAD, 2014.
[8] R. Ausavarungnirun, C. Fallin, X. Yu, K. Chang, G. Nazario, R. Das, G. H. Loh, andO. Mutlu. A Case for Hierarchical Rings with Deflection Routing. PARCO, 2016.
[9] J. Balfour and W. J. Dally. Design Tradeoffs for Tiled CMP On-Chip Networks.
ICS, 2006.
[10] M. Besta, S. M. Hassan, S. Yalamanchili, R. Ausavarungnirun, O. Mutlu, and T. Hoefler. Slim NoC: A Low-Diameter On-Chip Network Topology for High EnergyEfficiency and Scalability. Technical report, 2017.
[11] M. Besta and T. Hoefler. Slim Fly: A Cost Effective Low-Diameter Network
Topology. SC, 2014.
[12] Y. Cai, K. Mai, and O. Mutlu. Comparative Evaluation of FPGA and ASIC Implementations of Bufferless and Buffered Routing Algorithms for On-Chip Networks.
ISQED, 2015.
[13] A. Ceyhan, M. Jung, S. Panth, S. K. Lim, and A. Naeemi. Impact of Size Effects in
Local Interconnects for Future Technology Nodes: A Study Based on Full-Chip
Layouts. IITC/AMC, 2014.
[14] K. K.-W. Chang, R. Ausavarungnirun, C. Fallin, and O. Mutlu. HAT: Heterogeneous
Adaptive Throttling for On-Chip Networks. SBAC-PAD, 2012.
[15] C.-H. O. Chen, S. Park, T. Krishna, S. Subramanian, A. P. Chandrakasan, and L.-S.
Peh. SMART: A Single-Cycle Reconfigurable NoC for SoC Applications. DATE,
2013.
[16] L. Chen and T. M. Pinkston. Worm-bubble flow control. HPCA, 2013.
[17] L. Chen, R. Wang, and T. Pinkston. Critical Bubble Scheme: An Efficient Implementation of Globally Aware Network Flow Control. IPDPS, 2011.
[18] C. Craik and O. Mutlu. Investigating the Viability of Bufferless NoCs in Modern
Chip Multi-Processor Systems. CMU Safari Technical Report, 2011.
[19] W. Dally and B. Towles. Principles and Practices of Interconnection Networks.
Morgan Kaufmann Publishers Inc., 2003.

CONCLUSION

We introduce Slim NoC (SN), a new family of low-diameter on-chip
networks (NoCs) that minimize area and power consumption whileproviding high performance at both low and high loads. Slim NoC
extends the state-of-the-art rack-level Slim Fly topology to the onchip setting. We identify and preserve Slim Fly’s attractive propertiesand develop mechanisms to overcome its significant overheads in
12Slim NoC: A Low-Diameter On-Chip Network Topology

ASPLOS ’18, March 24–28, 2018, Williamsburg, US[20] R. Das, S. Eachempati, A. Mishra, V. Narayanan, and C. Das. Design and Evaluationof a Hierarchical On-Chip Interconnect for Next-Generation CMPs. HPCA, 2009.
[21] R. Das, O. Mutlu, T. Moscibroda, and C. Das. Application-Aware Prioritization
Mechanisms for On-Chip Networks. MICRO, 2009.
[22] R. Das, O. Mutlu, T. Moscibroda, and C. R. Das. Aérgia: Exploiting Packet Latency
Slack in On-Chip Networks. In ISCA, 2010.
[23] J. J. Dongarra, C. B. Moler, J. R. Bunch, and G. W. Stewart. LINPACK Users’ Guide.
SIAM, 1979.
[24] EZchip Semiconductor Ltd. EZchip Introduces TILE-Mx100 World’s Highest CoreCount ARM Processor Optimized for High-Performance Networking Applications.
http://www.tilera.com/News/PressRelease/?ezchip=97, 2015.
[25] C. Fallin, C. Craik, and O. Mutlu. CHIPPER: A Low-Complexity Bufferless Deflection Router. HPCA, 2011.
[26] C. Fallin, G. Nazario, X. Yu, K. Chang, R. Ausavarungnirun, and O. Mutlu. MinBD:
Minimally-Buffered Deflection Routing for Energy-Efficient Interconnect. NOCS,
2012.
[27] C. Fallin, G. Nazario, X. Yu, K. Chang, R. Ausavarungnirun, and O. Mutlu. Bufferless
and Minimally-Buffered Deflection Routing. Routing Algorithms in Networks-onChip, 2014.
[28] H. Fu, J. Liao, J. Yang, L. Wang, Z. Song, X. Huang, C. Yang, W. Xue, F. Liu, F. Qiao,
et al. The Sunway TaihuLight Supercomputer: System and Applications. Science
China Information Sciences, 2016.
[29] B. Grot, J. Hestness, S. Keckler, and O. Mutlu. Express Cube Topologies for On-Chip
Interconnects. HPCA, 2009.
[30] B. Grot, J. Hestness, S. Keckler, and O. Mutlu. Kilo-NoC: A Heterogeneous Networkon-Chip Architecture for Scalability and Service Guarantees. ISCA, 2011.
[31] S. Hassan and S. Yalamanchili. Centralized Buffer Router: A Low Latency, Low
Power Router for High Radix NoCs. NOCS, 2013.
[32] S. Hassan and S. Yalamanchili. Bubble Sharing: Area and Energy Efficient Adaptive
Routers using Centralized Buffers. NOCS, 2014.
[33] IBM ILOG. User’s Manual for CPLEX, v12.1. International Business Machines
Corporation, 2009.
[34] A. Jain, R. Parikh, and V. Bertacco. High-Radix On-Chip Networks with Low-Radix
Routers. ICCAD, 2014.
[35] N. Jiang, G. Michelogiannakis, D. Becker, B. Towles, and W. J. Dally. Booksim 2.0
User’s Guide. Standford University, 2010.
[36] Y.-H. Kao, M. Yang, N. S. Artan, and H. J. Chao. CNoC: High-Radix Clos Networkon-Chip. TCAD, 2011.
[37] J. Kim. Low-Cost Router Microarchitecture for On-Chip Networks. MICRO, 2009.
[38] J. Kim, W. J. Dally, and D. Abts. Flattened Butterfly: A Cost-Efficient Topology for
High-Radix Networks. ISCA, 2007.
[39] J. Kim, W. J. Dally, S. Scott, and D. Abts. Technology-Driven, Highly-Scalable
Dragonfly Topology. ISCA, 2008.
[40] A. K. Kodi, A. Sarathy, and A. Louri. iDEAL: Inter-Router Dual-Function Energy
and Area-Efficient Links for Network-on-Chip (NoC) Architectures. ISCA, 2008.
[41] A. Kumar, L.-S. Peh, P. Kundu, and N. Jha. Toward Ideal On-Chip Communication
Using Express Virtual Channels. IEEE Micro, 2008.
[42] C. E. Leiserson. Fat-Trees: Universal Networks for Hardware-Efficient Supercomputing. IEEE TC, 1985.
[43] J. Liu and J. G. Delgado-Frias. A DAMQ Shared Buffer Scheme for Network-onChip. CSS, 2007.
[44] R. Manevich, L. Polishuk, I. Cidon, and A. Kolodny. Designing Single-Cycle Long
Links in Hierarchical NoCs. Microprocessors and Microsystems, 2014.
[45] B. D. McKay, M. Miller, and J. Širán. A Note on Large Graphs of Diameter Two
and Given Maximum Degree. Journal of Combinatorial Theory, Series B, 1998.
[46] G. Michelogiannakis, J. Balfour, and W. Dally. Elastic-Buffer Flow Control for
On-Chip Networks. HPCA, 2009.
[47] T. Moscibroda and O. Mutlu. A Case for Bufferless Routing in On-Chip Networks.
ISCA, 2009.
[48] C. Nicopoulos, D. Park, J. Kim, N. Vijaykrishnan, M. S. Yousif, and C. R. Das.
ViChaR: A Dynamic Virtual Channel Regulator for Network-on-Chip Routers.
MICRO, 2006.

[49] G. Nychis, C. Fallin, T. Moscibroda, and O. Mutlu. Next Generation On-Chip
Networks: What Kind of Congestion Control Do We Need? In HotNets, 2010.
[50] G. P. Nychis, C. Fallin, T. Moscibroda, O. Mutlu, and S. Seshan. On-Chip Networks from a Networking Perspective: Congestion and Scalability in Many-CoreInterconnects. SIGCOMM, 2012.
[51] A. Olofsson. Epiphany-V: A 1024 Processor 64-bit RISC System-on-Chip. arXiv
preprint arXiv:1610.01832, 2016.
[52] Y. Pan, P. Kumar, J. Kim, G. Memik, Y. Zhang, and A. Choudhary. Firefly: Illuminating Future Network-on-Chip with Nanophotonics. ISCA, 2009.
[53] L.-S. Peh and W. J. Dally. A Delay Model and Speculative Architecture for Pipelined
Routers. HPCA, 2001.
[54] Pezy Computing. PEZY-SC2. http://pezy.jp.
[55] N. Pippenger and G. Lin. Fault-Tolerant Circuit-Switching Networks. SPAA, 1992.
[56] V. Puente, R. Beivide, J. Gregorio, J. Prellezo, J. Duato, and C. Izu. Adaptive Bubble
Router: A Design to Improve Performance in Torus Networks. ICPP, 1999.
[57] R. Ramanujam, V. Soteriou, B. Lin, and L.-S. Peh. Design of a High-Throughput
Distributed Shared-Buffer NoC Router. NOCS, 2010.
[58] P. Rosenfeld, E. Cooper-Balis, and B. Jacob. DRAMSim2: A Cycle Accurate Memory
System Simulator. IEEE CAL, 2011.
[59] S. Scott, D. Abts, J. Kim, and W. J. Dally. The BlackWidow High-Radix Clos
Network. ISCA, 2006.
[60] I. Seitanidis, A. Psarras, G. Dimitrakopoulos, and C. Nicopoulos. ElastiStore: An
Elastic Buffer Architecture for Network-on-Chip Routers. DATE, 2014.
[61] K. Sewell, R. G. Dreslinski, T. Manville, S. Satpathy, N. Pinckney, G. Blake, M. Cieslak, R. Das, T. F. Wenisch, D. Sylvester, D. Blaauw, and T. Mudge. Swizzle-Switch
Networks for Many-Core Systems. Emerging and Selected Topics in Circuits andSystems, 2012.
[62] A. Singh. Load-Balanced Routing in Interconnection Networks. PhD thesis, Stanford
University, 2005.
[63] S. Skiena. Dijkstra’s algorithm. Implementing Discrete Mathematics: Combinatorics
and Graph Theory with Mathematica. Addison-Wesley, 1990.
[64] A. Sodani. Knights Landing (KNL): 2nd Generation Intel® Xeon Phi Processor.
HCS, 2015.
[65] G. Strang. Introduction to Linear Algebra. Wellesley-Cambridge Press Wellesley,
MA, 1993.
[66] C. Sun, C. O. Chen, G. Kurian, L. Wei, J. E. Miller, A. Agarwal, L. Peh, and V. Stojanovic. DSENT - A Tool Connecting Emerging Photonics with Electronics for
Opto-Electronic Networks-on-Chip Modeling. NOCS, 2012.
[67] Y. Tamir and G. Frazier. Dynamically-Allocated Multi-Queue Buffers for VLSI
Communication Switches. IEEE TC, 1992.
[68] A. T. Tran and B. M. Baas. RoShaQ: High-Performance On-Chip Router with
Shared Queues. ICCD, 2011.
[69] A. N. Udipi, N. Muralimanohar, and R. Balasubramonian. Towards Scalable,
Energy-Efficient, Bus-Based On-Chip Networks. HPCA, 2010.
[70] J. Wang, J. Beu, R. Bheda, T. Conte, Z. Dong, C. Kersey, M. Rasquinha, G. Riley,
W. Song, H. Xiao, P. Xu, and S. Yalamanchili. Manifold: A Parallel Simulation
Framework for Multicore Systems. ISPASS, 2014.
[71] R. Wang, L. Chen, and T. M. Pinkston. Bubble Coloring: Avoiding Routing- andProtocol-Induced Deadlocks with Minimal Virtual Channel Requirement. ICS,
2013.
[72] X. Xiang, S. Ghose, O. Mutlu, and N.-F. Tzeng. A Model for Application Slowdown
Estimation in On-Chip Networks and Its Use for Improving System Fairness andPerformance. ICCD, 2016.
[73] X. Xiang, W. Shi, S. Ghose, L. Peng, O. Mutlu, and N.-F. Tzeng. Carpool: A Bufferless
On-Chip Network Supporting Adaptive Multicast and Hotspot Alleviation. ICS,
2017.
[74] Y. Xu, Y. Du, B. Zhao, X. Zhou, Y. Zhang, and J. Yang. A Low-Radix and LowDiameter 3D Interconnection Network Design. HPCA, 2009.
[75] H. Yang, J. Tripathi, N. E. Jerger, and D. Gibson. Dodec: Random-Link, Low-Radix
On-Chip Networks. MICRO, 2014.
[76] X. Yuan. On Nonblocking Folded-Clos Networks in Computer Communication
Environments. IPDPS, 2011.

13