Algoritmos Paralelos

 

Modelo para computación paralela:

Máquina de von Neumann es una por una instrucción, uno por uno item de data, siguiendo un programa en memoria. 

En el libro se usa el modelo "parallel random-access machine" o p-ram. También llamado "single-instruction multiple-data-stream"
Se tienen varios procesadores, que se asume que comparten una memoria global. Todos ejecutan el mismo programa dado por un punto central de control. Trabajan en la misma instrucción al mismo tiempo.

En cada paso lee o escribe en la memoria global que todos comparten, pero en no mas de una ubicación de esta. Dos pueden leer lo mismo, pero no escribir en lo mismo, ni leer mientras el otro escribe.

 

concurrent-read, exclusive-write(CREW). Usado en el libro
 

También existen:
-exclusive-read,exclusive-write(EREW)
-concurrent-read,concurrent-write(CRCW).

En el modelo, leer o escribir, es tiempo constante, sin importar el número de procesadores. Para términos del libro, en la realidad no funciona así.

No se permite que el statement sea llamadas a función, ni loops que el largo dependa de la data. 

Si tenemos p procesadores, toma 8(log p) en que comience, para decirle a todos que hacer.

 

Técnicas básicas:

1-Árbol binario completo:

Todas las hojas de un mismo nivel se ejecutan en paralelo. La solución se da en el paso lg-n.  Por lo que le toma 8(log n) en hacer la operación con un arreglo con todos los valores. Se ocupan n/2 procesadores como máximo.

2- Pointer doubling:

Técnica más simple, para listas. En la lista cada item tiene un puntero al siguiente s[i]. Y el ultimo tiene un puntero a nulo s[n]=nil. 
 

No hay problemas de escritura, pues cada procesador escribe en un solo nodo, pero si de lectura, hay que asegurarse que antes de leer, los anteriores deben haber terminado su proceso. 

Cada vez que se corre se dobla el puntero al que apunta. 8(log n) cada procesador hace tiempo constante por las operaciones elementales que realiza. 

 

Trabajo y eficiencia:

Trabajo: p*t, p=cantidad de procesadores, t=el tiempo

Dos algoritmos son work-efficient, si están en el orden del otro.

Dos reglas para que sea eficiente:

-La cantidad de procesadores para una instancia de tamaño n debe estar en O(n^a) a siendo una constante.
-El tiempo requerido para resolver una instancia de tamaño n deber estar en O(log^b n)b siendo una constante.

 

Un algoritmo paralelo eficiente tiene número polinomial de procesadores y tiempo poligarítmico.

Es óptimo si work-efficient con el mejor algoritmo secuencial o con el mejor conocido. Se puede decir que tiene aceleración óptima (optimal speed-up)

Se cree que hay problemas que se solucionan con secuencial, pero no se puede con paralelo. 

 

Ejemplos con grafos:

1. Camino más corto:

En la iteración k, da los caminos más cortos entre nodos usando no mas de 2^k arcos.

Orden: 8(log^2 n)

 

2. Componentes conexos:

Se encarga de ver que componentes se encuentran conexos de un grafo, dejando un árbol o bosque de resultado. Utiliza conjuntos disjuntos y los une después. 
Orden: 8(n^2)

 

Evaluación de expresiones paralelas:

suma, resta, multiplicación y división. Árbol binario nodos internos son operadores y las hojas son los operandos.

 

Redes de ordenamiento paralelo:

Comparador: circuito con dos entradas y dos salidas, izquierda y derecha respectivamente. Si son iguales se cambian de arriba a abajo. Se crean redes se comparadores que ordenan los números que les demos en paralelo.

N = cantidad de comparadores a usar (tamaño de la red)

Funciona en 8(n)

 

El principio cero-uno:

VER IMAGEN

 

Redes unidoras paralelas:

Una red unidora consiste de comparadores, con dos grupos de n entradas y un grupo de 2n salidas. Cada grupo está ya ordenado, sale todo el conjunto ordenado. 

 

Redes unidoras mejoradas:

Se implementa divide and conquer a lo anterior. 

 

Ordenamiento paralelo:

Lo anterior puede ordenar n elementos en 8(log^2 n) y con 8(log^2 n) procesadores.

ALGORTIMO DE COLE:

Ordena en 8(n log n)

Números en potencia de 2, todos distintos. 

 

 

EREW vs CRCW p-rams:

EREW < CREW < CRCW

 

Computación distribuida:

Modelo múltiple-instrucción múltiple-flujo-datos: cada procesador trabaja a su ritmo con su data y sus instrucciones.

SIMD and MIMD. 

SIMD: procesadores cerca entre ellos.