Article

A general compiler framework for speculative multithreading

Authors:

Anasua Bhowmik,

Manoj FranklinAuthors Info & Claims

SPAA '02: Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures

Pages 99 - 108

https://doi.org/10.1145/564870.564885

Published: 10 August 2002 Publication History

Get Access

Abstract

Speculative multithreading (SpMT) promises to be an effective mechanism for parallelizing non-numeric programs, which tend to use irregular data structures with pointers and have complex flows of control. Proper thread formation is crucial to obtaining good speedup in an SpMT system. This paper presents a compiler framework for partitioning a sequential program into multiple threads for parallel execution in an SpMT system. This framework is very general, and supports a wide variety of threads, such as speculative threads, non-speculative threads, loop-centric threads, and out-of-order thread spawning. The compiler uses profiling, intra-procedural pointer analysis, data dependence information and control dependence information. The compiler is implemented on the SUIF-MachSUIF platform. A simulation-based evaluation of the generated threads shows that an average speedup of 3 can be obtained with 6 processing elements for non-numeric programs. This speedup reduces to 2 if we use only loop-based threads.

References

[1]

A. Aho, R. Sethi, and J. Ullman,"Compilers: Principles, Techniques, and Tools", Addison-Wesley, Reading, MA, 1986.

Digital Library

Google Scholar

[2]

R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and F. Zadeck, "Efficiently computing static single assign-ment form and the control dependency graph", ACM Trans. Program. Lang. Syst., 13(4), October 1991.

Digital Library

Google Scholar

[3]

P. Dubey, K. O'Brien, K. M. O'Brien, and C. Barton, "Single-Program Speculative Multithreading (SPSM) Architecture: Compiler-assisted Fine-Grained Multi-threading", Proc. Int'l Conf. on Parallel Architecture and Compilation Techniques (PACT '95).

Digital Library

Google Scholar

[4]

M. Franklin and G. Sohi, "ARB: A Hardware Mechanism for Dynamic Reordering of Memory References", IEEE Transactions on Computers, Vol. 45, No. 5, pp. 552--571, May 1996.

Digital Library

Google Scholar

[5]

M. W. Hall, J. M. Anderson, S. P. Amarasinghe, B. R. Murphy, S. W. Liao, E. Bugnion, and M. S. Lam, "Maximizing Multiprocessor Performance with the SUIF Compiler", IEEE Computer, December 1996.

Digital Library

Google Scholar

[6]

W. W. Hwu, R. E. Hank,D. M. Gallagher, S. A. Mahlke, D. M. Lavery, G. E. Haab, J. C. Gyllenhaal, and D. I. August, "Compiler Technology for Future Microprocessors", Proc.IEEE, 83(12):1625--1640, December 1995.

Crossref

Google Scholar

[7]

S. Jayashree and S. Vajapeyam, "Exploiting Parallelism across Basic Blocks via Decoupled Control Flow", Technical Report TR No. IISc-CSA-95-01, Dept. of Computer Science and Automation, Indian Institute of Science, March, 1995.

Google Scholar

[8]

D. Naishlos, J. Nujman, C.-W. Tseng and U. Vishkin, "Evaluating Multithreading in Prototype XMT Environment", Proc. Workshop on Multi-Threaded Execution, Architecture and Compilation (MTEAC-2000).

Google Scholar

[9]

K. Olukotun, et al. "A Chip-Multiprocessor Architecture with Speculative Multithreading", IEEE Transac-tions on Computers, September 1999.

Digital Library

Google Scholar

[10]

M. D. Smith and G. Holloway, "An Introduction to Machine SUIF and Its Portable Libraries for

Google Scholar

[11]

X. Tang, "Compiling For Multithread Architectures", Ph.D. Thesis, Dept. of Electrical Eng., Univ. of Dela-ware, 1999.

Digital Library

Google Scholar

[12]

J-Y. Tsai and P-C. Yew. "The Superthreaded Architecture: ThreadPipelining with Run-Time Data Dependence Checking and Control Speculation", Proc. Int'l Conf. on Parallel Architectures and Compilation Techniques (PACT '96).

Digital Library

Google Scholar

[13]

T. N. Vijaykumar and G. S. Sohi. "Task Selection for a Multiscalar Processor", Proc. 31st Int'l Symposium on Microarchitecture (MICRO-31), 1998.

Digital Library

Google Scholar

[14]

K. Wang and M. Franklin, "Highly Accurate Data Value Prediction using Hybrid Predictors", Proc. Int'l Symposium on Microarchitecture (MICRO-30), 1997.

Digital Library

Google Scholar

Cited By

View all

Gorius JRokicki SDerrien SRodríguez GSadayappan PSukumaran-Rajam A(2024)A Unified Memory Dependency Framework for Speculative High-Level SynthesisProceedings of the 33rd ACM SIGPLAN International Conference on Compiler Construction10.1145/3640537.3641581(13-25)Online publication date: 17-Feb-2024
https://dl.acm.org/doi/10.1145/3640537.3641581
Yuxiang LZhiyong ZXinyong WShuaina HYaning S(2024)IDaTPA: importance degree based thread partitioning approach in thread level speculationDiscover Computing10.1007/s10791-024-09440-x27:1Online publication date: 19-Jun-2024
https://doi.org/10.1007/s10791-024-09440-x
Chen LZhu JDeng YLi ZChen JJiang XYin SWei SLiu L(2021)An Elastic Task Scheduling Scheme on Coarse-Grained Reconfigurable ArchitecturesIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2021.308480432:12(3066-3080)Online publication date: 1-Dec-2021
https://doi.org/10.1109/TPDS.2021.3084804
Show More Cited By

