Page 1 of 1

### parallelizing levenshtein distance with openmp

Posted: 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 4int 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;}`

Cheers,
bobi.

### Re: parallelizing levenshtein distance with openmp

Posted: 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.

### Re: parallelizing levenshtein distance with openmp

Posted: 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 4int 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?

Cheers,
bobi.

### Re: parallelizing levenshtein distance with openmp

Posted: 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.

### Re: parallelizing levenshtein distance with openmp

Posted: Thu May 30, 2013 4:44 am

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 4int 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.

### Re: parallelizing levenshtein distance with openmp

Posted: 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