| Dynamic programming approach solves complex problems efficiently bybreaking them down into simpler subproblems, and is widely utilized in scientificcomputing. With the increasing data volume of scientific applications, time cost ofsolving problem doesn’t satisfied people any more. The development ofmulti-core/multi-processor hardware technologies provides platforms for scientificcomputing parallelization, which makes it possible to reduce the time cost,particularly in multilevel computing environment. Compared with other scientificproblem, the intrinsically strong data dependency of dynamic programming alsomakes it difficult and error-prone for the programmer to write a correct and efficientparallel program.This paper presents a multi-level hybrid parallel runtime system for dynamicprogramming parallelization named EasyHPS and studies the dynamic programmingparallelization in MPP environment. Based on the feature of dynamic programmingproblem, we conclude dynamic programming formulations and build up a DAG DataDriven Model based on dynamic programming formulation. EasyHPS system realizesa framework for dynamic programming parallelization on multi-level in MPPenvironment with the DAG Data Driven Model. The EasyHPS system encapsulatesdetails of parallelization implementation, such as task scheduling and messagepassing, and provides APIs for users to parallel dynamic programming problemautomatically and reduce the complexity of parallel programming parallelization. Thispaper also does some research on fault tolerance on the computing process of dynamicprogramming problem parallelization. EasyHPS system implements two ways forfault tolerance by timeout detecting and log tracing, and makes it possible to continuecomputing after system interrupt or restart. At last, a bioinformatics example verifiesthe system and its efficiency. Compared with block-cyclic based wave front method,dynamic scheduling approach in EasyHPS is more efficient. |
PDF Full Text Request