Article

Mitosis compiler: an infrastructure for speculative threading based on pre-computation slices

Authors:

Carlos García Quiñones,

Carlos Madriles,

Jesús Sánchez,

Pedro Marcuello,

Antonio González,

Dean M. TullsenAuthors Info & Claims

PLDI '05: Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation

Pages 269 - 279

https://doi.org/10.1145/1065010.1065043

Published: 12 June 2005 Publication History

Abstract

Speculative parallelization can provide significant sources of additional thread-level parallelism, especially for irregular applications that are hard to parallelize by conventional approaches. In this paper, we present the Mitosis compiler, which partitions applications into speculative threads, with special emphasis on applications for which conventional parallelizing approaches fail.The management of inter-thread data dependences is crucial for the performance of the system. The Mitosis framework uses a pure software approach to predict/compute the thread's input values. This software approach is based on the use of pre-computation slices (p-slices), which are built by the Mitosis compiler and added at the beginning of the speculative thread. P-slices must compute thread input values accurately but they do not need to guarantee correctness, since the underlying architecture can detect and recover from misspeculations. This allows the compiler to use aggressive/unsafe optimizations to significantly reduce their overhead. The most important optimizations included in the Mitosis compiler and presented in this paper are branch pruning, memory and register dependence speculation, and early thread squashing.Performance evaluation of Mitosis compiler/architecture shows an average speedup of 2.2.

References

[1]

H. Akkary and M.A. Driscoll, "A Dynamic Multithreading Processor", in Proc. of the 31st Int. Symp. on Microarchitecture, 1998

Digital Library

[2]

M. Cintra, J.F. Martinez and J. Torrellas, "Architectural Support for Scalable Speculative Parallelization in Shared-Memory Systems", in Proc. of the 27th Int. Symp. on Computer Architecture, 2000

Digital Library

[3]

M. Cintra and J.Torrellas, "Eliminating Squashes through Learning Cross-thread Violations in Speculative Parallelization for Multiprocessors", in Proc. of the 8th Int. Symp. on High Performance Computer Architecture, 2002

Digital Library

[4]

L. Codrescu and D. Wills, "On Dynamic Speculative Thread Partitioning and the MEM-Slicing Algorithm", in Proc. of the Int. Conf. on Parallel Architectures and Compilation Techniques, pp. 40--46, 1999

Digital Library

[5]

J.D. Collins, H. Wang, D.M. Tullsen, C. Hughes, Y-F. Lee, D. Lavery and J.P. Shen, "Speculative Precomputation: Long Range Prefetching of Delinquent Loads", in Proc. of the 28th Int. Symp. on Computer Architecture, 2001

Digital Library

[6]

R.S. Chapel, J. Stark, S.P. Kim, S.K. Reinhanrdt and Y.N. Patt, "Simultaneous Subordinate Microthreading (SSMT)", in Procs. of the 26th Int. Symp. on Computer Architecture, pp. 186--195, 1999

Digital Library

[7]

K. Diekendorff, "Compaq Chooses SMT for Alpha", Microprocessor Report, December, 1999

[8]

Z.-H. Du, C-Ch. Lim, X.-F. Li, Q. Zhao and T.-F. Ngai, "A Cost-Driven Compilation Framework for Speculative Parallelization of Sequential Programs", in Procs. of the Conf. on Programming Language Design and Implementation, June 2004

Digital Library

[9]

P.K. Dubey, K. O'Brien, K.M. O'Brien and C. Barton, "Single-Program Speculative Multithreading (SPSM) Architecture: Compiler-Assisted Fine-Grained Multithreading", in Proc. of the Int. Conf. on Parallel Architectures and Compilation Techniques, 1995

Digital Library

[10]

M. Franklin and G.S. Sohi, "The Expandable Split Window Paradigm for Exploiting Fine Grain Parallelism", in Proc. of the 19th Int. Symp. on Computer Architecture, 1992

Digital Library

[11]

R. Ju, S. Chan and C. Wu, "Open Research Compiler for the ItaniumTM Family", in Tutorial in the 34th Int. Symp. on Microarchitecture, 2001

[12]

C. Luk, "Tolerating Memory Latency through Software-Controlled Pre-Execution in Simultaneous Multithreading Processors", in Proc. of the 28th Int. Symp. on Computer Architecture, pp. 40--51, 2001

Digital Library

[13]

