Programación paralela
Especificación de problema ? algoritmo paralelo.
Programación paralela:
no hay recetas,
creatividad,
aproximación metodológica.
Fases
Particionado: descomponer datos y tareas
independiente del número de procesadores
Comunicación: establecer comunicaciones entre tareas.
Aglomeración: combinación de tareas para reducir costes.
Mapeo: asignación de tareas a procesadores,
maximizar balanceo,
minimizar comunicaciones.
Particionado
Descomposición del problema de grano fino: gran número de tareas.
Descomposición del dominio: primero se descomponen los datos y después las tareas.
Descomposición funcional: primero se descomponen las tareas y después los datos.
Descomposición del dominio
Conjunto de datos del mismo tamaño.
Tareas que trabajen sobre esos datos.
Tareas pueden necesitar información de distintos conjuntos de datos.
Posibles distintas particiones:
Ejemplo: malla tridimensional.
Descomposición funcional
Puede haber datos distintos para las distintas funciones,
o compartición de datos:
Por duplicación,
Por comunicación
Ejemplo: modelado del clima, tratamiento de imágenes.
Particionado, chequeo
¿Las tareas superan al menos en un orden de magnitud el número de procesadores?
Si no, poca flexibilidad para los pasos posteriores.
¿Se evita duplicación de computación y de almacenamiento?
Si no, puede dar lugar a algoritmo no escalable.
¿Son las tareas de tamaño similar?
Si no, puede ser difícil hacer una asignación balanceada.
¿Aumenta el número de tareas con el tamaño del problema?
Si no, puede dar lugar a algoritmo no escalable.
¿Se han estudiado distintas particiones?
¿y descomposición del dominio y funcional?
Comunicación
Se definen canales (directos o indirectos) entre tareas que tienen que comunicar datos.
Se definen mensajes a enviar y recibir.
En paralelismo de datos no se podrán crear los canales.
Optimización de prestaciones:
Distribuyendo comunicaciones (paralelismo en comunicaciones). El sistema puede limitarlo (redes).
Comunicaciones globales: identificar conjuntos de tareas que intervienen en la comunicación. Utilizar rutinas optimizadas, o programarlas si no están disponibles.
Solapar comunicación y computación (pipeline).
Comunicación
Ejemplos:
Suma de n números.
Relajación de Jacobi.
Página siguiente  |