MinBD:
Minimally-Buffered Deflection Routing
for Energy-Efficient Interconnect
Chris Fallin, Greg Nazario, Xiangyao Yu*,
Kevin Chang, Rachata Ausavarungnirun, Onur Mutlu
Carnegie Mellon University*CMU and Tsinghua University

MotivationIn many-core chips, on-chip interconnect (NoC)
consumes significant powerIntel Terascale: ~28% of chip powerIntel SCC:
~10%MIT RAW:
~36%



Core

L1

L2 Slice

RouterRecent work1 uses bufferless deflection routing to
reduce power and die area

1Moscibroda and Mutlu, “A Case for Bufferless Deflection Routing in On-Chip Networks.” ISCA 2009.

2

Bufferless Deflection RoutingKey idea: Packets are never buffered in the network. When two
packets contend for the same link, one is deflected.

Removing buffers yields significant benefitsBut, at high network utilization (load), bufferless deflection
routing causes unnecessary link & router traversals
Reduces power (CHIPPER: reduces NoC power by 55%)
Reduces die area (CHIPPER: reduces NoC area by 36%)

Reduces network throughput and application performance
Increases dynamic power

Goal: Improve high-load performance of low-cost deflection
networks by reducing the deflection rate.
3Outline: This Talk


Motivation

Background: Bufferless Deflection Routing

MinBD: Reducing Deflections
Addressing Link Contention
 Addressing the Ejection Bottleneck Improving Deflection Arbitration

Results
 Conclusions4

Outline: This Talk


Motivation

Background: Bufferless Deflection Routing

MinBD: Reducing Deflections
Addressing Link Contention
 Addressing the Ejection Bottleneck Improving Deflection Arbitration

Results
 Conclusions5

Bufferless Deflection RoutingKey idea: Packets are never buffered in the network. Whentwo packets contend for the same link, one is deflected.1

Destination
1Baran, “On Distributed Communication Networks.” RAND Tech. Report., 1962 / IEEE Trans.Comm., 1964.

6

Bufferless Deflection Routing

Input buffers are eliminated: flits are buffered inpipeline latches and on network links
Input Buffers
North

North

South

South

East

East

West

West

Local

Local

7

Bufferless Deflection Routing

Input buffers are eliminated: flits are buffered inpipeline latches and on network links
Input Buffers
North

North

South

South

East

East

West

West

Local

Local
Deflection Routing Logic
8

Deflection Router Microarchitecture

Inject/Eject

InjectEject
Reassembly
Buffers

Fallin et al., “CHIPPER: A Low-complexity Bufferless Deflection Router”, HPCA 2011.

9Deflection Router Microarchitecture

Inject/Eject

InjectEject
Reassembly
Buffers

Stage 1: Ejection and injection of local traffic
Fallin et al., “CHIPPER: A Low-complexity Bufferless Deflection Router”, HPCA 2011.

10

Deflection Router Microarchitecture

Inject/Eject

InjectEject
Reassembly
Buffers

Stage 2: Deflection arbitration
Fallin et al., “CHIPPER: A Low-complexity Bufferless Deflection Router”, HPCA 2011.

11

Issues in Bufferless Deflection Routing

Correctness: Deliver all packets without livelock
CHIPPER1: Golden Packet
 Globally prioritize one packet until delivered

Correctness: Reassemble packets without deadlock


CHIPPER1: Retransmit-Once

Performance: Avoid performance degradation at high load


MinBD
12

1 Fallin et al., “CHIPPER: A Low-complexity Bufferless Deflection Router”, HPCA 2011.

Key Performance Issues
1. Link contention: no buffers to hold traffic 
any link contention causes a deflection use side buffers
2. Ejection bottleneck: only one flit can eject per router
per cycle  simultaneous arrival causes deflection
 eject up to 2 flits/cycle
3. Deflection arbitration: practical (fast) deflection
arbiters deflect unnecessarily
 new priority scheme (silver flit)

13

Outline: This Talk


Motivation

Background: Bufferless Deflection Routing

MinBD: Reducing Deflections
Addressing Link Contention
 Addressing the Ejection Bottleneck Improving Deflection Arbitration

