中国科学院机构知识库网格
Chinese Academy of Sciences Institutional Repositories Grid
首页 机构 成果 学者
  
  1. CAS IR Grid
  2. 计算技术研究所
  3. 中国科学院计算技术研究所
  4. 中国科学院计算技术研究所期刊论文
  5. 英文
PDG: A Prefetcher for Dynamic Graph Updating

文献类型：期刊论文

作者Zhang, Xinmiao3,4,5; Liu, Cheng2,3; Ni, Jiacheng1; Cheng, Yuanqing1; Zhang, Lei3,4,5; Li, Huawei2,3; Li, Xiaowei2,3
刊名IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS
出版日期2024-04-01
卷号43期号:4页码:1246-1259
关键词Prefetching Arrays Optimization Runtime Heuristic algorithms Computers Monitoring Computer architecture data prefetching memory system
ISSN号0278-0070
DOI10.1109/TCAD.2023.3335880
英文摘要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
资助项目National Key R&D Program of China
WOS研究方向Computer Science ; Engineering
语种英语
WOS记录号WOS:001188376700008
出版者IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
源URL[http://119.78.100.204/handle/2XEOYT63/38792]  
专题中国科学院计算技术研究所期刊论文_英文
通讯作者Liu, Cheng; Cheng, Yuanqing
作者单位1.Beihang Univ, Sch Integrated Circuit Sci & Engn, Beijing 100191, Peoples R China
2.Chinese Acad Sci, Inst Comp Technol, State Key Lab Processors, 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, Beijing Key Lab Mobile Comp & Pervas Device, Beijing 100190, Peoples R China
5.Chinese Acad Sci, State Key Lab Processors, Beijing 100190, 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.

入库方式： OAI收割

来源：计算技术研究所

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

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