Tyche: An Efficient and General Prefetcher for Indirect Memory Accesses

doi:10.1145/3641853

	Tyche: An Efficient and General Prefetcher for Indirect Memory Accesses
	Xue, Feng 1,2; Han, Chenji 1,2; Li, Xinyu 1,2; Wu, Junliang 1,2; Zhang, Tingting 3,4; Liu, Tianyi 5; Hao, Yifan 1; Du, Zidong 1; Guo, Qi 1; Zhang, Fuxin 1
	2024-06-01
发表期刊	ACM TRANSACTIONS ON ARCHITECTURE AND CODE OPTIMIZATION
ISSN	1544-3566
卷号	21 期号:2 页码:26
摘要	Indirect memory accesses (IMAs, i.e., A[f(B[i])]) are typical memory access patterns in applications such as graph analysis, machine learning, and database. IMAs are composed of producer-consumer pairs, where the consumers' memory addresses are derived from the producers' memory data. Due to the built-in value-dependent feature, IMAs exhibit poor locality, making prefetching ineffective. Hindered by the challenges of recording the potentially complex graphs of instruction dependencies among IMA producers and consumers, current state-of-the-art hardware prefetchers either (a) exhibit inadequate IMA identification abilities or ( b) rely on the run-ahead mechanism to prefetch IMAs intermittently and insufficiently. To solve this problem, we propose Tyche,1 an efficient and general hardware prefetcher to enhance IMA performance. Tyche adopts a bilateral propagation mechanism to precisely excavate the instruction dependencies in simple chains with moderate length (rather than complex graphs). Based on the exact instruction dependencies, Tyche can accurately identify various IMA patterns, including nonlinear ones, and generate accurate prefetching requests continuously. Evaluated on broad benchmarks, Tyche achieves an average performance speedup of 16.2% over the state-of-the-art spatial prefetcher Berti. More importantly, Tyche outperforms the state-of-the-art IMA prefetchers IMP, Gretch, and Vector Runahead, by 15.9%, 12.8%, and 10.7%, respectively, with a lower storage overhead of only 0.57 KB.
关键词	Data prefetching hardware prefetching indirect memory accesses microarchitecture
DOI	10.1145/3641853
收录类别	SCI
语种	英语
资助项目	National Key Research and Development Program of China[2022YFB3105103]
WOS研究方向	Computer Science
WOS类目	Computer Science, Hardware & Architecture ; Computer Science, Theory & Methods
WOS记录号	WOS:001242588100010
出版者	ASSOC COMPUTING MACHINERY
引用统计
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/39897
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Xue, Feng
作者单位	1.Chinese Acad Sci, Inst Comp Technol, SKLP, 6 Kexueyuan Nanlu, Beijing 100190, Peoples R China 2.Univ Chinese Acad Sci, 19A Yuquan Rd, Beijing 100049, Peoples R China 3.Loongson Technol Co Ltd, Loongson Ind Pk, Beijing 100095, Peoples R China 4.Chinese Acad Sci, Inst Comp Technol, 6 Kexueyuan Nanlu, Beijing 100190, Peoples R China 5.Univ Texas San Antonio, 1 UTSA Circle, San Antonio, TX 78249 USA
推荐引用方式 GB/T 7714	Xue, Feng,Han, Chenji,Li, Xinyu,et al. Tyche: An Efficient and General Prefetcher for Indirect Memory Accesses[J]. ACM TRANSACTIONS ON ARCHITECTURE AND CODE OPTIMIZATION,2024,21(2):26.
APA	Xue, Feng.,Han, Chenji.,Li, Xinyu.,Wu, Junliang.,Zhang, Tingting.,...&Zhang, Fuxin.(2024).Tyche: An Efficient and General Prefetcher for Indirect Memory Accesses.ACM TRANSACTIONS ON ARCHITECTURE AND CODE OPTIMIZATION,21(2),26.
MLA	Xue, Feng,et al."Tyche: An Efficient and General Prefetcher for Indirect Memory Accesses".ACM TRANSACTIONS ON ARCHITECTURE AND CODE OPTIMIZATION 21.2(2024):26.