Параллельное вычисление LCS с использованием диагонального подхода - PullRequest
Новая
       63

Параллельное вычисление LCS с использованием диагонального подхода

0 голосов
/ 18 июня 2020

Я пытаюсь рассчитать длину LCS с помощью OpenMP. Я взял по нему доклад конференции и начал выполнять алгоритм. Если честно, я не очень подробно разбирался в том, как работает алгоритм, но понимал, что он пытался вычислить значения по диагонали параллельно. Код, который я написал, следующий: 

#include <omp.h>
#include <stdio.h>

#define MAX(a,b) ((a) > (b) ? (a) : (b))
#define MIN(a,b) ((a) < (b) ? (a) : (b))

static long num_steps = 100000;
double step;

void main(){

    int m,n;
    printf("Enter m: ");
    scanf("%d", &m);
    char X[m];
    printf("Enter X: ");
    scanf("%s", X);

    printf("Enter n: ");
    scanf("%d", &n);
    char Y[n];
    printf("Enter Y: ");
    scanf("%s", Y);

    int C[m+1][n+1];

    #pragma omp parallel for
    for(int i=0; i<=m; i++)
    {
        C[i][0] = 0;
    }

    #pragma omp parallel for
    for(int j=0; j<=n; j++)
    {
        C[0][j] = 0;
    }


    for(int a = 0; a<m; a++){
        printf("\n");
        for(int b=0;b<n;b++){
            printf("%d ", C[a][b]);
        }
    }
    printf("\n-------------\n");


    int i,j,diag;

    #pragma omp parallel default(none) shared(X,Y,C,m,n) private(i,j,diag) //num_threads(8)
    {
        for(diag = 2; diag<=m+n; diag++) {
            #pragma omp parallel for
            for(i=MIN(m, diag-1); i<=MAX(1, diag-1); i--){
                j = diag - 1;
                if(X[i-1]==Y[j-1]) {
                    C[i][j] = C[i-1][j-1] + 1;
                }
                else {
                    C[i][j] = MAX(C[i-1][j], C[i][j-1]);
                }
            }
        }
    }

    for(int a = 0; a<m; a++){
        printf("\n");
        for(int b=0;b<n;b++){
            printf("%d ", C[a][b]);
        }
    }

Вы можете сказать мне, что здесь не так? Я также хотел бы узнать о хорошем ресурсе, чтобы понять этот алгоритм, потому что статья, которую я выбрал, не очень хорошо объясняет.

...