0.论文信息

文章来自IEEE Transactions on Parallel and Distributed Systems，TPDS，2023
Exploring Memory Access Similarity to Improve Irregular Application Performance for Distributed

所有作者及单位

Wenjie Liu， Xubin He，美国宾夕法尼亚州费城天普大学计算机与信息科学系
Qing Liu，美国新泽西州纽瓦克市新泽西理工学院电气与计算机工程系

1.Background

stacked DRAM and off-chip DRAM的异构。
并行工作模式使得在高性能集群上产生跨节点的不规则内存访问行为（memory access behaviors，MAB）。
但是执行共享功能或者数据结构时，节点间会产生相似的MAB。

工作节点之间内存访问相似性的示例。每个工作节点执行共享二进制代码的不同部分, 创建MAB的各种组合。如图所示,两个节点之间的相似性是通过重叠的MAB以及每个MAB覆盖的页面数量来估计的,例如,节点K和节点S共享相同的MAB并产生高相似性。

最常用的6个MAB所覆盖的内存页的细分。可以得出三个观察结果。首先, MAB,例如MAB 0,可以被所有节点共享为执行相同的二进制代码。
第二，在节点3.4.6.7.8.11.12.13上观察到相同的MAB组合;因为这样的节点可以执行相同的任务。第三, ~~MAB 5仅在节点14.上显示~~ ，并且大量页面被MAB 5覆盖,这意味着相似性不仅存在于节点之间，而且存在于节点内的多个页面之间。

2.解决的问题（Motivation）

为了利用堆叠DRAM实现的高性能，设计高效混合存储器系统的核心是两个挑战。

第一个挑战是确定运行时的最佳数据位置。
第二个挑战是减少元数据造成的开销。下图比较了现有技术的堆叠DRAM命中率和元数据导致的相应性能下降。如图所示，最先进的方法不断提高堆叠DRAM命中率。同时,对于不规则的HPC应用程序,元数据导致的性能开销显著增加，这降低了堆叠DRAM带来的性能增益。

3.其他学者解决这个问题的思路和缺陷

现有的方法通过利用每个数据块的访问历史[7] [8] [9]或操作系统[10] [11]提供的提示来识别热数据，这些提示忽略了由集群的并行工作模式启用的共享MAB,并且可能在集群环境中表现不佳。

[7] C. C. Chou, A. Jaleel, and M. K. Qureshi, “CAMEO: A two-level memory organization with capacity of main memory and flexibility of hardware-managed cache,” in Proc. IEEE/ACM 47th Annu. Int. Symp. Microarchitecture, 2014, pp. 1–12.
[8] J. B. Kotra, H. Zhang, A. R. Alameldeen, C. Wilkerson, and M. T. Kandemir, “Chameleon: A dynamically reconfigurable heterogeneous memory system,” in Proc. IEEE/ACM 47th Annu. Int. Symp. Microarchitecture, 2018, Art. no. 533.
[9] E. Vasilakis, V. Papaefstathiou, P. Trancoso, and I. Sourdis, “Hybrid2: Combining caching and migration in hybrid memory systems,” in Proc. IEEE Int. Symp. High Perform. Comput. Architecture, 2020, pp. 649–662.
[10] A. Kokolis, D. Skarlatos, and J. Torrellas, “PageSeer: Using page walks to trigger page swaps in hybrid memory systems,” in Proc. IEEE Int. Symp. High Perform. Comput. Architecture, 2019, pp. 596–608.
[11] A. Prodromou, M. Meswani, N. Jayasena, G. Loh, and D. M. Tullsen, “MemPod: A clustered architecture for efficient and scalable migration in flat address space multi-level memories,” in Proc. IEEE Int. Symp. High Perform. Comput. Architecture, 2017, pp. 433–444.

针对不规则应用的优化。现有的研究针对不规则应用, 要么将不规则性暴露给作业调度器进行自适应调度[31] ,[32] ,要么利用不规则性在异构集群中进行更好的资源分配[33] [34]。Nozal等人提出在使用OneAPI框架执行不规则应用程序时，平衡分配给不同硬件的负载[31]。此外, Dai等人在运行时检测不均匀分布的不规则工作负载, 并将不堪重负的节点的工作负载迁移到分配较少工作负载的节点[32]。另一方面,利用不规则性来细化集群中的资源分配。杨等人观察了集群中运行的不规则应用程序导致的随机和不规则网络流量,并提出利用数据压缩技术来最大限度地减少网络带宽消耗[34]。此外, Shin等人分析了GPU上运行的不规则应用程序导致的性能下降,并提出加快地址转换过程，以最大限度地减少SIMD指令的数据准备时间[33]。

