Answers are grounded in this paper and cite their sources.
RNA-RNA interactions (RRIs) are essential in many biological processes, including gene transcription, translation, and localization. They play a critical role in diseases such as cancer and Alzheimer's. Algorithms to model RRI typically use dynamic programming and have the complexity <tex-math notation="LaTeX">Θ (N³~M³)</tex-math> in time and <tex-math notation="LaTeX">Θ (N²~M²)</tex-math> in space where <tex-math notation="LaTeX">N</tex-math> and <tex-math notation="LaTeX">M</tex-math> are the lengths of the two RNA sequences. This makes it both essential and challenging to parallelize them. Previous efforts to do so have been hand-optimized, which is prone to human error and costly to develop and maintain. This paper presents a multi-core CPU parallelization of BPMax, one of the simpler RRI algorithms, generated by a user-guided polyhedral code generation tool, ALPHAZ.. The user starts with a mathematical specification of the dynamic programming algorithm and provides the choice of polyhedral program transformations such as schedules, memory-maps, and multi-level tiling. ALPHAZ. automatically generates highly optimized code. At the lowest level, we implemented a small hand-optimized register-tiled "matrix max-plus" kernel and integrated it with our tool-generated optimized code. Our final optimized program version is about <tex-math notation="LaTeX">400×</tex-math> faster than the base program, translating to around 312 GFLOPS, more than half of our platform's Roofline Machine Peak (RMP) performance. On a single core, we attain 80% of RMP. The main kernel in the algorithm, whose complexity is <tex-math notation="LaTeX">Θ (N³~M³)</tex-math> , attains 58 GFLOPS on a single-core and 344 GFLOPS on multi-core (90% and 58% of RMP, respectively).
No takes yet. Share an insight, caveat, or question.
Mondal et al. (2024) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: