Article

Software Bubbles: Using Predication to Compensate for Aliasing in Software Pipelines

Authors:

Benjamin Goldberg,

Emily Crutcher,

Chad Huneycutt,

Krishna V. PalemAuthors Info & Claims

PACT '02: Proceedings of the 2002 International Conference on Parallel Architectures and Compilation Techniques

Pages 211 - 221

Published: 22 September 2002 Publication History

Publisher Site

Abstract

This paper describes a technique for utilizing predication to support software pipelining on EPIC architectures in the presence of dynamic memory aliasing. The essential idea is that the compiler generates an optimistic software-pipelined schedule that assumes there is no memory aliasing. The operations in the pipeline kernel are predicated, however, so that if memory aliasing is detected by a run-time check, the predicate registers are set to disable the iterationsthat are so tightly overlapped as to violate the memory dependences. We refer to these disabled kernel operations as software bubbles.

References

[1]

V. Allan, R. Jones, R. Lee, and S. Allan. Software pipelining. ACM Computing Surveys, 27(3), 1995.

Digital Library

Google Scholar

[2]

D. Bernstein, D. Cohen, and D. Maydan. Dynamic memory disambiguation for array references. In Proceedings of the 27th Annual International Symposium on Microarchitecture, pages 105-112., San Jose, CA, November 1994.

Digital Library

Google Scholar

[3]

J. Dongarra D. Callahan and D. Levine. Vectorizing compilers: a test suite and results. In Supercomputing '88, pages 98-105,1988.

Digital Library

Google Scholar

[4]

J. Davidson and S. Jinturkar. Improving instructionlevel parallelism by loop unrolling and dynamic memory disambiguation. In Proceedings of the 28th annual international symposium on Microarchitecture, pages 125-132,1995.

Digital Library

Google Scholar

[5]

S. Muchnick. Advanced Compiler Design and Implementation. Morgan Kaufmann Publishers, 1997.

Digital Library

Google Scholar

[6]

A. Nicolau. Run-time disambiguation: Coping with statically unpredictable dependencies. IEEE Transactions on Computers, 38(5):663-678, 1989.

Digital Library

Google Scholar

[7]

B. R. Rau, M. Schlansker, and P. Tirumalai. Code generation schema for modulo scheduled loops. In Proceedings of the 25th Annual International Symposium on Microarchitecture, pages 158-169, Portland, OR, December 1992.

Digital Library

Google Scholar

[8]

B. Su, S. Habib, W. Zhao, J. Wang, and Y. Wu. A study of pointer aliasing for software pipelining using run-time disambiguation. In Proceedings of the 27th Annual International Symposium on Microarchitecture, pages 112-117, November 1994.

Digital Library

Google Scholar

[9]

The Trimaran Compiler Research Infrastrcture, http://www.trimaran.org.

Google Scholar

[10]

N. Warter, D. Lavery, and W-M. Hwu. The benefit of predicated execution for software pipelining. In Proceedings of the 26th Annual Hawaii International Conference on System Sciences, pages 497-506, Wailea, Hawaii, January 1993.

Crossref

Google Scholar

[11]

M. Wolfe. High Performance Compilers for Parallel Computing. Addison-Wesley Publishing Company, 1995.

Digital Library

Google Scholar

Cited By

View all

Zuck LPnueli AGoldberg BBarrett CFang YHu Y(2018)Translation and Run-Time Validation of Loop TransformationsFormal Methods in System Design10.1007/s10703-005-3402-z27:3(335-360)Online publication date: 29-Dec-2018
https://dl.acm.org/doi/10.1007/s10703-005-3402-z
Goldberg B(2010)Translation validation of loop optimizations and software pipelining in the TVOC frameworkProceedings of the 17th international conference on Static analysis10.5555/1882094.1882097(6-21)Online publication date: 14-Sep-2010
https://dl.acm.org/doi/10.5555/1882094.1882097
Tristan JLeroy X(2010)A simple, verified validator for software pipeliningACM SIGPLAN Notices10.1145/1707801.170631145:1(83-92)Online publication date: 17-Jan-2010
https://dl.acm.org/doi/10.1145/1707801.1706311
Show More Cited By

Recommendations

Software pipelining: an effective scheduling technique for VLIW machines
20 Years of the ACM SIGPLAN Conference on Programming Language Design and Implementation 1979-1999: A Selection

The basic idea behind software pipelining was first developed by Patel and Davidson for scheduling hardware pipe-lines. As instruction-level parallelism made its way into general-purpose computing, it became necessary to automate scheduling. How and ...
Software Pipelining of Nested Loops
CC '01: Proceedings of the 10th International Conference on Compiler Construction

Software pipelining is a technique to improve the performance of a loop by overlapping the execution of several iterations. The execution of a software-pipelined loop goes through three phases: prolog, kernel, and epilog. Software pipelining works best ...
Complementing software pipelining with software thread integration
Proceedings of the 2005 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems

Software pipelining is a critical optimization for producing efficient code for VLIW/EPIC and superscalar processors in high-performance embedded applications such as digital signal processing. Software thread integration (STI) can often improve the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

PACT '02: Proceedings of the 2002 International Conference on Parallel Architectures and Compilation Techniques

September 2002

168 pages

ISBN:0769516203

Publisher

IEEE Computer Society

United States

Publication History

Published: 22 September 2002

Check for updates

Qualifiers

Article

Conference

PACT02

Sponsor:

SIGARCH

PACT02: Parallel Architectures and Compilation Techniques

September 22 - 25, 2002

Acceptance Rates

Overall Acceptance Rate 121 of 471 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Zuck LPnueli AGoldberg BBarrett CFang YHu Y(2018)Translation and Run-Time Validation of Loop TransformationsFormal Methods in System Design10.1007/s10703-005-3402-z27:3(335-360)Online publication date: 29-Dec-2018
https://dl.acm.org/doi/10.1007/s10703-005-3402-z
Goldberg B(2010)Translation validation of loop optimizations and software pipelining in the TVOC frameworkProceedings of the 17th international conference on Static analysis10.5555/1882094.1882097(6-21)Online publication date: 14-Sep-2010
https://dl.acm.org/doi/10.5555/1882094.1882097
Tristan JLeroy X(2010)A simple, verified validator for software pipeliningACM SIGPLAN Notices10.1145/1707801.170631145:1(83-92)Online publication date: 17-Jan-2010
https://dl.acm.org/doi/10.1145/1707801.1706311
Tristan JLeroy XHermenegildo MPalsberg J(2010)A simple, verified validator for software pipeliningProceedings of the 37th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages10.1145/1706299.1706311(83-92)Online publication date: 17-Jan-2010
https://dl.acm.org/doi/10.1145/1706299.1706311

Abstract

References

Cited By

Recommendations

Software pipelining: an effective scheduling technique for VLIW machines

Software Pipelining of Nested Loops

Complementing software pipelining with software thread integration

Comments

Information

Published In

Sponsors

Publisher

Publication History

Check for updates

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations