Monografias.com > Sin categoría
Descargar Imprimir Comentar Ver trabajos relacionados

Programación Paralela con Memoria Compartida (página 2)




Enviado por Pablo Turmero



Partes: 1, 2

Monografias.com

Secciones omp
#pragma omp section
Precede cada bloque de código dentro del bloque abarcado descrito anteriormente
Puede ser omitido por la primera sección paralela después del pragma parallel sections
Los segmentos de programa adjuntos se distribuyen para ejecución paralela entre hilos disponibles

Monografias.com

Paralelismo a nivel funcional con secciones
#pragma omp parallel sections
{
#pragma omp section /* Optional */
a = alice();
#pragma omp section
b = bob();
#pragma omp section
c = cy();
}

s = boss(a, b);
printf ("%6.2fn", bigboss(s,c));

(Gp:)

Monografias.com

Ventajas de las secciones paralelas
Secciones independientes de código se pueden ejecutar concurrentemente

Serial
Paralela
#pragma omp parallel sections
{
#pragma omp section
phase1();
#pragma omp section
phase2();
#pragma omp section
phase3();
}

Monografias.com

Nuevo Soporte de OpenMP
Tareas – Lo principal en OpenMP 3.0
Permite paralelización de problemas irregulares
Ciclos sin límite
Algoritmos recursivos
Productor/Consumidor

Monografias.com

¿Qué son las tareas?
Las tareas son unidades de trabajo independientes
Los hilos se asignan para ejecutar trabajo en cada tarea
Las tareas pueden diferirse
Las tareas pueden ejecutarse inmediatamente
El sistema en tiempo de ejecución decide cual de las descritas anteriormente
Las tareas se componen de:
código para ejecutar
Ambiente de datos
Variables de control internas (ICV)
Serial
Paralelo

Monografias.com

Ejemplo de task
Se crea un grupo de 8 hilos
#pragma omp parallel
// assume 8 threads
{
#pragma omp single private(p)
{

while (p) {
#pragma omp task
{
processwork(p);
}
p = p->next;
}
}
}
Un hilo tiene acceso a ejecutar el ciclo while
El hilo que ejecuta el “ciclo while” crea una tarea por cada instancia de processwork()

Monografias.com

Task – Visión explícita de una tarea
Se crea un equipo de hilos en el omp parallel
Un solo hilo se selecciona para ejecutar el ciclo while – a este hilo le llamaremos “L”
El hilo L opera el ciclo while, crea tareas, y obtiene el siguiente apuntador
Cada vez que L pasa el omp task genera una nueva tarea que tiene un hilo asignada
Cada tarea se ejecuta en su propio hilo
Todas las tareas se terminan en la barrera al final de la región paralela

#pragma omp parallel
{
#pragma omp single
{ // block 1
node * p = head;
while (p) { //block 2
#pragma omp task private(p)
process(p);
p = p->next; //block 3
}
}
}

Monografias.com

¿Qué tareas son útiles?
#pragma omp parallel
{
#pragma omp single
{ // block 1
node * p = head;
while (p) { //block 2
#pragma omp task
process(p);
p = p->next; //block 3
}
}
}

Tienen potencial para paralelizar patrones irregulares y llamadas a funciones recursivas
(Gp:) Bloque 1
(Gp:) Bloque 2tarea 1
(Gp:) Bloque 2tarea 2
(Gp:) Bloque 2tarea 3
(Gp:) Bloque 3
(Gp:) Bloque3
(Gp:) Tiempo
(Gp:) Un solo hilo

(Gp:) Bloque 1
(Gp:) Bloque 3
(Gp:) Bloque 3
(Gp:) Hilo1 Hilo2 Hilo3 Hilo4
(Gp:) Bloque 2tarea 2
(Gp:) Bloque2tarea 1
(Gp:) Bloque2tarea 3
(Gp:) Tiempo ahorrado

(Gp:) Espera
(Gp:) Espera

Monografias.com

Actividad 3 – Lista encadenada usando tareas
Objetivo: Modifica la lista encadenada para implementar tareas para paralelizar la aplicación
Sigue la lista encadenada de tareas llamada LinkedListTask en el documento de la práctica

while(p != NULL){
do_work(p->data);
p = p->next;
}

Monografias.com

¿Cuándo las tareas se garantizan a ser completadas?
Las tareas se garantizan a ser completadas:
En las barreras de los hilos o tareas
En la directiva: #pragma omp barrier
En la directiva : #pragma omp taskwait

Monografias.com

Ejemplo de terminación de tareas
#pragma omp parallel
{
#pragma omp task
foo();
#pragma omp barrier
#pragma omp single
{
#pragma omp task
bar();
}
}
Aquí se crean varias tareas foo – una para cada hilo
Se garantiza que todas las tareas foo terminan aquí
Aquí se crea una tarea bar
Se garantiza que la tarea bar termina aquí

Monografias.com

