Login
Login

speculative multithreading

{{short description|Computer runtime parallelization technique}}

{{Multiple issues|

{{Update|date=March 2017 | inaccurate=yes}}

{{More footnotes needed|date=November 2018}}

}}

Thread Level Speculation (TLS), also known as Speculative Multi-threading, or Speculative Parallelization,{{Cite journal |last=Estebanez |first=Alvaro |date=2017 |title=A Survey on Thread-Level Speculation Techniques |url=https://dl.acm.org/doi/abs/10.1145/2938369 |journal=ACM Computing Surveys |volume=49 |issue=2 |pages=1–39|doi=10.1145/2938369 |s2cid=423292 |url-access=subscription }} is a technique to speculatively execute a section of computer code that is anticipated to be executed later in parallel with the normal execution on a separate independent thread. Such a speculative thread may need to make assumptions about the values of input variables. If these prove to be invalid, then the portions of the speculative thread that rely on these input variables will need to be discarded and squashed. If the assumptions are correct the program can complete in a shorter time provided the thread was able to be scheduled efficiently.

Description

TLS extracts threads from serial code and executes them speculatively in parallel with a safe thread. The speculative thread will need to be discarded or re-run if its presumptions on the input state prove to be invalid. It is a dynamic (runtime) parallelization technique that can uncover parallelism that static (compile-time) parallelization techniques may fail to exploit because at compile time thread independence cannot be guaranteed. For the technique to achieve the goal of reducing overall execute time, there must be available CPU resource that can be efficiently executed in parallel with the main safe thread.

TLS assumes optimistically that a given portion of code (generally loops) can be safely executed in parallel. To do so, it divides the iteration space into chunks that are executed in parallel by different threads. A hardware or software monitor ensures that sequential semantics are kept (in other words, that the execution progresses as if the loop were executing sequentially). If a dependence violation appears, the speculative framework may choose to stop the entire parallel execution and restart it; to stop and restart the offending threads and all their successors, in order to be fed with correct data; or to stop exclusively the offending thread and its successors that have consumed incorrect data from it.{{Cite journal |last=García Yaguez |first=Alvaro |date=2014 |title=Squashing Alternatives for Software-based Speculative Parallelization |url=https://ieeexplore.ieee.org/document/6475131 |journal=IEEE Transactions on Computers |volume=63 |issue=7 |pages=1826–1839|doi=10.1109/TC.2013.46 |s2cid=14081801 |url-access=subscription }}

References

{{Reflist|2|refs=

{{Cite book |doi = 10.1145/605397.605400|chapter = Speculative synchronization|title = Proceedings of the 10th international conference on architectural support for programming languages and operating systems (ASPLOS-X) - ASPLOS '02|pages = 18|year = 2002|last1 = Martínez|first1 = José F.|last2 = Torrellas|first2 = Josep|isbn = 1581135742|publisher=ACM|s2cid = 9189828|archive-url = https://web.archive.org/web/20181118133420/https://s3.amazonaws.com/academia.edu.documents/32836533/asplos02.pdf?AWSAccessKeyId=AKIAIWOWYYGZ2Y53UL3A&Expires=1542548785&Signature=wLPnjmhDH%2B0K%2Fu5zWo1R%2Fjna13Q%3D&response-content-disposition=inline%3B%20filename%3DSpeculative_Synchronization_Applying_Thr.pdf|archive-date = 2018-11-18|chapter-url=https://s3.amazonaws.com/academia.edu.documents/32836533/asplos02.pdf?AWSAccessKeyId=AKIAIWOWYYGZ2Y53UL3A&Expires=1542548785&Signature=wLPnjmhDH%2B0K%2Fu5zWo1R%2Fjna13Q%3D&response-content-disposition=inline%3B%20filename%3DSpeculative_Synchronization_Applying_Thr.pdf}}

}}

Further reading

  • {{cite journal

|last1=Yiapanis |first1=Paraskevas

|last2=Brown |first2=Gavin

|last3=Lujan |first3=Mikel

|year=2016

|title=Compiler-Driven Software Speculation for Thread-Level Parallelism

|journal=ACM Transactions on Programming Languages and Systems

|volume=38

|issue=2

|pages=1–45

|doi=10.1145/2821505

|doi-access=free

}}

  • {{cite journal

|last1=Yiapanis |first1=Paraskevas

|last2=Rosas-Ham |first2=Demian

|last3=Brown |first3=Gavin

|last4=Lujan |first4=Mikel

|year=2013

|title=Optimizing Software Runtime Systems for Speculative Parallelization

|journal=ACM Transactions on Architecture and Code Optimization

|volume=9

|issue=4

|pages=1–27

|doi=10.1145/2400682.2400698

|doi-access=free

}}

  • {{cite journal |last=Llanos |first=Diego R. |date=2007 |title=New scheduling strategies for randomized incremental algorithms in the context of speculative parallelization |url=https://ieeexplore.ieee.org/document/4167793 |journal=IEEE Transactions on Computers |volume=56 |issue=6 |pages=839–852|doi=10.1109/TC.2007.1030 |s2cid=3181243 |citeseerx=10.1.1.77.5496 }}
  • {{cite conference

|last1=Johnson |first1=Nick P.

|last2=Kim |first2=Hanjun

|last3=Prabhu |first3=Prakash

|last4=Zaks |first4=Ayal

|last5=August |first5=David I.

|year=2012

|title=Speculative separation for privatization and reductions

|url=http://liberty.princeton.edu/Publications/pldi12_privateer.pdf

|book-title=Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation

|conference=PLDI '12

|pages=359–370

|doi=10.1145/2254064.2254107

}}

  • {{cite conference

|last1=Bhowmik |first1=Anasua

|last2=Franklin |first2=Manoj

|year=2002

|title=A General Compiler Framework for Speculative Multithreading

|book-title=Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures

|conference=SPAA '02

|pages=99–108

|doi=10.1145/564870.564885

}}

  • {{cite conference

|last1=Bruening |first1=Derek

|last2=Devabhaktuni |first2=Srikrishna

|last3=Amarasinghe |first3=Saman

|year=2000

|title=Softspec: Software-based Speculative Parallelism

|url=http://www.cag.lcs.mit.edu/softspec/FDDO.pdf

|conference=FDDO-3

|pages=1–10

}}

  • {{cite conference

|last1=Chen |first1=Michael K.

|last2=Olukotun |first2=Kunle |author2-link=Kunle Olukotun

|year=1998

|title=Exploiting Method-Level Parallelism in Single-Threaded Java Programs

|book-title=International Conference on Parallel Architectures and Compilation Techniques

|conference=PACT 1998

|pages=176–184

|doi=10.1109/PACT.1998.727190

}}

  • {{cite conference

|last1=Chen |first1=Michael K.

|last2=Olukotun |first2=Kunle |author2-link=Kunle Olukotun

|year=2003

|title=The Jrpm System for Dynamically Parallelizing Java Programs

|book-title=Proceedings of the 30th annual international symposium on Computer architecture

|conference=ISCA '03

|pages=434–446

|doi=10.1145/859618.859668

}}

  • {{cite conference

|last1=Cintra |first1=Marcelo

|last2=Llanos |first2=Diego R.

|year=2003

|title=Toward Efficient and Robust Software Speculative Parallelization on Multiprocessors

|book-title=Proceedings of the ninth ACM SIGPLAN symposium on Principles and practice of parallel programming

|conference=PPoPP '03

|pages=13–24

|doi=10.1145/781498.781501

}}

  • {{cite journal

|last1=Cook |first1=Jonathan J.

|year=2002

|title=Reverse Execution of Java Bytecode

|journal=The Computer Journal

|volume=45

|issue=6

|pages=608–619

|doi=10.1093/comjnl/45.6.608

|citeseerx=10.1.1.20.4765

}}

  • {{cite conference

|last1=Quinones |first1=Carlos Garcia

|last2=Madriles |first2=Carlos

|last3=Sanchez |first3=Jesus

|last4=Marcuello |first4=Pedro

|last5=Gonzalez |first5=Antonio

|last6=Tullsen |first6=Dean M.

|year=2005

|title=Mitosis Compiler: An Infrastructure for Speculative Threading Based on Pre-Computation Slices

|book-title=Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation

|conference=PLDI '05

|pages=269–279

|doi=10.1145/1065010.1065043

}}

  • {{cite journal

|last1=Hu |first1=Shiwen

|last2=Bhargava |first2=Ravi

|last3=John |first3=Lizy Kurian

|year=2003

|title=The Role of Return Value Prediction in Exploiting Speculative Method-Level Parallelism

|journal=JILP

|volume=5

|pages=1–21

|url=http://www.jilp.org/vol5/v5paper14.pdf

}}

  • {{cite thesis

|last1=Kazi |first1=Iffat H.

|year=2000

|title=A Dynamically Adaptive Parallelization Model Based on Speculative Multithreading

|url=http://portal.acm.org/citation.cfm?id=931717

|type=Ph.D. thesis

|publisher=University of Minnesota

|pages=1–188

}}

  • {{cite conference

|last1=Pickett |first1=Christopher J.F.

|last2=Verbrugge |first2=Clark

|year=2005

|title=SableSpMT: A Software Framework for Analysing Speculative Multithreading in Java

|book-title=Proceedings of the 6th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering

|conference=PASTE '05

|pages=59–66

|doi=10.1145/1108792.1108809

}}

  • {{cite conference

|last1=Pickett |first1=Christopher J.F.

|last2=Verbrugge |first2=Clark

|year=2005

|title=Software Thread Level Speculation for the Java Language and Virtual Machine Environment

|url=http://www.sable.mcgill.ca/publications/papers/2005-5/pickett-05-software.pdf

|book-title=Proceedings of the 18th international conference on Languages and Compilers for Parallel Computing

|conference=LCPC '05

|series=LNCS

|volume=4339

|pages=304–318

|doi=10.1007/978-3-540-69330-7_21

}}

  • {{cite conference

|last1=Porter |first1=Leo

|last2=Choi |first2=Bumyong

|last3=Tullsen |first3=Dean M.

|year=2009

|title=Mapping Out a Path from Hardware Transactional Memory to Speculative Multithreading

|book-title=18th International Conference on Parallel Architectures and Compilation Techniques

|conference=PACT '09

|pages=313–324

|doi=10.1109/PACT.2009.37

|citeseerx=10.1.1.153.2503

}}

  • {{cite journal

|last1=Rundberg |first1=Peter

|last2=Stenstrom |first2=Per

|year=2001

|title=An All-Software Thread-Level Data Dependence Speculation System for Multiprocessors

|url=http://www.jilp.org/vol3/rundberg-jilp.pdf

|journal=JILP

|volume=3

|pages=1–28

}}

  • {{cite journal

|last1=Steffan |first1=J. Gregory

|last2=Colohan |first2=Christopher

|last3=Zhai |first3=Antonia

|last4=Mowry |first4=Todd C.

|year=2005

|title=The STAMPede Approach to Thread-Level Speculation

|journal= ACM Transactions on Computer Systems

|volume=23

|issue=3

|pages=253–300

|doi=10.1145/1082469.1082471

|citeseerx=10.1.1.79.4317

|s2cid=10499545

}}

  • {{cite conference

|last1=Whaley |first1=John

|last2=Kozyrakis |first2=Christos

|year=2005

|title=Heuristics for Profile-driven Method-level Speculative Parallelization

|book-title=International Conference on Parallel Processing

|conference=ICPP 2005

|pages=147–156

|doi=10.1109/ICPP.2005.44

|citeseerx=10.1.1.77.3989

}}

  • {{cite journal

|last1=Renau |first1=Jose

|last2=Strauss |first2=Karin|author2-link=Karin Strauss

|last3=Ceze |first3=Luis

|last4=Liu |first4=Wei

|last5=Sarangi |first5=Smruti

|last6=Tuck |first6=James

|last7=Torrellas |first7=Josep

|year=2006

|title=Energy-Efficient Thread-Level Speculation

|url=http://www.soe.ucsc.edu/~renau/docs/toppicks06.pdf

|journal=IEEE Micro

|volume=26

|issue=1

|pages=80–91

|doi=10.1109/MM.2006.11

|s2cid=206472480

}}

  • {{cite conference

|last1=Yoshizoe |first1=Kazuki

|last2=Matsumoto |first2=Takashi

|last3=Hiraki |first3=Kei

|year=1998

|title=Speculative Parallel Execution on JVM

|url=http://www.cs.cf.ac.uk/hpjworkshop/papers/okpapers/speculative.ps

|book-title=UK Workshop on HPNC

|pages=1–20

}}

  • {{cite conference

|last1=Oancea |first1=Cosmin E.

|last2=Mycroft |first2=Alan

|last3=Harris |first3=Tim

|year=2009

|title=A Lightweight In-Place Implementation for Software Thread-Level Speculation

|url=http://timharris.co.uk/papers/2009-spaa.pdf

|book-title=Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures

|conference=SPAA '09

|pages=1–10

|doi=10.1145/1583991.1584050

}}

{{Parallel computing}}

{{CPU technologies}}

Category:Concurrency control

Category:Parallel computing

Category:Programming language implementation

Category:Instruction processing

Category:Speculative execution

{{comp-sci-stub}}