C-AMAT Measurement Method Based on Cache Access Mode and Its Application in Graph Computing
-
摘要:
图应用是大数据领域的一个重要分支，尽管图分析在显示表示实体之间关系的能力相比传统的关系数据库具有更显著的性能优势，但图处理中大量的随机访问所导致的不规则访存模式破坏了访存的时间和空间局部性，从而对片外内存系统造成了很大的性能压力. 因此如何正确度量图应用在内存系统中的性能，对于高效的图应用体系结构优化设计至关重要. 并发式平均存储访问时间（concurrent average memory access time，C-AMAT）模型作为平均存储访问时间（average memory access time，AMAT）的扩展，同时考虑了存储器访问的局部性和并发性，能够更准确地对现代处理器下图应用在存储系统中的性能进行评估分析. 但C-AMAT 模型忽略了处理器下级cache层串行访问的事实，这会导致计算的不准确性，同时由于计算所需参数纯粹缺失周期等难以获取的原因，也使得C-AMAT难以进行实际应用. 为了使C-AMAT的计算模型与现代计算机中的存储器访问模式相匹配，基于C-AMAT提出了PC-AMAT（parallel C-AMAT），SC-AMAT（serial C-AMAT），其中PC-AMAT，SC-AMAT分别从cache的并行和串行访问模式对C-AMAT的计算模型进行了细粒度的扩展和表征，并在此基础上设计并实现了纯粹缺失周期的提取算法，避免直接测量带来的巨大硬件开销. 实验结果表明，在单核和多核模式下，PC-AMAT和SC-AMAT与IPC之间的相关性比C-AMAT更强，最终利用PC-AMAT和SC-AMAT度量和分析了图应用的存储器性能并据此提出图应用访存优化策略.
Abstract:Graph application is an important branch in the field of big data. Although graph analysis has more significant performance advantages than traditional relational databases in displaying the relationship between entities, the irregular memory access pattern caused by a large number of random accesses in graph processing destroys the time and space locality of memory access, thus causing great performance pressure on the off-chip memory system. Therefore, how to correctly measure the performance of graph application in memory system is crucial for efficient graph application architecture optimization. As an extension of average memory access time (AMAT), concurrent average memory access time (C-AMAT) takes into account the locality and concurrency of memory access, and can more accurately evaluate and analyze the performance of modern processors in the storage system. However, the C-AMAT model ignores the fact that the lower-level cache layer of the processor accesses serially, which will lead to the inaccuracy of the calculation. At the same time, it is difficult to obtain the parameters required for the calculation due to the “pure miss cycle” and other reasons, which also makes it difficult for C-AMAT to be applied in practice. In order to match the computing model of C-AMAT with the memory access mode in modern computers, we propose parallel C-AMAT (PC-AMAT) and serial C-AMAT (SC-AMAT) based on C-AMAT. PC-AMAT and SC-AMAT respectively extend and characterize the computing model of C-AMAT from the parallel and serial access modes of cache. On this basis, we design and implement a “pure miss cycle” extraction algorithm to avoid the huge hardware overhead caused by direct measurement. The experimental results show that the correlation between PC-AMAT and SC-AMAT, and IPC is stronger than that of C-AMAT in single-core and multi-core mode. Finally, PC-AMAT and SC-AMAT are used to measure and analyze the memory performance of graph application, based on which the optimization strategy of graph application access is proposed.
-
Keywords:
- graph application /
- graph analysis /
- AMAT /
- C-AMAT /
- pure miss cycle /
- cache
-
大数据时代下，人类社会中大规模与不规律数据信息快速增长，以图结构对这些数据进行存储分析越来越普遍. 基于图结构的信息存储方式被广泛应用于人际关系、社交网络分析、社会科学等各个领域，图数据处理变得越来越重要. 而目前图应用的主要性能瓶颈就在于其数据访问层面[1]，因此对于图应用在存储器中性能的评估与分析对于相应的硬件开发和算法设计都具有重要意义.
并发式平均存储访问时间（concurrent average memory access time，C-AMAT）模型通过同时考虑存储器访问的局部性和并发性[2]，可以更准确地表征图应用的存储器性能. 但是C-AMAT的计算模型认为数据访问的命中时间总是固定的，存在一定的局限性，同时，又因为其测量装置硬件开销大，使得其在实际应用中是不易实现的.
为了利用C-AMAT准确地评估检测图应用的存储器性能，我们基于缓存的访问模式将C-AMAT的计算模型扩展为PC-AMAT（parallel C-AMAT）和SC-AMAT（serial C-AMAT），并在此基础上设计并实现了C-AMAT中纯粹缺失周期（pure miss cycle，PMC）的提取算法及所需各项参数的测量. 最终利用C-AMAT在gem5[3]模拟器中对各类图应用在存储器中的性能进行了实验评估与分析，提出了相应的访存优化策略.
本文的主要贡献包括3个方面：
1） 基于缓存的数据访问模式将C-AMAT的计算模型扩展为PC-AMAT和SC-AMAT，使C-AMAT的计算模型与现代计算机中不同层次的存储器访问模式相匹配，从而为更准确地测量和计算应用程序运行过程中对数据的并发式平均存储访问时间提供了理论依据；
2） 设计并实现了计算C-AMAT所需的重要中间参数纯粹缺失周期的提取算法，避免了直接测量所需要的巨大硬件开销；
3） 利用相关系数验证了PC-AMAT和SC-AMAT与IPC之间的相关性比C-AMAT更强，进一步设计了图应用的存储器性能评估实验，通过应用各种规模的图数据集对图应用的访存性能进行了系统性地分析.
1. 相关工作
图处理是大数据领域中一类重要的计算方式，在机器学习、路径规划、传染病学、神经网络等领域都有广泛应用.
现实世界的图数据往往呈现出小世界性（small-world）[4]和无尺度性（scale-free）[5]，稀疏矩阵存储格式是典型的图数据存储格式，尽管有研究表明基于稀疏矩阵的压缩稀疏行（compressed sparse row，CSR）、对角线（diagonal，DIA）[6]等格式存储效率很高，但仍然改变不了图数据访问的不规则性，存储器性能效率低下已经成为图应用发展中最大的性能瓶颈. 目前学术界关于图数据处理性能的研究有很多. Basak等人[1]通过分析乱序CPU下图数据的访存行为发现不同数据类型加载指令之间的依赖链（load-load dependency chain，LLDC）是实现高内存级并行（memory level parallelism， MLP）的主要瓶颈；Balaji等人[7]在末级缓存（last level cache，LLC）更换不同的数据替换策略时发现，即使是最先进的缓存数据替换策略，图应用在LLC上的MPKI（misses per kilo instructions）依然没有明显下降；汤嘉武等人[8]通过实验分析出通用高层次综合（high level synthesis，HLS）系统缺乏对不规则图算法有效支撑的问题，提出了一种面向图计算的高效HLS方法，实现了高效的并行流水执行；Faldu等人[9]验证了由于图分析的高度不规则访问模式，最先进的硬件缓存管理方案在利用其重用方面依然不尽人意，为此，他们引入了专门用于LLC上对图分析进行缓存管理的GRASP，GRASP专用缓存策略利用了热顶点固有的高重用，同时保留了捕获其他缓存块中图数据重用的灵活性；Cooksey 等人[10]则从高速缓存行中获取任何看似合理的地址作为数据加载，但是，只有观察到数据结构是一个指针列表时，这些指针才将被引用，否则此类方案将显著超载，从而导致缓存污染和性能下降.
尽管学术界现有的研究工作从多个维度对图应用进行性能评测都发现了其性能瓶颈在访存层面，但采用的系统性能评估指标更多地停留在以计算为中心的层面，最为广泛使用的便是每周期完成指令数（ instruction per clock，IPC），但IPC是被设计用来测试CPU性能的，并且由于IPC受指令集、CPU微架构、存储器层次结构和编译器技术等多方面的影响，无法直接用来反映存储器系统的性能. 另一方面，传统的存储器性能指标，如访存缺失率（miss rate，MR）、平均缺失代价（average miss penalty，AMP）、平均存储器访问时间（average memory access time，AMAT），对于采用流水线缓存[11]、非阻塞缓存[12]等现代设计的存储器系统来说是不合适的. 我们在gem5中对内核数量进行了倍增，以此提高LLC上的并发性，在对GAP[13]基准测试套件中典型的BFS（breadth first search），PR（PageRank），BC（betweenness centrality），CC（connected components）这4个算法在LLC上的AMAT进行了测量，其中实验环境配置及工作负载见第4节. 图1显示了当并发性作为一个因素时，AMAT作为衡量内存性能的指标是失败的，AMAT指标表明：随着内核数量的增加，LLC上的总体性能会下降. 这和系统性能提升的事实相违背，显然是错误的. 这也进一步表明AMAT已无法准确反映现代处理器的内存性能.
2013年，Sun等人[2]提出了新的存储器性能度量标准C-AMAT，C-AMAT通过给出严格规整的数学表达式和逻辑证明，将AMAT进行了扩展，可以更准确、全面地评估现代存储器系统.
在定量上，C-AMAT被定义为总的存储访问周期除以总的存储访问次数[2]：
C_AMAT=TMemCycleCMemAcc, (1) 其中TMemCycle代表总的存储访问周期，CMemAcc则代表总的存储访问次数. 需要注意的是，TMemCycle是以重叠模式计算的，换句话说，当同一周期内存在多个内存访问时，TMemCycle仅增加1个周期. 此外，存储访问周期与CPU周期不同，至少有1次未完成内存访问的CPU周期才能算作内存访问周期.
根据相关系数的定义，C-AMAT应该与IPC呈负相关[14]，即IPC增加时，C-AMAT减少. 此外,当IPC有很大程度的增加时，C-AMAT也应该有类似程度的变化. 然而，当我们在对GAP基准测试套件中图应用进行测量时发现，图应用的IPC并不总与C-AMAT呈负相关. 实验结果如图2所示，其中实验环境配置及工作负载见第4节. 为了更直观地表现IPC和C-AMAT之间的关系变化，对图算法在各个数据集中的IPC和C-AMAT的平均值进行了比较. 在图2（a）中我们看到，随着内核数量的增加，IPC也随之递增. 然而从图2（b）~（d）中发现，随着内核数量的增加，在各级cache中的C-AMAT仅BFS算法在L1和LLC中呈现出递减的趋势，其他算法在各级cache中的变化则是无规律的，且变化幅度也是远小于IPC的.
之所以出现图2中的现象，是因为C-AMAT的计算模型总是认为数据访问过程中的命中延时是固定的，忽略了cache层中的数据访问模式，使用固定的cache访问延时会导致测量出的总存储访问周期TMemCycle与其理论值有所偏差.
事实上，现代处理器多采用乱序执行来提升CPU的处理效率，典型的如Intel在x86体系中的Pentium Pro，为了提高时钟频率并降低cache的缺失代价，对于cache中的Tag SRAM和Data SRAM这2部分的访问模式，现代处理器往往在L1 cache采用了并行访问的结构，但其访问命中时间并不是简单的Tag与Data延时相加得到的. 而L2 cache以及下一级cache的数据访问则通常采用的是串行访问模式[15]，即对于L2 cache及下一级cache而言，它们的命中延时在访问命中和访问缺失时不再是固定的，因此，C-AMAT的计算模型可能无法完全正确地表征存储器系统的整体性能. 其中的计算细节我们将在第2节重点讨论.
另一方面，与AMAT相比，C-AMAT的计算方法也更加复杂，并且需要额外的检测逻辑和寄存器来测量C-AMAT所需的参数，尽管文献[14]给出了每周期访问（access per cycle，APC）的测量逻辑，但这种方法却有着较大的硬件开销和繁杂的计数逻辑，不易实现. 因此，如何准确获取一段完整应用程序中的纯粹缺失周期和纯粹缺失访问仍然是测量C-AMAT的重点和难点.
为了准确度量图应用的存储性能，本文通过分析前人研究成果，基于现代乱序处理器中不同层次cache的不同访问模式，将C-AMAT的计算模型扩展为PC-AMAT和SC-AMAT，完善了C-AMAT的计算模型. 同时提出并实现了纯粹缺失周期和纯粹缺失访问的提取算法，最终基于PC-AMAT和SC-AMAT对图应用的存储性能进行表征，这使得寻找到适用于图应用系统的整体最佳参数组合成为可能.
2. PC-AMAT和SC-AMAT的计算模型
由于我们的工作直接基于C-AMAT，因此在本节首先介绍了C-AMAT的计算模型，然后通过分析不同层次cache的数据访问模式，引入了基于C-AMAT扩展的PC-AMAT和SC-AMAT的计算模型.
2.1 C-AMAT计算模型
式（1）给出了C-AMAT的原始定量公式，但并没有明显体现出C-AMAT的局部性和并发性，为了体现这2种性质，给出了C-AMAT的详细计算公式[2]：
CAMAT=HCh+pMR×pAMPCm， (2) 其中H代表命中延时，Ch和Cm分别代表命中存储请求的并发度和缺失存储请求的并发度，Ch和Cm是C-AMAT引入的2个新参数. 此外，这个计算公式首次引入了“纯粹缺失”的概念，即只有在缺失访问中至少包括1个纯粹缺失周期，在这个周期中，整个存储系统都没有命中发生，这样的缺失才称为纯粹缺失. pMR为纯粹缺失率，即纯粹缺失访问的次数与全部存储访问次数之比. pAMP即纯粹平均缺失代价，代表平均每个纯粹缺失访问中的纯粹缺失周期的数量[2].
然而，在C-AMAT中，无论当前层级存储器中的数据是否命中，它的命中时延总被认为是固定的. 事实上，现代处理器中cache层的数据命中时间与其访问模式息息相关，因此，我们基于cache访问模式对C-AMAT的计算模型进行了细粒度的扩展.
2.2 PC-AMAT计算模型
现代处理器中的cache由Tag和Data这2部分组成，但在实际的实现当中，cache line中的Tag和Data部分其实是分开放置的，称为Tag SRAM和Data SRAM，如果对这2部分的内容同时进行访问，则称为并行访问[16]，其结构如图3所示；反之，如果先访问Tag SRAM部分，根据Tag的比较结果再去访问Data SRAM部分，这种方式则称为串行访问[16]，其结构如图4所示.
当对图3这种结构的cache进行访问时，在对某个Tag部分的地址访问的同时会对该地址对应Data部分的数据也进行访问，并将它们送到多路选择器中选择出指定的数据块，最终经过数据对齐便可完成数据访问. 由于现代超标量处理器使用的是流水线访问，数据块选择时间和数据对齐部分的时间是可以忽略不计的，因此，在cache的并行访问结构中完成一次数据访问的时间其实是由Tag和Data中访问延时较长的部分所决定的，此时如将Tag与Data访问延时之和作为cache命中时间是错误的，因为这将会严重高估C-AMAT的值. 因此，并行结构下基于C-AMAT的PC-AMAT可以表示为式（3）.
PC_AMAT=PHCph+pMR×pAMPCm. (3) 在PC-AMAT中，PH代表了并发cache命中时间，即在并行访问结构中，cache的命中延时PH由Tag延时和Data延时的较大者决定，因此PH可以表示为：
PH={tag_latency,data_latency, tag_latency⩾ (4) 其中tag_latency和data_latency分别表示Tag部分访问和Data部分访问所需要的命中时间，一般情况下，现代处理器中L1 cache在这2部分的延迟都在2~5个周期之间，同一架构处理器中的tag_latency和data_latency差距并不会太大[17]，但文献[18]中将命中时延统一成一个固定的参数显然是与事实不符的，这会造成Cph和Cm的计算误差，最终导致计算出来的C-AMAT值与实际值存在较大误差. Cph和Cm的计算方式为：
{C_{{\text{ph}}}} = \frac{{PH \times access}}{{overlap\_hitTime}}, (5) {C_{\text{m}}} = \frac{{pMissTime}}{{pMissTime\_overlap}}, (6) 其中access表示当前存储器中总的数据访问次数，overlap_hitTime表示当前cache访问过程中的重叠命中时间，pMissTime表示所有数据访问总的纯粹缺失周期，而pMissTime_overlap则代表了所有数据访问过程中总的重叠纯粹缺失周期. 我们将在第3节详细解读上述变量的取值.
2.3 SC-AMAT计算模型
图4展示了cache的串行访问结构，在对数据进行访问时，首先需要对Tag SRAM进行访问，进行Tag比对之后，若Tag对应的Data部分中的数据在当前cache层中存在，则对其进行选择访问，此时就不再需要进行数据对齐即可对指定的数据块进行访问，这样的1次数据访问命中时间就是Tag与Data的访问延时之和；但若对Tag进行访问后在当前cache层中未检测到对应的数据部分，则进入下一级存储器进行访问，此时当前cache层中数据访问的命中时间只需将Tag部分延时包含在内.
因此，串行访问结构是不需要多路选择器进行数据选择的，而只需要访问数据部分指定的那个SRAM，其他的SRAM由于都不需要被访问，可以将它们的使能信号置为无效，这样就可以节省很多功耗，串行访问结构也多被应用于现代处理器的L2 cache和LLC. 即串行结构下的cache访问，其命中时间是由数据是否命中所决定的. 因此，串行结构下基于C-AMAT的SC-AMAT可以表示为：
S C\_AMAT = \frac{{S H}}{{{C_{{\text{sh}}}}}} + pMR \times \frac{{pAMP}}{{{C_{\text{m}}}}}. (7) 尽管在SC-AMAT中，SH也代表着cache的命中时间，但不同于式（2）中的PH，SH的大小是由数据是否命中决定的，因此，SH可表示为：
S H=\left\{\begin{array}{ll}& tag\_latency+data\_latency,\quad 数据访问命中\text{,}\\& tag\_latency,\qquad\qquad\qquad\quad 数据访问缺失\text{,}\end{array} \right. (8) 当数据访问命中时，命中时间SH是tag_latency和data_latency相加，而当数据访问缺失时，其命中时间SH则只由tag_latency决定. 现代处理器中L2 cache在这2部分的延迟都在6~12个周期，LLC在这2部分的延迟一般在32~64个周期[17]，当然，精确的访问延时需要根据具体的CPU架构来确定. 但显而易见，此时命中延时SH不是固定值，使用式（2）中的H将会对并发式平均访问时间的计算结果造成不可忽略的误差. 相应地，串行访问结构下数据访问的命中并发度Csh的表达式为：
\begin{split}& {C_{{\text{sh}}}} =\\&\quad \frac{{(tag\_latency + data\_latency) \times hit + tag\_latency \times miss}}{{overlap\_hitTime}},\end{split} (9) 其中hit代表当前存储器中数据访问的命中次数，miss表示当前存储器中数据访问的缺失次数，与Cph一样，Csh的分母overlap_hitTime依然是当前cache访问过程中的重叠命中时间.
第4节中我们将会根据IPC与C-AMAT，PC-AMAT，SC-AMAT这3个指标的相关系数来度量这3个指标的精确度，以验证扩展C-AMAT为PC-AMAT与SC-AMAT的必要性与合理性.
3. 纯粹缺失周期提取算法
本节详细介绍如何提取PC-AMAT和SC-AMAT测量过程中所需的重要中间参数—纯粹缺失周期，并据此计算出pMR，pAMP，Cm等依赖PMC的计算参数，进而计算出PC-AMAT和SC-AMAT .
根据式（2），我们知道想要计算C-AMAT首先需要测量Ch和Cm. 文献[18]提供了Ch和Cm的计算方法，如图5所示. 通过在原有的硬件结构上增加了2个探测器，分别是命中并发度探测器和缺失并发度探测器，这2个探测器都由检测逻辑和寄存器组成，命中并发度探测器中的检测逻辑用来监控是否有缓存Tag查询活动. 通过使用寄存器来统计总的命中周期和每个命中阶段的同时命中情况，并计算平均命中并发度. 因此，每个命中阶段至少需要2个寄存器，分别用来记录开始周期和结束周期. 缺失并发度探测器中的检测逻辑监控是否有新的请求到达MSHR（missing status holding register）[18]，并通过寄存器来探测纯粹缺失周期的数量和每个纯粹缺失阶段的并发度. 缺失并发度探测器所需的寄存器数量计算和命中并发度探测器数量的计算方法是类似的，不同之处在于选择的寄存器的数量需要考虑同一周期内共存的最大缺失访问数，即MSHR表项的数量乘以MSHR表项中目标的数量.
基于上述分析，我们发现仅是测量C-AMAT的Ch和Cm便会导致很大的硬件开销，因此想要通过这种测量装置直接测量出应用程序的C-AMAT是比较困难的. 据此，我们在测量图应用的C-AMAT时并没有直接使用文献[18]中的这种测量装置. 同样如图5所示，我们并没有在程序运行的过程中去监测访存的命中并发度与缺失并发度，对于每个命中与缺失阶段，都只需要2个寄存器分别用来记录开始周期与结束周期，在一次访存结束后，便可立即释放当前寄存器，而无需一直保留用来计算访问并发度. 最后通过设计相应的纯粹缺失周期提取算法，计算出PC-AMAT和SC-AMAT计算所需要的相关参数. 这种方法大大降低了C-AMAT测量所需的硬件开销，同时避免了程序运行阶段探测并发度时繁杂的访存检测逻辑.
3.1 PC-AMAT与SC-AMAT实例
为了更好地解释和理解纯粹缺失周期等相关概念，我们基于PC-AMAT举了一个简单的例子，如图6所示，图6中共存在5个不同的存储访问. 由于PC-AMAT是针对并行访问结构的cache而言的，我们假设当前cache中Tag SRAM部分的命中时间为2个周期，Data SRAM部分的命中时间为3个周期，因此，每次数据访问都必须经过3个周期的命中阶段. 如果访问没有在当前cache中命中，即访问缺失时，则会产生1个缺失代价，缺失代价的大小取决于最终该缺失的数据在哪一级存储层次中被找到. 图6中，访问请求1，2，5是命中访问，访问3和4是缺失访问. 访问3包含了4个周期的缺失代价，其中有2个周期与访问5的命中周期出现了重叠，因此，从并发存储的角度来看，访问3只存在2个纯粹缺失周期. 访问4有1个缺失周期，但该周期也与访问5的命中周期重叠，因此不是纯粹缺失周期. 因此，访问3是纯粹缺失访问，访问4不是，所以这5个访问的缺失率为0.4，而纯粹缺失率仅为0.2，纯粹平均访问缺失代价pAMP=1. 同时，对于式（5）和式（9）中提到的命中重叠时间overlap_hitTime，我们将其定义为在所有访问请求中，只要当前周期存在命中周期，那该周期则算作1次重叠命中周期. 类似地，纯粹缺失重叠时间pMissTime_overlap为在所有请求访问中，当前周期都是纯粹缺失周期时视作1次纯粹缺失重叠周期.
因此，从图6中我们可以观察到这5个访问总的命中重叠时间为7，总的纯粹缺失重叠时间为1，根据式（5）和式（6）计算可得Cph=15/7和Cm=2，最后由式（3）得到PC-AMAT的每次访问周期个数为1.8. 事实上，图6中5个访问请求总共经历了8个时钟周期，并且这8个周期都属于访问周期，因此我们也可以直接将总重叠访问周期除以访问次数得到PC-AMAT的每次访问周期个数为9/5=1.8.
而对于SC-AMAT，其与PC-AMAT最大的区别就在于当前存储器中的命中访问与缺失访问的命中时间是不一致的，为了更好地解释SC-AMAT，我们同样举了一个简单的例子，如图7所示，图7中也存在5个不同的存储访问. 我们假设当前cache中Tag SRAM和Data SRAM的命中时间都为3个周期，因此，每次数据访问若是在当前cache中命中，则其命中时间为6个周期. 若是访问缺失，则只会经历3个周期的Tag访问命中时间，接下来该缺失访问同样会根据数据最终查找到位置，产生相应的缺失代价. 图7中，由于访问请求1，2，5的命中时间都为6个周期，因此都属于命中访问；而访问3，4则属于缺失访问，它们在当前cache上的命中时间都仅为3个周期，访问3包含了8个周期的缺失代价，其中有5个周期与访问5的命中周期重叠，因此访问3存在3个纯粹缺失周期. 与访问3类似，访问4的缺失代价为5个周期，其中有2个周期为纯粹缺失周期. 通过以上分析，我们可以计算出图7示例中5个访问的纯粹缺失率为0.4，纯粹平均访问缺失代价pAMP=2.5，同时将命中重叠时间和纯粹缺失重叠时间分别等于9和3时代入式（9）和式（6），可以计算出Csh=8/3和Cm=5/3，最后由式（7）计算得到SC-AMAT每次访问2.4个周期. 同样，由于这5个访问所经历的总重叠时间为12个周期，我们也可以得到SC-AMAT每次访问2.4个周期（12/5）.
3.2 纯粹缺失周期提取算法
在实际应用程序中，并不是所有周期都属于访问周期，数据访问过程中存在着停滞周期，因此3.1节中的计算示例的计算方法并不适用于实际应用程序中C-AMAT的测量. 准确测量PC-AMAT和SC-AMAT的值的难点就在于如何准确地判断每个缺失周期是命中、失效重叠，还是纯失效. 据此，我们设计了纯粹缺失周期PMC提取方法，具体过程如图8所示.
为了获取每个缺失周期的属性值，我们首先将缺失访问进行了合并. 我们将所有缺失访问的缺失代价按照它们的开始周期进行递增排序，然后通过一个结构体missCycle记录每一个缺失周期的绝对时间start、该缺失周期被缺失访问占有的次数count以及该缺失周期所在的缺失访问请求parent. 我们通过分类和迭代便可获取到每个缺失周期的属性值，包括该缺失周期总共被占有的缺失访问的次数以及存在于哪些缺失访问中. 算法描述如算法1所示.
算法1. 缺失周期合并算法.
输入：缺失访问数组missAccess，当前缺失周期curr_cycle.
① for each curr_cycle in missAccess[i] do
② curr_cycle初始化；
③ end for
④ add first（missAccess[0]） into tempMiss array； /*将第1个缺失访问的缺失代价暂存中间 缺失数组tempMiss中*/
⑤ for each missAccess>1 in missAccess array do
⑥ if missAccess[i].start \geqslant tempMiss[i−1].start && missAccess[i].start<tempMiss[i−1].end then/*图8情景1*/
⑦ if missAccess[i].end \leqslant tempMiss[i−1].end
then
⑧ for each curr_cycle in missAccess[i] do
⑨ location=find（curr_cycle）；
⑩ curr_cycle.count++；
⑪ curr_cycle.parent.push_back（i）； 当在合并缺失访问时出现情景 1下的缺失访问时，只需对每个 缺失周期的属性值进行更新*/
⑫ end for
⑬ else
⑭ for each cycle in tempMiss[i−1] do
⑮ ⑨~⑪；/*图8情景2，周期更新*/
⑯ end for
⑰ for each curr_cycle from tempMiss [i−1].end to missAccess[i].end do
⑱ 将这部分curr_cycle初始化；
⑲ 缺失访问2的尾部插入到缺失访 问1的尾部；
⑳ end for
㉑ end if
㉒ else
㉓ for each curr_cycle in missAccess[i] do
㉔ 初始化curr_cycle；/*图8情景3*/
㉕ tempMiss.push_back（missAccess[i]）； /*此时缺失访问1无法再进行合 并操作，缺失访问2作为下一次 合并操作的缺失访问1*/
㉖ end for
㉗ end if
㉘ end for
对于图8中的缺失访问1和情景1下的缺失访问2，第n个缺失周期的绝对时间即为n，该缺失周期当前被缺失访问占有的次数为2，其所在的缺失访问请求为缺失访问1，2. 在经过上述处理时，缺失访问2相对于缺失访问1可能会出现图8所示的3种情况. 其中行④~㉑是当缺失访问2出现如图8中的情景1和情景2时，需要将每个curr_cycle属性进行更新，根据缺失访问2的结束时间是否大于缺失访问1来决定是否需要将其进行缺失访问合并操作，而行㉓~㉖则是当缺失访问2的开始时间大于缺失访问1时，此时这2次的缺失访问无法进行合并，则对缺失访问2的每个缺失周期进行初始化后开始新一轮的合并迭代操作. 通过对缺失访问的合并操作，我们便可以清晰地获取到每个缺失周期的信息，包括该缺失周期所处的缺失访问位置及出现次数. 同样，为了更快速地判断每个缺失周期是否是纯粹缺失周期，我们对命中阶段的周期也进行了合并操作，需要注意的是，此处命中阶段的含义不仅代表命中访问所经历的时间，而且缺失访问的命中时间也应该算作命中阶段，具体算法描述如算法2所示.
算法2. 命中周期合并算法.
输入：命中阶段数组hitPhase，当前命中阶段curr，下一命中阶段next.
① while next存在 do
② if next.start \geqslant curr.start && next.start \leqslant curr.end then
③ curr.end=next.end；
④ 在hitPhase中删除next；
⑤ next=curr，++next；
⑥ else
⑦ curr=next，++next；
⑧ end if
⑨ end while
我们在对命中阶段按开始周期以递增方式进行排序后，根据下一命中阶段的开始周期是否大于当前命中阶段的结束周期来决定是否将当前2个命中阶段进行合并. 通过这样的预处理，我们可以最小化每个缺失周期与命中周期的比较次数，从而快速判断该周期是否是纯粹缺失周期. 具体算法如算法3所示.
算法3. 纯粹缺失周期的提取算法.
输入：经过算法1合并后的缺失周期数组missCycle，当前缺失周期curr_cycle，经过算法2合并后的命中阶段数组hitPhase；
输出：是否属于纯粹缺失周期.
① for each curr_cycle in missCycle[i] do
② if curr_cycle in hitPhase then
③ return false；
④ else
⑤ pureMissCycle+=curr_cycle.count；
⑥ if 当前周期未被记录总的重叠纯粹缺 失周期 then
⑦ pMissTime_overlap++；
⑧ end if
⑨ return true；
⑩ end if
⑪ end for
该PMC的判断算法通过将经过缺失访问合并后的每个缺失访问的每个缺失周期与每个命中周期进行start属性比较，若当前缺失周期的start属性与某个命中周期的start相同，则该缺失周期不是纯粹缺失周期，反之则是.
4. 实验评估
由于本文研究C-AMAT的目的是为了度量图应用的存储器性能，发掘图应用在存储器中的性能优化方向，因此，本节将通过PC-AMAT和SC-AMAT对大规模图数据集进行存储器性能测试和评估，并分析其内存性能表现.
4.1 实验环境
我们在gem5模拟器中采用了乱序超标量CPU模型，该模型支持单核模式下的分支预测和多线程执行. 为了更准确地测量缓存/内存架构设计下图应用的PC-AMAT和SC-AMAT，我们参考了WikiChip[17]和丹麦技术大学[19]最新整理的IceLake CPU架构及其参数，在gem5中增加了3级共享缓存的架构，并重新进行了缓存参数配置，以使缓存架构及其对应的Tag延时与Data延时更加接近真实的硬件环境. 对于每个图应用的测量点，我们都根据4×108个模拟指令收集了图应用的访问数据，PC-AMAT和SC-AMAT的计算及其参数都来源于对这些访问数据的处理. 具体配置情况如表1所示.
表 1 模拟器配置Table 1. Simulator Configuration模块设置 参数配置 Processor O3 CPU core, 4 GHz, 8-issue width Function units 6 IntALU: 1 cycle;1 IntMul:3-cycle;
2 FPAdd: 2-cycle; 1 FPCmp: 2-cycle;
1 FPMul: 4-cycle; 1 FPDiv: 12-cycle;
1 FPCvt: 2-cyclePrivate L1 caches 32 KB inst/ 32 KB data,8-way, 64 B line,
4-cycle tag latency inst/ 4-cycle data,
4-cycle data latency inst/ 4-cycle data,
ICache 4 MSHR entry,
DCache 4 MSHR entryPrivate L2 cache 256 KB, 8-way, 64 B line, 7-cycle tag latency,
7-cycle data latency, 20 MSHR entryShared L3 cache 8 MB, 16-way, 64 B line, 37-cycle tag latency,
38-cycle data latency, 20 MSHR entryDRAM latency/width 240-cycle access latency/64 bit 4.2 工作负载
本文使用GAP基准套件[13]，它是典型的图处理基准套件，能够有效标准化图应用的指标评估. GAP之中的图算法均使用C++编写，并使用了优化多线程技术，我们之所以选择GAP是因为它可以排除任何与框架相关的性能开销，从而真正发现图应用在存储器中的性能瓶颈. 我们选取了其中最具代表性的BFS[20]，PR[21]，BC[22]，CC[23]4种算法作为工作负载进行测试，具体算法介绍如表2所示.
表 2 图算法列表Table 2. Graph Algorithm List算法 描述 BFS 广度优先搜索算法，逐层遍历图 PR 图的链接分析，根据相邻顶点的
秩对每个顶点进行排序BC 测量顶点的中间性，即通过它的其他
任意2个顶点之间的最短路径数CC 将图分解为一组连通子图 表2中的图算法分别代表了社交网络中心、工程应用领域和科学中的诸多应用，由于不同的图算法计算方式是不同的，主要以遍历为中心和以计算为中心，并且它们对于图的属性考虑也各有侧重，因此为了更全面地评估各类图应用的存储器性能，我们采用的图数据集如表3所示.
表 3 实验数据集Table 3. Experimental Datasets4.3 负载性能测试
由于存储器系统的性能对整体性能有很大的影响，因此应该选择一个适当的指标来反映它们之间的关系. 我们使用相关系数（correlation coefficient）[15]来描述内存指标PC-AMAT，SC-AMAT，C-AMAT与IPC之间的变化相似度，并作为它们的评价精度. 相关系数的取值范围为−1~1. 相关系数的绝对值越高，代表内存指标和IPC这2个变量之间的关系就越密切[25]. 相关系数的数学定义为：
{r_{XY}} = \frac{{\displaystyle\sum {XY} - \frac{{\left(\displaystyle\sum X \right)\left(\displaystyle\sum Y \right)}}{n}}}{{\sqrt {\left[\left(\displaystyle\sum {{X^2}} - \frac{{{{\left(\displaystyle\sum X \right)}^2}}}{n}\right)\left(\displaystyle\sum {{Y^2}} - \frac{{{{\left(\displaystyle\sum Y \right)}^2}}}{n}\right)\right]} }}, (10) 相关系数是通过积差方法进行计算的，通过以2个变量与各自平均值的离差为基础，将2个变量的离差相乘来反映2个变量之间的相关程度. 其中数组X和Y是2个变量的采样点.
我们首先分别计算了当内核数量为1，2，4时对应各级cache的相关系数. 对于各级cache，这2种存储器性能指标的相关系数，如图9所示. 图9（a）显示了L1 cache上C-AMAT与PC-AMAT的相关系数的对比，我们发现随着内核数量的增加，C-AMAT的相关系数并未出现明显变化，PC-AMAT在相关系数上则始终高于C-AMAT，并且内核数量并未明显影响其相关系数变化，之所以出现这样的原因，是因为L1 cache中的数据访问命中时间是固定的，内核数量的增加对于总的数据访问周期的测量误差并没有表现出比较明显的影响，但由于PC-AMAT在数据访问时的命中时间参数选取更加准确，因此其相关系数相比C-AMAT也更高. 图9（b）（c）分别代表了L2 cache和LLC上C-AMAT和SC-AMAT的相关系数对比，随着内核数量的增加，C-AMAT的相关系数都有小幅度提升，我们分析这是由于内核数量的增加，导致数据访问并发度也随之增加，尽管L2 cache和LLC上的数据访问命中时间存在不一致性，但并发度的提升导致数据访问重叠周期也更多，掩盖了一部分数据访问周期计算过程中的误差，但其相关系数始终与SC-AMAT有一段距离.
![]()
图 9 各级cache在不同内核数量中性能指标的相关系数Figure 9. The correlations coefficients of performance indicators in each cache level with different number of cores以内核数量为4时各个图应用中IPC 与C-AMAT，PC-AMAT和SC-AMAT的相关系数为例，进一步验证了将C-AMAT的计算模型扩展为PC-AMAT和SC-AMAT的有效性与合理性，实验结果如图10所示. 从图10（a）可以看出，在几乎所有的图应用中，L1 cache中PC-AMAT的相关系数都高于C-AMAT，相比C-AMAT，PC-AMAT的相关系数提升了11.7%. 从图10（b）（c）中我们观察到，在L2 cache与LLC中，SC-AMAT在L2 cache和LLC上的相关系数分别提升了26.1%和15.8%.
![]()
图 10 各级cache性能指标的相关系数对比Figure 10. Comparison of the correlation coefficients of cache performance indicators at each level由于PC-AMAT和SC-AMAT只是在计算与测量过程中对C-AMAT进行的扩展，因此在接下来的结果评估中将不再对PC-AMAT和SC-AMAT进行区分. 我们首先将图应用运行在单核模式下，我们计算了各级cache的C-AMAT和相关的内存性能参数，整体性能表现如图11所示.
由图11可以看出，PR算法的整体内存性能表现是优于其他算法的，同时对于L1 data cache来说，各类图应用程序性能表现类似，但值得注意的是，在绝大部分算法中，L2 cache的C-AMAT都明显高于LLC，这个现象直接暴露出了L2 cache的存在对于图数据访问而言是负收益的，而导致这种现象的本质还是图计算运行过程中不规则的细粒度访存导致CPU的L2 cache和LLC的命中率极低[26].
这些图应用负载的命中并发度和缺失并发度如图12和图13所示. 命中并发度与缺失并发度是影响C-AMAT的关键因素，可以看出，单核模式下，所有图应用在L2 cache的命中并发度表现都是最低的且其值都徘徊在1附近，这进一步表明了传统L2 cache的存在对于图应用并没有多大意义，甚至影响到了整体的图应用访存时间，现代处理器中的3级缓存存储器层次结构的设计对于图应用而言负面影响较大. 为了提高图应用的命中并发度，我们可以采用多端口缓存、多bank缓存来提高命中时间的重叠；同时，为了提高缺失并发度，我们也可以通过设置合理的MSHR数量来允许更多的缺失访问相互重叠.
这些图应用的纯粹平均缺失代价如图14所示. 与命中并发度和缺失并发度类似，各类图应用在在L2 cache上所表现出来的纯粹平均缺失代价都是最高的，这也从侧面反映了L2 cache中图数据访问缺失率高，而为了避免这种现象，最简单的方式就是在L2 cache上进行旁路策略，可以有效降低总体的图数据访问时间.
多发射流水线技术是处理器微体系结构设计的一个重要改进，它允许在同一周期内取指、解码、发射、执行和提交多个指令，大幅度提高了指令集并行度. 由于算法数据依赖、分支错误预测的高额代价、负载数据约束，以及一般的功率墙限制，增加发射带宽不是一个可行的选择，所以大多数商业处理器在不同的处理阶段对每个内核采用4~8大小的带宽[27]. 为了探究发射带宽对图应用的影响，我们通过设置不同大小的发射带宽，观察了其对图数据在各级cache中访存时间的影响. 由于L1 data cache的数据访问时间最能表现图应用的存储器性能，因此这里我们只统计了不同发射带宽下L1 data cache的C-AMAT，其结果如图15所示. 可以看到，当发射带宽设置为4时，图应用的C-AMAT相较于其他数值的发射带宽都呈现出下降的趋势，访存速度最快.
![]()
图 15 不同发射带宽下L1 data cache的C-AMATFigure 15. C-AMAT of L1 data cache at different issue widths现代处理器中的非阻塞缓存为了在缓存缺失时依然能够提供数据，往往采用了失效状态保存寄存器MSHR. 对于LLC，当其MSHR表为空时，表示没有未完成的主存访问，而当MSHR表为满时，则表示缓存无法提供更多的缓存访问，将阻塞CPU对内存或下一级内存的访问. 因此，MSHR表项的数量可以直接决定缺失并发度，进而影响到C-AMAT. 我们将LLC的MSHR表项的数量分别设置为4，8，16，并对图应用的C-AMAT进行了测量，结果如图16所示. 不难发现，当MSHR表项的数量设置为8时，就已经对图应用的数据访问不再产生影响，因此尽管图数据在LLC上的缺失率很高，但图应用在LLC数据访问总占比是极低的，尤其是单核模式下，MSHR表项的数量的设置越大对于图应用而言意义不大，对于图应用而言LLC的MSHR表项的数量设置在4~8已足够使用，不必再浪费额外的硬件资源.
指令集并行技术带来的图应用访存性能的提升仍存在很大的限制，增加每个CPU内核数量是提高系统总体性能的最直接和最高效的手段. 我们将内核数量进行了倍增，将图应用在L1 data cache的C-AMAT进行了统计分析，实验结果如图17所示. 内核数量的增加明显降低了图应用的C-AMAT，但并不总是如此，尤其对于PR算法而言，在其中3个数据集中双核CPU下的L1 data cache的C-AMAT相对于单核反而出现上升，我们推测产生这种现象是由于图应用中加载指令之间的依赖链过短，从而导致了流水线的断流和低内存级并行. 但总的来说，多核CPU在处理图应用过程中所表现的存储器性能依然是要高于单核CPU的.
![]()
图 17 不同内核数量下L1 data cache的C-AMATFigure 17. C-AMAT of L1 data dcache at different number of cores5. 总 结
图计算应用拥有特有的不规则执行行为，其引发的不规则负载和不规则访问是加速图应用面临的主要挑战之一. 认识图应用高度复杂的存储系统的局部性信息和并发性信息对于加速图计算架构设计至关重要. C-AMAT可以有效表征应用程序运行过程中高度复杂的存储系统的局部性和并发性的信息，但是其计算模型没有考虑cache层的访问方式，原始测量装置硬件开销巨大. 因此本文基于不同cache层的访问结构，对C-AMAT的计算模型扩展为PC-AMAT和SC-AMAT，并在此基础上设计并实现了纯粹缺失周期提取算法及各参数的测量与计算，能够有效实现C-AMAT的测量. 实验结果表明，在单核和多核模式下，PC-AMAT和SC-AMAT与IPC之间的相关性比C-AMAT与IPC的相关性更强，在4核模式下，L1 cache中PC-AMAT相比C-AMAT的相关系数提升了11.7%，SC-AMAT在L2 cache和LLC上的相关系数分别提升了26.1%和15.8%. 最终，我们通过更改相关的硬件配置利用C-AMAT评估和分析了图应用在存储器中的访存性能，并提出了相应的访存优化策略. 我们的下一步工作将根据如何提高图应用的命中并发度和缺失并发度，以及如何降低图应用的纯粹缺失率展开，拟从cache层面优化图应用的存储器性能.
作者贡献声明：陈炳彰提出算法思路和实验方案，并完成实验与论文撰写；刘伟指导方案设计并修改论文；于萧钰协助论文修改.
-
![]()
图 9 各级cache在不同内核数量中性能指标的相关系数
Figure 9. The correlations coefficients of performance indicators in each cache level with different number of cores
![]()
图 10 各级cache性能指标的相关系数对比
Figure 10. Comparison of the correlation coefficients of cache performance indicators at each level
![]()
图 15 不同发射带宽下L1 data cache的C-AMAT
Figure 15. C-AMAT of L1 data cache at different issue widths
![]()
图 17 不同内核数量下L1 data cache的C-AMAT
Figure 17. C-AMAT of L1 data dcache at different number of cores
表 1 模拟器配置
Table 1 Simulator Configuration
模块设置 参数配置 Processor O3 CPU core, 4 GHz, 8-issue width Function units 6 IntALU: 1 cycle;1 IntMul:3-cycle;
2 FPAdd: 2-cycle; 1 FPCmp: 2-cycle;
1 FPMul: 4-cycle; 1 FPDiv: 12-cycle;
1 FPCvt: 2-cyclePrivate L1 caches 32 KB inst/ 32 KB data,8-way, 64 B line,
4-cycle tag latency inst/ 4-cycle data,
4-cycle data latency inst/ 4-cycle data,
ICache 4 MSHR entry,
DCache 4 MSHR entryPrivate L2 cache 256 KB, 8-way, 64 B line, 7-cycle tag latency,
7-cycle data latency, 20 MSHR entryShared L3 cache 8 MB, 16-way, 64 B line, 37-cycle tag latency,
38-cycle data latency, 20 MSHR entryDRAM latency/width 240-cycle access latency/64 bit 
下载: 导出CSV
表 2 图算法列表
Table 2 Graph Algorithm List
算法 描述 BFS 广度优先搜索算法，逐层遍历图 PR 图的链接分析，根据相邻顶点的
秩对每个顶点进行排序BC 测量顶点的中间性，即通过它的其他
任意2个顶点之间的最短路径数CC 将图分解为一组连通子图
下载: 导出CSV
-
[1] Basak A, Li Shuangchen, Hu Xing, et al. Analysis and optimization of the memory hierarchy for graph processing workloads[C]// Proc of the 25th IEEE Int Symp on High Performance Computer Architecture (HPCA). Piscataway, NJ: IEEE, 2019: 373−386
[2] Sun Xianhe, Wang Dawei. Concurrent average memory access time[J]. Computer, 2013, 47(5): 74−80
[3] Binkert N, Beckmann B, Black G, et al. The gem5 simulator[J]. SIGARCH Computer Architecture News, 2011, 39(2): 1−7 doi: 10.1145/2024716.2024718
[4] Beutel A, Akoglu L, Faloutsos C. Graph-based user behavior modeling: From prediction to fraud detection[C]// Proc of the 21st ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2015: 2309−2310
[5] Barabási A L, Albert R. Emergence of scaling in random networks[J]. Science, 1999, 286(5439): 509−512 doi: 10.1126/science.286.5439.509
[6] 孙相征,张云泉,王婷,等. 对角线稀疏矩阵的 SpMV 自适应性能优化[J]. 计算机研究与发展,2013,50(3):648−656 Sun Xiangzheng, Zhang Yunquan, Wang Ting, et al. Auto- tuning of SpMV for diagonal sparse matrices[J]. Journal of Computer Research and Development, 2013, 50(3): 648−656 (in Chinese)
[7] Balaji V, Crago N, Jaleel A, et al. P-opt: Practical optimal cache replacement for graph analytics[C]// Proc of the 27th IEEE Int Symp on High Performance Computer Architecture (HPCA). Piscataway, NJ: IEEE, 2021: 668−681
[8] 汤嘉武,郑龙,廖小飞,等. 面向高性能图计算的高效高层次综合方法[J]. 计算机研究与发展,2021,58(3):467−478 doi: 10.7544/issn1000-1239.2021.20190679 Tang Jiawu, Zheng Long, Liao Xiaofei, et al. Effective high-level synthesis for high-performance graph processing[J]. Journal of Computer Research and Development, 2021, 58(3): 467−478 (in Chinese) doi: 10.7544/issn1000-1239.2021.20190679
[9] Faldu P, Diamond J, Grot B. Domain-specialized cache management for graph analytics[C]// Proc of the 26th IEEE Int Symp on High Performance Computer Architecture (HPCA). Piscataway, NJ: IEEE, 2020: 234−248
[10] Cooksey R, Jourdan S, Grunwald D. A stateless, content-directed data prefetching mechanism[J]. ACM SIGPLAN Notices, 2002, 37(10): 279−290 doi: 10.1145/605432.605427
[11] Agarwal A, Roy K, Vijaykumar T N. Exploring high bandwidth pipelined cache architecture for scaled technology[C]// Proc of the 6th Design, Automation and Test in Europe Conf and Exhibition. Piscataway, NJ: IEEE, 2003: 778−783
[12] Kroft D. Lockup-free instruction fetch/prefetch cache organization[C]// Proc of the 25th Int Symp on Computer Architecture. New York: ACM, 1998: 195−201
[13] Beamer S, Asanović K, Patterson D. The GAP benchmark suite[J]. arXiv preprint, arXiv: 1508. 03619, 2015
[14] Wang Dawei, Sun Xianhe. APC: A novel memory metric and measurement methodology for modern memory systems[J]. IEEE Transactions on Computers, 2013, 63(7): 1626−1639
[15] Soltis D, Gibson M. Itanium 2 processor microarchitecture overview[C]// Proc of the 14th Hot Chips. Los Alamitos: IEEE Computer Society, 2002: 44−54
[16] 姚永斌. 超标量处理器设计[M]. 北京:清华大学出版社,2014 Yao Yongbin. Superscalar Processor Design[M]. Beijing: Tsinghua University Press, 2014 (in Chinese)
[17] Gold X. 6130-Intel-WikiChip[EB/OL]. [2022-07-16].https://en.wikichip.org/ wiki/WikiChip
[18] 孙贤和. C-AMAT:大数据时代的数据存取模型[J]. 中国计算机学会通讯,2014,10(6):19−22 Sun Xianhe. C-AMAT: Data access model in the age of big data[J]. Communications of the CCF, 2014, 10(6): 19−22 (in Chinese)
[19] Fog A. The Microarchitecture of Intel, AMD and VIA CPUs : An optimization guide for assembly programmers and compiler makers[R]. Denmark: Copenhagen University College of Engineering, 2022
[20] Beamer S, Asanovic K, Patterson D. Direction-optimizing breadth-first search[C/OL]// Proc of the 12th Int Conf on High Performance Computing, Networking, Storage and Analysis. Piscataway, NJ: IEEE, 2012 [2022-07-16]. https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=646845 8
[21] Brin S, Page L. The anatomy of a large-scale hypertextual web search engine[J]. Computer Networks and ISDN Systems, 1998, 30(1-7): 107−117 doi: 10.1016/S0169-7552(98)00110-X
[22] Madduri K, Ediger D, Jiang K, et al. A faster parallel algorithm and efficient multithreaded implementations for evaluating betweenness centrality on massive datasets[C]// Proc of the 23rd IEEE Int Symp on Parallel & Distributed Processing. Piscataway, NJ: IEEE, 2009: 1−8
[23] Sutton M, Ben-Nun T, Barak A. Optimizing parallel graph connectivity computation via subgraph sampling[C]// Proc of the 32nd IEEE Int Parallel and Distributed Processing Symp (IPDPS). Piscataway, NJ: IEEE, 2018: 12−21
[24] da Rosa Righi R, Lehmann M, Gomes M M, et al. A survey on global management view: Toward combining system monitoring, resource management, and load prediction[J]. Journal of Grid Computing, 2019, 17(9): 473−502
[25] VanVoorhis C R W, Morgan B L. Understanding power and rules of thumb for determining sample sizes[J]. Tutorials in Quantitative Methods for Psychology, 2007, 3(2): 43−50 doi: 10.20982/tqmp.03.2.p043
[26] 叶楠,郝子宇,郑方,等. BFS算法与众核处理器的适应性研究[J]. 计算机研究与发展,2015,52(5):1187−1197 doi: 10.7544/issn1000-1239.2015.20140004 Ye Nan, Hao Ziyu, Zheng Fang, et al. Adaptability of BFS algorithm and many-core processor[J]. Journal of Computer Research and Development, 2015, 52(5): 1187−1197 (in Chinese) doi: 10.7544/issn1000-1239.2015.20140004
[27] Hennessy J L, Patterson D A. Computer Architecture: A Quantitative Approach[M]. Amsterdam: Elsevier, 2011
计量
- 文章访问数: 345
- HTML全文浏览量: 30
- PDF下载量: 91
