Optimization of an RNA folding algorithm for parallel architectures

In this paper we describe parallel implementations of a dynamic programming algorithm for predicting ribonucleic acid (RNA) secondary structure based on energy minimization in high performance computers. The computations of the energies for all possible fragments of the molecule consume almost all the computations in the prediction algorithm. The computation ordering and the data placement dictate the performance of the algorithm. Only the diagonal ordering, which starts with short fragments and progresses to successively greater fragments in length, out of three possible computation orderings can take full advantage of the advanced architectures discussed in this study. We have implemented two methods on a GRAY Y-MP. Our results demonstrate that the method with less bank conflict performs better in a single-processor environment. However, the other method utilizes the processors more efficiently in the multiple-processor environment of GRAY Y-MP. An efficient parallel algorithm has also been designed solely for a distributed-memory SIMD architecture. In a distributed memory system, the performance is also affected by the cost of communication between processors. The algorithm significantly reduces the data communication cost. Consequently, our results show that the performance on our MasPar MP-2 system is far better than that on a single-processor GRAY Y-MP as the problem size grows. Our algorithm has been applied to a SMP MIMD architecture (eight-processor GRAY Y-MP) and may be adapted to a distributed MIMD architecture. The methodology described in this study may possibly be applied to other optimization problems using a dynamic programming algorithm. (C) 1998 Elsevier Science B.V. All rights reserved.