Introducción

La computación paralela es el uso de múltiples recursos computacionales para resolver

un problema. Se distingue de la computación secuencial en que varias operaciones
pueden ocurrir simultáneamente.

El paralelismo clásico, o puesto de otra manera, el clásico uso del paralelismo, es el de

diseño de programas eficientes en el ámbito científico. La simulación de problemas
científicos es un área de gran importancia, los cuales requieren de una gran capacidad
de procesamiento y de espacio de memoria, debido a las complejas operaciones que se
deben realizar.

Otro uso clásico es el de las gráficas generadas por computadora. La generación de

fotogramas requiere de una gran cantidad de cálculos matemáticos. Esto supone una
tarea muy compleja para un solo procesador, luego es necesario que haya algún tipo de
paralelismo, para distribuir la tarea para que esta sea realizada eficiente y eficazmente.
Filosofía
¿Que es computación paralela?
En el sentido más simple, la computación paralela es el uso simultáneo de múltiples
recursos computacionales para resolver un problema computacional:

 Un problema se divide en partes discretas que se pueden resolver simultáneamente

 Cada parte se descompone en una serie de instrucciones

 Las instrucciones de cada parte se ejecutan simultáneamente en diferentes

procesadores

 Se emplea un mecanismo global de control/coordinación

Historia
 El interés por la computación paralela se remonta a finales de los años 50. Este interés
se vio expresado en forma de supercomputadores, que aparecieron en los años 60 y 70. Estos
computadores tenían procesadores de memoria compartida, con múltiples procesadores
trabajando lado a lado con datos compartidos.
 A mediados de los 80, un nuevo tipo de computador paralelo fue creado cuando el
proyecto “Concurrent Computation” de Caltech construyó un supercomputador para
aplicaciones científicas. El sistema mostró que se podría lograr un rendimiento extremo
usando microprocesadores regulares, disponibles en el mercado.
 Empezando a los finales de los 80, los clusters surgieron para competir y con los MPP.
Un cluster es un tipo de computador paralelo, construido usando múltiples computadores “off-
the-shelf”, conectados usando una red “off-the-shelf”. Hoy en día, los clusters son la
arquitectura dominante en los datacenters.
 Para los MPP y clusters surgió el estándar MPI a mediados de los 90, que convergió de
otras API. Para los multiprocesadores con memoria compartida, un proceso de convergencia
similar se observó a finales de los 90, con el surgimiento de pthreads y OpenMP.
 En la actualidad, la computación paralela se ha vuelto mainstream prácticamente, con
la llegada de los procesadores de varios núcleos casi por defecto en la mayoría de dispositivos
computacionales.
 El software ha sido una parte activa en la evolución de la programación paralela. Los
programas paralelos son más difíciles de escribir que los programas secuenciales, ya que se
requiere que haya una comunicación y sincronización entre las tareas que se han paralelizado.

Ventajas
 Resuelve problemas que no se podrían realizar en una sola CPU
 Resuelve problemas que no se pueden resolver en un tiempo razonable
 Permite ejecutar problemas de un orden y complejidad mayor
 Permite ejecutar código de manera más rápida (aceleración)
 Permite ejecutar en general más problemas
 Obtención de resultados en menos tiempo
 Permite la ejecución de varias instrucciones en simultáneo
 Permite dividir una tarea en partes independientes

Desventajas
 Mayor consumo de energía
 Mayor dificultad a la hora de escribir programas
 Dificultad para lograr una buena sincronización y comunicación entre las tareas
 Retardos ocasionados por comunicación ente tareas
 Número de componentes usados es directamente proporcional a los fallos potenciales
 Condiciones de carrera
 Múltiples procesos se encuentran en condición de carrera si el resultado de los
mismos depende del orden de su llegada
 Si los procesos que están en condición de carrera no son correctamente
sincronizados, puede producirse una corrupción de datos

Conceptos Clave
 Conceptos acerca de Tareas
