Clase 4: Intro Programación en

paralelo
IE0521: 1 Estructuras de computadoras II
Universidad de Costa Rica
Ing. Gerardo Castro
II semestre 2021
Agenda
• Programación en paralelo
• Clasificación de Flynn
• Anatomía de computadoras en paralelo
• Programación en paralelo
• Procesos e hilos.
• Modelo de programación de memoria compartida.
• Pthreads
• OS Scheduling
• Ejemplo contador compartido
• Sincronización
• OpenMP
• Modelo de programación: Message Passing.
• Modelo de programación de datos paralelos.
• Proceso de paralelización
• Descomposición
• Ley de Amdahl
• Asignación
• Orquestación
• Mapeo
 Programación en paralelo
• La demanda en aplicaciones para mejorar el rendimiento genera avances
en el hardware que a su vez habilitan nuevas aplicaciones.
• Demanda en aplicaciones:
• Comerciales (bases de datos, procesamiento de transacciones en línea, minería
de datos, data warehouses)
• Científicas (genoma humano, circulación oceánica, modelado de fluidos)
• Ingeniería (automotriz, aeronáutica, visualización, procesamiento de imágenes)

Fuente imagen: https://computing.llnl.gov/tutorials/parallel_comp

 Programación en paralelo
• La densidad de chip continúa
creciendo ~2X cada 2 años (Ley de
Moore).
• La potencia y la frecuencia de
reloj no se están incrementando.
• El paralelismo a nivel de
instrucción aumenta lentamente.
• Existe poco paralelismo a nivel de
instrucción por encontrarse.
• La industria cambió su curso en
2005 cuando Intel anunció
arquitecturas multiprocesador,
siguiendo el liderazgo del
procesador Power 4 de IBM y el
procesador Niagara de Sun
Microsystems. (Asanovic, 2006)
• El paralelismo se debe exponer al
software y el programador no
podrá continuar pensando en
términos un modelo de
programación serial.
Clasificación de Flynn

• En 1966, Flynn propuso una

clasificación para un a computadora
paralela.
• La propuesta se basa en como la
instrucciones operan los datos.
• SISD  corresponda a la forma más
simple. Ejemplo (PC antiguas con
un solo procesador).
• SIMD  por ejemplo un
procesador de operaciones
vectoriales (Ej.: GPU, AVX Intel). Fuente imagen: https://www.cac.cornell.edu/Stampede/Parallel/tax.aspx

• MISD  por ejemplo un conjunto

de filtros digitales operando en
paralelo un flujo de datos.
• MIMD  corresponde a una
máquina con un conjunto de
procesadores convencionales.
Fuente imagen: https://computing.llnl.gov/tutorials/parallel_comp
Clasificación de Flynn

Fuente imágenes: https://computing.llnl.gov/tutorials/parallel_comp

 Anatomía de computadoras en paralelo
• Una computadora en paralelo es una colección de elementos de
procesamiento que cooperan para resolver problemas grandes rápido.
• Elementos de hardware de una computadora en paralelo:
• Múltiples procesadores.
• Múltiples memorias.
• Red de interconexión.
• Elementos de software de una computadora en paralelo:
• Sistema operativo en paralelo.
• Estructuras de programación para expresar concurrencia.
• Aplicaciones con algoritmos paralelos.
 Anatomía de computadoras en paralelo
• Nodo:
• Un nodo se considera como un procesador con una jerarquía de memoria
privada y una interfaz de interconexión.
• Un conjunto de nodos se conectan a través de una red para construir una
computadora en paralelo.
• Los nodos pueden existir en un mismo chip o en múltiples chips (múltiples
sockets).

P0 P1 P2 P3

Red de Interconexion

P4 P5 P6 P7
Ejemplo

Fuente imagen: https://computing.llnl.gov/tutorials/parallel_comp

Clasificación Estructural

• Arquitecturas de procesamiento:
• homogéneas (simétricas): múltiples instancias del mismo procesador o
recurso (por ejemplo: múltiples CPUs).
• heterogéneas (asimétricas): instancias diferentes de procesadores o recursos
(CPU big, CPU little, GPU, DSP, AI, etc).

