Privatización (programación informática)

El siguiente paso del modelo agrupa las tareas en tareas más grandes, ya que normalmente hay más tareas que procesadores disponibles. Por lo general, el número de hilos de ejecución asignados a las tareas se elige de forma que sea menor o igual al número de procesadores, asignándose cada hilo a un procesador único. ^{[ 1 ]}

Inmediatamente después de este paso, es necesario analizar el uso de variables dentro de las tareas. Este paso determina si cada variable debe ser compartida por todos o privada para cada hilo. ^{[ 1 ]} Este paso es exclusivo de la programación con memoria compartida. (Una alternativa es el paso de mensajes , en el que todas las variables son privadas). ^{[ 1 ]}

Según su comportamiento, las variables se clasifican de la siguiente manera:

• Solo lectura : cuando una variable solo puede ser leída por todas las tareas paralelas.
• Lectura/escritura sin conflictos : cuando una variable es leída, escrita o ambas por una sola tarea. Si la variable no es escalar, diferentes tareas paralelas pueden leer/escribir distintos elementos.
• Conflicto de lectura/escritura : ocurre cuando una tarea escribe en una variable y otra puede leerla. Si la variable no es escalar, diferentes tareas paralelas leen/escriben elementos distintos.

Como se desprende de su definición, las variables de lectura/escritura conflictivas introducen dependencias entre diferentes hilos de ejecución y, por lo tanto, impiden la paralelización automática del programa. Las dos técnicas principales utilizadas para eliminar estas dependencias son la privatización y la reducción . En la reducción, a cada hilo se le proporciona una copia de la variable de lectura/escritura conflictiva para operar sobre ella y producir un resultado parcial, que luego se combina con las copias de otros hilos para producir un resultado global. ^{[ 1 ]} Otra técnica similar a la privatización se denomina expansión , en la que una variable escalar se expande en un array, lo que hace que cada hilo acceda a un elemento diferente del array. ^{[ 5 ]} Si la variable que se va a expandir es un array, la expansión añade otra dimensión al array. ^{[ 6 ]}

Las dependencias —posibles conflictos entre diferentes hilos durante la ejecución— impiden la paralelización, y estos conflictos surgen cuando tenemos variables con permisos de lectura/escritura conflictivos. Una técnica para eliminar estos conflictos es la privatización. El principio básico consiste en crear una copia privada de una variable para cada hilo, en lugar de compartir una única instancia. Esto cambia la categoría de la variable de "Lectura/Escritura conflictiva" a "Lectura/Escritura no conflictiva".

Las instancias locales (privadas) reales de las variables con conflicto de lectura/escritura se crean en tiempo de compilación, asignando varias áreas de memoria para las variables almacenadas en diferentes ubicaciones de memoria. La arquitectura de los multiprocesadores de memoria compartida ayuda, ya que los hilos comparten un espacio de direcciones .

Existen dos situaciones en las que una variable puede describirse como privatizable :

1. Cuando la variable se escribe antes de que la lea la misma tarea durante la secuencia de ejecución del programa original. En este caso, si la tarea escribiera en su copia privada en lugar de la compartida, se eliminaría el conflicto/dependencia. Esto se debe a que la secuencia de ejecución del programa garantiza que el valor será el escrito por la misma tarea, eliminando cualquier conflicto que pudiera surgir si otros subprocesos accedieran a la misma variable. Véase el  ejemplo 1 .
2. Cuando la variable se lee antes de que la misma tarea la escriba. La diferencia radica en que el valor que la tarea intenta leer proviene de un paso de cálculo previo en otra tarea. Pero si cada tarea escribiera en su propia copia privada, cualquier conflicto o dependencia se resolvería durante la ejecución, ya que todas leerían un valor conocido de antemano y luego escribirían sus valores correctos en sus propias copias. Véase el  ejemplo 2 .

Dado que las variables con conflictos de lectura/escritura son la única categoría que impide la paralelización, no es necesario declarar explícitamente como privadas las variables de solo lectura y las variables sin conflictos de lectura/escritura. Si bien hacerlo no afectará la corrección del programa, podría consumir más memoria debido a copias innecesarias.

En ocasiones, una variable no puede ni privatizarse ni reducirse para eliminar el conflicto de lectura/escritura. En estos casos, la variable con conflicto de lectura/escritura debe actualizarse mediante diferentes tareas en diferentes momentos. Véase el  ejemplo 3 .

Este problema a veces se puede resolver cambiando el alcance del paralelismo para explorar una región paralela diferente. Esto podría producir buenos resultados, ya que a menudo, después de volver a analizar el código, algunas variables con conflictos de lectura/escritura pueden pasar a ser sin conflictos de lectura/escritura. ^{[ 1 ]} Si la variable sigue causando conflictos, el último recurso es declararla como compartida y proteger su acceso mediante alguna forma de exclusión mutua , y proporcionar sincronización si los accesos a la variable deben ocurrir en un orden específico para garantizar la corrección.

