Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/100238
Title: EasyPDP: an efficient parallel dynamic programming runtime system for computational biology
Authors: Tang, Shanjiang
Yu, Ce
Sun, Jizhou
Lee, Bu-Sung
Zhang, Tao
Xu, Zhen
Wu, Huabei
Keywords: DRNTU::Engineering::Computer science and engineering::Theory of computation::Analysis of algorithms and problem complexity
Issue Date: 2012
Source: Tang, S. J., Yu, C., Sun, J. Z., Lee, B. S., Zhang, T., Xu, Z., & Wu, H. B. (2012). EasyPDP: an efficient parallel dynamic programming runtime system for computational biology. IEEE transactions on parallel and distributed systems, 23(5), 862-872.
Series/Report no.: IEEE transactions on parallel and distributed systems
Abstract: Dynamic programming (DP) is a popular and efficient technique in many scientific applications such as computational biology. Nevertheless, its performance is limited due to the burgeoning volume of scientific data, and parallelism is necessary and crucial to keep the computation time at acceptable levels. The intrinsically strong data dependency of dynamic programming makes it difficult and error-prone for the programmer to write a correct and efficient parallel program. Therefore, this paper builds a runtime system named EasyPDP aiming at parallelizing dynamic programming algorithms on multicore and multiprocessor platforms. Under the concept of software reusability and complexity reduction of parallel programming, a DAG Data Driven Model is proposed, which supports those applications with a strong data interdependence relationship. Based on the model, EasyPDP runtime system is designed and implemented. It automatically handles thread creation, dynamic data task allocation and scheduling, data partitioning, and fault tolerance. Five frequently used DAG patterns from biological dynamic programming algorithms have been put into the DAG pattern library of EasyPDP, so that the programmer can choose to use any of them according to his/her specific application. Besides, an ideal computing distribution model is proposed to discuss the optimal values for the performance tuning arguments of EasyPDP. We evaluate the performance potential and fault tolerance feature of EasyPDP in multicore system. We also compare EasyPDP with other methods such as Block-Cycle Wavefront (BCW). The experimental results illustrate that EasyPDP system is fine and provides an efficient infrastructure for dynamic programming algorithms.
URI: https://hdl.handle.net/10356/100238
http://hdl.handle.net/10220/16509
DOI: http://dx.doi.org/10.1109/TPDS.2011.218
Fulltext Permission: none
Fulltext Availability: No Fulltext
Appears in Collections:SCSE Journal Articles

Google ScholarTM

Check

Altmetric

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.