A Cache-conscious Profitability
Model for Empirical Tuning ofLoop Fusion
Apan Qasem
Ken Kennedy
Rice University
Houston, TX

Outline– Motivation– Related Work
– Profitability Model• Using hierarchical classification of reuse• Accounting for conflict misses• Enforcing resource constraints• Tuning fusion parameters– Preliminary Experiments– Conclusions and Future WorkLCPC 2005

Rice University2

Motivation– Making the right fusion choices is a nontrivial task
• Optimal fusion known to be NP-complete• Profitability depends on the underlyingarchitecture– Conflict misses– Resource Constraints• Exploiting inter-loop nest locality is not enough

LCPC 2005

Rice University3

outer loop reuse in a()

L1: do j = 1, N
do i = 1, Mb(i,j) = a(i,j)+a(i,j-1)+a(i,j-2)
enddo
enddo
loop-crossing reuse in b()

L2: do j = 1, N
do i = 1, M
c(i,j) = b(i,j) + d(i,j)
enddo
enddo

lost reuse in a()

L12: do j = 1,N
do i = 1, Mb(i,j) = a(i,j)+a(i,j-1)+a(i,j-2)c(i,j) = b(i,j) + d(i,j)
enddo
enddo

saved loads for b()

Fused loop nest from weather modeling application

5
Rice University
LCPC 2005

Related Work– Heuristic algorithms to find good fusionsolutions• Gao et. al. [92], Kennedy [00], Lim and Lam[01],– Approaches that aim to reduce bandwidth• Ding and Kennedy [01], Song et. al. [01]– Main distinction from previous work
• Use of architecture specific information• Empirical tuning of fusion parameters

LCPC 2005

Rice University6

Outline– Motivation– Related Work
– Profitability Model• Using hierarchical classification of reuse• Accounting for conflict misses• Enforcing resource constraints• Tuning fusion parameters– Preliminary Experiments– Conclusions and Future WorkLCPC 2005

Rice University

7

Hierarchical Reuse– Use the concept of reuse level as a way toquantify reuse at each level of the memory
hierarchy– Associate with each reference a value that
expresses the level at which the reuse is
exploited
Reuse Level = smallest k such that
Reuse Distance ≤ Capacity(Lk)

LCPC 2005

Rice University8

Hierarchical Reuse– Obtain benefit from reuse of r only if
Reuse Level(r)pre > Reuse Level(r)post– Perform this check for every reusedreference– Account for miss access cost for each levelof memory

LCPC 2005

Rice University

9Conflict Miss Model– Use a probabilistic model to predict when aconflict miss might occur• Derived from Hill & Smith model for
associativity [HS:IEEE89]– Ask the question:
If m distinct cache lines are accessed between
references to the same cache line r what is theprobability that n of them are going to land in
the line occupied by r?

LCPC 2005

Rice University

10mmemory
accessr1

r1

2-waycache?
?
Set 0 Set 1Set n⎛ m⎞⎡1⎤i ⎡ s −1⎤m−iP = 1− ∑⎜ ⎟⎢ ⎥ ⎢⎥⎦⎣⎦⎣iss
i= 0 ⎝ ⎠a−1Set P to be ≤ T

Effective Cache Capacitym ≤ E(a,s,T)Effective Cache Capacity– Effective cache capacity is the maximum
reuse distance for which we can expect areused value to still be in cache– We adjust the definition of reuse levelbased on the definition of effective cachecapacity

Reuse Level = smallest k such that
Reuse Distance ≤ ECC(Lk)

LCPC 2005

Rice University

12Evaluation of Conflict Miss Model:
erlebacher
16%
14%
12%
10%
8%
6%
4%
2%
0%(10, 76)(52, 182)
Predicted

LCPC 2005(107, 272)

Measured (direct)

Rice University(166, 349)

Measured (2-way)13

Evaluation of Conflict Miss Model:
arraysweep
16%
14%
12%
10%8%
6%
4%2%0%(10, 76)(52, 182)
Predicted

LCPC 2005(107, 272)

Measured (direct)

Rice University(166, 349)

Measured (2-way)14

Resource Constraints– Need to constrain resource demands offused loop
Register Pressure(Lfused) < Register Set Size
Instructions(Lfused) < I-Cache Capacity– Easy to incorporate into a constrained
weighted fusion algorithm

