中国科学院机构知识库网格
Chinese Academy of Sciences Institutional Repositories Grid
首页 机构 成果 学者
  
  1. CAS IR Grid
  2. 计算技术研究所
  3. 中国科学院计算技术研究所
  4. 中国科学院计算技术研究所期刊论文
  5. 英文
Cache oblivious algorithms for nonserial polyadic programming

文献类型：期刊论文

作者Tan, Guangming; Feng, Shengzhong; Sun, Ninghui
刊名JOURNAL OF SUPERCOMPUTING
出版日期2007-02-01
卷号39期号:2页码:227-249
关键词dynamic programming nonserial polyadic cache oblivious algorithmic transformation data dependencies
ISSN号0920-8542
DOI10.1007/s11227-007-0106-8
英文摘要The nonserial polyadic dynamic programming algorithm is one of the most fundamental algorithms for solving discrete optimization problems. Although the loops in the nonserial polyadic dynamic programming algorithm are similar to those in matrix multiplication, the available automatic optimization techniques have little effect on this imperfect loop because of nonuniform data dependencies. In this paper, we develop algorithmic optimizations to improve the cache performance of the nonserial polyadic dynamic programming algorithm. Our algorithmic transformation takes advantage of the cache oblivious method by relaxing some dependencies in the standard iterative version. Based on the ideal cache model of the cache oblivious algorithm, the approximate bound of cache misses is given by Theta(n(3)Z/L root Z + n(2)/L + n/L root Z). We also found that the optimized algorithm with the cache oblivious approach is more sensitive to conventional optimization techniques such as tiling. Experimental results on several platforms show that the optimized algorithms improve the cache performance and achieves speedups of 2-10 times.
WOS研究方向Computer Science ; Engineering
语种英语
WOS记录号WOS:000245006300007
出版者SPRINGER
源URL[http://119.78.100.204/handle/2XEOYT63/10977]  
专题中国科学院计算技术研究所期刊论文_英文
通讯作者Tan, Guangming
作者单位1.Chinese Acad Sci, Inst Comp Technol, Beijing 100080, Peoples R China
2.Chinese Acad Sci, Comp Technol Inst, Natl Res Ctr Intelligent Comp Syst, Beijing, Peoples R China
推荐引用方式
GB/T 7714		 Tan, Guangming,Feng, Shengzhong,Sun, Ninghui. Cache oblivious algorithms for nonserial polyadic programming[J]. JOURNAL OF SUPERCOMPUTING,2007,39(2):227-249.
APA Tan, Guangming,Feng, Shengzhong,&Sun, Ninghui.(2007).Cache oblivious algorithms for nonserial polyadic programming.JOURNAL OF SUPERCOMPUTING,39(2),227-249.
MLA Tan, Guangming,et al."Cache oblivious algorithms for nonserial polyadic programming".JOURNAL OF SUPERCOMPUTING 39.2(2007):227-249.

入库方式： OAI收割

来源：计算技术研究所

浏览0
下载0
收藏0
其他版本

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。