Práctica: Suma de Prefijos

Haciendo uso de la infraestructura de canales mediante pipes introducida en la sección 4.1.8 escriba un algoritmo paralelo para el cálculo de la suma de prefijos ( $s_i = s_{i-1]}+a_i$ , $s_0 = a_0$ ) de un vector $a$ . Para simplificar, suponga que el número de procesos $p = 2^{\log(p)}$ es potencia de 2 y que el tamaño del vector $N$ es divisible por $p$ . Los $p$ procesos se configuran según un hipercubo de dimensión $\log(p)$ .

Después de realizar las sumas parciales en su segmento el proceso $k$ intercambia con su vecino ( $k \oplus 2^i$ , donde $\oplus$ significa XOR) en dimensión $i = 0 \ldots \log(p)$ la suma del hipercubo $i$ -dimensional en el que está. El subtotal recibido se acumula para la siguiente etapa. Si el proceso $k$ está en el hipercubo alto (Esto es, si el bit $i$ de $k$ está a 1) lo acumula también a su suma parcial. Por último suma los valores de la suma parcial a cada uno de los elementos de su segmento. Para una descripción mas completa del algoritmo véase [2] y en concreto el capítulo 3, página 58 (16 del pdf) accesible desde el enlace http://nereida.deioc.ull.es/˜casiano/book/cap3redes.pdf.

Tenga en cuenta que los canales hacia un procesador $i$ son compartidos para escritura por los restantes ($j \ne i$ ) y por tanto se pueden producir race conditions o condiciones de carrera. Ilustre un ejemplo de tal situación. Para solucionar el problema, escriba una subrutina receive para la recepción de mensajes que recibe como argumento el procesador fuente del mensaje. La subrutina administra un hash (declárelo en clausura con la subrutina) en la que almacena los mensajes que llegan y que no son del fuente solicitado. Cuando es llamada, la subrutina comprueba si el mensaje ya solicitado esta en el hash. Si es asi, lo obtiene, lo elimina del hash y lo retorna. En caso contrario permanece a la espera por el canal del mensaje solicitado. Los mensajes que llegan y que no son del fuente solicitado son almacenados. Cuando llega el mensaje solicitado termina la espera y se retorna su valor. Escriba una subrutina send de envío que colabore con la subrutina de recepción descrita.