EasyPDP: An Efficient Parallel Dynamic Programming Runtime System for Computational Biology
EasyPDP: An Efficient Parallel Dynamic Programming Runtime System for Computational Biology
复制标题
EasyPDP：计算生物学的高效并行动态编程运行时系统
DOI：
10.1109/tpds.2011.218
复制
发表时间：
2012-05-01
影响因子：
5.3
通讯作者：
Wu, Huabei
中科院分区：
文献类型：
--
作者：
Tang, Shanjiang;Yu, Ce;Wu, Huabei
动态规划（DP）是一种流行的和有效的技术在许多科学应用，如计算生物学。然而，由于科学数据量的激增，其性能受到限制，并行性对于将计算时间保持在可接受的水平是必要的和关键的。动态程序设计固有的强数据依赖性使得程序员很难写出正确高效的并行程序。因此，本文构建了一个运行时系统EasyPDP，旨在多核多处理器平台上并行化动态规划算法。在软件复用和降低并行编程复杂度的思想下，提出了一种DAG数据驱动模型，该模型支持具有强数据依赖关系的应用。基于该模型，设计并实现了EasyPDP运行时系统。它自动处理线程创建、动态数据任务分配和调度、数据分区和容错。EasyPDP的DAG模式库中包含了生物动态规划算法中常用的5种DAG模式，程序员可以根据自己的具体应用选择使用其中的任意一种模式。此外，提出了一个理想的计算分布模型，讨论了EasyPDP的性能调整参数的最佳值。我们评估了EasyPDP在多核系统中的性能潜力和容错功能。我们还比较了EasyPDP与其他方法，如块周期波前（BCW）。实验结果表明，EasyPDP系统性能良好，为动态规划算法提供了一个有效的基础设施。
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.