Sistemas Distribuidos y Paralelos Medio Curso

¿Qué es una computadora paralela?

Sistema con varios procesadores

¿Qué modelo describe una computadora secuencial tradicional?

Von Neumann

¿Quién propuso la taxonomía para clasificar arquitecturas de computadoras?

Flynn

¿Qué arquitectura usa una instrucción y un dato?

SISD

¿Qué arquitectura ejecuta una instrucción sobre múltiples datos?

SIMD

¿Qué arquitectura permite múltiples instrucciones y múltiples datos?

MIMD

¿En qué hardware es común el modelo SIMD?

GPU

¿Qué arquitectura se usa en CPUs multinúcleo modernas?

MIMD

¿Cómo se llama el multiprocesador con memoria compartida centralizada?

SMP

¿Qué paradigma usa envío y recepción de mensajes?

Message passing

¿Qué modelo teórico de memoria compartida se usa para analizar algoritmos paralelos?

PRAM

¿Qué modelo considera latencia y ancho de banda en comunicación?

LogP

¿Qué redes tienen conexiones fijas entre procesadores?

Estáticas

¿Qué redes crean conexiones bajo demanda?

Dinámicas

¿Qué red dinámica es considerada la más potente?

Barra Cruzada

¿Qué red dinámica usa menos conmutadores pero puede bloquearse?

Multietapa

¿Cómo se llama dividir un programa en tareas paralelas?

Paralelización

¿Qué proceso identifica el orden de ejecución de tareas?

Dependencias

¿Cómo se llaman tareas muy pequeñas en paralelización?

Granularidad fina

¿Cómo se llama cuando dos tareas escriben en la misma variable?

Dependencia de salida

¿Cuál es la función principal de los grafos?

Representar redes de comunicación y dependencias entre programas

¿Cuál es la diferencia principal entre un grafo dirigido y uno no dirigido?

En el dirigido las conexiones tienen dirección (flechas), mientras que en el no dirigido son simétricas (doble sentido)

¿En qué algoritmo de búsqueda se basa el método para crear un Ordenamiento Topológico?

Se basa en la Búsqueda en Profundidad (DFS)

¿Cuándo es mejor usar una Lista de Adyacencia en lugar de una Matriz y por qué?

Cuando el grafo es disperso (tiene pocas aristas), porque la Lista ahorra mucha memoria comparada con la Matriz

¿Por qué el gráfico de tareas debe ser acíclico?

Porque debe de representar un programa factible

Desenrollado

Es una técnica para crear un gráfico de tareas repitiendo los nodos y aristas del cuerpo de un bucle para cada iteración

Para realizar la técnica de "desenrollado" (unrolling) de un gráfico de flujo, es indispensable conocer el número total de iteraciones

Verdadero

El peso de un nodo o coste de cálculo puede ser cero

Falso

¿Cuál es la condición necesaria para que un programa sea considerado "factible" según su Grafo de Dependencia?

Que el grafo sea acíclico (sin ciclos)

¿Cuáles son los tres tipos de dependencia de datos que puede representar un DG?

Dependencia de flujo, antidependencia y dependencia de salida

En la representación gráfica, ¿qué indica una flecha con un pequeño círculo atravesándola?

Indica una dependencia de salida

¿Cómo se llama el grafo que se construye cuando no es posible determinar el vector de distancia exacto de una dependencia?

Grafo de dependencia conservador

¿Qué representa un nodo en un grafo de flujo?

Una tarea del programa que se ejecuta en cada iteración

¿Qué indica el valor D(e) en una arista?

El número de iteraciones de retardo en la comunicación

¿Puede un grafo de flujo tener ciclos?

Sí, siempre que tengan al menos una arista con retardo

¿Qué tipo de política usan las colas en el modelo dirigido por datos?

FIFO (primero en entrar, primero en salir)

¿Cómo se llaman los puntos que representan las tareas en el gráfico?

Nodos

¿Cómo se llaman las flechas que unen las tareas?

Bordes (o aristas)

¿Para qué proceso se utiliza principalmente el modelo DAG?

Planificación

¿Qué nombre recibe el tiempo que tarda una tarea en ejecutarse?

Peso (o costo)

Es el tiempo total que tarda en finalizar la última tarea de un programa paralelo. Representa el tiempo completo de ejecución del sistema.

Makespan

Bajo este modelo se asume que se tiene conocimiento total del programa, incluyendo el número de procesadores, los costos exactos de cómputo de cada tarea y los costos de comunicación entre ellas.

Modelo clásico

Implica que no existe un algoritmo conocido capaz de encontrar la solución perfecta de forma eficiente para todos los casos posibles.

NP-completo

Qué condición hace que el scheduling sin comunicación sí se pueda resolver en tiempo polinomial?

Tener procesadores ilimitados

¿Cómo se escribe la nomenclatura de “comunicación sin costo” en el grafo de tareas?

c(e)=0

¿Qué permite identificar la tabla de NODE LEVEL?

Qué tareas pertenecen al camino crítico

¿El camino crítico es siempre el camino más corto en un grafo de tareas?

Falso

¿El bottom level de un nodo incluye el peso (tiempo de ejecución) del propio nodo?

Falso

¿El top level de un nodo incluye el peso (tiempo de ejecución) del propio nodo?

Falso

¿Para que sirve la Granularity?

Analiza si el tiempo que una tarea pasa calculando es mayor o menor que el tiempo que pasa comunicándose con otras tareas

Es el tipo de comunicación donde el intercambio de datos es entre distintos procesadores y su costo es más elevado

Comunicación Remota