系统中的相似性。相似之处存在于许多方面各方面的计算系统, 以及先前的工作探讨了相似性以提高系统性能。Koller等人提出了一种基于观察到的存储和访问数据的高度相似的I/O内容的I/O重复数据消除方法[35]。同时,Xiao等人利用高级程序中丰富的自相似性来加速芯片之间的数据通信[36]。刘等人利用集群的并行工作模式,提出了提高掉队性能的方法。

混合存储器系统。现有工程确定热点通过监视每个数据块的存储器访问行为或依赖于操作系统发现的信息来获取数据。通过监测每个数据块的内存访问行为, 可以使用获得的访问行为来识别下面访问的缓存行，并且可以执行准确的数据迁移/缓存[7]、[8]、[9]。另一方面,Prodromou等人提出利用操作系统观察到的内存访问行为，并使用多数元素算法来预测热页[1]。此外,研究人员将计算能力集成到堆叠的DRAM中，这进一步减少了内存流量,并为内存密集型应用提供了更高的效率[37] ,[38]。

4.围绕该问题作者如何构建解决思路（Design）

4.1 Similarity Monitor

提出了一种量化方法来测量节点之间的内存访问相似度，
将来自所有节点的MAB聚合为全局内存访问行为向量(GMABV) ,生成每节点内存访问行为矢量(PMABV) ，并计算PMABV之间的距离作为相似性。

比较两种共享方案，全局共享无法为不规则应用提供高的共享精度，因为并非每个MAB都对其他节点有帮助。相反,选择性共享按需共享MAB,这会给部署的节点带来性能开销。由于MAB共享不准确,这两种方法都存在性能损失，GS和SS的性能损失分别高达13.1%和15.4%，这表明在不规则应用的情况下需要一种有效的MAB共享方案。

# Similarity-Based Sharing
Input: Receiving access behavior AccBhv from node k
	if AccBhv in GMABV then
		if node k belongs to a Similarity Group then
			Forward AccBhv to nodes within the group with global sharing
	else
		Perform selective sharing with all Low Similarity nodes
	end if
	Update metadata
	else
	Update PMABV , GMABV and Similarity Matrix
	end if

4.2 Access Behavior Buffer

根据SMABS的设计，节点之间只共享当前工作集的MAB，这减轻了每个节点上MAB监控带来的开销。此外，由于每个节点处理的大量结构化数据和HPC应用程序中丰富的循环，跨节点的多个内存页共享相同的MAB。因此，即使是单个共享MAB也可以描述相应节点内多个页面的访问行为。

如图访问行为缓冲区的一个条目。状态和覆盖比特都确定新观察到的MAB是否将被发送到相似性监视器以进行相似性更新。而起始地址和覆盖页是用来快速识别内存请求的滑动窗口部分。

4.3 Swap Executor

为了利用访问行为缓冲区中缓冲的M4B,交换执行器用于通过使用共享M4B作为“配方”来执行底层混合存储器系统的数据放置。

4.4 SM-HMS Overview

5.从结果看，作者如何有力证明他解决了问题

在模拟器上运行的，首先是作业完成时间比较：

之后是IPC比较：

还讨论了相应的参数敏感性、堆叠命中率（不过这都是针对片内DRAM的了）延迟和带宽的收益应该是来自于共享吧。之后容量占用之类的数据都很好，不放图片了。

我们对由多达256个节点组成的各种集群配置上的一组不规则应用程序的评估结果表明， SM-HMS在完成时间减少方面优于最先进的方法Cameo、Chameleon和Hyrbid2 ，分别减少了58.6%、56.7%和31.3%，平均减少了46.1%、41 .6%和19.3%。与理想的混合存储系统相比， SM-HMS的效率高达98.6%(平均91.9% )。此外,在常规应用.上的实验表明，所提出的
SM-HMS有利于更广泛的HPC应用。