Speculative multithreading

Short description: Computer runtime parallelization technique

Thread Level Speculation (TLS), also known as Speculative Multi-threading, 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. https://ieeexplore.ieee.org/document/4167793. 
• Johnson, Nick P.; Kim, Hanjun; Prabhu, Prakash; Zaks, Ayal; August, David I. (2012). "Speculative separation for privatization and reductions". PLDI '12. pp. 359–370. doi:10.1145/2254064.2254107. http://liberty.princeton.edu/Publications/pldi12_privateer.pdf. 
• Bhowmik, Anasua; Franklin, Manoj (2002). "A General Compiler Framework for Speculative Multithreading". SPAA '02. pp. 99–108. doi:10.1145/564870.564885. 
• Bruening, Derek; Devabhaktuni, Srikrishna; Amarasinghe, Saman (2000). "Softspec: Software-based Speculative Parallelism". FDDO-3. pp. 1–10. http://www.cag.lcs.mit.edu/softspec/FDDO.pdf. 
• Chen, Michael K. (1998). "Exploiting Method-Level Parallelism in Single-Threaded Java Programs". PACT 1998. pp. 176–184. doi:10.1109/PACT.1998.727190. 
• Chen, Michael K. (2003). "The Jrpm System for Dynamically Parallelizing Java Programs". 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". 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. 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". 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". JILP 5: 1–21. http://www.jilp.org/vol5/v5paper14.pdf. 
• 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". 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". LCPC '05. 4339. pp. 304–318. doi:10.1007/978-3-540-69330-7_21. http://www.sable.mcgill.ca/publications/papers/2005-5/pickett-05-software.pdf. 
• Porter, Leo; Choi, Bumyong; Tullsen, Dean M. (2009). "Mapping Out a Path from Hardware Transactional Memory to Speculative Multithreading". 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". JILP 3: 1–28. http://www.jilp.org/vol3/rundberg-jilp.pdf. 
• 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. doi:10.1145/1082469.1082471. 
• Whaley, John; Kozyrakis, Christos (2005). "Heuristics for Profile-driven Method-level Speculative Parallelization". ICPP 2005. pp. 147–156. doi:10.1109/ICPP.2005.44. 
• Renau, Jose (2006). "Energy-Efficient Thread-Level Speculation". IEEE Micro 26 (1): 80–91. doi:10.1109/MM.2006.11. http://www.soe.ucsc.edu/~renau/docs/toppicks06.pdf. 
• Yoshizoe, Kazuki; Matsumoto, Takashi; Hiraki, Kei (1998). "Speculative Parallel Execution on JVM". pp. 1–20. http://www.cs.cf.ac.uk/hpjworkshop/papers/okpapers/speculative.ps. 
• Oancea, Cosmin E.; Mycroft, Alan; Harris, Tim (2009). "A Lightweight In-Place Implementation for Software Thread-Level Speculation". SPAA '09. pp. 1–10. doi:10.1145/1583991.1584050. http://timharris.co.uk/papers/2009-spaa.pdf.