Register Pressurein Software-Pipelined Loop Nests
Fast Computation and Impact on Architecture Design

Alban Douillet

Guang R. Gao{douillet,ggao}@capsl.udel.edu
Department of Electrical & Computer Engineering
University of Delaware

18th International Workshop
on Languages and Compilers for Parallel Computing
Hawthorne, New York
October 20th -22nd , 2005

A. Douillet, G.R. Gao (Univ. of Delaware)

Register Pressure in SWP’ed Loop Nests

LCPC’05

1 / 43

Introduction

Scientific Applications
loop nests dominantSingle-dimension Software Pipelining (SSP)
software pipelines most profitable loop in loop nesthigh register pressure
register allocation is time-consuming

Need for a fast method to evaluate register pressure
detect infeasible schedules before calling the register allocatormeasure quality of register allocation solution
give estimate of register needs for future architecture designs

A. Douillet, G.R. Gao (Univ. of Delaware)

Register Pressure in SWP’ed Loop Nests

LCPC’05

2 / 43

Outline1

Loop Nest Software-Pipelining

2

Problem Statement

3

Definitions & Issues

4

Fast Register Pressure Computation

5Experiments

6Conclusion

A. Douillet, G.R. Gao (Univ. of Delaware)

Register Pressure in SWP’ed Loop Nests

LCPC’05

3 / 43

Outline1

Loop Nest Software-Pipelining

2

Problem Statement

3Definitions & Issues

4

Fast Register Pressure Computation

5Experiments

6Conclusion

A. Douillet, G.R. Gao (Univ. of Delaware)

Register Pressure in SWP’ed Loop Nests

LCPC’05

4 / 43Modulo Schedulingmost popular SWP techniquewell studied and understoodfull array of loop optimizations
single loop, parallel execution of iterations
new iteration issued every T cyles (initiation interval)

FOR J=0,4bcd
END FOR

A. Douillet, G.R. Gao (Univ. of Delaware)bc bd cbdcbdcbdc

prologkerneld

Register Pressure in SWP’ed Loop Nests

epilog

LCPC’05

5 / 43Modulo Scheduling

But...
limited to innermost loop
loop transformations to bring ILP or data cache reuse potential to
innermost loop not always possible

A. Douillet, G.R. Gao (Univ. of Delaware)

Register Pressure in SWP’ed Loop Nests

LCPC’05

6 / 43

Single-Dimension Software-Pipelining (SSP)

proposed by Rong et al. (CGO’04, PLDI’05)
software pipelines the most profitable loop level in a loop nestequivalent to MS if innermost level selected
can be seen as generalization of MS to loop nests
proven performance boost vs. MS
can take advantage of loop optimizations used for MS
single-dimension b/c simplifies multi-dimensional DDG into a
uni-dimensional DDG

A. Douillet, G.R. Gao (Univ. of Delaware)

Register Pressure in SWP’ed Loop Nests

LCPC’05

7 / 43

SSP Kernel
SSP generates a kernel similar to MS
enclosed stages
single initiation interval T
L1 is the outermost loop and Ln the innermost
Si : number of stages at level i
middle loop stages

cycles01...

TT−2
T−1

innermost stages

A. Douillet, G.R. Gao (Univ. of Delaware)

Register Pressure in SWP’ed Loop Nests

LCPC’05

8 / 43

SSP Ideal Schedule

Generated using kernel as a template
new outermost iteration issued every T cycles
outermost iterations executed in parallel
inner iterations executed sequentially within one outermost iteration
resource conflicts!

A. Douillet, G.R. Gao (Univ. of Delaware)

Register Pressure in SWP’ed Loop Nests

LCPC’05

9 / 43

SSP Ideal Schedule: Examplea

FOR I=1,4a
FOR J=1,3bcd
END FOReEND FORS1=5edcb aTb ac b ad c b ab d c b

T=1S2=3
A. Douillet, G.R. Gao (Univ. of Delaware)

cbdcdcbdbdcbcbdcdecbddecbdec

resource
conflicts

deRegister Pressure in SWP’ed Loop Nests

LCPC’05

10 / 43SSP Final Schedule

delays some outermost iterations toavoid resource conflicts
outermost iterations executed in groupsof Sn
resource conflict-free scheduleab ac b ad c bb d cc b dd c bb d cc b dd c be d ce deSniterations

