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 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.

Answer 1

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.

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.

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;
}

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;
}