Asignar las diferentes iteraciones de un
lazo sobre diferentes procesadores,
definiendo el orden de ejecución
Planificación de lazos paralelos
No tiene dependencia
de datos
Estática
Dinámica
Basado en cola central
Basado en colas distribuidas
Lazos con dependencia de datos
Intradependencia
Interdependencia
Operaciones de
entrada/salida
Minimizar tiempo de inicio
de operaciones de E/S
Maximizar utilización del camino
entre procesadores y unidades de E/S
Tareas de programas
Tiempos de comunicación
no considerados
Grafo de tareas tipo árbol
Sólo 2 procesadores
en el sistema
Sistema de
planificación
Sistema computacional
Programa paralelo
Planificación generada
Criterio de
rendimiento
Estrategias
Deterministas o
No deterministas
Estáticas o
dinámicas
Múltiples
programas o no
Apropiativas o
no apropiativas
Adaptativas o no
adaptativas
Centralizadas o
descentralizadas
Problema de asignación
de tareas
Función de costo general
Costo general
Costo de comunicación
Costo de referencia a un archivo
Costo de interferencia
Costo por desequilibrio
de carga de trabajo
Restricciones en sistemas
distribuidos
Restricciones de memoria
Plazos de tiempo
Relación tarea-procesador
Basados en una teoría
Basada en un proceso de búsqueda
Asignación de datos
Problema de asignación
de archivos
Asignar f archivos sobre n sitios para
optimizar ciertos criterios de rendimiento
La comunicación entre los diferentes
sitios en el sistema debe ser mínima
El tiempo de ejecución efectivo de
las aplicaciones debe ser minimizado
La carga en los diferentes
sitios debe ser balanceada
Problema de replicacion
de archivos
Dado un número de archivos, determinar el número de copias/réplicas por cada archivo y dónde se deben asignar para maximizar el
rendimiento del sistema. Este problema es típico cuando los usuarios están dispersos y las costos de comunicación son importantes
Distribución de carga de trabajo
Equilibrio de la carga
de trabajo
Modelos de presión
Algoritmo Round Robin
Bisección recursiva
A nivel de objetivos
nivel de implementación
Estructura
Modelo de transferencia
de la carga
Intercambio de información
Coordinación
Algoritmo
Proceso de decisión
estático o dinámico
Toma de Decisiones centralizada
Recolección centralizado
Difusión de la información
Decisión a la iniciativa
Actualización de la información
Sensibilidad del costo
Control de estabilidad
Reglas de decisión deterministas,
probabilísticas o a ciega
Determinación del estado
global del sistema
Partición de datos/programas
Descomposición de programas
Es un problema min-max, consistente en buscar el equilibrio
entre maximizar el paralelismo y minimizar la comunicación.
Descomposición de archivos
Determinar, dado un número de archivos,
cuál es la división óptima de los mismos
Mecanismos de migración
Son requeridos en los enfoques dinámicos
de asignación para equilibrar la carga
Entidad migrante
Activa
Procesos o hilos
Pasiva
Datos
Políticas
Localización
Seleccción
Transferencia
Copia perezosa
Copia perezosa centralizada
Pre-copiado
Transparencia
Manejo de memoria
Memoria caché
Política de
reemplazo
FIFO
LRU
MRU
LFU
DGS
Acelera el
acceso
Disminuye la
congestión
Coherencia
Protocolo entrometido
Protocolo directo
Bancos de memoria
Sub-bloques de la memoria
Conectados a los procesadores
Acceso independiente a cada uno
Canal de E/S propio
Conflictos
Bancos ocupados
Bancos simultaneos
Tolerancia a fallas
Tipos de falla
Transitiva
Intermitente
Permanente
Redundancia
De información
De tiempo
Física
Réplica activa
Respaldos primarios
Réplica pasiva
Otras técnicas
Códigos de error
Puntos de chequeo
Test de aceptación
Dependencia de datos
Análisis escalar
Determina la
aplicabilidad y
efecto de los
métodos de
transformación
Local
Interprocedimientos
Completo
Dependencia
en los lazos
Lazo normalizado
Vector de iteración
Orden textual
Orden lexicográfico
Test
Análisis Diofantino
Test inexacto
MCD
Test del borde
Test de dependencia
Teorema de verificación
de dependencias
Tipos
Dependencia verdadera
Antidependencias
Dependencia de salida
Dependencia de control
Tecnicas de transformación
Transformación DOALL
Convierte cada iteración de un lazo
en un proceso que es independiente
de todos los otros
Distribución de lazos
Divide la ejecución de un lazo en varios
grupos de instrucciones de su cuerpo,
para ser ejecutadas en diferentes lazos
Intercambio de lazos
Permuta un par de lazos anidados, tal
que el lazo más externo se convierte
en el más interno y viceversa
Eliminación de dependencias de salida y anti-dependencias
Eliminar las antidependencias
y las dependencias de salidas
Renombrar
Expansión escalar
Fusión de lazos
Combina dos lazos
adyacentes en uno
Torción de lazos
Modifica la forma del espacio de iteraciones
al desplazar el trabajo por iteración. Modifica
los índices de los lazos originales, creando un
nuevo espacio de iteraciones
Otros
Alineación y replicación
Intenta transformar una
dependencia generada por el lazo
en una dependencia independiente
del lazo, sin distribuir el lazo
Destapar minas y unir lazos
Distribuye un largo lazo sobre diferentes
procesadores: el lazo más externo es
paralelizado, a cada procesador se le
asigna una instancia del lazo más interno
Partición de nodos
Trata de aislar las operaciones de una instrucción
que no participan en un ciclo de dependencia. De
esta forma, el ciclo de dependencia puede ser
roto, resultando en una paralelización
Encoger lazos
Desenrollar lazos
Hace una o más copias del cuerpo
del lazo. Reestructura el lazo,
escribiendo las iteraciones como
segmentos de código lineal