Comunicación
Preferible comunicación estructurada.
No estructurada:
dificulta la programación,
puede necesitar algoritmos de asignación para mejorar balanceo y reducir comunicaciones,
aumenta coste.
Dinámica: se sabe en tiempo de ejecución.
Ejemplo: matrices dispersas.
Comunicación
Lectura de datos globales ? comunicación asíncrona.
Posibilidades:
cada tarea testea periódicamente si recibe peticiones,
otro conjunto de tareas para atender requerimientos,
interrupciones.
En Memoria Compartida problema de coherencia.
Ejemplo: backtracking y branch & bound.
Comunicación, chequeo
¿Se han balanceado las comunicaciones?
Si no, algoritmos poco escalables.
Si estructura a la que se accede muy frecuentemente controlada por una tarea, cuello de botella: distribuir la estructura y crear más tareas.
¿Se comunica cada tarea con un número reducido?
¿Se pueden ejecutar las comunicaciones concurrentemente?
Si no, puede dar lugar a algoritmo no escalable.
¿Impiden las comunicaciones que las tareas se ejecuten concurrentemente?
¿Se puede solapar comunicación y computación?
Aglomeración
En la aglomeración y mapeo se piensa en el sistema donde se va a ejecutar.
Para obtener buenas prestaciones puede ser necesario agrupar tareas:
menos tiempo de creación,
menos comunicaciones.
Estudiar distintas maneras de agrupamiento.
Si el número de tareas se reduce a una por procesador, el diseño está acabado.
Ejemplo: suma de números, malla tridimensional.
Aglomeración
Intentar reducir las comunicaciones:
Reducir número de datos a enviar o número de mensajes.
Efecto volumen/superficie:
normalmente la computación es de un orden de magnitud mayor que la comunicación (matriz-vector, matriz-matriz),
por lo que la relación computación/comunicación es mayor al aumentar la granularidad (relajación de Jacobi)
Algunas veces se puede reducir la comunicación replicando computación o datos (suma en anillo)
Si las tareas no pueden ejecutarse concurrentemente se pueden aglomerar tareas de diferentes niveles (suma en árbol)
Aglomeración
Número de tareas:
Con número reducido menor coste de creación.
Número mayor que procesadores, permite:
asignar varias tareas a un procesador y solapar comunicación y computación (por ejemplo, una tarea para comunicación y otra para computación en cada procesador),
estudiar varias posibilidades de mapeo.
El número de tareas debe variar con el tamaño del sistema y el problema.
Tener en cuenta reutilización de código y que la salida de un programa puede ser entrada para otro.
Aglomeración, chequeo
¿Hemos aglomerado tareas que se comunican frecuentemente?
Si no, puede haber un gran número de comunicaciones.
Si se replican computaciones, ¿repercute en una reducción de las comunicaciones?
Si se replican mucho puede ser perjudicial para la escalabilidad.
¿Se han generado tareas con coste de computación y de comunicación semejante (balanceo de la carga)?
¿Varía el número de tareas proporcionalmente al número de procesadores?
Si no, no escalable.
¿Se ha reducido todo lo posible el número de tareas sin reducir posibilidades de escalabilidad ni producir desbalanceo?
¿Se posibilita la reutilización de código?
Mapeo
En memoria distribuida no hay herramientas automáticas eficientes para asignar tareas a procesadores, pero sí en memoria compartida.
Para reducir tiempo de ejecución:
asignar tareas que se comunican con frecuencia al mismo procesador (puede haber limitaciones en el número de tareas por procesador),
y tareas que se ejecutan concurrentemente a procesadores distintos.
Mapeo
Algoritmos de balanceo de carga:
Estáticos, si el número de tareas y la carga de cada una es conocido.
Tienen coste adicional al principio.
Dinámicos, si no se conoce a priori, o se conoce pero la distribución de la carga no es regular, o si las tareas pueden generar nuevas tareas.
Coste adicional durante la ejecución.
Ejemplo: matrices dispersas, branch & bound.
Mapeo
ESTÁTICOS
Bisección recursiva:
Dividir la tarea en dos subgrupos minimizando comunicaciones y manteniendo balanceo.
Y seguir recursivamente.
Métodos probabilistas:
Asignar arbitrariamente. Se obtiene buena distribución sólo en algunos casos. Las comunicaciones no deben ser locales.
Mapeo cíclico:
Si se sabe que la carga evoluciona regularmente.
Puede ser cíclico por bloques.
Preprocesado:
Antes de le ejecución realizar una evaluación (trazado de rayos).
Mapeo
DINÁMICOS
Algoritmos locales:
Cada procesador compara periódicamente su carga con la de procesadores vecinos, y puede haber intercambio de datos.
Utilización de una bolsa de tareas:
Los procesadores toman tareas de la bolsa y posiblemente generan nuevas tareas.
La computación acaba cuando la bolsa está vacía y no hay posibilidad de generar nuevas tareas (problema de detección de la terminación).
Un único manejador de la bolsa, puede ser un cuello de botella si las tareas son pequeñas y hay comunicaciones frecuentes.
Jerarquía de manejadores, que se comunican entre ellos, y posiblemente un maestro común.
Distribuida entre los procesadores. Cada procesador debe evaluar su bolsa además de computar, por lo que habrá tareas de computación y de gestión de la bolsa.
Mapeo, chequeo
¿Se ha considerado las dos posibilidades de creación estática y dinámica de tareas?
Si se utiliza esquema maestro-esclavo, estudiar si el maestro se puede convertir en un cuello de botella, especialmente si puede llegar a ejecutarse en un gran número de procesadores.
Si es posible, utilizar asignaciones estáticas, pues son simples, especialmente las probabilísticas y cíclicas, y no es necesario aplicar algoritmos de rebalanceo durante la ejecución.
En caso de distribución probabilística o cíclica, asegurarse de que hay muchas más tareas que procesadores.
 Página anterior | Volver al principio del trabajo | Página siguiente  |