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

ACM SIGPLAN Notices, Volume 40, Issue 6

Pages 269 - 279

https://doi.org/10.1145/1064978.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

Martínez MFraguela BCabaleiro JRivera F(2024)A new thread-level speculative automatic parallelization model and library based on duplicate code executionThe Journal of Supercomputing10.1007/s11227-024-05987-080:10(13714-13737)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1007/s11227-024-05987-0
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
Kumar SSingh SAggarwal NGupta BAlhalabi WBand S(2022)An efficient hardware supported and parallelization architecture for intelligent systems to overcome speculative overheadsInternational Journal of Intelligent Systems10.1002/int.2306237:12(11764-11790)Online publication date: 8-Sep-2022
https://dl.acm.org/doi/10.1002/int.23062
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
PLDI '05: 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 SIGPLAN Notices

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

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

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 June 2005

Published in SIGPLAN Volume 40, Issue 6

Check for updates

Author Tags

Qualifiers

Article

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

Martínez MFraguela BCabaleiro JRivera F(2024)A new thread-level speculative automatic parallelization model and library based on duplicate code executionThe Journal of Supercomputing10.1007/s11227-024-05987-080:10(13714-13737)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1007/s11227-024-05987-0
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
Kumar SSingh SAggarwal NGupta BAlhalabi WBand S(2022)An efficient hardware supported and parallelization architecture for intelligent systems to overcome speculative overheadsInternational Journal of Intelligent Systems10.1002/int.2306237:12(11764-11790)Online publication date: 8-Sep-2022
https://dl.acm.org/doi/10.1002/int.23062
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
Li YZhao YSun LShen M(2019)A hybrid sample generation approach in speculative multithreadingThe Journal of Supercomputing10.1007/s11227-017-2118-375:8(4193-4225)Online publication date: 1-Aug-2019
https://dl.acm.org/doi/10.1007/s11227-017-2118-3
Li YZhang ZZhang LNiu D(2018)Thread-Level Speculation: Review and Perspectives2018 5th International Conference on Information Science and Control Engineering (ICISCE)10.1109/ICISCE.2018.00263(1291-1295)Online publication date: Jul-2018
https://doi.org/10.1109/ICISCE.2018.00263
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
Barbanera FLanese Ide’Liguoro U(2017)Retractable and Speculative ContractsCoordination Models and Languages10.1007/978-3-319-59746-1_7(119-137)Online publication date: 27-May-2017
https://doi.org/10.1007/978-3-319-59746-1_7
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
Li YZhao YWu Q(2016)A Graph-Based Thread Partition Approach in Speculative Multithreading2016 IEEE 18th International Conference on High Performance Computing and Communications; IEEE 14th International Conference on Smart City; IEEE 2nd International Conference on Data Science and Systems (HPCC/SmartCity/DSS)10.1109/HPCC-SmartCity-DSS.2016.0065(406-413)Online publication date: Dec-2016
https://doi.org/10.1109/HPCC-SmartCity-DSS.2016.0065
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 Issue’s Table of Contents