Estás en:   ArielOrtiz.info > Programación paralela y concurrente > Resolviendo problemas con OpenMP

Resolviendo problemas con OpenMP

Objetivos

Durante esta actividad el alumno será capaz de:

• Paralelizar problemas en lenguaje C utilizando OpenMP.

Esta actividad promueve las siguientes habilidades, valores y actitudes: análisis y síntesis, capacidad de resolver problemas, creatividad, y uso eficiente de la informática y las telecomunicaciones.

Resuelve los siguientes dos problemas tomados de [PACHECO] pp. 267 y 268. Compara varios tiempos de ejecución de las versiones secuenciales y paralelas y realiza un breve reporte donde documentes el speedup obtenido.

1. Suppose we toss darts randomly at a square dartboard, whose bullseye is at the origin, and whose sides are 2 feet in length. Suppose also that there’s a circle inscribed in the square dartboard. The radius of the circle is 1 foot, and it’s area is pi square feet. If the points that are hit by the darts are uniformly distributed (and we always hit the square), then the number of darts that hit inside the circle should approximately satisfy the equation

```   number in circle       π
______________________ = ___

total number of tosses    4
```

since the ratio of the area of the circle to the area of the square is pi/4.

We can use this formula to estimate the value of pi with a random number generator:

```number_in_circle = 0;
for (toss = 0; toss < number_of_tosses; toss++) {
x = random double between -1 and 1;
y = random double between -1 and 1;
distance_squared = x*x + y*y;
if (distance_squared <= 1) number_in_circle++;
}
pi_estimate = 4 * number_in_circle/((double) number_of_tosses);
```

This is called a “Monte Carlo” method, since it uses randomness (the dart tosses).

Write an OpenMP program that uses a Monte Carlo method to estimate pi. Use a reduction clause to find the total number of darts hitting inside the circle. Print the result after joining all the threads. You may want to use `long long int`s for the number of hits in the circle and the number of tosses, since both may have to be very large to get a reasonable estimate of pi.

2. Count sort is a simple serial sorting algorithm that can be implemented as follows:

```void count_sort(int a[], int n) {
int i, j, count;
int* temp = malloc(n * sizeof(int));
for (i = 0; i < n; i++) {
count = 0;
for (j = 0; j < n; j++)
if (a[j] < a[i])
count++;
else if (a[i] == a[j] && j < i)
count++;
temp[count] = a[i];
}
memcpy(a, temp, n * sizeof(int));
free(temp);
} /* Count_sort */
```

The basic idea is that for each element `a[i]` in the list `a`, we count the number of elements in the list that are less than `a[i]`. Then we insert `a[i]` into a temporary list using the subscript determined by the count. There’s a slight problem with this approach when the list contains equal elements, since they could get assigned to the same slot in the temporary list. The code deals with this by incrementing the count for equal elements on the basis of the subscripts. If both `a[i] == a[j]` and `j < i`, then we count `a[j]` as being “less than” `a[i]`.

After the algorithm has completed, we overwrite the original array with the temporary array using the string library function `memcpy`.

Write an OpenMP program that includes a parallel implementation of `count_sort`.

¿Qué se debe entregar?

En la parte superior de los archivos fuente de C coloca en comentarios tus datos personales. Por ejemplo:

```/*--------------------------------------------------------------------
*
* Actividad de programación: Resolviendo problemas con OpenMP
* Fecha: 5-Mar-2013
* Autor: 1160611 Anthony Stark
*
*--------------------------------------------------------------------*/
```

Coloca en un archivo tarball llamado `tarea4.tgz` todos los archivos fuentes de tu programa así como el reporte del speedup en formato PDF.

Sube el archivo tarball usando el Sistema de Entrega de Tareas Automatizado.

Fecha límite: Martes, 5 de marzo.