我是 OpenMP 的新手,正在尝试并行化 Jarvis 的算法。然而事实证明,与顺序代码相比,并行程序花费的时间要长 2-3 倍。
难道问题本身就不能并行化吗?或者我并行化它的方式有问题。
这是我针对该问题的 openMP 程序,其中有 2 个部分是并行的:
#include <stdio.h>
#include <sys/time.h>
#include <omp.h>
typedef struct Point
{
int x, y;
} Point;
// To find orientation of ordered triplet (p, q, r).
// The function returns
// 0 for colinear points
// 1 as Clockwise
// 2 as Counterclockwise
int orientation(Point p, Point i, Point q)
{
int val = (i.y - p.y) * (q.x - i.x) -
(i.x - p.x) * (q.y - i.y);
if (val == 0) return 0; // colinear
return (val > 0)? 1: 2; // clock or counterclock wise
}
// Prints convex hull of a set of n points.
void convexHull(Point points[], int n)
{
// There must be at least 3 points
if (n < 3) return;
// Initialize array to store results
Point results[n];
int count = 0;
// Find the leftmost point
int l = 0,i;
#pragma omg parallel shared (n,l) private (i)
{
#pragma omp for
for (i = 1; i < n; i++)
{
#pragma omp critical
{
if (points[i].x < points[l].x)
l = i;
}
}
}
// Start from leftmost point, keep moving counterclockwise
// until reach the start point again.
int p = l, q;
do
{
// Add current point to result
results[count]= points[p];
count++;
q = (p+1)%n;
int k;
#pragma omp parallel shared (p) private (k)
{
#pragma omp for
for (k = 0; k < n; k++)
{
// If i is more counterclockwise than current q, then
// update i as new q
#pragma omp critical
{
if (orientation(points[p], points[k], points[q]) == 2)
q = k;
}
}
}
// Now q is the most counterclockwise with respect to p
// Set p as q for next iteration, to add q to result
p = q;
} while (p != l); // While algorithm does not return to first point
// Print Result
int j;
for (j = 0; j < count; j++){
printf("(%d,%d)\n", results[j].x,results[j].y);
}
}
int main()
{
//declaration for start time, end time
//and total executions for the algorithm
struct timeval start, end;
int i, num_run = 100;
gettimeofday(&start,NULL);
Point points[] = {{0, 3}, {2, 2}, {1, 1}, {2, 1},
{3, 0}, {0, 0}, {3, 3}};
int n = sizeof(points)/sizeof(points[0]);
convexHull(points, n);
gettimeofday(&end,NULL);
int cpu_time_used = (((end.tv_sec - start.tv_sec) * 1000000) + (end.tv_usec
- start.tv_usec));
printf("\n\nExecution time: %d ms\n", cpu_time_used);
return 0;
}
尝试通过添加以下代码行来使输入足够丰富:
Point points[3000];
int i;
for(i=0;i<3000;i++) {
points[i].x = rand()%100;
points[i].y = rand()%100;
int j;
for(j=i+1;j<3000;j++) {
if(points[i].x==points[j].x) {
if(points[i].y==points[j].y) {
i--;
break;
}
}
}
}
但有时会崩溃