ensayo

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 incrementadocontinuamente para
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
– Sonsistemas cada vez más complejos 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 globalatmosphere divided into cells of size 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) takes106 seconds or over 10 days.

•

To perform calculation 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
bycalculating 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 N2algorithm and almost a year for one
iteration using an efficient 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 a saturarse.
• 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 variosprocesadores. Sistemas paralelos
Con la tecnología VLSI, el costo de los procesadores 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 variosprocesadores trabajando juntos para
resolver una tarea común
• El modo de uso de los procesadores 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...