Optimizing RNA-RNA Interaction Computations

RNA-RNA (Ribo-Nucleic Acid) Interactions (RRI) has led to significant successes in Cancer treatment. However, programs that model these interactions are computationally and memory intensive: for sequences of lengths N and M, space is Theta(N-2 M-2), and the time is Theta(N-3 M-3). Conducting genomewide RNA-RNA interactions can take forever. Therefore, there is a need to speed up these computations. On examining two RRI applications (piRNA and IRIS), we find that the dominant computations fit the polyhedral model, a widely accepted tool for loop nest optimization. Applying existing automatic polyhedral tools on this whole application is near to impossible. Hence, we analyzed a surrogate kernel that captures the main dependence pattern found in piRNA and IRIS. But even on this kernel, a state-of-the-art automatic polyhedral, Pluto does not significantly improve the performance of the baseline implementation. Whereas, with simple manual loop permutation and skewing techniques, we were able to achieve an average of 17x (sequential) and 112x (parallel on a 6-core Intel Broadwell processor) speed-up over the baseline. This performance represents 75% (respectively, 88%) of attainable single-core and multi-core L1 bandwidth. Preliminary results from tiling show that there is a room for two-three fold improvement when the data foot-print required to compute the inner three loop dimensions fit in the main memory.