Loop Selection for Thread-Level
Speculation
Shengyue Wang, Xiaoru Dai, Kiran S. Yellajyosula,
Antonia Zhai, Pen-Chung Yew
Department of Computer Science & Engineering
University of Minnesota

Chip Multiprocessors (CMPs)
IBM Power5• CMPs:•IBM Power5• Sun Niagara• Intel dual-core Xeon
• AMD dual-core Opteron

Proc Proc
Proc
Cache

Improve program performance with parallel threads

Shengyue Wang

Thread-Level Speculation (TLS)
Automatic parallelization is difficult•

Ambiguous data dependences• Complex control flow

TLS facilitates automatic parallelization by:•Executing potentially dependent threads in parallel• Preserving data dependences via runtime checking
Where do we find speculative parallel threads?

Shengyue Wang

Parallelizing Loops under TLS
Loops are good candidates for parallelism•

Regular structure• Significant coverage on dynamic execution time

General purpose applications are complicatedFacts about SPECINT 2000•

Average number of loops: 714• Average dynamic loop nesting: 8Loop selection: which loops should be parallelized?
Shengyue Wang

Potential of Loop Selection
Outer loop

Inner loop

Best

80%
60%
40%
20%

perlbmkgccgappa
rs
er

vp
r

gz
ipbz
ip2vorte
x-40%

twolf-20%

cr
af
ty0%

mcf

program speedup

100%

Carefully selected loops can improve performance significantly!

Shengyue Wang

Outline¾ Loop selection¾Algorithm• Parallel performance prediction• Dynamic loop behavior• Conclusions

Shengyue Wang

Loop Nestingmain( ) {while ( condition1 ) {while ( condition2 ) {foo( );goo( );}}}
foo( ) {while ( condition3 ) {goo( );}}
goo( ) {while ( condition4 ) {}}Source codeShengyue Wang

main_loop1

main_loop2

foo_loop1

goo_loop1

Loop graph: static loop
: nesting relationshipBenefit of Parallelizing a Single Loop13%

main_loop1
20%main_loop2
5%foo_loop1

Coverage

Loop Speedup

Benefit

80%

1.2

13%

70%

1.4

20%

30%

1.2

5%

50%

1.6

18%

18%

goo_loop1

benefit = % program execution time saved= coverage × (1 – 1 / loop speedup)

Program speedup = 1 / (1 - benefit) = 1.25

Shengyue Wang

Loop Selection: Problem Definition
Goal:
Select the set of loops that maximizes theoverall program performance when parallelized

Constraint:
The set cannot contain loops with nesting
relationship

Loop selection is NP-complete!
Weighted maximum independent set

Shengyue Wang

Loop Selection: Algorithm• Exhaustive search (≤ 50 nodes)•

Try all possible combinations of loops• Greedy algorithm (> 50 nodes)•In descending order of benefit• Check for nesting relation• Add the loop to the set if no nesting

Average number of loops for SPECINT 2000: 714

Shengyue Wang

Loop Pruning
loop1

loop2

loop4

loop3

loop5

loop7

loop6loop8

Only resort to greedy algorithm for gcc and parser

Shengyue Wang

Benefit of Parallelizing a Single Loop13%

main_loop1
20%main_loop2
5%foo_loop1

Coverage

Speedup

Benefit

80%

1.2

13%

70%

1.4

20%

30%

1.2

5%

50%

1.6

18%

18%

goo_loop1

Loop graph

Shengyue Wang

How can we estimate the speedup?

Outline¾ Loop selection• Algorithm¾Parallel performance prediction• Dynamic loop behavior• Conclusions

Shengyue Wang

Estimating Parallel Performance
Communicating value between speculative threads
adds significant overhead to parallel execution• Synchronization:• Resolves frequently occurring data dependences• Speculation:• Resolves infrequently occurring data dependences

Estimating communication costs with the compiler

Shengyue Wang

