Optimal ILP and Register Tiling:
Analytical Model andOptimization Framework

Lakshminarayanan. Renganarayana,
Upadrasta Ramakrishna,
Sanjay RajopadhyeComputer Science Department
Colorado State University

Overview

ILP and register reuseExecution time and register pressure functions

Optimal ILP and register tiling problem

Optimal tiling problem as convex opt. problem

Validation



Related workConclusions & Future work

October 21, 2005

LCPC '05

2

ILP and Register Reuse

Loop programs

dominate application execution timemain sources of ILP and register reuse

Transformations


expose / exploit ILPenable register reuseThese transformations interact in subtle ways

ILP - Register Reuse tradeoff?

October 21, 2005

LCPC '05

3

ILP - Register Reuse Tradeoff Optimal combination of transformations
 Quantification of interactions
 A mathematical modelto study the interactions

to choose the optimal trans. parameters

 TTBOOK: no such model has been studied
October 21, 2005

LCPC '05

4

Contributions
 Cost model with trans. params. as variables

closed forms: execution time & register pressure Convex optimization problem formulation
 A globally optimal solution
 First such formulation & optimal solution

October 21, 2005

LCPC '05

5

Exposing and Exploiting ILP
 Exposing ILP

Unroll and Jam

Loop permutation or skewingMulti-dimensional scheduling Exploiting ILP

DAG schedulers

Software pipelining

October 21, 2005

LCPC '05

6

Exposing ILP with Unroll and Jam
Unrolled Loop body
(9 iterations)for i1 = 1 to 6
for i2 = 1 to 6
A[i1,i2] = A[i1-1,i2]+A[i1,i2-1]

DAG exposesparallelism

October 21, 2005

LCPC '05

7

Exposing ILP with Permutation
for i2 = 1 to 6
for i1 = 1 to 6A[i1,i2] = 3.23 * A[i1,i2-1]

for i1 = 1 to 6
for i2 = 1 to 6
A[i1,i2] = 3.23 * A[i1,i2-1]

October 21, 2005

LCPC '05

8

Exposing ILP with Skewing
for i1 = 1 to 6
for i2 = 1 to 6
A[i1,i2] = A[i1-1,i2]+A[i1,i2-1]

All the iterationsof inner-mostloop are parallel Sufficient ILP Performance limited
only by the available
execution resources

October 21, 2005

LCPC '05

9Register Reuse Unrol and Jam  Scalar replacement
scalar replacement enables register placement

classic register allocators are sufficient Loop tiling  array register allocation

registers allocated to array valuesno code size increase requires an array register allocator

October 21, 2005

LCPC '05

10

Scalar Replacement
for i1 = 1 to 6
for i2 = 1 to 6
A[i1,i2] = A[i1-1,i2]+A[i1,i2-1]
unroll 2 x 2

for i1 = 1 to 6 step 2
for i2 = 1 to 6 step 2
A[i1,i2]= A[i1-1,i2]+A[i1,i2-1]
A[i1+1,i2] = A[i1,i2]+A[i1+1,i2-1]
A[i1,i2+1] = A[i1-1, i2+1]+A[i1,i2]
A[i1+1,i2+1] = A[i1,i2+1]+A[i1+1,i2]

for i1 = 1 to 6 step 2
T = A[i1,0]
for i2 = 1 to 6 step 2
T= A[i1-1,i2]+ T
A[i1+1,i2] = T +A[i1+1,i2-1]
A[i1,i2+1] = A[i1-1, i2+1]+T
A[i1+1,i2+1] = A[i1,i2+1]+A[i1+1,i2]
A[i1,i2]=Treplace A[i1,i2] bya scalar T Saves 2 loop independent loads
plus 1 loop carried load T can be allocated to a register

Which array references to scalar replace?
October 21, 2005

LCPC '05

11TilingTiling Similar to Unroll and Jam Decreases life time of values
 Limits MAXLIVE

for i1 = 1 to 6
for i2 = 1 to 6
A[i1,i2] = A[i1-1,i2]+A[i1,i2-1]

October 21, 2005

LCPC '05

12

