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: | 10.1109/TPDS.2011.218 | Schools: | School of Computer Engineering | Fulltext Permission: | none | Fulltext Availability: | No Fulltext |
Appears in Collections: | SCSE Journal Articles |
SCOPUSTM
Citations
20
23
Updated on Mar 27, 2024
Web of ScienceTM
Citations
20
16
Updated on Oct 25, 2023
Page view(s) 10
846
Updated on Mar 29, 2024
Google ScholarTM
Check
Altmetric
Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.