Zusammenfassung der Ressource
Computación
Paralela
- Problemas de planificación
- Estructuras
condicionales
- Lazos de ejecución
- 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