Tarea:

Un problema complejo se subdivide en una cantidad discreta de tareas que representan

trabajo computacional. Una tarea esta compuesta de un conjunto de instrucciones que seran
ejecutadas por un procesador.

Granularidad:

Se refiere al tamaño de cada tarea y a la independiencia de las demás tareas, se dividen en dos
categorías.
 Gruesa: Cantidad relativamente grande de trabajo, alta independencia entre tareas y
poca necesidad de sincronización.
 Fina: Cantidades pequeñas de trabajo, poca independencia entre tareas, y una alta
demanda de sincronización.

Scheduling:

Scheduling es el proceso en el que las tareas son asignadas a los procesos o hilos, y se les da
un orden de ejecución. Este puede ser especificado en el código, en tiempo de compilación o
dinámicamente en tiempo de ejecución. El proceso de scheduling debe tener en cuenta la
dependencia entre tareas, ya que, aunque muchas pueden ser independientes, otras pueden
requerir los datos producidos por otras tareas.

Conceptos acerca de Hilos

Hilo:
Un proceso pesado padre puede convertirse en varios procesos livianos hijos, ejecutados de
manera concurrente. Cada uno de estos procesos livianos se conoce como hilo. Estos se
comunican entre ellos a través de la memoria global.

Sincronizacion:

Los programas en paralelo necesitan la coordinación de procesos e hilos, para que haya una
ejecución correcta. Los métodos de coordinación y sincronización en la programación paralela
están fuertemente asociados a la manera en que los procesos o hilos intercambian
información, y esto depende de cómo está organizada la memoria en el hardware.

Mapping:

Mapping en el proceso de asignación de procesos e hilos a unidades de procesamiento,

procesadores o núcleos. Usualmente el mapping se hace por el sistema en tiempo de
ejecución, aunque en ocasiones puede ser influenciado por el programador.
 Otros conceptos
Balanceo de carga

Se refiere a la práctica de distribuir cantidades equitativas de trabajo entre las tareas, de

modo que todas las tareas se mantengan ocupadas todo el tiempo.
 Speedup:

Es un proceso para aumentar el rendimiento entre dos sistemas procesando el mismo

problema. Es la mejora en la velocidad de ejecución de una tarea ejecutada en dos
arquitecturas similares con diferentes recursos.

Overhead

Es la cantidad de tiempo requerido para coordinar tareas paralelas, en lugar de hacer un

trabajo útil. Incluye factores como:

 Tiempo de inicio de la tarea

 Sincronización
 Comunicaciones de datos
 Sobrecarga de software impuesta por lenguajes paralelos, bibliotecas, sistema
operativo, etc.
 Tiempo de terminación de la tarea

Sección crítica

Un proceso tiene un segmento de código llamado sección crítica cuando este puede modificar
o leer información de memoria compartida con otros procesos. Dos procesos no pueden
ejecutar su seccion critica al mismo tiempo.
 Concurrencia vs Paralelismo
Concurrencia
Capacidad de operar actividades al mismo tiempo. Es decir se pueden tener varios
procesos corriendo cada uno en un procesador o puede haber varios proceso que corran
solo en un procesador
Paralelismo
Son muchas actividades teniendo lugar al mismo tiempo, “la cualidad o el estado de ser
paralelo”. El hecho de ser paralelo implica que solo se pueden tener varios procesos
corriendo cada uno en un procesador.

Arquitectura de Von Neumann

Se caracterizaba por guardar las instrucciones de los procesos y los datos en una
memoria electronica, a diferencia de como se modelaban los computadores de la epoca
a través de una conexion de cables

Componentes principales

 Memoria
 Unidad de control
 Unidad Aritmetica Logica
 Entradas/Salidas
Memoria de acceso aleatorio

En la memoria de acceso aleatorio se almacenaban los datos y los programas que

estaban siendo ejecutados
 Las instrucciones del programa son datos codificados que le dicen al computador que
es lo que tiene que hacer
 Los datos son simplemente informacion que sera usada por el programa

Taxonomia de Flynn
Single Instruction, Single Data (SISD)
hay un elemento de procesamiento, que tiene acceso a un único programa y a un
almacenamiento de datos. En cada paso, el elemento de procesamiento carga una instrucción
y la información correspondiente y ejecuta esta instrucción. El resultado es guardado de vuelta
en el almacenamiento de datos. Luego SISD es el computador secuencial convencional, de
acuerdo al modelo de von Neumann.
Multiple Instruction, Single Data (MISD)
hay múltiples elementos de procesamiento, en el que cada cual tiene memoria privada del
programa, pero se tiene acceso común a una memoria global de información. En cada paso,
cada elemento de procesamiento de obtiene la misma información de la memoria y carga una
instrucción de la memoria privada del programa. Luego, las instrucciones posiblemente
diferentes de cada unidad, son ejecutadas en paralelo, usando la información (idéntica)
recibida anteriormente. Este modelo es muy restrictivo y no se ha usado en ningún
computador de tipo comercial.

Single Instruction, Multiple Data (SIMD):

Hay múltiples elementos de procesamiento, en el que cada cual tiene acceso privado a la
memoria de información (compartida o distribuida). Sin embargo, hay una sola memoria de
programa, desde la cual una unidad de procesamiento especial obtiene y despacha
instrucciones. En cada paso, cada unidad de procesamiento obtiene la misma instrucción y
carga desde su memoria privada un elemento de información y ejecuta esta instrucción en
dicho elemento. Entonces, la instrucción es síncronamente aplicada en paralelo por todos los
elementos de proceso a diferentes elementos de información. Para aplicaciones con un grado
significante de paralelismo de información, este acercamiento puede ser muy eficiente.
Ejemplos pueden ser aplicaciones multimedia y algoritmos de gráficos de computadora.
Multiple Instruction, Multiple Data (MIMD):
hay múltiples unidades de procesamiento, en la cual cada una tiene tanto instrucciones como
información separada. Cada elemento ejecuta una instrucción distinta en un elemento de
información distinto. Los elementos de proceso trabajan asíncronamente. Los clusters son
ejemplo son ejemplos del modelo MIMD.

Tipos de paralelismo
Paralelismo a nivel de bit:
Se habla de paralelismo al nivel de bit, cuando se aumenta el tamaño de la palabra
del procesador (tamaño de la cadena de bits a procesar). Este aumento reduce el
número de instrucciones que tiene que ejecutar el procesador en variables cuyos
tamaños sean mayores a la longitud de la cadena.
Ejemplo: En un procesador de 8-bits sumar dos números de 16bits tomaría dos
instrucciones. En un procesador de 16-bits esa operación requiere solo una instrucción.

 
Nota: este método está “estancado” desde el establecimiento de las arquitecturas de 32 y 64
bits.

Paralelismo a nivel de instrucción

Este tipo de paralelismo consiste en cambiar el orden de las intrucciones de un
programa y juntarlas en grupos para posteriormente ser ejecutados en paralelo sin
alterar el resultado final del programa.
Pipelining

El pipelining proviene de la idea de que en una tubería no es necesario esperar a que

todo el agua dentro salga, para que pueda entrar más. Los procesadores modernos tienen
un 'pipeline' que separa las instrucciones en varias etapas, donde cada etapa
corresponde a una acción diferente que necesita la salida de la anterior.
Ejemplo: Un pipeline de 5 etapas: fetch (buscar la instrucción), decode (decodificarla),
execute (ejecutarla), write (escribir en memoria el resultado de la operación).

En el gráfico anterior se observa el procesamiento de dos instrucciones sin pipeline,

tomando un tiempo de 8 ciclos, y con pipeline reduciendo este tiempo a solo 5 ciclos.
Paralelismo a nivel de datos
Cada procesador realiza la misma tarea sobre un subconjunto independiente de datos.
Ej: Dos granjeros se dividen el área de césped a podar.

