More Web Proxy on the site http://driver.im/

Article

A fast approximate interprocedural analysis for speculative multithreading compilers

Authors:

Anasua Bhowmik,

Manoj FranklinAuthors Info & Claims

ICS '03: Proceedings of the 17th annual international conference on Supercomputing

Pages 32 - 41

https://doi.org/10.1145/782814.782822

Published: 23 June 2003 Publication History

Abstract

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 data dependences as precisely as possible. Interprocedural points-to and side-effects information is essential to accurately determine data dependences. Determining this information has been an Achilles' heel in SpMT compilation. Existing interprocedural analyses are unsuitable for large programs, as they have high complexity or generate imprecise (very conservative) information that is not useful for aggressive speculative parallelization.This paper presents a novel interprocedural analysis scheme that is highly effective for use in SpMT compilers. It has running time and memory requirement almost linear in the number of procedures in the input program. The information it generates is comparable in accuracy with those generated by highly accurate context-sensitive interprocedural analyses, although it does not guarantee safe information (which is not a requirement for SpMT compilers any way). We implemented this interprocedural analysis in our SpMT compiler, and parallelized large non-numeric programs from the SPEC 2000 suite. Parallel execution of these threads in an SpMT simulator demonstrate good speedups for these non-numeric programs.

References

[1]

H. Akkary and M. A. Driscoll. "A Dynamic Multithreading Processor," in Proc. Intl. Symp. on Microarchitecture, 1998.

Digital Library

[2]

A. Bhowmik and M. Franklin. "A General Compiler Framework for Speculative Multithreading," in Proc. ACM Symp. on Parallel Algorithms and Architectures, 2002.

Digital Library

[3]

A. Bhowmik. "A General Compiler Framework for Speculative Multithreaded Processors," PhD. Thesis, Computer Science Department, University of Maryland, College Park, 2003.

Digital Library

[4]

D. R. Chase, M. Wegman, and F. K. Zadeck. "Analysis of Pointers and Structures," in Proc. Conf. on Programming Language Design and Implementation, 1990.

Digital Library

[5]

J-D. Choi, M. Burke, and P. Carini. "Efficient Flow-Sensitive Interprocedural Computation of Pointer-Induced Aliases and Side-Effects," in Proc. Symp. on Principles of Programming Languages, 1993.

Digital Library

[6]

M. Emami. "A Practical Interprocedural Alias Analysis For an Optimizing/Parallelizing C Compiler," Masters Thesis, School of Computer Science, McGill University, 1993.

[7]

M. Emami, R. Ghiya and L. J. Hendren. "Context-Sensitive Interprocedural Points-to Analysis in Presence of Function Pointers," in Proc. Conf. on Programming Language Design and Implementation, 1994.

Digital Library

[8]

M. Franklin. "Multiscalar Processors," Kluwer Academic Publishers, 2002.

Digital Library

[9]

L. Hammond, M. Willey and K. Olukotun. "Data Speculation Support for a Chip Multiprocessor," in Proc. Conf. on Architectural Support for Programming Languages and Operating Systems, 1998.

Digital Library

[10]

R. Hasti and S. Horwitz. "Using Static Single Assignment Form to Improve Flow-Insensitive Pointer Analysis," in Proc. Conf. on Programming Language Design and Implementation, 1998.

Digital Library

[11]

W. Landi and B. G. Ryder. "A Safe Approximate Algorithm for Interprocedural Pointer Aliasing," in Proc. Conf. on Programming Language Design and Implementation, 1992.

Digital Library

[12]

W. Landi, B. G. Ryder, and S Zhang. "Interprocedural Modification Side-Effect Analysis with Pointer Aliasing," in Proc. Conf. on Programming Language Design and Implementation, 1993.

Digital Library

[13]

P. Marcuello and A. Gonzalez. "Clustered Speculative Multithreaded Processors," in Proc. ACM Int'l Conf. on Supercomputing, 1999.

Digital Library

[14]

K. Olukotun, L. Hammond, and M. Willey. "Improving the Performance of Speculatively Parallel Applications on the Hydra CMP," in Proc. ACM Int'l Conf. on Supercomputing, 1999.

Digital Library

[15]

E. Ruf. "Context-Insensitive Alias Analysis Reconsidered," in Proc. Conf. on Programming Language Design and Implementation, 1995.

