Exercise 1 for the course "Parallel and distributed systems" of THMMY in AUTH university.
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

249 lines
6.2 KiB

4 years ago
/*
bitonic.c
This file contains two different implementations of the bitonic sort
recursive version : recBitonicSort()
imperative version : impBitonicSort()
The bitonic sort is also known as Batcher Sort.
For a reference of the algorithm, see the article titled
Sorting networks and their applications by K. E. Batcher in 1968
The following codes take references to the codes avaiable at
http://www.cag.lcs.mit.edu/streamit/results/bitonic/code/c/bitonic.c
http://www.tools-of-computing.com/tc/CS/Sorts/bitonic_sort.htm
http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/bitonic/bitonicen.htm
*/
/*
------- ----------------------
Nikos Pitsianis, Duke CS
-----------------------------
*/
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <time.h>
#include <pthread.h>
typedef enum { false, true } bool;
struct timeval startwtime, endwtime;
double seq_time;
int threadsNum; //number of threads
int N; // data array size
int *a; // data array to be sorted
unsigned randSeed; //seed array initialisation
bool sortPass; //flag showing whether the test passed or not
const int ASCENDING = 1;
const int DESCENDING = 0;
const int REC_BITONIC_MERGE_PARALLEL_GRAINSIZE = 1 << 14;
const int REC_BITONIC_MERGE_PARALLEL_COMPARE_MIN = (1 << 12) - 1;
const int REC_BITONIC_MERGE_PARALLEL_CALL_MIN = (1 << 8) - 1;
const int REC_BITONIC_SORT_PARALLEL_MIN = (1 << 22) + 1;
typedef struct impBitonicSortThreadData{
int i;
int N;
int j;
int k;
} impBitonicSortThreadData;
void getArgs(int argc, char** argv);
void init(void);
void print(void);
void sort(void);
void test(void);
void qSortTest(void);
void exchange(int i, int j);
void compare(int i, int j, int dir);
void *impBitonicSortThread(void * threadArgs);
void impBitonicSort(void);
int qSortAscendingCompFuncWithTest (const void * a, const void * b);
int qSortAscending (const void * a, const void * b);
int qSortDescending (const void * a, const void * b);
/** the main program **/
int main(int argc, char **argv) {
getArgs(argc, argv);
a = (int *) malloc(N * sizeof(int));
randSeed = (unsigned) time(NULL);
//Sorts using the qSort algorithm
init();
gettimeofday (&startwtime, NULL);
qsort(a, N, sizeof(int), qSortAscending);
gettimeofday (&endwtime, NULL);
seq_time = (double)((endwtime.tv_usec - startwtime.tv_usec)/1.0e6
+ endwtime.tv_sec - startwtime.tv_sec);
printf("qSort wall clock time = %f\n\n", seq_time);
//Sorts using the imperative bitonic algorithm
init();
gettimeofday (&startwtime, NULL);
impBitonicSort();
gettimeofday (&endwtime, NULL);
seq_time = (double)((endwtime.tv_usec - startwtime.tv_usec)/1.0e6
+ endwtime.tv_sec - startwtime.tv_sec);
printf("Imperative wall clock time = %f\n", seq_time);
test();
qSortTest();
free(a);
}
/** -------------- SUB-PROCEDURES ----------------- **/
void getArgs(int argc, char** argv){
if (argc != 3) {
printf("Usage: %s p q\nwhere:\n\tP=2^p is the the number of threads(power of two)\n\tN=2^q is problem size (power of two)\n",
argv[0]);
exit(1);
}
threadsNum = 1<<atoi(argv[1]);
N = 1<<atoi(argv[2]);
}
/** procedure test() : verify sort results **/
void test() {
int pass = 1;
int i;
for (i = 1; i < N; i++) {
pass &= (a[i-1] <= a[i]);
}
printf("\tTEST\t\t%s\n",(pass) ? "PASSed" : "FAILed");
}
/** procedure qSortTest() : verify sort results using qsort method **/
void qSortTest(){
sortPass = true;
qsort(a, N, sizeof(int), qSortAscendingCompFuncWithTest);
printf("\tQSORT TEST\t%s\n",(sortPass) ? "PASSed" : "FAILed");
}
/** procedure init() : initialize array "a" with data **/
void init() {
srand(randSeed);
int i;
for (i = 0; i < N; i++) {
a[i] = rand() % N; // (N - i);
}
}
/** procedure print() : print array elements **/
void print() {
int i;
for (i = 0; i < N; i++) {
printf("%d\n", a[i]);
}
printf("\n");
}
/** INLINE procedure exchange() : pair swap **/
inline void exchange(int i, int j) {
int t;
t = a[i];
a[i] = a[j];
a[j] = t;
}
/** procedure compare()
The parameter dir indicates the sorting direction, ASCENDING
or DESCENDING; if (a[i] > a[j]) agrees with the direction,
then a[i] and a[j] are interchanged.
**/
inline void compare(int i, int j, int dir) {
if (dir==(a[i]>a[j]))
exchange(i,j);
}
void *impBitonicSortThread(void * threadArgs){
impBitonicSortThreadData *thisThreadData = (impBitonicSortThreadData *) threadArgs;
int i;
int N = thisThreadData->N;
int j = thisThreadData->j;
int k = thisThreadData->k;
for (i; i<N; i++) {
int ij=i^j;
if ((ij)>i) {
if ((i&k)==0 && a[i] > a[ij])
exchange(i,ij);
if ((i&k)!=0 && a[i] < a[ij])
exchange(i,ij);
}
}
pthread_exit(NULL);
}
/*
imperative version of bitonic sort
*/
void impBitonicSort() {
int t,j,k;
impBitonicSortThreadData impBitonicSortThreadDataArray[threadsNum];
pthread_t threads[threadsNum];
pthread_attr_t attr;
pthread_attr_init(&attr);
pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE);
int threadN = N/threadsNum;
for (k=2; k<=N; k+=k) {
for (j=k>>1; j>0; j=j>>1) {
for (t = 0; t < threadsNum; ++t){
impBitonicSortThreadDataArray[t].i = t * threadN;
impBitonicSortThreadDataArray[t].N = (t + 1) * threadN;
impBitonicSortThreadDataArray[t].j = j;
impBitonicSortThreadDataArray[t].k = k;
int rc = pthread_create(&threads[t], &attr, impBitonicSortThread, (void *) &impBitonicSortThreadDataArray[t]);
if (rc){
printf("ERROR; return code from pthread_create() is %d\n", rc);
exit(-1);
}
}
void *status;
for(t = 0; t < threadsNum; ++t) {
int rc = pthread_join(threads[t], &status);
if (rc) {
printf("ERROR; return code from pthread_join() is %d\n", rc);
exit(-1);
}
}
}
}
pthread_attr_destroy(&attr);
}
/** function used by qsort for comparing as well as testing **/
int qSortAscendingCompFuncWithTest (const void * a, const void * b) {
int result = ( *(int*)a - *(int*)b );
if (result > 0){
sortPass = false;
}
return result;
}
/** function used by qsort for comparing **/
int qSortAscending (const void * a, const void * b) {
return ( *(int*)a - *(int*)b );
}
/** function used by qsort for comparing **/
int qSortDescending (const void * a, const void * b) {
return ( *(int*)b - *(int*)a );
}