Alcance de los datos – ¿Qué se comparte?
OpenMP usa un modelo de memoria compartida
Variable compartida – una variable que pueden leer o escribir varios hilos
La cláusula shared puede usarse para hacer elementos explícitamente compartidos
Las variables globales se comparten por default entre tareas
Variables globales, variables con alcance del namespace, variables estáticas, variables con calificador de constante que no tienen miembro mutable son compartidas, Variables estáticas que son declaradas en un alcance dentro del bloque de construcción son compartidas

Monografias.com

Alcance de los datos – ¿Qué es privado?
No todo se comparte…
Ejemplos de determinadas variables implícitamente privadas:
Las variables locales (stack) en funciones llamadas de regiones paralelas son PRIVADAS
Las variables automáticas dentro de un bloque de sentencias de omp son PRIVADAS
Las variables de iteración de ciclos son privadas
Las variables implícitamente declaradas privadas dentro de tareas serán tratadas como firstprivate

La cláusula Firstprivate declara uno o más elementos a ser privados para una tarea, y inicializa cada uno de ellos con un valor

Monografias.com

Un ejemplo de ambiente de datos
(Gp:) temp
(Gp:) A, index, count
(Gp:) temp
(Gp:) temp
(Gp:) A, index, count

¿Cuáles variables son compartidas y cuáles privadas?
float A[10];
main ()
{
integer index[10];
#pragma omp parallel
{
Work (index);
}
printf (“%dn”, index[1]);
}
extern float A[10];
void Work (int *index)
{
float temp[10];
static integer count;
<…>
}
A, índex, y count se comparten en todos los hilos, pero temp es local para cada hilo

Monografias.com

int fib ( int n )
{

int x,y;
if ( n < 2 ) return n;
#pragma omp task
x = fib(n-1);
#pragma omp task
y = fib(n-2);
#pragma omp taskwait
return x+y
}
Problema con el Alcance de los datos – ejemplo de fib
n es privada en ambas tareas
¿Qué es incorrecto?
No se pueden usar variables
privadas fuera de las tareas
x es una variable privaday es una variable privada

Monografias.com

int fib ( int n )
{

int x,y;
if ( n < 2 ) return n;
#pragma omp task shared(x)
x = fib(n-1);
#pragma omp task shared(y)
y = fib(n-2);
#pragma omp taskwait
return x+y;
}

n es privada en ambas tareas
x & y son compartidas
Buena solución necesitamos ambos valores para calcular sum
Ejemplo del alcance de datos – ejemplo de fib

Monografias.com

List ml; //my_list
Element *e;
#pragma omp parallel
#pragma omp single
{
for(e=ml->first;e;e=e->next)
#pragma omp task
process(e);
}
Problema con el alcance de datos – Recorrido de listas
¿Qué está mal aquí?
Posible condición de concurso !La variable compartida e la actualizan múltiples tareas

Monografias.com

List ml; //my_list
Element *e;
#pragma omp parallel
#pragma omp single
{
for(e=ml->first;e;e=e->next)
#pragma omp task firstprivate(e)
process(e);
}
Buena solución – e es firstprivate
Ejemplo de alcance de datos – Recorrido de listas

Monografias.com

List ml; //my_list
Element *e;
#pragma omp parallel
#pragma omp single private(e)
{
for(e=ml->first;e;e=e->next)
#pragma omp task
process(e);
}
Buena solución – e es privada
Ejemplo de alcance de datos – Recorrido de listas

Monografias.com

List ml; //my_list
#pragma omp parallel
{
Element *e;
for(e=ml->first;e;e=e->next)
#pragma omp task
process(e);
}
Ejemplo de alcance de datos – Recorrido de listas
Buena solución – e es privada

Monografias.com

Ejemplo: Producto Punto
float dot_prod(float* a, float* b, int N)
{
float sum = 0.0;
#pragma omp parallel for shared(sum)
for(int i=0; i< num_steps; i++){
x = (i+0.5)*step;
sum = sum + 4.0/(1.0 + x*x);
}
pi = step * sum;
printf(“Pi = %fn”,pi);
}

Monografias.com

C/C++ Operaciones de reducción
Un rango de operadores asociativos y conmutativos pueden usarse con la reducción
Los valores iniciales son aquellos que tienen sentido

Monografias.com

Actividad 4 – Calcular Pi
Paraleliza el código de integración numérica usando OpenMP
¿Qué variables pueden compartirse?
¿Qué variables necesitan ser privadas?
¿Qué variables pueden usarse en reducciones?
static long num_steps=100000; double step, pi;

void main()
{ int i;
double x, sum = 0.0;

step = 1.0/(double) num_steps;
for (i=0; i< num_steps; i++){
x = (i+0.5)*step;
sum = sum + 4.0/(1.0 + x*x);
}
pi = step * sum;
printf(“Pi = %fn”,pi);
}

Monografias.com

