Multiprocesamiento especulativo

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

La especulación a nivel de subproceso ( TLS ), también conocida como multiproceso especulativo o paralelización especulativa, ^[1] es una técnica para ejecutar especulativamente una sección de código informático que se prevé que se ejecutará más adelante en paralelo con la ejecución normal en un subproceso independiente separado . Un subproceso especulativo de este tipo puede necesitar hacer suposiciones sobre los valores de las variables de entrada. Si estas resultan ser inválidas, entonces las partes del subproceso especulativo que dependen de estas variables de entrada deberán descartarse y eliminarse. Si las suposiciones son correctas, el programa puede completarse en un tiempo más corto siempre que el subproceso haya podido programarse de manera eficiente.

Descripción

TLS extrae subprocesos del código serial y los ejecuta especulativamente en paralelo con un subproceso seguro. El subproceso especulativo deberá descartarse o volver a ejecutarse si sus presunciones sobre el estado de entrada resultan ser inválidas. Es una técnica de paralelización dinámica (en tiempo de ejecución) que puede descubrir paralelismos que las técnicas de paralelización estática (en tiempo de compilación) pueden no 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 de ejecución general, debe haber un recurso de CPU disponible que pueda ejecutarse de manera eficiente en paralelo con el subproceso seguro principal. ^[2]

TLS asume de manera optimista que una porción dada de código (generalmente bucles) puede ejecutarse en paralelo de manera segura. Para ello, divide el espacio de iteración en fragmentos que son ejecutados en paralelo por 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 estuviera ejecutando 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 subprocesos infractores y todos sus sucesores, para que se les proporcionen los datos correctos; o detener exclusivamente el subproceso infractor y sus sucesores que han consumido datos incorrectos de él. ^[3]

Referencias

1. Estebanez, Alvaro (2017). "Una encuesta sobre técnicas de especulación a nivel de subproceso". ACM Computing Surveys . 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 10ª conferencia internacional sobre soporte arquitectónico para lenguajes de programación y sistemas operativos (ASPLOS-X) - ASPLOS '02 . ACM. p. 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, Alvaro (2014). "Alternativas de aplastamiento para la paralelización especulativa basada en software" . IEEE Transactions on Computers . 63 (7): 1826–1839. doi :10.1109/TC.2013.46. S2CID  14081801.

Lectura adicional

• Yiapanis, Paraskevas; Brown, Gavin; Lujan, Mikel (2016). "Especulación de software basada en compiladores para paralelismo a nivel de subproceso". 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). "Optimización de sistemas de ejecución de software para paralelización especulativa". 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. 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 general de compilación para subprocesamiento múltiple 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–10.
• Chen, Michael K.; Olukotun, Kunle (1998). "Explotación del paralelismo a nivel de método en programas Java de un solo subproceso". Conferencia internacional sobre arquitecturas paralelas y técnicas de compilación . PACT 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.
• 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 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". 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 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 subprocesamiento múltiple especulativo (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 sexto taller ACM SIGPLAN-SIGSOFT sobre análisis de programas para herramientas de software e ingeniería . PASTE '05. págs. 59–66. doi :10.1145/1108792.1108809.
• Pickett, Christopher JF; Verbrugge, Clark (2005). "Especulación a nivel de subproceso 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. págs. 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 subprocesamiento múltiple especulativo". 18.ª Conferencia internacional sobre arquitecturas paralelas y técnicas de compilación . PACT '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 subproceso de todo el 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 subproceso". 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. págs. 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 subproceso energéticamente eficiente" (PDF) . IEEE Micro . 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 subproceso 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.