Register tilingfor i1 = 1 to 6
for i2 = 1 to 6
A[i1,i2] = A[i1-1,i2]+A[i1,i2-1]

3x3 register tile

Tile sizes:
Affects load/store savings
Constrained by number of registers
How to choose the tile sizes?

October 21, 2005

LCPC '05

13Our Approach

Traditional Approach

Traditional vs. Our Approach
Code Transformation

Sched. & Reg. Alloc

Choose optimal
unroll andscalar promotion
parameters

Unroll and Jam+
Scalar Promotion

DAG Scheduler or
Software Pipelining+
Scalar Register
Allocation

Choose optimal
skew andtile
parameters

Permutation
or Skewing+Tiling

Software Pipelining+
Scalar & Array
Register Allocation

October 21, 2005

LCPC '0514

Program, Tiling, and ArchitectureClass

Input loops:

perfectly nested, rectangular loops

uniform dependence bodies

Rectangular tilingwe assume: input loop nest admits rectangular tiling

ILP-exposed by: permutation or skewingArchitectures: superscalar or VLIWOctober 21, 2005

LCPC '05

15

Execution Time
(When permutation exposes ILP)
T = (ntiles * tile_cost) + loop_overhead
tile_cost =max(comp_cost,load_store_cost)
comp_cost = α * tile_vol
load_store_cost = β * LS(t,D)
loop_overhead = η * LO(t,N)
ntiles = N1/t1 * … * Nn/tn
t = vector of tile sizes
N = vector of iter. space sizes
D = dependence matrix
October 21, 2005

LCPC '05

16

Execution Time Model(when permutation cannot expose ILP: skew)
Skewing affects
 iteration space shape -- makes counting of partial, full, and no. of tiles hard.
 dependence lengths -- affects the amount of data loaded / stored in a tile.

Partial tiles treatedas full tiles.
Number of tiles
approximated by
N1/t1 * … * Nn/tn
 Dep. matrix = SD LS(t,SD) is theload store volume

October 21, 2005

LCPC '05

17

Optimal ILP and Register Tiling:Optimization Problem Formulation
minimize TotalExecutionTime(t,S)
subject to LoadStoreVolume(t,S) ≤ Registers
For a fixed skew S
 t is the only variable opt. prob. reduces to an integer convex opt. prob.

October 21, 2005

LCPC '05

18

Solution Steps
Can permutation expose a parallel loop?
Yes!



No skewing, only tiling

Fix S=I in opt. prob.

Solve for optimal tilesizes Single integer convex
opt. problem.
October 21, 2005

No!

Construct set (Γ)of validskews
 For each element in Γ
solve the fixed skew
optimization problem
 Pick the best
 Only d(d-1) problems

LCPC '05

19

Solving for Optimal Tile Sizes
 Opt. Prob. for tile sizes is a Integer Geometric

Program (à la Integer Linear Programs)
 GPs can be transformed into convex opt. probs.
 Standard solvers are available
 Running time:

depends on #vars & #constraints



few seconds (< 10 secs.)

October 21, 2005

LCPC '05

20

Validation


Experimental validation requires
array register allocatorarchitectural support (like rotating registers)

Similar model used for finding optimal unroll factor

optimal unroll factors can be found with small tweaks

In tiling for memory hierarchy

we have successfully used a similar model
almost all the cost models used by other researchers can becast into our GP framework [RR-SC04]

October 21, 2005

LCPC '0521

Related Work

Unroll and Jam approach

Hierarchical tiling[Carter et al.-95], [Mitchell et al.-98]

Software pipelining of loop nests
[Callhan et al.-90], [Carr-Kennedy-94], [Sarkar-01][Ramanujam-94], [Rong et al. 04], [Rong et al. 05]

Code generation for register tiling[Jiminez et al.-02], [Sarkar-01]

October 21, 2005

LCPC '05

22

Conclusions & Future Work
 A mathematical formulation of the combined

ILP and register tiling problem.
 A globally optimal solution.
 Future work:adapting modulo schedulers to pipeline skewed loopsdeveloping an array register allocatorexperimental validation on benchmarks

October 21, 2005

LCPC '05

23