Multihilo especulativo

Técnica de paralelización del tiempo de ejecución de la computadora

La especulación a nivel de subprocesos ( TLS ), también conocida como subprocesos múltiples especulativos o paralelización especulativa, ^[1] es una técnica para ejecutar especulativamente una sección de código de computadora que se anticipa que se ejecutará más adelante en paralelo con la ejecución normal en un sistema independiente separado. hilo . Tal hilo especulativo puede necesitar hacer suposiciones sobre los valores de las variables de entrada. Si resultan ser inválidos, entonces las partes del hilo especulativo que dependen de estas variables de entrada deberán descartarse y aplastarse. Si las suposiciones son correctas, el programa puede completarse en un tiempo más corto siempre que el hilo se haya podido programar de manera eficiente.

Descripción

TLS extrae subprocesos del código serie y los ejecuta de forma especulativa en paralelo con un subproceso seguro. El hilo especulativo deberá descartarse o volver a ejecutarse si sus presunciones sobre el estado de entrada resultan no válidas. Es una técnica de paralelización dinámica (tiempo de ejecución) que puede descubrir paralelismo que las técnicas de paralelización estática (tiempo de compilación) pueden no lograr explotar porque en tiempo de compilación no se puede garantizar la independencia de los subprocesos. 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 principal seguro. ^[2]

TLS asume con optimismo que una determinada porción de código (generalmente bucles) se puede ejecutar de forma segura en paralelo. Para ello, divide el espacio de iteración en fragmentos que se ejecutan en paralelo mediante diferentes subprocesos. Un monitor de hardware o software garantiza que se mantenga la semántica secuencial (en otras palabras, que la ejecución avance como si el bucle se ejecutara secuencialmente). Si aparece una violación de dependencia, el marco especulativo puede optar por detener toda la ejecución paralela y reiniciarla; detener y reiniciar los hilos infractores y todos sus sucesores, para recibir datos correctos; o detener exclusivamente el hilo infractor y sus sucesores que han consumido datos incorrectos del mismo. ^[3]

Referencias

1. Estebanez, Álvaro (2017). "Una encuesta sobre técnicas de especulación a nivel de subprocesos". Encuestas de Computación ACM . 49 (2): 1–39. doi :10.1145/2938369. S2CID  423292.
2. Martínez, José F.; Torrellas, Josep (2002). «Sincronización especulativa» (PDF) . Actas de la décima conferencia internacional sobre soporte arquitectónico para lenguajes de programación y sistemas operativos (ASPLOS-X) - ASPLOS '02 . ACM. pag. 18. doi : 10.1145/605397.605400. ISBN 1581135742. S2CID  9189828. Archivado desde el original (PDF) el 18 de noviembre de 2018.
3. García Yaguez, Álvaro (2014). "Aplastando alternativas para la paralelización especulativa basada en software" . Transacciones IEEE en computadoras . 63 (7): 1826–1839. doi :10.1109/TC.2013.46. S2CID  14081801.

Otras lecturas

• Yiapanis, Paraskevas; Marrón, Gavin; Luján, Mikel (2016). "Especulación del software impulsado por compilador para el paralelismo a nivel de subprocesos". Transacciones ACM sobre lenguajes y sistemas de programación . 38 (2): 1–45. doi : 10.1145/2821505 .

