Improving Performance of Dynamic Programming via Parallelism and Locality on Multicore Architectures
文献类型：期刊论文
| 作者 | Tan, Guangming1; Sun, Ninghui1; Gao, Guang R.2 |
| 刊名 | IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
 |
| 出版日期 | 2009-02-01 |
| 卷号 | 20期号:2页码:261-274 |
| 关键词 | Dynamic programming memory hierarchy latency tolerant percolation multicore |
| ISSN号 | 1045-9219 |
| DOI | 10.1109/TPDS.2008.78 |
| 英文摘要 | 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. |
| 资助项目 | NSFC[60633040] ; IBM ; ET International ; Department of Energy[DE-FC02-01ER25503] ; US National Science Foundation (NSF)[CNS-0509332] |
| WOS研究方向 | Computer Science ; Engineering |
| 语种 | 英语 |
| WOS记录号 | WOS:000261892000011 |
| 出版者 | IEEE COMPUTER SOC |
| 源URL | [http://119.78.100.204/handle/2XEOYT63/11655]  |
| 专题 | 中国科学院计算技术研究所期刊论文_英文 |
| 通讯作者 | 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. |
入库方式： OAI收割
来源：计算技术研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。