 |
The Recursive LRPD Test
The Recursive LRPD Test
Description
The original LRPD test worked well for fully parallel loops. However, partially parallel loops would have a slowdown equal to the speculative parallel execution time. For loops which were presumed to be partially parallel, we have developed an inspector/executor technique. The major disadvantages are that this method may require large additional data structures and a proper side-effect free inspector is not always available.
We propose to transform a partially parallel loop into a sequence of fully parallel loops. We use a block-scheduled processor-wise version of the original LRPD test. All iterations before the sink of the first data dependence executed correctly and are committed. Then, the LRPD test is reapplied in the same manner on the remaining iterations. The following picture describes the Recursive LRPD (R-LRPD) algorithm.
R-LRPD Algorithm
The worst case for this method is that the total time is proportional to the sequential time plus the testing overhead. Thus, we can use apply the same method for both fully and partially parallel loops.
We have also used the following optimizations in conjunction with the R-LRPD test:
- Work Redistribution (RD) - If a failure is detected, the remaining iterations can be redistributed across all processors. This will decrease the execution time for each stage. However, more dependences may be uncovered across processors and remote cache misses may be caused from data redistribution. The following illustrations depicts work redistribution.
Work Redistribution Illustration
- On-demand Checkpointing (ODC) - Before speculative execution, all shared data structures that may be modified during loop must be checkpointed. Another approach is to checkpoint during loop execution. It is fully parallel and the per operation cost is small. For sparse codes, the on-demand strategy can be orders of magnitude less than a full-copy approach.
- Feedback-Guided Block Scheduling (FB) - Blocked scheduling is a requirement of the R-LRPD test and can pose performance problems. Our solution was to use the timing information from the previous instantiation to predict a schedule for the current instantiation with minimal load imbalance. Also, redistribution can use feedback-guided block scheduling to distribute based upon the time distribution of the remaining iterations.
Experimental Results
We have applied the R-LRPD test to the most important loops in TRACK, a PERFECT benchmark. Also, we have created several inputs to vary the degree of parallelism.
 |
 |
| TRACK Program Speedup | NLFILT Optimization Contributions |
 |
 |
| EXTEND_do400 Speedup | FPTRAK_do300 Speedup |
NLFILT_do300 Speedup
Publications
The R-LRPD Test: Speculative Parallelization of Partially Parallel Loops, Francis Dang, Hao Yu, Lawrence Rauchwerger, In Proc. Int. Par. and Dist.
Proc. Symp. (IPDPS), Fort Lauderdale, FL, Apr 2002. Also, Technical Report, TR02-001, Department of Computer Science and Engineering, Texas A&M University, College Station, TX, Jan 2002.
Proceedings(ps, pdf, abstract) Technical Report(ps, pdf, abstract)
Speculative Parallelization of Partially Parallel Loops, Francis Dang, Lawrence Rauchwerger, In Wkshp. on Lang. Comp. and Run-time Sys. for Scal. Comp. (LCR)., Rochester, New York, USA, May 2000.
Proceedings(ps, pdf, abstract)
Presentations
The R-LRPD Test: Speculative
Parallelization of Partially Parallel Loops,
in Proc. of the 16th International Parallel and Distributed Processing
Symposium (IPDPS '02)
April 2002, Fort Lauderdale, Florida.
by Francis Dang