P, Marcuello and A. González, "Clustered Speculative Multithreaded Processors", in Proc. of the 13th Int. Conf. on Supercomputing, pp. 365--372, 1999

Digital Library

[14]

P. Marcuello, J. Tubella and A. González, "Value Prediction for Speculative Multithreaded Architectures", in Proc. of the 32nd. Int. Conf,. on Microarchitecture, pp. 203--236., 1999

Digital Library

[15]

P. Marcuello and A. González, "Thread-Spawning Schemes for Speculative Multithreaded Architectures", in Proc. of the 8th Int. Symp, on High Performance Computer Architectures, 2002

Digital Library

[16]

T. Marr et al., "Hyper-threading Technology Architecture and Microarchtiecture", Intel technology Journal, 6(1), 2002

[17]

J. Oplinger et. al., "Software and Hardware for Exploiting Speculative Parallelism in Multiprocessors", Technical Report CSL-TR-97-715, Stanford University, 1997

Digital Library

[18]

Roth and G.S. Sohi, "Speculative Data-Driven Multithreading", in Proc. of the 7th. Int. Symp. On High Performance Computer Architecture, pp. 37--48, 2001

Digital Library

[19]

G.S. Sohi, S.E. Breach and T.N. Vijaykumar, "Multiscalar Processors", in Proc. of the 22nd Int. Symp. on Computer Architecture, pp.414--425, 1995

Digital Library

[20]

J. Steffan and T. Mowry, "The Potential of Using Thread-level Data Speculation to Facilitate Automatic Parallelization", in Proc. of the 4th Int. Symp. on High Performance Computer Architecture, pp. 2--13, 1998

Digital Library

[21]

J. Steffan, C. Colohan, A. Zhai and T. Mowry, "Improving Value Communication for Thread-Level Speculation", in Proc. of the 8th Int. Symp. on High Performance Computer Architecture, pp. 58--62, 1998

Digital Library

[22]

S. Storino an dJ. Borkenhagen, "A Multithreaded 64-bit PowerPC Commercial RISC Processor Design", in Proc. Of the 11th Int. Conf. on High Performance Chips, 1999

[23]

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

Digital Library

[24]

M. Tremblay et al., "The MAJC Architecture, a synthesis of of Parallelism and Scalability", IEEE Micro, 20(6), 2000

Digital Library

[25]

D. M. Tullsen, S.J. Eggers and H.M. Levy, "Simultaneous Multithreading: Maximizing On-Chip Parallelism", in Proc. of the 22nd Int. Symp. on Computer Architecture, pp. 392--403, 1995

Digital Library

[26]

T.N. Vijaykumar, "Compiling for the Multiscalar Architecture", Ph.D. Thesis, Univ. of Wisconsin-Madison, 1998

Digital Library

[27]

C.B. Zilles and G.S. Sohi, "Execution-Based Prediction Using Speculative Slices", in Proc. of the 28th Int. Symp. on Computer Architecture, 2001

Digital Library

[28]

C.B. Zilles and G.S. Sohi, "Master/Slave Speculative Parallelization", in Proc. of the 35th Int. Symp. on Microarchitecture, 2002.

Digital Library

Cited By

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
Ying VJeffrey MSanchez DMartínez JDuato JEeckhout L(2020)T4Proceedings of the ACM/IEEE 47th Annual International Symposium on Computer Architecture10.1109/ISCA45697.2020.00024(159-172)Online publication date: 30-May-2020
https://dl.acm.org/doi/10.1109/ISCA45697.2020.00024
Li YZhang ZZhang LNiu DZhao CSong BLiang L(2019)ProCTA: program characteristic-based thread partition approachThe Journal of Supercomputing10.1007/s11227-019-02943-1Online publication date: 3-Jul-2019
https://doi.org/10.1007/s11227-019-02943-1
Show More Cited By

Index Terms

Mitosis compiler: an infrastructure for speculative threading based on pre-computation slices
1. Computer systems organization
  1. Architectures
    1. Parallel architectures
2. Software and its engineering
  1. Software notations and tools
    1. Compilers
      1. Source code generation

Recommendations

Mitosis compiler: an infrastructure for speculative threading based on pre-computation slices
Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation

Speculative parallelization can provide significant sources of additional thread-level parallelism, especially for irregular applications that are hard to parallelize by conventional approaches. In this paper, we present the Mitosis compiler, which ...
Mitosis: A Speculative Multithreaded Processor Based on Precomputation Slices

