Cache and energy efficient algorithms for Nussinov’s RNA Folding
Cache and energy efficient algorithms for Nussinov’s RNA Folding
复制标题
Nussinov RNA 折叠的缓存和节能算法
作者：
Chunchun Zhao;S. Sahni
RNA折叠/RNA二级结构预测算法通过最大化互补碱基对的数量和最小化能量来确定非嵌套/无假结结构。 Nussinov 的经典 RNA 折叠算法的几种实现已经被提出。我们的重点是通过减少缓存未命中次数来获得运行时间和能源效率。为 Nussinov 的 RNA 折叠开发了三种高效缓存算法：ByRow、ByRowSegment 和 ByBox。使用简单的 LRU 缓存模型，我们表明 Nussinov 的经典算法具有最高的缓存未命中次数，其次是 Transpose（Li 等人）、ByRow、ByRowSegment 和 ByBox 算法（按此顺序）。使用两种编程语言（C 和 Java）在四种计算平台（Xeon E5、AMD Athlon 64 X2、Intel I7 和 PowerPC A2）上进行的大量实验表明，我们的高速缓存高效算法在运行时间和能耗方面也很高效。我们的基准测试表明，根据计算平台和编程语言，ByRow 或 ByBox 均可提供最佳的运行时间和能源性能。与 Classical 相比，这些算法的 C 版本可减少多达 97.2% 的运行时间和多达 88.8% 的能耗，与 Transpose 相比可减少多达 56.3% 和 57.8% 的能耗。 Java 版本相对于 Classical 减少了多达 98.3% 的运行时间，相对于 Transpose 减少了多达 75.2% 的运行时间。 Transpose 以牺牲内存为代价来实现运行时间和能源效率，因为它需要的内存是 Classical 所需内存的两倍。 ByRow、ByRowSegment、ByBox 所需内存与 Classical 相同。因此，使用相同数量的内存，我们提出的算法可以解决比 Transpose 解决的问题大 40% 的问题。
An RNA folding/RNA secondary structure prediction algorithm determines the non-nested/pseudoknot-free structure by maximizing the number of complementary base pairs and minimizing the energy. Several implementations of Nussinov’s classical RNA folding algorithm have been proposed. Our focus is to obtain run time and energy efficiency by reducing the number of cache misses. Three cache-efficient algorithms, ByRow, ByRowSegment and ByBox, for Nussinov’s RNA folding are developed. Using a simple LRU cache model, we show that the Classical algorithm of Nussinov has the highest number of cache misses followed by the algorithms Transpose (Li et al.), ByRow, ByRowSegment, and ByBox (in this order). Extensive experiments conducted on four computational platforms–Xeon E5, AMD Athlon 64 X2, Intel I7 and PowerPC A2–using two programming languages–C and Java–show that our cache efficient algorithms are also efficient in terms of run time and energy. Our benchmarking shows that, depending on the computational platform and programming language, either ByRow or ByBox give best run time and energy performance. The C version of these algorithms reduce run time by as much as 97.2% and energy consumption by as much as 88.8% relative to Classical and by as much as 56.3% and 57.8% relative to Transpose. The Java versions reduce run time by as much as 98.3% relative to Classical and by as much as 75.2% relative to Transpose. Transpose achieves run time and energy efficiency at the expense of memory as it takes twice the memory required by Classical. The memory required by ByRow, ByRowSegment, and ByBox is the same as that of Classical. As a result, using the same amount of memory, the algorithms proposed by us can solve problems up to 40% larger than those solvable by Transpose.