NPRG042 Programming in Parallel Environment

Assignment 3

Design and implement a parallel algorithm for computing Levenshtein's Edit Distance using OpenMP.

Your solution must use a framework, which is also available 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, and you must 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 the -debug argument, the debugging version of the class is used. You may use it to print debugging information, but make sure that the regular (non-debug) version does not print anything to stdout.

Your solution will be tested on different datasets from those provided to you. However, the evaluation data will use the same string lengths as the testing data. We recommend designing your performance-optimized solution to assume that the string lengths are divisible by 1,024 (but note that the debugging data are much smaller). Also, note that ReCodEx does not test the largest dataset (10-1M) because it takes too long to evaluate.