El caso clásico de paralelismo de datos, es el cálculo de pi por partes usando el método

de monte carlo:

Ejemplo hecho en python

Paralelismo a nivel de tareas

Cada hilo realiza una tarea distinta e independiente de las demás.
Ej: Un granjero poda el césped, el otro cosecha.
Patrones de control paralelo
Los patrones se han establecido como buenas practicas a la hora de realizar ingeniería
de software.

Los patrones de control en el caso de la programación paralela son maneras de combinar

la distribución de los procesos y el acceso a los datos para la solucion de un problema.

Fork-Join
Fork-Join es un patrón que nos permite partir el flujo de un programa en múltiples flujos
paralelos para reunirlos luego.
Map
Map es un patrón que replica una función sobre todos los elementos de un conjunto de
entrada. La función que está siendo replicada se llama función elemental, dada que la
misma se aplica a una coleccion real de datos.
Stencil
Stencil es un generalización del patron de Map, en el cual una función elemental tiene
acceso no solo a un elemento del conjunto de entrada sino también a un conjunto de
"vecinos"
Como la estructura de datos no es infinita se deben tener en cuenta el manejo de
excepciones para los bordes de la misma.
 Reducción
Una reducción combina cada elemento de una colección en uno solo utilizado una
función asociativa conocida como función combinatoria. Como es asociativa las tareas
se pueden distribuir de muchas maneras y si la función resultara ser también
conmutativa el número de posibilidides aumentaría aún más.
Scan
Scan realiza las reducciones de cada elemento perteneciente a una estructura. En otras
palabras cada elemento de salida es la reduccion de un elemento de entrada. A traves de
una función sucesora se avanza de un estado al otro haciendo folds en el proceso
asociativo.

Arquitecturas de memoria de computación

paralela
Memoria compartida
 Los procesos comparten un espacio de memoria común
 Escriben y leen de manera asíncrona
 No es necesario especificar cómo se comunican los datos entre las tareas
 Se usan semáforos o locks para controlar el acceso a la memoria compartida
Uniform Memory Access (UMA):
 Lo más comúnmente representado hoy por las máquinas Symmetric Multiprocessor
(SMP)
 Procesadores idénticos
 Igual acceso y tiempos de acceso a la memoria
 Si un procesador actualiza una ubicación en memoria compartida, todos los demás
procesadores saben sobre la actualización, esto es llamado coherencia del caché

Non-Uniform Memory Access (NUMA)

 Hecho mediante la vinculación física de dos o más SMP

 Un SMP puede acceder directamente a la memoria de otro SMP
 No todos los procesadores tienen igual tiempo de acceso a toda la memoria
 El acceso a la memoria es más lento
 Si se mantiene la coherencia del caché

Memoria distribuida
 También llamado modelo de paso de mensajes
 requieren una red de comunicación para conectar la memoria entre procesadores
 Las tareas intercambian datos por medio del paso y recepción de mensajes
 Los procesadores tienen su propia memoria local. Las direcciones de memoria en un
procesador no se asignan a otro procesador, por lo que no hay concepto de espacio de
direcciones global en todos los procesadores.
 Debido a que cada procesador tiene su propia memoria local, funciona
independientemente. Los cambios que hace en su memoria local no tienen ningún efecto en la
memoria de otros procesadores. Por lo tanto, el concepto de coherencia de caché no se aplica.
 Cuando un procesador necesita acceso a los datos de otro procesador, suele ser la
tarea del programador definir explícitamente cómo y cuándo se comunican los datos. La
sincronización entre tareas también es responsabilidad del programador.
 Hibrido memoria distribuida-comopartida
 Es la combinación entre memoria compartida y memoria distribuida, con sus ventajas
en común.
 Su principal ventaja es su escalabilidad.
 Su principal desventaja es que la complejidad de programación aumenta.

