Algoritmos Paralelos

Otro modelo de computación es cuando tenemos más de un procesador, digamos p procesadores. En este caso, la memoria puede ser compartida o distribuida.

Memoria : Compartida Misma máquina

distribuida

Distribuida Distintas máquinas

Análisis y Diseño de Algoritmos

– En general, cuando se trata de máquinas distribuidas lo óptimo es minimizar el número de mensajes.

Objetivo de un buen algoritmo paralelo:

– Paralelizar al máximo Tp* =T1/Tp p: procesadores

Esto no siempre es posible, así que se define :

– SpeedUp= T1/Tp ≤ p ; Factor de paralelización

– La idea es poder balancear la carga en los procesadores (que todos hagan el mismo trabajo)

Análisis y Diseño de Algoritmos

Sin embargo, el poder obtener un buen balance de carga es una tarea compleja, esto requiere de una buena a) sincronización y coordinación.

En general podríamos decir que el tiempo en paralelo, está conformado de la siguiente manera:

Tiempo = Tiempo de Procesamiento + Tiempo de Coord.

Paralelo Simultaneo Sincronización

Análisis y Diseño de Algoritmos

En el tiempo de sincronización y coordinación va implicado el tamaño y número de mensajes que se envían los procesadores entre si, en un modelo distribuido.

Análisis y Diseño de Algoritmos

El paralelismo está determinado por las estrategias de paralelización, el compilador y el sistema operativo (por ejemplo : procesos, hebras (threads)).

Análisis y Diseño de Algoritmos

Memoria Compartida

En este caso puede haber acceso concurrente de varios procesadores a un lugar de memoria para leer o escribir.

Es decir pueden haber varios procesadores escribiendo en la memoria, leer no es problema.

La lectura concurrente en general no es un problema.

Análisis y Diseño de Algoritmos

a) Escritura Exclusiva: Sólo un procesador puede escribir al mismo tiempo. Una forma de resolver esto es utilizar semáforos cuando uno de los procesadores se encuentre escribiendo. Aquí el balance de carga es un problema, ya que existen procesadores esperando para poder escribir. Si todos escriben lo mismo no hay problema, el problema es cuando todos los procesadores escriben cosas diferentes.

Análisis y Diseño de Algoritmos

b) Escritura Concurrente: Sólo uno tiene éxito al escribir. Este modelo se llama PRAM y dependiendo de la concurrencia tenemos:

• CREW PRAM (escritura exclusiva) Más usado• CRCW PRAM (escritura concurrente)• EREW (todo exclusivo)

Análisis y Diseño de Algoritmos

Problema: Buscar una palabra de largo m en un texto de largo n. Dividimos el texto en p partes, cada uno busca en su parte.

Este es un problema altamente paralelizable, lo que hacemos es dividir el texto en p pedazos y cada procesador busca en un texto de largo n/p+m-1 ( esto es, por si la palabra cae en 2 pedazos).

Análisis y Diseño de Algoritmos

Tp=T1(n/p+m-1)= k*(n/p+m)(usamos un algoritmo lineal con largo k, en el peor

caso)

Por lo que el factor de paralelización:

SpeedUp: kn/k*(n/p+m) =p/(1+(mp)/n =p(1-(mp)/n), donde mp/n es menor que 1

Análisis y Diseño de Algoritmos