qsort pthread

#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 nn quick n, where n is the size of matrixn");
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 sortedn");
return 1;
}
if (sorted(arrayB, n) != 1)
{
printf("B Not sortedn");
return 1;
}
*/
 
if (check(arrayA, arrayB, n) != 1)
{
printf("Different Result Errorn");
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
{
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 %dn", 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 %dnTime : %lfn", 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 %lfn",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;
}