Hilos
 Un proceso pesado puede convertirse en varios procesos livianos ejecutados de
manera concurrente.
 Se pueden describir como una subrutina dentro del programa principal.
 Se comunican entre ellos a través de la memoria global.
 Datos en paralelo
 También conocido como PGAS (Partitioned Global Address Space)
 Una serie de tareas trabajan de manera colectiva en la misma estructura de datos
 Las tareas realizan la misma operación, pero cada una en su partición pero cada tarea
trabaja en una partición diferente de ésta

Sincronización
 Administrar la secuencia de trabajo y las tareas que lo realizan es una consideración
crítica del diseño para la mayoría de los programas paralelos.
 Puede ser un factor significativo en el desempeño del programa, pues un diseño de
sincronización adecuado reduce el tiempo overhead.
 A menudo requiere "serialización" de segmentos del programa.

Sincronización Mínima:
1. Identificar suficiente concurrencia en la descomposición del problema.
2. Decidir cómo manejarla: distribución estática o dinámica.
3. Determinar el grado de granularidad y cómo explotar la concurrencia.
4. Reducir serialización y costes de sincronización.
1. Identificar suficiente concurrencia

Paralelismo por Tareas:

 Grandes tareas (procedimientos) pueden realizarse en paralelo

 No suele haber muchas tareas, no aumenta con el tamaño del problema
 Dificultad para aplicar balanceo de carga
Paralelismo por Datos:

 Más escalable, proporcional al tamaño del problema

 Es factible aplicar balanceo de carga
2. Manejando concurrencia

Técnicas estáticas:

 Asignación basada en la entrada

 Bajo overhead
 Siempre que sea posible, es preferible
Técnicas dinámicas:

 Adapta el balanceo en tiempo de ejecución

 Aumenta la comunicación y el overhead
 3. Determinación de la granularidad

Grano grueso: pocas oportunidades de balanceo de carga. Grano fino: mayor

overhead, mayor comunicación, más sincronización.
4. Reducir la serialización

Sincronización de eventos:

 Global versus punto a punto

 Sincronización a bajo nivel produce mayor cantidad de sincronizaciones
Exclusión mutua:

 Regiones críticas pequeñas

 Dispersar las regiones críticas en el tiempo
Tipos de sincronización:
Barrier

 Todas las tareas están involucradas

 Cada tarea realiza su trabajo hasta que alcanza la barrera. Después, se detiene o
"bloquea".
 Cuando la última tarea llega a la barrera, todas las tareas se sincronizan.
Lo que sucede a partir de aquí varía. Algunas veces, una sección del código debe ser ejecutada
en serie. En otros casos, las tareas se liberan automáticamente para continuar su trabajo.

Lock / semaphore

 Puede involucrar cualquier número de tareas

 Se utiliza para serializar el acceso a datos globales o a una sección de código. Sólo una
tarea a la vez se puede ejecutar.
 La primera tarea en llegar al lock "lo bloquea". Esta tarea puede acceder de forma
segura (en serie) a los datos protegidos o al código.
 Otras tareas pueden intentar adquirir el lock pero deben esperar hasta que la tarea
que posee el bloqueo lo libere.
 Operaciones de comunicación sincrónica

 Incluye sólo aquellas tareas que ejecutan una operación de comunicación

 Cuando una tarea realiza una operación de comunicación, se requiere alguna forma de
coordinación con las otras tareas que participan en la comunicación.
 Antes de que una tarea pueda realizar una operación de envío, primero debe recibir
un aviso del receptor sobre si está disponible para enviar.
Se utilizan las funciones send y recieve para coordinar las acciones.

Un ejemplo que ilustra esta técnica es el handshake que establece la comunicación

usando el protocolo http.
 Balanceador de carga
