| j18-ago,v19-ago | Video |
|---|---|
Crear repositorio personal. IDE. Plugin para pseudocódigo |
1. Paradigmas de programación concurrente y distribuido
| j18-ago,v19-ago | Video |
|---|---|
Proceso de resolución de problemas |
|
Paradigmas de programación |
|
Paradigmas de programación (cont.) |
|
Serial vs concurrente vs paralelo |
|
Concurrencia basada en eventos |
|
Concurrencia multihilo |
|
Distribución simétrica. Clústers |
|
Distribución asimétrica. Mallas. Comparación con simétrica. |
|
Concurrencia heterogénea. Aceleración por hardware |
|
Incremento del desempeño (paralelismo de datos). Separación de asuntos (concurrencia de tareas) |
2. Concurrencia compartida imperativa (Phtreads)
La concurrencia de estado compartido, concurrencia de recursos compartidos, o simplemente concurrencia compartida ocurre cuando varios trabajadores (hilos de ejecución) realizan una tarea concurrentemente y pueden acceder a regiones compartidas de memoria porque están dentro del mismo espacio de direcciones de memoria del proceso.
Los hilos de ejecución siguen este esquema, dado que comparten todos los segmentos del proceso (código, datos, y memoria dinámica), excepto el segmento de pila. Por ejemplo, un dato que un hilo escriba en la memoria compartida, otro hilo puede leerlo inmediatamente, sin tener que depender de la intervención del sistema operativo. De esta forma, la memoria compartida se convierte en un mecanismo directo de comunicación entre los hilos de ejecución.
Se estudiarán en el curso dos tecnologías para implementar concurrencia compartida: Pthreads y OpenMP. Los POSIX Threads es un estándar que permite a los desarrolladores crear y controlar hilos de ejecución en los sistemas operativos basados en Unix.
2.1. Hilo de ejecución (execution thread)
2.1.1. Hola mundo con hilos
Escriba un programa que al correr cree dos hilos, el principal y uno secundario. Ambos hilos deben saludar en la salida estándar con el mensaje "Hello from main thread" y "Hello from secondary thread" respectivamente. Utilice un analizador dinámico de código como las herramientas memcheck y helgrind de Valgrind, o los Google Sanitizers, para asegurarse de que su programa no provoca condiciones de carrera.
| L22-ago,k23-ago | Video |
|---|---|
Ejemplo Hello: Diseño en pseudocódigo |
|
Notación de pseudocódigo (ocho tipos de instrucciones) |
|
Creación de threads en pseudocódigo |
|
Ptheads = POSIX threads |
|
Convertir pseudocódigo en comentarios usando expresiones regulares |
|
Implementación del hola Pthread. pthread_create(). Error estándar |
|
Compilar el código. Compilador, preprocesador, enlazador |
En la siguiente solución se incluye además un archivo de reglas Makefile que permite a un desarrollador compilar el código fuente sin tener que recordar los argumentos con los que se debe invocar al compilador. Bastará que el programador emita el comando make en la carpeta, y éste invocará al compilador siguiendo la primera regla estipulada en el Makefile.
| Archivo | Descripción | Cambios |
|---|---|---|
Diseño en pseudocódigo de la solución. |
||
Implementación en Pthreads. Dice "hola mundo" desde el hilo principal y desde un hilo secundario. |
||
Un archivo para compilar el código fuente sin tener que recordar los argumentos de invocación al compilador. También permite correr pruebas durante el desarrollo como quitar pelusas (linting), revisar accesos inválidos y fugas de memoria ( |
2.1.2. Herramientas
Para instalar el compilador (GCC), el analizador estático de código (cpplint), el analizador dinámico de código (valgrind), y el compilador Clang que instrumenta código con sanitizers, puede instalar los siguientes paquetes en un Linux basado en Debian:
sudo apt update
sudo apt install build-essential python3-pip valgrind clang
sudo pip3 install cpplintPara compilar con GCC –o un compilador compatible– código fuente que use Pthreads, se necesita el parámetro -pthread:
cc -g -Wall -Wextra hello.c -o hello -pthread
echo hello > .gitignore
git add hello.c .gitignoreRecuerde siempre ignorar los ejecutables en su repositorio de control de versiones. Para ello, cree o agregue a su archivo .gitignore el nombre del ejecutable. Luego agregue el código fuente y el .gitignore a control de versiones. Los dos últimos comandos de arriba hacen este trabajo. La Figura 3 muestra el resultado final de rastrear la memoria durante la ejecución del código.
| L22-ago,k23-ago | Video |
|---|---|
Tool1: El compilador. Habilitar warnings |
|
Tool2: Linter (cpplint). Análisis estático de código. |
|
Tool3: Memcheck de Valgrind: errores de memoria (fugas, accesos inválidos…) |
|
Makefiles |
|
Tool4: Helgrind de Valgrind: errores de concurrencia (condiciones de carrera…) |
|
Tool5: Address Sanitizer (ASan) de Google para fugas y accesos inválidos |
|
Tool6: Memory Sanitizer (MSan) de Google para memoria no inicializada |
|
Tool7: Thread Sanitizer (TSan) de Google para errores de concurrencia |
|
Tool8: Undefined Behavior Sanitizer (UBSan) de Google para comportamientos inesperados |
|
Corregir el thread leak. |
2.1.3. Rastreo de memoria
| j25-ago,v26-ago | Video |
|---|---|
Indeterminismo. |
|
Rastreo de memoria. Cargado del proceso. Segmento de código. Segmento de datos |
|
Creación del hilo principal. El ambiente de ejecución del lenguaje (crt0) |
|
Invocación de |
|
Crear un nuevo hilo. Start routine. Stack pointer |
|
Estado ready y estado running de un hilo de ejecución |
|
Colas de espera. Reanudar la ejecución |
|
Estado terminated. |
|
Definición de hilo de ejecución. Metáfora de hilo |
2.2. Indeterminismo (indeterminism)
2.2.1. Hola mundo múltiple
Modifique el programa de "hola mundo" para crear una cantidad arbitraria de hilos de ejecución. Cada uno de los cuales imprime "Hello from secondary thread i" en la salida estándar y termina su ejecución. Permita al usuario indicar la cantidad de hilos de ejecución como argumento de la línea de comandos. Si este argumento se omite, suponga la cantidad de CPUs disponibles en el sistema.
| L29-ago, k30-ago | Video |
|---|---|
Actividad hello_w. Copiar hello/ a hello_w/. Archivo .gitignore. |
|
Variables y funciones en Makefile |
|
Solución en pseudocódigo de hello_w. |
|
Argumentos en línea de comandos. Espacios e interpolación en argumentos. |
|
Implementación de pseudocódigo. Conversión texto a número con |
|
Corregir vulnerabilidad índice fuera de rango. Programación defensiva. |
|
Desborde de pila por arreglo variable automático (vulnerabilidad). Memoria dinámica. |
|
Corregir fuga de memoria. |
|
Serialización por join |
|
Concepto de indeterminismo |
|
Correr herramientas de validación. Falsos positivos de helgrind |
|
Linter. Enteros de tamaño fijo. Filtrar reglas del linter |
|
Obtener la cantidad de CPUs disponibles con |
| Archivo | Descripción | Cambios |
|---|---|---|
Diseño en pseudocódigo de la solución. |
|
|
Varios threads dicen "hola mundo" junto con el hilo principal. |
|
|
El Makefile usa unas pocas variables nombradas, variables automáticas, y funciones. Por ejemplo para especificar banderas del compilador, el nombre del ejecutable, y archivos de compilación. |
|
2.3. Memoria privada (private memory)
2.3.1. Hola mundo numerado
Cree una nueva versión de su programa "hola mundo" donde cada thread imprime "Hello from secondary thread i of w", donde i es el número de thread y w la cantidad total de hilos creada. Está prohibido usar variables en el segmento de datos (globales, estáticas, externas). Cree un registro de memoria (estructura) privado para cada thread.
| 01-set, 02-set | Video |
|---|---|
Modularización del ejemplo |
|
Makefile para uso de los ejemplos, tareas, y proyectos del curso |
|
Diferencia entre la concurrencia de tareas y el paralelismo de datos en pseudocódigo |
|
Implementación de memoria privada (parte 1): Thread team. Registros de memoria. |
|
Implementación de memoria privada (parte 2): |
|
Validar código. Ejercicio para la casa: |
| Archivo | Descripción | Cambios |
|---|---|---|
Diseño en pseudocódigo de la solución. |
|
|
Varios threads saludan indicando su identificador y tamaño del equipo en la salida estándar. |
|
|
A partir de este ejemplo se usa un |
2.4. Memoria compartida (shared memory)
2.4.1. Hola mundo numerado (memoria compartida)
Cree una nueva versión de su programa "hola mundo numerado" donde cada hilo de ejecución imprime "Hello from secondary thread i of w", donde i es el número de hilo y w la cantidad total de hilos que componen el equipo, pero con los siguientes cambios:
-
Haga que los datos comunes para todos los hilos de ejecución (el número
w) estén en un registro (estructura) compartido para cada hilo. Mantenga los datos exclusivos para cada hilo (i) se mantengan en el registro privado. -
Reporte la duración en segundos que los hilos toman en saludar. Puede usar la función POSIX
clock_gettime()de<time.h>.
| 01-set, 02-set | Video |
|---|---|
Ejemplo |
|
Memoria compartida en pseudocódigo. La declaración |
|
Implementación de la memoria compartida en Pthreads |
| Archivo | Descripción | Cambios |
|---|---|---|
Diseño en pseudocódigo de la solución. |
|
|
Varios threads saludan indicando su identificador en la salida estándar. |
|
|
Facilita la construcción y prueba de la la solución. |
El código en este ejemplo es de suma importancia, porque es el código base para crear programas concurrentes con Pthreads. Este código permite a los hilos tanto compartir memoria como tener su propia memoria privada de trabajo sin incurrir en malas prácticas como el uso de variables globales.
2.5. Espera activa (busy waiting)
2.5.1. Hola mundo ordenado
Haga que los threads saluden siempre en orden. Es decir, si se crean w threads, la salida sea siempre en orden
Hello from thread 0 of w Hello from thread 1 of w Hello from thread 2 of w ... Hello from thread w of w
Utilice espera activa como mecanismo de sincronización (control de concurrencia).
Ejecute varias veces su solución de hello_order_busywait con la cantidad máxima de threads que el su sistema operativo le permite. ¿Es consistente la duración de su solución con espera activa?
Describa el comportamiento del programa y explique la razón de este comportamiento en el archivo readme.md dentro de su carpeta hello_order_busywait. Indique en qué condiciones sería apremiante utilizar espera activa, o en caso de no haberlas, sugiera soluciones alternativas.
La espera activa (busy waiting) es un ciclo que hace a un hilo de ejecución esperar repetitivamente hasta que una condición se haga falsa. Por ejemplo, si la variable next_thread indica el número del próximo thread que puede realizar una tarea que debe ser serializada en orden, el código
// Wait until it is my turn
while (next_thread < my_thread_id) {
// busy-wait
}
// Do the ordered-task here
task();
// Allow subsequent thread to do the task
++next_thread;| 05-set, 06-set | Video |
|---|---|
Medir tiempo de pared. CPU time. SO de tiempo real. División entera |
|
Espera activa (busy waiting). Pseudocódigo de hello_order_busywait |
|
Implementación y ejecución de espera activa con Pthreads |
|
Explicación del efecto en tiempo de ejecución de la espera activa |
| Archivo | Descripción | Cambios |
|---|---|---|
Diseño en pseudocódigo de la solución. |
|
|
Varios threads saludan en orden gracias a la espera activa, pero a costa de un consumo injustificado de recursos. |
|
|
Facilita la construcción y prueba de la la solución. |
2.6. Condición de carrera y exclusión mutua (race condition, mutex)
2.6.1. Posición en la carrera
Modifique su solución a Ejemplo 5 para implementar una carrera de hilos de ejecución. Cada vez que un hilo llega a la meta, lo avisa en la salida estándar, como ocurre en la siguiente corrida hipotética:
Thread 0/4: I arrived at position 1 Thread 2/4: I arrived at position 2 Thread 1/4: I arrived at position 3 Thread 3/4: I arrived at position 4
Note que las posiciones tienen que aparecer en orden, mientras que el número de cada hilo es indeterminístico. Utilice algún mecanismo de control de concurrencia para que el reclamo de la posición sea el correcto.
| 05-set, 06-set | Video |
|---|---|
Ejemplo |
|
Ejemplo |
|
Definición de condición de carrera (data race o race condition) |
|
Exclusión mutua (mutex o candado). Región crítica. Metáfora del puente angosto |
|
Repaso de la lección previa: exclusión mutua |
|
Implementación de mutex en Pthreads. Imprimir en la región crítica |
|
Liberar el mutex ( |
|
Mutex debe proteger todos los accesos a la variable, no sólo escritura |
|
Múltiples regiones críticas |
|
Olvidar liberar un mutex ("el proceso bello durmiente") |
| Archivo | Descripción | Cambios |
|---|---|---|
Diseño en pseudocódigo de la solución. |
|
|
Varios threads compiten en una carrera, y reportan el orden en que llegan a la meta. Utilizan exclusión mutua cuando llegan a la meta para incrementar la variable contadora correctamente y para evitar la condición de carrera en la impresión en la salida estándar. |
|
|
Facilita la construcción y prueba de la la solución. |
2.7. Semáforos
La definición original de semáforo por Dijkstra puede variar ligeramente de algunas implementaciones. Para Dijkstra un semáforo es un entero con signo, con tres características:
-
Cuando se crea un semáforo, éste se inicializa con un entero cualquiera (negativo, cero, o positivo). Pero después de inicializado las únicas dos operaciones que están permitidas es incrementar en uno (signal) y decrementar en uno (wait) al semáforo. No se puede leer el valor actual del semáforo.
-
Cuando un hilo decrementa un semáforo, si el resultado es negativo, el hilo es bloqueado y no puede continuar hasta que otro hilo incremente el semáforo.
-
Cuando un hilo incrementa un semáforo, si hay otros threads esperando, uno de ellos será desbloqueado. Tanto el hilo que incrementa el semáforo como el que fue desbloqueado siguen ejecutándose concurrentemente. Si hay varios hilos esperando, no hay forma de saber cuál de ellos será el desbloqueado por el scheduler del sistema operativo. El programador no tiene forma de saber si al incrementar un semáforo, se desbloqueará o no un hilo en espera, dado que no se puede leer el valor actual del semáforo por la regla 1.
El valor actual de un semáforo indica lo siguiente. Si el valor es positivo indica la cantidad de hilos que pueden decrementar el semáforo sin bloquearse. Si es negativo indica la cantidad de hilos que están bloqueados esperando actualmente por el semáforo. Si el valor es cero, indica que no hay hilos esperando por el semáforo, pero si un thread trata de decrementarlo, será bloqueado.
Algunas implementaciones, por ejemplo POSIX, permiten probar la espera (sem_trywait). Esta función nunca bloquea al hilo que la invoca. Si se trata de esperar un semáforo que tiene un valor positivo, se decrementará el semáforo y el hilo continuará ejecutándose como una invocación normal a wait(). Pero si se trata de esperar por un semáforo que quedaría en un valor negativo, la función sem_trywait() no decrementa al semáforo ni bloquea al hilo, sino que retorna de inmediato indicando un código de error (por ejemplo, -1). Dado que el hilo mantiene su ejecución, quien programa puede decidir condicionando (if) el valor de retorno del sem_trywait() y tomar distintas acciones que realice el hilo cuando se pudo o no esperar por el semáforo.
En los siguientes ejemplos se seguirá la definición original de Dijkstra, que no permite probar la espera. Se usará pseudocódigo con la siguiente sintaxis para los hilos y semáforos, con el fin de centrar la atención en estos temas y no en detalles de implementación de una tecnología particular (ej.: Pthreads):
sem := create_semaphore(3) // Create a semaphore with initial value 3
signal(sem) // Increment and wake a waiting thread if any
wait(sem) // Decrement and block if the result is negative2.7.1. Hola mundo ordenado (semáforos)
Al igual que Ejemplo 5, haga que los threads saluden siempre en orden. Es decir, si se crean w threads, la salida sea siempre en orden
Hello from thread 0 of w Hello from thread 1 of w Hello from thread 2 of w ... Hello from thread w of w
Utilice una colección de semáforos como mecanismo de sincronización (control de concurrencia).
| 08-set, 09-set | Video |
|---|---|
Definición original de semáforo (Dijkstra) |
|
Metáfora de semáforo |
|
Usar un arreglo de semáforos para imponer orden |
|
Repaso: mutex, semáforo. Futex (fast userspace mutex) |
|
Ejemplo |
|
Semáforos en POSIX. Semáforos de memoria. Semáforos nombrados |
|
|
|
Corrección de errores en |
| Archivo | Descripción | Cambios |
|---|---|---|
Diseño en pseudocódigo de la solución. |
|
|
Utiliza una colección de semáforos, uno para cada hilo de ejecución. Sólo el semáforo para el hilo 0 está inicialmente en verde. Cuando un hilo pasa su semáforo, saluda en la salida estándar, y luego enciende el semáforo del siguiente. De esta forma, las impresiones se hacen en orden. Esta solución tiene una limitación de la cantidad de hilos que se pueden crear. |
|
|
Facilita la construcción y prueba de la la solución. |
2.7.2. Ejercicios
Suponga usted va a construir el edificio para su organización. Para que quede lo mejor posible, usted sólo va a contratar una persona especializada para cada tarea del proceso de construcción. Estas tareas están expresadas en el siguiente grafo de tareas.
En un grafo de tareas (task graph) los nodos son tareas de un proceso a realizar, y los vértices son dependencias. Un vértice dirigido de A hacia B indica que la tarea A debe completarse para poder iniciar la tarea B, dado que la salida o productos generados por la tarea A son requeridos por la tarea B. Una tarea puede iniciarse sólo si todas sus dependencias han sido completadas. Dos o más tareas en esta condición pueden realizarse en paralelo.
Se modeló esta situación en un programa concurrente. El maestro de obras (foreman) es el hilo principal que contrató a cada albañil experto. Cada albañil (builder) reporta en la salida estándar cuando inicia su labor. Luego representa el tiempo dedicado con una espera aleatoria. Una vez que finalizada su labor, lo reporta en la salida estándar.
Sin embargo hay un problema con el programa. Una vez que es ejecutado, todos los albañiles inician sus tareas de inmediato, sin respetar las dependencias del grafo de tareas. Por ejemplo, el experto en pintura exterior comienza a pintar las paredes que aún no se han construido. Por favor, corrija esta irrealista situación para que la simulación logre construir el edificio acorde a las dependencias. El programa será correcto cuando no haya forma de que un albañil inicie su actividad antes de que todas sus dependencias hayan sido completadas.
2.8. Seguridad condicional (conditionally safe)
2.8.1. Hola mundo ordenado con seguridad condicional
Al igual que Ejemplo 7, haga que los threads saluden siempre en orden. Es decir, si se crean w threads, la salida sea siempre en orden
Hello from thread 0 of w Hello from thread 1 of w Hello from thread 2 of w ... Hello from thread w of w
Evite (si es posible) el control de concurrencia, es decir, trate de usar seguridad condicional (conditionally safe).
| 08-set, 09-set | Video |
|---|---|
Seguridad condicional (conditionally safe) |
|
|
|
|
| Archivo | Descripción | Cambios |
|---|---|---|
Diseño en pseudocódigo de la solución. |
|
|
Imprime en orden sin usar mecanismos de control de concurrencia. Usa una estructura de datos (un arreglo) donde cada hilo de ejecución escribe sus resultados sin afectar a los demás. El hilo principal se encarga de la tarea secuencial de imprimir. |
|
|
Facilita la construcción y prueba de la la solución. |
2.9. Problema del productor-consumidor
El problema del productor-consumidor en computación es un problema clásico de control de concurrencia, propuesto por Edsger Dijkstra. Se suele presentar de forma semi-concreta, lo que ayudar a identificar otros contextos donde su solución se puede aplicar. Hay dos variantes, una de buffer acotado y otra de buffer no acotado. De ambas se puede generalizar un patrón de software que puede enriquecerse con otros paradigmas de programación como el genérico y orientado a objetos.
2.9.1. Problema de buffer acotado
El problema del productor-consumidor lo tienen dos entes concurrentes, uno que produce algo que el segundo consume. Ambos tienen acceso a un espacio finito (acotado) donde se alojan los productos, comúnmente llamado buffer y de naturaleza circular. Dado que los entes son concurrentes, uno está agregando productos al buffer mientras el otro está al mismo tiempo consumiéndolos (o quitándolos) del buffer.
El problema surge cuando ambos entes actúan a diferente velocidad. Si el consumidor es más rápido que el productor, podría consumir productos que aún no se han colocado en el buffer. Si el productor es más rápido que el consumidor, lo alcanza y sobrescribe productos que el consumidor aún no ha procesado.
El problema se resuelve cuando el consumidor procesa todos los productos y en el mismo orden en que el productor los genera. Al igual que ocurre con seres humanos, la solución implica imponer espera. Si el consumidor es más veloz, vaciará el buffer y deberá esperar a que el productor genere el próximo producto. Si el productor es más veloz y satura el buffer, deberá esperar a que el consumidor libere al menos un espacio para poder continuar produciendo.
Cree una simulación del productor-consumidor. Su programa recibirá seis argumentos en la línea de comandos:
-
El tamaño del buffer.
-
La cantidad de rondas, vueltas, o veces que se debe llenar y vaciar el buffer.
-
La duración mínima en milisegundos que el productor tarda en generar un producto.
-
La duración máxima en milisegundos que el productor tarda en generar un producto.
-
La duración mínima en milisegundos que el consumidor tarda en consumir un producto.
-
La duración máxima en milisegundos que el consumidor tarda en consumir un producto.
El programa debe crear un buffer para almacenar productos identificados por números secuenciales iniciando en 1. Por ejemplo, si se piden 2 rondas con un buffer de tamaño 3, el 4 identificará el primer producto de la segunda ronda.
Generar un producto no es inmediato. El tiempo que el productor tarda depende de la naturaleza del contexto en que se aplique el problema del consumidor-productor. Para efectos de la simulación, los argumentos 3 y 4 sirven de rango para generar números pseudoaleatorios. Cada vez que el productor tiene que construir un producto, se generará una duración pseudoaletoria y el productor esperará esta cantidad de milisegundos, simulando hasta que el producto esté acabado. Luego el productor agrega el producto al buffer e imprime en la salida estándar el texto i generated, donde i es el número de producto.
Una vez que el consumidor extrae un producto del buffer imprime en la salida estándar el texto Consuming i y se dispone a consumir. Consumir un producto no es inmediato. El tiempo que el consumidor tarda se genera también en forma pseudoaletoria con los argumentos 5 y 6. Sugerencia: indente la salida del consumidor para distinguirla de la salida del productor.
En el siguiente ejemplo de ejecución, los entes hacen dos rondas llenando y consumiendo un buffer de 3 elementos. El productor es rápido y tarda máximo 100ms creando un producto. El consumidor es más lento y podría tardar máximo 750ms consumiendo un producto. Como se puede ver en la salida, el productor rápidamente llena el buffer y debe esperar a que el consumidor libere espacio en el buffer para continuar produciendo. En la salida se comprueba que el consumidor procesa todos los datos generados por el productor y en el mismo orden.
$ ./producer_consumer 3 2 0 100 0 750 Produced 1 Produced 2 Produced 3 Consuming 1 Produced 4 Consuming 2 Produced 5 Consuming 3 Consuming 4 Consuming 5 Produced 6 Consuming 6
Puede usar el siguiente código no modularizado como punto de partida para su solución:
| Archivo | Descripción |
|---|---|
Diseño inicial en pseudocódigo |
|
Implementación inicial en C sin modularización |
| Archivo | Descripción | Cambios |
|---|---|---|
Diseño en pseudocódigo de la solución. |
|
|
Simula el problema con un productor y un consumidor que comparten un buffer acotado. |
|
|
Facilita la construcción y prueba de la la solución. Usa la variable |
|
| L12-set, k13-set | Video |
|---|---|
Análisis del problema del productor-consumidor de buffer acotado |
|
Ejecutar el código dado |
|
Comprensión del pseudcódigo dado |
|
Idear una solución con dos semáforos |
|
Solución en pseudocódigo |
|
Comprensión del código en C dado |
|
Implementación y ejecución de la solución con Pthreads |
2.9.2. Problema de buffer no acotado
Dijkstra publicó una segunda versión del problema del productor-consumidor que elimina las limitaciones del buffer acotado. En esta versión, el buffer tiene memoria infinita, hay una cantidad arbitraria de productores, y una cantidad arbitraria de consumidores. Al igual que el anterior, el problema se resuelve si todos los consumidores procesan todos los productos en el mismo orden en que los productores los generan.
Modifique la simulación del problema productor-consumidor generalizando las siguientes restricciones.
-
El buffer no es acotado, sino de tamaño arbitrario o dinámico, definido por los límites de memoria del sistema.
-
No existe el concepto de ronda. El primer argumento de línea de comandos indica la cantidad de productos a simular. Identifique los productos en orden secuencial.
-
Varios productores, indicados por el usuario en el segundo argumento de línea de comandos.
-
Varios consumidores, indicados por el usuario en el tercer argumento de línea de comandos.
-
Cada productor y consumidor indica su número en la salida estándar.
El siguiente ejemplo de ejecución simula la construcción de 5 unidades de trabajo por 2 productores que tardan entre 0 y 100 milisegundos en producir, y 3 consumidores que tardan entre 0 y 750 milisegundos en consumir.
$ ./producer_consumer 5 2 3 0 100 0 750 0 produced 1 1 produced 3 1 consuming 1 0 produced 2 2 consuming 3 0 produced 5 0 consuming 5 1 consuming 2 1 produced 4 2 consuming 4
Note que no necesariamente los productos se generan en orden secuencial, debido al indeterminismo de los productores. Recuerde, el problema está resuelto si todos los consumidores procesan todos los productos en el mismo orden en que los productores los generan. Puede usar el siguiente código modularizado como punto de partida para su solución:
| Archivos | Descripción |
|---|---|
Contiene a todos los demás |
|
Diseño preliminar en pseudocódigo de la solución. |
|
Instancia e inicia la simulación |
|
Implementa el controlador de la simulación |
|
Código común usado entre todos los componentes de la simulación |
|
Implementa una cola de enteros |
|
Rutina de inicio de un hilo productor |
|
Rutina de inicio de un hilo consumidor |
| j15-set, v16-set Diseño | Video |
|---|---|
Poblema del Productor-consumidor de buffer acotado. Archivos dados. Makefile v2.2.2 |
|
Comprender el pseudocódigo dado |
|
Rastreo de procesamiento. Encontrar las condiciones de carrera |
|
Hacer la cola thread-safe usando exclusión mutua |
|
Corregir productores usando variables contadoras (variante 0) |
|
Corregir productores usando ciclo infinito (variante 1) |
|
Corregir consumidores usando variables contadoras y ciclo infinito (variante 1) |
|
Evitar que los consumidores extraigan de la cola si está vacía |
|
Rastreo rápido de procesamiento de los consumidores con variables contadoras (variante 1) |
|
Consumidores con variables contadoras y espera activa (variante -2) |
|
Detener consumidores cuando la cola está vacía y los productores terminaron (variante 2) |
|
Repaso. Numerar las variantes de productor y consumidor |
|
Detener consumidores usando un valor centinela (variante 3) |
| 15-set, 16-set Implementación | Video |
|---|---|
Comprender el código C dado |
|
Implementación de la cola thread-safe: |
|
Cola thread-safe: |
|
Cola thread-safe: |
|
Cola thread-safe: |
|
Cola thread-safe: |
|
Cola thread-safe: ¿Debería |
|
Implementación de la variante 1 de los productores en Pthreads |
|
Implementación de la variante 1 de los consumidores en Pthreads |
| Archivo | Descripción | Cambios |
|---|---|---|
Variante 0: Detiene a los productores con variables contadoras y redundancia de código. Incluye también una variante de consumidor con espera activa a modo de ejemplo de una solución que no es aceptable. |
|
|
Variante 1: Detiene a los productores y consumidores con variables contadoras |
|
|
Variante 2: Detiene a los consumidores con cuando la cola está vacía y los productores han terminado de producir. |
|
|
Variante 3: Detiene a los consumidores con un valor especial en la cola que indica la condición de parada |
|
|
Inicia la ejecución de la simulación. |
||
Realiza la simulación del productor-consumidor de buffer no acotado |
|
|
Código común usado entre todos los componentes de la simulación |
|
|
Implementa una cola thread-safe de productos (números enteros) |
|
|
Realiza la simulación del productor-consumidor de buffer no acotado |
|
|
Realiza la simulación del productor-consumidor de buffer no acotado |
|
|
Facilita la construcción y prueba de la la solución. Actualizado a la versión 2.2.2 |
|
2.9.3. Patrón productor-consumidor
La solución al problema del productor-consumidor es aplicable a una cantidad significativa de contextos. El código siguiente trata de generalizar la solución para que pueda ser reutilizada. Para esto se aprovechan mecanismos de reutilización de código provistos por paradigmas de programación como el orientado objetos (herencia y polimórfismo) y programación genérica (plantillas en C++). Se aplican otros patrones como el modelo-vista-controlador y singleton.
| Archivo | Descripción | Cambios |
|---|---|---|
Carpeta con los archivos fuente que simulan una red de un productor, un repartidor, y una cantidad de consumidores dada por argumentos de línea de comandos. Incluye el código para crear un servidor web, base para el |
||
Comprimido que incluye los archivos de la carpeta anterior. |
La subcarpeta prodcons/ contiene las clases base genéricas reutilizables en otros contextos en particular:
-
Thread: Clase abstracta que facilita crear hilos de ejecución. Se debe crear una clase hija que sobrescriba el métodorun(), el cual se invocará en un hilo aparte cuando se le invoquestartThread(). -
Semaphore: Encapsula un semáforo POSIX, dado questd::counting_semaphorerequiere compiladores modernos con C++20. -
Producer: Clase base abstracta genérica para crear hilos productores. Se debe heredar y sobrescribir el métodorun()heredado deThread. -
Consumer: Clase base abstracta genérica para crear hilos consumidores. Se debe heredar y sobrescribir el métodorun()heredado deThready el métodoconsume()que se invoca cada vez que el consumidor logra extraer un dato de la cola de consumo. -
Assembler: Es un hilo que consume de una cola que produce en otra cola. -
Dispatcher: Es un hilo que consume de una cola y reparte a varias colas usando valores llave.
El código provisto ofrece un ejemplo en el que se usa las clases genéricas anteriores. Se trata de una simulación de una red, donde un productor genera paquetes dirigidos a una cantidad arbitraria de consumidores. Un repartidor intermediario se encarga de redirigir los paquetes de red a su correspondiente destinatario.
El código provisto contiene un servidor web serial que puede ser paralelizado mediante una cadena de producción, y por lo tanto, la intervención de varios hilos productores y consumidores. Este es el objetivo del proyecto01 del curso.
| L19-set, k20-set | Video |
|---|---|
Patrón productor-consumidor. Ejecución de la simulación de red |
|
Principio del patrón productor-consumidor. Flow-based programming paradigm |
|
Repaso del patrón modelo-vista-controlador (MVC) |
|
Controlador de la simulación de red |
|
Controlador de la simulación de red (repaso) |
|
Clase abstracta genérica |
|
Clase abstracta |
|
Plantilla |
|
Clase abstracta genérica |
|
Clase abstracta genérica |
|
Clase abstracta genérica |
Modifique el código de la simulación de red para introducir pérdida de paquetes. Reciba un parámetro más en línea de comandos que corresponde a la probabilidad de perder paquetes, como un porcentaje en precisión flotante. Implemente un hilo ensamblador que es uno de los destinos del repartidor, como se ve en el siguiente diseño de flujo de datos.
Por cada paquete que este hilo ensamblador recibe, se genera un número flotante pseudoaleatorio entre 0 y 100. Si este número generado es menor que la probabilidad de pérdida de paquetes, el hilo descarta el paquete, de lo contrario, modifica al azar el destino del paquete, y lo pone de regreso en la cola entre el productor y el repartidor.
Tome en cuenta que el hilo ensamblador que extravía paquetes no es parte de la cantidad de consumidores. El siguiente podría ser un ejemplo de ejecución con dos consumidores, y un ensamlador que extravía aproximadamente la mitad de los paquetes que recibe. La otra mitad son redirigidos a los dos consumidores.
bin/network_simul_packet_loss 1000 2 1 -2 0 50
Info Producer 1000 messages sent
Info Consumer 416 messages consumed
Info Consumer 404 messages consumed
Info Assembler 180 messages lost2.9.4. Servidor web concurrente (proyecto 1)
| L19-set, k20-set | Video |
|---|---|
Objetivo del proyecto. Estructura del código dado. Correr el servidor web |
|
Servidor web vs aplicación web. Interfaz de un servidor |
|
El servidor web (clase |
|
Iniciar el servidor (método |
|
Establecimiento de la conexión |
|
Mensaje de solicitud y de respuesta. Ciclo de atención de solicitudes. Lista de to-do |
|
Metáfora del food court. Tomador de órdenes ( |
|
Avances del proyecto 1 explicados en la cadena de producción |
|
Enrutamiento web. HTML. Solicitud HTTP. Respuesta HTTP |
|
La aplicación web de factorización de números |
3. Paralelismo de datos
3.1. Optimización
La optimización es una etapa normalmente opcional del proceso de resolución de problemas (Figura 6), que surge cuando las implementaciones no logran satisfacer los requerimientos de eficiencia de los usuarios. Consiste regresar a la fase de diseño, y encontrar un modelo solución más eficiente. Este modelo típicamente es más elaborado, complejo, con un efecto de hacer más difícil de comprender al código o hacerlo más dependiente de un contexto, por lo que debe tenerse el cuidado de que exista un retorno de la inversión. Resulta muy apremiante realizar esta fase del proceso de resolución de problemas de forma sistemática, por lo que se propone un Método sugerido para optimizar.
| L19-set, k20-set | Video |
|---|---|
Motivación al paralelismo de datos |
|
Optimización. Método sugerido para optimizar |
|
Repaso de optimización |
3.2. Descomposición
En un problema, la descomposición es identificar las tareas o unidades de trabajo que se pueden realizar de forma independiente, y por lo tanto, de forma paralela. Una vez definidas, las tareas se consideran unidades indivisibles de computación. Es seguido por el mapeo, que consiste en asignar esas unidades de trabajo a los ejecutantes (procesos o hilos de ejecución). Esta sección resume conceptos teóricos de la descomposición de acuerdo a (Grama, Gupta, Karypis, y Kumar. Introduction to Parallel Computing 2ed, 2003) y el mapeo se estudia en la sección siguiente.
La granularidad (granularity) de la descomposición es la cantidad y tamaño de las tareas en la que un problema es descompuesto, y puede ser:
-
Granularidad fina (fine-grained) cuando se definen muchas tareas pequeñas. Tiende a incrementar el grado de concurrencia, pero también, la interacción entre tareas (ejecutantes), es decir, compoartir datos, trabajo, o información de sincronización.
-
Granularidad gruesa (coarse-grained) cuando se definen pocas tareas grandes. Disminuye la interacción entre ejecutantes, pero reduce el grado de concurrencia.
Existen algunas técnicas que pueden emplearse para definir las unidades de descomposición, entre las que se pueden citar:
-
Descomposición recursiva (recursive decomposition) es una forma de divide y vencerás. Un problema o tarea se divide en subproblemas o subtareas que se pueden realizar de forma concurrente. Cada una de estas se subdividen en otros subproblemas o subtareas y así sucesivamente. Por ejemplo, quicksort es un algoritmo que se puede paralelizar de esta manera. Cada vez que se subdivide el vector en dos, el ejecutante se encarga de un trozo y crea otro ejecutante que se encarga del otro trozo del arreglo.
-
Descomposición de datos (data-decomposition) se usa con grandes estructuras de datos. Se particiona el conjunto de datos en trozos de aproximadamente igual carga de trabajo. Todos los ejecutantes contribuyen al progreso de la solución, y típicamente obtiene un incremento del desempeño sistemático.
-
Descomposición exploratoria (exploratory decomposition) se usa con problemas de búsqueda en un espacio de soluciones, el cual se puede particionar para buscar concurrentemente hasta encontrar las soluciones esperadas. Apenas un ejecutante encuentra una o la última solución, avisa a los demás para que todos se detengan. Son ejemplos, el ajedrez o buscar el camino en un laberinto. A diferencia de la descomposición de datos, los ejecutantes podrían no contribuir al progreso de la solución (su partición no contiene solución alguna) y un incremento de desempeño no se comporta de forma sistemática, pues depende de dónde se encuentre la solución en el espacio de búsqueda y cómo se particione éste.
-
Descomposición especulativa (speculative decomposition) se usa cuando se puede predecir con alguna probabilidad que un evento futuro ocurrirá, y la tarea asociada puede ser ejecutada en forma anticipada y concurrente a la actual. De esta forma si el evento ocurre, su tiempo de ejecución será menor. Por ejemplo, tras una consulta en un buscador web, mientras el navegador carga los resultados, concurrentemene carga la página del primer resultado retornado por el buscador. Si el usuario hace click en el primer resultado, verá casi de forma instantánea la página cargada en el navegador.
Las técnicas anteriores no son las únicas ni son excluyentes. Varias pueden emplearse para resolver problemas complejos, a lo que corresponde una descomposición híbrida (hybrid decomposition).
| L19-set, k20-set | Video |
|---|---|
Descomposición: concepto y técnicas: recursiva, de datos, exploratoria, especulativa |
3.3. Mapeo
La Figura 7 muestra el resultado de la actividad de mapear tres conjuntos de datos de distinta naturaleza, representados como arreglos en fondo celeste. El valor en cada celda celeste significa una unidad de trabajo medida como una potencial duración. Los números sobre el arreglo de fondo celeste indican el índice basado en cero.
Debajo de los arreglos celestes en la Figura 7 se anota el número de trabajador que realiza esa unidad de trabajo. El número varía de acuerdo al mapeo. Los mapeos pueden clasificarse en estáticos o dinámicos. En el mapeo estático la asignación de las unidades de trabajo se conoce de antemano, es decir, antes de iniciar el trabajo, sólo depende de conocer el número total de unidades de trabajo y trabajadores. El mapeo por bloque y cíclico son dos formas de mapeo estático.
En el mapeo dinámico la asignación ocurre durante la realización del trabajo, es decir, los trabajadores se asignan las unidades de trabajo conforme ellos terminan las previas. Aunque normalmente consigue mejores distribuciones, es más costoso en recursos que los mapeos estáticos, dado que requiere control de concurrencia y manipulación de estructuras de datos dinámicas.
| L19-set, k20-set | Video |
|---|---|
Mapeo: concepto. Mapeo estático. Mapeo dinámico |
|
Actividad de mapeo manual en una hoja de cálculo |
3.3.1. Mapeo por bloque
El mapeo estático por bloque asigna rangos continuos de trabajo a cada trabajador (ejecutante, hilo, o proceso). Es el mapeo que potencialmente puede disminuir más fallos de caché o false sharing (Section 3.8) si se trabaja con memoria continua. El bloque de un trabajador \$i\$ está dado por el rango de índices enteros \$[\text{start}, \text{finish}[\$, donde \$\text{start}\$ y \$\text{finish}\$ son funciones dadas por
donde \$i\$ es el número del trabajador (iniciando en 0), \$D\$ es la cantidad de datos, y \$w\$ es la cantidad total de trabajadores.
| L19-set, k20-set | Video |
|---|---|
Mapeo estático por bloque no balanceado |
|
Modelo matemático del mapeo estático por bloque balanceado |
|
Mapeo por bloque en la actividad de la hoja de cálculo |
3.3.2. Mapeo cíclico
El mapeo estático cíclico asigna al trabajador \$i\$ todas las unidades de trabajo con índice \${i,i+w, i+2w, ...}\$. Puede tener ventajas cuando las unidades de datos presentan algún patrón predecible y que no es apto para el mapeo por bloque. Se puede hacer un híbrido del mapeo cíclico por bloque que reparte no una unidad, sino bloques de unidades de trabajo de igual tamaño de forma cíclica a cada trabajador.
| L19-set, k20-set | Video |
|---|---|
Mapeo estático cíclico. Metáfora de la baraja de naipes |
|
Mapeo estático cíclico con bloques |
3.3.3. Mapeo dinámico
Los algoritmos de mapeo dinámico reparten las unidades de descomposición entre los ejecutantes en tiempo de ejecución. Un principio de diseño que puede seguirse es "cuando un ejecutante se desocupa toma la siguiente unidad de trabajo disponible". Este principio puede implementarse de formas como las siguientes:
-
Variable de control. Una variable compartida y protegida por exclusión mutua que indica cuál es la próxima unidad de trabajo disponible. Cuando un ejecutante se desocupa, compite por el mutex y cuando lo adquiere, toma la siguiente unidad de trabajo disponible y deja en la variable compartida la unidad que le sigue. Esto se repite hasta que los ejecutantes hayan completado todo el trabajo.
-
Productor-consumidor. El trabajo se agrega, normalmente por el hilo principal a un buffer (por ejemplo, una cola thread-safe) llamado work pool. Los ejecutantes consumen del buffer y procesan cada unidad de trabajo que extraen. Se debe decidir la forma de detener los consumidores, como usar variables contadoras, cuando el buffer está vacío, o cuando se extrae un valor centinela.
-
Mapeo dinámico aleatorio. En caso de paso de mensajes o de uso del patrón productor-consumidor, el productor de trabajo lo reparte de forma aleatoria entre los ejecutantes (consumidores).
| L19-set, k20-set | Video |
|---|---|
Mapeo dinámico |
3.4. Métricas
3.4.1. Incremento de velocidad (speedup)
Para determinar en cada iteración de optimización si hubo realmente una ganancia de rendimiento (pasos 1 y 5 del método sugerido), se puede utilizar varias métricas. La medida relativa speedup \$S\$ (incremento de velocidad), se calcula como la relación entre el tiempo que tarda una computación previa a la optimización (\$T_\text{before}\$), contra el tiempo que tarda la misma computación posterior la optimización (\$T_\text{after}\$):
La paralización de código serial es una forma de optimización. Una comparación de incremento de velocidad común es el tiempo de ejecución serial (antes) respecto al tiempo de ejecución posterior a la paralización (después). En este caso, el speedup indica la cantidad de veces que la computación paralela es más rápida que la computación serial. Un valor mayor a 1 indica un incremento de velocidad, 1 que la velocidad se mantiene igual, y un valor menor a 1 un decremento en la velocidad.
| L19-set, k20-set | Video |
|---|---|
Métrica del incremento de velocidad (speedup) |
3.4.2. Eficiencia
El speedup sólo considera los tiempos de ejecución pero no los recursos que se invirtieron en conseguir el incremento de desempeño. La métrica de eficiencia (\$E\$, efficiency) es una relación entre el incremento de velocidad y la cantidad de trabajadores (\$w\$) que tuvieron que involucrarse para conseguirlo:
La eficiencia es un valor entre 0 y 1, donde 0 indica un sistema no eficiente, y 1.0 es la eficiencia ideal donde todo el trabajo es realizado en paralelo por los trabajadores, en forma equitativa y sin necesidad de control de concurrencia. Sin embargo, es poco probable que un programa logre una eficiencia de 1.0. Normalmente los programas tienen porciones de código secuencial (por ejemplo, antes de crear los hilos de ejecución, o al usar control de concurrencia como exclusión mutua) y porciones de código paralelo, como ocurre en la línea de tiempo de la Figura 8.
| L19-set, k20-set | Video |
|---|---|
Métrica de eficiencia (efficiency). Gráficos combinados |
3.4.3. Medición de los tipos de mapeo
| L19-set, k20-set | Video |
|---|---|
Mapeos estáticos para los casos 2 y 3 en la hoja de cálculo |
|
Mapeo dinámico para los casos 2 y 3 en la hoja de cálculo |
|
Comparación de los tipos de mapeo |
|
Ejercicio de la simulación de mapeo. Algoritmos de posibles implementaciones de los mapeos |
3.5. Ley de Amdahl
La Ley de Amdahl establece que el máximo speedup que un programa puede alcanzar por paralelización está acotado por la porción del programa que se mantiene o sólo puede ser serial. Por ejemplo, para la Figura 8 la duración total del trabajo si se realizara en forma serial sería \$T_s = 1 + 24 + 1 = 26\$ horas. Si se tuviera una paralelización ideal, la fase paralelizable de 24h se podría repartir entre \$w\$ trabajadores y reducir a \$\frac{24}{w}\$ horas, por ejemplo en la Figura 8 se ilustran \$w = 3\$ trabajadores que reducirían la fase central a \$\frac{24}{3} = 8\$ horas. Por consiguiente la duración total de la versión paralela del programa sería \$2 + \frac{24}{w}\$ horas, y por lo tanto, el incremento de velocidad se obtendría por la relación:
Por ejemplo, con \$w = 3\$ trabajadores, el speedup sería \$S = \frac{26}{2 + \frac{24}{3}} = 2.6\$. Con ocho trabajadores se tendría el doble del speedup anterior \$S = 5.2\$. Para maximizar el speedup es natural pensar en incrementar la cantidad de trabajadores \$w\$, procurando que el denominador se acerque a cero. Sin embargo, en caso extremo, cuando \$w\$ tiende a infinito número de trabajadores se obtiene que
Es decir, para la situación del programa de la Figura 8, el speedup está acotado a 13. Aunque la Ley de Amdahl puede verse como una limitación negativa al paralelismo, también puede usarse a favor. Si se sabe que para un programa concurrente el speedup máximo es 13, con unos pocos hilos o alquilar unas pocas máquinas en la nube, se podría alcanzar un speedup satisfactorio, en lugar de invertir en recursos costosos que poco incrementarían la velocidad, dado a que está acotada como muestra la Figura 9 para 100 trabajadores.
| j22-set, v23-set | Video |
|---|---|
Mapeo dinámico aleatorio |
|
Eficiencia ideal (1.0) |
|
Ley de Amdahl. Máximo speedup teórico. Usarla para estimar recursos |
3.6. Profiling
Para encontrar regiones de código que podrían ser optimizadas por su alto consumo de recursos se puede usar una herramienta de profiling. Estas herramientas proveen análisis dinámico de código ejecutable con fines de optimización. Algunos ejemplos son Callgrind y perf.
3.6.1. Callgrind
Callgrind es una herramienta que forma parte de Valgrind. Conviene incrustar el código fuente al compilar el ejecutable para obtener información más contextualiazada, como muestran los siguientes comandos.
# Install tools
sudo apt install build-essential valgrind kcachegrind
# Compile executable including its source code
cc -g -Wall -Wextra source.c -o executable -pthread
# Run the program under callgrind
valgrind --tool=callgrind --separate-threads=yes ./executable args_for_executable
# Visualize the data collected by callgrind in the current directory
kcachegrindCallgrind realiza contabilidad de invocaciones de subrutinas y cantidad de instrucciones ejecutadas. Se requiere incluir el código fuente dentro del ejecutable al compilar el programa. Luego se corre el programa con callgrind, el cual crea archivos en la carpeta donde se invoca con nombres como callgrind.PID-TH donde PID es el número de proceso y TH el número de hilo, si se pide separar las estadísticas de cada hilo ejecutado por el programa. Finalmente se requiere un programa de visualización que tome las estadísticas almacenadas en los archivos y los presente de forma que ayude a las personas a comprender el comportamiento del programa, como KCachegrind (en algunas distribuciones de Linux podría llamarse qcachegrind).
KCachegrind permite encontrar rápida y visualmente las líneas de código fuente que consumen más instrucciones de procesador, y por tanto, las líneas críticas que convienen optimizar, incluso en una base de código extensa. En la esquina superior izquierda de la Figura 10 muestra un gráfico de consumo por cada hilo de ejecución. En la esquina inferior izquierda muestra las subrutinas que han ejecutado más instrucciones de procesador en porcentajes, isPrime() está seleccionada. En la esquina superior derecha se muestra las líneas de código fuente de isPrime() que consumieron más instrucciones. Se puede ver la invocación a qSqrt() y el operador módulo (%) son los que causan casi la totalidad del procesamiento. Estos son los puntos críticos a optimizar para esta aplicación.
Suponga que se le contrata para optimizar una solución a un problema que debe encontrar el perímetro mayor para marcar una cerca en mapas. Ya existe una solución serial disponible en la carpeta fence/.
Encuentre las regiones de código que consumen mayor procesamiento y podrían ser las prioritarias de paralelizar. Use una herramienta de profiling para este fin.
| j22-set, v23-set | Video |
|---|---|
Análisis estático y dinámico de código |
|
Problema de ejemplo: marcar la cerca |
|
Callgrind: herramienta de profiling para invocaciones y procesamiento |
|
Concepto de visualización. Procesos en segundo plano en el shell |
|
Kcachegrind: herramienta de visualización. Encontrar regiones de código que más consumen CPU |
3.6.2. Gprof
Gprof es una herramienta que reporta el tiempo de pared que toma cada invocación de subrutina. Sin embargo, parece ir quedando en desuso posiblemente por prevalencia de otras herramientas como Perf. Los siguientes comandos resumen el uso de gprof:
# Compile a modified executable that measures function call durations
gcc -g -Wall -Wextra -pg -no-pie source.c -o executable
# Run the executable as usual, it will generate binary file gmon.out
./executable args
# Generate a report from the gmon.out binary log
gprof ./executable gmon.out > report.txt3.6.3. Perf
La herramienta perf permite realizar variedad de análisis de rendimiento de los programas, sin afectar su tiempo de ejecución. Tampoco requiere modificar o recompilar el ejecutable en estudio. Es capaz de reportar las funciones que consumen más CPU, generar gráficos de uso de CPU, entre otras operaciones. Para obtener la duración total que tarda un programa se usa la acción stat de la forma:
perf stat ./executable argsPara que perf pueda monitorear otros programas, puede requerir darle permisos o configurar el sistema operativo para disminuir el nivel de seguridad del sistema. Este paso varía mucho de un sistema operativo a otro. En distribuciones basadas en Debian o Ubuntu, puede ejecutar los siguientes comandos con permisos de administración para instalar perf.
# Debian
apt install linux-perf
echo 1 > /proc/sys/kernel/perf_event_paranoid
echo kernel.perf_event_paranoid=1 > /etc/sysctl.d/local.conf
# Ubuntu
apt install linux-tools-common linux-tools-`uname -r`
echo 1 > /proc/sys/kernel/perf_event_paranoid
echo 'kernel.perf_event_paranoid = 1' >> /etc/sysctl.conf3.7. Clústers de computadoras
Un clúster es una red de computadoras lo más homogéneas posibles: misma marca y modelo de procesador, igual cantidad de RAM, disco duro, mismo sistema operativo, misma versión del sistema operativo, compiladores, herramientas… de tal forma que un programa pueda correr de forma distribuida en paralelo sin hacerle modificaciones.
| j22-set, v23-set | Video |
|---|---|
Clúster de Arenal. Nodo máster y esclavos |
|
Determinar cantidad de CPUs ( |
|
Correr procesos en el clúster. Monitorear procesos ( |
3.8. Falso compartido (false sharing)
Estudie y ejecute el programa dado en sus cuatro modos, usando los argumentos de línea de comandos 0 a 3. Todos los modos realizan la misma tarea de actualizar dos elementos de un arreglo cien millones de veces. En los modos 0 y 1 los dos elementos se actualizan de forma serial. En los modos 2 y 3 dos hilos concurrentemente actualizan los elementos, como se muestra en la siguiente tabla.
| Modo | Tipo | Elemento 1 | Elemento 2 |
|---|---|---|---|
0 |
Secuencial |
El primero del arreglo |
El segundo del arreglo |
1 |
Secuencial |
El primero del arreglo |
El último del arreglo |
2 |
Concurrente |
El primero del arreglo |
El segundo del arreglo |
3 |
Concurrente |
El primero del arreglo |
El último del arreglo |
Se espera que las versiones seriales tarden aproximadamente lo mismo y que las versiones concurrentes tarden aproximadamente la mitad de las versiones seriales. Sin embargo, esto no ocurre. Trate de explicar por qué.
| Archivo | Descripción |
|---|---|
Actualiza cien millones de veces dos elementos de un arreglo. |
|
Permite compilar y ejecutar la solución. Puede usar |
| j10-nov, v11-nov | Video |
|---|---|
|
|
|
|
Arquitectura de la jerarquía de caché |
|
Rastreo de caché. Fallo de caché. Principio de localidad. Dirty bit. Coherencia de caché |
|
Falso compartido (false sharing). Modificación de memoria cercana y distante |
|
Análisis dinámico de fallos de caché (profiling). |
|
Relación entre los tipos de mapeo y el falso compartido |
Estudie y ejecute el programa dado en sus cuatro modos, usando los argumentos de línea de comandos 0 a 3. Todos los modos realizan las mismas tareas: sumar usando un incremento en una variable compartida, e incrementar un contador compartido. En los modos 0 y 1 las dos tareas se realizan de forma serial. En los modos 2 y 3 la suma y el incremento se realizan de forma concurrente, como se muestra en la siguiente tabla.
| Modo | Tipo | Tarea 1 | Tarea 2 |
|---|---|---|---|
0 |
Secuencial |
Suma leyendo el incremento compartido |
Incrementa el contador compartido |
1 |
Secuencial |
Suma con una copia privada del incremento |
Incrementa el contador compartido |
2 |
Concurrente |
Suma leyendo el incremento compartido |
Incrementa el contador compartido |
3 |
Concurrente |
Suma con una copia privada del incremento |
Incrementa el contador compartido |
Se espera que las versiones seriales tarden aproximadamente lo mismo, y que las versiones concurrentes tarden aproximadamente la mitad de las versiones seriales. Sin embargo, esto no ocurre. Trate de explicar por qué.
| Archivo | Descripción |
|---|---|
Suma leyendo e incrementa escribiendo cien millones de veces los campos de un registro compartido. |
|
Permite compilar y ejecutar la solución. Puede usar |
| j10-nov, v11-nov | Video |
|---|---|
|
4. Concurrencia de tareas
Los dos tipos de problemas que resuelve el paradigma de programación concurrente son los que requieren incremento de desempeño y separación de asuntos.
-
El incremento del desempeño se busca principalmente al optimizar algorimos que requieren mucho poder de cómputo o procesar grandes volúmenes de datos. Son de especial interés para otras disciplinas que requieren apoyo de la computación. Se busca principalmente maximizar el paralelismo de datos a través de entes de ejecución (hilos o procesos) y disminuir la cantidad de comunicación entre los entes.
-
La separación de asuntos o concurrencia de tareas no busca tanto la optimización, sino que los entes realicen tareas distintas de forma correcta. Los problemas en esta categoría son de especial interés para la computación misma, dado que son aplicables a variedad de herramientas como sistemas operativos, motores de bases de datos, servidores web, entre otros. Típicamente los problemas en esta categoría buscan que la concurrencia de tareas genere resultados correctos a través de la aplicación de mecanismos de sincronización, por lo que se les suele también llamar problemas de sincronización.
Esta sección se concentra en problemas del segundo tipo de la lista anterior, muchos de los cuales tienen aspecto de acertijos y resultan muy interesantes para la persona profesional de la computación. Están basados en el libro libre The Little Book of Semaphores escrito por Allen B. Downey.
| L26-set, k27-set | Video |
|---|---|
Concurrencia de tareas. El pequeño libro de los semáforos |
4.1. Primitivas
En la solución de problemas de sincronización se suele trabajar a nivel de diseño, lo que permite concentrarse en el problema de sincronización y abstraer los detalles del contexto en el que se aplica (ej.: persistencia en una base de datos) y los detalles de implementación (como lenguajes de programación y ambientes de concurrencia).
Existen varias notaciones empleadas para el diseño concurrente, como diagramas de flujo, UML, TLA+, cálculo-π, pseudocódigo, redes de Petri, entre otros. En el curso se usarán los últimos dos.
4.1.1. Algoritmos (pseudocódigo)
No existe una convención estándar para especificar algoritmos en pseudocódigo. Por el contrario, es común que los autores escojan sus propias convenciones. Existen estilos similares a un lenguaje de programación, a la notación matemática, o al idioma natural. En el curso se ha usado una notación que ha surgido de la creación de los docentes y estudiantes del mismo. En el siguiente listado se resume esta notación.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
// Declares a constant shared by all threads, operator := is for variables
const CONST_NAME = const_value
// Declares a new data type as an enumeration of constants
define Month as enumeration of
jan = 1, feb, mar, apr, may, jun, jul, aug, sep, oct, nov, dec
end enumeration
// Declares a new type of record, note the use of Uppercase
define Date as record of
day as integer,
month as Month,
year as integer
end record
// Use {} for records. Use [] for arrays and associative-arrays
const CHRISTMAS = Date{25, dec, 0000}
// Main subroutine that will be executed by the main thread
procedure main()
// Declares a local, private variable, data type is optional if it can be
// inferred from initial_value
declare local_var as data_type := initial_value
// Declares a variable shared by all threads, stored in shared_data record
// Its initial value is read as an integer from standard input
shared thread_count := read_integer()
// Create an array of boolean, char, integer, float, text, semaphore, record
shared values as array of thread_count of integer initialized in 0
// Concurrency control mechanisms are always shared
shared a_mutex := create_mutex()
// Semaphores receive an initial integer value
shared a_semaphore := create_semaphore(5)
// Create a secondary thread, returns a thread identifier
// args is a list of comma-separated values passed as private variables
declare thread1 := create_thread(routine1, args)
// Create a team of threads, all of them will execute the same routine
// concurrently. The routine will be called with the thread_number as first
// parameter starting at 0. Extra arguments can be provided.
// Returns an array of thread identifiers
declare team := create_threads(thread_count, routine2, 5)
// Secondary threads are implicitly joined before main() finishes, however
// they can be joined/waited manually using the thread identifiers
join_thread(thread1)
join_threads(team)
end procedure
// Functions always return a value and has no side effects in process state
function routine1(params)
// Arithmetic operators are similar to mathematics: div for integer division,
// mod for integer modulus, and / for floating point division
return 3 * mod(10, 4)
end function
// Procedure may not return a value and has side effects in process state
procedure routine2(my_rank, increment)
// Note the flow control structures
if condition then
// Condition-loop
while condition do
statements
end while
else
// Counter-loops, "for" implies declaration of new variables
// "in steps of 1" is by default
for index := 0 to thread_count in steps of 1 do
values[my_rank] := index * my_rank + increment
end for
end if
end procedure
Cuando la notación de pseudocódigo no define un constructo específico, se toman características del lenguaje de programación usado en el curso, en este caso, C/C++.
| L26-set, k27-set | Video |
|---|---|
Notaciones de pseudocódigo concurrente |
Dos threads ejecutan las siguientes tareas. Liste todas las rutas de ejecución indicando el valor final de la variable x y la salida estándar. Una ruta de ejecución (execution path) es una combinación de instrucciones que depende del orden en que sean ejecutadas.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
procedure main()
shared x := 0
create_thread(thread_a)
create_thread(thread_b)
end procedure
procedure thread_a()
x := 5
print(x)
end procedure
procedure thread_b()
x := 7
end procedure
| L26-set, k27-set | Video |
|---|---|
Rutas de ejecución concurrente |
| Archivo | Descripción | Cambios |
|---|---|---|
Lista todas las posibles rutas de ejecución. |
4.1.2. Redes de Petri
Las redes de Petri (Petri net) fueron ideadas por el alemán Carl Adam Petri (1926-2010) a sus 13 años para describir procesos químicos, aunque su formalización ocurriría 23 años después, en su tesis doctoral de matemática en 1962. La aplicación de este concepto beneficia la representación de fenómenos que tienen componentes que actúan de forma concurrente o distribuida.
Una red de Petri es una representación matemática (un modelo) de la estructura y comportamiento dinámico de un sistema distribuido. Un sistema es un conjunto de componentes que interactúan de forma coordinada para realizar una actividad. El sistema es un concepto recursivo porque un sistema, con todos sus componentes, forma una unidad que puede ser parte de un sistema más grande, lo que crea una jerarquía o red de sistemas y subsistemas. Un sistema tiene estado (memoria), realiza actividades (procesamiento), e interacciona con otros sistemas (comunicación).
Cada componente en sí es un sistema que tiene un estado independiente al de otros componentes, lo que crea distribución del estado. El comportamiento futuro de un componente depende de este estado, y puede o no depender del pasado gracias a que el estado puede guardar historia. La actividad que un componente realiza podría ser simultánea a las actividades que realizan los otros componentes del sistema, lo que crea concurrencia o paralelismo de las actividades.
Es común que los componentes tengan que interactuar para lograr la actividad global del sistema, y esto requiere sincronización entre ellos para que los resultados sean correctos. Esta sincronización es normalmente una forma de espera (waiting), donde un componente detiene su actividad hasta la ocurrencia de un evento que asegure el orden correcto de actividades o la transferencia correcta de estado entre los componentes.
| L26-set, k27-set | Video |
|---|---|
Redes de Petri. Modelado de sistemas concurrentes y distribuidos. |
Al modelo de Petri de las rutas de ejecución le hizo falta la declaración de la variable commpartida shared x := 0. Modifique la red de Petri para agregar esta instrucción. Use la herramienta Workflow Petrinet Designer (WoPeD) que requiere del ambiente de ejecución de Java.
| Archivo | Descripción | Cambios |
|---|---|---|
Red de petri que representa el mismo programa que el pseudocódigo dado. |
Suponga que el hilo de ejecución principal crea w=100 hilos secundarios con los siguientes códigos.
1
2
3
4
5
6
7
8
9
10
11
procedure main()
shared count := 0
create_threads(100, secondary)
end procedure
procedure secondary()
for i := 0 to 100 do
const temp := count
count := temp + 1
end for
end procedure
-
¿Cuál es el valor más grande que la variable compartida
countpodría llegar a obtener? ¿En qué rutas de ejecución se alcanza este valor? -
¿Cuál es el menor valor que la variable compartida
countpodría llegar a obtener? ¿En qué rutas de ejecución se alcanza este valor?
| L26-set, k27-set | Video |
|---|---|
Ejemplo de las rutas de ejecución en red de Petri. Lugares, transiciones y arcos |
|
Ejemplo |
| Archivo | Descripción | Cambios |
|---|---|---|
Conjetura los potenciales resultados. |
4.2. Patrones básicos
4.2.1. Avisar/notificar (signaling)
Modifique los códigos de los hilos para que la instrucción a1 se ejecute siempre antes que la instrucción b1. Esto es, que un hilo envíe una señal (aviso) a otro (signaling).
1
2
3
4
5
6
7
8
9
10
11
12
procedure main()
create_thread(thread_a)
create_thread(thread_b)
end procedure
procedure thread_a()
statement a1
end procedure
procedure thread_b()
statement b1
end procedure
Modifique la red de Petri para que el hilo a haga el aviso al hilo b:
| j29-set, v30-set | Video |
|---|---|
Ejemplo |
|
Ejemplo |
| Archivo | Descripción | Cambios |
|---|---|---|
Usa un semáforo que indica cuando la instrucción |
|
|
Red de petri que usa una un estado intermedio para representar el aviso. |
|
4.2.2. Encuentro (rendezvous)
Modifique los códigos de los hilos para que la instrucción a1 y b1 se ejecuten siempre antes que las instrucciones a2 y b2. Este problema tiene el nombre francés rendezvous que significa encuentro en un punto de ejecución, y ninguno de los dos hilos pueden continuar su ejecución hasta que el otro haya llegado.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
procedure main()
create_thread(thread_a)
create_thread(thread_b)
end procedure
procedure thread_a()
statement a1
statement a2
end procedure
procedure thread_b()
statement b1
statement b2
end procedure
Modifique la red de Petri para que ocurra el encuentro entre los hilos de ejecución:
| j29-set, v30-set | Video |
|---|---|
Encuentro (rendezvous): solución 1 en pseudocódigo [err] |
|
Encuentro (rendezvous): solución 2 en pseudocódigo [err] |
|
Encuentro (rendezvous): Bloqueo mutuo (deadlock) |
|
Encuentro (rendezvous): red de Petri |
| Archivo | Descripción | Cambios |
|---|---|---|
Usa dos semáforos para asegurar que dos threads han llegado a cierto punto. En esta solución, los dos threads avisan apenas hayan terminado de ejecutar las instrucciones |
|
|
En esta versión un thread primero espera y el otro avisa. Es una solución correcta aunque ligeramente menos eficiente que la versión 1. Hay dos variantes equivalentes: a) El hilo |
|
|
En esta versión ambos threads esperan a que el otro haya terminado de ejecutar su instrucción. No es una solución al problema porque genera un bloqueo mutuo (deadlock). |
|
|
Un encuentro es una doble señal cruzada entre los hilos |
|
4.2.3. Exclusión mutua con semáforos (mutex)
Agregue semáforos al pseudocódigo siguiente para forzar a que los incrementos en los hilos se hagan con exclusión mutua.
1
2
3
4
5
6
7
8
9
10
11
12
13
procedure main()
shared count := 0
create_thread(thread_a)
create_thread(thread_b)
end procedure
procedure thread_a()
count := count + 1
end procedure
procedure thread_b()
count := count + 1
end procedure
Corrija la red de Petri para que los incrementos se realicen con exclusión mutua.
| j29-set, v30-set | Video |
|---|---|
Exclusión mutua con semáforos (sem_mutex): pseudocódigo |
|
Exclusión mutua con semáforos (sem_mutex): red de Petri |
| Archivo | Descripción | Cambios |
|---|---|---|
Un semáforo inicializado en 1 y que nunca supera este valor, es un semáforo binario. Es equivalente a un mutex excepto que no tiene dueño (ownership). Cuando el semáforo tiene el valor 1 indica que el mutex está disponible, y el valor 0 que está bloqueado. Se diferencia en que un mutex nunca supera el valor 1, mientras que un semáforo técnicamente puede hacerlo, y de que un mutex sólo puede ser incrementado por el mismo thread que lo decrementó. |
|
|
Un lugar (place) con un token del cual salen dos arcos sirve para crear exclusión mutua en una red de Petri, lo que corresponde a "bloquear" el mutex. Luego el token debe regresar a este lugar, lo que semánticamente equivale a "desbloquear" (unlock) el mutex. |
|
Note que en la actividad anterior ambos threads ejecutaban el código en subrutinas distintas, a lo que se le llama una solución asimétrica (separación de asuntos o concurrencia de tareas). Sin embargo, el código de las subrutinas era el mismo y por tanto podría convertirse en una solución simétrica. En una solución simétrica los hilos ejecutan el mismo código, es decir, la misma subrutina.
Las soluciones simétricas son a menudo más fáciles de generalizar. Agregue semáforos al pseudocódigo siguiente para forzar a que los incrementos hechos por una cantidad arbitraria de hilos sean con exclusión mutua.
1
2
3
4
5
6
7
8
9
10
procedure main()
shared count := 0
input const thread_count
create_threads(thread_count, secondary)
end procedure
procedure secondary()
// Critical section
count := count + 1
end procedure
Corrija la red de Petri para que una cantidad arbitraria de hilos (cinco en la red dada) hagan el incremento con exclusión mutua.
| L03-oct, k04-oct | Video |
|---|---|
Exclusión mutua simétrica (sem_mutex_sym): pseudocódigo |
|
Repaso de patrones básicos en redes de Petri |
|
Exclusión mutua simétrica ( |
| Archivo | Descripción | Cambios |
|---|---|---|
El semáforo usado adecuadamente obliga a una serialización de los hilos. |
|
|
Se usa un place con un token que permite avanzar sólo a un hilo a la vez |
|
4.2.4. Exclusión mutua acotada (multiplex)
Modifique el pseudocódigo dado para que imponga una cota o límite superior de n hilos ejecutando una sección de concurrencia acotada. A este patrón se le llama multiplex y es útil para problemas donde se tienen distintos entes trabajando al mismo tiempo pero con máximo de capacidad.
Por ejemplo, la cantidad de cajeros atendiendo en las ventanillas de un banco o de clientes patinando en la pista del salón de patines. En este último caso, si la capacidad de la pista se agota, algunos clientes tendrán que esperar afuera, y apenas una persona sale de la pista, otra podrá ingresar de inmediato. Use el código siguiente para reflejar este comportamiento.
1
2
3
4
5
6
7
8
9
procedure main()
input const skater_count, const room_capacity
create_threads(skater_count, skater)
end procedure
procedure skater()
// Concurrency-bounded region
skate()
end procedure
Modifique la red de Petri para reflejar la llegada de 10 patinadores a un salón de patines que tiene una capacidad para 3 patinadores concurrentes.
| L03-oct, k04-oct | Video |
|---|---|
Concurrencia acotada (multiplex): pseudocódigo |
|
Concurrencia acotada ( |
| Archivo | Descripción | Cambios |
|---|---|---|
Simplemente se inicializa el semáforo con el límite superior de threads permitidos concurrentemente. Si el semáforo llega a alcanzar el valor 0, indica que se agotó la capacidad concurrente y los hilos subsecuentes tendrán que esperar. Cuando un hilo incrementa el semáforo es porque "sale del salón" y deja espacio para que otro ingrese. ¿Cuál será el valor final del semáforo cuando todos los hilos hayan pasado por la sección crítica? |
|
|
Es la misma solución a sem_mutex_sym (Ejemplo 20) con la diferencia de que el semáforo en lugar de inicializarse en 1, lo hace en la capacidad de la región de concurrencia acotada. |
|
4.2.5. Barrera (barrier)
-
Generalice su solución a la actividad rendezvous (Ejemplo 18) para asegurar que una cantidad arbitraria de hilos no continúen su ejecución hasta que todos hayan alcanzado (ejecutado) el punto de encuentro. Es decir, si se crean
whilos, los primerosw - 1hilos que lleguen al punto de encuentro deberían esperar hasta que el hilo en la posiciónwllegue al punto de encuentro. En tal momento todos loswthreads podrán continuar ejecutándose concurrentemente. A este patrón se le conoce como barrera (barrier). Implemente una barrera con semáforos en el siguiente pseudocódigo para que la instrucciónStatement Bse ejecute sólo hasta que todos los hilos hayan ejecutado la instrucciónStatement A.1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
procedure main() // How many threads have arrived to the barrier shared count := 0 // Protects the increment of the count shared can_access_count := create_semaphore(1) // Locked (0) until all threads arrive, then it is unlocked (1) shared barrier := create_semaphore(0) // Read thread count from standard input input shared const thread_count // Create a thread team running secondary create_threads(thread_count, secondary) end procedure procedure secondary() Statement A // Adapt rendezvous solution here // Statement B can be only executed until all threads have run Statement A Statement B end procedure
-
Agregue una barrera a la red de Petri para que los tres hilos ejecuten las instrucciones
Statement Bsólo hasta que los tres hayan ejecutado las instruccionesStatement A.
-
Generalice la red de Petri para que w hilos ejecuten las instrucciones
Statement Bsólo hasta que todos hayan ejecutado las instruccionesStatement A.
| L03-oct, k04-oct | Video |
|---|---|
Barrera con semáforos ( |
|
Barrera con semáforos ( |
|
Barrera con semáforos ( |
|
Metáfora de barrera: aguja de paso vehicular |
| Archivo | Descripción | Cambios |
|---|---|---|
Implementa una barrera de una pasada. Es decir, después de usada, la barrera no se debe reutilizar. |
|
|
Implementa una barrera para 3 hilos usando un esquema de fork/join |
|
|
Implementa una barrera para una cantidad arbitraria de hilos usando arcos ponderados (weighted arcs) |
|
Haga que su solución a la actividad Ejemplo 22 sea reusable. Es decir, que la barrera quede lista para volver a usarse, por ejemplo, dentro de un ciclo. Debe asegurarse de que el contador quede en 0, y los threads que salen de la barrera no se combinen con otros que aún están en ella.
Sugerencia: Puede reemplazar la barrera por dos torniquetes. Un torniquete (turnstile) o "trompo" es un dispositivo de control de acceso que impide o da paso a una secuencia de personas de acuerdo a ciertas condiciones. Se usa típicamente en instalaciones deportivas, transporte público, acceso a edificios, parques de diversiones, y otros.
Un torniquete es un semáforo que detiene a todos los hilos que lleguen a él. Pero apenas un hilo logre pasarlo, inmediatamente habilita el paso al siguiente. Puede pensarse como una manera más elegante de que el último hilo que llega a la barrera haga un ciclo de incrementos por todos los demás.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
procedure main()
...
// Stops all threads, but the first one that passess it passess the rest
shared turnstile := create_semaphore(0)
...
end procedure
procedure secondary()
while true do
Statement A
...
// Use turnstile
wait(turnstile)
signal(turnstile)
...
// Statement B can be only executed until all threads have run Statement A
Statement B
end while
end procedure
| L03-oct, k04-oct | Video |
|---|---|
Problema de la barrera reusable ( |
|
Barrera diseñada con un torniquete (turnstile) |
|
Barrera reusable en un ciclo con dos torniquetes (turnstiles) |
| Archivo | Descripción | Cambios |
|---|---|---|
Usa dos torniquetes (trompos) para evitar que hilos de ejecución ávidos salgan de la barrera y vuelvan a ingresar a ella antes que otros hayan salido. |
|
La solución a este problema permite reutilizar barreras. Por ejemplo, se puede crear una interfaz como la siguiente:
| Archivo | Descripción |
|---|---|
Pseudocódigo que convierte la barrera en código reusable. |
Para la solución de nuevos problemas se puede suponer que se tiene disponible barreras con la interfaz del siguiente listado, en el que se crea una barrera que se levanta cuando llegan 3 hilos de ejecución a esperar por ella.
1
2
3
4
5
6
7
8
9
10
procedure main:
shared my_barrier := create_barrier(3)
...
end procedure
procedure secondary:
...
wait(my_barrier)
...
end procedure
| L03-oct, k04-oct | Video |
|---|---|
Interfaz en pseudocódigo concurrente para crear barreras |
4.2.6. Carrera de relevos (barrera)
Simule una carrera de relevos, donde los competidores son equipos de threads. Cada equipo consta de dos corredores. Un corredor tomará la estafeta (en inglés, baton) y se posicionará en la línea de salida. El otro corredor esperará en la mitad de la pista a que el primer corredor llegue y le transfiera la estafeta. En tal momento, el segundo corredor seguirá a toda velocidad hasta alcanzar la meta. Ganan únicamente los tres primeros equipos en llegar con la estafeta a la meta, quienes son premiados con oro, plata, y bronce.
Su simulación recibirá tres parámetros: la cantidad de equipos, la duración en milisegundos que tarda el primer corredor atravesando la etapa 1 de la carrera (entre la salida y la mitdad de la pista), y la duración en milisegundos del segundo corredor atravesando la etapa 2 de la carrera (de la mitad de la pista hasta la meta). Suponga que los corredores de una etapa tardan exactamente esta duración y no un valor generado al azar. Ejemplo de ejecución:
./relay_race 10 300 700 Place 1: team 2 Place 2: team 4 Place 3: team 1 Simulation time: 1.006079000s
En la salida anterior se reportan sólo los tres primeros equipos en llegar. Recuerde verificar la corrección de su solución (ej.: fugas de memoria, condiciones de carrera). Puede usar el siguiente código como punto de partida.
| Archivo | Descripción |
|---|---|
Pseudocódigo inicial para la carrera de relevos. |
|
Código en C con Pthreads inicial para la carrera de relevos. |
| L03-oct, k04-oct | Video |
|---|---|
Carrera de relevos ( |
|
Carrera de relevos ( |
|
Carrera de relevos ( |
|
Barreras en Pthreads |
|
Carrera de relevos ( |
| Archivo | Descripción | Cambios |
|---|---|---|
Diseño de la simulación de carrera de relevos usando metáforas visuales. |
|
|
Diseño en pseudocódigo de la simulación de carrera de relevos con equipos de hilos de ejecución. |
|
|
Implementación con Pthreads de la simulación de la carrera de relevos. |
|
|
Facilita la construcción y prueba de la la solución. |
4.3. Variable de condición
Rastree la memoria y el procesamiento del siguiente programa en una copia de esta hoja de cálculo, la cual tiene precargado el programa. Exporte el rastreo a un PDF y agréguelo a su repositorio de ejemplos. ¿Qué trabajo realiza la función mistery()?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
typedef struct {
unsigned int counter;
unsigned int max;
pthread_mutex_t mutex;
pthread_cond_t cond_var;
} mist_t;
void mist_init(mist_t* mist, unsigned max) {
mist->counter = 0;
mist->max = max;
pthread_mutex_init(&mist->mutex, NULL);
pthread_cond_init(&mist->cond_var, NULL);
}
void mist_destroy(mist_t* mist) {
mist->counter = 0;
pthread_mutex_destroy(&mist->mutex);
pthread_cond_destroy(&mist->cond_var);
}
void mistery(mist_t* mist) {
pthread_mutex_lock(&mist->mutex);
++mist->counter;
if (mist->counter < mist->max) {
// Preferred: while ( pthread_cond_wait(...) != 0 ) /* empty */;
pthread_cond_wait(&mist->cond_var, &mist->mutex);
} else {
mist->counter = 0;
pthread_cond_broadcast(&mist->cond_var);
}
pthread_mutex_unlock(&mist->mutex);
}
static mist_t mist;
void* run(void* data) {
fprintf(stderr, "%zu: before mist()\n", (size_t)data);
sleep((unsigned)(size_t)data);
mistery(&mist);
fprintf(stderr, "%zu: after mist()\n", (size_t)data);
return NULL;
}
int main() {
mist_init(&mist, 3);
pthread_t* workers = malloc(3 * sizeof(pthread_t));
for (size_t index = 0; index < 3; ++index) {
pthread_create(&workers[index], NULL, run, (void*)index);
}
for (size_t index = 0; index < 3; ++index) {
pthread_join(workers[index], NULL);
}
mist_destroy(&mist);
return 0;
}
| j03-nov, v04-nov | Video |
|---|---|
|
|
|
|
Concepto de variable de condición. Metáfora del oficial de tránsito y el intercomunicador. Variables de condición en Pthreads |
|
|
| Archivo | Descripción | Cambios |
|---|---|---|
Rastreo de procesamiento en una hoja de cálculo del código misterio. |
4.4. Filósofos comensales
En 1965 Edsger Dijkstra planteó el problema de los filósofos comensales como un ejercicio de un examen para estudiantes. Posteriormente Tony Hoare lo reformuló y se convirtió en un problema clásico de sincronización de procesos en los cursos de sistemas operativos. Existen varias adaptaciones como la que se muestra a continuación considerando algunos aspectos de higiene.
Cinco filósofos, que representan procesos o hilos de ejecución, están sentados a una mesa circular (Figura 12). Los filósofos en silencio piensan y luego comen, y repiten esta rutina eternamente. Ante cada filósofo se encuentra un plato, y al centro de la mesa un tazón con infinito abastecimiento de espagueti. Este abastecimiento representa un recurso compartido, como una cinta magnética en el problema original.
Para poder comer espagueti, en la mesa están dispuestos cinco tenedores (forks) o palillos chinos en el problema original (chopstiks). Tanto los filósofos como los palillos están enumerados de 0 a 4 como se ve en la figura Figura 12. Para poder comer, un filósofo i necesita los dos palillos (get chopstick), uno a su mano izquierda (i + 1) y el otro a su mano derecha (i), y no los comparte mientras está comiendo. Una vez que haya terminado de comer, el filósofo lava los palillos y los coloca de regreso en sus posiciones en la mesa (put chopstick). Un filósofo nunca sabe cuándo otro va a comer o pensar.
El reto es construir un algoritmo que permita a los filósofos eternamente pensar y comer que cumpla los siguientes tres requerimientos:
-
Los filósofos no se detengan de pensar y comer (bloqueo mutuo o deadlock).
-
Ningún filósofo muera de hambre esperando por un palillo (inanición o starvation).
-
Dos o más filósofos puedan comer al mismo tiempo (concurrency).
Los filósofos ya saben cómo realizar las operaciones de pensar think() y comer eat(), ninguna de las dos dura eternamente, y no se debe detener a un filósofo mientras las realiza.
Corrija el siguiente pseudocódigo de concurrencia de recursos compartidos para que resuelva el problema de los filósofos comensales, y por lo tanto, logre cumplir con los tres requerimientos.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
procedure main(argc, argv[]):
shared chopsticks[] := create_semaphores(5, 1)
for id := 0 to 5 do
create_thread(philosopher, id)
end for
end procedure
procedure philosopher(id):
while true do
think()
get_left_chopstick(id)
get_right_chopstick(id)
eat()
put_left_chopstick(id)
put_right_chopstick(id)
end while
end procedure
procedure get_left_chopstick(id):
wait(chopsticks[(id + 1) mod 5])
end procedure
procedure get_right_chopstick(id):
wait(chopsticks[id])
end procedure
procedure put_left_chopstick(id):
signal(chopsticks[(id + 1) mod 5])
end procedure
procedure put_right_chopstick(id):
signal(chopsticks[id])
end procedure
Considere las condiciones que son necesarias para que el bloqueo mutuo o la inanición ocurran, y cambie una de ellas a la vez para generar distintas soluciones:
-
Considere la lateralidad de los filósofos.
-
Considere la cantidad de filósofos que pueden comer concurrentemente.
-
Haga que los filósofos decidan con variables protegidas por exclusión mutua.
| j03-nov, v04-nov | Video |
|---|---|
Filósofos comensales: Enunciado del problema ( |
|
Filósofos comensales: análisis del psedocódigo inicial |
|
Filósofos comensales: solución 1: lateralidad (zurdos y diestros) |
|
Filósofos comensales: solución 2: cuota (capacidad de comensales concurrentes en la mesa) |
|
Filósofos comensales: Otras soluciones: con contadores, distribuida centralizada (mesero), y distribuida descentralizada. |
|
Filósofos comensales: solución en red de Petri (con inanición) |
| Archivo | Descripción | Cambios |
|---|---|---|
Solución 1: No todos los filósofos tienen la misma lateralidad |
|
|
Solución 2: Hay una cuota o límite (de 4) en la cantidad de filósofos que pueden intentar comer al mismo tiempo, implementada por un multiplex |
|
|
Red de petri que impide el bloqueo mutuo de los filósofos comensales, pero no la inanición. |
|
4.5. Lectores y escritores
4.5.1. Problema de lectores y escritores
El problema de los lectores y escritores es de mucha importancia en la disciplina de la computación porque ocurre en varios escenarios, como sistemas operativos y bases de datos.
Permita que varios lectores puedan leer de un medio común, pero sólo un escritor puede modificarlo a la vez. Por cada letra R que se lea de la entrada estándar se crea un hilo lector (reader), y por cada W que se lea de la entrada estándar se crea un hilo escritor (writer). Varios hilos pueden invocar la función read() al mismo tiempo, pero sólo un único hilo puede invocar write() a la vez. Esta puede considerarse una exlusión mutua categórica (categorical mutual exclusion) porque permite paralelismo de una categoría de hilos, pero excluye los de otra.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
procedure main()
while true do
case read_char() of
'R': create_thread(reader)
'W': create_thread(writer)
EOF: return
end case
end while
end procedure
procedure reader()
read()
end procedure
procedure writer()
write()
end procedure
| L07-nov, k08-nov | Video |
|---|---|
Lectores y escritores: Enunciado del problema |
|
Lectores y escritores: Solución en pseudocódigo |
|
|
| Archivo | Descripción | Cambios |
|---|---|---|
Diseño en pseudocódigo de la solución. |
|
4.5.2. Candados de lectura-escritura
Implemente una solución al problema de los lectores y escritores usando candados de lectura y escritura de Pthreads. Los escritores escriben en un contador compartido, y los lectores reportan el valor leído. Recuerde que varios lectores pueden trabajar al mismo tiempo mientras que en escritor necesita acceso exclusivo al recurso compartido. Su código no debe producir anomalías de memoria ni concurrencia. Puede usar el siguiente código como punto de partida.
| Archivos | Descripción |
|---|---|
Contiene a los demás archivos |
|
Código inicial para la solución a los lectores y escritores con candados de lectura y escritura |
|
Makefile para facilitar la construcción de la solución con Pthreads |
|
Casos de prueba de ejemplo |
| L07-nov, k08-nov | Video |
|---|---|
Candado de lectura y escritura. Metáfora del puente levadizo. |
|
Ejercicios de candados de lectura y escritura. Comparación de rendimiento entre |
| Archivo | Descripción | Cambios |
|---|---|---|
Los candados de lectura y escritura de Pthreads ( |
|
|
Facilita la construcción y prueba de la la solución. |
||
Casos de prueba de ejemplo. Son parte del código inicial dado. |
4.6. Reentrante vs thread-safe
Haga el mínimo de modificaciones a la siguiente implementación del generador lineal congruencial de números pseudoaleatorios para que sea:
-
Thread-safe
-
Reentrante y thread-safe
| Archivos | Descripción |
|---|---|
Generación de números aleatorios que no es ni reentrante ni thread-safe |
|
Makefile para facilitar la construcción de la solución con Pthreads |
| j10-nov, v11-nov | Video |
|---|---|
Subrutinas reentrantes vs thread-safe |
4.7. Otros problemas de sincronización
4.7.1. Formar agua
Este problema aparentemente está basado en un ejercicio de libro de programación concurrente de Gregory Andrews, y popularizado en el curso de sistemas operativos de la Universidad de California en Berkeley.
Hay dos tipos de hilos: los de hidrógeno y los de oxígeno. Su objetivo es formar agua con ellos. Usted dispone de un dispositivo, que cuando se coloca en él dos átomos de hidrógeno y uno de oxígeno, y se invoca bond() en cada uno de ellos, se forma agua. El dispositivo no funciona en cualquier otra combinación de átomos.
El dispositivo sólo puede trabajar en una molécula a la vez. Es decir, usted debe garantizar que los tres átomos de una molécula invoquen bond() antes de los hilos de la siguiente molécula. Escriba el código para cada átomo que garantice este comportamiento. Puede tomar el siguiente pseudocódigo como punto de partida.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
procedure main()
while read atom do
case atom of
'H': create_thread(hydrogen)
'O': create_thread(oxygen)
end case
end while
end procedure
procedure hydrogen()
bond()
end procedure
procedure oxygen()
bond()
end procedure
| L07-nov, k08-nov | Video |
|---|---|
|
|
|
| Archivo | Descripción | Cambios |
|---|---|---|
Solución propuesta por Jeisson Hidalgo. Utiliza multiplex y una barrera. |
|
4.7.2. Parejas de baile (colas con semáforos)
En una academia de artes las personas aprendices están entrenando bailes criollos, los cuales se bailan en parejas de un hombre con una mujer. Como es natural, las personas bailarinas no llegan todas al mismo tiempo al salón. Cuando se aproximan a este salón hacen dos grupos o filas, una de hombres y otra de mujeres. Cuando en ambas filas hay personas, un hombre y una mujer se toman de la mano e ingresan al salón de baile.
Naturalmente si una o varias mujeres llegan a la fila y la fila de hombres está vacía, tendrán que esperar. Lo mismo ocurre si los hombres llegan y encuentran la fila de mujeres vacía.
Simule con hilos de ejecución a las personas bailarinas, su espera en las colas, y el ingreso al salón de baile. Inmediatamente que hayan ingresado, bailarán, lo cual es indicado por la subrutina dance(). Suponga que las personas bailarinas se leen de la entrada estándar donde W indica una mujer y M un hombre como muestra el siguiente código. Suponga además que el salón tiene capacidad ilimitada para el número de parejas.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
procedure main()
while read genre do
case genre of
'M': create_thread(male)
'W': create_thread(female)
end case
end while
end procedure
procedure male()
dance()
end procedure
procedure female()
dance()
end procedure
Sugerencia. Un semáforo puede representar una cola de espera. Un valor inicial de 0 indica que la cola está vacía. Recuerde que un valor negativo indica la cantidad de hilos esperando en ella.
Si es necesario, modifique su solución al problema Ejemplo 31 para asegurarse de que realmente los bailarines entren en pareja al salón de baile. Es decir, que un hombre invoque dance() concurrentemente con una única mujer y viceversa. Suponga que se trata de un examen o audición, y por tanto, sólo una pareja puede estar en el salón de baile a la vez con el fin de que el jurado pueda calificarlos.
4.7.3. Fumadores de cigarrillos
Originalmente presentado por Suhas Patil. Participan cuatro hilos:
-
Un agente que representa un sistema operativo que asigna recursos.
-
Tres fumadores que representan aplicaciones que necesitan los recursos para realizar su labor.
Los cuatro hilos están en un ciclo infinito. Los fumadores esperan por tres ingredientes que representan los recursos: papel, tabaco, y fósforos. Una vez que obtienen los tres ingredientes pueden fabricar un cigarrillo y fumarlo.
El agente tiene un suminitro infinito de todos los tres ingredientes, y cada fumador tiene un suministro infinito de uno de los tres ingredientes. Es decir, un fumador tiene sólo papel, otro tiene sólo tabaco, y el tercero tiene sólo fósforos. Sin embargo, los fumadores no se comunican entre ellos.
El agente repetidamente escoge dos ingredientes al azar y los hace disponible a los fumadores. El fumador con el tercer ingrediente debería recoger los dos disponibles y fabricar su cigarrillo. Por ejemplo, si el agente provee papel y tabaco, el fumador que tiene fósforos debería recogerlos y avisarle al agente que ya puede sacar otros dos ingredientes.
El reto de la solución es permitir a las aplicaciones, que cuentan con los recursos que necesitan, correr concurrentemente, y evitar despertar una aplicación que no puede proceder. Usted tiene el rol de un desarrollador de aplicaciones, quien no puede modificar el código del agente (sistema operativo). Esta es una restricción realista, dado que no se modifica el sistema operativo cada vez que alguien desarrolla una aplicación para el usuario.
El siguiente pseudocódigo provee la implementación del agente, el cual delega trabajo en sub-agentes que proveen los materiales. Se provee una implementación intuitiva para cada fumador. ¿Qué problema presenta esta solución?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
main:
shared agent_sem := semaphore(1)
shared match := semaphore(0)
shared paper := semaphore(0)
shared tobacco := semaphore(0)
create_thread(agent)
create_thread(smoker_with_matches)
create_thread(smoker_with_paper)
create_thread(smoker_with_tobacco)
agent:
create_thread(agent_without_matches)
create_thread(agent_without_paper)
create_thread(agent_without_tobacco)
agent_without_matches:
while true do
wait(agent_sem)
signal(paper)
signal(tobacco)
agent_without_paper:
while true do
wait(agent_sem)
signal(match)
signal(tobacco)
agent_without_tobacco:
while true do
wait(agent_sem)
signal(match)
signal(paper)
smoker_with_matches:
while true do
wait(paper)
wait(tobacco)
make_cigarette()
signal(agent_sem)
smoke()
smoker_with_paper:
while true do
wait(match)
wait(tobacco)
make_cigarette()
signal(agent_sem)
smoke()
smoker_with_tobacco:
while true do
wait(match)
wait(paper)
make_cigarette()
signal(agent_sem)
smoke()
Corrija el pseudocódigo dado para que los agentes y fumadores logren su objetivo.
Sugerencia. La solución propuesta por Parnas usa tres hilos asistentes llamados pushers que responden a los avisos (signal) del agente, llevan cuenta de los ingredientes disponibles, y avisaan al fumador apropiado. Esta solución agrega las siguientes variables al código provisto:
1
2
3
4
5
6
7
8
9
main:
shared mutex := semaphore(1)
shared is_match := false
shared is_paper := false
shared is_tobacco := false
shared match_sem := semaphore(0)
shared paper_sem := semaphore(0)
shared tobacco_sem := semaphore(0)
Las variables booleanas indican si un ingrediente está o no disponible en la mesa. Los pushers usan los semáforos con nombre de ingrediente para avisar al fumador con tal ingrediente que los ingredientes complementarios están disponibles.
5. Concurrencia compartida declarativa (OpenMP)
OpenMP (Open Multi-Processing) es una tecnología desarrollada por varias empresas para implementar paralelismo de datos de manera más declarativa, o menos imperativa que Pthreads. No está diseñada para concurrencia de tareas, por ejemplo, no dispone de semáforos. Es una especificación para C/C++ y Fortran que varios compiladores implementan. Conviene tener a mano la guía de referencia al iniciar con esta tecnología. Para los ejemplos de esta sección cree una carpeta openmp/ en su repositorio personal de control de versiones para el curso.
5.1. Hola mundo (región paralela, directivas)
El siguiente es un "Hola mundo" en OpenMP. En adelante se usará C++, aunque OpenMP puede usarse perfectamente con C. Para trabajar con esta tecnología se requiere comprender conceptos como los siguientes:
-
Instrumentalización de código: el compilador modifica o inyecta código que no estaba en los programas de los desarrolladores.
-
Directivas del preprocesador (
pragma): son ignoradas por compiladores en los que no se ha habilitado la instrumentalización. -
Región paralela (
omp parallel): siempre implica la creación de un equipo de hilos. -
Barrera o join: está implícita en muchas directivas de OpenMP, como es el caso tras el bloque de instrucciones que conforman la región paralela (
omp parallel). -
En los Linux OpenMP usa Pthreads internamente. La instrumentalización traslada el código de la región paralela a una rutina, crea hilos con
pthread_create(), y espera por ellos conpthread_join(). -
El hilo principal no puede ejecutar trabajo durante la región paralela, a diferencia de Pthreads.
| j06-oct, v07-oct | Video |
|---|---|
Concurrencia de tareas declarativa: OpenMP |
|
Hola mundo en OpenMP. Directivas del preprocesador. Instrumentalización de código con OpenMP |
|
Región paralela. Bloque estructurado |
|
Invocación de subrutinas en la región paralela |
|
Indeterminismo en la salida por los operadores de flujo de C++. Región crítica (mutex) |
|
OpenMP con Google Sanitizers y Valgrind |
| Archivo | Descripción | Cambios |
|---|---|---|
Dice "hola mundo" desde hilos secundarios con OpenMP. En esta tecnología el hilo principal sólo crea y espera por los hilos secundarios por lo tanto, no puede realizar otra acción mientras los hilos secundarios están en ejecución. |
||
Agrega la bandera |
|
Para compilar con GCC o un compilador compatible debe habilitarse instrumentalización de OpenMP con la opción -fopenmp. El Makefile del ejemplo incluye esta bandera:
gcc -g -Wall -Wextra -fopenmp source.c -o executable
g++ -g -Wall -Wextra -fopenmp source.cpp -o executablePara poder usar OpenMP con Valgrind (y en algunas circuntancias con Google Sanitizers) es necesario recompilar la biblioteca de OpenMP que viene con el compilador. Es decir, descargar el código fuente del compilador, compilarlo con banderas que indiquen que se quiere habilitar el soporte para Valgrind (o Sanitizers), y posiblemente instalar el compilador en el sistema o hacerlo funcionar en como una alternativa al oficial de la distribución de Linux.
5.2. Hola mundo múltiple (funciones de biblioteca)
Modifique el programa de "hola mundo" para que cada hilo de ejecución salude indicando su número y la cantidad de hilos en el equipo al que pertenece. Permita al usuario indicar la cantidad de hilos como argumento de la línea de comandos. Si el usuario omite este argumento, suponga la cantidad de CPUs disponibles en el sistema. La siguiente podría ser una salida hipotética.
Hello from secondary thread 1 of 4
Hello from secondary thread 2 of 4
Hello from secondary thread 0 of 4
Hello from secondary thread 3 of 4Indague en la especificación cómo obtener el número de CPUs disponibles con OpenMP o bien, la cantidad sugerida de hilos a crear en una región paralela.
| j06-oct, v07-oct | Video |
|---|---|
Ejemplo |
|
Ejemplo de un bloque no estructurado |
| Archivo | Descripción | Cambios |
|---|---|---|
Cada hilo secundario saluda diciendo su número en el equipo (team) y la cantidad de miembros en el equipo. |
|
|
Facilita la construcción y prueba de la la solución. |
Aunque OpenMP no está diseñado para la concurrencia de tareas (por ejemplo, no provee semáforos), se puede conseguir separación de asuntos asignando a los hilos secundarios tareas distintas de acuerdo a su número de hilo (rank), por ejemplo:
1
2
3
4
5
6
7
#pragma omp parallel num_threads(2)
{
switch (omp_get_thread_num()) {
case 0: produce(); break;
case 1: consume(); break;
}
}
5.3. Repartir las iteraciones (omp parallel for)
La directiva omp parallel crea siempre una región paralela, que implica la creación y destrucción (join) de hilos de ejecución (a menos de que esté anidada). La instrucción o bloque paralelizado es ejecutado por todos los hilos del equipo. La directiva omp parallel for siempre debe estar seguida por un ciclo por contador (for) estructurado (sin terminaciones abruptas como break, continue, y return). Por ser una región paralela (por la palabra parallel) también crea y destruye hilos, pero a diferencia de omp parallel, omp parallel for reparte las iteraciones del ciclo entre los hilos creados.
Modifique el programa de Ejemplo 34 para repartir iteraciones entre hilos de ejecución. El programa debe permitir al usuario indicar en el segundo argumento opcional de la línea de comandos la cantidad de iteraciones. Si el usuario omite este argumento, tome la cantidad de hilos a crear, de tal forma que cada hilo tenga al menos una iteración con que trabajar.
El programa debe imprimir en la salida estándar el número de hilo y las iteraciones que realizó. Por ejemplo, para repartir 10 iteraciones entre 3 hilos, una salida podría ser:
$ bin/parallel_for 3 10
0/3: iteration 0/10
0/3: iteration 1/10
1/3: iteration 4/10
1/3: iteration 5/10
1/3: iteration 6/10
0/3: iteration 2/10
0/3: iteration 3/10
2/3: iteration 7/10
2/3: iteration 8/10
2/3: iteration 9/10¿Qué tipo de mapeo aplicó por defecto OpenMP? Como buena práctica de programación, impida que OpenMP escoja automáticamente el tipo de memoria entre datos privados o compartidos (default(none)).
| L10-oct, k11-oct | Video |
|---|---|
Repaso. Potencial concurrencia de tareas en OpenMP |
|
Ejemplo |
|
Restricciones: ciclo por contador y bloque estructurado |
|
Pasar valores a los hilos: |
| Archivo | Descripción | Cambios |
|---|---|---|
La directiva |
|
|
Facilita la construcción y prueba de la la solución. |
5.4. Reutilizar hilos (omp for)
Si se tienen varias regiones parallel for una tras otra que utilizan la misma cantidad de hilos, es ineficiente crearlos y destruirlos cada vez que se ingresa y sale de estas secciones, en especial si se encuentran dentro de un ciclo, de ahí la utilidad de la directiva for.
Modifique el programa de Ejemplo 35 para realizar tres etapas o fases de iteración. Es decir, tres ciclos for independientes uno tras otro. En cada ciclo se realiza la misma cantidad de iteraciones.
Optimice el programa para reutilizar los hilos. Es decir, en cada ciclo no cree ni destruya hilos, sino que créelos antes del primer ciclo y destrúyalos después del tercer ciclo. En cada ciclo los hilos son reutilizados.
El programa debe imprimir en la salida estándar la etapa en la que se encuentra, el número de hilo y las iteraciones que realizó. Las etapas siempre deben aparecer en orden y separadas entre ellas por un único cambio de línea. Por ejemplo, para repartir 5 iteraciones entre 2 hilos en las tres etapas, una salida podría ser:
$ ./several_for 2 5
stage 1: 0/2: iteration 0/5
stage 1: 1/2: iteration 3/5
stage 1: 1/2: iteration 4/5
stage 1: 0/2: iteration 1/5
stage 1: 0/2: iteration 2/5
stage 2: 1/2: iteration 3/5
stage 2: 1/2: iteration 4/5
stage 2: 0/2: iteration 0/5
stage 2: 0/2: iteration 1/5
stage 2: 0/2: iteration 2/5
stage 3: 1/2: iteration 3/5
stage 3: 1/2: iteration 4/5
stage 3: 0/2: iteration 0/5
stage 3: 0/2: iteration 1/5
stage 3: 0/2: iteration 2/5| L10-oct, k11-oct | Video |
|---|---|
Enunciado de reutilizar hilos ( |
|
Reutilizar hilos. Diferencia entre |
|
Barreras ( |
|
Anuncio: Ejercicio de ordenamiento par-impar. Comandos |
| Archivo | Descripción | Cambios |
|---|---|---|
La directiva |
|
|
Facilita la construcción y prueba de la la solución. |
5.5. Descomposición y mapeo en OpenMP (schedule)
Modifique el programa de Ejemplo 35 para repartir iteraciones entre hilos usando los tipos de mapeo (scheduling) provistos por OpenMP:
static static,N dynamic dynamic,N guided guided,N
Recuerde que el programa debe permitir al usuario indicar la cantidad de hilos y de iteraciones como argumentos opcionales en la línea de comandos. Agregue un tercer parámetro que equivale al número N de la lista de arriba, conocido como el "tamaño de bloque" (chunk en terminología de OpenMP). Si se omite, use el tipo de mapeo sin este parámetro.
Cree un arreglo dinámico de enteros, uno para cada iteración. Haga que los hilos marquen en el arreglo las iteraciones que les fueron asignadas, con su número identificador. Por ejemplo si se reparten 7 iteraciones entre 3 hilos, y si al hilo 2 le correspondieron las iteraciones 5 y 6 establecería
arr[5] := 2
arr[6] := 2Finalmente el programa debe imprimir en la salida estándar una tabla, con el tipo de mapeo en las filas, las iteraciones en las columnas, y los threads en las celdas. Por ejemplo, para repartir 10 iteraciones entre 3 threads, una salida sin N podría ser:
$ ./schedule 3 10
0 1 2 3 4 5 6 7 8 9
static 0 0 0 0 1 1 1 2 2 2
dynamic 0 1 0 2 1 0 2 1 0 2
guided 0 0 0 0 1 1 2 2 0 1La siguiente es una salida hipotética con N=2. Haga más corridas y trate de inferir el algoritmo de mapeo de cada planificación provista por OpenMP.
$ ./schedule 3 10 2
0 1 2 3 4 5 6 7 8 9
static,2 0 0 1 1 2 2 0 0 1 1
dynamic,2 0 0 1 1 0 0 2 2 1 1
guided,2 0 0 0 0 1 1 2 2 0 0| L10-oct, k11-oct | Video |
|---|---|
Descomposición (iteraciones) y mapeo (scheduling) en OpenMP. Mapeo estático por bloque |
|
Mapeo dinámico y mapeo guiado en OpenMP |
|
Mapeo guiado (guided scheduling). Diferencias entre GCC y Clang |
|
Parámetro tamaño de bloque en los mapeos de OpenMP. Mapeo cíclico |
| Archivo | Descripción | Cambios |
|---|---|---|
Reparte iteraciones entre hilos y guarda el rastro de qué hilo las ejecutó. |
|
|
Facilita la construcción y prueba de la la solución. |
Cree una versión reducida de Ejemplo 37 que escoja el tipo de mapeo (scheduling) en tiempo de ejecución con la variable ambiente OMP_SCHEDULE. Por ejemplo:
$ OMP_SCHEDULE=static bin/runtime_schedule 3 10
runtime 0 0 0 0 1 1 1 2 2 2
$ OMP_SCHEDULE=static,1 bin/runtime_schedule 3 10
runtime 0 1 2 0 1 2 0 1 2 0| j13-oct, v14-oct | Video |
|---|---|
Mapeo en tiempo de ejecución ( |
| Archivo | Descripción | Cambios |
|---|---|---|
Escoje el tipo de mapeo en tiempo de ejecución de acuerdo al valor de una variable ambiente |
|
|
Facilita la construcción y prueba de la la solución. |
5.6. Reducciones (reduction)
El paralelismo contribuye en incrementar la velocidad en que la máquina procesa colecciones de datos. Dos operaciones comunes derivadas del paradigma de programación funcional con la transformación de los valores de una colección en otros valores (map), y la reducción de los valores de una colección a uno sólo (reduce).
Haga un programa que lea un conjunto arbitrario de números flotantes de la entrada estándar, calcule concurrentemente el promedio y lo imprima en la salida estándar. La cantidad de números no se conoce de antemano. Para evitar la condición de carrera, use control de concurrencia (exclusión mutua). Sugerencia: cree primero una versión serial. Mida el rendimiento de una ejecución serial y la concurrente. El siguiente ejemplo de ejecución calcula el promedio de los primeros 10 millones de números.
seq 1 10000000 | perf stat bin/average_mutex
| j13-oct, v14-oct | Video |
|---|---|
Ejemplo de calcular el promedio ( |
| Archivo | Descripción | Cambios |
|---|---|---|
Calcula el promedio de números leídos de la entrada estándar de forma serial. |
||
Calcula el promedio de números leídos de la entrada estándar con varios hilos serializados con exclusión mutua. Esta implementación es menos eficiente que la versión serial. |
|
|
Reutiliza el archivo de |
La solución al ejemplo anterior tiene una serialización innecesaria provocada por el control de concurrencia para evitar una condición de carrera. Una alternativa es usar seguridad condicional (conditionally safety) ¿Qué diseño propondría usted para aplicar los beneficios de la seguridad condicional a la solución de este problema?
Una forma de crear seguridad condicional es con variables privadas declaradas en la pila de cada hilo de ejecución. Utilice este esquema para calcular sumas parciales. Aplique control de concurrencia para calcular la suma total.
| j13-oct, v14-oct | Video |
|---|---|
|
|
|
| Archivo | Descripción | Cambios |
|---|---|---|
Cada hilo calcula su suma parcial en una variable local privada con los elementos del arreglo que le correspondieron. Usa exclusión mutua para agregar su suma parcial a la total. |
|
|
Reutiliza el archivo de |
En el ejemplo anterior, la región crítica consta de una operación muy elemental, que los procesadores pueden ejecutar de forma excluyente entre sus núcleos, gracias a las operaciones atómicas en su conjunto de instrucciones. Lenguajes de programación como C11/C++11 disponen de decoraciones para instruir al compilador a usar operaciones atómicas. La tecnología OpenMP también dispone de este constructo. Use operaciones atómicas de OpenMP para reemplazar el control de concurrencia en el cálculo de la suma total.
| j13-oct, v14-oct | Video |
|---|---|
|
| Archivo | Descripción | Cambios |
|---|---|---|
Usa una operación atómica del procesador que es más eficiente que un mecanismo de control de concurrencia provisto por el sistema operativo. |
|
|
Facilita la construcción y prueba de la la solución. |
Modifique su solución a Ejemplo 41 para calcular el promedio de forma paralela usando reducciones de OpenMP. Compare su código resultante con la versión serial original.
| j13-oct, v14-oct | Video |
|---|---|
|
| Archivo | Descripción | Cambios |
|---|---|---|
Utiliza la notación compacta de las reducciones, que es semejante a la versión serial más una decoración con directivas. |
|
|
Facilita la construcción y prueba de la la solución. |
5.7. Tareas (task)
OpenMP permite fácilmente repartir las iteraciones de ciclos por contador (for estructurados). Sin embargo, los ciclos por contador no son la única forma de repetición que podría necesitarse paralelizar, también existen ciclos por condición (while y for no estructurados) y la recursión (ej.: el recorrido por una lista o árbol). Para poder paralelizar este tipo de repeticiones, OpenMP v3 introdujo el concepto de tareas y OpenMP v4 grupos de tareas.
Dentro de una región paralela, algunos o todos los hilos pueden crear tareas siempre y cuando sean independientes entre sí. Las tareas se ejecutarán luego en cualquier orden. Cada vez que un hilo encuentre una directiva #pragma omp task, el hilo creará una tarea y la pondrá en una cola para su ejecución posterior. Cuando un hilo llega al final de la región paralela, sacará repetitivamente tareas de la cola y las ejecutará. Las tareas pueden crear otras tareas que serán también colocadas al final de la cola. Una vez que la cola esté vacía, ya no quedará trabajo pendiente en la región paralela y el hilo se destruirá (join).
Escriba un programa que lea palabras de la entrada estándar hasta que estas se acaben. Piense que cada palabra es una tarea y las tareas deben hacerse de forma concurrente. El objetivo con cada tarea es simplemente imprimir la palabra en la salida estándar, separada de otras por un espacio en blanco, de manera que se forme una oración con indeterminismo (con sentido o no). Su programa debe crear tareas de OpenMP que respeten estas reglas:
-
La primera palabra leída de la entrada estándar debe siempre imprimirse de primero.
-
Las demás palabras se imprimen indeterminísticamente en cualquier orden separadas por un espacio en blanco.
-
La oración siempre debe terminar en punto.
Todas las tres reglas anteriores deben ser realizadas por tareas de OpenMP. Ejemplos de ejecución:
$ echo El niño pobre | bin/shuffle_sentence El pobre niño. $ echo El del niño mordió al papá perro | bin/shuffle_sentence El papá mordió al perro del niño. $ echo El del niño mordió al papá perro | bin/shuffle_sentence El mordió perro al papá niño del.
Puede tomar el siguiente código como punto de partida.
| Archivos | Descripción |
|---|---|
Código C++ inicial para barajar la oración. |
6. Distribución simétrica (MPI)
El paradigma de programación distribuido permite crear programas escalables que aprovechan máquinas que pueden correr procesos y pueden comunicarse a través de redes de computadoras. En la concurrencia de recursos compartidos, los hilos pueden acceder a la misma memoria y el mismo reloj sin intervención del sistema operativo. En la concurrencia de recursos distribuidos, los procesos tienen cada uno su propia memoria exclusiva y los relojes pueden ser distintos, por lo que tienen que comunicarse a través de los mecanismos provistos por el sistema operativo para intercomunicación de procesos, normalmente el paso de mensajes.
Existen dos variantes de la distribución. En la distribución heterogénea, los ambientes en el que corre el programa son distintos: diferente hardware, sistema operativo, huso horario, etc., lo que forma una malla de computadoras. En la distribución homogénea, el ambiente (tanto el hardware como el software) debe ser idéntico para todos los procesos del programa, lo que se llama un clúster de computadoras. La distribución homogénea logra conseguir los mayores niveles de paralelismo.
| L17-oct, k18-oct | Video |
|---|---|
Paradigma de programación distribuida |
|
Repaso de distribución |
|
Especificación MPI. Implementaciones: MPICH, Open MPI. Instalación de Open MPI |
|
Correr comandos con |
6.1. Interfaz de paso de mensajes (MPI)
Message Passing Interface (MPI) es una tecnología de distribución homogénea creado por un grupo de académicos con el fin de facilitar el parelismo de aplicaciones científicas, que se convirtió en un estándar de facto. Existen otras tecnologías como Charm++ de más alto nivel.
Cree una carpeta mpi/ en su repositorio de control de versiones. Para el pseudocódigo se utilizará la siguiente convención de paso de mensajes:
// Global constants
process_number // Number of this process (integer)
process_count // Number of processes in the team this process belongs to
process_hostname // Name of the computer where this process is running (text)
any_process // For accepting messages from any process
any_tag // For accepting messages classified with any tag
// Send a variable or array (a set of bytes) to the destination process
send(message, count, to_process, tag = 0)
// Receive a set of bytes into a variable from a source process
receive(&message, count, from_process = any_process, tag = any_tag)
// Send a variable or array from the source process to the rest
broadcast(&message, count, from_process)
// Reduce the data value from all processes to a single result value in
// destination process applying the given operation
reduce(data, &result, count, operation, to_process)
// Reduce the data value from all processes to a single result value that will
// be available in all processes
all_reduce(data, &result, count, operation)
// Distributes an array into subsets for each process using block mapping
scatter(entire_array, entire_count, &subset_array, &subset_count, from_process)
// Updates the entire array from the subsets that where assigned to each process
gather(&entire_array, entire_count, subset_array, subset_count, to_process)
// Get the wall time for the calling process
wall_time()
// Make all processes of a team wait until all of them have reached the barrier
wait_barrier()6.2. Concepto de proceso
Un proceso es un programa en ejecución. De un mismo ejecutable se pueden crear múltiples procesos, por ejemplo, correr varias instancias de un procesador de palabras para editar archivos distintos. Cada instancia sería un proceso independiente. Si uno de ellos produce una excepción, los demás continuarán ejecutándose. Los procesos permiten resolver problemas que requieren separación de asuntos o incremento de desempeño. La tecnología MPI está diseñada para facilitar la creación de procesos para incrementar el desempeño (paralelismo de datos).
6.2.1. Hola mundo en MPI
Haga que cada proceso del equipo salude, indicando su número, la cantidad de procesos miembros del equipo, y la máquina desde la que se ejecuta.
Hello from main thread of process 0 of 3 on hostname1 Hello from main thread of process 2 of 3 on hostname2 Hello from main thread of process 1 of 3 on hostname2
Dado que existe indeterminismo por la salida estándar, la salida que su programa obtenga sea distinta a la anterior.
| L17-oct, k18-oct | Video |
|---|---|
Ejemplo |
|
Documentación de MPI. |
|
Process rank (número de proceso). Tamaño del mundo (cantidad de procesos). Nombre del procesador (nombre de la máquina) |
|
Reusar |
|
Correr localmente el ejemplo de hola mundo. Errores de Sanitizers y Valgrind. |
|
Pregunta: Depuración y análisis de código distribuido. Bitácoras. Monitoreo. Visualización |
|
Correr el ejemplo de hola mundo en el clúster con MPICH. Mapeo cíclico con bloques (slots) de procesos a nodos |
|
Correr el ejemplo de hola mundo en el clúster con Open MPI. Mapeo por bloque (slots) de procesos a nodos |
|
Editar archivos remotamente: |
| Archivo | Descripción | Cambios |
|---|---|---|
Diseño en pseudocódigo de la solución. |
||
Dice "hola mundo" desde uno o varios procesos en una o varias máquinas. |
||
Reutiliza el archivo de Makefile usando la directiva |
||
Archivo de hosts para distribuir entre los nodos del clúster Arenal de la ECCI con MPICH, ej.: |
||
Archivo de hosts para distribuir entre los nodos del clúster Arenal de la ECCI con Open MPI, ej.: |
6.2.2. Compilación y ejecución de programas con MPI
Para compilar programas con MPI se requiere instalar una implementación de MPI como MPICH (preferible) u Open MPI. Conviene instalarlo también en su computadora personal. Si su extensión es basada en Debian, puede instalar MPICH con los comandos:
sudo apt update
sudo apt install mpichPara compilar se debe invocar al compiler wrapper mpicc o mpic++ el cual pasa parámetros al compilador de GCC para que ubique los encabezados y las bibliotecas del MPI instalado, por ejemplo:
mpicc -g -Wall -Wextra file.c -o appSi usa el Makefile genérico, puede indicarle que invoque a los wrappers en lugar del compilador de GCC, sobrescribiendo las variables CC (C-Compiler) y XC (C++ Compiler):
include ../../common/Makefile
CC=mpicc
XC=mpic++Si se quiere que el programa corra en varios nodos de un clúster, se requiere un archivo que los liste, uno por línea, además el tamaño de bloque, que indica la antidad de la cantidad de procesos a asignar por nodo (slots). La sintaxis varía dependiendo de la implementación. Para MPICH se indica la cantidad de procesos en la misma línea separado por dos puntos (:) por ejemplo:
node1:4
node2:4
node3:2El archivo anterior indica que se quieren correr 4 procesos en la computadora cuyo nombre es node1, cuatro procesos en node2, y 2 procesos en node3. La implementación Open MPI usa el texto slots= para indicar la cantidad de procesos en cada nodo. El ejemplo anterior se escribiría:
node1 slots=4
node2 slots=4
node3 slots=2Es común que en los clústers de computadoras se ofrezcan archivos preconfigurados como los anteriores o preferiblemente se usen sistemas de colas. Por ejemplo, para el clúster de Arenal de la ECCI, se ofrecen copias en la carpeta /etc/skel/, la cual se copia cuando se crean las cuentas de usuario, por lo que probablemente disponga de ellos en su carpeta de usuario.
Ambas tecnologías reparten los procesos usando un mapeos estáticos distintos. Los números en el archivo de hosts corresponden a tamaños de bloque. Por ejemplo, en MPICH si se crean 13 procesos se asignarán los primeros 4 al node1, los siguientes 4 al node2, los siguientes 2 al node3, y los restantes 3 al node1 como se ve a continuación:
node1: 0 1 2 3 10 11 12
node2: 4 5 6 7
node3: 8 9Para correr un programa en un clúster con MPICH, se usa el comando
mpiexec -np P -f hosts.txt bin/my_program argsdonde P es la cantidad de procesos que se quieren correr en el clúster. En Arenal MPICH está cargado por defecto. Los siguientes comandos cambian el ambiente a Open MPI (comando module) y nótese cómo los argumentos para mpiexec difieren para esta tecnología:
module clear
module load compilers/gcc-9.4.0
module load mpi/openmpi-4.1.1
mpiexec --oversubscribe --bind-to none -np P --hostfile hosts.txt bin/my_program argsEl parámetro --oversubscribe indica a Open MPI que permita crear más procesos que la cantidad de procesos indicados en el archivo de hosts. El parámetro --bind-to indica cuál es el valor de referencia para establecer el máximo de hilos a permitir por proceso. Por defecto se usa la cantidad de procesadores disponibles, mientras que el valor none deshabilita este tope y permite a los programas o usuarios escoger la cantidad de hilos sin restricciones.
6.3. Distribución híbrida (proceso-hilo)
Los procesos (distribución) no ejecutan código, sino los hilos (concurrencia) dentro de sí, y los hilos no pueden existir si no es dentro de un proceso. Dado que se puede crear una cantidad arbitraria de procesos y en cada uno de ellos, una cantidad arbitraria de hilos, se tiene un modelo híbrido de ejecución distribuida-concurrente que aproveche las ventajas de cada paradigma.
6.3.1. Procesos e hilos de ejecución
El ejemplo de "Hola mundo" lanza un único hilo principal (main thread) en cada proceso ejecutado. Modifique el programa para que cada proceso lance tantos hilos secundarios (secundary thread) como CPUs hay disponibles en la máquina donde se ejecuta. Cada hilo secundario debe imprimir en la salida estándar una línea antecedida por un tabulador en la que salude al usuario. Por ejemplo si se lanzan dos procesos y cada uno crea tres hilos secundarios, se podría obtener una salida como la siguiente:
Hello from main thread of process 0 of 2 on hostname1 Hello from thread 0 of 3 of process 0 on hostname1 Hello from thread 2 of 3 of process 0 on hostname1 Hello from thread 1 of 3 of process 0 on hostname1 Hello from main thread of process 1 of 2 on hostname2 Hello from thread 1 of 3 of process 1 on hostname2 Hello from thread 0 of 3 of process 1 on hostname2 Hello from thread 2 of 3 of process 1 on hostname2
Dado que existe indeterminismo por la salida estándar, la salida que obtenga puede ser muy distinta a la anterior. Sugerencia: Puede usar OpenMP junto con MPI para lograr el modelo de concurrencia híbrida solicitada en esta actividad.
| j20-oct, v21-oct | Video |
|---|---|
Ejemplo |
|
Modelo de ejecución de MPI (ssh, nfs) |
|
Rastreo de procesos e hilos. Mecanismos de intercomunicación de procesos (IPC) |
|
|
| Archivo | Descripción | Cambios |
|---|---|---|
Diseño en pseudocódigo de la solución híbrida entre distribución y concurrencia imperativa (Pthreads). |
||
Diseño en pseudocódigo de la solución híbrida entre distribución y concurrencia declarativa (OpenMP). |
||
Dice "hola mundo" desde el hilo principal e hilos secundarios (OpenMP) en varios procesos (MPI). |
|
|
Agrega la bandera |
|
|
Archivo de hosts para distribuir entre los nodos del clúster Arenal de la ECCI con MPICH, ej.: |
||
Archivo de hosts para distribuir entre los nodos del clúster Arenal de la ECCI con Open MPI, ej.: |
6.3.2. Mapeo híbrido (proceso-hilo)
En capítulos previos se ha usado la concurrencia también para el paralelismo de datos, es decir, repartir trabajo entre hilos mediante descomposición y mapeo. El modelo de ejecución híbrido permite repartir trabajo entre procesos y luego entre hilos. En tecnologías declarativas como OpenMP, la unidad de descomposición (iteraciones) y los tipos de mapeos están implementados de antemano. En tecnologías imperativas, la descomposición y el mapeo es implementado manualmente por las personas desarrolladoras. Este es el caso de MPI, aunque se proveen subrutinas muy elementales para distribuir datos que se verán luego.
Modifique el programa del Ejemplo 45 (hello_hybrid) para que reciba un rango indicado como dos números enteros [a,b[ en los argumentos de línea de comandos. Su programa debe distribuir (particionar) el rango entre los procesos de forma lo más equitativa posible, y dentro de los procesos debe distribuir los subrangos entre los hilos de ejecución.
El hilo principal de cada proceso debe reportar en la salida estándar el rango asignado al proceso. Use la notación hostname:process.thread: message como prefijo para simplificar la salida. Cada hilo secundario debe reportar su rango asignado antecedido por un tabulador. La siguiente podría ser una interacción con su programa en dos nodos de un clúster, cada uno con un proceso por nodo, y cada nodo con tres CPU:
$ mpiexec -n 2 -f hosts.txt bin/hybrid_distr_arg 3 20
hostname1:0: range [3, 12[ size 9
hostname1:0.0: range [3,6[ size 3
hostname1:0.1: range [6,9[ size 3
hostname1:0.2: range [9,12[ size 3
hostname2:1: range [12, 20[ size 8
hostname2:1.0: range [12,15[ size 3
hostname2:1.1: range [15,18[ size 3
hostname2:1.2: range [18,20[ size 2Reporte además el tamaño del rango asignado a cada proceso e hilo de ejecución. Puede tomar el siguiente código como punto de partida.
| Archivos | Descripción |
|---|---|
Diseño preliminar en pseudocódigo de la solución. |
|
Código C++ inicial para la distribución del rango en argumentos |
| j20-oct, v21-oct | Video |
|---|---|
|
|
|
|
|
|
|
| Archivo | Descripción | Cambios |
|---|---|---|
Diseño en pseudocódigo de la solución. |
|
|
Distribuye el rango en los argumentos de línea de comandos entre procesos y entre hilos usando mapeo por bloque. |
|
|
Facilita la construcción y prueba de la la solución. |
||
Archivo de hosts para distribuir entre los nodos del clúster Arenal de la ECCI con MPICH, ej.: |
||
Archivo de hosts para distribuir entre los nodos del clúster Arenal de la ECCI con Open MPI, ej.: |
6.4. Comunicación punto a punto (send-receive)
La comunicación punto a punto envía mensajes de un proceso a otro que forman parte del mismo equipo. MPI provee una familia de funciones para enviar y recibir mensajes. Las dos más básicas son: MPI_Send y MPI_Recv.
6.4.1. Envío y recepción de escalares
Modifique el ejemplo Ejemplo 44 (hello) para que los procesos saluden en orden por su identificador (rank). Dado que la función de comunicación punto a punto MPI_Recv implica bloqueo, y la espera es el mecanismo fundamental del control de concurrencia, puede usarse para sincronizar procesos, junto con MPI_Send. La salida será siempre determinística, por ejemplo:
Hello from main thread of process 0 of 3 on a_host Hello from main thread of process 1 of 3 on other_host Hello from main thread of process 2 of 3 on a_host
Cada proceso debe escribir en la salida estándar su saludo. Controle la concurrencia de esta impresión con comunicación punto-a-punto simulando semáforos.
| L24-oct, k25-oct | Video |
|---|---|
Comunicación punto a punto. Primitivas send y receive. Entrada y salida blocking o sincrónica |
|
|
|
|
|
Repaso ejemplo |
|
|
|
|
| Archivo | Descripción | Cambios |
|---|---|---|
Diseño en pseudocódigo de la solución. |
|
|
Siempre los procesos saludan en orden. El proceso 0 imprime su saludo y avisa al siguiente. Los demás procesos esperan a recibir la señal del proceso previo. |
|
|
Facilita la construcción y prueba de la la solución. |
||
Archivo de hosts para distribuir entre los nodos del clúster Arenal de la ECCI con MPICH, ej.: |
||
Archivo de hosts para distribuir entre los nodos del clúster Arenal de la ECCI con Open MPI, ej.: |
6.4.2. Envío y recepción de arreglos
El paso de mensajes en MPI es orientado a arreglos. Es decir, las operaciones pueden enviar no sólo un elemento (escalar), sino varios de ellos (vectorial), siempre y cuando estén serializados en la memoria. También permite separar asuntos de acuerdo al número de proceso (rank).
Modifique la solución a la Ejemplo 47 (send_recv_ord_sem) para que los procesos saluden en orden por su identificador (rank) a través de un intermediario. Es decir, los procesos envían su saludo a uno del equipo, quien recibe los saludos y los imprime en la salida estándar en orden.
Al usar un itermediario con comunicación punto a punto, se simula "seguridad condicional". Note que los saludos son información vectorial y no escalar. Tenga presente que no es posible enviar datos discontinuos de la memoria a través de la red en una operación de send/receive.
| L24-oct, k25-oct | Video |
|---|---|
|
|
|
|
|
|
|
| Archivo | Descripción | Cambios |
|---|---|---|
Diseño en pseudocódigo de la solución. |
|
|
Todos los procesos envían mensajes de saludo al intermediario (proceso 0) quien los recibe en cualquier orden, pero los imprime en orden del número de proceso (rank) en la salida estándar. |
|
|
Facilita la construcción y prueba de la la solución. |
||
Archivo de hosts para distribuir entre los nodos del clúster Arenal de la ECCI con MPICH, ej.: |
||
Archivo de hosts para distribuir entre los nodos del clúster Arenal de la ECCI con Open MPI, ej.: |
6.4.3. Indeterminismo del paso de mensajes
La comunicación punto a punto en MPI es indeterminística entre procesos distintos, pero no entre los mismos procesos. Por ejemplo, si varios procesos envían mensajes a un receptor, los mensajes llegarán en cualquier orden. Pero si un proceso A envía varios mensajes a otro proceso B, los mensajes llegarán en el mismo orden en que fueron enviados.
Modifique la solución de la Ejemplo 48 (send_recv_ord_itm) para que usando comunicación punto a punto, los procesos saluden al proceso intermediario y éste reporte los saludos en el orden en que los recibió.
| L24-oct, k25-oct | Video |
|---|---|
|
| Archivo | Descripción | Cambios |
|---|---|---|
Diseño en pseudocódigo de la solución. |
|
|
Todos los procesos envían mensajes de saludo al intermediario (proceso 0) quien los recibe e imprime en el orden en que los recibió, y no en el orden de número de proceso (rank). |
|
|
Facilita la construcción y prueba de la la solución. |
||
Archivo de hosts para distribuir entre los nodos del clúster Arenal de la ECCI con MPICH, ej.: |
||
Archivo de hosts para distribuir entre los nodos del clúster Arenal de la ECCI con Open MPI, ej.: |
6.4.4. Tipos de send y receive en MPI
MPI ofrece una familia de funciones de send y receive que varían principalmente en:
-
Si permiten a las personas desarrolladoras controlar los buffers de memoria que se usan para enviar o recibir datos, marcadas con una
Ben su nombre, comoMPI_Bsend(). -
Si se bloquean (por defecto) o no mientras se realiza la operación. Las que no se bloquean están marcadas con una
Ien su nombre, por ejemploMPI_ISend(). Estas funciones retornan inmediatamente, pero invocan a un manejador de eventos cuando su operación finalmente haya tenido efecto. -
Si la función de envío espera hasta que los datos hayan sido recibidos por completo por el proceso receptor. En tal caso se marcan con una
Rde ready, comoMPI_RSend(). No aplica para las funciones de receive.
La siguiente tabla resume las combinaciones que pueden generarse de las variantes anteriores. Las funciones están ordenadas por la duración de su efecto, de la que tardaría menos hasta la que duraría más.
| Function | Blocking | Description | |
|---|---|---|---|
Send |
|||
I |
|
Nonblocking |
Starts copying data to buffer |
B |
|
Blocking |
Allows control of sending buffer |
Ib |
|
Nonblocking |
Starts copying to a controlled buffer |
S |
|
Blocking |
Blocks until data has started to arrive to target |
R |
|
Blocking |
Blocks until data has completely arrived to target |
Ir |
|
Nonblocking |
Starts sending, callbacks until data has arrived to target |
Receive |
|||
|
Blocking |
Blocks until all data has been received and copied to process' memory |
|
I |
|
Nonblocking |
Callbacks when all data has been received and copied to process' memory |
M |
|
Blocking |
Allow control how message matching is done? |
Im |
|
Nonblocking |
Allow control how message matching is done? |
| L24-oct, k25-oct | Video |
|---|---|
Tipos de send y receive en MPI: blocking, non-blocking (I), buffered (B) y ready (R) |
6.5. Lectura distribuida
Modifique la solución de la Ejemplo 49 (send_recv_urd) para que:
-
Los procesos lean un arreglo de números en la entrada estándar con los cuales trabajar. Luego cada proceso imprime los números que leyó en la salida estándar.
-
Haga las correcciones para que todos los procesos tengan y puedan efectivamente imprimir el arreglo.
-
Los procesos reporten en la salida estándar la cantidad de segundos en que tarda su ejecución.
| L24-oct, k25-oct | Video |
|---|---|
|
|
|
|
|
|
|
| Archivo | Descripción | Cambios |
|---|---|---|
Diseño en pseudocódigo de la solución. |
|
|
MPI sólo permite al proceso 0 leer. Este debe reenviar copias de los datos o asignar fracciones de los mismos para que los otros hilos puedan realizar su trabajo. La función |
|
|
Facilita la construcción y prueba de la la solución. |
||
Archivo de hosts para distribuir entre los nodos del clúster Arenal de la ECCI con MPICH, ej.: |
||
Archivo de hosts para distribuir entre los nodos del clúster Arenal de la ECCI con Open MPI, ej.: |
||
Un archivo con algunos números para poder probar redireccionando la entrada, ej: |
MPI permite que sólo el proceso 0 lea de la entrada estándar. Más específicamente, la entrada la lee el comando mpiexec, la captura y la envía al proceso 0. Los demás procesos no reciben la entrada, por tanto si intentan leer, se quedarán bloqueados perennemente. Si un proceso debe leer de la entrada estándar, el proceso 0 tendrá que usar comunicación para enviarla a los demás procesos.
La lectura de archivos nombrados no sufre las limitaciones de la entrada estándar en MPI. Normalmente los clústers de computadoras se configuran para que un archivo esté disponible en todos los nodos esclavos, por ejemplo, haciendo que el disco duro donde se encuentran los datos de los usuarios, esté compartido por todas las máquinas. De esta manera, los procesos creados con MPI tendrán acceso al mismo archivo y podrán leerlo de forma concurrente. Como es de esperar, el archivo nombrado forma un recurso compartido entre procesos, de tal forma que si se modifica de forma concurrente sin control de concurrencia o seguridad condicional, provocará una condición de carrera y potencialmente contamine el archivo.
Para calcular la duración en segundos del tiempo en la pared use la función MPI_Wtime. La medición del tiempo en los sistemas distribuidos es un problema sumamente complejo, dado que los procesos pueden ejecutarse en máquinas distintas, y por consiguiente, con diferentes relojes no perfectamente sincronizados entre sí. La función MPI_Wtime() reporta un tiempo transcurrido en segundos que un proceso puede usar como referencia para sí mismo, pero no es válido para otros procesos.
6.6. Barreras distribuidas
Implementar mecanismos de control de concurrencia distribuida es menos eficiente que en concurrencia de recursos compartidos, por lo que puede explicar su menor número. Las operaciones de send y receive pueden usarse para enviar avisos (signaling) como se hace con los semáforos. MPI ofrece barreras con la subrutina MPI_Barrier() que imponen espera a un equipo de procesos hasta que todos los miembros hayan alcanzado la barrera.
Simule una carrera de relevos, donde los competidores son procesos en equipos. Cada equipo consta de dos corredores. Un corredor tomará la estafeta (en inglés, baton) y se posicionará en la línea de salida. El otro corredor esperará en la mitad de la pista a que el primer corredor llegue y le transfiera la estafeta. En tal momento, el segundo corredor seguirá a toda velocidad hasta alcanzar la meta.
Usted puede imponer restricciones sobre la cantidad de procesos con los que deberá ser ejecutada la simulación. Por ejemplo, un número mínimo de procesos que puede ser par o impar de acuerdo a sus decisiones de separación de asuntos. Idee un mecanismo para decidir qué procesos pertenecen al mismo equipo. Por ejemplo, los procesos 1 y 2 podrían conformar el equipo 1, los procesos 3 y 4 al equipo 2, y así sucesivamente. Si se invoca con una cantidad no adecuada de procesos, la simulación deberá detenerse y emitir un mensaje de error que ayude al usuario a escoger el número correcto.
Cada proceso recibirá dos parámetros: la duración en milisegundos que tarda el primer corredor atravesando la etapa 1 de la carrera (entre la salida y la mitad de la pista), y la duración en milisegundos del segundo corredor atravesando la etapa 2 de la carrera (de la mitad de la pista hasta la meta). Suponga que los corredores de una etapa tardan exactamente esta duración y no un valor generado al azar. Ejemplo de ejecución:
$ mpiexec -np 10 -f hosts.txt bin/relay_race_dist 1100 900
Place 1: team 3 in 2.35075s
Place 2: team 4 in 2.35085s
Place 3: team 5 in 2.35087s
Place 4: team 2 in 2.35089s
Place 5: team 1 in 2.35092sPuede usar el siguiente código como punto de partida.
| Archivo | Descripción |
|---|---|
Pseudocódigo inicial para la carrera de relevos distribuida. |
|
Código inicial para la carrera de relevos distribuida en C++ con MPI. |
| j27-oct, v28-oct | Video |
|---|---|
|
|
Solución con metáforas visuales. Modelos centralizados y descentralizados |
|
Solución en pseudocódigo: subrutina |
|
Pseudocódigo de los corredores de las etapas 1 y 2. Barreras en MPI ( |
|
Pseudocódigo del árbitro |
|
Implementación con MPI. Tiempo transcurrido desde el punto de vista del árbitro |
| Archivo | Descripción | Cambios |
|---|---|---|
Diseño en pseudocódigo de la solución. |
|
|
Implementación con MPI de la simulación de la carrera de relevos distribuida. |
|
|
Facilita la construcción y prueba de la la solución. |
||
Archivo de hosts para distribuir entre los nodos del clúster Arenal de la ECCI con MPICH, ej.: |
||
Archivo de hosts para distribuir entre los nodos del clúster Arenal de la ECCI con Open MPI, ej.: |
6.7. Comunicación colectiva
MPI permite dos formas de paso de mensajes:
-
Punto a punto donde un proceso envía (send) un mensaje directamente a otro proceso, quien explícitamente lo recibe (receive).
-
Comunicación colectiva donde un proceso envía un mensaje a todos los demas (broadcast), o un proceso recibe mensajes de todos los demas (reduction).
6.7.1. Difusión de mensajes (broadcast)
Modifique la solución de la Ejemplo 50 (stdin_sendrecv) para que el proceso intermediario comparta los valores leídos de la entrada estándar con los demás procesos mediante comunicación colectiva.
| j27-oct, v28-oct | Video |
|---|---|
|
|
|
| Archivo | Descripción | Cambios |
|---|---|---|
Diseño en pseudocódigo de la solución. |
|
|
Usa las capacidades de comunicación colectiva de MPI para copiar el arreglo que el proceso 0 lee de la entrada estándar en los demás procesos del equipo. |
|
|
Facilita la construcción y prueba de la la solución. |
||
Archivo de hosts para distribuir entre los nodos del clúster Arenal de la ECCI con MPICH, ej.: |
||
Archivo de hosts para distribuir entre los nodos del clúster Arenal de la ECCI con Open MPI, ej.: |
||
Un archivo con algunos números para poder probar redireccionando la entrada, ej: |
En una difusión (broadcast) un proceso cualquiera llamado raíz envía datos a todos los demás procesos del equipo. Los demás procesos recibirán, y por tanto, esperarán, por los datos si llegan al broadcast antes que el emisor (raíz). Internamente los procesos crean un árbol de envíos, donde el proceso emisor (raíz) envía los datos a otros dos, y éstos a su vez a otros dos, y así recursivamente hasta completar todos los procesos del equipo. Idealmente todos los procesos del equipo deben ejecutar la invocación al broadcast, de lo contrario, el equipo de procesos se quedaría bloqueado (aunque los procesos "hoja" podrían no provocar este comportamiento).
6.7.2. Reducciones (reduce)
Escriba un programa donde cada proceso escoge al azar su número de la suerte entre 00 y 99 inclusive. Haga que el proceso 0 reporte el mínimo, el promedio, y el máximo de los números de la suerte escogidos entre todos los procesos. El siguiente puede ser un ejemplo de ejecución:
$ mpiexec -np 5 -f hosts.txt bin/lucky_number_reduce
Process 0: my lucky number is 83
Process 0: all minimum: 10
Process 0: all average: 44.20
Process 0: all maximum: 83
Process 1: my lucky number is 56
Process 2: my lucky number is 10
Process 3: my lucky number is 10
Process 4: my lucky number is 62Para su solución y generar números pseudoaleatorios, puede usar el siguiente código base en C++.
| Archivo | Descripción |
|---|---|
Pseudocódigo inicial para el diseño de la solución. |
|
Código inicial para la implementación de la solución. |
|
Clase en C++ para generar números pseudoaleatorios en un rango con distribución uniforme. |
|
Ejemplo de uso de la clase anterior. Crea un comando que recibe tres argumentos |
| L31-oct, k01-nov | Video |
|---|---|
|
|
|
|
|
|
|
|
Cómo funciona la reducción en MPI. Árbol binario de reducción. Usar número de proceso en la semilla de números aleatorios. |
| Archivo | Descripción | Cambios |
|---|---|---|
Diseño en pseudocódigo de la solución. |
|
|
Todos los procesos escogen un número de la suerte al azar y lo envían al proceso 0 quien imprime estadísticas. Note que se usa el número de proceso en la semilla para generar números pseudoaletorios para evitar que los procesos escojan el mismo número de la suerte. |
|
|
Clase en C++ para generar números pseudoaleatorios en un rango con distribución uniforme. Es parte del código inicial dado en el enunciado. |
||
Facilita la construcción y prueba de la la solución. |
||
Archivo de hosts para distribuir entre los nodos del clúster Arenal de la ECCI con MPICH, ej.: |
||
Archivo de hosts para distribuir entre los nodos del clúster Arenal de la ECCI con Open MPI, ej.: |
6.7.3. Difusión de reducciones (all-reduce)
Modifique su programa de la Ejemplo 53 (lucky_number_reduce) para que cada proceso escoja al azar su número de la suerte entre 00 y 99 inclusive, y el mismo proceso reporta si su número es el menor o el mayor de los números escogidos por todos los procesos. El siguiente puede ser un ejemplo de ejecución:
$ mpiexec -np 5 -f hosts.txt bin/lucky_number_who
Process 0: my lucky number (83) is greater than the average (36.00)
Process 0: my lucky number (83) is the maximum (83)
Process 1: my lucky number (18) is less than the average (36.00)
Process 2: my lucky number (07) is less than the average (36.00)
Process 2: my lucky number (07) is the minimum (07)
Process 3: my lucky number (46) is greater than the average (36.00)
Process 4: my lucky number (26) is less than the average (36.00)El reporte de mínimo, máximo y promedio es independiente. Por ejemplo, si sólo un proceso se ejecuta cumplirá los tres criterios:
$ mpiexec -np 1 -f hosts.txt bin/lucky_number_who
Process 0: my lucky number (31) is the minimum (31)
Process 0: my lucky number (31) is equals to the average (31.00)
Process 0: my lucky number (31) is the maximum (31)Puede usar el siguiente código como punto de partida.
| Archivo | Descripción |
|---|---|
Pseudocódigo inicial para el diseño de la solución. |
|
Código inicial para la implementación de la solución. |
| L31-oct, k01-nov | Video |
|---|---|
|
|
|
|
Otros temas de MPI: scatter, gather, soporte multi-hilos, paralelización de archivos. |
| Archivo | Descripción | Cambios |
|---|---|---|
Diseño en pseudocódigo de la solución. |
|
|
Cada proceso escoge un número de la suerte y lo envía a todos los demás. Pero en lugar de recibir los números enviados, cada proceso recibe el mínimo, la suma y el máximo de los números escogidos. Con estas reducciones cada proceso calcula el promedio y compara su número de la suerte contra estos estadísticos. |
|
|
Clase en C++ para generar números pseudoaleatorios en un rango con distribución uniforme. Es parte del código inicial dado en el enunciado del problema anterior. |
||
Facilita la construcción y prueba de la la solución. |
||
Archivo de hosts para distribuir entre los nodos del clúster Arenal de la ECCI con MPICH, ej.: |
||
Archivo de hosts para distribuir entre los nodos del clúster Arenal de la ECCI con Open MPI, ej.: |
6.7.4. Descomposición y mapeo distribuido (scatter y gather)
MPI ofrece la función MPI_Scatter() que toma un vector de valores y los reparte entre todos los procesos de un equipo, incluyendo al mismo que tiene el vector original. Usa un mapeo estático por bloque.
MPI_Scatter() tiene la limitación de que la cantidad de elementos en el vector tiene que ser múltiplo de la cantidad de procesos P. En caso contrario produce un error. La subrutina MPI_Scatterv() rompe esta limitación, pero requiere que el invocador construya de antemano una estructura de datos que indique los rangos del vector que cada proceso recibirá.
Una vez que un vector ha sido repartido entre procesos, estos realizarán algún trabajo con los valores asignados y probablemente querrán regresar los resultados al proceso que repartió los datos. Las subrutinas MPI_Gather() y MPI_Gatherv() realizan el trabajo de recolectar los datos distribuidos entre los procesos y consolidarlos en el vector original.
Las funciones MPI_Scatter() y MPI_Gather() sufren de una limitación artificial, mientras que la interfaz de las funciones MPI_Scatterv() y MPI_Gatherv es compleja. Por otra parte, las primitivas de send y receive permiten a los desarrolladores implementar los tipos de mapeo tradicionales, como se hizo en la Ejemplo 46 (hybrid_distr_arg) para el mapeo estático por bloque.
MPI ofrece otras funcionalidades avanzadas. Por ejemplo, la subrutina MPI_Init_thread() permite escoger si los hilos secundarios dentro de un proceso pueden o no invocar subrutinas de MPI, y en caso afirmativo si éstas se ejecutan con exclusión mutua o no.
MPI ofrece su propio manejo de entrada y salida optimizado para el paralelismo. Por ejemplo, la familia de subrutinas MPI_File_ están diseñadas para que todos los procesos de un equipo puedan abrir o modificar el mismo archivo de forma paralela, en especial si el hardware facilita el acceso paralelo. Esto se contrapone a las primitivas de entrada y salida de los sistemas operativos, que están ideadas para que sólo un proceso acceda un archivo a la vez.
7. Distribución heterogénea: aceleración gráfica
La aceleración por hardware es el uso de la electrónica para optimizar tareas específicas. Por ejemplo, disminuir la cantidad de tiempo de ejecución, disminuir el consumo de energía, o incrementar el tiempo de respuesta, entre otras optimizaciones. Este hardware se conoce como de propósito específico, pues está diseñado para trabajar sólo el contexto para el que fue diseñado. En el extremo opuesto se encuentran las CPUs que son de propósito general y pueden ser programadas para una cantidad arbitraria de contextos. En un punto medio se encuentra hardware como los aceleradores gráficos y los field-programmable gate arrays (FPGA).
Los aceleradores gráficos o GPUs (Graphics Processing Units) sugieron a finales de los 1990 para mejorar la calidad y velocidad de despliegue de imágenes en video juegos, animaciones, y aplicaciones afines. Se caracterizan por un uso masivo del paralelismo conocido como many cores. Este hardware también sirve para solventar problemas científicos y de otros contextos que requieren más paralelismo que el disponible en un procesador de uso general. Sin embargo, a nivel de software, inicialmente la programación de GPUs fue a través de ambientes de programación exclusivos para contextos gráficos, como OpenGL y DirectX, lo que motivó a iniciativas de crear ambientes de programación general usando los aceleradores gráficos, como OpenCL y CUDA.
El Open Computing Language (OpenCL) es un ambiente de programación basado en C y creado hacia el 2009 por un consorcio de compañías de hardware con el ambicioso objetivo de correr en una variedad de plataformas heterogéneas, entre las que se incluyen CPUs, GPUs, FPGAs, digital signal processors (DSP), y otros dispositivos de aceleración por hardware. En el extremo opuesto se encuentra la Compute Unified Device Architecture (CUDA), una extensión para los lenguajes C/C++ y Fortran, creada hacia el 2007 por Nvidia exclusivamente para programación de aceleradores gráficos y sólo los producidos por esta compañía. Esta limitación de CUDA es quizá la explicación de su éxito, dado que está en armonía con un principio de la optimización, de que las soluciones que logran más eficiencia tienden a ser más dependientes del contexto.
Máquina vs dispositivo.
Cree una carpeta ejemplos/gpu en su repositorio personal.
7.1. Transmisión de calor
Descargue los siguientes archivos a una carpeta ejemplos/gpu/heat_perf. Agregue la hoja de cálculo a control de versiones, pero no los casos de prueba (archivos .bin). Llene las celdas en blanco de la hoja de cálculo con las duraciones de ejecución de las actividades en esta sección. Actualice la gráfica para incluir los incrementos de velocidad en un eje secundario.
Descargue los archivos de la solución serial a una carpeta ejemplos/gpu/heat_serial. Agréguelos a control de versiones. Compile la solución. Realice las cuatro ejecuciones de la columna serial de la hoja de cálculo que descargó en Ejemplo 55, y anote la cantidad de generaciones y sus duraciones. Un ejemplo de ejecución podría ser:
./heat_serial ../heat_perf/test001.bin 0.1-
Sugerencia 1: realice las ejecuciones en terminales distintas simultáneamente. Es decir, no espere a que la anterior finalice para realizar la siguiente.
-
Sugerencia 2: compare las ejecuciones de su ejecutable generado con GCC y PGI.
Copie la solución de Ejemplo 56 a la carpeta heat_openmp. Modifique la solución para aprovechar los CPU disponibles en la máquina donde se ejecuta la simulación. Use OpenMP como tecnología para paralelizar la simulación.
Ejecute la solución resultante con los dos casos de prueba de Ejemplo 55 y anote las duraciones en la hoja de cálculo. Verifique que la cantidad de generaciones sea la misma que la versión serial.
Copie la solución de Ejemplo 56 a la carpeta heat_openacc_cpu. Modifique la solución para paralelizar la simulación con OpenACC. Adapte el Makefile-pgi para generar un ejecutale unificado (unified binary) que incluya código para CPU y GPU. Revise cuidadosamente la salida del compilador. Realice dos tipos de ejecuciones:
-
Ejecute la solución resultante en CPU con los dos casos de prueba de Ejemplo 55 y anote las duraciones en la hoja de cálculo. Verifique que la cantidad de generaciones sea la misma que la versión serial. Compare las duraciones con OpenMP.
-
Ejecute la solución resultante en GPU con los dos casos de prueba de Ejemplo 55 y anote las duraciones en la hoja de cálculo. Verifique que la cantidad de generaciones sea la misma que la versión serial.
La siguiente podría ser una interacción:
$ make
pgcc -c -g -acc -ta=multicore,tesla -Minfo=accel heat_openacc.c -o heat_openacc.o
pgcc. -g -acc -ta=multicore,tesla -Minfo=accel heat_openacc.o -o heat_openacc
$ ACC_DEVICE_TYPE=host ./heat_openacc ../heat_perf/test001.bin 0.1
...
$ export ACC_DEVICE_TYPE=nvidia
$ ./heat_openacc ../heat_perf/test001.bin 0.1