Bloque de construcción Single
Denota un bloque de código que será ejecutado por un solo hilo
El hilo seleccionado es dependiente de la implementación
Barrera implícita al final
#pragma omp parallel
{
DoManyThings();
#pragma omp single
{
ExchangeBoundaries();
} // threads wait here for single
DoManyMoreThings();
}

Monografias.com

Bloque de construcción Master
Denota bloques de código que serán ejecutados solo por el hilo maestro
No hay barrera implícita al final
#pragma omp parallel
{
DoManyThings();
#pragma omp master
{ // if not master skip to next stmt
ExchangeBoundaries();
}
DoManyMoreThings();
}

Monografias.com

Barreras implícitas
Varias sentencias de OpenMP* tienen barreras implícitas
Parallel – barrera necesaria – no puede removerse
for
single
Las barreras innecesarias afectan el rendimiento y pueden removerse con la cláusula nowait
La cláusula nowait puede aplicarse a :
La cláusula For
La cláusula Single

Monografias.com

Cláusula Nowait
Cuando los hilos esperarían entren cómputos independientes
#pragma single nowait
{ […] }

#pragma omp for nowait
for(…)
{…};
#pragma omp for schedule(dynamic,1) nowait
for(int i=0; i< n; i++) {
#pragma omp atomic
x[index[i]] += work1(i);
y[i] += work2(i);
}

Monografias.com

Bloque de Construcción Parallel – Vista de tareas explícita
Las tareas se crean en OpenMP incluso sin una directiva task explícita
Veremos como las tareas se crean implícitamente para el fragmento de código que está abajo.
El hilo que encuentra la sentencia parallel empaca un conjunto de tareas implícitas
Se crea un conjunto de hilos.
Cada hilo en el equipo está asignado a una de las tareas (y vinculado a ella).
La barrera mantiene el hilo maestro original hasta que todas las tareas implícitas terminan
(Gp:) #pragma omp parallel

(Gp:) #pragma omp parallel
{ int mydata
code
}

{ int mydata; code…
}
(Gp:) { mydatacode
}

(Gp:) { mydatacode
}
(Gp:) { mydatacode
}

(Gp:) Thread
(Gp:) 1
(Gp:) Thread
(Gp:) 2
(Gp:) Thread
(Gp:) 3

Barrier

Monografias.com

Bloque de construcción Task
#pragma omp task [clause[[,]clause] …]
bloque estructurado
if (expresion)
untied
shared (lista)
private (lista)
firstprivate (lista)
default( shared | none )
Donde la claúsula puede ser un:

Monografias.com

Tareas vinculadas y tareas no vinculadas
Tareas vinculadas:
Una tarea vinculada se le asigna un hilo en su primera ejecución y este mismo hilo le da servicio a la tarea por su tiempo de vida.
Un hilo ejecutando una tarea vinculada, puede suspenderse, y enviarse a ejecutar otra tarea, pero eventualmente, el mismo hilo regresará a continuar la ejecución de su tarea vinculada originalmente.
Las tareas están vinculadas mientras no se declare desvincular explícitamente

Monografias.com

Tareas vinculadas y tareas no vinculadas
Tareas no vinculadas:
Una tarea no vinculada no tienen ninguna asociación a largo plazo con ningún hilo. Cualquier hilo que no esté ocupado puede ejecutar una tarea no vinculada. El hilo asignado para ejecutar una tarea no vinculada solo puede cambiar en un “punto de planificación de tareas”
Una tarea no vinculada se crea agregando “untied” a la cláusula tarea
Ejemplo: #pragma omp task untied

Monografias.com

Cambio de tareas
Cambio de tareas El acto de un hilo en cambiar de la ejecución de una tarea a otra tarea.

El propósito de cambiar la tarea es distribuir hilos a lo largo de las tareas no asignadas en el equipo para evitar que se acumulen colas largas de tareas no asignadas

Monografias.com

Cambio de tareas
El cambio de tareas, para tareas vinculadas, solo puede ocurrir en puntos de planificación de tareas localizados dentro de los siguientes bloques de construcción
Se encuentran sentencias task
Se encuentran sentencias taskwait
Se encuentran directivas barrier
Regiones barrier implícitas
Al final de una región de tarea vinculada

Las tareas no vinculadas tienen implementación dependiendo de los puntos de planificación

Partes: 1, 2
 Página anterior Volver al principio del trabajoPágina siguiente 

Nota al lector: es posible que esta página no contenga todos los componentes del trabajo original (pies de página, avanzadas formulas matemáticas, esquemas o tablas complejas, etc.). Recuerde que para ver el trabajo en su versión original completa, puede descargarlo desde el menú superior.

Todos los documentos disponibles en este sitio expresan los puntos de vista de sus respectivos autores y no de Monografias.com. El objetivo de Monografias.com es poner el conocimiento a disposición de toda su comunidad. Queda bajo la responsabilidad de cada lector el eventual uso que se le de a esta información. Asimismo, es obligatoria la cita del autor del contenido y de Monografias.com como fuentes de información.

Categorias
Newsletter