O'Reilly logo

Principles and Practices of Interconnection Networks by Brian Patrick Towles, William James Dally

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

k-ary n-cube (Torus) k-ary n-mesh (Mesh)
bisection boundhop count bound
Two-level packaging (k even)
router serialization wire
k-ary 1-cube
0 1
nk
2 k
k-ary 1-mesh
0 1 2 k
Two-level packaging (k even)
0
3
1
2
Folding to eliminate long channels
from a torus layout.
k-ary
(n-1)-cube
k-ary
(n-1)-cube
k-ary
(n-1)-cube
k
n–1
channels
Recursive construction of higher
dimensional k-ary n-cubes.
uniform
traffic
Topology
H
min
B
C
w
Θ
ideal
NH
min
=
b
γ
max
γ
max
γ
max
γ
max
C
>
2B
C
>
N
T
0
=H
min
t
r
L
b
D
min
υ
+
+
4
k
8
4
n
(
k
4k
1
)
k even
k odd
k even
k odd
=
=
=
k
k
8
1
8k
4k
n–1
4N
=
b
T
s
L
δ=4n
b=wf
<
min
W
n
kW
s
4n
4N
Θ
ideal
=
8b
nk
uniform
traffic
H
min
B
C
w
γ
max
4
k
4
3
n
(
k
3k
1
)
k even
k odd
k even
k odd
=
=
=
=
=
k
k
4
1
4k
2k
n–1
2N
=
T
s
L
δ=4n
b=wf
<
min
W
n
kW
s
4n
2N
Θ
ideal
=
4b
k
b
k
,
,
k-ary n-fly (Butterfly) Clos
2-ary 3-fly
(m = 3, n = 3, r = 4) Clos network
Two-level packaging:
0
1
2
3
4
5
6
7
00
01
02
03
10
11
12
13
20
21
22
23
0
1
2
3
4
5
6
7
m = 3 r × r
middle switches
M1
M2
M3
I1
I2
I3
I4
O1
O2
O3
O4
1.1
1.2
1.3
2.1
2.2
2.3
3.1
3.2
3.3
4.1
4.2
4.3
1.1
1.2
1.3
2.1
2.2
2.3
3.1
3.2
3.3
4.1
4.2
4.3
r = 4 n × m
input switches
r = 4 m × n
output switches
Rearrangeably non-blocking if m n
Non-blocking for fanout f multicast if
Strictly non-blocking if
m 2n –1
Channel Slicing
worst-case (n even)
uniform traffic
1
2
3
0
1
2
3
0
Channel sliced 4-ary 1-fly
Channel slicing a butterfly
with slicing factor x:
γ
max
=1
γ
max,wc
= N
H
min
B
C
=
=
n+1
N
2
1+log
k
x
δ=2k
w
b=wf
<
min
W
n
2W
s
2k
N
,
=
b
T
s
L
Θ
ideal
= b
f
<
m(m – n)
m(n – 1)
n=
T
s
=
T
h
=t
r
xL
b
n
1+log
k
x
n
Units of Resource Allocation
Channel
Cycle
H
B
B
B T
H
B
B
B T
H
B
B
B T
H
B B B T
0
1
2
3
0 1 2 3 4 5 6 7
Channel
Cycle
H
B
B
B T
H
B
B
B T
H
B
B
B T
H
B B B T
0
1
2
3
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
Store-and-forward Flow Control
Cut-through / Wormhole FC
Message
Packet
Header
Head Flit
Tail Flit
Flit
Body Flit
Phit
Head, Body,
Tail, or H&T
SNRI
VC
Node 1 Node 2
flit
flit
flit
flit
flit
flit
flit
flit
flit
flit
credit
credit
credit
flit
flit
t
crt
t
bi
process
process
Node 1 Node 2
t
rt
t
rt
off
process
on
process
On/Off Flow ControlCredit-based Flow Control
TY
F
L
f
t
crt
b
F
L
f
2t
rt
b
T
0
=H
T
0
=Ht
r
b
L
+
t
r
b
L
+
An Input Queued, Virtual Channel Router
G R O P C
G R O P C
Switch
Allocator
VC
Allocator
Input Unit
Input Unit
Output Unit
Switch
G I C
G I C
Route r
Router
Output Unit
Head Flit
Body Flit
Cycle
RC VA SA ST
SA ST
1 2 3 4 5
Saturation throughput (
λ
S
)
Routing bound
Offered Traffic (bits/sec)
Latency Versus Offered Traffic
Latency (sec)
Zero-load latency (T
0
)
Topology bound
Topology bound
Routing bound
Θ
ideal
<
2bB
C
H
avg
t
r
+
Ν
Θ
R
<
bC
NH
avg
Θ
ideal
<
bC
ΝΗ
min
b
L
H
min
t
r
+
b
L

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required