Logo PTI Logo FedCSIS

Communication Papers of the 18th Conference on Computer Science and Intelligence Systems

Annals of Computer Science and Information Systems, Volume 37

Polyhedral Tiling Strategies for the Zuker Algorithm Optimization

, , ,

DOI: http://dx.doi.org/10.15439/2023F7645

Citation: Communication Papers of the 18th Conference on Computer Science and Intelligence Systems, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 37, pages 37–41 ()

Full text

Abstract. In this paper, we focus on optimizing the code for computing the Zuker RNA folding algorithm. This bioinformatics task belongs to the class of non-serial polyadic dynamic programming, which involves non-uniform program loop dependencies. However, its dependence pattern can be represented using affine formulas, allowing us to automatically employ tiling strategies based on the polyhedral method. We use three source-to-source compilers Pluto, Traco, and Dapt based on affine transformations, transitive closure of dependence relation graph and space-time tiling, respectively, to automatically generate cache-efficient codes. We evaluate the speed-up and scalability of optimized codes and check their performance applying two multi-core machines. We also discuss related approaches and outline future work in the conclusion of the paper.

References

  1. T. Smith and M. Waterman, “Identification of common molecular subsequences,” Journal of Molecular Biology, vol. 147, no. 1, pp. 195 – 197, 1981.
  2. R. Nussinov et al., “Algorithms for loop matchings,” SIAM Journal on Applied mathematics, vol. 35, no. 1, pp. 68–82, 1978.
  3. M. Zuker and P. Stiegler, “Optimal computer folding of large rna sequences using thermodynamics and auxiliary information.” Nucleic Acids Research, vol. 9, no. 1, pp. 133–148, 1981.
  4. G. Lei, Y. Dou, W. Wan, F. Xia, R. Li, M. Ma, and D. Zou, “CPU-GPU hybrid accelerating the zuker algorithm for RNA secondary structure prediction applications,” BMC Genomics, vol. 13, no. Suppl 1, p. S14, 2012. http://dx.doi.org/10.1186/1471-2164-13-s1-s14
  5. J. Xue, Loop Tiling for Parallelism. Norwell, MA, USA: Kluwer Academic Publishers, 2000. ISBN 0-7923-7933-0
  6. S. Verdoolaege, “Integer set library - manual,” Tech. Rep., 2011. [Online]. Available: www.kotnet.org/~skimo//isl/manual.pdf,
  7. R. T. Mullapudi and U. Bondhugula, “Tiling for dynamic scheduling,” in Proceedings of the 4th International Workshop on Polyhedral Compilation Techniques, Vienna, Austria, Jan. 2014.
  8. M. Palkowski and W. Bielecki, “Parallel tiled Nussinov RNA folding loop nest generated using both dependence graph transitive closure and loop skewing,” BMC Bioinformatics, vol. 18, no. 1, p. 290, 2017. http://dx.doi.org/10.1186/s12859-017-1707-8
  9. Z. J. Lu, J. W. Gloor, and D. H. Mathews, “Improved RNA secondary structure prediction by maximizing expected pair accuracy,” RNA, vol. 15, no. 10, pp. 1805–1813, Aug. 2009. http://dx.doi.org/10.1261/rna.1643609. [Online]. Available: https://doi.org/10.1261/rna.1643609
  10. J. S. McCaskill, “The equilibrium partition function and base pair binding probabilities for RNA secondary structure,” Biopolymers, vol. 29, no. 6-7, pp. 1105–1119, may 1990. http://dx.doi.org/10.1002/bip.360290621
  11. M. Palkowski and W. Bielecki, “NPDP benchmark suite for loop tiling effectiveness evaluation,” in Parallel Processing and Applied Mathematics. Springer International Publishing, 2023, pp. 51–62. [Online]. Available: https://doi.org/10.1007/978-3-031-30445-3 5
  12. T. Malas, G. Hager, H. Ltaief, H. Stengel, G. Wellein, and D. Keyes, “Multicore-optimized wavefront diamond blocking for optimizing stencil updates,” SIAM Journal on Scientific Computing, vol. 37, no. 4, pp. C439–C464, Jan. 2015. http://dx.doi.org/10.1137/140991133. [Online]. Available: https://doi.org/10.1137/140991133
  13. U. Bondhugula, V. Bandishti, and I. Pananilath, “Diamond tiling: Tiling techniques to maximize parallelism for stencil computations,” IEEE Transactions on Parallel and Distributed Systems, vol. 28, no. 5, pp. 1285–1298, May 2017. http://dx.doi.org/10.1109/tpds.2016.2615094
  14. J. Li, S. Ranka, and S. Sahni, “Multicore and GPU algorithms for Nussinov RNA folding,” BMC Bioinformatics, vol. 15, no. 8, p. S1, 2014. http://dx.doi.org/10.1186/1471-2105-15-S8-S1. [Online]. Available: http://dx.doi.org/10.1186/1471-2105-15-S8-S1
  15. M. Palkowski and W. Bielecki, “Parallel tiled cache and energy efficient code for zuker’s RNA folding,” in Parallel Processing and Applied Mathematics. Springer International Publishing, 2020, pp. 25–34.
  16. C. Zhao and S. Sahni, “Efficient RNA folding using zuker's method,” in 2017 IEEE 7th International Conference on Computational Advances in Bio and Medical Sciences (ICCABS). IEEE, oct 2017. http://dx.doi.org/10.1109/iccabs.2017.8114309
  17. D. Wonnacott, T. Jin, and A. Lake, “Automatic tiling of “mostly-tileable” loop nests,” in 5th International Workshop on Polyhedral Compilation Techniques, Amsterdam, 2015.
  18. M. Palkowski and W. Bielecki, “Parallel cache-efficient code for computing the McCaskill partition functions,” vol. 18, pp. 207–210, 2019. http://dx.doi.org/10.15439/2019F8
  19. Y. Frid and D. Gusfield, “An improved Four-Russians method and sparsified Four-Russians algorithm for RNA folding,” Algorithms for Molecular Biology, vol. 11, no. 1, aug 2016. http://dx.doi.org/10.1186/s13015-016-0081-9
  20. V. K. Tchendji, F. I. K. Youmbi, C. T. Djamegni, and J. L. Zeutouo, “A parallel tiled and sparsified Four-Russians algorithm for Nussinov's RNA folding,” IEEE/ACM Transactions on Computational Biology and Bioinformatics, pp. 1–12, 2022. http://dx.doi.org/10.1109/tcbb.2022.3216826
  21. M. Palkowski and W. Bielecki, “Tiling Nussinov’s RNA folding loop nest with a space-time approach,” BMC Bioinformatics, vol. 20, no. 1, apr 2019. http://dx.doi.org/10.1186/s12859-019-2785-6
  22. W. Bielecki, M. Palkowski, and M. Poliwoda, “Automatic code optimization for computing the McCaskill partition functions,” in Annals of Computer Science and Information Systems. IEEE, sep 2022. http://dx.doi.org/10.15439/2022f4
  23. U. Bondhugula et al., “A practical automatic polyhedral parallelizer and locality optimizer,” SIGPLAN Not., vol. 43, no. 6, pp. 101–113, Jun. 2008. [Online]. Available: http://pluto-compiler.sourceforge.net
  24. OpenMP Architecture Review Board, “OpenMP application program interface version 5.2,” 2022. [Online]. Available: https://www.openmp.org/specifications/