Kyle Wu

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define NUM_THREADS 8

#define FRAND frand(1, 100)
#define frand(xmin, xmax) ( (double)xmin + (double)(xmax-xmin) * rand()/(double)RAND_MAX)

void serial(double*, int, int);
int partition(double*, int, int, int);
void swap(double*, double *);

void parallel(double*, int, int);
void* parallel_thread(void *);

void print(double*, int);
int check(double*, double*, int);
int sorted(double*, int);

int timer();

struct thread_data {
    double *array;
    int left;
    int right;
    int current_depth;
    int depth;
} ;

int main(int argc, const char *argv[])
{
   

    int n;
    int num_threads;
    double* arrayA;
    double* arrayB;

    int serial_time;
    int parallel_time;

    int i;
    if (argc != 3) {
        printf("Please support an argument n\n quick n, where n is the size of matrix\n");
        return 1;
    }

    n = atoi(argv[1]);
    num_threads = atoi(argv[2]);

    arrayA = (double*) malloc(n * sizeof(double));
    arrayB = (double*) malloc(n * sizeof(double));
    for (i = 0; i < n; i++) {
        arrayA[i] = FRAND;
        arrayB[i] = arrayA[i];
    }
    //printf("Array :\n");
    //print(arrayA, n);

    serial_time = timer();
    serial(arrayA, 0, n-1);
    serial_time = timer() - serial_time;

    printf("Serial time : %f \n", serial_time/1000000.0);

    parallel_time = timer();
    parallel(arrayB, n, num_threads);
    parallel_time = timer() - parallel_time;

    printf("Parallel time : %f \n", parallel_time/1000000.0);

    /*
    if (sorted(arrayA, n) != 1)
    {
        printf("A Not sorted\n");
        return 1;
    }
    if (sorted(arrayB, n) != 1)
    {
        printf("B Not sorted\n");
        return 1;
    }
    */

    if (check(arrayA, arrayB, n) != 1)
    {
        printf("Different Result Error\n");
        return 1;
    }

    //printf("Result A:\n");
    //print(arrayA, n);
    //print(arrayB, n);

    return 0;
}

int partition(double *A, int left, int right, int pivotIndex)
{
    int i,storeIndex;
    double pivotValue = *(A+pivotIndex);
    swap(A+pivotIndex,A+right);
    storeIndex = left;
    for(i=left;i<right;i++)
    {
        if(*(A+i) <= pivotValue)
        {
            swap(A+i,A+storeIndex);
            storeIndex++;
        }
    }
    swap(A+storeIndex,A+right);
    return storeIndex;
}
 
void serial(double *A,int left,int right)
{
    int pivotIndex,pivotNewIndex;
    if(right > left)
    {
        pivotIndex = left + (right - left)/2;
        pivotNewIndex = partition(A,left,right,pivotIndex);
        serial(A,left,pivotNewIndex - 1);
        serial(A,pivotNewIndex + 1,right);
    }
}

void parallel(double* A, int n, int num)
{
    struct thread_data thread_data;
    pthread_t thread;
    void* status;
    thread_data.array = A;
    thread_data.left = 0;
    thread_data.right = n-1;
    thread_data.current_depth = 0;
    thread_data.depth = log2(num);

    parallel_thread((void*)&thread_data);
}

void* parallel_thread(void *data)
{
    int i;
    double time;

    // Get data
    struct thread_data *my_data = (struct thread_data*)data;
    double* array = my_data->array;
    int left = my_data->left;
    int right = my_data->right;
    int depth = my_data->depth;
    int current_depth = my_data->current_depth;

    // pthread attribute
    pthread_attr_t attr;
    pthread_attr_init(&attr);
    pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE);

    // threads array
    pthread_t *threads = (pthread_t*) malloc( (depth - current_depth) * sizeof(pthread_t) );
    struct thread_data *thread_data_array = (struct thread_data*) malloc ((depth - current_depth) * sizeof(struct thread_data) );
    void* status;

    // variables for partition
    int l,r;
    double pivot;
    double temp;
    int pivotIndex;

    for (i = 0; i < depth - current_depth; i++) {
   
        // partition
        pivotIndex = left + (right-left)/2;

        l = left;
        r = right;
        pivot = array[pivotIndex];

        time = timer();
       while (l <= r) {
            while (*(array + l) < pivot)
                l++;
            while (*(array + r) > pivot)
                r--;
            if (l <= r) {
                temp = array[l];
                array[l] = array[r];
                array[r] = temp;
                l++;
                r--;
            }
        };
   
        // construct thread data
        thread_data_array[i].array = array;
        thread_data_array[i].left = l;
        thread_data_array[i].right = right;
        thread_data_array[i].depth = depth;
        thread_data_array[i].current_depth = current_depth + i + 1;

        //printf("new thread left %d right %d %d new %d\n", thread_data_array[i].left, thread_data_array[i].right, current_depth, thread_data_array[i].current_depth);
        pthread_create(&threads[i], &attr, parallel_thread, (void *)&thread_data_array[i]);

        // update local variable
        right = r;
    }

    //time = timer();
    serial(array, left, right);
    //printf("%d begin serial sort left %d right %d\nTime : %lf\n", current_depth, left, right, (timer()-time) / 10e6);

    for (i = 0; i < depth - current_depth; i++) {
        pthread_join(threads[i], &status);
    }
   
}

int timer(void)
{
  struct timeval tv;
  gettimeofday(&tv, (struct timezone*)0);
  return (tv.tv_sec*1000000+tv.tv_usec);
}

void swap(double *A, double *B)
{
    double temp;
    temp = *A;
    *A = *B;
    *B = temp;
    return;
}

void print(double* A, int n)
{
    int i;
    for (i = 0; i < n; i++) {
        printf("%lf ", A[i]);
    }
    printf("\n");
}

int check(double* A, double* B, int n)
{
    int i;
    for (i = 0; i < n; i++) {
        if(A[i] - B[i] > 10e-6){
            printf("\n%d %lf %lf\n",i, A[i], B[i]);
            return 0;
        }
    }
    return 1;
}

int sorted(double *A, int n)
{
    int i;
    for (i = 0; i < n-1; i++) {
        if(A[i] - A[i+1] > 10e-6) return 0;
    }
    return 1;
}