Guest User

Untitled

a guest
Oct 17th, 2019
103
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