**** The program has to be written in the C programming language and must compile and run in the terminal of a Linux operating system **** a) Program needed b) 5 Examples of the format & info that will help. -------------------------------------------------------------------- A) Program needed: 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 is a circle inscribed in the square dartboard. The radius of the circle is 1 foot, and its area is π 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 π/4. We can use this formula to estimate the value of π 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 a Pthreads program that uses a Monte Carlo method to estimate π. The main thread should read in the total number of tosses and print the estimate. 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 π . -------------------------------- B) Examples: Example 1: The following serial program calculates and displays π. //File name: a.c #include <stdio.h> #include <stdlib.h> #define n 1000000 int main(){ double factor = 1, sum = 0, pi; int i; for(i = 0; i < n; i++){ sum += factor/(2*i+1); factor = -factor; } pi = 4 * sum; printf("pi = %fn", pi); return 0; } Output: pi = 3.141592 ------------------------------------------------- Example 2 The following parallel program calculates and displays π. //File name: a.c #include <stdio.h> #include <stdlib.h> #include <pthread.h> long long n = 100000; long thread_count = 5; //n must be divisible by the value of this variable. long double sum; void *Thread_sum(void* rank); int main(){ long thread; pthread_t* thread_handles; thread_handles = malloc(thread_count*sizeof(pthread_t)); sum = 0; for (thread = 0; thread < thread_count; thread++) pthread_create(&thread_handles[thread], NULL, Thread_sum, (void*) thread); for (thread = 0; thread < thread_count; thread++) pthread_join(thread_handles[thread], NULL); printf("pi = %Lfn", 4 * sum); free(thread_handles); return 0; } void *Thread_sum(void* rank){ long my_rank = (long) rank; double factor; long long i; long long my_n = n/thread_count; long long my_first_i = my_n*my_rank; long long my_last_i = my_first_i + my_n; if(my_first_i % 2 == 0) factor = 1; else factor = -1; for(i = my_first_i; i < my_last_i; i++){ sum += factor/(2*i+1); factor = -factor; } return NULL; } -------------------------------------------- Example 3 We would like to write a parallel program with p threads. Each thread is interchanging two elements of an array of alphabet. //File name: a.c #include <stdio.h> #include <stdlib.h> #include <pthread.h> #include <ctype.h> #include <time.h> #define thread_count 10 char a[] = "abcdefghijklmnopqrstuvwxyz"; pthread_mutex_t mutex[26]; void *change(void* rank); int main (){ pthread_t* thread_handles; int thread, i; printf("Originally: %sn", a); thread_handles = malloc(thread_count*sizeof(pthread_t)); for (i = 0; i < 26; i++) pthread_mutex_init(&mutex[i], NULL); for (thread = 0; thread < thread_count; thread++) pthread_create(&thread_handles[thread], NULL, change, (void*) thread); for (thread = 0; thread < thread_count; thread++) pthread_join(thread_handles[thread], NULL); for(i = 0; i < 26; i++) pthread_mutex_destroy(&mutex[i]); free(thread_handles); printf("Now: %sn", a); return 0; } void *change(void* rank){ int i, j; char t; srandom((unsigned)time(NULL) + (int)rank); i = random()%26; do j = random()%26; while(i == j); pthread_mutex_lock(&mutex[i]); pthread_mutex_lock(&mutex[j]); printf("Thread %d interchanged a[%d] = %c and a[%d] = %c ", (int)rank, i, a[i], j, a[j]); t = a[i]; a[i] = a[j]; a[j] = t; printf("to a[%d] = %c and a[%d] = %cn", i, a[i], j, a[j]); pthread_mutex_unlock(&mutex[j]); pthread_mutex_unlock(&mutex[i]); return NULL; } Output: Originally: abcdefghijklmnopqrstuvwxyz Thread 6 interchanged a[0] = a and a[17] = r to a[0] = r and a[17] = a Thread 7 interchanged a[25] = z and a[5] = f to a[25] = f and a[5] = z Thread 4 interchanged a[5] = z and a[4] = e to a[5] = e and a[4] = z Thread 5 interchanged a[0] = r and a[5] = e to a[0] = e and a[5] = r Thread 9 interchanged a[8] = i and a[19] = t to a[8] = t and a[19] = i Thread 8 interchanged a[22] = w and a[2] = c to a[22] = c and a[2] = w Thread 3 interchanged a[12] = m and a[19] = i to a[12] = i and a[19] = m Thread 2 interchanged a[19] = m and a[2] = w to a[19] = w and a[2] = m Thread 1 interchanged a[6] = g and a[21] = v to a[6] = v and a[21] = g Thread 0 interchanged a[22] = c and a[17] = a to a[22] = a and a[17] = c Now: ebmdzrvhtjklinopqcswugaxyf --------------------------------------------------- Example 4 //File name: a.c #include <stdio.h> #include <stdlib.h> #include <pthread.h> typedef struct{ int rank, a, b; } record_type; int thread_count = 4; void *Thread_add(void* args); int main(){ int thread, x = 1; pthread_t* thread_handles; record_type data[4]; thread_handles = malloc(thread_count*sizeof(pthread_t)); for (thread = 0; thread < thread_count; thread++){ data[thread].rank = thread; data[thread].a = x++; data[thread].b = x++; pthread_create(&thread_handles[thread], NULL, Thread_add, &data[thread]); } for (thread = 0; thread < thread_count; thread++) pthread_join(thread_handles[thread], NULL); free(thread_handles); return 0; } void *Thread_add(void* args){ record_type *data = (record_type *)args; printf("In thread %d sum of %d and %d is %dn",data -> rank,data-> a,data-> b,data-> a + data- >b); return NULL; } Output: In thread 3 sum of 7 and 8 is 15 In thread 2 sum of 5 and 6 is 11 In thread 1 sum of 3 and 4 is 7 In thread 0 sum of 1 and 2 is 3 ----------------------------------------------- Example 5 //File name: a.c #include <stdio.h> #include <stdlib.h> #include <pthread.h> #define m 6 //Number of rows #define n 5 //Number of columns int** a; int *x, *y; int thread_count = 3; //m must be divisible by this number void read(int* a[], int x[]); void *Pth_mat_vect(void* rank); void print(int* a[], int x[], int y[]); int main(){ long thread; pthread_t* thread_handles; a=(int**) malloc(m*sizeof(int*)); x = malloc(n * sizeof(int)); y = malloc(n * sizeof(int)); read(a, x); thread_handles = malloc(thread_count*sizeof(pthread_t)); for (thread = 0; thread < thread_count; thread++) pthread_create(&thread_handles[thread], NULL, Pth_mat_vect, (void*) thread); for (thread = 0; thread < thread_count; thread++) pthread_join(thread_handles[thread], NULL); print(a, x, y); free(thread_handles); return 0; } void *Pth_mat_vect(void* rank){ long my_rank = (long) rank; int i, j; int local_m = m/thread_count; int my_first_row = my_rank*local_m; int my_last_row = my_first_row + local_m; for (i = my_first_row; i < my_last_row; i++){ y[i] = 0; for (j = 0; j < n; j++) y[i] += a[i][j] * x[j]; } return NULL; }