Durante esta actividad el alumno será capaz de:
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.
Esta actividad debe ser elaborada de manera individual.
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.
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 ints 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.
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.
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.
Esta actividad será evaluada usando los siguientes criterios:
| 100 | La actividad cumple con todos los requerimientos. |
|---|---|
| -10 | No se incluyó en comentario los datos del autor. |
| 10 | El programa fuente produce uno o más errores al momento de compilarlo. |
| 50-90 | El programa funciona, pero produce algunos errores a tiempo de ejecución y/o los resultados no son del todo correctos. |
| DA | La solución es un plagio. |