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 (N^{3} \, M^{3})$in time and$\Theta (N^{2} \, M^{2})$in space where$N$and$M$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.AlphaZautomatically 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\times$faster than the base program, translating to around 312 GFLOPS, more than half of our platform'sRoofline Machine Peak(RMP) performance. On a single core, we attain 80% ofRMP. The main kernel in the algorithm, whose complexity is$\Theta (N^{3} \, M^{3})$, attains 58 GFLOPS on a single-core and 344 GFLOPS on multi-core (90% and 58% ofRMP, respectively).