El paralelismo DOACROSS es una técnica de paralelización que se utiliza para realizar paralelismo a nivel de bucle mediante el uso de primitivas de sincronización entre las instrucciones de un bucle. Esta técnica se utiliza cuando un bucle no se puede paralelizar por completo mediante el paralelismo DOALL debido a dependencias de datos entre iteraciones del bucle, normalmente dependencias transportadas por el bucle. Las secciones del bucle que contienen dependencias transportadas por el bucle se sincronizan, mientras que cada sección se trata como una tarea paralela por sí misma. Por lo tanto, el paralelismo DOACROSS se puede utilizar para complementar el paralelismo DOALL para reducir los tiempos de ejecución del bucle.
El paralelismo DOACROSS es particularmente útil cuando una sentencia depende de los valores generados por otra sentencia. En un bucle de este tipo, el paralelismo DOALL no se puede implementar de manera directa. Si la primera sentencia bloquea la ejecución de la segunda sentencia hasta que se haya producido el valor requerido, entonces las dos sentencias podrían ejecutarse independientemente una de la otra (es decir, cada una de las sentencias mencionadas anteriormente se paralelizaría para una ejecución simultánea [1] utilizando el paralelismo DOALL.
El siguiente pseudocódigo ilustra el funcionamiento del paralelismo DOACROSS en tal situación. [2]
para ( 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 a por la iteración anterior. Sin embargo, la instrucción completa no depende de la iteración anterior, sino solo de una parte de ella. La instrucción se divide en dos bloques para ilustrar esto.
publicar ( 0 ); para ( int i = 0 ; i < N ; i ++ ) { temp = b [ i ] * c [ i ] + d [ i ] / e [ i ] + 1 ; esperar ( i -2 ); a [ i ] = a [ i -2 ] + temp ; publicar ( i ); } La primera instrucción 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 uso por otros subprocesos. El comando wait(i-2) espera el valor a[i-2] antes de desbloquear. El tiempo de ejecución del paralelismo DOACROSS depende en gran medida de qué fracción del programa sufre de dependencia de bucle. Se observan mayores ganancias cuando una porción considerable del bucle se ve afectada por la dependencia de bucle. [2]
El paralelismo DOACROSS sufre de sobrecargas significativas de espacio y granularidad debido a las primitivas de sincronización utilizadas. Los compiladores actuales a menudo pasan por alto este método debido a esta importante desventaja. [1] Las sobrecargas se pueden reducir reduciendo la frecuencia de sincronización a lo largo del bucle, aplicando las primitivas para grupos de declaraciones a la vez. [2]