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 siguiente |