Adaptive Data Refinement for Parallel Dynamic Programming Applications

Load balancing is a challenging work for parallel dynamic programming due to its intrinsically strong data dependency. Two issues are mainly involved and equally important, namely, the partitioning method as well as scheduling and distribution policy of subtasks. However, researchers take into account their load balancing strategies primarily from the aspect of scheduling and allocation policy, while the partitioning approach is roughly considered. In this paper, an adaptive data refinement scheme is proposed. It is based on our previous work of DAG Data Driven Model. It can spawn more new computing subtasks during the execution by repartitioning the current block of task into smaller ones if the workload unbalance is detected. The experiment shows that it can dramatically improve the performance of system. Moreover, in order to substantially evaluate the quality of our method, a theoretic upper bound of improvable space for parallel dynamic programming is given. The experimental result in comparison with theoretical analysis clearly shows the fairly good performance of our approach.