Index Terms

A general compiler framework for speculative multithreading
1. Computer systems organization
  1. Architectures
    1. Parallel architectures
2. Software and its engineering
  1. Software notations and tools
    1. Compilers

Recommendations

A fast approximate interprocedural analysis for speculative multithreading compilers
ICS '03: Proceedings of the 17th annual international conference on Supercomputing

Speculative multithreading (SpMT) promises to be very effective for parallelizing non-numeric programs. Data dependences are perhaps the most important factor in the crucial step of deciding the thread boundaries, and SpMT compilers need to estimate ...
Exploiting Data Value Prediction in Compiler Based Thread Formation
HiPC '02: Proceedings of the 9th International Conference on High Performance Computing

Speculative multithreading (SpMT) is an effective execution model for parallelizing non-numeric programs, which tend to use irregular and pointer-intensive data structures, and have complex flows of control. An SpMT compiler performs program ...
On the performance potential of different types of speculative thread-level parallelism: The DL version of this paper includes corrections that were not made available in the printed proceedings
ICS '06: Proceedings of the 20th annual international conference on Supercomputing

Recent research in thread-level speculation (TLS) has proposed several mechanisms for optimistic execution of difficult-to-analyze serial codes in parallel. Though it has been shown that TLS helps to achieve higher levels of parallelism, evaluation of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SPAA '02: Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures

August 2002

302 pages

ISBN:1581135297

DOI:10.1145/564870

Conference Chair:
Arnold Rosenberg
University of Massachusetts
,
Program Chair:
Bruce Maggs
Carnegie Mellon University

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 August 2002

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SPAA02

Sponsor:

SPAA02: Fourteenth ACM Symposium on Parallelism in Algorithms and Architectures

August 10 - 13, 2002

Manitoba, Winnipeg, Canada

Acceptance Rates

Overall Acceptance Rate 447 of 1,461 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

53
Total Citations
View Citations
929
Total Downloads

Downloads (Last 12 months)11
Downloads (Last 6 weeks)1

Reflects downloads up to 28 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Gorius JRokicki SDerrien SRodríguez GSadayappan PSukumaran-Rajam A(2024)A Unified Memory Dependency Framework for Speculative High-Level SynthesisProceedings of the 33rd ACM SIGPLAN International Conference on Compiler Construction10.1145/3640537.3641581(13-25)Online publication date: 17-Feb-2024
https://dl.acm.org/doi/10.1145/3640537.3641581
Yuxiang LZhiyong ZXinyong WShuaina HYaning S(2024)IDaTPA: importance degree based thread partitioning approach in thread level speculationDiscover Computing10.1007/s10791-024-09440-x27:1Online publication date: 19-Jun-2024
https://doi.org/10.1007/s10791-024-09440-x
Chen LZhu JDeng YLi ZChen JJiang XYin SWei SLiu L(2021)An Elastic Task Scheduling Scheme on Coarse-Grained Reconfigurable ArchitecturesIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2021.308480432:12(3066-3080)Online publication date: 1-Dec-2021
https://doi.org/10.1109/TPDS.2021.3084804
Ying VJeffrey MSanchez D(2020)T4: Compiling Sequential Code for Effective Speculative Parallelization in Hardware2020 ACM/IEEE 47th Annual International Symposium on Computer Architecture (ISCA)10.1109/ISCA45697.2020.00024(159-172)Online publication date: May-2020
https://doi.org/10.1109/ISCA45697.2020.00024
Saad MKishi MJing SHans SPalmieri RHollingsworth JKeidar I(2019)Processing transactions in a predefined orderProceedings of the 24th Symposium on Principles and Practice of Parallel Programming10.1145/3293883.3295730(120-132)Online publication date: 16-Feb-2019
https://dl.acm.org/doi/10.1145/3293883.3295730
Li YNiu DZhang ZZhang L(2019)TPAoPI:A Thread Partitioning Approach Based on Procedure Importance in Speculative Multithreading2019 IEEE 21st International Conference on High Performance Computing and Communications; IEEE 17th International Conference on Smart City; IEEE 5th International Conference on Data Science and Systems (HPCC/SmartCity/DSS)10.1109/HPCC/SmartCity/DSS.2019.00325(2339-2344)Online publication date: Aug-2019
https://doi.org/10.1109/HPCC/SmartCity/DSS.2019.00325
Yan XJoa AWong BCassell BSzepesi TNaouach MLam DPierre GFerreira PShrira L(2018)SpecRPCProceedings of the 19th International Middleware Conference10.1145/3274808.3274829(266-278)Online publication date: 26-Nov-2018
https://dl.acm.org/doi/10.1145/3274808.3274829
Li YZhao YLiu B(2017)Qinling: A Parametric Model in Speculative MultithreadingSymmetry10.3390/sym90901809:9(180)Online publication date: 2-Sep-2017
https://doi.org/10.3390/sym9090180
Li YZhao YSun LShen M(2017)A hybrid sample generation approach in speculative multithreadingThe Journal of Supercomputing10.1007/s11227-017-2118-3Online publication date: 7-Aug-2017
https://doi.org/10.1007/s11227-017-2118-3
Li YZhao YWu Q(2017)GbA: A graph‐based thread partition approach in speculative multithreadingConcurrency and Computation: Practice and Experience10.1002/cpe.429429:21Online publication date: 4-Oct-2017
https://doi.org/10.1002/cpe.4294
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

A fast approximate interprocedural analysis for speculative multithreading compilers

Exploiting Data Value Prediction in Compiler Based Thread Formation

On the performance potential of different types of speculative thread-level parallelism: The DL version of this paper includes corrections that were not made available in the printed proceedings