Distributed and parallel dynamic programming algorithms modelled on cP systems

Abstract

We discuss a membrane computing prototype for a simple but typical bottom-up dynamic programming algorithm: finding the longest common subsequence (LCS) of two strings. Conceptually, this problem can be solved by systematically considering all possible subproblems and organising their partial results in a 2D matrix. Large problems can be solved by partitioning this matrix (grid) into blocks, which can be distributed among existing processors. The system evolves by diagonal wavefronts: the blocks are activated by a high-level diagonal wavefront and each active block is swept over by its own diagonal wavefront. We base our work on cP, a slightly revised version of our earlier P systems with complex symbols. We propose a composite prototype of two layers with similar data flows: (i) a message based distributed macro model, and (ii) a shared memory parallel micro model. We discuss the tradeoffs and we conjecture that the same approach can be used to model more complex related algorithms. The asynchronous versions of these prototypes can be efficiently mapped to a distributed Actor system, such as Akka.