Fuente imagen: http://hpic.korea.ac.kr/research/heterogeneous-computing/heterogeneous-multicore-processor/

Clasificación Estructural

• Arquitecturas de memoria:
• UMA (Uniform Memory Access)
• NUMA (Non Uniform Memory Access)
• ccNUMA (cache coherent NUMA)

Fuente imagen: https://computing.llnl.gov/tutorials/parallel_comp

 Procesos
• Crear un proceso es costoso:
• El OS de asignar recursos.
• Se debe asignar un espacio de memoria (de código y datos)
• Se deben crear estructuras como: la tabla de paginación, PC, registros, pila, etc.
• La comunicación entre procesos es costosa (a través del sistema operativo).
• La mayoría de los procesos comparten estas estructuras y surge el
concepto de hilo (“thread”) como la estructura mínima de control (PC, SP,
registros.
• Entonces la mayoría de OS soporta dos entidades:
• Proceso: que define el espacio de memoria y los atributos generales.
• Hilo: que define un flujo de ejecución secuencial dentro de un proceso.
• Un proceso puede tener varios hilos. Los hilos solamente existen dentro
de un proceso.
• Un proceso es un contenedor de hilos. Un hilo es la unidad de
“scheduling” para el OS.
Hilos (Threads)

• Los hilos tienen su propia pila y registros. El segmento de código y datos

pertenece al proceso.
• La creación de hilos es menos costosa que la de un proceso por lo que es
menos costoso el cambio de contexto entre hilos (task switching).
• Permiten soportar mas fácil aplicaciones multi-hilo (multi-threaded).
• La concurrencia es útil para:
• Mejorar la estructura del programa.
• Manejo de eventos concurrentes.
• Creación de programas paralelos.
• Compartir recursos.
• Utilización de una arquitectura multiprocesador.
• Concurrencia vs Paralelismo:
• Concurrencia: es cuando dos threads empiezan, corren y terminan en periodos de
tiempo traslapados. No significa que ambos corrieron en el mismo instante.
• Paralelismo: es cuando los threads corren al mismo tiempo como por ejemplo en
procesador de múltiples núcleos.
Procesos e Hilos
Caso de paralelismo

• Considere el siguiente fragmento de código en un CPU de dos núcleos.

for(k = 0; k < n; k++)
a[k] = b[k] * c[k];
• Se podría pensar los dos núcleos de la siguiente forma:
• Núcleo 1:
for(k = 0; k < n/2; k++)
a[k] = b[k] * c[k];
• Núcleo 2:
for(k = n/2; k < n; k++)
a[k] = b[k] * c[k];
• Pero surgen las siguientes preguntas:
• ¿Cómo se crean los flujos de ejecución?
• ¿Qué orden existe entre operaciones?
• ¿Cómo se sincronizan?
• ¿Los datos son compartidos o privados?
• ¿Cuál es costo?
 Programas Paralelos
• Para construir programas paralelos que se ejecutan en un
multiprocesador se requiere:
• Se requiere un API (interfaz de programación de aplicaciones) que permita crear
y manipular procesos/hilos.
• Libreria.: pthreads, openMP, Cuda, MPI, openCL, ...
• Lenguaje: Go, SystemC. Clojure, Rust,…
• Un modelo de programación que permita una abstraer la arquitectura de
máquina:
• Memoria Compartida.
• Intercambio de mensajes (Message Passing).
• Datos Paralelos.
• Donde cada proceso está mapeado a un espacio de memoria.
• Darle a cada proceso su dirección inicial y sus parámetros iniciales.
• El sistema operativo (OS) programará (“scheduling”) estos procesos en paralelo.
 Modelo programación: Memoria Compartida
• Un modelo de programación esta conformado por los lenguajes y la
librerías que crean una visión abstracta de la máquina.
• En un modelo de programación de memoria compartida se tiene que:
• Los programas son una colección de “threads”.
• Cada thread tiene un conjunto de variables privadas y compartidas.
• La comunicación entre se realiza de forma implícita a través de las variables
compartidas.
• Los threads se coordinan a través de la sincronización de las variables
compartidas

Fuente imagen:
http://www.cs.berkeley.edu/~kubitron/talks/printable/BootCampHardware_081610.pdf
Creación de procesos: Fork

• Fork es una llamada al sistema en Unix que permite la creación de

procesos.
• Primero se hace una copia del proceso padre para crear un proceso
hijo que inicia otro flujo de ejecución.
Ejemplo Fork
Pthreads

• POSIX (Portable Operating System Interface for Unix) es una interfaz

para utilidades del sistema operativo.
• Pthreads (POSIX threads):
• API que permita crear y manipular hilos (threads).
• Bastante uniforme en Unix OS. Estándar IEEE 1003.1c
• Tiene soporte para:
• Crear paralelismo.
• Sincronización.
• Variables creadas fuera del “main” son compartidas.
Ejemplo básico Pthreads.
OS “scheduling”

• Cual es resultado del siguiente programa paralelo:

• Núcleo 0: cont++, while cont < 10
• Núcleo 1: cont--, while cont > -10

• Si la variable cont se inicializa en 0.

• Cual thread gana?
• Es posible garantizar un ganador?
Ejemplo OS Scheduling.
 OS scheduling
• Normalmente se puede asumir:
• A “scheduler” provee siempre todos los hilos oportunidades para que corran.
• No necesariamente de forma equitativa.
• Se debe pensar en como el “scheduler” puede afectar el algoritmo.
• El programador puede dar pistas o afinidad en algunos caso. Ej: crear N threads
para N procesadores).