Es el momento más temprano en que una tarea puede iniciar en un procesador P, dependiendo de cuándo llegan todos los datos de sus predecesores.

Data Ready Time

¿Qué significa que la planificación sea "sin costos de comunicación"?

Que la transferencia de información de un procesador a otro es instantánea.

En este modelo, ¿cuándo está lista una tarea para empezar a ejecutarse?

Exactamente en el mismo instante en que terminan las tareas anteriores de las que depende, sin importar en qué procesador se hayan ejecutado.

En el ejemplo de la Figura 4.4, ¿por qué los nodos c y d pueden empezar inmediatamente en el tiempo 2?

Porque el nodo a (del que dependen) termina en el tiempo 2 y, al no haber retrasos por la red, c y d reciben los datos al instante para comenzar a trabajar.

¿Cómo se llama la técnica heurística dominante en la planificación de tareas que ordena los nodos de un grafo según un criterio de prioridad y luego los asigna a procesadores disponibles respetando las precedencias?

List Scheduling

¿Cómo se le llama a la asignación parcial de nodos a procesadores que se va construyendo durante el proceso de planificación?

Partial Schedule (programación parcial)

¿Cómo se denomina al nodo de un grafo de tareas cuyos predecesores ya terminaron su ejecución y que ya puede ser programado?

Free Node

¿Cómo se llama la técnica de asignación donde un nodo se coloca al final de las tareas que ya se ejecutan en un procesador?

End Technique

¿Cómo se denomina la técnica que permite colocar una tarea en un espacio libre dentro del calendario de ejecución para que pueda iniciar antes?

Insertion Technique

¿Cómo se llama el criterio que selecciona el procesador que permita que una tarea comience lo más pronto posible?

Minimización del tiempo de inicio (Start Time Minimization)

¿Cómo se denomina al tipo de algoritmo que toma en cada paso la mejor decisión local con el objetivo de obtener una buena solución global?

Algoritmo Greedy

¿Cómo se llaman las prioridades calculadas antes de iniciar el proceso de planificación y que no cambian durante la ejecución?

Prioridades estáticas

¿Cómo se llama la métrica que mide la longitud desde un nodo hasta un nodo final dentro de un grafo de tareas?

Bottom Level (bl)

¿Cómo se denomina la métrica que mide la longitud desde un nodo inicial hasta el nodo actual en un grafo de tareas?

Top Level (tl)

¿Cómo se llaman las prioridades que se recalculan en cada paso del proceso de planificación considerando el estado actual del scheduling?

Prioridades dinámicas

¿Cómo se denomina el algoritmo que combina el bottom level con el tiempo de inicio más temprano para decidir la asignación de tareas?

Dynamic Level Scheduling (DLS)

¿Cómo se llama el algoritmo que selecciona directamente el par nodo procesador con el menor tiempo de inicio posible?

Earliest Time First (ETF)

¿Cómo se denominan los algoritmos que agrupan nodos de un grafo de tareas en grupos para reducir costos de comunicación y mejorar la ejecución?

Algoritmos de agrupamiento (Clustering Algorithms)

¿Cómo se llama el algoritmo de agrupamiento que analiza una arista a la vez y decide si conviene fusionar las tareas que conecta en un mismo cluster?

Single Edge Clustering

¿Qué son las Técnicas de inserción?

Se refieren a cómo se asignan o colocan nuevas tareas, procesos o datos dentro de un conjunto de nodos ya activos, buscando optimizar rendimiento, balanceo de carga y uso de recursos.

¿En qué consiste la Inserción Round Robin?

Las tareas se asignan de forma secuencial y equitativa entre nodos disponibles

¿En qué consiste la Inserción Basada en Carga?

La nueva tarea se inserta en el nodo con menor carga actual (CPU, RAM o uso de red)

¿Qué es la Duplicación de Nodos?

Es una técnica que consiste en duplicar ciertos nodos en más de un procesador para reducir la comunicación entre ellos

¿Cuál es el objetivo de la Duplicación de Nodos?

Minimizar retraso por transferencia de datos y mejorar el paralelismo.

¿Qué son las Heurísticas de la Duplicación de Nodos?

Son reglas prácticas o algoritmos aproximados que ayudan a decidir qué nodos conviene duplicar

¿Cómo se define la heterogeneidad de Tipo 1 (Velocidad)?

Todos los procesadores tienen las mismas capacidades funcionales, pero operan a diferentes velocidades

¿Cómo se define la heterogeneidad de Tipo 2 (Funcionalidad)?

Los procesadores tienen capacidades distintas; algunas tareas solo pueden ejecutarse en procesadores específicos (común en sistemas embebidos)

¿En qué modelo de los sistemas heterogéneos, la relación de velocidad es constante?

Los Sistemas Consistentes

¿Cómo se define el Costo de Computación en sistemas heterogéneos?

El peso de un nodo se redefine como el promedio de los tiempos de ejecución en todos los procesadores

En la clasificación (α|β|γ), ¿qué especifica el campo α (Alpha)?

Especifica el entorno del procesador

¿Qué son los Algoritmos Genéticos?

Son algoritmos de búsqueda que se basan en los conceptos de la evolución y genética natural.

¿Cuáles son los componentes fundamentales de los Algoritmos Genéticos?

Cromosoma, Población, Evaluación, Selección, Cruzamiento, Mutación

¿Qué es la Representación Indirecta de un cromosoma?

En esta representación el string de cromosomas contiene información que sirve como la entrada para que la heurística cree una programación

¿Qué es la Mutación en algoritmos genéticos?

El operador que cambia aleatoriamente partes de un cromosoma para evitar convergencia