Speculative multithreading

Thread Level Speculation (TLS), also known as Speculative Multithreading, or Speculative Parallelization, 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.

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.
• Llanos, Diego R. (2007). "New scheduling strategies for randomized incremental algorithms in the context of speculative parallelization". IEEE Transactions on Computers. 56 (6): 839–852. doi:10.1109/TC.2007.1030. S2CID 3181243.
• 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.
• 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.
• Bruening, Derek; Devabhaktuni, Srikrishna; Amarasinghe, Saman (2000). Softspec: Software-based Speculative Parallelism (PDF). FDDO-3. pp. 1–10.
• 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.
• 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.
• 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.
• 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.
• 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.
• 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.
• 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.
• 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. S2CID 10499545.
• 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.
• 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. S2CID 206472480.
• Yoshizoe, Kazuki; Matsumoto, Takashi; Hiraki, Kei (1998). "Speculative Parallel Execution on JVM". UK Workshop on HPNC. pp. 1–20.
• 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.