## parallelizing levenshtein distance with openmp

General OpenMP discussion

### parallelizing levenshtein distance with openmp

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

Thank you in advance!

Cheers,
bobi.
bobi

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

### Re: parallelizing levenshtein distance with openmp

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: 674
Joined: Thu Jan 08, 2009 10:12 am
Location: EPCC, University of Edinburgh

### Re: parallelizing levenshtein distance with openmp

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?

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

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: 674
Joined: Thu Jan 08, 2009 10:12 am
Location: EPCC, University of Edinburgh

### Re: parallelizing levenshtein distance with openmp

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 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.
bobi

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

### Re: parallelizing levenshtein distance with openmp

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: 674
Joined: Thu Jan 08, 2009 10:12 am
Location: EPCC, University of Edinburgh

Return to Using OpenMP

### Who is online

Users browsing this forum: Yahoo [Bot] and 7 guests