Paralelo

ALGORITMOS PARALELOS Tema 1: Introducción a la Computación Paralela

• Necesidad de la computación paralela • ¿Qué es la programación paralela? • Modelos de computadores • Evaluación de los computadores paralelos

Introducción a la Computación Paralela

1

Necesidad de la Computación Paralela
• La velocidad de los computadores secuenciales convencionales se ha incrementado continuamentepara adaptarse a las necesidades de las aplicaciones • Simultáneamente hay una demanda continua de un poder computacional superior
– Modelado y simulación numérica de problemas en ciencias e ingeniería – Costosos cálculos iterativos sobre grandes cantidades de datos y fuertes restricciones temporales: – Ejemplos: predicción meteorológica, biocomputación, astrofísica – Son sistemas cada vez máscomplejos que requieren mayor tiempo de cómputo
Introducción a la Computación Paralela 2

Necesidad de la Computación Paralela

Introducción a la Computación Paralela

3

Necesidad de la Computación Paralela

Introducción a la Computación Paralela

4

Necesidad de la Computación Paralela
Global Weather Forecasting Example
• Suppose whole global atmosphere divided into cells ofsize 1 mile × 1 mile × 1 mile to a height of 10 miles (10 cells high) - about 5 × 108 cells. Suppose each calculation requires 200 floating point operations. In one time step, 1011 floating point operations necessary. To forecast the weather over 7 days using 1-minute intervals, a computer operating at 1Gflops (109 floating point operations/s) takes 106 seconds or over 10 days. To performcalculation in 5 minutes requires computer operating at 3.4 Tflops (3.4 × 1012 floating point

•

•

•

operations/sec).
Introducción a la Computación Paralela 5

Necesidad de la Computación Paralela
Modeling Motion of Astronomical Bodies
• Each body attracted to each other body by gravitational forces. Movement of each body predicted by calculating total force on each body. • With N bodies,N - 1 forces to calculate for each body, or approx. N2 calculations. (N log2 N for an efficient approx. algorithm.) • After determining new positions of bodies, calculations repeated. • A galaxy might have, say, 1011 stars. • Even if each calculation done in 1 ms (extremely optimistic figure), it takes 109 years for one iteration using N2 algorithm and almost a year for one iteration using anefficient N log2 N approximate algorithm.
Introducción a la Computación Paralela 6

Necesidad de la Computación Paralela
• Siempre habrá aplicaciones que requieren más poder computacional • La relación coste/prestaciones se hace desfavorable si se pretende incrementar más aún la potencia de los computadores secuenciales. • Además, el rendimiento de los computadores secuenciales está comenzando asaturarse. • En todo caso hay límites para una única CPU
– Memoria disponible – Prestaciones

• Solución: Usar varios procesadores. Sistemas paralelos
Con la tecnología VLSI, el costo de los procesadores es menor.
Introducción a la Computación Paralela 7

Necesidad de la Computación Paralela
• Solución: Usar varios procesadores. Sistemas paralelos
Con la tecnología VLSI, el costo de losprocesadores es menor.

• Muchas posibilidades:
– – – – – – – Pipeline Cachés Paralelismo a nivel de instrucción Ejecución fuera de orden Especulación Varios procesadores en un chip LAN de altas prestaciones
Introducción a la Computación Paralela 8

¿Qué es la programación paralela? • Uso de varios procesadores trabajando juntos para resolver una tarea común • El modo de uso de losprocesadores puede ser diseñado por el programador: – Cada procesador trabaja en una porción del problema. – Los procesos pueden intercambiar datos, a través de la memoria o por una red de interconexión.
Introducción a la Computación Paralela 9

Ventajas de la Computación Paralela • La programación paralela permite: – Resolver problemas que no caben en una CPU – Resolver problemas que no se...