Results
 Conclusions14

Outline: This Talk


Motivation

Background: Bufferless Deflection Routing

MinBD: Reducing Deflections
Addressing Link Contention
 Addressing the Ejection Bottleneck Improving Deflection Arbitration

Results
 Conclusions15

Addressing Link Contention
Problem 1: Any link contention causes a deflection

Buffering a flit can avoid deflection on contention
 But, input buffers are expensive:All flits are buffered on every hop  high dynamic energy Large buffers necessary  high static energy and large area

Key Idea 1: add a small buffer to a bufferless deflection
router to buffer only flits that would have been deflected

16

How to Buffer Deflected Flits
Destination
Destination

Eject Inject

Baseline Router

1 Fallin et al., “CHIPPER: A Low-complexity Bufferless Deflection Router”, HPCA 2011.

17

How to Buffer Deflected Flits
Destination
Destination

DEFLECTED
Eject Inject

Baseline Router

1 Fallin et al., “CHIPPER: A Low-complexity Bufferless Deflection Router”, HPCA 2011.

18

How to Buffer Deflected FlitsSide Buffer

Destination
Destination

Eject

InjectSide-Buffered Router
19How to Buffer Deflected FlitsSide Buffer

Destination
Destination

DEFLECTED
Eject

InjectSide-Buffered Router
20How to Buffer Deflected FlitsSide Buffer

Destination

Step 1. Remove up to
one deflected flit per
cycle from the outputs.

Eject

Inject

DEFLECTED

Side-Buffered Router21How to Buffer Deflected FlitsSide Buffer

Step 2. Buffer this flit in asmall FIFO “side buffer.”
Destination

Eject

InjectSide-Buffered Router
22How to Buffer Deflected FlitsSide Buffer

Destination
Step 3. Re-inject this flit into
pipeline when a slot is available.

Eject

InjectSide-Buffered Router23How to Buffer Deflected FlitsSide Buffer

Destination

Eject

InjectSide-Buffered Router24How to Buffer Deflected FlitsSide Buffer

Destination

Eject

InjectSide-Buffered Router
25

Why Could A Side Buffer Work Well?


Buffer some flits and deflect other flits at per-flit level


Relative to bufferless routers, deflection rate reduces(need not deflect all contending flits)
 4-flit buffer reduces deflection rate by 39%

Relative to buffered routers, buffer is more efficiently
used (need not buffer all flits)
 similar performance with 25% of buffer space26

Outline: This Talk


Motivation

Background: Bufferless Deflection Routing

MinBD: Reducing Deflections
Addressing Link Contention
 Addressing the Ejection Bottleneck Improving Deflection Arbitration

Results
 Conclusions27

Addressing the Ejection BottleneckProblem 2: Flits deflect unnecessarily because only one flit
can eject per router per cycle

In 20% of all ejections, ≥ 2 flits could have ejected all but one flit must deflect and try again
 these deflected flits cause additional contentionEjection width of 2 flits/cycle reduces deflection rate 21%

Key idea 2: Reduce deflections due to a single-flit ejection
port by allowing two flits to eject per cycle28Addressing the Ejection Bottleneck

Eject

InjectSingle-Width Ejection29Addressing the Ejection Bottleneck
DEFLECTED

Eject

InjectSingle-Width Ejection30

Addressing the Ejection Bottleneck

Eject

InjectDual-Width Ejection31Addressing the Ejection Bottleneck

Eject

InjectDual-Width Ejection32

Addressing the Ejection Bottleneck

For fair comparison, baseline routers have
dual-width ejection for perf. (not power/area)
Eject

InjectDual-Width Ejection33

Outline: This Talk


Motivation

Background: Bufferless Deflection Routing

MinBD: Reducing Deflections
Addressing Link Contention
 Addressing the Ejection Bottleneck Improving Deflection Arbitration

Results
 Conclusions34

Improving Deflection Arbitration
Problem 3: Deflections occur unnecessarily because fast
arbiters must use simple priority schemesAge-based priorities (several past works): full priority order
gives fewer deflections, but requires slow arbitersState-of-the-art deflection arbitration (Golden Packet &two-stage permutation network)
Prioritize one packet globally (ensure forward progress)
 Arbitrate other flits randomly (fast critical path)