This paper presents the Mitosis framework, which is a combined hardware-software approach to speculative multithreading, even in the presence of frequent dependences among threads. Speculative multithreading increases single-threaded application ...
Boosting single-thread performance in multi-core systems through fine-grain multi-threading

Industry has shifted towards multi-core designs as we have hit the memory and power walls. However, single thread performance remains of paramount importance since some applications have limited thread-level parallelism (TLP), and even a small part with ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PLDI '05: Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation

June 2005

338 pages

ISBN:1595930566

DOI:10.1145/1065010

General Chair:
Vivek Sarkar
IBM Research
,
Program Chair:
Mary Hall
USC/ISI

ACM SIGPLAN Notices Volume 40, Issue 6
Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation
June 2005
325 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/1064978
Issue’s Table of Contents

Copyright © 2005 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: 12 June 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

PLDI05

Sponsor:

PLDI05: ACM SIGPLAN Conference on Programming Language Design and Implementation 2005

June 12 - 15, 2005

IL, Chicago, USA

Acceptance Rates

Overall Acceptance Rate 406 of 2,067 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

139
Total Citations
View Citations
933
Total Downloads

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

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

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
Ying VJeffrey MSanchez DMartínez JDuato JEeckhout L(2020)T4Proceedings of the ACM/IEEE 47th Annual International Symposium on Computer Architecture10.1109/ISCA45697.2020.00024(159-172)Online publication date: 30-May-2020
https://dl.acm.org/doi/10.1109/ISCA45697.2020.00024
Li YZhang ZZhang LNiu DZhao CSong BLiang L(2019)ProCTA: program characteristic-based thread partition approachThe Journal of Supercomputing10.1007/s11227-019-02943-1Online publication date: 3-Jul-2019
https://doi.org/10.1007/s11227-019-02943-1
Tran KJimborean ACarlson TKoukos KSjälander MKaxiras S(2018)SWOOP: software-hardware co-design for non-speculative, execute-ahead, in-order coresACM SIGPLAN Notices10.1145/3296979.319239353:4(328-343)Online publication date: 11-Jun-2018
https://dl.acm.org/doi/10.1145/3296979.3192393
Tran KJimborean ACarlson TKoukos KSjälander MKaxiras SFoster JGrossman D(2018)SWOOP: software-hardware co-design for non-speculative, execute-ahead, in-order coresProceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3192366.3192393(328-343)Online publication date: 11-Jun-2018
https://dl.acm.org/doi/10.1145/3192366.3192393
Tran KCarlson TKoukos KSjälander MSpiliopoulos VKaxiras SJimborean AReddi VSmith ATang L(2017)Clairvoyance: look-ahead compile-time schedulingProceedings of the 2017 International Symposium on Code Generation and Optimization10.5555/3049832.3049852(171-184)Online publication date: 4-Feb-2017
https://dl.acm.org/doi/10.5555/3049832.3049852
Qiu JZhao ZWu BVishnu ASong SGropp WBeckman PLi ZCazorla F(2017)Enabling scalability-sensitive speculative parallelization for FSM computationsProceedings of the International Conference on Supercomputing10.1145/3079079.3079082(1-10)Online publication date: 14-Jun-2017
https://dl.acm.org/doi/10.1145/3079079.3079082
Oh TBeard SJohnson NPopovych SAugust D(2017)A Generalized Framework for Automatic Scripting Language Parallelization2017 26th International Conference on Parallel Architectures and Compilation Techniques (PACT)10.1109/PACT.2017.28(356-369)Online publication date: Sep-2017
https://doi.org/10.1109/PACT.2017.28
Kim CKim JKang JLee JKim H(2017)Context-Aware Memory Profiling for Speculative Parallelism2017 IEEE 24th International Conference on High Performance Computing (HiPC)10.1109/HiPC.2017.00045(328-337)Online publication date: Dec-2017
https://doi.org/10.1109/HiPC.2017.00045
Wang QWang JShen LWang Z(2017)A Software-Hardware Co-designed Methodology for Efficient Thread Level Speculation2017 IEEE International Conference on Computer and Information Technology (CIT)10.1109/CIT.2017.49(184-191)Online publication date: Aug-2017
https://doi.org/10.1109/CIT.2017.49
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