Cache oblivious algorithms for nonserial polyadic programming

doi:10.1007/s11227-007-0106-8

	Cache oblivious algorithms for nonserial polyadic programming
	Tan, Guangming ; Feng, Shengzhong ; Sun, Ninghui
	2007-02-01
发表期刊	JOURNAL OF SUPERCOMPUTING
ISSN	0920-8542
卷号	39 期号:2 页码:227-249
摘要	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.
关键词	dynamic programming nonserial polyadic cache oblivious algorithmic transformation data dependencies
DOI	10.1007/s11227-007-0106-8
收录类别	SCI
语种	英语
WOS研究方向	Computer Science ; Engineering
WOS类目	Computer Science, Hardware & Architecture ; Computer Science, Theory & Methods ; Engineering, Electrical & Electronic
WOS记录号	WOS:000245006300007
出版者	SPRINGER
引用统计	被引频次：1[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/10978
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	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.