Random common case leads to uncoordinated arbitration
35

Fast Deflection Routing ImplementationLet’s route in a two-input router first:

Step 1: pick a “winning” flit (Golden Packet, else random) Step 2: steer the winning flit to its desired output
and deflect other flit Highest-priority flit always routes to destination

36

Fast Deflection Routing with Four Inputs
Each block makes decisions independently
 Deflection is a distributed decision

N

N

E

S

S

E

W

W
37

Unnecessary Deflections in Fast ArbitersHow does lack of coordination cause unnecessary deflections?
1. No flit is golden (pseudorandom arbitration)

Destination

all flits haveequal priority
Destination

38

Unnecessary Deflections in Fast ArbitersHow does lack of coordination cause unnecessary deflections?
1. No flit is golden (pseudorandom arbitration)
2. Red flit wins at first stage
3. Green flit loses at first stage (must be deflected now)

Destination

all flits haveequal priority
Destination

39

Unnecessary Deflections in Fast ArbitersHow does lack of coordination cause unnecessary deflections?
1. No flit is golden (pseudorandom arbitration)
2. Red flit wins at first stage
3. Green flit loses at first stage (must be deflected now)
4. Red flit loses at second stage; Red and Green are deflected

Destination

all flits haveequal priority

unnecessary
deflection!

Destination

40

Improving Deflection Arbitration
Key idea 3: Add a priority level and prioritize one flit
to ensure at least one flit is not deflected in each cycle

Higest priority: one Golden Packet in network
Chosen in static round-robin schedule Ensures correctnessNext-highest priority: one silver flit per router per cycle
Chosen pseudo-randomly & local to one router Enhances performance41

Adding A Silver Flit

Randomly picking a silver flit ensures one flit is not deflected
1. No flit is golden but Red flit is silver

Destination

red flit has
higher priority
Destination

42Adding A Silver Flit

Randomly picking a silver flit ensures one flit is not deflected
1. No flit is golden but Red flit is silver
2. Red flit wins at first stage (silver)
3. Green flit is deflected at first stage

Destination

red flit has
higher priority
Destination

43

Adding A Silver Flit

Randomly picking a silver flit ensures one flit is not deflected
1. No flit is golden but Red flit is silver
2. Red flit wins at first stage (silver)
3. Green flit is deflected at first stage
4. Red flit wins at second stage (silver); not deflected

Destination

red flit has
higher priority

At least one flit
is not deflected
Destination

44

Minimally-Buffered Deflection Router

Eject

Inject45

Minimally-Buffered Deflection Router

Problem 1: Link Contention
Solution 1: Side Buffer

Eject

Inject46

Minimally-Buffered Deflection Router

Problem 2: Ejection Bottleneck
Solution 2: Dual-Width Ejection

Eject

Inject47

Minimally-Buffered Deflection Router

Eject

Problem 3: Unnecessary Deflections
InjectSolution 3: Two-level priority scheme48

Minimally-Buffered Deflection Router

Eject

Inject49

Outline: This Talk


Motivation

Background: Bufferless Deflection Routing

MinBD: Reducing Deflections
Addressing Link Contention
 Addressing the Ejection Bottleneck Improving Deflection Arbitration50

Outline: This Talk


Motivation

Background: Bufferless Deflection Routing

MinBD: Reducing Deflections
Addressing Link Contention
 Addressing the Ejection Bottleneck Improving Deflection Arbitration

Results
 Conclusions

51

Methodology: Simulated System
Chip Multiprocessor Simulation
64-core and 16-core models
 Closed-loop core/cache/NoC cycle-level model Directory cache coherence protocol (SGI Origin-based) 64KB L1, perfect L2 (stresses interconnect), XOR-mapping Performance metric: Weighted Speedup(similar conclusions from network-level latency)
 Workloads: multiprogrammed SPEC CPU2006


75 randomly-chosen workloads
Binned into network-load categories by average injection rate52