Cost of Mis-speculation
T1

T2
load

store

Amount ofwork wasted

×

Cost of mis-speculation= amount of work wasted × prob. of mis-speculation
Shengyue Wang

Cost of Mis-speculation
T1

Sequential part

T2
load
store

Amount ofwork wasted

×

Cost of mis-speculation= amount of work wasted × prob. of mis-speculation
Shengyue Wang

Synchronization

T1

store

T2

load

Synchronization serializes parallel execution

Shengyue Wang

Cost of Synchronization
T1
store2store1

Est. III

Est. II

Est. I
T2

T1

T2

T1

T2

load1
load2

store1store1

load1

load1

Synchronization Cost =Synchronization Cost =Synchronization Cost =# of dependent instructions

longest stall

longest stall based on
dependent instructions

Shengyue Wang

Experimental Framework• Machine model•

4 single-issue in-order processors• Private L1 data cache (32K, 2-way, 1 cycle)• Shared L2 data cache (2M, 4-way, 10 cycles)• Speculation support (write buffer, address buffer)• Synchronization support (comm. buffer, 10 cycles)• Compiler optimizations using ORC 2.1•Instruction scheduling to improve parallelism

Shengyue Wang

Comparison: Speedup Estimation Techniques
100%

program speedup

Est. I80%

Est. II

60%

Est. III40%

Perfect

20%
0%
-20%

mcf

crafty-40%

twolf

gzip

bzip2

vortexvpr

parsergap

gcc

perlbmk

Average program speedup: 20%, coverage: 70%

coverage100%

Est.II I
Est.
Est.

80%
80%

Est.IIII
Est.
Est. III
Est. III60%60%

Perf ect

Perfect
Perfect40%

40%

20%20%0%0%
mcfWangcrafty
Shengyuemcfcrafty

twolf

twolf

gzip

gzip

bzip2

bzip2

vortexvortexvpr

vpr

parserparserparser

gap

gap
gap

gcc

gcc
gcc

perlbmk

perlbmperlbmkk

Outline• Loop selection• Algorithm• Parallel performance prediction¾ Dynamic loop behavior• Conclusions

Shengyue Wang

Loop Behavior May Changemain( ) {while ( condition1 ) {while ( condition2 ) {foo( );goo( );}}}
foo( ) {while ( condition3 ) {goo( );}}goo( ) {while ( condition4 ) {}}Source code
Shengyue Wang

main_loop1

main_loop2

foo_loop1

goo_loop1_A

goo_loop1_B

Loop tree
Calling context of a loop:
the path from the root to that loop

Loop Selection in a Tree13%

main_loop1
20%main_loop2

goo_loop1 is parallelized
only when it is reachedfrom main_loop2

5%foo_loop1-2%

goo_loop1_A

18%

goo_loop1_B

Loop cloning can be used

Shengyue Wang

Loop Behavior May Change
main_loop1

foo_loop1

only parallelize the loop
in these invocationsfoo_loop1

goo_loop1_A

goo_loop1_B

Exploit loop behavior dynamically
Shengyue Wang

Potential of Exploiting Dynamic Behavior
Callingtt
CallingContex
ContexOracleO
racle

60%
40%20%perlb
mkgccgappa
rser

vprbz
ip2vortexgz
ip

twolf

cr
af
ty

0%

100%

5 out of 11 benchmarks show performance potentialNoNoContex
Contextt
Calling
CallingContex
Contextt

80%

OOracleracle

60%
40%perlbmk

gccgappa
rser

vprbz
ip2vortexgz
ip

cr
af
ty0%
Shengyue Wang

twolf20%m
cf

coverage

Nott
NoContexContex

80%m
cf

program speedup

100%Conclusions
Loop selection is important for TLS• Compiler-based loop selection• Speedup 20%, Coverage 70%• Exploiting dynamic behavior offers
performance potential

Shengyue Wang

Thank You!

Shengyue Wang