http://www.cs.berkeley.edu/~kubitron/talks/printable/BootCampHardware_081610.pdf
Ejemplo: contador compartido

• Cual es resultado del siguiente programa paralelo:

• Núcleo 0: cont++, 10000 veces
• Núcleo 1: cont++, 10000 veces
• Núcleo 2: cont++, 10000 veces
• Núcleo 3: cont++, 10000 veces
 Problema: contador compartido
• La instrucción contador se implementa a nivel de lenguaje ensamblador (x86):
mov eax, [cont_dir];
add eax, 1;
mov [cont_dir], eax;
• La ejecución del programa puede ocurrir así:
P0 P1
mov eax, [cont_dir];
mov eax, [cont_dir];
add eax, 1;
mov [cont_dir], eax;
add eax, 1;
mov [cont_dir], eax;

• Al final de esta ejecución cont vale 1 en vez de 2. P0 sobrescribe el valor de cont.

• cont++ NO se implementa como una operación atómica.
• Una operación atómica es aquella que realiza una modificación a memoria sin
interrupciones.
Sincronización

• En un programa paralelo, los hilos eventualmente tratarán

de acceder datos compartidos.
• Para resolver esto necesario convertir estas secciones de
código en secciones críticas donde solamente un hilo se
encuentra ellas en un tiempo dado.
• Esta propiedad se conoce como exclusión mutua. Y se
implementa a través de bloqueos (“locks”).
• El hilo adquiere acceso a la sección crítica a través de un
bloqueo y cuando finaliza su ejecución desbloquea la
sección crítica.
Sincronización

• Un algoritmo de bloqueo satisface 3 propiedades:

• Exclusión mutua (safety)  secciones críticas entre
threads no se traslapan.
• Starvation freedom (liveness)  todo thread que intenta
realizar un bloqueo, logrará conseguirlo eventualmente.
• Deadlock freedom (bounded waiting)  si un thread
realiza un bloqueo, luego otro siempre logrará hacerlo.
• Igualdad (Fairness)  threads tienen las mismas
oportunidades de bloquear una sección critica.
 Operaciones Atómicas
• Una operación atómica es aquella que realiza una modificación a memoria sin interrupciones.
Es decir una operación indivisible.
• La arquitectura debe proveer este tipo de instrucciones. Por ejemplo la arquitectura de Intel
tiene las instrucciones xchg, cmpxchg que son comúnmente usadas para implementar bloqueos
(lock).
• xchg: escribe el valor del registro EAX en destino y retorna en EAX el valor que tenia el destino (Escritura
y Lectura).
• cmpxchg: compara el valor del destino con EAX, si son iguales, escribe el valor del registro ECX en
destino y retorna en ECX el valor que tenia el destino (Comparación, Escritura y Lectura).

int atomic_exchange(int *dest, int value) {

mov eax, value;
mov ecx, dest;
/*lock*/ xchg eax, dword ptr [ecx]; }

