| Levenshtein's edit distance | |
| OpenMP | |
| Assigned: | 2.4.2024 |
| Deadline: | 15.4.2024 23:59 (CEST) |
| Supervisor: | Martin Kruliš |
| ReCodEx: | assignment |
| speedup | points |
|---|---|
| 2× or less | 0 |
| 2× to 6× | 1 |
| 6× to 12× | 2 |
| 12× to 20× | 3 |
| 20× or more | 4 |
Design and implement a parallel algorithm for computing Levenshtein's Edit Distance using the OpenMP technology.
Your solution must use a framework, which is available for you at /home/_teaching/para/03-levenshtein (including the testing data, data generator, and serial implementation). Your solution is expected to modify only the implementation.hpp file of the framework while you have to preserve the name of the implementation class (EditDistance). The modified file implementation.hpp is also the only file you are expected to submit in ReCodEx. If you need to create additional headers (*.hpp), submit them as well, but do not create any subdirectories.
Use the attached Makefiles for compilation. When debugging, the EditDistance class has a bool template parameter DEBUG. When the program is called with -debug argument, the debugging version of the class is used. You may use it to print out debugging information, but make sure that the regular (non-debug) version is not printing anything to the stdout.
Your solution will be tested on different datasets than you are provided. However, the evaluation data will use the same string lengths as the testing data. We recommend designing your performance-optimized solution to expect that the string lengths are divisible by 1,024 (but note that debugging data are much smaller). Also, note that ReCodEx does not test the largest dataset (10-1M) since it takes too long to evaluate.