parallelizing levenshtein distance with openmp

General OpenMP discussion

parallelizing levenshtein distance with openmp

Postby bobi » Sat May 18, 2013 11:14 am

Hi folks,

I'm just trying to parallelize the calculation of Levenshtein distance with OpenMP, but the results are always changing. It seems that there is a concurrence issue, since the code works well sequentially. Unfortunately, I couldn't figure it out, so maybe you can help me. Here is the code:

Code: Select all
#include <omp.h>
#include <stdio.h>
#include <string.h>

#define MIN(x,y,z) (((x < y) ? x : y) < z ? ((x < y) ? x : y) : z)
#define NP 4

int main(int argc, char** argv) {
   
   if(argc != 3) return -1;
   
   char* word1 = argv[1];
   char* word2 = argv[2];
   int i, j, cost;
   double start, end, time;
   
    if(strcmp(word1, word2) == 0) {
      printf("Distance: 0\n");
      return 0;
   }
   
    if (strlen(word1) == 0) {
      printf("Distance: %zd\n", strlen(word2));
      return 0;
   }
   
    if (strlen(word2) == 0) {
      printf("Distance: %zd\n", strlen(word1));
      return 0;
   }

   int v0[strlen(word2) + 1];
   int v1[strlen(word2) + 1];

   omp_set_num_threads(4);
   
   start = omp_get_wtime();
   int max = sizeof(v0)/sizeof(v0[0]);

   #pragma omp parallel for
   for (i = 0; i < max; i++)
        v0[i] = i;

   #pragma omp parallel for private(j)
   for (i = 0; i < strlen(word1); i++)
    {
        v1[0] = i + 1;
      
        for (j = 0; j < strlen(word2); j++)
        {
            cost = (word1[i] == word2[j]) ? 0 : 1;
            v1[j + 1] = MIN(v1[j] + 1, v0[j + 1] + 1, v0[j] + cost);
        }

        for (j = 0; j < max; j++) {
            v0[j] = v1[j];
        }
   }

   end = omp_get_wtime();
   time = end - start;

   printf("Distance: %d\nTime: %f\n", v1[strlen(word2)], time);

   return 0;
}


Thank you in advance!

Cheers,
bobi.
bobi
 
Posts: 3
Joined: Sat May 18, 2013 10:56 am

Re: parallelizing levenshtein distance with openmp

Postby MarkB » Mon May 20, 2013 2:26 am

Hi there,

You have race conditions on the shared variables cost, v0 and v1. The race on cost can be fixed by making it private, but I see no straightforward way of fixing the others in the code as written. Parallelising this algorithm is non-trivial: the best advice I can give you is to go and search the literature on this.

Hope that helps,
Mark.
MarkB
 
Posts: 422
Joined: Thu Jan 08, 2009 10:12 am

Re: parallelizing levenshtein distance with openmp

Postby bobi » Sun May 26, 2013 12:46 am

Thanks, I got it working now, with the following code:

Code: Select all
#include <omp.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MIN(x,y,z) (((x < y) ? x : y) < z ? ((x < y) ? x : y) : z)
#define NP 4

int main(int argc, char** argv) {
   
   if(argc > 3) return -1;
   
   char* word1;
   char* word2;
   int i, j, cost;
   double start, end, time;
   FILE* f;
   size_t len = 0;

   if(argc == 3) {
      word1 = argv[1];
      word2 = argv[2];
   }
   else {
      return -1;
   }
   
       if(strcmp(word1, word2) == 0) {
      printf("Distance: 0\n");
      return 0;
   }
   
   if (strlen(word1) == 0) {
      printf("Distance: %zd\n", strlen(word2));
      return 0;
   }
   
   if (strlen(word2) == 0) {
      printf("Distance: %zd\n", strlen(word1));
      return 0;
   }

   int v0[strlen(word2) + 1];
   int v1[strlen(word2) + 1];

   omp_set_num_threads(4);
   
   start = omp_get_wtime();
   int max = sizeof(v0)/sizeof(v0[0]);

   #pragma omp parallel for
   for (i = 0; i < max; i++)
           v0[i] = i;

   #pragma omp parallel for private(cost) schedule(dynamic, 10)
   for (i = 0; i < strlen(word1); i++) {
           v1[0] = i + 1;
      
           for (j = 0; j < strlen(word2); j++) {
                  cost = (word1[i] == word2[j]) ? 0 : 1;
                  v1[j + 1] = MIN(v1[j] + 1, v0[j + 1] + 1, v0[j] + cost);
           }

           for (j = 0; j < max; j++) {
                  v0[j] = v1[j];
           }
   }

   end = omp_get_wtime();
   time = end - start;

   printf("Distance: %d\nTime: %f\n", v1[strlen(word2)], time);

   return 0;
}