Methodology: Routers and NetworkInput-buffered virtual-channel router
8 VCs, 8 flits/VC [Buffered(8,8)]: large buffered router 4 VCs, 4 flits/VC [Buffered(4,4)]: typical buffered router 4 VCs, 1 flit/VC [Buffered(4,1)]: smallest deadlock-free router All power-of-2 buffer sizes up to (8, 8) for perf/power sweep

Bufferless deflection router: CHIPPER1
 Bufferless-buffered hybrid router: AFC2


Has input buffers and deflection routing logic
 Performs coarse-grained (multi-cycle) mode switchingCommon parameters2-cycle router latency, 1-cycle link latency
 2D-mesh topology (16-node: 4x4; 64-node: 8x8)
 Dual ejection assumed for baseline routers (for perf. only)

1Fallin et al., “CHIPPER: A Low-complexity Bufferless Deflection Router”, HPCA 2011.
2Jafri et al., “Adaptive Flow Control for Robust Performance and Energy”, MICRO 2010.

53

Methodology: Power, Die Area, Crit. Path

Hardware modeling

Verilog models for CHIPPER, MinBD, buffered control logicSynthesized with commercial 65nm library

ORION 2.0 for datapath: crossbar, muxes, buffers and links

Power
Static and dynamic power from hardware models
 Based on event counts in cycle-accurate simulations
 Broken down into buffer, link, other54

Reduced Deflections & Improved Perf.

Weighted Speedup15

1. All mechanisms individually reduce deflections

14.5
14Baseline
B (Side(Side-Buf)
Buffer)D (Dual-Eject)
S (Silver Flits)
B+D
B+S+D (MinBD)

13.5
13
12.5
12
Deflection 28%
Rate

17%

22% 27%55

Reduced Deflections & Improved Perf.

Weighted Speedup

15
14.5

1. All mechanisms individually reduce deflections
2. Side buffer alone is not sufficient for performance(ejection bottleneck remains)

14
Baseline
B (Side(Side-Buf)
Buffer)D (Dual-Eject)
S (Silver Flits)
B+D
B+S+D (MinBD)

13.5
13
12.5
12
Deflection 28%
Rate

17%

22% 27%56

Weighted Speedup

Reduced Deflections & Improved Perf.
3. Overall, 5.8% over baseline, 2.7% over dual-eject15
by reducing deflections 64% / 54%
14.5
14

2.7%
5.8%

Baseline
B (Side(Side-Buf)
Buffer)D (Dual-Eject)
S (Silver Flits)
B+D
B+S+D (MinBD)

13.5
13
12.5
12
Deflection 28%
Rate

17%

22% 27%

11%

10%

57

Overall Performance Results
Weighted Speedup

16

14
Buffered (8,8)

12Buffered (4,4)
Buffered (4,1)

10

CHIPPERAFC (4,4)
MinBD-4

8

Injection Rate
58

Overall Performance Results
16

Weighted Speedup

2.7%
2.7%

14
8.3%
12

Buffered (8,8)
Buffered (4,4)
Buffered (4,1)

10

CHIPPER
8.1%

8

AFC (4,4)
MinBD-4

Rate (8.1% at high load)• Improves 2.7% overInjection
CHIPPER• Within 2.7% of Buffered (4,4) (8.3% at high load)

59

Overall Performance Results
Weighted Speedup

16

14
Buffered (8,8)

12Buffered (4,4)
Buffered (4,1)

10

CHIPPERAFC (4,4)
MinBD-4

8

Injection Rate

• Similar perf. to Buffered (4,1) @ 25% of buffering space60

Overall Power Results
dynamic otherstatic other2.5

dynamic linkstatic link

dynamic buffer
static buffer

2.0
1.5
1.0
0.5

MinBD
-4

AFC(4,
4)

CHIPPER

Buffered (4,1)

Buffered (4,4)0.0
Buffered (8,8)

Network Power (W)

3.0

61

Overall Power Results
3.0

Network Power (W)non-buffer

buffer

2.5
2.0
1.5
1.0
0.5

MinBD-4

AFC(4,4)

CHIPPER

Buffered(4,1)

Buffered(4,4)

Buffered
(8,8)