Se refiere a la práctica de distribuir cantidades aproximadamente iguales de trabajo
entre las tareas, de modo que todas las tareas se mantengan ocupadas todo el tiempo. Se
puede considerar una minimización del tiempo de inactividad de la tarea.

 Asignar el trabajo que recibe cada tarea equitativamente

 Puede ser un factor significativo en el desempeño del programa
 A menudo requiere "serialización" de segmentos del programa.
Asignación de trabajo dinámico

Ciertas clases de problemas producen desequilibrios de carga incluso si los datos están
distribuidos uniformemente entre las tareas

 Cuando la cantidad de trabajo que realiza cada tarea es variable o no se puede

predecir, puede ser útil usar un planificador - task pool approach. Cuando cada tarea termina
su trabajo, espera en una cola para obtener una nueva pieza de trabajo.
 Puede ser necesario diseñar un algoritmo que detecte y maneje desequilibrios de
carga como ocurren dinámicamente dentro del código.
 Paralelismo automatico vs manual
Paralelismo automatico
 El compilador analiza el codigo fuente e identifica oportunidades de paralelismo
 Los ciclos son los objetivos mas frecuentes para una paralelizacion automatica
 El analisis incluye identificar inhibidores al paralelismo y posiblemente un costo en, si
el paralelismo puede o no mejorar el rendimiento
 un ejemplo de este tipo puede ser OpenMP
Paralelismo manual
 Usando las directivas del compilador el programador explicitamente le dice al
compilador como quiere paralelizar el codigo
 Se puede usar o complementar en algun grado con paralelizacion automatica

Medidas de rendimiento
Tiempo de respuesta
Es el tiempo que tarda en ejecucion el programa A.

MIPS - MFLOPS
MIPS - Millones de operaciones por segundo. MFLOPS - Millones de operaciones de
punto flotante por segundo.
Eficiencia
La eficiencia del programa se mide en el costo de ejecucion.

SpeedUp
El SpeedUp resresenta la ganacia que se obtiene en la version paralela del programa
respecto a la version secuencial del mimo.

Ley de Amdahl
El incremento de velocidad de un programa utilizando múltiples procesadores en
computación paralela está limitada por la fracción secuencial del programa. Sea f el
porcentaje paralelizado del programa expresado en decimal, la ley de Amdahl dice que
llega un punto en el cual sin importar que el numero de procesadores sea muy alto , el
speedup se va a comportar de manera lineal ; esto de acuerdo al porcentaje que este
paralelizado el codigo. El speedup de un programa con un fragmento paralelizado se
calcula con :

Lenguajes de programacion
Aplicaciones
Computación grafica

Ciertas clases de problemas producen desequilibrios de carga incluso si los datos están
distribuidos uniformemente entre las tareas

Aproximación y cálculo de constantes y/o

funciones numéricas.
Worldwide LHC Computing Grid (WLCG) es una colaboración global de centros de
computación. Fue lanzado en 2002 para proporcionar un recurso para almacenar,
distribuir y analizar los 15 petabytes (15 millones de gigabytes) de datos generados cada
año por el Large Hadron Collider (LHC).

Predicción del clima y cambio climático

Uno de los primeros usos exitosos de la computación paralela fue la predicción del
tiempo. La información, como la temperatura, la humedad y las precipitaciones, se ha
recolectado y utilizado para predecir el clima durante más de 500 años. En 1904, el
físico y meteorólogo noruego Vilhelm Bjerknes propuso un modelo de ecuaciones
diferenciales para la predicción meteorológica que incluía siete variables, incluyendo
temperatura, lluvia y humedad.
Análisis de imágenes multiespectro
Las imágenes satelitales consisten en grandes cantidades de datos. Por ejemplo, las
imágenes Landsat 7 consta de siete tablas de datos, donde cada entrada en una tabla
representa una longitud de onda magnética diferente (azul, verde, rojo o infrarrojo
térmico) para un píxel de 30 metros cuadrados de la superficie de la Tierra.