Digital Library

[16]

M. Shapiro and S. Horwitz. "Fast and Accurate Flow-Insensitive Points-To Analysis," in Proc. Symp. on Principles of Programming Languages, 1997.

Digital Library

[17]

B. Steensgard. "Points-to Analysis in Almost Linear Time," in Proc. Symp. on Principles of Programming Languages, 1996.

Digital Library

[18]

J. G. Steffan and T. Mowry. "The Potential for Using Thread-Level Data Speculation to Facilitate Automatic Parallelization," in Proc. Int'l Symp. on High-Performance Computer Architecture, 1998.

Digital Library

[19]

J-Y. Tsai and P-C. Yew. "The Superthreaded Architecture: Thread Pipelining with Run-Time Data Dependence Checking and Control Speculation," in Proc. Int'l Conf. on Parallel Architectures and Compilation Techniques, 1996.

Digital Library

[20]

J.-Y. Tsai, Z. Jiang, Z. Li, D. J. Lilja, X. Wang, P.-C. Yew, B. Zheng, and S. Schwinn. "Integrating Compilation Technology and Processor Architecture for Cost-Effective Concurrent Multithreading," in Journal of Information Science and Engineering, March 1998.

[21]

T. N. Vijaykumar and G. S. Sohi. "Task Selection for a Multiscalar Processor," in Proc. Int'l Symp. on Microarchitecture, 1998.

Digital Library

[22]

R. Wilson, R. French, C. Wilson, S. Amarsinghe, J. Anderson, S. Tjiang, S. Liao, C.-W. Tseng, M. Hall, M. Lam, and J. Hennesy. "SUIF: An Infrastructure for Research on Parallelizing and Optimizing Compiler," ACM SIGPLAN Notices, Vol. 29, No. 12, December 1996.

Digital Library

[23]

R. P. Wilson and M. S. Lam. "Efficient Context-Sensitive Pointer Analysis for C Programs," in Proc. Conf. on Programming Language Design and Implementation, 1995.

Digital Library

Cited By

Chen MYe JChen TDai H(2017)Shared write buffer to boost applications on SpMT architectureThe Journal of Supercomputing10.1007/s11227-016-1710-273:8(3508-3525)Online publication date: 1-Aug-2017
https://dl.acm.org/doi/10.1007/s11227-016-1710-2
Ye JDai HLi SChen T(2015)Shared Write Buffer to Support Speculative ExecutionProceedings of the 2015 IEEE 17th International Conference on High Performance Computing and Communications, 2015 IEEE 7th International Symposium on Cyberspace Safety and Security, and 2015 IEEE 12th International Conf on Embedded Software and Systems10.1109/HPCC-CSS-ICESS.2015.310(1494-1499)Online publication date: 24-Aug-2015
https://dl.acm.org/doi/10.1109/HPCC-CSS-ICESS.2015.310
Ye JLi SChen T(2015)Shared Write Buffer to Support Data Sharing Among Speculative Multi-threading CoresProceedings of the 2015 IEEE 17th International Conference on High Performance Computing and Communications, 2015 IEEE 7th International Symposium on Cyberspace Safety and Security, and 2015 IEEE 12th International Conf on Embedded Software and Systems10.1109/HPCC-CSS-ICESS.2015.287(835-838)Online publication date: 24-Aug-2015
https://dl.acm.org/doi/10.1109/HPCC-CSS-ICESS.2015.287
Show More Cited By

Index Terms

A fast approximate interprocedural analysis for speculative multithreading compilers
1. Computer systems organization
  1. Architectures
    1. Parallel architectures
2. Software and its engineering
  1. Software notations and tools
    1. Compilers

Recommendations

A general compiler framework for speculative multithreading
SPAA '02: Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures

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 ...
Interprocedural pointer alias analysis

We present practical approximation methods for computing and representing interprocedural aliases for a program written in a language that includes pointers, reference parameters, and recursion. We present the following contributions: (1) a framework ...
Interprocedural Pointer Analysis in Goanna

Goanna is an industrial-strength static analysis tool used in academia and industry alike to find bugs in C/C++ programs. Unlike existing approaches, Goanna uses the off-the-shelf model checker NuSMV as its core analysis engine on a syntactic flow-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ICS '03: Proceedings of the 17th annual international conference on Supercomputing