0.0

• Buffers are significant fraction of power in baseline routers62• Buffer power is much smaller in MinBD (4-flit buffer)

Overall Power Results
3.0

Network Power (W)dynamic

static

2.5
2.0
1.5
1.0
0.5

MinBD4

AFC(4,
4)

CHIPPER

Buffered (4,1)

Buffered (4,4)

Buffered (8,8)0.0• Dynamic power increases with deflection routing• Dynamic power reduces in MinBD relative to CHIPPER

63

Overall Power Results
dynamic otherstatic other2.5

dynamic linkstatic link

dynamic buffer
static buffer

2.0
1.5
1.0
0.5

MinBD
-4

AFC(4,
4)

CHIPPER

Buffered (4,1)

Buffered (4,4)0.0
Buffered (8,8)

Network Power (W)

3.0

64

Weighted Speedup

Performance-Power Spectrum
15.0
14.8
14.6
14.4
14.2
14.0
13.8
13.6
13.4
13.2
13.0

More Perf/PowerLess Perf/PowerBuf (8,8)

MinBD

Buf (4,4)AFC
Buf (4,1)
CHIPPER
Buf (1,1)

0.5

1.0

1.5

2.0

2.5

3.0

Network Power (W)65

Weighted Speedup

Performance-Power Spectrum
15.0
14.8
14.6
14.4
14.2
14.0
13.8
13.6
13.4
13.2
13.0

More Perf/PowerLess Perf/PowerBuf (8,8)

MinBD

Buf (4,4)AFC
Buf (4,1)
CHIPPER
Buf (1,1)• Most(perf/watt)of
0.5 energy-efficient
1.0
1.5
2.0
2.5anyevaluated networkNetworkrouterPower
design
(W)

3.0

66

Die Area and Critical Path
Normalized Die Area
2.5
2
1.5
1
0.5

MinBD

CHIPPER

Buffered (4,1)

Buffered (4,4)

Buffered (8,8)

067Die Area and Critical Path
Normalized Die Area
2.5
2

-36%

1.5
+3%

1
0.5

MinBD

CHIPPER

Buffered (4,1)

Buffered (4,4)

Buffered (8,8)

0• Only 3% area increase over CHIPPER (4-flit buffer)• Reduces area by 36% from Buffered (4,4)
68Die Area and Critical Path
Normalized Die Area

Normalized Critical Path

2.5

1.2

2

-36%

1.0
0.8

1.5

0.6

+3%

1

MinBD

CHIPPER

Buffered (4,1)

Buffered (4,4)

MinBD

CHIPPER

0.0

Buffered (4,1)

0Buffered (4,4)

0.2

Buffered (8,8)

0.5

Buffered (8,8)

0.4

69

Die Area and Critical Path
Normalized Die Area

Normalized Critical Path

2.5

1.2

2

-36%

+8%

+7%

1.0
0.8

1.5

0.6

+3%

1

MinBD

CHIPPER

Buffered (4,1)

Buffered (4,4)

MinBD

CHIPPER

0.0

Buffered (4,1)

0Buffered (4,4)

0.2

Buffered (8,8)

0.5

Buffered (8,8)

0.4• Increases by 7% over CHIPPER, 8% over Buffered (4,4)
70Conclusions


Bufferless deflection routing offers reduced power & area
But, high deflection rate hurts performance at high load

MinBD (Minimally-Buffered Deflection Router) introduces:













Side buffer to hold only flits that would have been deflected
Dual-width ejection to address ejection bottleneck
Two-level prioritization to avoid unnecessary deflections

MinBD yields reduced power (31%) & reduced area (36%)
relative to buffered routers
MinBD yields improved performance (8.1% at high load)
relative to bufferless routers  closes half of perf. gap
MinBD has the best energy efficiency of all evaluated designs
with competitive performance71

THANK YOU!

72

MinBD: Minimally-Buffered Deflection
Routing for Energy-Efficient Interconnect
Chris Fallin, Greg Nazario, Xiangyao Yu*,
Kevin Chang, Rachata Ausavarungnirun, Onur Mutlu
Carnegie Mellon University*CMU and Tsinghua University

