loading...
Exploiting Postdominance for Speculative Parallelization
Scottsdale, AZ, USA February 10-February 14
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/HPCA.2007.3462072007 IEEE 13th International Symposiu ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Mayank Agarwal, Coordinated Science Laboratory, University of Illinois, Urbana-Champaign. magarwa2@uiuc.edu
Kshitiz Malik, Coordinated Science Laboratory, University of Illinois, Urbana-Champaign. kmalikl@uiuc.edu
Kevin M. Woley, Coordinated Science Laboratory, University of Illinois, Urbana-Champaign. woley@uiuc.edu
Sam S. Stone, Coordinated Science Laboratory, University of Illinois, Urbana-Champaign. ssstone2@uiuc.edu
Matthew I. Frank, Coordinated Science Laboratory, University of Illinois, Urbana-Champaign. mif@uiuc.edu
Task-selection policies are critical to the performance of any architecture that uses speculation to extract parallel tasks from a sequential thread. This paper demonstrates that the immediate postdominators of conditional branches provide a larger set of parallel tasks than existing task-seletion heuristics, which are limited to programming language constructs (such as loops or procedure calls). Our evaluation shows that postdominance-based task selection achieves, on average, more than double the speedup of the best individual heuristic, and 33% more speedup than the best combination of heuristics. The specific contributions of this paper include, first, a description of task selection based on immediate postdominance for a system that speculatively creates tasks. Second, our experimental evaluation demonstrates that existing task-selection heuristics based on loops, procedure calls, and if-else statements are all subsumed by compilergenerated immediate postdominators. Finally, by demonstrating that dynamic reconvergence prediction closely approximates immediate postdominator analysis, we show that the notion of immediate postdominators may also be useful in constructing dynamic task selection mechanisms.
Citation:
Mayank Agarwal, Kshitiz Malik, Kevin M. Woley, Sam S. Stone, Matthew I. Frank, "Exploiting Postdominance for Speculative Parallelization," hpca, pp.295-305, 2007 IEEE 13th International Symposium on High Performance Computer Architecture, 2007
Usage of this product signifies your acceptance of the Terms of Use.