PDG: A Prefetcher for Dynamic Graph Updating

doi:10.1109/TCAD.2023.3335880

	PDG: A Prefetcher for Dynamic Graph Updating
	Zhang, Xinmiao 1,2,3; Liu, Cheng 3,4; Ni, Jiacheng 5; Cheng, Yuanqing 5; Zhang, Lei 1,2,3; Li, Huawei 3,4; Li, Xiaowei 3,4
	2024-04-01
发表期刊	IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS
ISSN	0278-0070
卷号	43 期号:4 页码:1246-1259
摘要	Dynamic graphs can be utilized to model manyreal-world applications like social media analysis in whichthe connections and entities evolve continuously. Hence, theprocessing of dynamic graphs is gaining increasing popularity.However, prior dynamic graph processing systems mainly focuson the optimization of graph analytics but overlook graphupdating which manages the evolving graph structure andpresents a unified view to graph analytics. Since graph updatingoperates on evolving graphs and involves a large number ofirregular memory accesses, it poses a substantial influence onthe performance of dynamic graph processing systems. In thiswork, we observe that graph updating is mainly bottlenecked bya frequent indirect memory access pattern & lowast;(& lowast;(B[A[i]]+offset)).The pattern is inherent to the typical graph updating from theincoming edge stream to the base data store organized witheither an adjacent list or a compressed sparse row. With thisobservation, we propose a novel prefetcher for dynamic graphupdating abbreviated as PDG. PDG is a lightweight pipelinedinstruction-based prefetcher specialized for graph updating andit is also compatible with the irregular memory access patternB[A[i]] widely used in graph analytics. In addition, it leveragesa monitor of the instruction queue to decide the appropriatetiming of prefetching to make the best use of the cache.According to our experiments, PDG achieves 1.60x,1.26x,and1.30xperformance speedup compared to three representativeprefetchers, respectively, with negligible hardware overhead ingraph updating
关键词	Prefetching Arrays Optimization Runtime Heuristic algorithms Computers Monitoring Computer architecture data prefetching memory system
DOI	10.1109/TCAD.2023.3335880
收录类别	SCI
语种	英语
资助项目	National Key R&D Program of China
WOS研究方向	Computer Science ; Engineering
WOS类目	Computer Science, Hardware & Architecture ; Computer Science, Interdisciplinary Applications ; Engineering, Electrical & Electronic
WOS记录号	WOS:001188376700008
出版者	IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
引用统计
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/38793
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Liu, Cheng; Cheng, Yuanqing
作者单位	1.Chinese Acad Sci, State Key Lab Processors, Beijing 100190, Peoples R China 2.Chinese Acad Sci, Inst Comp Technol, Beijing Key Lab Mobile Comp & Pervas Device, Beijing 100190, Peoples R China 3.Univ Chinese Acad Sci, Dept Comp Sci, Beijing 100089, Peoples R China 4.Chinese Acad Sci, Inst Comp Technol, State Key Lab Processors, Beijing 100190, Peoples R China 5.Beihang Univ, Sch Integrated Circuit Sci & Engn, Beijing 100191, Peoples R China
推荐引用方式 GB/T 7714	Zhang, Xinmiao,Liu, Cheng,Ni, Jiacheng,et al. PDG: A Prefetcher for Dynamic Graph Updating[J]. IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS,2024,43(4):1246-1259.
APA	Zhang, Xinmiao.,Liu, Cheng.,Ni, Jiacheng.,Cheng, Yuanqing.,Zhang, Lei.,...&Li, Xiaowei.(2024).PDG: A Prefetcher for Dynamic Graph Updating.IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS,43(4),1246-1259.
MLA	Zhang, Xinmiao,et al."PDG: A Prefetcher for Dynamic Graph Updating".IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 43.4(2024):1246-1259.