Loop selection for thread-level speculation

Shengyue Wang, Xiaoru Dai, Kiran S. Yellajyosula, Antonia Zhai, Pen Chung Yew

Research output: Chapter in Book/Report/Conference proceedingConference contribution

22 Scopus citations

Abstract

Thread-level speculation (TLS) allows potentially dependent threads to speculatively execute in parallel, thus making it easier for the compiler to extract parallel threads. However, the high cost associated with unbalanced load, failed speculation, and inter-thread value communication makes it difficult to obtain the desired performance unless the speculative threads are carefully chosen. In this paper, we focus on extracting parallel threads from loops in general-purpose applications because loops, with their regular structures and significant coverage on execution time, are ideal candidates for extracting parallel threads. General-purpose applications, however, usually contain a large number of nested loops with unpredictable parallel performance and dynamic behavior, thus making it difficult to decide which set of loops should be parallelized to improve overall program performance. Our proposed loop selection algorithm addresses all these difficulties. We have found that (i) with the aid of profiling information, compiler analyses can achieve a reasonably accurate estimation of the performance of parallel execution, and that (ii) different invocations of a loop may behave differently, and exploiting this dynamic behavior can further improve performance. With a judicious choice of loops, we can improve the overall program performance of SPEC2000 integer benchmarks by as much as 20%.

Original languageEnglish (US)
Title of host publicationLanguages and Compilers for Parallel Computing - 18th International Workshop, LCPC 2005, Revised Selected Papers
Pages289-303
Number of pages15
DOIs
StatePublished - Dec 1 2006
Event18th International Workshop on Languages and Compilers for Parallel Computing, LCPC 2005 - Hawthorne, NY, United States
Duration: Oct 20 2005Oct 22 2005

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4339 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other18th International Workshop on Languages and Compilers for Parallel Computing, LCPC 2005
CountryUnited States
CityHawthorne, NY
Period10/20/0510/22/05

Fingerprint Dive into the research topics of 'Loop selection for thread-level speculation'. Together they form a unique fingerprint.

Cite this