Misplaced Pages

Revision as of 08:45, 24 November 2019

This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these messages) This article's factual accuracy may be compromised due to out-of-date information. Please help update this article to reflect recent events or newly available information. (March 2017) This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (November 2018) (Learn how and when to remove this message) (Learn how and when to remove this message)

Thread Level Speculation (TLS) 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 the speculative thread 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.

It is also known as Speculative Multithreading (SpMT).

Description

TLS extracts threads from serial code and executes them speculatively in parallel with a safe thread. The speculative thread will need to be squashed or discarded or re-run if its presumptions on the input state prove to be invalid. It is a runtime parallelization technique which uncovers parallelism that static (compile-time) parallelization techniques fail to exploit. This particular case of speculative execution occurs at the thread level as opposed to the instruction level and can be implemented both in hardware as well as in software.

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.

References

1. Martínezy, Jose F.; Torrellas, Josep. "Speculative Synchronization: Applying Thread-Level Speculation to Explicitly Parallel Applications". {{cite web}}: Missing or empty |url= (help)

Further reading

• Yiapanis, Paraskevas; Brown, Gavin; Lujan, Mikel (2016). "Compiler-Driven Software Speculation for Thread-Level Parallelism". ACM Transactions on Programming Languages and Systems. 38 (2): 1–45. doi:10.1145/2821505.

• Yiapanis, Paraskevas; Rosas-Ham, Demian; Brown, Gavin; Lujan, Mikel (2013). "Optimizing Software Runtime Systems for Speculative Parallelization". ACM Transactions on Architecture and Code Optimization. 9 (4): 1–27. doi:10.1145/2400682.2400698.
• Johnson, Nick P.; Kim, Hanjun; Prabhu, Prakash; Zaks, Ayal; August, David I. (2012). "Speculative separation for privatization and reductions" (PDF). Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation. PLDI '12. pp. 359–370. doi:10.1145/2254064.2254107. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help)
• Bhowmik, Anasua; Franklin, Manoj (2002). "A General Compiler Framework for Speculative Multithreading". Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures. SPAA '02. pp. 99–108. doi:10.1145/564870.564885. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help)
• Bruening, Derek; Devabhaktuni, Srikrishna; Amarasinghe, Saman (2000). Softspec: Software-based Speculative Parallelism (PDF). FDDO-3. pp. 1–10. {{cite conference}}: Cite has empty unknown parameter: |booktitle= (help)
• Chen, Michael K.; Olukotun, Kunle (1998). "Exploiting Method-Level Parallelism in Single-Threaded Java Programs". International Conference on Parallel Architectures and Compilation Techniques. PACT 1998. pp. 176–184. doi:10.1109/PACT.1998.727190. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help)
• Chen, Michael K.; Olukotun, Kunle (2003). "The Jrpm System for Dynamically Parallelizing Java Programs". Proceedings of the 30th annual international symposium on Computer architecture. ISCA '03. pp. 434–446. doi:10.1145/859618.859668. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help)
• Cintra, Marcelo; Llanos, Diego R. (2003). "Toward Efficient and Robust Software Speculative Parallelization on Multiprocessors". Proceedings of the ninth ACM SIGPLAN symposium on Principles and practice of parallel programming. PPoPP '03. pp. 13–24. doi:10.1145/781498.781501. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help)
• Cook, Jonathan J. (2002). "Reverse Execution of Java Bytecode". The Computer Journal. 45 (6): 608–619. CiteSeerX 10.1.1.20.4765. doi:10.1093/comjnl/45.6.608.
• Quinones, Carlos Garcia; Madriles, Carlos; Sanchez, Jesus; Marcuello, Pedro; Gonzalez, Antonio; Tullsen, Dean M. (2005). "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. PLDI '05. pp. 269–279. doi:10.1145/1065010.1065043. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help)
• Hu, Shiwen; Bhargava, Ravi; John, Lizy Kurian (2003). "The Role of Return Value Prediction in Exploiting Speculative Method-Level Parallelism" (PDF). JILP. 5: 1–21.
• Kazi, Iffat H. (2000). A Dynamically Adaptive Parallelization Model Based on Speculative Multithreading (Ph.D. thesis). University of Minnesota. pp. 1–188.
• Pickett, Christopher J.F.; Verbrugge, Clark (2005). "SableSpMT: A Software Framework for Analysing Speculative Multithreading in Java". Proceedings of the 6th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering. PASTE '05. pp. 59–66. doi:10.1145/1108792.1108809. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help)
• Pickett, Christopher J.F.; Verbrugge, Clark (2005). "Software Thread Level Speculation for the Java Language and Virtual Machine Environment" (PDF). Proceedings of the 18th international conference on Languages and Compilers for Parallel Computing. LCPC '05. LNCS. Vol. 4339. pp. 304–318. doi:10.1007/978-3-540-69330-7_21. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help)
• Porter, Leo; Choi, Bumyong; Tullsen, Dean M. (2009). "Mapping Out a Path from Hardware Transactional Memory to Speculative Multithreading". 18th International Conference on Parallel Architectures and Compilation Techniques. PACT '09. pp. 313–324. doi:10.1109/PACT.2009.37. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help)
• Rundberg, Peter; Stenstrom, Per (2001). "An All-Software Thread-Level Data Dependence Speculation System for Multiprocessors" (PDF). JILP. 3: 1–28.
• Steffan, J. Gregory; Colohan, Christopher; Zhai, Antonia; Mowry, Todd C. (2005). "The STAMPede Approach to Thread-Level Speculation". ACM Transactions on Computer Systems. 23 (3): 253–300. CiteSeerX 10.1.1.79.4317. doi:10.1145/1082469.1082471.
• Whaley, John; Kozyrakis, Christos (2005). "Heuristics for Profile-driven Method-level Speculative Parallelization". International Conference on Parallel Processing. ICPP 2005. pp. 147–156. doi:10.1109/ICPP.2005.44. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help)
• Renau, Jose; Strauss, Karin; Ceze, Luis; Liu, Wei; Sarangi, Smruti; Tuck, James; Torrellas, Josep (2006). "Energy-Efficient Thread-Level Speculation" (PDF). IEEE Micro. 26 (1): 80–91. doi:10.1109/MM.2006.11.
• Yoshizoe, Kazuki; Matsumoto, Takashi; Hiraki, Kei (1998). "Speculative Parallel Execution on JVM". UK Workshop on HPNC. pp. 1–20. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help)
• Oancea, Cosmin E.; Mycroft, Alan; Harris, Tim (2009). "A Lightweight In-Place Implementation for Software Thread-Level Speculation" (PDF). Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures. SPAA '09. pp. 1–10. doi:10.1145/1583991.1584050. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help)

This computer science article is a stub. You can help Misplaced Pages by expanding it.

• v
• t
• e

• Concurrency control
• Parallel computing
• Programming language implementation
• Instruction processing
• Speculative execution
• Computer science stubs