[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.5555/774861.774871acmconferencesArticle/Chapter ViewAbstractPublication PagesmicroConference Proceedingsconference-collections
Article

Master/slave speculative parallelization

Published: 18 November 2002 Publication History

Abstract

Master/Slave Speculative Parallelization (MSSP) is an execution paradigm for improving the execution rate of sequential programs by parallelizing them speculatively for execution on a multiprocessor. In MSSP, one processor---the master---executes an approximate version of the program to compute selected values that the full program's execution is expected to compute. The master's results are checked by slave processors that execute the original program. This validation is parallelized by cutting the program's execution into tasks. Each slave uses its predicted inputs (as computed by the master) to validate the input predictions of the next task, inductively validating the entire execution.The performance of MSSP is largely determined by the execution rate of the approximate program. Since approximate code has no correctness requirements (in essence it is a software value predictor), it can be optimized more effectively than traditionally generated code. It is free to sacrifice correctness in the uncommon case to maximize performance in the common case.A simulation-based evaluation of an initial MSSP implementation achieves speedups of up to 1.7 (harmonic mean 1.25) on the SPEC2000 integer benchmarks. Performance is currently limited by the effectiveness with which our current automated infrastructure approximates programs, which can likely be improved significantly.

References

[1]
H. Akkary and M. Driscoll. A Dynamic Multithreading Processor. Micro-31, Nov. 1998.
[2]
T. Austin. DIVA: A Reliable Substrate for Deep Submicron Microarchitecture Design. Micro-32, Nov. 1999.
[3]
V. Bala, E. Duesterwald, and S. Banerjia. Transparent Dynamic Optimization. Technical Report HPL-1999-77, Hewlett Packard Labs, June 1999.
[4]
D. Burger and T. Austin. The SimpleScalar Tool Set, Version 2.0. Technical Report CS-TR-1997-1342, Computer Sciences Department, University of Wisconsin--Madison, 1997.
[5]
B. Calder, P. Feller, and A. Eustace. Value Profiling and Optimization. Journal of lnstruction Level Parallelism, Mar. 1999.
[6]
M. Cintra, J. Martinez, and J. Torrellas. Architectural Support for Scalable Speculative Parallelization in Shared-Memory Systems. ISCA-27, June 2000.
[7]
J. Collins, et al. Speculative precomputation: Long-range prefetching of delinquent loads. ISCA-28, July 2001.
[8]
P. Dubey, et al. Single-Program Speculative Multithreading (SPSM) Architecture: Compiler-Assisted Fine-Grained Multithreading. PACT, June 1995.
[9]
B. Fahs, et al. Performance Characterization of a Hardware Framework for Dynamic Optimization. Micro-34, Dec. 2001.
[10]
J. Fisher. Trace scheduling: a technique for global microcode compaction. IEEE Transactions on Computers, 30(7):478--490, 1981.
[11]
D. Gallagher, et al. Dynamic memory disambiguation using the memory conflict buffer. ASPLOS-6, Oct. 1994.
[12]
L. Hammond, M. Willey, and K. Olukotun. Data Speculation Support for a Chip Multiprocessor. ASPLOS-8, Oct. 1998.
[13]
W. M. Hwu, et al. The Superblock: An Effective Technique for VLIW and Superscalar Compilation. Journal of Supercomputing, 7(1 ):229--248, Mar 1993.
[14]
R. Kessler. The Alpha 21264 Microprocessor. IEEE Micro, 19(2):24--36, March/April 1999.
[15]
P. Marcuello, J. Tubella, and A. Gonzalez. Value Prediction for Speculative Multithreaded Architectures. Micro-32, Nov. 1999.
[16]
J. Oplinger, D. Heine, and M. Lam. In Search of Speculative Thread-Level Parallelism. PACT, Oct. 1999.
[17]
E. Rotenberg, et al. Trace Processors. Micro-30, Dec. 1997.
[18]
A. Roth and G. Sohi. Speculative Data-Driven Multi-Threading. HPCA-7, Jan. 2001.
[19]
A. Sodani and G. Sohi. Dynamic Instruction Reuse. ISCA-24, June 1997.
[20]
G. Sohi, S. Breach, and T. Vijaykumar. Multiscalar Processors. ISCA-22, June 1995.
[21]
J. Steffan, et al. Improving Value Communication for Thread-Level Speculation. HPCA-6, Jan. 2000.
[22]
K. Sundaramoorthy, Z. Purser, and E. Rotenberg. Slipstream Processors: Improving both Performance and Fault Tolerance. ASPLOS-9, Nov. 2000.
[23]
J.-Y. Tsai and P.-C. Yew. The Superthreaded Architecture: Thread Pipelining with Run-Time Data Dependence Checking and Control Speculation. PACT, Oct. 1996.
[24]
C. Zilles. Master/Slave Speculative Parallelization and Approximate Code. PhD thesis, Computer Sciences Department, University of Wisconsin--Madison, Aug. 2002.
[25]
C. Zilles and G. Sohi. Execution-based Prediction Using Speculative Slices. ISCA-28, July 2001.

Cited By

View all
  • (2019)CoNDAProceedings of the 46th International Symposium on Computer Architecture10.1145/3307650.3322266(629-642)Online publication date: 22-Jun-2019
  • (2018)Automatic Parallelization for Binary on Multi-core PlatformsProceedings of the 2nd International Conference on Computer Science and Application Engineering10.1145/3207677.3277982(1-6)Online publication date: 22-Oct-2018
  • (2018)A Case for a More Effective, Power-Efficient Turbo BoostingACM Transactions on Architecture and Code Optimization10.1145/317043315:1(1-22)Online publication date: 22-Mar-2018
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
MICRO 35: Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture
November 2002
442 pages
ISBN:0769518591

Sponsors

Publisher

IEEE Computer Society Press

Washington, DC, United States

Publication History

Published: 18 November 2002

Check for updates

Qualifiers

  • Article

Conference

Micro-35
Sponsor:

Acceptance Rates

Overall Acceptance Rate 484 of 2,242 submissions, 22%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)0
Reflects downloads up to 11 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2019)CoNDAProceedings of the 46th International Symposium on Computer Architecture10.1145/3307650.3322266(629-642)Online publication date: 22-Jun-2019
  • (2018)Automatic Parallelization for Binary on Multi-core PlatformsProceedings of the 2nd International Conference on Computer Science and Application Engineering10.1145/3207677.3277982(1-6)Online publication date: 22-Oct-2018
  • (2018)A Case for a More Effective, Power-Efficient Turbo BoostingACM Transactions on Architecture and Code Optimization10.1145/317043315:1(1-22)Online publication date: 22-Mar-2018
  • (2018)Software Speculation on Caching DSMsInternational Journal of Parallel Programming10.1007/s10766-017-0499-946:2(313-332)Online publication date: 1-Apr-2018
  • (2017)Towards Practical Default-On Multi-Core Record/ReplayACM SIGARCH Computer Architecture News10.1145/3093337.303775145:1(693-708)Online publication date: 4-Apr-2017
  • (2017)Towards Practical Default-On Multi-Core Record/ReplayACM SIGPLAN Notices10.1145/3093336.303775152:4(693-708)Online publication date: 4-Apr-2017
  • (2017)Towards Practical Default-On Multi-Core Record/ReplayProceedings of the Twenty-Second International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3037697.3037751(693-708)Online publication date: 4-Apr-2017
  • (2017)A speculative parallel decompression algorithm on Apache SparkThe Journal of Supercomputing10.1007/s11227-017-2000-373:9(4082-4111)Online publication date: 1-Sep-2017
  • (2016)A Survey on Thread-Level Speculation TechniquesACM Computing Surveys10.1145/293836949:2(1-39)Online publication date: 30-Jun-2016
  • (2014)Parallelization of RNA secondary structure prediction algorithm on multicoreProceedings of the 7th ACM India Computing Conference10.1145/2675744.2675765(1-6)Online publication date: 9-Oct-2014
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media