El hecho de añadir más procesadores no es siempre sinónimo de mejora en el rendimiento de nuestro programa, ya que muchos programas secuenciales fueron escritos para correr en un solo procesador, este es el caso de la versión recursiva del algoritmo para calcular el factorial de un número o el de fibonacci, los cuales no se pueden paralelizar (claro, f(n) depende de un valor o más anteriores, f(n-1), f(n-2), etc), el rendimiento que se logra al correr estos algoritmos en un solo procesador o en múltiples procesadores es el mismo. Veamos un ejemplo paralelizable.
Queremos calcular n valores y sumarlos, entonces
suma = 0;
for (i = 0; i < n; i++) {
x = calcularSiguienteValor(. . .);
suma += x;
}
Ahora si supones que tenemeos p cores(número de cpu's), y n es mucho mayor que p, entonces cada core puede realizar
una porción de suma de n/p cantidades.
suma_privada = 0;
inicio_privada = . . . ;
final_privada = . . . ;
for (i_privada = inicio_privada; i_privada < final_privada; i_privada++) {
valor_privado = calcularSiguienteValor(. . .);
suma_privada += valor_privado;
}
La variables ahora son privadas, quiere decir que cada core tendrá su propida variable, es decir, aunque el nombre de la variable sea el mismo para cada core, estas seran privadas localmente. Por lo tanto cada core puede ejecutar el bloque anterior independientemente, supongamos que tenemos 4 cores, y n = 12 entonces cada bloque se dividirá de la siguiente manera
4, 7, 2 11, 9, 1 15, 0, 4
donde el core0 tendra la suma parcial de 4+7+2 = 13, el core1 = 21, el core2 = 19.
Luego cada core envía su suma parcial a un core master, por ejemplo :
if (Soy el core master) {/*Puede ser el core0*/
suma = suma_privada;
for (cada core diferente que el mio) {
recibir el valor del core;
suma += valor;
}
}
else {
/*Si el master es el core0, entonces aqui caen los demás, core1, core2, etc*/
enviar mi suma_privada al master;
}
Veamos un tipo de comunicación de "master local", donde no necesariamente todos los cores envian su valor a un solo core, sino que lo envian a su antecesor , de esta manera se mejora la eficiencia:
En este caso se usa un tipo de comunicación tipo árbol, habiendo muchos otros. Se observa que el core0 recibe la suma parcial del core1 y lo suma, lo mismo ocurre con el core2, el core4 y el core6; luego a su vez estos envia su data a un nodo, asi sucesivamente hasta que toda la data converge a un nodo.
Habiendo visto este ejemplo, se pude decir que existen principios básicos para paralelizar un algoritmo, como se observa en el gráfico la coordinacion involucra comunicación, uno o más cores envian su valor privado a otros, también se necesita un balanceo de cargas ya que no queremos que un core trabaje más que otros, se busca siempre uniformizar la data entre todos los cores, de tal manera que cada core tenga aproximadamenta (n / p) cantidad de valores, si un no hubiera el balanceo de cargas entonces un core puede acabar su trabajo muy pronto y por lo tanto esperaría a que los otros acaben, por lo tanto estaría perezoso y otros que tienen mucha carga se demoraría mucho más en acabar, entonces sumando el tiempo total no se llegaría a una mejora con respecto a una implementación secuencial. Otro tipo muy importante de coordinación es la sincronización ya que sin esa condición no se podria controlar que core debe ejecutar un bloque de código, si se tiene un bloque de lectura de datos y otro bloque que trabaja con estos datos, entonces a la vez que se obtiene un dato se comenzaría a trabajar con ellos sin haber terminado la lectura aún, por lo tanto entre estos dos bloques se necesita un tipo de sentencia que espere a que todos los cores tengan los datos, luego recién empezar a calcular.
En el siguiente post veremos ejemplos concretos aplicando paralismo a cierto problemas.
Referencias
An introduction to Parallel Programming, Peter Pacheco, University of San Francisco, 2011.
Principios básicos
