Guest User

Untitled

a guest
Nov 21st, 2018
105
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.26 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <sys/time.h>
  3. #include <omp.h>
  4.  
  5. typedef struct Point
  6. {
  7. int x, y;
  8. } Point;
  9.  
  10. // To find orientation of ordered triplet (p, q, r).
  11. // The function returns
  12. // 0 for colinear points
  13. // 1 as Clockwise
  14. // 2 as Counterclockwise
  15. int orientation(Point p, Point i, Point q)
  16. {
  17. int val = (i.y - p.y) * (q.x - i.x) -
  18. (i.x - p.x) * (q.y - i.y);
  19. if (val == 0) return 0; // colinear
  20. return (val > 0)? 1: 2; // clock or counterclock wise
  21. }
  22.  
  23. // Prints convex hull of a set of n points.
  24. void convexHull(Point points[], int n)
  25. {
  26. // There must be at least 3 points
  27. if (n < 3) return;
  28.  
  29. // Initialize array to store results
  30. Point results[n];
  31. int count = 0;
  32.  
  33. // Find the leftmost point
  34. int l = 0,i;
  35.  
  36. #pragma omg parallel shared (n,l) private (i)
  37. {
  38. #pragma omp for
  39. for (i = 1; i < n; i++)
  40. {
  41. #pragma omp critical
  42. {
  43. if (points[i].x < points[l].x)
  44. l = i;
  45. }
  46. }
  47.  
  48. }
  49.  
  50. // Start from leftmost point, keep moving counterclockwise
  51. // until reach the start point again.
  52. int p = l, q;
  53. do
  54. {
  55. // Add current point to result
  56. results[count]= points[p];
  57. count++;
  58.  
  59. q = (p+1)%n;
  60. int k;
  61.  
  62. #pragma omp parallel shared (p) private (k)
  63. {
  64. #pragma omp for
  65. for (k = 0; k < n; k++)
  66. {
  67. // If i is more counterclockwise than current q, then
  68. // update i as new q
  69. #pragma omp critical
  70. {
  71. if (orientation(points[p], points[k], points[q]) == 2)
  72. q = k;
  73. }
  74. }
  75.  
  76. }
  77.  
  78. // Now q is the most counterclockwise with respect to p
  79. // Set p as q for next iteration, to add q to result
  80. p = q;
  81.  
  82.  
  83. } while (p != l); // While algorithm does not return to first point
  84.  
  85. // Print Result
  86. int j;
  87. for (j = 0; j < count; j++){
  88. printf("(%d,%d)n", results[j].x,results[j].y);
  89. }
  90.  
  91. }
  92.  
  93. int main()
  94. {
  95. //declaration for start time, end time
  96. //and total executions for the algorithm
  97. struct timeval start, end;
  98. int i, num_run = 100;
  99.  
  100. gettimeofday(&start,NULL);
  101.  
  102. Point points[] = {{0, 3}, {2, 2}, {1, 1}, {2, 1},
  103. {3, 0}, {0, 0}, {3, 3}};
  104.  
  105. int n = sizeof(points)/sizeof(points[0]);
  106.  
  107. convexHull(points, n);
  108.  
  109. gettimeofday(&end,NULL);
  110.  
  111. int cpu_time_used = (((end.tv_sec - start.tv_sec) * 1000000) + (end.tv_usec
  112. - start.tv_usec));
  113. printf("nnExecution time: %d msn", cpu_time_used);
  114. return 0;
  115. }
  116.  
  117. int l = 0,i;
  118. #pragma omp parallel shared (n,l) private (i)
  119. {
  120. #pragma omp for
  121. for (i = 1; i < n; i++)
  122. {
  123. #pragma omp critical
  124. {
  125. if (points[i].x < points[l].x)
  126. l = i;
  127. }
  128. }
  129. }
  130.  
  131. int l = 0,i;
  132. #pragma omp parallel shared (n,l) private (i)
  133. {
  134. int l_local = 0; //This variable is private to the thread
  135.  
  136. #pragma omp for nowait
  137. for (i = 1; i < n; i++)
  138. {
  139. // This part of the code can be executed in parallel
  140. // since all write operations are on thread-local variables
  141. if (points[i].x < points[l_local].x)
  142. l_local = i;
  143. }
  144.  
  145. // The critical section is entered only once by each thread
  146. #pragma omp critical
  147. {
  148. if (points[l_local].x < points[l].x)
  149. l = l_local;
  150. }
  151.  
  152. #pragma omp barrier
  153. // a barrier is needed in case some more code follow
  154. // otherwise there is an implicit barrier at the end of the parallel region
  155. }
Add Comment
Please, Sign In to add comment