Hispanopedia WikiEl paralelismo DOACROSS es una técnica de paralelismo que se utiliza para lograr paralelismo a nivel de bucle mediante primitivas de sincronización entre las instrucciones de un bucle. Esta técnica se emplea cuando un bucle no puede paralelizarse completamente con el paralelismo DOALL debido a dependencias de datos entre iteraciones, generalmente dependencias internas del bucle. Las secciones del bucle que contienen dependencias internas se sincronizan, tratando cada sección como una tarea paralela independiente. Por lo tanto, el paralelismo DOACROSS puede complementar al paralelismo DOALL para reducir los tiempos de ejecución de los bucles.
Descripción
El paralelismo DOACROSS es particularmente útil cuando una instrucción depende de los valores generados por otra. En un bucle de este tipo, el paralelismo DOALL no se puede implementar de forma directa. Si la primera instrucción bloquea la ejecución de la segunda hasta que se haya producido el valor requerido, entonces ambas instrucciones podrían ejecutarse de forma independiente (es decir, cada una de las instrucciones mencionadas se paralelizaría para su ejecución simultánea [ 1 ] mediante el paralelismo DOALL).
El siguiente pseudocódigo ilustra el funcionamiento del paralelismo DOACROSS en tal situación. [ 2 ]
Ejemplo
for ( int i = 0 ; i < N ; i ++ ) { a [ i ] = a [ i -2 ] + b [ i ] * c [ i ] + d [ i ] / e [ i ] + 1 ; }En este ejemplo, cada iteración del bucle requiere el valor escrito en la iteración anterior. Sin embargo, la instrucción completa no depende de la iteración anterior, sino solo una parte de ella. La instrucción se divide en dos bloques para ilustrar esto.
post ( 0 ); for ( int i = 0 ; i < N ; i ++ ) { temp = b [ i ] * c [ i ] + d [ i ] / e [ i ] + 1 ; wait ( i - 2 ); a [ i ] = a [ i - 2 ] + temp ; post ( i ); }La primera instrucción ya no tiene dependencia de bucle, y el resultado de esta instrucción se almacena en la variable temp. El comando post() se utiliza para indicar que se ha producido el resultado requerido para su utilización por otros hilos. El comando wait(i-2) espera el valor a[i-2] antes de desbloquearse. El tiempo de ejecución del paralelismo DOACROSS depende en gran medida de qué fracción del programa sufre dependencia de bucle. Se observan mayores ganancias cuando una porción considerable del bucle se ve afectada por la dependencia de bucle. [ 2 ]
Desventajas
El paralelismo DOACROSS sufre de importantes sobrecargas de espacio y granularidad debido a las primitivas de sincronización utilizadas. Los compiladores modernos suelen pasar por alto este método debido a esta importante desventaja. [ 1 ] Las sobrecargas pueden reducirse disminuyendo la frecuencia de sincronización a lo largo del bucle, aplicando las primitivas a grupos de instrucciones a la vez. [ 2 ]
Véase también
Referencias
- ^ Unnikrishnan , Priya; Shirako, junio; Barton, equipo; Chatterjee, Sanjay; Silvera, Raúl; Sarkar, Vivek (27 de agosto de 2012). Kaklamanis, Christos; Papatheodorou, Theodore; Spirakis, Paul G. (eds.). Procesamiento Paralelo Euro-Par 2012 . Apuntes de conferencias sobre informática. Springer Berlín Heidelberg. págs. 219–231 . doi : 10.1007/978-3-642-32820-6_23 . ISBN 9783642328190.
- 1 2 3 Solihin, Yan (2009). Fundamentos de la arquitectura multinúcleo paralela . Chapman and Hall/CRC.
- Análisis de datos