Improving Performance of Dynamic Programming via Parallelism and Locality on Multicore Architectures

doi:10.1109/TPDS.2008.78

	Improving Performance of Dynamic Programming via Parallelism and Locality on Multicore Architectures
	Tan, Guangming 1; Sun, Ninghui 1; Gao, Guang R.2
	2009-02-01
发表期刊	IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
ISSN	1045-9219
卷号	20 期号:2 页码:261-274
摘要	Dynamic programming (DP) is a popular technique which is used to solve combinatorial search and optimization problems. This paper focuses on one type of DP, which is called nonserial polyadic dynamic programming (NPDP). Owing to the nonuniform data dependencies of NPDP, it is difficult to exploit either parallelism or locality. Worse still, the emerging multi/many-core architectures with small on-chip memory make these issues more challenging. In this paper, we address the challenges of exploiting the fine grain parallelism and locality of NPDP on multicore architectures. We describe a latency-tolerant model and a percolation technique for programming on multicore architectures. On an algorithmic level, both parallelism and locality do benefit from a specific data dependence transformation of NPDP. Next, we propose a parallel pipelining algorithm by decomposing computation operators and percolating data through a memory hierarchy to create just-in-time locality. In order to predict the execution time, we formulate an analytical performance model of the parallel algorithm. The parallel pipelining algorithm achieves not only high scalability on the 160-core IBM Cyclops64, but portable performance as well, across the 8-core Sun Niagara and quad-cores Intel Clovertown.
关键词	Dynamic programming memory hierarchy latency tolerant percolation multicore
DOI	10.1109/TPDS.2008.78
收录类别	SCI
语种	英语
资助项目	NSFC[60633040] ; IBM ; ET International ; Department of Energy[DE-FC02-01ER25503] ; US National Science Foundation (NSF)[CNS-0509332]
WOS研究方向	Computer Science ; Engineering
WOS类目	Computer Science, Theory & Methods ; Engineering, Electrical & Electronic
WOS记录号	WOS:000261892000011
出版者	IEEE COMPUTER SOC
引用统计	被引频次：17[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/11656
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Tan, Guangming
作者单位	1.Chinese Acad Sci, Inst Comp Technol, NCIC, Beijing 100190, Peoples R China 2.Univ Delaware, Dept Elect & Comp Engn, Newark, DE 19716 USA
推荐引用方式 GB/T 7714	Tan, Guangming,Sun, Ninghui,Gao, Guang R.. Improving Performance of Dynamic Programming via Parallelism and Locality on Multicore Architectures[J]. IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS,2009,20(2):261-274.
APA	Tan, Guangming,Sun, Ninghui,&Gao, Guang R..(2009).Improving Performance of Dynamic Programming via Parallelism and Locality on Multicore Architectures.IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS,20(2),261-274.
MLA	Tan, Guangming,et al."Improving Performance of Dynamic Programming via Parallelism and Locality on Multicore Architectures".IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 20.2(2009):261-274.