Research And Implementation Of Applications Oriented System With Dag Data Dependence

Dynamic programming is a popular and efficient technology in many scientific applications such as computational biology. However, its performance is limited due to the burgeoning volume of scientific data, and parallelism is necessary and crucial to keep the computational time at acceptable levels. Moreover, 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 it is crucial and necessary to develop a tool or framework to simplify the parallel programming.The paper, under the concept of software reusability and complexity reduction of parallel programming, first proposes a DAG data driven model, and then builds a runtime system named EasyPDP based on this model aiming at parallelizing dynamic programming algorithms on multi-core and multi-processor platforms. By adopting the EasyPDP system, the user only needs to focus his attention on the specific application rather than on the detailed implementation of parallel program, which is done by EasyPDP itself. It automatically handles thread creation, dynamic data task allocation and scheduling, data partitioning, and fault tolerance.To begin with, the paper presents a DAG data driven model. It consists of three modules: Parallel application module, DAG pattern module and DAG runtime system module. A detailed introduction and analysis is given from the value and purpose aspects of programming model.Secondly, a comprehensive introduction and classification for Dynamic programming is clarified and explained as well as the research background of its parallelization. Particularly, we summarize and implement five frequently used DAG pattern in the EasyPDP so that user could easily choose to use it accordingly.Finally, a detailed description and analysis for the EasyPDP runtime system is given. Specifically, we discuss it thoroughly from the target of EasyPDP, system modules, system data flow, fault tolerance mechanism and performance arguments. Afterwards, a performance evaluation of EasyPDP is analyzed and discussed. We firstly propose a performance analysis model to discuss the relationships among the arguments. Then the empirical discussions are made from the experimental respect with regard to the performance arguments, EasyPDP overhead and its cache miss, comparison with static methods such as BCW and fault tolerance of EasyPDP.