Программа OpenMP C работает медленнее, чем последовательный код - PullRequest
Новая
       7

Программа OpenMP C работает медленнее, чем последовательный код

0 голосов
/ 21 ноября 2018

Я новичок в OpenMP, пытаюсь распараллелить алгоритм Джарвиса.Однако оказывается, что параллельная программа занимает в 2-3 раза больше времени, чем последовательный код.

Неужели сама проблема не может быть распараллелена?Или что-то не так в том, как я распараллеливаю это.

Это моя openMP-программа для решения проблемы, с параллелизацией двух частей: 

#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;
            }
        }
    }
}

Но иногда происходит сбой

1 Ответ

0 голосов
/ 21 ноября 2018

В следующем фрагменте вашего кода все содержимое параллельного цикла for заключено в оператор critical.Это означает, что эта часть кода никогда не будет введена более чем одним потоком за раз.Работа нескольких потоков по одному не будет проходить быстрее, чем если бы один поток прошел все итерации.Но вдобавок к этому некоторое время затрачивается на накладные расходы на синхронизацию (каждый поток должен получить мьютекс перед входом в критическую секцию и впоследствии освободить его). 

int l = 0,i;
#pragma omp 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;
        }
    }
}

Для параллелизации последовательный код необходимо несколько реорганизовать.Сокращение часто является хорошим подходом для простых операций: пусть каждый поток вычисляет частичный результат на одной части итераций (например, частичный минимум, частичная сумма), а затем объединяет все результаты в глобальный.Для поддерживаемых операций можно использовать синтаксис #pragma omp for reduction(op:var).Но в этом случае сокращение должно быть сделано вручную.

Посмотрите, как в следующем коде используются локальные переменные для отслеживания индекса минимума x, а затем используется один критический раздел для вычисления глобального минимального индекса. 

int l = 0,i;
#pragma omp parallel shared (n,l) private (i)
{
    int l_local = 0; //This variable is private to the thread

    #pragma omp for nowait
    for (i = 1; i < n; i++)
    {
        // This part of the code can be executed in parallel
        // since all write operations are on thread-local variables
        if (points[i].x < points[l_local].x)
            l_local = i;
    }

    // The critical section is entered only once by each thread
    #pragma omp critical
    {
    if (points[l_local].x < points[l].x)
        l = l_local;
    }

    #pragma omp barrier
    // a barrier is needed in case some more code follow
    // otherwise there is an implicit barrier at the end of the parallel region
}

Тот же принцип должен быть применен ко второму параллельному циклу, который страдает от той же самой проблемы фактической полной сериализации оператором critical.

...