Multihilo especulativo

La especulación a nivel de hilo ( TLS ), también conocida como multihilo especulativo o paralelización especulativa, ^{[ 1 ]} es una técnica para ejecutar de forma especulativa una sección de código informático que se prevé que se ejecute posteriormente en paralelo con la ejecución normal en un hilo independiente . Dicho hilo especulativo puede necesitar hacer suposiciones sobre los valores de las variables de entrada. Si estas resultan ser inválidas, las partes del hilo especulativo que dependen de dichas variables de entrada deberán descartarse y eliminarse. Si las suposiciones son correctas, el programa puede completarse en un tiempo menor, siempre que el hilo se haya podido programar de forma eficiente.

TLS extrae hilos del código secuencial y los ejecuta de forma especulativa en paralelo con un hilo seguro. El hilo especulativo deberá descartarse o volver a ejecutarse si sus suposiciones sobre el estado de entrada resultan inválidas. Se trata de una técnica de paralelización dinámica (en tiempo de ejecución) que puede descubrir paralelismo que las técnicas de paralelización estática (en tiempo de compilación) podrían no aprovechar, ya que en tiempo de compilación no se puede garantizar la independencia de los hilos. Para que la técnica logre el objetivo de reducir el tiempo total de ejecución, debe haber recursos de CPU disponibles que puedan ejecutarse eficientemente en paralelo con el hilo seguro principal. ^{[ 2 ]}

TLS parte de la premisa optimista de que una porción determinada de código (generalmente bucles) puede ejecutarse de forma segura en paralelo. Para ello, divide el espacio de iteración en fragmentos que son ejecutados en paralelo por diferentes hilos. Un monitor de hardware o software garantiza que se mantenga la semántica secuencial (es decir, que la ejecución progrese como si el bucle se ejecutara secuencialmente). Si se produce una violación de dependencia, el marco especulativo puede optar por detener toda la ejecución paralela y reiniciarla; detener y reiniciar los hilos problemáticos y todos sus sucesores para que reciban los datos correctos; o detener exclusivamente el hilo problemático y sus sucesores que hayan consumido datos incorrectos. ^{[ 3 ]}

