투기성 멀티스레딩

이 문서에는 여러 가지 문제가 있습니다.개선을 돕거나 토크 페이지에서 이러한 문제에 대해 논의해 주십시오.(이러한 템플릿메시지를 삭제하는 방법과 타이밍에 대해 설명합니다) 오래된 정보로 인해 이 문서의 사실 정확도가 저하될 수 있습니다. 최근 이벤트나 새로운 정보를 반영하여 이 기사를 업데이트 할 수 있도록 도와주세요. (2017년 3월) 이 문서에는 일반적인 참조 목록이 포함되어 있지만 대응하는 충분한 인라인 인용이 없습니다. 좀 더 정밀한 인용문을 도입하여 이 글의 개선에 도움을 주시기 바랍니다.(2018년 11월) (이 템플릿메시지 삭제 방법 및 삭제 시기 확인) (이 템플릿메시지를 삭제하는 방법과 타이밍을 확인합니다)

스레드 레벨 사양(TLS)은 투기적 멀티스레딩 또는 투기적 ^[1]병렬화라고도 하며 나중에 다른 독립 스레드에서 일반 실행과 병렬로 실행될 것으로 예상되는 컴퓨터 코드 섹션을 추측적으로 실행하는 기술입니다.이러한 추측성 스레드는 입력 변수의 값에 대한 가정을 해야 할 수 있습니다.이러한 입력 변수가 유효하지 않은 것으로 판명될 경우 이러한 입력 변수에 의존하는 투기 스레드 부분은 폐기하고 뭉개야 합니다.전제조건이 맞다면 스레드를 효율적으로 스케줄 할 수 있다면 프로그램을 단시간에 완료할 수 있습니다.

묘사

TLS는 시리얼 코드에서 스레드를 추출하여 안전한 스레드와 병렬로 추측적으로 실행합니다.입력 상태에 대한 추측이 잘못된 것으로 판명되면 투기성 스레드를 폐기하거나 다시 실행해야 합니다.이것은 동적(런타임) 병렬화 기술로 컴파일 시 스레드의 독립성을 보장할 수 없기 때문에 정적(컴파일 타임) 병렬화 기술이 이용에 실패할 수 있는 병렬화를 밝혀낼 수 있습니다.이 기술이 전체 실행 시간을 단축하는 목표를 달성하려면 메인 세이프 ^[2]스레드와 병렬로 효율적으로 실행할 수 있는 CPU 리소스가 있어야 합니다.

TLS는 코드의 특정 부분(일반적으로 루프)을 병렬로 안전하게 실행할 수 있다고 낙관적으로 가정합니다.이를 위해 반복 공간을 서로 다른 스레드에 의해 병렬로 실행되는 청크로 나눕니다.하드웨어 또는 소프트웨어 모니터는 시퀀셜시멘틱을 유지합니다(즉, 루프가 순차적으로 실행되는 것처럼 실행이 진행됩니다).의존관계 위반이 발생했을 경우 투기적 프레임워크는 병렬실행 전체를 중지하고 재시작하거나, 문제가 되는 스레드와 그 모든 후속 스레드를 중지하고 재시작하여 올바른 데이터를 공급받거나,^[3] 문제가 되는 스레드와 후속 스레드에서 잘못된 데이터를 소비한 후속 스레드를 단독으로 중지하도록 선택할 수 있습니다.

레퍼런스

추가 정보

• 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.