Jerry Lacmou Zeutouo

Dynamic programming is a technique widely used to solve several combinatory optimization problems. A well-known example is the minimum cost parenthesizing problem (MPP), which is usually used to represent a class of non-serial polyadic dynamic-programming problems. These problems are characterized by a strong dependency between subproblems. This paper outlines a coarse-grained multicomputer parallel solution using the four-splitting technique to solve the MPP. It is a partitioning technique consisting of subdividing the dependency graph into subgraphs (or blocks) of variable size and splitting large-size blocks into four subblocks to avoid communication overhead caused by a similar partitioning technique in the literature. Our solution consists in evaluating a block by computing and communicating each subblock of this block to reduce the latency time of processors which accounts for most of the global communication time. It requires O(n^3/p) execution time with O(k * \sqrt{p}) communication rounds. n is the input data size, p is the number of processors, and k is the number of times the size of blocks is subdivided.

To enable extensive research on the ribonucleic acid (RNA) molecule, predicting its spatial structure stands as a much-valued research field. In this regard, Nussinov and Jacobson published the (now) de facto solution to predict the halfway secondary structure, which runs in cubic time for an n -nucleotide sequence. We design our contribution starting from two of the several works conducted to improve this running time. First, those of Frid and Gusfield, which associate a speedup named sparsification with an on-demand Four-Russians paradigm to achieve the fastest theoretical solution known to date. And second, those of Palkowski and Bielecki, which efficiently restructure the classical Nussinov loop nest with a novel tiling technique. Alongside other loop transformations, this paper shows that, owing to loop restructuring promoting cache reuse and variable-grained parallelism, applying the latter approach to the Frid and Gusfield doubly sped-up loop nest yields outperforming improvements both in sequential and in parallel. In fact, following empirical evaluation, we have obtained relatively to Palkowski's sequential basis, speedups up to x3.26 sequentially and up to x28.50 on 32 threads of a multicore processor with a 30,000-nucleotide sequence. Furthermore, the massive parallel environment in graphics cards has led this speedup factor to reach x44.37.

Summary: This article presents a fast sequential algorithm for the matrix chain ordering problem. Our solution is based on Yao's sequential algorithm that solves this problem in time by reducing the total number of distinct subproblems to be performed. We solve them fastly by avoiding some unnecessary computations. Our strategy consists in organizing the evaluation of the subproblems according to their dependencies instead of their precedence order as in the previous solutions. In many cases, our solution runs in time. An experimental study is conducted to benchmark the performance of our algorithm by measuring the average of the results obtained on five random data sets. This shows that our algorithm is 18.93 faster than Yao's sequential algorithm and 5.07 faster than the previous best CGM‐based parallel solutions on 32 processors.