int atomic_compare_and_exchange(int *dest, int exchange, int

comperand) {
mov edx, dest;
mov ecx, exchange;
mov eax, comperand;
/*lock*/ cmpxchg dword ptr [edx], ecx }
 Implementación de bloqueos
• Se crea una variable que se modifica a través de
operaciones atómicas.
• Para bloquear, el hilo debe leer un 0 (libre) y se guarda
un 1 para generar el bloqueo.
• Si está bloqueado, se lee 1 y se guarda un 1. No hay
cambio y se continúa el lazo hasta que sea cero (spin-
lock or busy-wait).
• Esta implementación:
• consume ciclos mientras se espera.
• Algunos threads pueden tomar ventaja sobre otros.
• es costosa ya que cada intento de bloqueo puede atravesar
toda la red de procesadores.
 Implementación de bloqueos
• En otra implementación se puede interrumpir el hilo
para ejecutar otro mientras se libera la variable
(blocking). Esta implementación:
• Tiene mayor latencia ya que el thread se debe despertar.
• Requiere un mecanismo de notificación.
• Se puede implementar de forma hibrida.
• Intentar el bloqueo por cierto tiempo y luego interrumpir.
Ejemplo: Pthreads exclusión
mutua
Problemas de la exclusión mutua

• Inversión de prioridad: ocurre cuando un hilo de baja

prioridad realiza un bloqueo cuando un hilo de mayor
prioridad lo necesita.
• Convoying: ocurre cuando un hilo realiza un bloqueo y no
progresa (interrupción) haciendo que el resto de los hilos no
progresen.
• Deadlock: ocurre cuando un hilo realiza un bloque sobre un
mismo objeto en diferente orden.
openMP Intro

• Es un API multiplataforma para la programación

paralela en memoria compartida en C++ y fortran.
• OpenMP define una API escalable, portable con una
simple y flexible interface para el desarrollo de
aplicaciones paralelas.
• Tiene pragmas (directivas de compilador) para:
• Crear paralelismo.
• Sincronización.
• Paralelización de lazos.
• Diferentes tipos de variables compartidas y privadas.
• Diferentes tipos de OS scheduling de los lazos.
• Los threads se mapean a los procesadores.
 OpenMP
exclusión mutua, parallel for & OS scheduling
Semáforos & barreras

• Semáforos: es la generalización de la exclusión mutua. Un

semáforo tiene cierta capacidad C (definida durante su
inicialización) y permite que C hilos ingresen a la región
crítica.
• Barreras: es una forma de sincronización global donde todos
los hilos llegan un mismo punto de bloqueo y se avanza
hasta que todos los hilos llegan a ese punto. Se crea una
variable que se inicializa con el número de hilos esperados.
 Coherencia de cache y modelo de
consistencia de memoria
• Los procesadores pueden observar valores distintos de un dato luego de
una escritura.
• Solución: coherencia de cache.
• Los procesadores pueden observar las lecturas y escrituras a diferentes
posiciones de memoria en diferente orden
• Solución: modelo de consistencia de memoria.

http://www.cs.berkeley.edu/~kubitron/talks/printable/BootCampHardware_081610.pdf
 Modelo de programación: Message Passing
• El programa consiste en una colecciones de programas donde cada hilo
tiene su propio espacio de memoria. No hay datos compartidos.
• Los hilos se comunican en forma explicita a través de mensajes de
enviado y recibido.
• La sincronización es implícita con cada evento de comunicación.
• MPI (Message Passing interface) es el software más usado.

Fuente imagen:
http://www.cs.berkeley.edu/~kubitron/talks/printable/BootCampHardware_081610.pdf
Modelo de Programación: Datos paralelos.

• El espacio de memoria es
global.
• La mayoría el trabajo
concurrente se enfoca en
operaciones sobre un conjunto
de datos.
• Las operaciones se realizan
sobre la misma estructura de
datos.
• Cada tarea se ejecuta en
particiones diferentes con la
misma operación. Fuente imagen: https://computing.llnl.gov/tutorials/parallel_comp
Proceso de Paralelización

• El proceso de paralelización implica:

• Identificar el trabajo que se puede paralelizar.
• Determinar como distribuir el trabajo y datos entre los
procesadores.
• Manejar acceso de datos, comunicación y sincronización.
• El objetivo una aceleración considerable con
respecto al mejor algoritmo secuencial que resuelve
el problema.
• Este proceso de puede realizar a nivel de
programador o nivel de las capas de software.
Proceso de Paralelización

•Pasos para paralelizar un programa:

•Descomposición de problema en tareas.
•Asignación las tareas a procesos/hilos.
•Orquestación (manejar el acceso de datos,
comunicación y sincronización).
•Mapeo de procesos/hilos a procesadores.
Proceso de Paralelización

• Descomposición: el objetivo es exponer suficiente

concurrencia para mantener los procesos ocupados
todo el tiempo.
• Un poca concurrencia limita la aceleración que se
puede lograr con la paralelización.
• Para conocer el impacto de la concurrencia
disponible se utiliza la ley de Amdahl.
 Ley de Amdahl
• La ley de Amdahl dice que la máxima aceleración que se puede obtener
de paralelizar un trabajo se ve limitada por cuanto trabajo se tiene que
realizar en forma secuencial.
• La ley de Amdahl dice que la aceleración es el radio entre el tiempo
secuencial y el tiempo paralelo normalizado:

• Donde n es el número de procesadores.

• Esta ley provee la cota máxima (n= ) y no considera el costo de
paralelizar el trabajo (creación de hilos, sincronización, arquitectura de
la máquina, ancho de banda, latencia, etc.).

Fuente imagen:
https://www.cac.cornell.edu/Stampede/Parallel/tax.aspx
Ley de Amdahl

Fuente imagen: https://computing.llnl.gov/tutorials/parallel_comp

Proceso de Paralelización

• Existen dos formas

básicas de realizar la
descomposición o
partición:
• Por dominio: cada tarea
concurrente trabaja con
un sección de los datos.
• Por función: cada tarea
concurrente realiza una
operación del trabajo.

Fuente imágenes: https://computing.llnl.gov/tutorials/parallel_comp

Proceso de Paralelización

• Asignación: especifica el mecanismo de como las

tareas se van a distribuir entre los procesadores.
• El objetivo es balancear la carga de trabajo entre
procesadores, reducir la comunicación y reducir la
sobrecarga de manejar las asignaciones.
• Si las asignaciones están definidas al principio del
programa es llamada estática. Si la asignación se
determina durante a ejecución es llamada
dinámica.
Proceso de Paralelización

• Orquestación: en este paso la arquitectura, el modelo

de programación y el lenguaje de programación juegan
un papel muy importante.
• En la orquestación utiliza los mecanismos de
disponibles para la comunicación, acceso de datos y la
sincronización.
• Incluye como se van a organizar las estructuras de
datos, como se hará el scheduling para explotar
localidad.
• El objetivo es reducir el costo de comunicación y
sincronización, preservar la localidad de los datos y
scheduling de las tareas.
Proceso de Paralelización

• Mapeo: el programa puede tomar control de del

mapeo de los procesos a los procesadores para la
ejecución. Si no es así, el sistema operativo se hace
cargo.
• Se puede mapear un subconjunto de procesadores para
ejecutar el programa.
• Se puede ligar procesos a procesadores para evitar
migraciones durante la ejecución.
• Se puede controlar los procesadores que ejecutarán una
proceso en específico para mantener localidad.
Paralelización Automática

• Algunos compiladores pueden insertar OpenMP para optimizar el

programa automáticamente.
• El compilador de Intel soporta paralelización automática.
• Ejemplo: Lazo for.
Bibliografía

• https://computing.llnl.gov/tutorials/parallel_comp
• http://www.cs.berkeley.edu/~kubitron/talks/printable/BootCampHar
dware_081610.pdf
• https://www.cac.cornell.edu/Stampede/Parallel/tax.aspx
• D. Culler, J. Singh y A. Gupta. “Parallel Computer Architecture: A
Hardware/Software Approach.” Morgan Kaufmann, Primera Edición,
1998.
• M. Herlihy, N. Shavit. “The Art of Multiprocessor Programming” .
Morgan Kaufmann, Segunda Edición, 2008.