Astronomía
Hay muchas aplicaciones de los supercomputadores a la astronomía, incluyendo el uso
de un supercomputador para simular eventos en el futuro, o pasado, para probar teorías
astronómicas. La Universidad de Minnesota Supercomputer Center simuló lo que una
explosión de supernova que se origina en el borde de una gigantesca nube de gas
molecular interestelar parecería 650 años después de la explosión.
 Renderizado de imagenes y animación
OpenMP
Es una interfaz de programa de aplicación (API) que se puede utilizar para dirigir
explícitamente paralelismo de memoria compartida multi-procesos. Está compuesto por:

 Directivas de compilación
 Runtime Library Routines
 Variables de entorno
Estructura general de OpenMP en C++

#include <omp.h>
int main () {
int var1, var2, var3;
//Código en serie...

//Comienzo de la región paralela hace fork del conjunto de threads

#pragma omp parallel private(var1, var2) shared(var3)
{
//Región paralela ejecutada por todos los threads
//otras directivas OpenMP
//Todos los threads se juntan en el thread master
}
//Continuación del código...
}

Ejemplo región paralela

#include <omp.h>
#include <stdio.h>
int main(int argc, char *argv[])
{
/* Cada thread tiene una variable id privada (tid) */
int nthreads, tid;

#pragma omp parallel private(tid)

{
/* Se asigna y se imprime el id de cada thread */
tid = omp_get_thread_num();
printf("Hello World desde el thread = %d\n", tid);
/* Solo el thread master ejecuta lo siguiente */
if (tid == 0)
{
 nthreads = omp_get_num_threads();
printf("El numero de threads es = %d\n", nthreads);
}
}
}

 Un programa "Hello World" simple

 Cada hilo ejecuta todo el código encerrado en la región paralela
 Las rutinas de la biblioteca OpenMP se utilizan para obtener identificadores de
subprocesos y número total de subprocesos
 Output:
World desde el thread = 2
Hello World desde el thread = 1
Hello World desde el thread = 4
...
El numero de threads es = x
Parallel For

#include <omp.h>
#include <stdio.h>

#define N 1000
#define CHUNKSIZE 100

int main(int argc, char *argv[])

{

int i, chunk;
float a[N], b[N], c[N];

for (i=0; i < N; i++)

a[i] = b[i] = i * 1.0;
chunk = CHUNKSIZE;

#pragma omp parallel for \

shared(a,b,c,chunk) private(i) \
schedule(static,chunk)

for (i=0; i < N; i++)

c[i] = a[i] + b[i];
}

Programa simple de adición de vectores

 Las matrices A, B, C y la variable N serán compartidas por todos los subprocesos.

 Variable i será privada para cada hilo; Cada hilo tendrá su propia copia única.
 Las iteraciones del bucle "For" se distribuirán dinámicamente en trozos de tamaño
"CHUNK".
 Los hilos no se sincronizarán al completar sus trabajos individuales (NOWAIT).
Sincronización en OpenMP

#include <omp.h>
 int main(int argc, char *argv[])
{
int x;
x = 0;

#pragma omp parallel shared(x)

{
#pragma omp critical
x = x + 1;
}
/* Final de la región paralela */
}

Sincronización por medio del comando "critical"

 El comando CRITICAL especifica una región de código que debe ser ejecutada por un
solo hilo a la vez.
 Si un subproceso está ejecutándose actualmente dentro de una región CRÍTICA y otro
subproceso llega a esa región CRÍTICA e intenta ejecutarla, se bloqueará hasta que el primer
subproceso salga de esa región CRÍTICA.
 todos los hilos del equipo intentarán ejecutarse en paralelo. Sin embargo, debido a la
construcción CRÍTICA que rodea el incremento de x, sólo un hilo podrá leer, incrementar o
escribir x en cualquier momento
Ejemplo de Programación Paralela en Java

