DocumentCode :
1995726
Title :
EasyHPS: A Multilevel Hybrid Parallel System for Dynamic Programming
Author :
Jun Du ; Ce Yu ; Jizhou Sun ; Chao Sun ; Shanjiang Tang ; Yanlong Yin
Author_Institution :
Sch. of Comput. Sci. & Technol., Tianjin Univ., Tianjin, China
fYear :
2013
fDate :
20-24 May 2013
Firstpage :
630
Lastpage :
639
Abstract :
Dynamic programming approach solves complex problems efficiently by breaking them down into simpler sub-problems, and is widely utilized in scientific computing. With the increasing data volume of scientific applications and development of multi-core/multi-processor hardware technologies, it is necessary to develop efficient techniques for parallelizing dynamic programming algorithms, particularly in multilevel computing environment. The intrinsically strong data dependency of dynamic programming also makes it difficult and error-prone for the programmer to write a correct and efficient parallel program. In order to make the parallel programming easier and more efficient, we have developed a multilevel hybrid parallel runtime system for dynamic programming named EasyHPS based on the Directed Acyclic Graph(DAG) Data Driven Model in this paper. The EasyHPS system encapsulates details of parallelization implementation, such as task scheduling and message passing, and provides easy API for users to reduce the complexity of parallel programming parallelization. In the DAG Data Driven Model, the entire application is initially partitioned by data partitioning into sub-tasks that each sub-task processing a data block. Then all sub-tasks are modeled as a DAG, in which each vertex represents a sub-task and each edge indicates the communication dependency between the two sub-tasks. In task scheduling, a dynamic approach is proposed based on DAG Data Driven Model to achieve load balancing. Data partitioning and task scheduling are both done on processor-level and thread-level in the multilevel computing environment. In addition, experimental results demonstrate that the proposed dynamic scheduling approach in EasyHPS is more efficient in comparison with those static ones such as block-cyclic based wave front.
Keywords :
application program interfaces; computational complexity; directed graphs; dynamic programming; message passing; parallel algorithms; parallel programming; scheduling; API; DAG data driven model; EasyHPS system; block-cyclic based wave front; communication dependency; complexity reduction; data block; data partitioning; data volume; directed acyclic graph; dynamic programming algorithm parallelization; dynamic scheduling; load balancing; message passing; multicore hardware technology; multilevel computing environment; multilevel hybrid parallel runtime system; multilevel hybrid parallel system; multiprocessor hardware technology; parallel programming; processor-level task scheduling; scientific applications; scientific computing; subtask processing; thread-level task scheduling; Computational modeling; Data models; Dynamic programming; Load modeling; Partitioning algorithms; Processor scheduling; Runtime; Directed Acyclic Graph Data Driven Model; EasyHPS; dynamic programming; load balancing; multilevel computing environment; task scheduling;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Parallel and Distributed Processing Symposium Workshops & PhD Forum (IPDPSW), 2013 IEEE 27th International
Conference_Location :
Cambridge, MA
Print_ISBN :
978-0-7695-4979-8
Type :
conf
DOI :
10.1109/IPDPSW.2013.93
Filename :
6650939
Link To Document :
بازگشت