• Yiapanis, Paraskevas; Brown, Gavin; Lujan, Mikel (2016). "Especulación de software dirigida por compilador para paralelismo a nivel de hilos" . 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). "Nuevas estrategias de planificación para algoritmos incrementales aleatorios en el contexto de la paralelización especulativa". IEEE Transactions on Computers . 56 (6): 839– 852. Bibcode : 2007ITCmp..56..839L . CiteSeerX 10.1.1.77.5496 . doi : 10.1109/TC.2007.1030 . S2CID 3181243 .  
• Johnson, Nick P.; Kim, Hanjun; Prabhu, Prakash; Zaks, Ayal; August, David I. (2012). "Separación especulativa para privatización y reducciones" (PDF) . Actas de la 33.ª Conferencia ACM SIGPLAN sobre diseño e implementación de lenguajes de programación . PLDI '12. págs. 359–370 . doi : 10.1145/2254064.2254107 . 
• Bhowmik, Anasua; Franklin, Manoj (2002). "Un marco de compilador general para multihilo especulativo". Actas del decimocuarto simposio anual de la ACM sobre algoritmos y arquitecturas paralelas . SPAA '02. págs. 99–108 . doi : 10.1145/564870.564885 . 
• Brüning, Derek; Devabhaktuni, Srikrishna; Amarasinghe, Saman (2000). Softspec: paralelismo especulativo basado en software (PDF) . FDDO-3. págs. 1 a 10. 
• Chen, Michael K.; Olukotun, Kunle (1998). "Aprovechamiento del paralelismo a nivel de método en programas Java de un solo hilo". Conferencia Internacional sobre Arquitecturas Paralelas y Técnicas de Compilación . PACT 1998. pp. 176–184 . doi : 10.1109/PACT.1998.727190 . 
• Chen, Michael K.; Olukotun, Kunle (2003). "El sistema Jrpm para la paralelización dinámica de programas Java". Actas del 30.º simposio internacional anual sobre arquitectura de computadoras . ISCA '03. pp. 434–446 . doi : 10.1145/859618.859668 . 
• Cintra, Marcelo; Llanos, Diego R. (2003). "Hacia una paralelización especulativa de software eficiente y robusta en multiprocesadores". Actas del noveno simposio ACM SIGPLAN sobre principios y práctica de la programación paralela . PPoPP '03. pp. 13–24 . doi : 10.1145/781498.781501 . 
• Cook, Jonathan J. (2002). "Ejecución inversa de código de bytes de Java". The Computer Journal . 45 (6): 608– 619. CiteSeerX 10.1.1.20.4765 . doi : 10.1093/comjnl/45.6.608 . 
• Quinones, Carlos García; Madriles, Carlos; Sánchez, Jesús; Marcuello, Pedro; González, Antonio; Tullsen, Dean M. (2005). "Mitosis Compiler: una infraestructura para la programación especulativa basada en segmentos de precomputación". Actas de la conferencia ACM SIGPLAN de 2005 sobre diseño e implementación de lenguajes de programación . PLDI '05. págs. 269–279 . doi : 10.1145/1065010.1065043 . 
• Hu, Shiwen; Bhargava, Ravi; John, Lizy Kurian (2003). "El papel de la predicción del valor de retorno en la explotación del paralelismo a nivel de método especulativo" (PDF) . JILP . 5 : 1–21 .
• Kazi, Iffat H. (2000). Un modelo de paralelización dinámicamente adaptativo basado en multihilo especulativo (tesis doctoral). Universidad de Minnesota. págs. 1–188 . 
• Pickett, Christopher JF; Verbrugge, Clark (2005). "SableSpMT: Un marco de software para analizar el multihilo especulativo en Java". Actas del 6.º taller ACM SIGPLAN-SIGSOFT sobre análisis de programas para herramientas e ingeniería de software . PASTE '05. págs. 59–66 . doi : 10.1145/1108792.1108809 . 
• Pickett, Christopher JF; Verbrugge, Clark (2005). "Especulación a nivel de subprocesos de software para el lenguaje Java y el entorno de máquina virtual" (PDF) . Actas de la 18.ª conferencia internacional sobre lenguajes y compiladores para computación paralela . 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). "Trazando un camino desde la memoria transaccional de hardware hasta el multihilo especulativo". 18.ª Conferencia Internacional sobre Arquitecturas Paralelas y Técnicas de Compilación . PACT '09. pp. 313–324 . CiteSeerX 10.1.1.153.2503 . doi : 10.1109/PACT.2009.37 .  
• Rundberg, Peter; Stenstrom, Per (2001). "Un sistema de especulación de dependencia de datos a nivel de subprocesos totalmente basado en software para multiprocesadores" (PDF) . JILP . 3 : 1–28 .
• Steffan, J. Gregory; Colohan, Christopher; Zhai, Antonia; Mowry, Todd C. (2005). "El enfoque STAMPede para la especulación a nivel de hilo". 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). "Heurísticas para la paralelización especulativa a nivel de método basada en perfiles". Conferencia Internacional sobre Procesamiento Paralelo . ICPP 2005. pp. 147–156 . CiteSeerX 10.1.1.77.3989 . doi : 10.1109/ICPP.2005.44 .  
• Renau, Jose; Strauss, Karin ; Ceze, Luis; Liu, Wei; Sarangi, Smruti; Tuck, James; Torrellas, Josep (2006). "Especulación a nivel de hilo energéticamente eficiente" (PDF) . IEEE Micro . 26 (1): 80– 91. Bibcode : 2006IMicr..26a..80R . doi : 10.1109/MM.2006.11 . S2CID 206472480 . 
• Yoshizoe, Kazuki; Matsumoto, Takashi; Hiraki, Kei (1998). "Ejecución paralela especulativa en JVM" . Taller del Reino Unido sobre HPNC . págs. 1–20 . 
• Oancea, Cosmin E.; Mycroft, Alan; Harris, Tim (2009). "Una implementación ligera in situ para la especulación a nivel de subprocesos de software" (PDF) . Actas del vigésimo primer simposio anual sobre paralelismo en algoritmos y arquitecturas . SPAA '09. págs. 1–10 . doi : 10.1145/1583991.1584050 .