But the remaining problem is, that there is no speedup if I run it on more than 1 processor. Is this an implementation problem? Or could you think of some other issue preventing the speedup?

Thank you in advance for your help!

Cheers,
bobi.
bobi
 
Posts: 3
Joined: Sat May 18, 2013 10:56 am

Re: parallelizing levenshtein distance with openmp

Postby MarkB » Mon May 27, 2013 1:58 am

I'm afraid it's not correct: different threads can simultaneously write to the same elements of v0 and v1.
This is also probably why you see no speedup: there will be a lot of contention for write-ownership of the cache lines
containing these arrays.
MarkB
 
Posts: 422
Joined: Thu Jan 08, 2009 10:12 am

Re: parallelizing levenshtein distance with openmp

Postby bobi » Thu May 30, 2013 4:44 am

What about this one? Is this correct or easier to protect if not?

Code: Select all
#include <omp.h>
#include <stdio.h>
#include <string.h>

#define MIN(x,y,z) (((x < y) ? x : y) < z ? ((x < y) ? x : y) : z)
#define NP 4

int main(int argc, char** argv) {
   
   char* word1 = argv[1];
   char* word2 = argv[2];
   int lm[strlen(word1)+1][strlen(word2)+1];
   int i, j;
   double start, end, time;
   if(argc != 3) return -1;
   
   if(strcmp(word1, word2) == 0) {
      printf("Distance: 0\n");
      return 0;
   }
   
   if (strlen(word1) == 0) {
      printf("Distance: %zd\n", strlen(word2));
      return 0;
   }
   
   if (strlen(word2) == 0) {
      printf("Distance: %zd\n", strlen(word1));
      return 0;
   }
   
   omp_set_num_threads(NP);
   
   start = omp_get_wtime();
   
   #pragma omp parallel for
   for(i = 0; i < strlen(word1)+1; i++) {
      for(j = 0; j < strlen(word2)+1; j++) {
            lm[i][j] = 0;
      }
   }
   
   #pragma omp parallel for
   for(i = 1; i < strlen(word1)+1; i++) {
      lm[i][0] = i;
   }
   
   #pragma omp parallel for
   for(j = 1; j < strlen(word2)+1; j++) {
      lm[0][j] = j;
   }
   
   int distance;
   
   #pragma omp parallel for private(lm)
   for(j = 1; j < strlen(word2)+1; j++) {
      for(i = 1; i < strlen(word1)+1; i++) {
      printf("Thread %d\n", omp_get_thread_num());
         if(word1[i-1] == word2[j-1]) {
            #pragma omp critical
            lm[i][j] = lm[i-1][j-1];
         }
         else {
            #pragma omp critical
            lm[i][j] = MIN(lm[i-1][j] + 1, lm[i][j-1] + 1, lm[i-1][j-1] + 1);
         }
         distance = lm[i][j];
      }
   }
   
   end = omp_get_wtime();
   time = end - start;
   
   for(i = 0; i < strlen(word1)+1; i++) {
      for(j = 0; j < strlen(word2)+1; j++) {
         printf("%d", lm[i][j]);
      }
      printf("\n");
   }
   
   printf("Distance: %d\nTime: %f\n", distance, time);
   return 0;
}


Would be really nice if you could help me, and thanks in advance!

Cheers,
bobi.
bobi
 
Posts: 3
Joined: Sat May 18, 2013 10:56 am

Re: parallelizing levenshtein distance with openmp

Postby MarkB » Thu May 30, 2013 6:09 am

That can't be right: there is a race condition on distance. Having lm private and protecting accesses to it with critical makes no sense. If it should be shared, then the critical regions will mean that you get no speedup from this.

I really don't believe you are going to get anywhere with this approach: you need a fundamental rethink of the algorithm to get an efficient parallel implementation. This paper might be a useful place to start: http://srg.cs.illinois.edu/srg/sites/de ... gnment.pdf
MarkB
 
Posts: 422
Joined: Thu Jan 08, 2009 10:12 am


Return to Using OpenMP

Who is online

Users browsing this forum: Exabot [Bot] and 14 guests