June 2003

380 pages

ISBN:1581137338

DOI:10.1145/782814

General Chair:
Utpal Banerjee
Intel Corporation
,
Program Chairs:
Kyle A. Gallivan
Florida State University
,
Antonio Gonzalez
Intel Labs & Univ. Politècnica de Catalunya

Copyright © 2003 ACM.

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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 June 2003

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ICS03

Sponsor:

ICS03: International Conference on Supercomputing 2003

June 23 - 26, 2003

CA, San Francisco, USA

Acceptance Rates

ICS '03 Paper Acceptance Rate 36 of 171 submissions, 21%;

Overall Acceptance Rate 629 of 2,180 submissions, 29%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
484
Total Downloads

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

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chen MYe JChen TDai H(2017)Shared write buffer to boost applications on SpMT architectureThe Journal of Supercomputing10.1007/s11227-016-1710-273:8(3508-3525)Online publication date: 1-Aug-2017
https://dl.acm.org/doi/10.1007/s11227-016-1710-2
Ye JDai HLi SChen T(2015)Shared Write Buffer to Support Speculative ExecutionProceedings of the 2015 IEEE 17th International Conference on High Performance Computing and Communications, 2015 IEEE 7th International Symposium on Cyberspace Safety and Security, and 2015 IEEE 12th International Conf on Embedded Software and Systems10.1109/HPCC-CSS-ICESS.2015.310(1494-1499)Online publication date: 24-Aug-2015
https://dl.acm.org/doi/10.1109/HPCC-CSS-ICESS.2015.310
Ye JLi SChen T(2015)Shared Write Buffer to Support Data Sharing Among Speculative Multi-threading CoresProceedings of the 2015 IEEE 17th International Conference on High Performance Computing and Communications, 2015 IEEE 7th International Symposium on Cyberspace Safety and Security, and 2015 IEEE 12th International Conf on Embedded Software and Systems10.1109/HPCC-CSS-ICESS.2015.287(835-838)Online publication date: 24-Aug-2015
https://dl.acm.org/doi/10.1109/HPCC-CSS-ICESS.2015.287
Wang XZhao YWei YSong SHan B(2010)Prophet Synchronization Thread Model and Compiler SupportProceedings of the International Symposium on Parallel and Distributed Processing with Applications10.1109/ISPA.2010.83(81-87)Online publication date: 6-Sep-2010
https://dl.acm.org/doi/10.1109/ISPA.2010.83
Wang SZhai AYew P(2006)Exploiting speculative thread-level parallelism in data compression applicationsProceedings of the 19th international conference on Languages and compilers for parallel computing10.5555/1757112.1757126(126-140)Online publication date: 2-Nov-2006
https://dl.acm.org/doi/10.5555/1757112.1757126
Da Silva JSteffan J(2006)A probabilistic pointer analysis for speculative optimizationsACM SIGARCH Computer Architecture News10.1145/1168919.116890834:5(416-425)Online publication date: 20-Oct-2006
https://dl.acm.org/doi/10.1145/1168919.1168908
Da Silva JSteffan J(2006)A probabilistic pointer analysis for speculative optimizationsACM SIGPLAN Notices10.1145/1168918.116890841:11(416-425)Online publication date: 20-Oct-2006
https://dl.acm.org/doi/10.1145/1168918.1168908
Da Silva JSteffan J(2006)A probabilistic pointer analysis for speculative optimizationsACM SIGOPS Operating Systems Review10.1145/1168917.116890840:5(416-425)Online publication date: 20-Oct-2006
https://dl.acm.org/doi/10.1145/1168917.1168908
Da Silva JSteffan JShen JMartonosi M(2006)A probabilistic pointer analysis for speculative optimizationsProceedings of the 12th international conference on Architectural support for programming languages and operating systems10.1145/1168857.1168908(416-425)Online publication date: 23-Oct-2006
https://dl.acm.org/doi/10.1145/1168857.1168908
Zhai AColohan CSteffan JMowry T(2004)Compiler Optimization of Memory-Resident Value Communication Between Speculative ThreadsProceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization10.5555/977395.977667Online publication date: 20-Mar-2004
https://dl.acm.org/doi/10.5555/977395.977667
Show More Cited By

View Options

Login options

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

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents