Tipos de problemas paralelos. Metodología de desarrollo de programas paralelos
Enviado por Pablo Turmero
Índice 1. Introducción. 2. Análisis de algoritmos. 3. Metodología de desarrollo de programas paralelos. 4. Esquemas de algoritmos paralelos. 5. Problemas numéricos. Librerías.
? Los problemas que pueden resolverse mediante un algoritmo paralelo son, obviamente, muy heterogéneos.
Suelen ser problemas de complejidad elevada, aún no perteneciendo al grupo de problemas intratables (el número de operaciones crece de forma rápida –p.e. exponencial– con el tamaño del problema).
? Dentro del conjunto de problemas tratables (el número de operaciones crece polinómicamente con el tamaño del problema) se suelen dar dos situaciones que hacen necesaria la programación paralela:
– Problemas de gran dimensión
– Problemas de tiempo real Otro tipo de problemas: problemas de gran desafío, por su relevancia social (genoma humano, meteorología, clima, fenómenos sísmicos…).
? Diferentes modelos sobre distintos aspectos de la programación paralela: – Modelo arquitectónico: arquitectura de la máquina — multiprocesadores: memoria compartida — multicomputadores: paso de mensajes — modelos mixtos – Modelo de programación: herramientas de alto nivel (OpenMP, MPI). – Modelo de coste: permite evaluar el coste del algoritmo.
Índice 1. Introducción. 2. Análisis de algoritmos. 3. Metodología de desarrollo de programas paralelos. 4. Esquemas de algoritmos paralelos. 5. Problemas numéricos. Librerías.
? En la programación paralela (al igual que en la secuencial) son necesarias herramientas que permitan estimar el tiempo de ejecución y la memoria consumidos por un algoritmo, para determinar si es adecuado o no para la resolución del problema.
El objetivo es desarrollar algoritmos eficientes (eficiencia: relación entre los recursos que consume y los resultados que obtiene).
? Factores que influyen en el tiempo de ejecución de un programa:
– el lenguaje de programación (el programador) – la máquina – el compilador (opciones) – los tipos de datos – los usuarios que estén trabajando en el sistema
? Factores que influyen en el tiempo de ejecución de un programa paralelo:
– la competencia por la memoria (bloques de cache) – la fracción de código secuencial (Amdahl) – la creación/asignación de procesos – la computación extra: variables de control, identificación de procesos, cálculos adicionales… – la comunicación (para memoria distribuida) – la sincronización – los desequilibrios de carga
| Página siguiente |