• Yiapanis, Paraskevas; Rosas-Ham, Demián; Marrón, Gavin; Luján, Mikel (2013). "Optimización de sistemas de ejecución de software para paralelización especulativa". Transacciones ACM sobre arquitectura y optimización de código . 9 (4): 1–27. doi : 10.1145/2400682.2400698 .
• Llanos, Diego R. (2007). "Nuevas estrategias de programación para algoritmos incrementales aleatorios en el contexto de paralelización especulativa". Transacciones IEEE en computadoras . 56 (6): 839–852. CiteSeerX  10.1.1.77.5496 . doi :10.1109/TC.2007.1030. S2CID  3181243.
• Johnson, Nick P.; Kim, Hanjun; Prabhu, Prakash; Zaks, Ayal; Agosto, David I. (2012). «Separación especulativa para privatizaciones 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 compilación general para subprocesos múltiples especulativos". Actas del decimocuarto simposio anual de ACM sobre arquitecturas y algoritmos paralelos . 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–10.
• Chen, Michael K.; Olukotun, Kunle (1998). "Explotación del paralelismo a nivel de método en programas Java de un solo subproceso". Congreso Internacional de Arquitecturas Paralelas y Técnicas de Compilación . PACTO 1998. págs. 176–184. doi :10.1109/PACT.1998.727190.
• Chen, Michael K.; Olukotun, Kunle (2003). "El sistema Jrpm para paralelizar dinámicamente programas Java". Actas del 30º simposio internacional anual sobre arquitectura informática . ISCA '03. págs. 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. págs. 13-24. doi : 10.1145/781498.781501.
• Cocine, Jonathan J. (2002). "Ejecución inversa de Java Bytecode". La revista informática . 45 (6): 608–619. CiteSeerX  10.1.1.20.4765 . doi : 10.1093/comjnl/45.6.608.
• Quiñones, Carlos García; Madrid, Carlos; Sánchez, Jesús; Marcuello, Pedro; González, Antonio; Tullsen, Dean M. (2005). "Compilador de mitosis: una infraestructura para subprocesamiento especulativo basado en cortes previos al cálculo". Actas de la conferencia ACM SIGPLAN 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; Juan, Lizy Kurian (2003). "El papel de la predicción del valor de retorno en la explotación del paralelismo especulativo a nivel de método" (PDF) . JILP . 5 : 1–21.
• Kazi, Iffat H. (2000). Un modelo de paralelización dinámicamente adaptativo basado en subprocesos múltiples especulativos (tesis doctoral). Universidad de Minnesota. págs. 1–188.
• Pickett, Christopher JF; Verbrugge, Clark (2005). "SableSpMT: un marco de software para analizar subprocesos múltiples especulativos en Java". Actas del 6to taller ACM SIGPLAN-SIGSOFT sobre análisis de programas para herramientas e ingeniería de software . PEGAR '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áquinas virtuales" (PDF) . Actas de la 18ª conferencia internacional sobre lenguajes y compiladores para computación paralela . LCPC'05. LNCS. vol. 4339, págs. 304–318. doi :10.1007/978-3-540-69330-7_21.
• Portero, Leo; Choi, Bumyong; Tullsen, Dean M. (2009). "Trazar un camino desde la memoria transaccional de hardware hasta el subproceso múltiple especulativo". XVIII Congreso Internacional de Arquitecturas Paralelas y Técnicas de Compilación . PACTO '09. págs. 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 de software para multiprocesadores" (PDF) . JILP . 3 : 1–28.
• Steffan, J. Gregorio; Colohan, Christopher; Zhai, Antonia; Mowry, Todd C. (2005). "El enfoque STAMPede para la especulación a nivel de subprocesos". Transacciones ACM en sistemas informáticos . 23 (3): 253–300. CiteSeerX  10.1.1.79.4317 . doi :10.1145/1082469.1082471. S2CID  10499545.
• Whaley, Juan; Kozyrakis, Christos (2005). "Heurística para la paralelización especulativa a nivel de método basada en perfiles". Congreso Internacional sobre Procesamiento Paralelo . ICPP 2005. págs. 147-156. CiteSeerX  10.1.1.77.3989 . doi :10.1109/ICPP.2005.44.
• Renau, José; Strauss, Karin ; Céze, Luis; Liu, Wei; Sarangi, Smruti; Tuck, James; Torrellas, Josep (2006). "Especulación a nivel de subprocesos sobre eficiencia energética" (PDF) . Micro IEEE . 26 (1): 80–91. 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.