Adaptive Data Refinement for Parallel Dynamic Programming Applications

被引：1

作者：

Tang, Shanjiang ^{[1
]}

Yu, Ce ^{[1
]}

Lee, Bu-Sung ^{[2
]}

Sun, Chao ^{[1
]}

Sun, Jizhou ^{[1
]}

机构：

[1] Tianjin Univ, School Comp Sci & Technol, Tianjin, Peoples R China

[2] Nanyang Technol Univ, Sch Comp Engn, Singapore, Singapore

来源：

2012 IEEE 26TH INTERNATIONAL PARALLEL AND DISTRIBUTED PROCESSING SYMPOSIUM WORKSHOPS & PHD FORUM (IPDPSW) | 2012年

基金：

中国国家自然科学基金;

关键词：

Dynamic Programming; DAG Data Driven Model; Adaptive Data Refinement; Load Balancing; ALGORITHM; SPACE;

D O I：

10.1109/IPDPSW.2012.274

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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.

引用

页码：2220 / 2229

页数：10