A. Douillet, G.R. Gao (Univ. of Delaware)

Register Pressure in SWP’ed Loop Nests

delayabcdbcdb
LCPC’05

11 / 43SSP Loop Patterns...

Patterns:
Outermost Loop Pattern
Inner Loop Execution Segment

OLP

Innermost Loop Pattern
Draining & Filling Pattern

Composition:
OLP: all S kernel stages
ILES: cyclic combination of Sn
consecutive stages

ILES

e d c b aKernelOLP

e d c b ae d c b ad cc dd c
ILPc dd c
DFPb ddelayc bdcdce decdcdc b ad c b a...

A. Douillet, G.R. Gao (Univ. of Delaware)

Register Pressure in SWP’ed Loop Nests

LCPC’05

12 / 43SSP Implementation
loop nest

LoopSelection

Dependence
Simplification

loopnest

1−DDDG

Schedule
Construction

kernelRegister
Allocation

A. Douillet, G.R. Gao (Univ. of Delaware)registerallocatedkernelCode
Generation

Register Pressure in SWP’ed Loop Nests

final schedule

LCPC’05

13 / 43

Outline1

Loop Nest Software-Pipelining

2

Problem Statement

3

Definitions & Issues

4

Fast Register Pressure Computation

5Experiments

6Conclusion

A. Douillet, G.R. Gao (Univ. of Delaware)

Register Pressure in SWP’ed Loop Nests

LCPC’05

14 / 43

Motivationneed to determine feasibility of schedules
register allocation is time-consuming
unfeasible schedules b/c of high register pressure not uncommon

need to evaluate quality of register allocator
how far from optimal solution?

need to evaluate actual register needs for architectural designs
are register files big enough?

A. Douillet, G.R. Gao (Univ. of Delaware)

Register Pressure in SWP’ed Loop Nests

LCPC’05

15 / 43

Problem Statement

Given a loop nest and an SSP schedule for it, evaluate the registerpressure MaxLive of the final schedule.
only rotating registers
MaxLive = maximum number of live variables at any given cycle in thefinal schedule
MaxLive definition similar to the one for MS.

A. Douillet, G.R. Gao (Univ. of Delaware)

Register Pressure in SWP’ed Loop Nests

LCPC’05

16 / 43

Updated SSP Implementation
loop nest

LoopSelection
choose different
loop levelloopnest

Dependence
Simplification

1−DDDG

Schedule
Construction

OR increase initiation interval
kernelyes

Register Pressure

too high?

Evaluation

noRegister
Allocation

A. Douillet, G.R. Gao (Univ. of Delaware)registerallocatedkernel

Code
Generation

Register Pressure in SWP’ed Loop Nests

final schedule

LCPC’05

17 / 43

Outline1

Loop Nest Software-Pipelining

2

Problem Statement

3

Definitions & Issues

4

Fast Register Pressure Computation

5Experiments

6Conclusion

A. Douillet, G.R. Gao (Univ. of Delaware)

Register Pressure in SWP’ed Loop Nests

LCPC’05

18 / 43

Definitions
scalar lifetime:
start: definition cycle of the value
end: kill cycle of the value
omega: number of outermost iterations spannedclassification
global: constant values, ignored
input & output: prolog and epilog, ignored
local: within same outermost iteration
cross-iteration: between outermost iterations

localstartcross−iteration

endomega

A. Douillet, G.R. Gao (Univ. of Delaware)

Register Pressure in SWP’ed Loop Nests

LCPC’05

19 / 43

Issuesmore complex lifetime patterns than MS
non-constant initiation ratestretched lifetimes

same stage may have different lifetimes patterns
a stage is not always followed by the same stages
difference between first and last instance of the same stage

A. Douillet, G.R. Gao (Univ. of Delaware)

Register Pressure in SWP’ed Loop Nests

LCPC’05

20 / 43

Lifetimes Exampleedcbaedcbdccddcbdcbdcbaedcbe

A. Douillet, G.R. Gao (Univ. of Delaware)aRegister Pressure in SWP’ed Loop Nests

aLCPC’05

21 / 43

Outline1

Loop Nest Software-Pipelining

2

Problem Statement

3

Definitions & Issues

4

Fast Register Pressure Computation

5

Experiments

6

Conclusion

A. Douillet, G.R. Gao (Univ. of Delaware)

Register Pressure in SWP’ed Loop Nests

