Parallel tiled Nussinov RNA folding loop nest generated using both dependence graph transitive closure and loop...

Area of Science:

• Bioinformatics
• Computational Biology
• High-Performance Computing

Background:

• RNA secondary structure prediction is crucial for bioinformatics but computationally intensive.
• Traditional methods like Nussinov's algorithm use affine loops, suitable for polyhedral models.
• Existing polyhedral compilation techniques are suboptimal for dynamic programming in RNA structure prediction.

Purpose of the Study:

• To present a novel approach for generating a parallel, tiled Nussinov RNA loop nest.
• To enhance performance through improved code locality and parallelization.
• To demonstrate the effectiveness of the new technique compared to existing methods.

Main Methods:

• Applied automatic loop nest tiling to all three loops of the Nussinov algorithm.
• Corrected initial rectangular tiles using the transitive closure of a dependence graph.
• Utilized loop skewing to generate parallel code from the tiled loop nest.

Main Results:

• The novel approach generates a parallel tiled Nussinov RNA loop nest.
• Achieved significant performance gains due to enhanced code locality and parallelization.
• The generated code is considerably faster than related codes with only partially tiled loops.

Conclusions:

• The technique is implemented in the TRACO compiler and tested on Intel processors.
• Demonstrated substantial speed-up factors for Nussinov RNA parallel code.
• The proposed method offers a considerable performance improvement for RNA folding computations.