BACKUP SLIDES

74

Correctness: Golden Packet


The Golden Packet is always prioritized long enough to bedelivered (hop latency * (max # hops + serialization
delay))


Golden Packet rotates statically through all packet IDs

E.g. 4x4: 16 senders, 16 transactions/sender  256 choices

Max latency is GP epoch * # packet IDs
“Epoch length”: e.g. 4x4: 3 * (7 + 7) = 42 cycles (pick 64 cyc)E.g., 64*256 = 16K cycles

Flits in Golden Packet are arbitrated by sequence # (totalorder)
75

Correctness: Retransmit-Once
Finite reassembly buffer size may lead to buffer exhaustion What if a flit arrives from a new packet and no buffer isfree?
 Answer 1: Refuse ejection and deflect  deadlock!
 Answer 2: Use large buffers  impractical Retransmit-Once (past work): operate opportunistically &assume available buffers

If no buffer space, drop packet (once) and note its ID
 Later, reserve buffer space and retransmit (once)End-to-end flow control provides correct endpoint operation
without in-network backpressure
76

Correctness: Side Buffer
Golden Packet ensures delivery as long as flits keep moving
 What if flits get “stuck” in a side buffer?
Answer: buffer redirection


If buffered flit cannot re-inject after Cthreshold cycles, then:
1. Force one input flit per cycle into buffer (random choice)
2. Re-inject buffered flit into resulting empty slot in network

If a flit is golden, it will never enter a side buffer If a flit becomes golden while buffered, redirection willrescue it after Cthreshold * BufferSize (e.g.: 2 * 4 = 8 cyc) Extend Golden epoch to account for this

77

Why does Side Buffer Alone Lose Perf.?
Adding a side buffer reduces deflection rate

Raw network throughput increases

But ejection is still the system bottleneckEjection rate remains nearly constantSide buffers are utilized  more traffic in flightHence, latency increases (Little’s Law): ~10%78

Buf(8,8)
Buf(4,4)Buf(4,1)
CHIPPER
AFC(4,4)
MinBD-4
Buf(8,8)
Buf(4,4)Buf(4,1)
CHIPPER
AFC(4,4)
MinBD-4
Buf(8,8)
Buf(4,4)Buf(4,1)
CHIPPER
AFC(4,4)
MinBD-4

2

Buf(8,8)
Buf(4,4)Buf(4,1)
CHIPPER
AFC(4,4)
MinBD-4

2.5

Buf(8,8)
Buf(4,4)Buf(4,1)
CHIPPER
AFC(4,4)
MinBD-4

3

Buf(8,8)
Buf(4,4)Buf(4,1)
CHIPPER
AFC(4,4)
MinBD-4

Network Power (W)Overall Power Results

3.5

dynamic otherdynamic link
dynamic buffer
static otherstatic linkstatic buffer

1.5

1

0.5

0

0.00 – 0.15 0.15 – 0.30
0.30 – 0.40
0.40 – 0.50
> 0.50
AVG
79

MinBD vs. AFC
AFC:
Combines input buffers and deflection routing
 In a given cycle, all link contention is handled by buffers or
by deflection (global router mode) Mode-switch is heavyweight (drain input buffers) and takes
multiple cycles
 Router has area footprint of buffered + bufferless, but could
save power with power-gating (assumed in Jafri et al.)
 Better performance at highest loads (equal to buffered)

MinBD:
Combines deflection routing with a side buffer In a given cycle, some flits are buffered, some are deflected Smaller router and no mode switching But, loses some performance at highest load

80

Related Work

Baran, 1964


Original “hot potato” (deflection) routing

BLESS (Moscibroda and Mutlu, ISCA 2009)
Earlier bufferless deflection router Age-based arbitration  slow (did not consider critical path)

CHIPPER (Fallin et al., HPCA 2011)

AFC (Jafri et al., MICRO 2010)Assumed baseline for this work
Coarse-grained bufferless-buffered hybrid

SCARAB (Hayenga et al., MICRO 2009), BPS (Gomez+08)
Drop-based deflection networks
 SCARAB: dedicated circuit-switched NACK network81