LCPC’05

22 / 43

Method Overview

Method Keys:
separate OLP from ILES instances of stages
separate first from last instances of stages
separate local from cross-iteration lifetimes
Steps:
count number of local lifetimes in first instance of stages
count number of local lifetimes in last instance of stages
count number of cross-iteration lifetimes in each stage
list all possible combinations of stages in schedule
add number of lifetimes for each combination in OLP and ILES
MaxLive is the highest value

A. Douillet, G.R. Gao (Univ. of Delaware)

Register Pressure in SWP’ed Loop Nests

LCPC’05

23 / 43

Local Lifetimes

last

traditional liveness analysis
computes for both first andlast instances of stage seach cycle c in stage
between 0 and T − 1live-out set of stage(c = T )firststage of level i visited itimes
LTlocal (s, c, first/last)level 1

A. Douillet, G.R. Gao (Univ. of Delaware)

Register Pressure in SWP’ed Loop Nests

level 2level 3

LCPC’05

24 / 43

Cross-Iteration Lifetimes
Sdef = 1
cdef = 2

aneed stage and cycle ofdefinition and killdirect formulafor each cycle c in OLP
between 0 and T − 1
not stage-specific

Skill = 0c kill = 0bacbadcbaLT cross212omega=3LTcross (c)=X((Skill (v ) − Sdef (v ) + 1) + δdef (c, v ) + δkill (c, v ))v ∈civswhere

A. Douillet, G.R. Gao (Univ. of Delaware)δdef (c, v ) = −1 if c < cdef (v ), 0 otherwise
δkill (c, v ) = −1 if c > ckill (v ), 0 otherwise

Register Pressure in SWP’ed Loop Nests

LCPC’05

25 / 43

OLP: last stages local lifetimesedcbaedcbdccddcbdcbdcbaedcbeaa

Combination of first and last stages not always the samel1X

LTlocal (s, c, last)s=ln −i

A. Douillet, G.R. Gao (Univ. of Delaware)

Register Pressure in SWP’ed Loop Nests

LCPC’05

26 / 43

OLP: first stages local lifetimes
edcbaedcbdccddcbdcbdcbaedcbeaa

Combination of first and last stages not always the same
lnX
−1−i

LTlocal (s, c, first)

s=f1

A. Douillet, G.R. Gao (Univ. of Delaware)

Register Pressure in SWP’ed Loop Nests

LCPC’05

27 / 43

OLP: cross-iteration lifetimes

edcbaedcbdccddcbdcbdcbaedcbeaa

Number of cross-iteration lifetimes identical between instances of OLP
LTcross (c)A. Douillet, G.R. Gao (Univ. of Delaware)

Register Pressure in SWP’ed Loop Nests

LCPC’05

28 / 43

OLP count

LTolp (c)= LTcross (c)+ max i∈[1,Sn ]A. Douillet, G.R. Gao (Univ. of Delaware)

l1X

LTlocal (s, c, last) +s=ln −i

Register Pressure in SWP’ed Loop Nests

lnX−1−is=f1

LTlocal (s, c, first)

LCPC’05

29 / 43

ILES: last stretched local lifetimes
edcbaedcbdccddcbdcbdcbaedcbeaa

Live-out of last stages
l1X

LTlocal (s, T , last)

s=ln

A. Douillet, G.R. Gao (Univ. of Delaware)

Register Pressure in SWP’ed Loop Nests

LCPC’05

30 / 43

ILES: first stretched local lifetimes
edcbaedcbdccddcbdcbdcbaedcbeaaLive-out of first stages
fXn −2

LTlocal (s, T , first)

s=f1

A. Douillet, G.R. Gao (Univ. of Delaware)

Register Pressure in SWP’ed Loop Nests

LCPC’05

31 / 43

ILES: stretched cross-iteration lifetimes

edcbaedcbdccddcbdcbdcbaedcbeaa

live-out cross-iteration lifetimes from OLP
LTcross (T )A. Douillet, G.R. Gao (Univ. of Delaware)

Register Pressure in SWP’ed Loop Nests

LCPC’05

32 / 43

ILES: local lifetimes
edcbaedcbdccddcbdcbdcbaedcbeaa

Sn consecutive stages (cyclic)maxl∈[2,n]max

i0 ∈[0,Sl −1]

A. Douillet, G.R. Gao (Univ. of Delaware)

SXn −1!!

LTlocal (fl + (i0 + i)%Sl , c, first)

i=0

Register Pressure in SWP’ed Loop Nests

LCPC’05

33 / 43

ILES countLTiles (c)= LTcross (T )+l1
X

LTlocal (s, T , last)

s=ln+

fX
n −2

LTlocal (s, T , first)

s=f1+ maxl∈[2,n]A. Douillet, G.R. Gao (Univ. of Delaware)max

i0 ∈[0,Sl −1]

SXn −1!!

LTlocal (fl + (i0 + i)%Sl , c, first)

i=0

Register Pressure in SWP’ed Loop Nests

LCPC’05

34 / 43

MaxLive

FatCoverolp=FatCoveriles=MaxLive

A. Douillet, G.R. Gao (Univ. of Delaware)max∀c∈[0,T −1]

max∀c∈[0,T −1]

LTolp (c)(LTiles (c))= max(FatCoveriles , FatCoverolp )Register Pressure in SWP’ed Loop Nests

LCPC’05

35 / 43

Outline1

Loop Nest Software-Pipelining

2

Problem Statement

3

Definitions & Issues

4

Fast Register Pressure Computation

5Experiments

6Conclusion

A. Douillet, G.R. Gao (Univ. of Delaware)

Register Pressure in SWP’ed Loop Nests

LCPC’05

36 / 43

Experimental Framework

ORC2.1 compiler
1.4Ghz Itanium workstation, 1GB RAM
Livermore, SPEC2000 FP, NPB 2.2 benchmarks
127 loop nests
328 test cases

A. Douillet, G.R. Gao (Univ. of Delaware)

Register Pressure in SWP’ed Loop Nests

LCPC’05

37 / 43

Running Timein the order of 1/1000 sec
quadratic running time
3 orders of magnitude faster than register allocator
speedup increases as loop gets deeper⇒ fast enough to use in SSP framework
100000Speedup (log scale)

10000

1000

100

101Benchmarks

A. Douillet, G.R. Gao (Univ. of Delaware)

Register Pressure in SWP’ed Loop Nests

LCPC’05

38 / 43

MaxLive

Average: INT=42 FP=15
register pressure too high for 43% of loop nests of depth 4

Amenability Ratio

1
0.8
0.6
0.4
0.2
01

A. Douillet, G.R. Gao (Univ. of Delaware)

234Depth

5

Register Pressure in SWP’ed Loop Nests

LCPC’05

39 / 43

FP/INT Comparison
FP register pressure stable as loop gets deeper
pressure never exceeds 64 registers

INT register pressure increases as loop gets deeper
loop overheads
array indexes
longer live ranges
50
Level 3 or higher
Level 2
Level 1

Extra FP Register Pressure per Level

45403530
2520151050Benchmarks

A. Douillet, G.R. Gao (Univ. of Delaware)

Register Pressure in SWP’ed Loop Nests

LCPC’05

40 / 43

Register File Size
max FP register file size: 64
ideal INT/FP ratio: 277% and 67% of loop nests of depth 4 and 5 would become feasible
256

2192
160

1.5

128
1FP/INT Ratio

Total Register Pressure (FP+INT)

224

2.5
Total Register Pressure
FP/INT Ratio

96
640.5

320Benchmarks

A. Douillet, G.R. Gao (Univ. of Delaware)

Register Pressure in SWP’ed Loop Nests

LCPC’05

41 / 43

Outline1

Loop Nest Software-Pipelining

2

Problem Statement

3Definitions & Issues

4

Fast Register Pressure Computation

5Experiments

6Conclusion

A. Douillet, G.R. Gao (Univ. of Delaware)

Register Pressure in SWP’ed Loop Nests

LCPC’05

42 / 43

Conclusion

SSP
software-pipelines loop nests at the most profitable levelregister pressure is however very highneed for fast method to evaluate register pressure
detect infeasible schedules earlymeasure quality of register allocator
give an estimate of the actual register needs for future architecture designs

proposed solution
deals with issues specific to loop nest SWP and SSP
is very fast and can be used before register allocation

future work
incremental solution to be integrated to the scheduler
different architectures: clustered VLIW,...

A. Douillet, G.R. Gao (Univ. of Delaware)

Register Pressure in SWP’ed Loop Nests

LCPC’05

43 / 43