Ατζέντα εργαστηρίου Παράλληλου Προγραμματισμού 18/5/2021

README.md

Ατζέντα εργαστηρίου Παράλληλου Προγραμματισμού 18/5/2021

Στο gist αυτό θα αναρτηθούν λύσεις και υποδείξεις κατά τη διεξαγωγή του εργαστηρίου.

S10-fib-notasks.c

// compile with: gcc -O2 -Wall fib-notasks.c -o fib-notasks

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


#define N 13


int fibonacci(int n) {
int i,j;

  printf("Computing fib(%d)\n",n);
  
  if (n<2) return n;

  i = fibonacci(n-1);
  
  j = fibonacci(n-2);
  
  return i+j;
}


int main() {
int fib;

  fib = fibonacci(N);
  
  printf("fib(%d)= %d\n",N,fib);
  
  return 0;
}

S20-fib-tasks.c

// compile with: gcc -fopenmp -O2 -Wall fib-tasks.c -o fib-tasks

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

#include <omp.h>

#define N 13


int fibonacci(int n) {
int i,j;

  printf("Thread %d computing fib(%d)\n",omp_get_thread_num(),n);

  if (n<2) return n;

  #pragma omp task shared(i)	// shared(i) NEEDED HERE, else firstprivate(i) by default
  {
    i = fibonacci(n-1);
  }
  
  #pragma omp task shared(j)	// shared(j) NEEDED HERE, else firstprivate(j) by default
  {
    j = fibonacci(n-2);
  }
  
  #pragma omp taskwait
  
  return i+j;
}


int main() {
int fib;

  #pragma omp parallel
  {
    #pragma omp single nowait
    {
      fib = fibonacci(N);
    }  // no need for a barrier here
  }
  
  printf("fib(%d)= %d\n",N,fib);
  
  return 0;
}

S30-quicksort-simple.c

// Simple (non-threaded) quicksort implementation
// compile with e.g. gcc -O2 -Wall quicksort-simple.c -o quicksort-simple -DN=10000000

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


#define CUTOFF 10

void inssort(double *a,int n) {
int i,j;
double t;
  
  for (i=1;i<n;i++) {
    j = i;
    while ((j>0) && (a[j-1]>a[j])) {
      t = a[j-1];  a[j-1] = a[j];  a[j] = t;
      j--;
    }
  }

}


int partition(double *a,int n) {
int first,last,middle;
double t,p;
int i,j;

  // take first, last and middle positions
  first = 0;
  middle = n/2;
  last = n-1;  
  
  // put median-of-3 in the middle
  if (a[middle]<a[first]) { t = a[middle]; a[middle] = a[first]; a[first] = t; }
  if (a[last]<a[middle]) { t = a[last]; a[last] = a[middle]; a[middle] = t; }
  if (a[middle]<a[first]) { t = a[middle]; a[middle] = a[first]; a[first] = t; }
    
  // partition (first and last are already in correct half)
  p = a[middle]; // pivot
  for (i=1,j=n-2;;i++,j--) {
    while (a[i]<p) i++;
    while (p<a[j]) j--;
    if (i>=j) break;

    t = a[i]; a[i] = a[j]; a[j] = t;      
  }
  
  // return position of pivot
  return i;
}


void quicksort(double *a,int n) {
int i;
  // check if below cutoff limit
  if (n<=CUTOFF) {
    inssort(a,n);
    return;
  }
  
  // partition into two halves
  i = partition(a,n);
   
  // recursively sort halves
  quicksort(a,i);
  quicksort(a+i,n-i);
  
}


int main() {
double *a;
int i;
 
  a = (double *)malloc(N*sizeof(double));
  if (a==NULL) {
    printf("error in malloc\n");
    exit(1);
  }

  // fill array with random numbers
  srand(0);
  for (i=0;i<N;i++) {
    a[i] = (double)rand()/RAND_MAX;
  }

  // sort array
  quicksort(a,N);

  // check sorting
  for (i=0;i<(N-1);i++) {
    if (a[i]>a[i+1]) {
      printf("Sort failed!\n");
      break;
    }
  }  

  free(a);
  
  return 0;
}

S40.c

// code base for various sorting algorithms
// compile with e.g. gcc -fopenmp -O2 -Wall quicksort-tasks.c -o quicksort-tasks -DN=1000000


#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#include <omp.h>

// NOTE: threaded code performance is favored by greater CUTOFF values (e.g. 1000 instead of 10)
#define CUTOFF 1000

void inssort(double *a,int n) {
int i,j;
double t;
  
  for (i=1;i<n;i++) {
    j = i;
    while ((j>0) && (a[j-1]>a[j])) {
      t = a[j-1];  a[j-1] = a[j];  a[j] = t;
      j--;
    }
  }

}


int partition(double *a,int n) {
int first,last,middle;
double t,p;
int i,j;

  // take first, last and middle positions
  first = 0;
  middle = n/2;
  last = n-1;  
  
  // put median-of-3 in the middle
  if (a[middle]<a[first]) { t = a[middle]; a[middle] = a[first]; a[first] = t; }
  if (a[last]<a[middle]) { t = a[last]; a[last] = a[middle]; a[middle] = t; }
  if (a[middle]<a[first]) { t = a[middle]; a[middle] = a[first]; a[first] = t; }
    
  // partition (first and last are already in correct half)
  p = a[middle]; // pivot
  for (i=1,j=n-2;;i++,j--) {
    while (a[i]<p) i++;
    while (p<a[j]) j--;
    if (i>=j) break;

    t = a[i]; a[i] = a[j]; a[j] = t;      
  }
  
  // return position of pivot
  return i;
}


void quicksort(double *a,int n) {
int i;

  // debug only
  //printf("Thread %d sorting array of %d elements\n",omp_get_thread_num(),n);

  // check if below cutoff limit
  if (n<=CUTOFF) {
    inssort(a,n);
    return;
  }
  
  // partition into two halves
  i = partition(a,n);
   
  // recursively sort halves
  
  #pragma omp task	
  {
    quicksort(a,i);
  }
  
  #pragma omp task	
  {
    quicksort(a+i,n-i);
  }
  
  // no need for #pragma omp taskwait
  
}


int main() {
double *a;
int i;
 
  a = (double *)malloc(N*sizeof(double));
  if (a==NULL) {
    printf("error in malloc\n");
    exit(1);
  }

  // fill array with random numbers
  srand(0);
  for (i=0;i<N;i++) {
    a[i] = (double)rand()/RAND_MAX;
  }

  // sort array
  #pragma omp parallel
  {
    #pragma omp single nowait
    {
      quicksort(a,N);
    }
  }
  
  // check sorting
  for (i=0;i<(N-1);i++) {
    if (a[i]>a[i+1]) {
      printf("Sort failed!\n");
      break;
    }
  }  

  free(a);
  
  return 0;
}