LCPC 2005

Rice University

15

Parameterizing the Model– Parameters amenable to tuning• Effective Cache Capacity• Register Set Size
• I-Cache Capacity

LCPC 2005

Rice University

16

Parameterizing the Model– Use a tolerance factor to determine howmuch of a resource we can use at eachtuning step
Effective Registers = T x Register Set Size
[0 < T ≤ 1]
Effective Cache Capacity = E(a, s, T)[0.01 ≤ T ≤ 0.20]

LCPC 2005

Rice University

17

Tuning Fusion Parameters– Start off conservatively with a low tolerance
value and increase tolerance at each step
– Each tuning parameter constitutes a single
search dimension– Search is sequential and orthogonal• stop when performance starts to worsen• use reference values for other dimension whensearching a particular dimension

LCPC 2005

Rice University

18

Experimental Setup– Four different strategies• ccfm, simple, mips-pro, no-fuse– Four benchmarks• advect3d, erlebacher,livermore18, mgrid– Platform• SGI R12K
• 2-level cache hierarchy• Primary L1 I-Cache, Unified L2

LCPC 2005

Rice University

19Performance Improvement Summary
1.5
1.4

Speedup over no-fuse1.3
1.2

ccfm

1.1

simple1

mips-pro

0.9

nofuse0.8
0.7
advect3d

erlebacher

liv18

mgridBenchmarks

LCPC 2005

Rice University

20

Conclusions– Detailed cache effect analysis combinedwith empirical search can lead to better
fusion choices– Overall memory performance can befurther improved by considering fusion andtiling interactions

LCPC 2005

Rice University21Extra Slides Begin Here

Memory Performance
Comparison: advect3d
1.3

1.2

1.1

ccfm
simplemips
no-fuse

1

0.9

0.8
CyclesLCPC 2005

L1D Misses

L2D Misses

Rice University

Graduated lds23Memory Performance
Comparison: erlebacher
1.3

1.2

1.1
ccfm
simple1

mips-pronofuse
0.9

0.8

0.7
CyclesLCPC 2005

L1D Misses

L2D Misses

Rice University

Graduated lds

24Memory Performance
Comparison: livermore18
1.5
1.4
1.3
1.2
1.1

ccfm
simple1

mips-pro
0.9

nofuse

0.8
0.7
0.6
0.5
CyclesLCPC 2005

L1D Misses

L2D Misses

Rice University

Graduated lds

25Memory Performance
Comparison: m g rid
1.2

1.1

ccfm
simple1

mips-pronofuse0.9

0.8
CyclesLCPC 2005

L1D Misses

L2D Misses

Rice University

Graduated lds

26

Experimental Results on advect3dFusion
StrategyCycle CountL1D Misses

L2D Misses

Graduated
Loads

Speedupccfm

8.41E+04

4.48E+04

5.13E+04

3.66E+05

1.17

simple

1.23E+05

3.78E+04

5.08E+04

4.26E+05

0.80

mips-pro

9.88E+04

3.76E+04

9.19E+04

3.06E+05

1.00

nofuse9.88E+04

3.76E+04

9.19E+04

3.06E+05

1.00

LCPC 2005

Rice University27

Experimental Results on erlebacher

FusionStrategyCycle CountL1D Misses

L2D Misses

Graduated
Loads

Speedupccfm

5.23E+09

2.00E+08

2.72E+07

4.02E+08

1.08simple

5.68E+09

1.85E+08

3.09E+07

3.90E+08

0.99

mips-pro

5.23E+09

1.70E+08

2.74E+07

4.52E+08

1.08

nofuse5.65E+09

2.34E+08

2.92E+07

4.34E+08

1.00

LCPC 2005

Rice University28

Evaluation of Conflict Miss Model :randaccess
18%
16%
14%
12%
10%
8%
6%
4%
2%
0%
(10, 76)(52, 182)
Predicted

LCPC 2005(107, 272)

Measured (direct)

Rice University(166, 349)

Measured (2-way)29

Putting It All Together– Use hierarchical reuse analysis and conflict
miss model to assign weights between
fusible loops– Use weights to drive a resource
constraint-based fusion algorithm– Empirically tune for effective cache
capacity and other parameters

LCPC 2005

Rice University30