Question

Help with a Parallel and Distributed Programming assignment.

In this assignment, you will be exploring different methods of counting the prime numbers between 1 and N. You will use 8 threads, and each will be given a range in which to count primes. The question is: where do you store your counter? Do you use a local variable? Do you use a global variable?

Please use the following function to determine whether an integer number is a prime.

// Return 1 if n is prime, else 0

int is_prime(int n) {

  if (n < 2)return 0;

  if (n == 2)return 1;

  if (n % 2 == 0)return 0;

  for (int i=3; i < n; i += 2) {

    if (n % i == 0) return 0;

  }

  return 1;

}

Part 1: Simple Solutions

Each thread counts a section of the array (the first thread gets numbers 1 through N/8, the second threads gets numbers N/8+1 through 2*N/8, etc.) - it is alright to mandate that N be a multiple of 8 so that it divides evenly among the threads. It doesn't matter if N is a global variable, constant, or command line input. I have found that the value N=800000 is a good one for my desktop (it takes long enough for me to time it, but not too long).

Solution 1: Global Counter (Scalar)

Use a global variable to keep track of the total count of prime numbers. Since all threads will be reading and writing to it like crazy, we need to protect it with a mutexlock. So, make a global variable mutexlock. Every time a thread sees a prime number, it locks the lock, updates the counter, and then unlocks the lock.

Solution 2: Global Counter (Array), Global Scalar Update

Use a global variable that is an array of counters - one counter for each thread. When a thread sees a prime number, it updates its entry in the global array. Before the thread exits, it should update a mutexprotected global scalar variable.

Solution 3: Global Counter (Array), Global Array Update – No mutex required

Use a global variable that is an array of counters - one counter for each thread. When a thread sees a prime number, it updates its entry in the global array. The main code should be responsible for summing the entries in this array. I do this after each thread is joined.

Solution 4: Local Counter, Global Scalar Update

Use a local variable to keep track of an individual thread's prime number count. Then, before the thread exits, it should update a mutex protected global scalar value.

This is what I have so far.

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h> //for the time
#include <pthread.h> //include pthreads

// Return 1 if n is prime, else 0
int is_prime(int n) {
    if (n < 2) return 0;
    if (n == 2) return 1;
    if (n % 2 == 0) return 0;
    for (int i=3; i < n; i += 2) {
        if (n % i == 0) return 0;
    }
    return 1;
}

int main(int argc, char* argv[]){
    pthread_t tid[8]; //We're only using 8 threads
    pthread_attr_t attr; //Thread attribute object identifier

    //In addition to checking the primality of all these numbers,
    //we have to log the time it took for the program to complete its operations
    struct timeval start, end; //timeval structs contain tv_sec & tv_usec (microseconds)
    gettimeofday(&start, NULL); //2nd argument is timezone

    long input = strtol(argv[1], (char**) NULL, 10); //Convert the user input to a long type

    //The pthreads code should should somewhere between here and the
    //next gettimeofday() call


    pthread_attr_init(&attr); //Create thread attribute object

    //This SHOULD create 8 threads and send an 8th of the data to each
    //is_prime() function call
    for (int i=0; i<8; i+=1){
        printf("Half of data: %i\n", i);
        for (long j=i*input/8+1; j<=(i+1)*input/8; j+=1){
            pthread_create(&tid[i], &attr, is_prime, j);
            int result = is_prime(j);
            /*if (result){
                printf("%li is prime\n", j);
            }else{
                printf("%li is not prime\n", j);
            }*/
        }
    }
    for (int i=0; i<8; i+=1){
        //pthread_join(tid[i], NULL);
        //Suspend execution of tid[i] until tid[i-1] terminates
    }

    //We need to check the primality of each individual number
    //between 1 and N (the user's input)
    /*for (long i = 1; i <= input; i+=1){
        is_prime(i); //Calls is_prime with i as its argument
    }*/


    //Log the time the operation ended so we can show how long it took
    gettimeofday(&end, NULL);

    //Print how long the operations took
    printf("Time used for operations: %ld\n", 
            ((end.tv_sec * 1000000 + end.tv_usec) - 
                (start.tv_sec * 1000000 + start.tv_usec))
          );
    
    return 0;
}

Answer 1

Answer:

We will store the value of Counter as a global variable to betterly access the variable.

Benefit of declaring the counter variable as Global:

1. Global variable is accessible through out the program so from anywhere in the program we can access the value of global (Counter) variable.

2. Global variable initializes its value at the time of object creation through constructor.

3. We can access the value of global variable in inside of any method or in any class.