SHARE
TWEET

Untitled

a guest Oct 17th, 2019 101 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <pthread.h>
  4. #include <math.h>
  5.  
  6. int NReps;
  7. int printLevel;
  8. int N;
  9. int* v;
  10. int *vQSort;
  11. int *vNew;
  12. pthread_barrier_t barrier;
  13. int P = 4;
  14.  
  15. void merge(int source[], int start, int mid, int end, int destination[]) {
  16.     // DO NOT MODIFY
  17.     int iA = start;
  18.     int iB = mid;
  19.     int i;
  20.  
  21.     for (i = start; i < end; i++)
  22.     {
  23.         if (end == iB || (iA < mid && source[iA] <= source[iB])) {
  24.             destination[i] = source[iA];
  25.             iA++;
  26.         } else {
  27.             destination[i] = source[iB];
  28.             iB++;
  29.         }
  30.     }
  31. }
  32.  
  33. void compareVectors(int * a, int * b) {
  34.     // DO NOT MODIFY
  35.     int i;
  36.     for(i = 0; i < N; i++) {
  37.         if(a[i]!=b[i]) {
  38.             printf("Sorted incorrectly\n");
  39.             return;
  40.         }
  41.     }
  42.     printf("Sorted correctly\n");
  43. }
  44.  
  45. void displayVector(int * v) {
  46.     // DO NOT MODIFY
  47.     int i;
  48.     int displayWidth = 2 + log10(v[N-1]);
  49.     for(i = 0; i < N; i++) {
  50.         printf("%*i", displayWidth, v[i]);
  51.         if(!((i+1) % 20))
  52.             printf("\n");
  53.     }
  54.     printf("\n");
  55. }
  56.  
  57. int cmp(const void *a, const void *b) {
  58.     // DO NOT MODIFY
  59.     int A = *(int*)a;
  60.     int B = *(int*)b;
  61.     return A-B;
  62. }
  63.  
  64. void getArgs(int argc, char **argv)
  65. {
  66.     if(argc < 4) {
  67.         printf("Not enough paramters: ./program N NReps printLevel\nprintLevel: 0=no, 1=some, 2=verbouse\n");
  68.         exit(1);
  69.     }
  70.     N = atoi(argv[1]);
  71.     NReps = atoi(argv[2]);
  72.     printLevel = atoi(argv[3]);
  73. }
  74.  
  75. void init()
  76. {
  77.     int i;
  78.     v = malloc(sizeof(int) * N);
  79.     vQSort = malloc(sizeof(int) * N);
  80.     vNew = malloc(sizeof(int) * N);
  81.     if(v == NULL) {
  82.         printf("malloc failed!");
  83.         exit(1);
  84.     }
  85.  
  86.     // generate the vector v with random values
  87.     // DO NOT MODIFY
  88.     srand(42);
  89.     for(i = 0; i < N; i++)
  90.         v[i] = rand()%N;
  91. }
  92.  
  93. void printPartial()
  94. {
  95.     compareVectors(v, vQSort);
  96. }
  97.  
  98. void printAll()
  99. {
  100.     displayVector(v);
  101.     displayVector(vQSort);
  102.     compareVectors(v, vQSort);
  103. }
  104.  
  105. void print()
  106. {
  107.     if(printLevel == 0)
  108.         return;
  109.     else if(printLevel == 1)
  110.         printPartial();
  111.     else
  112.         printAll();
  113. }
  114.  
  115. void* threadFunction(void *var)
  116. {
  117.     int thread_id = *(int*)var;
  118.     int nrELem = 2;
  119.     int start = thread_id  * N/P;
  120.     int end = start + nrELem;
  121.     int i;
  122.  
  123.     int width, *aux;
  124.     for (width = start + 1; width < end; width = 2 * width) {
  125.         pthread_barrier_wait(&barrier);
  126.         for (i = start; i < end; i = i + 2 * width) {
  127.             merge(v, i, i + width, i + 2 * width, vNew);
  128.            
  129.         }
  130.         pthread_barrier_wait(&barrier);
  131.         if(thread_id == 0){
  132.             aux = v;
  133.             v = vNew;
  134.             vNew = aux;
  135.         }
  136.         pthread_barrier_wait(&barrier);
  137.         nrELem = nrELem * 2;
  138.         pthread_barrier_wait(&barrier);
  139.        
  140.     }
  141.  
  142. }
  143.  
  144. int main(int argc, char *argv[])
  145. {
  146.     int i, j;
  147.     getArgs(argc, argv);
  148.     init();
  149.  
  150.     pthread_t tid[P];
  151.     int thread_id[P];
  152.  
  153.     // make copy to check it against qsort
  154.     // DO NOT MODIFY
  155.     for(i = 0; i < N; i++)
  156.         vQSort[i] = v[i];
  157.     qsort(vQSort, N, sizeof(int), cmp);
  158.  
  159.     for(i = 0;i < P; i++)
  160.         thread_id[i] = i;
  161.  
  162.     for(i = 0; i < P; i++) {
  163.         pthread_create(&(tid[i]), NULL, threadFunction, &(thread_id[i]));
  164.     }
  165.  
  166.     for(i = 0; i < P; i++) {
  167.         pthread_join(tid[i], NULL);
  168.     }
  169.  
  170.     // int width, *aux;
  171.     // for (width = 1; width < N; width = 2 * width) {
  172.     //  for (i = 0; i < N; i = i + 2 * width) {
  173.     //      merge(v, i, i + width, i + 2 * width, vNew);
  174.     //  }
  175.     //  aux = v;
  176.     //  v = vNew;
  177.     //  vNew = aux;
  178.     // }
  179.  
  180.     print();
  181.  
  182.     return 0;
  183. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top