Locality and parallelism optimization for dynamic programming algorithm in bioinformatics

Guangming Tan, Shengzhong Feng, Ninghui Sun
Key Laboratory of Computer System and Architecture, Institute of Computing Technology, Chinese Academy of Sciences
In SC ’06: Proceedings of the 2006 ACM/IEEE conference on Supercomputing (2006), 78


   title={Locality and parallelism optimization for dynamic programming algorithm in bioinformatics},

   author={Tan, G. and Feng, S. and Sun, N.},

   booktitle={Proceedings of the 2006 ACM/IEEE conference on Supercomputing},






Download Download (PDF)   View View   Source Source   



Dynamic programming has been one of the most efficient approaches to sequence analysis and structure prediction in biology. However, their performance is limited due to the drastic increase in both the number of biological data and variety of the computer architectures. With regard to such predicament, this paper creates excellent algorithms aimed at addressing the challenges of improving memory efficiency and network latency tolerance for nonserial polyadic dynamic programming where the dependences are nonuniform. By relaxing the nonuniform dependences, we proposed a new cache oblivious scheme to enhance its performance on memory hierarchy architectures. Moreover we develop and extend a tiling technique to parallelize this nonserial polyadic dynamic programming using an alternate block-cyclic mapping strategy for balancing the computational and memory load, where an analytical parameterized model is formulated to determine the tile volume size that minimizes the total execution time and an algorithmic transformation is used to schedule the tile to overlap communication with computation to further minimize communication overhead on parallel architectures. The numerical experiments were carried out on several high performance computer systems. The new cache-oblivious dynamic programming algorithm achieve 2-10 speedup and the parallel tiling algorithm with communication-computation overlapping shows a desired potential for fine-grained parallel computing on massively parallel computer systems.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: