{'fraction_non_alphanumeric': 0.023540489642184557, 'fraction_numerical': 0.0018832391713747645, 'mean_word_length': 5.746031746031746, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
High-performance recursive dynamic programming for bioinformatics using MM-like flexible kernels

Dynamic Programming (DP) provides optimal solutions to a problem by combining optimal solutions to many overlapping subproblems. DP algorithms exploit this overlapping property to explore otherwise exponential-sized problem spaces in polynomial time, making them central to many important applications spanning from logistics to computational biology. In this paper, we present a general strategy of obtaining highly efficient parallel DP implementations using recursive cache-oblivious divide and conquer technique which turns inflexible kernels into flexible ones (kernels that read from and write to disjoint sub-matrices). We solve four non-trivial DP problems widely used in Bioinformatics, namely the parenthesis problem, Floyd-Warshall's all-pairs shortest paths, gap problem and protein accordion folding using recursive cache-oblivious technique that decompose the original inflexible looping kernel to highly optimizable flexible kernels. To the best of our knowledge no such recursive parallel DP algorithms were known for the protein folding and gap problems. The algorithms are hybrid in the same way as most high-performance matrix multiplication algorithms are recursive with iterative base cases. We show that the base cases of these recursive divide-and-conquer algorithms are predominantly matrix-multiplication-like (MM-like) flexible that expose many optimization opportunities not offered by the traditional looping DP codes. Moreover, the most costly/dominating kernel for these problems are often flexible. As a result, one can obtain highly efficient DP implementations by simply optimizing these kernels. We present a few generic optimization steps that suffices to optimize these DP implementations. Our implementations achieve 5--100x speedup over their standard loop based DP counterparts on modern multicore machines. We also present results on manycores (Xeon Phi) and clusters of multicores obtained by simple extensions for SIMD and shared-distributed-shared-memory architectures, respectively.