public class CajeraThread extends Thread {

private String nombre;
private Cliente cliente;
private long initialTime;
// Constructor, getter & setter

@Override
public void run() {
System.out.println("La cajera " + this.nombre + "
COMIENZA A PROCESAR LA COMPRA DEL CLIENTE "
+ this.cliente.getNombre() + "
EN EL TIEMPO: "
+ (System.currentTimeMillis() -
this.initialTime) / 1000
+ "seg");
for (int i = 0; i <
this.cliente.getCarroCompra().length; i++) {
this.esperarXsegundos(cliente.getCarroCompra()
[i]);
System.out.println("Procesado el producto " +
(i + 1)
+ " del cliente " + this.cliente.getNombre() +
"->Tiempo: "
+ (System.currentTimeMillis() -
this.initialTime) / 1000
+ "seg");
}
System.out.println("La cajera " + this.nombre + " HA
TERMINADO DE PROCESAR "
+
this.cliente.getNombre() + " EN EL TIEMPO: "
 +
(System.currentTimeMillis() - this.initialTime) / 1000
+ "seg");
}

private void esperarXsegundos(int segundos) {

try {
Thread.sleep(segundos * 1000);
} catch (InterruptedException ex) {
Thread.currentThread().interrupt();
}
}
}

Supermercado

En este ejemplo elaborado mediante el uso de objetos en java se simula el proceso de

compra en un supermercado, para esto se tiene la clase cliente y la clase cajero que es la
que se va a paralelizar mediante la herencia de la clase Thread.

Ejemplo de Programación Paralela en Java

public class MainThread {

public static void main(String[] args) {

Cliente cliente1 = new Cliente("Cliente 1", new int[] {

2, 2, 1, 5, 2, 3 });
Cliente cliente2 = new Cliente("Cliente 2", new int[] {
1, 3, 5, 1, 1 });

// Tiempo inicial de referencia

long initialTime = System.currentTimeMillis();
CajeraThread cajera1 = new CajeraThread("Cajera 1",
cliente1, initialTime);
CajeraThread cajera2 = new CajeraThread("Cajera 2",
cliente2, initialTime);

cajera1.start();
cajera2.start();
}
}

Supermercado

Se inicializan los dos hilos, luego se imprime en pantalla cada vez que se pasen los
productos en cada cajero.
Se puede observar como se realiza de forma paralela la compra en cada cajero.

Ejemplo de Programación Paralela en Java

La cajera Cajera 1 COMIENZA A PROCESAR LA COMPRA DEL CLIENTE Cliente
1 EN EL TIEMPO: 0seg
La cajera Cajera 2 COMIENZA A PROCESAR LA COMPRA DEL CLIENTE Cliente
2 EN EL TIEMPO: 0seg
Procesado el producto 1 del cliente Cliente 2->Tiempo: 1seg
Procesado el producto 1 del cliente Cliente 1->Tiempo: 2seg
Procesado el producto 2 del cliente Cliente 2->Tiempo: 4seg
Procesado el producto 2 del cliente Cliente 1->Tiempo: 4seg
Procesado el producto 3 del cliente Cliente 1->Tiempo: 5seg
Procesado el producto 3 del cliente Cliente 2->Tiempo: 9seg
Procesado el producto 4 del cliente Cliente 2->Tiempo: 10seg
Procesado el producto 4 del cliente Cliente 1->Tiempo: 10seg
Procesado el producto 5 del cliente Cliente 2->Tiempo: 11seg
La cajera Cajera 2 HA TERMINADO DE PROCESAR Cliente 2 EN EL TIEMPO:
11seg
Procesado el producto 5 del cliente Cliente 1->Tiempo: 12seg
Procesado el producto 6 del cliente Cliente 1->Tiempo: 15seg
La cajera Cajera 1 HA TERMINADO DE PROCESAR Cliente 1 EN EL TIEMPO:
15seg

Supermercado

Resultados obtenidos al ejecutar el programa para los casos de ejemplo descritos en el

main haciendo uso de dos hilos de trabajo.