Computación Paralela 3-4

Computación Paralela

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

Next up

Computación Paralela 3-4

Description

Resource summary

Similar

	Created by klozknf almost 9 years ago