Posted By

kylewu on 04/27/11


Tagged

pthread


Versions (?)

qsort pthread


 / Published in: C
 

  1. #define NUM_THREADS 8
  2.  
  3. #define FRAND frand(1, 100)
  4. #define frand(xmin, xmax) ( (double)xmin + (double)(xmax-xmin) * rand()/(double)RAND_MAX)
  5.  
  6. void serial(double*, int, int);
  7. int partition(double*, int, int, int);
  8. void swap(double*, double *);
  9.  
  10. void parallel(double*, int, int);
  11. void* parallel_thread(void *);
  12.  
  13. void print(double*, int);
  14. int check(double*, double*, int);
  15. int sorted(double*, int);
  16.  
  17. int timer();
  18.  
  19. struct thread_data {
  20. double *array;
  21. int left;
  22. int right;
  23. int current_depth;
  24. int depth;
  25. } ;
  26.  
  27. int main(int argc, const char *argv[])
  28. {
  29.  
  30. int n;
  31. int num_threads;
  32. double* arrayA;
  33. double* arrayB;
  34.  
  35. int serial_time;
  36. int parallel_time;
  37.  
  38. int i;
  39. if (argc != 3) {
  40. printf("Please support an argument nn quick n, where n is the size of matrixn");
  41. return 1;
  42. }
  43.  
  44. n = atoi(argv[1]);
  45. num_threads = atoi(argv[2]);
  46.  
  47. arrayA = (double*) malloc(n * sizeof(double));
  48. arrayB = (double*) malloc(n * sizeof(double));
  49. for (i = 0; i < n; i++) {
  50. arrayA[i] = FRAND;
  51. arrayB[i] = arrayA[i];
  52. }
  53. //printf("Array :n");
  54. //print(arrayA, n);
  55.  
  56. serial_time = timer();
  57. serial(arrayA, 0, n-1);
  58. serial_time = timer() - serial_time;
  59.  
  60. printf("Serial time : %f n", serial_time/1000000.0);
  61.  
  62. parallel_time = timer();
  63. parallel(arrayB, n, num_threads);
  64. parallel_time = timer() - parallel_time;
  65.  
  66. printf("Parallel time : %f n", parallel_time/1000000.0);
  67.  
  68. /*
  69. if (sorted(arrayA, n) != 1)
  70. {
  71. printf("A Not sortedn");
  72. return 1;
  73. }
  74. if (sorted(arrayB, n) != 1)
  75. {
  76. printf("B Not sortedn");
  77. return 1;
  78. }
  79. */
  80.  
  81. if (check(arrayA, arrayB, n) != 1)
  82. {
  83. printf("Different Result Errorn");
  84. return 1;
  85. }
  86.  
  87. //printf("Result A:n");
  88. //print(arrayA, n);
  89. //print(arrayB, n);
  90.  
  91. return 0;
  92. }
  93.  
  94. int partition(double *A, int left, int right, int pivotIndex)
  95. {
  96. int i,storeIndex;
  97. double pivotValue = *(A+pivotIndex);
  98. swap(A+pivotIndex,A+right);
  99. storeIndex = left;
  100. for(i=left;i
  101. {
  102. if(*(A+i) <= pivotValue)
  103. {
  104. swap(A+i,A+storeIndex);
  105. storeIndex++;
  106. }
  107. }
  108. swap(A+storeIndex,A+right);
  109. return storeIndex;
  110. }
  111.  
  112. void serial(double *A,int left,int right)
  113. {
  114. int pivotIndex,pivotNewIndex;
  115. if(right > left)
  116. {
  117. pivotIndex = left + (right - left)/2;
  118. pivotNewIndex = partition(A,left,right,pivotIndex);
  119. serial(A,left,pivotNewIndex - 1);
  120. serial(A,pivotNewIndex + 1,right);
  121. }
  122. }
  123.  
  124. void parallel(double* A, int n, int num)
  125. {
  126. struct thread_data thread_data;
  127. pthread_t thread;
  128. void* status;
  129. thread_data.array = A;
  130. thread_data.left = 0;
  131. thread_data.right = n-1;
  132. thread_data.current_depth = 0;
  133. thread_data.depth = log2(num);
  134.  
  135. parallel_thread((void*)&thread_data);
  136. }
  137.  
  138. void* parallel_thread(void *data)
  139. {
  140. int i;
  141. double time;
  142.  
  143. // Get data
  144. struct thread_data *my_data = (struct thread_data*)data;
  145. double* array = my_data->array;
  146. int left = my_data->left;
  147. int right = my_data->right;
  148. int depth = my_data->depth;
  149. int current_depth = my_data->current_depth;
  150.  
  151. // pthread attribute
  152. pthread_attr_t attr;
  153. pthread_attr_init(&attr);
  154. pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE);
  155.  
  156. // threads array
  157. pthread_t *threads = (pthread_t*) malloc( (depth - current_depth) * sizeof(pthread_t) );
  158. struct thread_data *thread_data_array = (struct thread_data*) malloc ((depth - current_depth) * sizeof(struct thread_data) );
  159. void* status;
  160.  
  161. // variables for partition
  162. int l,r;
  163. double pivot;
  164. double temp;
  165. int pivotIndex;
  166.  
  167. for (i = 0; i < depth - current_depth; i++) {
  168.  
  169. // partition
  170. pivotIndex = left + (right-left)/2;
  171.  
  172. l = left;
  173. r = right;
  174. pivot = array[pivotIndex];
  175.  
  176. time = timer();
  177. while (l <= r) {
  178. while (*(array + l) < pivot)
  179. l++;
  180. while (*(array + r) > pivot)
  181. r--;
  182. if (l <= r) {
  183. temp = array[l];
  184. array[l] = array[r];
  185. array[r] = temp;
  186. l++;
  187. r--;
  188. }
  189. };
  190.  
  191. // construct thread data
  192. thread_data_array[i].array = array;
  193. thread_data_array[i].left = l;
  194. thread_data_array[i].right = right;
  195. thread_data_array[i].depth = depth;
  196. thread_data_array[i].current_depth = current_depth + i + 1;
  197.  
  198. //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);
  199. pthread_create(&threads[i], &attr, parallel_thread, (void *)&thread_data_array[i]);
  200.  
  201. // update local variable
  202. right = r;
  203. }
  204.  
  205. //time = timer();
  206. serial(array, left, right);
  207. //printf("%d begin serial sort left %d right %dnTime : %lfn", current_depth, left, right, (timer()-time) / 10e6);
  208.  
  209. for (i = 0; i < depth - current_depth; i++) {
  210. pthread_join(threads[i], &status);
  211. }
  212.  
  213. }
  214.  
  215. int timer(void)
  216. {
  217. struct timeval tv;
  218. gettimeofday(&tv, (struct timezone*)0);
  219. return (tv.tv_sec*1000000+tv.tv_usec);
  220. }
  221.  
  222. void swap(double *A, double *B)
  223. {
  224. double temp;
  225. temp = *A;
  226. *A = *B;
  227. *B = temp;
  228. return;
  229. }
  230.  
  231. void print(double* A, int n)
  232. {
  233. int i;
  234. for (i = 0; i < n; i++) {
  235. printf("%lf ", A[i]);
  236. }
  237. printf("n");
  238. }
  239.  
  240. int check(double* A, double* B, int n)
  241. {
  242. int i;
  243. for (i = 0; i < n; i++) {
  244. if(A[i] - B[i] > 10e-6){
  245. printf("n%d %lf %lfn",i, A[i], B[i]);
  246. return 0;
  247. }
  248. }
  249. return 1;
  250. }
  251.  
  252. int sorted(double *A, int n)
  253. {
  254. int i;
  255. for (i = 0; i < n-1; i++) {
  256. if(A[i] - A[i+1] > 10e-6) return 0;
  257. }
  258. return 1;
  259. }

Report this snippet  

You need to login to post a comment.