Las variables que pueden generar conflictos de lectura/escritura pueden ser escalares o de tipos compuestos, como arreglos, matrices, tipos estructurados, etc. La privatización se puede aplicar a ambos tipos de variables.

Cuando se aplica a variables escalares, el espacio adicional y la sobrecarga introducidos al hacer copias privadas adicionales por hilo son relativamente pequeños, porque los escalares son pequeños. ^{[ 1 ]} Sin embargo, aplicar la privatización a arreglos, matrices u otros tipos compuestos es mucho más complejo.

Al trabajar con arreglos, el compilador intenta analizar el comportamiento de cada elemento por separado y verificar el orden en que se lee y se escribe. Si cada elemento se escribe antes de leerse en la misma iteración, este arreglo puede privatizarse. Para ello, el compilador necesita analizar el arreglo con mayor detalle para agrupar sus accesos en secciones. Además, el compilador debe contar con funciones adicionales para manipular y gestionar los elementos del arreglo. Por ejemplo, algunas expresiones de arreglo pueden contener términos simbólicos; por lo tanto, para poder privatizar dicho arreglo, el compilador necesita funciones avanzadas de manipulación simbólica . ^{[ 5 ]}

Una variable puede considerarse privada si cada tarea escribe en ella antes de leerla. En este caso, no importa si otros hilos lo hacen. En el código siguiente, la variable xse utiliza para intercambiar tres pares de variables diferentes. Dado que siempre se escribe en ella antes de leerla, puede considerarse privada.

//Código secuencial: x = a; a = b; b = x; x = c; c = d; d = x; x = e; e = f; b = x; 

Este código no se puede paralelizar sin privatizarlo x. Con xprivatizado, puede ejecutarse en tres hilos diferentes, cada uno con su propio privado x:

//Código paralelo: //Hilo 1: x[1] = a; a = b; b = x[1]; // Hilo 2: x[2] = c; c = d; d = x[2]; // Hilo 3: x[3]= e; e = f; b = x[3]; 

La privatización es posible cuando se conoce el valor de una variable antes de usarla, incluso si otra tarea escribe en ella. El siguiente código lo demuestra. La variable xse modifica en medio de cada tarea, pero su valor podría calcularse durante la compilación del programa. Al declararla xprivada y definirla al inicio de cada tarea, el código puede ejecutarse en paralelo.

//Código secuencial: x = 1; y = x * 3; x = 4; z = y/x; a = x * 9; x = 3; b = a/x; c = x * 1; x = 11; d = c/x; 

Para que el código secuencial anterior sea paralelo, se deben agregar algunas líneas de código para que xpueda ser privatizado:

//Código paralelo //Hilo 0: x[0] = 1; y = x[0] * 3; x[0] = 4; z = y/x[0]; //Hilo 1: x[1] = 4; a = x[1] * 9; x[1] = 3; b = a/x[1]; //Hilo 2: x[2] = 3; c = x[2] * 1; x[2] = 11; d = c/x[2]; 

Debido al código adicional, este breve ejemplo podría no mostrar una mejora significativa en la velocidad. Sin embargo, en código más extenso y real, esta técnica puede mejorar considerablemente el rendimiento.

Se produce un fallo de privatización cuando una variable se escribe en una tarea y se lee en otra, sin conocer su valor de antemano. Un ejemplo es la suma de los elementos de un array. La suma es una variable compartida que se lee y se escribe en cada iteración del bucle.

En código secuencial, esto funciona correctamente. Pero si cada iteración se ejecutara en un hilo diferente, se calcularía una suma incorrecta. En este caso, la privatización no funciona. sumNo se puede hacer privada porque depende de su valor de la iteración anterior.

//Código secuencial: suma = 0; para (i = 0; i < 100; i++) suma += a[i]; 

Este problema se puede resolver en parte mediante el desenrollado de bucles . Dado que no importa el orden en que se agreguen los elementos , el bucle se puede dividir en un número arbitrario de partes:

// Hilo 0: suma[0] = 0; para (i[0] = 0; i[0] < 100; i[0] += 3) suma[0] += a[i[0]]; // Hilo 1: suma[1] = 0; para (i[1] = 1; i[1] < 100; i[1] += 3) suma[1] += a[i[1]]; // Hilo 2: suma[2] = 0; para (i[2] = 2; i[2] < 100; i[2] += 3) suma[2] += a[i[2]]; // Hilo "Maestro": esperar_para_todos(hilo[0], hilo[1], hilo[2]); suma = suma[0] + suma[1] + suma[2];