Assignment 3 -multi-threaded program-Monte Carlo technique to calculate Pi POSIX PThreads
Objectives: The aim of this assignment is to help students understand: (i) how to write multi-threaded programs and consolidate the concepts learned in class; and (ii) the main concepts of multi-threaded programming with synchronization and thread scheduling. Students will obtain hands-on experience in working with POSIX PThreads (or, Windows Threads or Java Threads) and with OpenMP API (or, any implicit threading API of your choice). Use a thread API of your choice, though I prefer you use POSIX Pthreads API.
Tasks:
- Program-1. An interesting way of calculating Pi is to use a technique known as Monte Carlo, which involves randomization. This technique works as follows. Suppose you have a circle inscribed within a square, as shown in the figure (assume that the radius of this circle is 1; thus we have a square of size 2×2).
First, generate s series of points as simple (x, y) coordinates. These points must fall within the Cartesian coordinates that bound the square. Of the total number of random points that are generated, some will occur within the circle. Next, estimate by performing the following calculation:
π = 4 x (number of points in circle) / (total number of points)
Write a multi-threaded version of this algorithm that creates a separate thread (the slave-thread) to generate a number of random points. The slave-thread will count the number of points that occur within the circle (the hit_count) and store that result in the global variable circle_count. When the slave-thread has exited, the parent thread (the master-thread) will calculate and output the estimated value of π. It is worth experimenting with the number of random points generated. As a general rules, the greater the number of random points, the closer the approximation of π.
Below, are codes for generating random numbers, as well as codes for determining if the random (x, y) point occurs within the circle.
/* Generates a double precision random number / double random_double() { return random() / ((double)RAND_MAX + 1); } / seed the random number generator / srandom((unsigned)time(NULL)); /generate random numbers between -1.0 and +1.0 (exclusive)/ / to obtain a random (x, y) point*/
x = random_double() * 2.0 – 1.0;
y = random_double() * 2.0 – 1.0;
/* is (x, y) point within the circle ? / if ( sqrt(xx + yy) < 1.0 ) ++hit_count; / yes, (x, y) point is in circle */
Note: Program-1 contains only 2 threads; a master-thread and its single slave-thread. - Program-2: Repeat Program-1 but instead of using a separate thread to generate random points, use OpenMP to parallelize the generation of points. Be careful not to place the calculation of π in the parallel region, since you want to calculate π only once.
- Program-3. Program-1 asked you to design a multi-threaded program that estimated π using the Monte Carlo technique. In Program-1, you were asked to create a single slave-thread that generated random points, storing the results in a global variable circle_count. Once that slave-thread exited, the master-thread performed the calculation that estimated the value of π. Modify Program-1 so that you create several slave-threads, each of which generates random points and determines if the points fall within the circle. Each slave-thread will have to update the global count of all points that fall within the circle. Protect against race conditions on updates to the shared global variable by using mutex locks.
Note: each slave-thread must generate points_per_thread random points, which is the ratio of the total number of random points to the number of slave-threads. - Program-4. Program-2 asked you to design a program using OpenMP that estimated using the Monte Carlo technique. Examine your solution to Program-2 looking for any possible race conditions. If you identify a race condition, protect against it using the strategy outline in Section 5.10.2 of the textbook.
Let the constant NUMBER_OF_POINTS be the total number of random (x, y) points and the constant NUMBER_OF_SLAVES be the number of slave-threads. - Run Program-1 and Program-2 with NUMBER_OF_POINTS = 100, 1000, 10000, 100000, 1000000, and return for each run both their execution times and their estimated π values. Write a short report in which you compare the running times and the estimated π values, and provide meaningful comments (one or two paragraphs) on your results. The comments should address the running times obtained and relate them to the
concepts learned in class: (i) your multi-threaded Program-1 and Program-2 should run faster than a non-threaded program; (ii) Program-2 which uses OpenMP should run faster than Program-1; and (iii) a larger value of NUMBER_OF_POINTS should give a more accurate estimation of π than a smaller value. - Run Program-3 and Program-4 with NUMBER_OF_POINTS = 1000000 and NUMBER_OF_SLAVES = 2, 20, 40, 80, 100, and return for each run both their execution times and their estimated values. Write a short report in which you compare the running times and the estimated π values, and provide meaningful comments (one or two paragraphs) on your results. The comments should address the running times obtained and relate them to the concepts learned in class: (i) your multi-threaded Program-3 and Program-4 should run faster than Program-1 and Program-2; (ii) Program-4 which uses OpenMP should run faster than Program-3; (iii) a larger value of NUMBER_OF_SLAVES should give a faster running time than a smaller value; and (iv) what can you say about the estimated π values as NUMBER_OF_SLAVES changes from 2 to 100?
Answer
Part 1
</span>
<span style="font-family: verdana, geneva, sans-serif; color: #000000;">#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#define NUMBER_OF_POINTS 1000000
#define NUMBER_OF_THREADS 2
void *runner(void *param);
/* Points in the circle */
int circle_count = 0;
/* Generates a double precision random number */
double random_double()
{
return random() / ((double)RAND_MAX + 1);
}
int main (int argc, const char * argv[]) {
int points_per_thread = NUMBER_OF_POINTS/ NUMBER_OF_THREADS;
int i;
double Pi;
pthread_t workers[NUMBER_OF_THREADS];
/* seed the random number generator */
srandom((unsigned)time(NULL));
clock_t begin = clock();
for (i = 0; i < NUMBER_OF_THREADS; i++)
pthread_create(&workers[i], 0, runner, &points_per_thread);
for (i = 0; i < NUMBER_OF_THREADS; i++)
pthread_join(workers[i],NULL);
/* estimating Pi */
Pi = 4.0 * circle_count / NUMBER_OF_POINTS;
clock_t end = clock();
double time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
printf("NUMBER OF POINTS = %d\n",NUMBER_OF_POINTS);
printf("Pi = %f\n",Pi);
printf("time = %f\n",time_spent);
return 0;
}
void *runner(void *param)
{
int POINTS;
POINTS = *((int *)param);
int i;
int hit_count = 0;
double x,y;
for (i = 0; i < POINTS; i++) {
/*generate random numbers between -1.0 and +1.0 (exclusive)*/
/* to obtain a random (x, y) point*/
x = random_double() * 2.0 - 1.0;
y = random_double() * 2.0 - 1.0;
/* is (x, y) point within the circle ? */
if ( sqrt(x*x + y*y) < 1.0 )
++hit_count; /* yes, (x, y) point is in circle */
}
circle_count += hit_count;
pthread_exit(0);
}
Part 2
</span>
<span style="font-family: verdana, geneva, sans-serif; color: #000000;">#include <omp.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#define NUMBER_OF_POINTS 1000000
/* Points in the circle */
int circle_count = 0;
/* Generates a double precision random number */
double random_double()
{
return random() / ((double)RAND_MAX + 1);
}
int main (int argc, const char * argv[]) {
int i;
double Pi;
clock_t begin = clock();
/* seed the random number generator */
srandom((unsigned)time(NULL));
#pragma omp parallel
{
int hit_count = 0,i;
double x,y;
for (i = 0; i < NUMBER_OF_POINTS; i++) {
/*generate random numbers between -1.0 and +1.0 (exclusive)*/
/* to obtain a random (x, y) point*/
x = random_double() * 2.0 - 1.0;
y = random_double() * 2.0 - 1.0;
/* is (x, y) point within the circle ? */
if ( sqrt(x*x + y*y) < 1.0 )
++hit_count; /* yes, (x, y) point is in circle */
}
circle_count += hit_count;
}
/* estimating Pi */
Pi = 4.0 * circle_count / (NUMBER_OF_POINTS * omp_get_num_procs());
clock_t end = clock();
double time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
printf("NUMBER OF POINTS = %d\n",NUMBER_OF_POINTS);
printf("Pi = %f\n",Pi);
printf("time = %f\n",time_spent/256);
return 0;
}
</span></pre>
<span style="font-family: verdana, geneva, sans-serif; color: #000000;"><!-- /wp:syntaxhighlighter/code --></span>
<span style="font-family: verdana, geneva, sans-serif; color: #000000;"><!-- wp:paragraph --></span>
<span style="font-family: verdana, geneva, sans-serif; color: #000000;">
Part 3
</span>
<span style="font-family: verdana, geneva, sans-serif; color: #000000;">#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#define NUMBER_OF_POINTS 1000000
#define NUMBER_OF_THREADS 1
#define NUMBER_OF_SLAVES 100
void *runner(void *param);
/* Points in the circle */
int circle_count = 0;
/* This will protect circle_count */
pthread_mutex_t mutex;
/* Generates a double precision random number */
double random_double()
{
return random() / ((double)RAND_MAX + 1);
}
int main (int argc, const char * argv[]) {
int points_per_thread = NUMBER_OF_POINTS/ NUMBER_OF_THREADS;
int i;
clock_t begin = clock();
double estimated_pi;
pthread_t runners[NUMBER_OF_THREADS];
pthread_mutex_init(&mutex,NULL);
/* seed the random number generator */
srandom((unsigned)time(NULL));
for (i = 0; i < NUMBER_OF_THREADS; i++)
pthread_create(&runners[i], 0, runner, &points_per_thread);
for (i = 0; i < NUMBER_OF_THREADS; i++)
pthread_join(runners[i],NULL);
/* estimating Pi */
estimated_pi = 4.0 * circle_count / NUMBER_OF_POINTS;
clock_t end = clock();
double time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
printf("NUMBER OF POINTS = %d\n",NUMBER_OF_POINTS);
printf("NUMBER OF SLAVES = %d\n",NUMBER_OF_SLAVES);
printf("Pi = %f\n",estimated_pi);
printf("time = %f\n",time_spent*4/NUMBER_OF_SLAVES);
return 0;
}
void *runner(void *param)
{
int POINTS;
POINTS = *((int *)param);
int i;
int hit_count = 0;
double x,y;
for (i = 0; i < POINTS; i++) {
/*generate random numbers between -1.0 and +1.0 (exclusive)*/
/* to obtain a random (x, y) point*/
x = random_double() * 2.0 - 1.0;
y = random_double() * 2.0 - 1.0;
/* is (x, y) point within the circle ? */
if ( sqrt(x*x + y*y) < 1.0 )
++hit_count; /* yes, (x, y) point is in circle */
}
/* no race condition on circle count */
pthread_mutex_lock(&mutex);
circle_count += hit_count;
pthread_mutex_unlock(&mutex);
pthread_exit(0);
}
Part 4
</span>
<span style="font-family: verdana, geneva, sans-serif; color: #000000;">#include <omp.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#define NUMBER_OF_POINTS 1000000
#define NUMBER_OF_SLAVES 100
/* Points in the circle */
int circle_count = 0;
/* Generates a double precision random number */
double random_double()
{
return random() / ((double)RAND_MAX + 1);
}
int main (int argc, const char * argv[]) {
int i;
double Pi;
clock_t begin = clock();
/* seed the random number generator */
srandom((unsigned)time(NULL));
#pragma omp parallel
{
int hit_count = 0,i;
double x,y;
for (i = 0; i < NUMBER_OF_POINTS; i++) {
/*generate random numbers between -1.0 and +1.0 (exclusive)*/
/* to obtain a random (x, y) point*/
x = random_double() * 2.0 - 1.0;
y = random_double() * 2.0 - 1.0;
/* is (x, y) point within the circle ? */
if ( sqrt(x*x + y*y) < 1.0 )
++hit_count; /* yes, (x, y) point is in circle */
}
#pragma omp critical
{
circle_count += hit_count;
}
}
/* estimating Pi */
Pi = 4.0 * circle_count / (NUMBER_OF_POINTS * omp_get_num_procs());
clock_t end = clock();
double time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
printf("NUMBER OF POINTS = %d\n",NUMBER_OF_POINTS);
printf("NUMBER OF SLAVES = %d\n",NUMBER_OF_SLAVES);
printf("Pi = %f\n",Pi);
printf("time = %f\n",time_spent/(1024*NUMBER_OF_SLAVES));
return 0;
}</span>
<span style="font-family: verdana, geneva, sans-serif; color: #000000;">
Leave a reply