Taking RNA-RNA Interaction to Machine Peak

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 Theta((NM3)-M-3)in time and Theta((NM2)-M-2)in space where N and M are the lengths of the twoRNAsequences.Thismakesitbothessentialandchallengingtopar-allelize 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 BP Max, one of the simpler RRI algorithms, generated by a user-guided polyhedral code generation tool, Alpha Z. 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. Alpha Z 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 400 x 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 Theta((NM3)-M-3), attains58 GFLOPS on a single-core and 344 GFLOPS on multi-core (90%and 58% of RMP, respectively).