基于社区结构的图数据预取器设计  

Design of graph data prefetcher based on community structure

作　　者：李策 章隆兵[1,2] LI Ce;ZHANG Longbing(State Key Laboratory of Computer Architecture,Institute of Computing Technology,Chinese Academy of Sciences,Beijing 100190;School of Computer Engineering,University of Chinese Academy of Sciences,Beijing 100190)

机构地区：[1]计算机体系结构国家重点实验室(中国科学院计算技术研究所),北京100190 [2]中国科学院大学计算机学院,北京100190

出　　处：《高技术通讯》2022年第12期1251-1261,共11页Chinese High Technology Letters

基　　金：中国科学院战略性先导科技专项(C类)课题(XDC05020100)资助项目。

摘　　要：由于图数据规模庞大且结构不规则,图应用运行时会产生大量高延迟内存访问,大幅度降低了通用处理器的运行效率。本文采用软硬件结合的方式设计了图计算专用预取器,利用图数据访存特点以及社区结构的存储规律,通过对图数据进行混合预取,缩短了图计算访存的延迟,在含有较多社区的图数据集上获得了显著的性能收益。在不同图算法与图数据集上的实验表明,该预取器相对于无预取情况、流式预取器及传统图数据预取器,分别实现了65%~176%、6%~21%和4%~18%的性能提升。Due to the large scale and irregular structure of graph data,a large number of high-latency memory accesses are generated when graph applications are running,which greatly reduces the efficiency of general-purpose processors.This paper uses a combination of software and hardware to design a dedicated prefetcher for graph analytics.Using the characteristics of graph data access and the storage law of community structure,and through hybrid prefetching of graph data,the memory access latency of graph analytics are shortened and significant performance gains are obtained on graph datasets containing more communities.Experiments on different graph algorithms and graph datasets show that the prefetcher achieves 65%-176%performance improvement over the no-prefetch baseline,6%-21%performance improvement over the stream prefetcher,and 4%-18%performance improvement over the traditional graph data prefetcher.

关 键 词：图计算 预取器 社区结构 存储规律 及时性 

分 类 号：O157.5[理学—数学]