Modelo PRAM (Parallel Random Access Machine)
Comparación en cada procesador del algoritmo PRAM-CRCW
ij 5 6 9 2 9 7 8 3 m
5 F V V F V V V F F
6 F F V F V V V F F
9 F F F F F F F F V
2 V V V F V V V V F
9 F F F F F F F F V
7 F F V F V F V F F
8 F F V F V F F F F
3 V V V F V V V F F
Modelo PRAM (Parallel Random Access Machine)
El algoritmo paralelo requiere de 6 pasos para concluir. Sí n es el número de datos a comparar
Su complejidad asintótica temporal es T?(n) = 6 = O(1).
Se requieren n2 procesadores para ejecutarlo, por lo que su complejidad de hardware es H(n) = n2.
Modelo PRAM (Parallel Random Access Machine)
Encontrar el número mayor del arreglo A, se analiza en una computadora PRAM-EREW.
Modelo PRAM (Parallel Random Access Machine)
El algoritmo paralelo requiere de 3 pasos para su ejecución, esto es log28.
Por tanto, el tiempo paralelo será T?(n) = 3 = log28 = O(log2n).
Con respecto al hardware, se requerirán n/2 procesadores, por lo que H(n) = O(n).
Modelo de circuitos
n nodos de entrada con grado de entrada cero, los cuales contienen los datos de inicio x1, x2, …, xn
Nodos de operación con grado de entrada dos, etiquetados con alguno de los operadores aritméticos o booleanos.
m nodos de salida con grado de salida cero.
Modelo de circuitos
Modelo de circuitos
La profundidad d(n) de un circuito es la longitud del camino mas largo, en función del número de operaciones, de cualquier entrada a una salida de C(n).
El ancho w(n) es el máximo número de operaciones realizadas en paralelo en cualquier paso:
Modelo de circuitos
El tamaño de un circuito s(n) es el número total de operaciones en los nodos:
H(n) ? w(n)= 2
T?(n)? d(n) = 2
Modelo de redes
El algoritmo del problema queda definido mediante Galg = {Nt, Ti, Cij, Zij}.
Nt son las tareas concurrentes y se representan por círculos
Ti tiempo de ejecución de la tarea i
Cij volumen de comunicación de la tarea i a la j
Zij es el retraso y representa por una D en el grafo
Modelo de redes
a(n) = 45b(n-1) + 10c(n) + u(n)
b(n) = 10a(n) + c(n)
c(n) = a(n-1) + c(n-1)
Donde:
u(n) es una entrada
los datos son de 4 bytes
Modelo de redes
Modelo de redes
(H(n)) = 3 procesadoress unidades
(T?(n)) = 6 unidades (un período)
Complejidad de los algoritmos paralelos
Secuencial
Tamaño de la entrada (n)
La complejidad temporal del algoritmo O
La calidad del código generado
La velocidad de la máquina
Clasificación
Polinomiales (P)
NP
Complejidad de los algoritmos paralelos
En los algoritmos paralelos, clase NC:
Tiempo de ejecución polinomial en función del logaritmo del tamaño de la entrada (log n)k
Número de procesadores polinomial (nk).
A estos algoritmos se les llama algoritmos eficientemente paralelizables
Los problemas NC están dentro de P
Complejidad de los algoritmos paralelos
Métricas para determinar su desempeño
Ejecuciones paralelas (tiempo requerido)
Trabajo
Aceleración, asintótica: S(?) y S(p)
Eficiencia E(p)
Redundancia R(p)
Utilización del sistema U(p)
Calidad Q(p)
Métricas para determinar su desempeño
Tiempo de ejecución (Secuencial)
Se mide en segundos o en el número de operaciones requeridos por el proceso de cálculo An para una entrada de datos n.
Donde:
m: grado de paralelismo (número de tareas que se ejecutan en un instante dado)
ti: tiempo total en que hay exactamente i procesadores trabajando en paralelo
Métricas para determinar su desempeño
Tiempo de ejecución en paralelo obtenido de los modelos descritos.
No se tiene un límite en el número de procesadores; a éste se le denomina “tiempo asintótico” y se determina por:
Métricas para determinar su desempeño
Trabajo
Se define como el número de operaciones que se ejecutan durante el proceso de cálculo y se determina por:
Métricas para determinar su desempeño
Métricas para determinar su desempeño
Paradigma de trabajo-tiempo de Brent
Cuando se tiene disponible un número de procesadores igual al requerido por los modelos descritos, Tp(An) = T?(An).
Pero cuando el número de procesadores es menor, el trabajo que se realiza se debe repartir entre los procesadores disponibles. El tiempo de ejecución se incrementa entonces, y está acotado por la relación siguiente:
Métricas para determinar su desempeño
Aceleraciones S(?) y S(p)
La aceleración asintótica S(?), es la relación entre el tiempo necesario para resolver un problema dado usando el mejor algoritmo secuencial conocido T1(An) y el tiempo necesario para resolver el mismo problema por un algoritmo paralelo usando el número de procesadores determinadas por el modelo ideal T?(An).
Métricas para determinar su desempeño
La aceleración S(p), es la relación entre el tiempo secuencial T1(An) y el tiempo necesario para resolver el mismo problema por un algoritmo paralelo usando p procesadores Tp(An):
Métricas para determinar su desempeño
Las operaciones que se deben de ejecutar secuencialmente limitan la aceleración de un algoritmo paralelo
Sea (?) la fracción secuencial, entre 0???1
(1- ?) la fracción paralela
Se le conoce como la ley de Amdhal:
Métricas para determinar su desempeño
Eficiencia E(p)
La eficiencia se define como la relación entre la aceleración S(p) y el número de procesadores p. Este factor indica qué tan bien son utilizados los procesadores.
Métricas para determinar su desempeño
Redundancia R(p)
La redundancia se define como la relación entre el número total de operaciones realizadas usando p procesadores O(p), y el número de operaciones realizadas usando un procesador O(1).
Métricas para determinar su desempeño
Utilización del sistema U(p)
Esta es una medida de desempeño directamente proporcional a la eficiencia y a la redundancia. Indica el porcentaje de los recursos que estuvieron ocupados durante la ejecución del programa paralelo.
Métricas para determinar su desempeño
Calidad Q(p)
Medida de desempeño directamente proporcional a la eficiencia y a la aceleración e inversamente proporcional a la redundancia. Evalúa el mérito de una aplicación paralela en un sistema de computadoras
 Página anterior | Volver al principio del trabajo | Página siguiente  |