异构存储器负载平衡意识的数据放置管理系统paddiser

204××→→异构存储器上的数据放置：具有负载平衡意识的摘要镇谢zhen. anl.gov加州大学默塞德分校阿贡国家实验室李佳佳jiajia.li邮件ncsu.edu北卡罗来纳州立大学街六jliu279@ucmerced.edu加州大学默塞德东里dli35@ucmerced.edu加州大学默塞德CCS概念：·计算机系统组织→异构存储器的出现为高性能计算应用提供了一种经济高效的解决方案。 决定HM上数据对象的位置对于高性能至关重要。 我们揭示了HM上的数据放置相关的性能问题。在任务并行的高性能计算应用中，任务间的负载不平衡是一个突出的问题问题的根源在于没有意识到并行任务的语义，以及错误地假设将频繁访问的页面放到快速内存中总是会带来更好的性能。为了解决这个问题，我们引入了一个负载平衡感知的页面管理系统，命名为paddiser。Merchan-diser在内存分析期间引入了任务语义，而不是与应用程序无关。利用有限的任务语义，调度器有效地建立了任务之间的协调，使用HM快速完成所有任务，而不是只考虑任何单个任务。Merchan-diser是高度自动化的，以实现高可用性。 与内存消耗HPC应用程序进行评估，我们表明，与基于硬件的解决方案和行业质量的基于软件的解决方案相比，Advertiser减少了负载不平衡，并导致平均17.1%和15.4%（高达26.0%和23.2%）的性能提高。允许免费制作本作品的全部或部分的数字或硬拷贝，以供个人或课堂使用，前提是制作或分发副本的目的不是为了盈利或商业利益，并且副本的第一页上有本声明和完整的引用必须尊重作者以外的其他人拥有的本作品组件的版权允许使用学分进行摘要以其他方式复制、重新发布、在服务器上发布或重新分发到列表中，需要事先获得特定许可和/或付费。请求权限请发邮件至permissions@acm.org。PPoPP©2023版权归所有者/作者所有。 授权给ACM的出版权。ACM ISBN 979-8-4007-0015-6/23/02。. . 15美元https://doi.org/10.1145/3572848.3577497异构（混合）系统;·计算理论并行计算模型;·硬件非易失性存储器。关键词：数据放置，异构内存，并行计算，负载平衡ACM参考格式：谢震，刘杰，李佳佳，李冬。2023年异构存储器上的数据放置与负载平衡意识的任务并行HPC应用在第28届ACM SIGPLAN年度并行编程原理与实践研讨会（PPoPP '23）上，2023年2月25日至3月1日，加拿大蒙特利尔。 ACM ， 纽 约 州 纽 约 市 ， 美 国 ， 14 页 。https://doi.org/10.1145/3572848的网站上下载。35774971引言许多高性能计算（HPC）应用程序正在变得消耗内存。例如，密度重整化群（DMRG）[6，77]，一种用于获得量子多体系统的低能物理的数值算法，可以消耗1。在单台机器上使用271 TB内存320 320 [21，46]。为了满足这些应用对存储器的需求，大存储系统应运而生。这种系统的一个示例是构建在八个NUMA 节点上并提供高达 12 TB内存的Amazon EC2 HighMemoryInstance [31]。大型内存系统通常是异构的，这意味着具有不同延迟和带宽的多个内存组件形成主存。HM提出了数据放置问题。 由于快速存储器的容量较小，而慢速存储器的性能相对较差，因此必须在快速存储器和慢速存储器之间分配和迁移存储器页面，使得大部分存储器访问可以在快速存储器中进行以获得高性能。已经表明，一些HPC应用程序可能遭受高达5。7性能损失（与使用快速内存解决方案相比），HM上的数据放置不理想[61，63，67，84]。205PPoPP许多解决方案[19，25，33，34，41，54，84，86]都使用了分析引导优化（PGO）方法来解决HM上的数据放置问题。 这些解决方案通过周期性地对存储器页面进行采样并跟踪对它们的存储器访问来识别频繁访问的存储器页面（“热页面”）。然后，热页迁移到快速内存以获得更好的性能。这些解决方案与应用无关，这意味着它们不需要应用知识或更改应用。 这些解决方案的成功是基于一个隐含的假设，即将热页放在快速内存中总是会带来更好的性能。然而，我们发现，这是不正确的许多任务并行HPC应用程序。任务并行程序在HPC中很常见任务并行程序可以是基于MPI的，每个MPI进程执行一个任务。 它可以是基于OpenMP的，每个OpenMP线程执行一个任务。任务之间存在同步，其中任务必须在继续进行其余计算之前到达同步点。由于任务之间的同步性，快速完成所有任务而不是快速完成单个任务是高性能的关键HM上的PGO不能很好地用于任务并行应用。他们缺乏“快速完成所有任务”以获得高绩效的观点。 它们将热页迁移并放置到快速内存中，但不考虑哪个任务访问这些内存页。因此，现有的努力可能会引入负载不平衡：一个任务不必要地比其他任务更早到达同步点，并等待其他任务完成，因为该任务的许多页面驻留在快速存储器中，导致其执行时间更短为了揭示HM上的负载不平衡问题，我们研究了基于Optane的HM上的五个HPC应用该HM由192GB DRAM和1. 5TB Optane [32]. 我们研究了两种代表性的解决方案：行业质量的软件解决方案（Intel MemoryOptimizer [16]）和硬件解决方案（Optane的内存模式）。 我们有两个观察结果（详见评估部分的图5）。与在同构内存上运行相比，在HM上运行增加了任务之间的性能差异平均而言，任务之 间 的 性 能 差 异 增 加 了 17% 和 16% （ 分 别 使 用MemoryOptimizer 和 Memory Mode 时 ） ， 这 表 明 在HM上使用MemoryOptimizer和Memory Mode后，负载更不平衡。性能改进是最小的使用内存优化和内存模式后 性能改进仅为4. 32%和3。71%（与仅使用Optane相比），因为整体性能受到最慢任务的阻碍。造成上述绩效问题的根本原因有两个。首先，PGO解决方案（如MemoryOptimizer）不知道任务并行性。任务之间缺乏协调以共享有限的快速存储器空间。该空间是根据对任务中的热页的机会性检测来分配给任务的，而不是根据对使用快速存储器执行任务的潜在性能优势进行性能分析。它可能会不公平地将一个任务中的太多页面放置到快速内存中，导致负载不平衡。第二，PGO解决方案使用基于随机页面随机采样可以有效地避免在大型内存系统中分析所有内存页面的大量开销但是，它可能会从一个任务中收集许多内存访问，这会导致该任务的太多页面迁移到快速内存中，从而导致负载不平衡。为了解决这个问题，我们引入了一个负载平衡感知的数据放置系统HM，命名为Advertiser在内存分析过程中，任务语义被引入.这意味着在性能分析期间，Replodiser将内存访问与任务相关联，而不是与应用程序无关。通过使用有限的任务语义，调度器有效地在HM的使用上建立了任务之间的协调此外，Paddiser使用历史的，细粒度的分析，任务的结果，以指导数据的位置，为后续执行相同的任务与新的输入。然而，要实现可持续发展，我们面临两个挑战。首先，在程序执行期间任务的输入问题可以变化，并且从一个输入收集的历史分析结果不能直接用于预测另一个输入的性能，因为存储器访问次数的差异。其次，如何在任务之间划分快速存储空间是具有挑战性的。 除非所有任务都具有相同的内存访问模式和数据对象大小，否则无法在任务之间均匀共享快速内存。我们必须决定每个任务与新的输入，哪些对象应该被放置在快速内存中，而无需先验知识的内存访问对象的数量我们还必须预测迁移后任务的执行时间，以便量化和评估负载平衡的有效性。为了解决处理新输入问题的第一个挑战，数据库管理员根据数据对象的内存访问模式对数据对象进行分类，基于此，数据库管理员分析得出新输入问题的主存访问次数。在许多HPC应用程序中，对于给定任务的输入问题，存储器访问模式大多是不变的，从而提供关于存储器访问次数的可靠指示。 我们还认识到内存访问模式的影响的差异，并估计数量对不同的模式进行不同的内存访问基于估计的内存访问，当一部分内存访问发生在快内存中，而其余的内存访问发生在慢内存中时，该算法引入性能模型来预测任务的执行我们的性能建模的新颖性在于不同的数据放置的任务之间的性能相关性的建模。特别地，性能建模将数据放置的性能作为输入，然后预测另一个数据放置的性能。性能建模建立了上述两个性能之间的相关性，··任务并行HPC应用的HM数据布局PPoPP206××××∗∗任务特征任务的特点表示和量化使用的几个性能事件，从只有一个特定的数据放置执行收集。为了解决第二个挑战，决定哪些页面应该被迁移到快速内存的并行任务，我们引入了一个贪婪的启发式算法来决定如何分配快速内存空间之间的任务，以最大化(a) 基于MPI的App （DMRG）1分块Hamilton算子2每个MPI秩得到一个块3块具有其输入数据（H，PSI）4对于扫描in扫描：5S1：Constructproblem6S2：解决戴维森函数7S3：应用SVD更新（H，PSI）8交换边界和同步。(b) 基于OpenMP的App （SpGEMM）1对于（A* B）在应用中：2按行将A划分为bin3每个bin都有其大小和NNZ4#pragma ompparallel5{T1：C的计算NNZ6同步点17T2：C计算C值8同步点2}所有任务的性能优势（而不是单个任务）。该算法根据性能模型改变快存访问的部分，以找到负载平衡的解决方案。总之，我们做出了以下贡献。我们确定了一个新的性能问题HM。我们在分析过程中引入任务语义，以实现对任何数据放置的准确性能预测，并使用贪婪的启发式算法来指导HM上各种数据放置的Advertiser使用具有高可用性的自动化工作流程与基于Optane的HM上的基于硬件的解决方案（Optane中的内存模式 ） 和 行 业 质 量 的 基 于 软 件 的 解 决 方 案（MemoryOptimizer [16]）相比，它大大降低了负载不平 衡 ， 并 导 致 平 均 17.1% 和 15.4% （ 高 达 26.0% 和23.2%）的性能改进。2背景异构存储器（HM）。我们使用Intel Optane Per-sistent Memory（PM）和DRAM作为HM的一个例子.随着其他技术（如CXL [11]和高带宽存储器）的出现，HM正在成为一种趋势。PM和DRAM之间存在性能差异。在Optane PM 100系列中，PM上顺序和随机读取的存储器延迟为2。08和3。77比DRAM上长; PM上读写的峰值内存带宽为3. 87和4。74比DRAM低[36，64]。PM模块可以配置为应用程序直接模式或内存模式。通过应用程序直接模式，软件显式控制内存页面在PM和DRAM上的位置在内存模式下，DRAM作为一个直接映射的回写缓存到PM，并由硬件管理。Merchan- diser是一个软件解决方案，因此它使用应用程序直接模式。内存模式的性能优于内存模式。HM上的数据放置现有的解决方案[2，15，33，34，41，60]操纵页表条目（PTE）用于存储器剖析以检测热页。它们反复扫描PTE或拦截页面保护故障，以检查PTE中的特定位是否被硬件更改 如果是，则记录存储器访问，并且复位该位以用于将来的剖析。 使用这种方法可以准确地捕获内存访问。 但是，它很慢（需要几秒钟来分析数百GB的内存），并且无法捕获不同的工作负载行为。为了避免长时间的分析，在地址空间中对页面进行采样以进行分析是很自然的然而，所有任务的非歧视性页面采样可能导致负载不平衡。图1.任务并行HPC应用程序的两个示例。（NNZ =非零元素的数量任务并行HPC应用程序。 我们研究任务并行HPC应用程序[22]。在这样的应用程序中，多个任务并行运行，并且通常基于MPI或OpenMP。在基于MPI的应用程序中，每个MPI进程处理一个任务，而在基于OpenMP的应用程序中，并行区域中的每个OpenMP线程处理一个任务。此外，任务可以重复执行，并且每次执行可以使用不同的输入。 我们将任务的每次执行称为任务实例。图1.a给出了一个基于MPI的任务并行应用程序DMRG的示例 [6，21，77]。在DMRG中，首先将哈密尔顿矩阵划分为多个块，每个块分配给一个MPI进程（第1-3行）。然后，每个MPI进程运行一个计算循环，使用分配的块状态（Block）和矩阵乘积状态（Matrix Product State）作为输入迭代地运行DMRG算法（第5-7行）。循环的迭代被视为任务实例。 因此，MPI进程中的任务被重复执行。任务实例使用相同但不同的作为输入。在每次迭代结束时，MPI进程之间存在图1.b给出了Ginkgo [5]中基于OpenMP的任务并行应用程序SpGEMM（ = ） 在本例中，主循环运行多个SpGEMM（=）。 在主循环的每次迭代中， 首先按行划分为bin，然后有一个OpenMP并行区域，每个线程访问 bin 并产生一部分 。在循环的一次迭代中，一个线程在一个任务实例上工作，在下一次迭代中，这个线程在另一个任务实例上工作，但使用不同的 和 。在OpenMP区域的末尾，存在线程之间的隐式同步我们假设，对于给定的任务，算法或记忆访问模式在任务实例之间不改变例如，在图1.a中，在MPI进程中，无论如何，当输入数据（输入数据）改变时，第5-7行中的算法和内存访问模式保持不变。然而，如果跨任务实例的算法或存储器访问模式有变化，则这些任务实例应被分类为不同的任务。3概述如图2所示，HMDISER使用性能建模来指导HM中的数据放置性能建模使用任务信息作为输入，其中包括执行···PPoPPZhen Xie，Jie Liu，Jiajia Li，andDong Li207图2. 一个概述的martiser。任务程序中的基本块的时间和运行时性能事件对于决定任务对数据放置的性能敏感度至关重要。在任务的第一实例中使用输入问题（称为基本输入）收集任务信息，并由性能建模使用以预测HM上的各种数据放置下的相同任务对于新输入的性能。 性能模型被集成到一个运行时系统中，以决定数据迁移是否会导致任务之间的负载不平衡。为了准确地预测具有新输入的任务的执行时间，我们的性能建模首先估计具有新输入的数据对象的内存访问次数（参见第4节）。 该方法首先通过静态分析对数据对象级的内存访问模式进行分析，然后根据数据对象大小、从基本输入中收集的内存访问次数和内存访问模式进行估计。性能建模预测任务的执行时间与一个新的输入下的各种数据放置在HM。该预测使用估计的存储器访问次数、工作负载特性和同构存储器上的执行时间预测（即，仅限PM或DRAM）（参见第5节）。 工作负载特征是基于每个事件对预测准确性的贡献的量化从性能事件中选择的。同构存储器上的执行时间预测建立在对输入无关基本块的静态分析和离线剖析的基础上。Replodiser有一个运行时系统，它使用性能建模来决定是否应该使用负载平衡感知进行数据迁移（参见第6节）。在任务执行之前，运行时首先采用启发式算法来决定多少快速内存访问应该发生在每个任务的性能模型的基础上 。 然后， 利 用 现 有 解 决 方 案 中 的 存 储 器 剖 析 机 制 ，Replodiser确定是否应该将对应于每个任务的页面从慢速存储器迁移到快速存储器。4输入感知的存储器访问量化针对一个新的输入问题，估计对数据对象的内存访问是一个挑战.在不使用大量和昂贵的内存分析的情况下，如何捕获缓存对主存访问的影响以及如何进行估计而不与架构细节紧密耦合以实现高可用性是具有挑战性的。我们的解决方案突出了两个基本的创新：（1）使用有限的内存分析与基础输入来指导估计，这是有用的，以简化估计方法，提高可用性;（2）区分内存访问模式，这是有用的，以捕捉缓存效果，提高估计质量。我们的估计方法有三个步骤：（1）使用用户API来指定HM上管理的数据对象，（2）对任务中这些对象的内存访问模式进行分类，以及（3）估计内存访问计数。用户API。 在任务并行HPC应用程序中，大多数数据访问发生在几个主要的数据对象上。 例如������������，图1.a（DMRG） ������和图1.b（SpGEMM）。配置器负责放置用户通过API指定的数据对象。我们假设数据对象大小在运行时期间的任务执行之前是已知的（例如，图1.a中的第3行和图1.b中的第3行）。 这种假设在许多HPC应用中通常是正确的[4，44，57，75，79-81]。Paddiser希望用户使用以下API指定要管理的数据对象void *LB_HM_config（void* objects，int* sizes），其中*objects指向要管理以进行分析和迁移的用户指定的数据对象列表，*sizes指向到它们的大小的列表（例如，DMRG的PSI数组长度数据对象的大小可以是变量，它们的值在任务执行之前就已经知道了 API在任务执行之前被放置在程序中。 在DMRG和SpGEMM的示例中，API分别位于图1.a和图1.b中的第5行和第4行之前。请注意，用户在使用API时不需要了解哪些数据对象会导致负载不平衡 任何数据对象都可以传递给API。存储器访问模式的分类。我们执行对象级的内存访问模式分析的数据对象指定的用户，并将内存访问分为四个模式。这些模式用以下代码（作为循环的主体）描述，其中，Rk是循环归纳变量：• 流：A[i] = B[i] + C[i]• 步幅：A[i*stride] = B[i*stride]• Stenosis：A[i]=A[i−1]+ A[i+1]• 随机：A[i] = B[C[i]]流模式表现为遍历循环中的任何数组，其中索引由循环归纳确定。该模式还包括增量模式（例如，A[i]= A[i]+ d），减少（例如，x = x + A[i]）和转置（例如，A[i][j]= B[j][i]）。 步幅模式是流模式的更一般的情况，其中步幅是从应用知识已知的常数。模板模式涉及在循环的迭代之间顺序访问数组，例如Jacobi中使用的7点模板性能建模使用新输入性能预测基于采样热门页面检测数据迁移数据放置业绩决策预测任务N...任务2同步任务1企业任务应用启发式算法工作量特性分析模型输入感知的存储器访问量化静态分析访问模式分类存储器访问估计基极输入数据迁移任务并行HPC应用的HM数据布局PPoPP208×表1.在五个应用程序中检测到访问模式应用SpGEMM WarpXBFSDMRG公司简介接入模式流随机跨步模板流随机流跨步流随机和高斯-赛德尔核[38]。随机模式包括使用间接寻址的指针追踪、聚集（诸如A[i]中的B = B[C[i]]）和分散（诸如A[B[i]]中的A = C[i]）。我们使用Spindle [83]来识别这些模式。 Spindle是一个基于LLVM的静态分析工具。 它通过提取与存储器访问指令相关的结构信息来识别数据对象级别的存储器访问模式。在我们的评估中（见表1和表2），这些模式存在于主要的数据对象中，占应用程序内存消耗的至少98%。内存访问计数的估计 给定一个任务，我们在任务的第一次执行期间（使用基本输入）测量数据对象级别的内存访问次数。然后，我们估计的内存访问的数量为后续执行相同的任务与新的输入，基于内存访问的测量。要使用基本输入进行分析（测量），我们使用以下方法。DRAM和PM中的内存访问配置文件使用不同的方法，以避免大的配置文件，ING开销。在PM中，Replodiser使用MemoryOptimizer中 的 profiling 方 法 来 识 别 热 页 ， 因 为 该profiling方法限制了用于分析的内存页的数量，以使分析开 销 较小 。 在 DRAM 中 ， DRAM 使 用Thermostat 中 的profiling方法[3]。此分析方法从每个2MB页面中选择一个4 KB页面进行分析，并缩放4 KB页面中的内存访问次数，以表示对2 M页面的内存访问次数。这种分析方法更准确，可用于识别冷页，以消除DRAM。 当分析数十GB的DRAM时，它导致内存访问性能下降不到1%[3]，但在分析数百GB或TB规模时会导致大量分析开销，这阻止了它应用于大容量的PM。这两种分析方法都操作PTE来检测内存访问，如第2节所述。为了估计新输入的存储器访问计数我们使用以下方法。我们假设测量到的对数据对象的内存访问次数是prof_acc_acc，数据对象的大小是prof_base。 我们 还 假 设 要为新输入估计的 存 储 器 访 问 的 数 量 是esti_acci_acc，并且数据对象大小是新的。 我们有等式1。esti_prof_acc=newprof_prof_acc（1）公司简介术语 新捕获数据对象大小从基本输入到新输入的变化。测试i_acci_acc正在进行中对于该改变（即，新尺寸与基础尺寸的比率尺寸）。此外，该比例应当考虑存储器访问模式可能具有输入依赖性的事实。行为并命中可变数量的缓存行，从而导致不同的内存访问计数。这一事实被 一个参数捕获，该参数旨在通过考虑缓存效应来量化输入之间的内存访问差异。计算成本具有挑战性。我们依赖于内存访问模式的分类和运行时细化，使之成为可能。 对于流模式和步幅模式， 通过考虑步幅长度和数据类型来计算。例如，假设高速缓存行大小为64字节，数据类型为整数（4字节），并假设因此，对于流模式，缓存将导致3次存储器访问，并且��������������� 将导致2次存储器访问（即，__=2).因此，= 1。������������对于流模式和跨步模式，如果缓存行大小不能整除缓存行或缓存行大小不能整除缓存行，则将其舍入为稍大的可整除大小。���������������������������我们列举了各种步幅长度和数据类型，然后离线计算相应的步长 这些值���在运行时在等式1中使用一 ���������次并且 ������������是已知的。对于模板图案， 根据图案是否与输入无关来计算。 流行的独立于输入的格式，如5/7/9点格式，只根据循环归纳变量更新数据对象的元素。对于这些支架，支架是离线测量的特别是，我们运行一个微基准测试，在循环中的数据对象上练习模板模式，然后使用性能计数器测量模板代码导致的主存访问次数。我们还计算在程序级发生了多少次内存访问。那么，Rk是程序级测量与基于计数器的测量的比率如果模板是依赖于输入的，这意味着模板在输入之间发生了变化，那么我们将task设置为1，并依赖于一个细化过程来改善任务执行期间的task。随机模式由于其依赖于输入的特征而采用相同的细化方法。对R1的R2细化是基于等式1的任务实例上的迭代过程（ R1被初始化为1）。 给定具有依赖于输入的模板或随机模式的数据对象，通过在采样模式中使用性能计数器（例如，Intel的基于事件的精确采样或AMD的基于指令的采样 这种模式允许我们将内存访问与特定的内存地址相关联，我们通过这些地址与数据对象连接。 这种基于性能计数器的测量在任务实例执行时发生。利用所测量的存储器访问计数，随着任务实例的执行，内存访问数不断更新，并用于估计下一个任务实例的内存访问数。处理未知模式。 虽然这四种模式广泛存在于HPC应用中，但如果任务中的数据对象具有未知的存储器访问模式，则该访问模式被视为随机的，并且 依赖于细化过程来提高估计精度。PPoPPZhen Xie，Jie Liu，Jiajia Li，andDong Li209更好规范化执行时间（·）（·）（−）登录_注册（−）（·）5性能建模在HM上的各种数据放置下对应用性能进行是重要的，因为存储器访问被分布到DRAM和PM，并且对这种分布的影响进行取决于工作负载特性和存储器性能两者。为了解决建模挑战，我们的性能模型引入了两个基本的创新：（1）通过最佳和最差性能来约束性能预测。这两个性能分别在仅DRAM和仅PM上收集，并且隐式地捕获存储器架构对性能的影响（例如，内存级并行性）;（2）基于我们对内存计数的估计（第4节），根据工作负载特征扩展两个性能界限。这种由工作负载特性驱动的性能扩展简化了我们对内存访问模式建模的工作，但显著提高了可用性。我们的性能建模采用以下信息作为输入：（1）新输入的内存访问总数（__）。此数量是所有数据对象的内存访问估计数量的累积。（2）仅在DRAM（__）和PM（__）上具有新输入的任务的预测执行时间（见5.2节）。性能建模预测任务在新输入上的执行时间，其中一些页面迁移到DRAM。 我们使用_来表示运行新输入时的DRAM访问次数，以及新输入的预测执行时间。输入为���������_���������������。���我们的性能建模基于以下比率-DRAM访问与存储器访问总数的比率= 0%比率= 50%比率= 100%1.000.750.500.250.00输入处理索引搜索累积写回输出排序 整个任务NWChem-TC的五个执行阶段图3. 当我们改变DRAM访问与内存访问总数的比率时，性能会发生变化。作为NWChem-TC），从头计算化学软件包，具有表2中列出的代表性输入问题。我们测量NWChem-TC的所有五个扩展阶段的性能，并改变DRAM访问与存储器访问总数的比率。 图3显示了仅使用PM的性能标准化。当总存储器访问的 一 半 从 PM 移 动 到 DRAM 时 ， 写 回 和 输 入 过 程（NWChem-TC中的两个执行阶段的执行时间分别减少了47.5%和26.2%为了更好地对Pneumnew_hybrid和Pneumnew_pm_only之间的相关性进行建模，我们在等式中引入了相关函数2. 我们将在5.1节中讨论如何构建，以及如何估计同构内存上的执行时间（即，new_pm_only和 new_pm_only）。5.1相关函数我们基于相关函数应包括工作负载特征的原则构建相关函数，这些工作负载特征指示应用程序对HM上的数据放置的敏感程度。 相关函数采用工作负载特性和DRAM访问与总访问的比率注：（1）应在以下范围内限定最大值：和DRAM_DRAM_DRAM;（2）对于单个任务，主存储器访问次数登录_访问）作为输入。访问导致更好的性能。公式2预测这是一个很好的例子，并反映了上述原理。���_ℎ���������������=(2)���__���× (1−���_)×���������������������������（在等式2中，PMC是性能监视器计数器;_acc= 术 语 1_ new_acc 反 映 了 基 本 原 理 （ 2 ） ， 并 对new_pm_only和new_hybrid之间的相关性进行建模。 当所有存储器访问发生在 DRAM 中 时 （ 即， ESTi_acc = esti_ESTi_acc） 或PM（ 即 ，_acc= 0 ） ， 则 性 能 变 为new_pm_only 或new_pm_only。请注意，仅1个字符串_acc项不足以捕获新的混合和新的pm_only之间的相关性。 当DRAM中发生更多的存储器访问时，提高的性能与DRAM访问次数之间不存在简单的线性关系。当更多的存储器访问发生在DRAM中时，指令流水线能够更快地运行，这影响存储器并行性和 指 令 调 度 顺 序 。 为 了 验 证 上 述 结 论 ， 我 们 运 行 了NWChem（参考相关函数是一个统计模型。由于以下原因，我们不使用分析建模。首先，分析建模难以捕捉内存访问和计算之间的重叠。 这种重叠会影响应用程序对内存延迟和带宽的性能敏感度，因此应该对其进行建模。尽管现有的努力使用分析建模来对重叠进行建模[24，28，30，78]，但它们是建立在详细的架构信息（例如， 存储体之间的数据分布）并得到编译器的有力支持（例如，量化指令级并行性），这限制了它们的可行性。第二，分析建模的复杂性会导致很大的运行时开销。我们研究了第7节表3中列出的统计模型。我们使用从性能计数器收集的所有性能事件作为工作负载特征。这些事件用作模型输入（属性）。然后，我们用计算出的目标值训练模型。 我们选择梯度提升回归（GBR）作为最终的相关函数，因为它导致我们研究的统计模型中建模精度最高。在下文中，我们将讨论如何训练模型并生成训练数据。任务并行HPC应用的HM数据布局PPoPP210（·）（·）（·）（·）2.（·）训练数据生成。 我们的训练数据包括数千个训练样本。 每个训练样本是由任务特征（等式2中的PMC）和特定的 Pmax_acc以及计算的值 组成的对。为了生成训练样本，���通过运行代码样本根据等式2计算目标值。特别是，我们仅在PM和DRAM上运行代码样本，使用相同的随机输入，并测量性能（ 在等式2中用作参数_参数我们改变了DRAM上的数据对象的分配，以生成- ate 10个不同的数据位置。 每个数据放置都应用于具 有 相 同 输 入 的 代 码 示 例 ， 并 且 我 们 测 量���_and������������_numb���������������。 替换���new_pm_only，通过等式2中的测量值，我们得到的值 。为了生成代码示例，我们使用CERE [10]。 CERE是一个基于LLVM的编译器工具，可以自动提取代码区域（也称为，循环）出程序。 我们使用NAS并行基准测试[7]和SPEC2006 FP基准测试[26]来提取281个代码区域作为代码样本。每个训练样本必须包括PMC作为工作负载特征的代表。收集PMC和生成训练样本使用相同的代码，但输入不同。我们使用不同输入的原因是，在性能模型（公式2）中，工作负载特征是使用基本输入收集的，但预测性能是针对与基本输入不同的新输入。 我们将用于收集PMC的输入称为种子输入。选择工作量特征。在选择统计模型时，我们使用所有可收集的硬件事件作为工作负载特征，这确保了模型选择不受工作负载特征选择的影响。一旦选择模型作为相关函数，我们就减少这些硬件事件作为工作负载特征，原因如下。首先，其中一些事件是冲突的，不能同时收集。这意味着我们必须多次运行任务来收集所有这些事件，这限制了我们性能建模的可用性其次，使用所有事件来构建模型会导致更大的运行时开销，并且需要更多的训练数据来提高建模精度。我们使用以下方法来选择硬件事件。我们首先使用所有事件（或特征）训练模型，然后删除对模型准确性最不重要的硬件事件。 我们使用一个度量来量化硬件事件的重要性，即基尼重要性[52]，因为它具有很强的可微性。在删除硬件事件后，我们重新训练模型，然后再次删除最不重要的功能。 我们继续这个过程，直到去除最不重要的特征后的模型精度比第二好的模型差。我们选择8个事件来表示工作负载特征：LLC_MPKI、IPC、PRF_Miss、MEM_WCY、L2_LD_Miss、BR_MSP、VEC_INS，和L3_LD_Miss（按重要性降序列出）。LLC_MPKI、IPC和PRF_Miss是最重要的事件。LLC_MPKI表示每千指令的最后一级缓存未命中，其指示任务从存储器获取数据的频率; IPC是每个时钟周期执行的指令的平均数量，其指示任务是计算还是存储器受限; PRF_Miss是导致未命中的数据预取与数据预取总数的比率，其指示数据预取是否成功以及存储器访问模式是否高度不规则。一般来说，这三个事件具有高度的区分性，可以指示应用程序性能对数据放置的敏感性，因此可以用于构建鲁棒的模型。5.2同构存储器的性能预测许多努力预测具有各种输入的应用程序的执行时间[29，47，55，56，65，73，76]。 它们基于工作负载特性没有变化的假设（例如，存储器访问模式和控制流）。 我们使用相同的假设，并使用工作[55]来预测__和__。我们使用[55]中的方法来识别输入无关在PM和DRAM上离线测量它们的执行时间 除了工作[55]之外，在运行时，Quaddiser计算任务中每个基本块使用基本输入执行的次数。然后，基于输入数据对象的大小，计算基本输入和新输入之间的相似性特别地，给定包括一个或多个数据对象的输入，我们构建向量，并且向量的每个元素表示输入数据对象的大小。 我们通过计算两个向量的余弦相似度[17]来量化基础输入和新输入之间的相似度。我们使用余弦相似度的值来缩放使用基本输入执行基本块的次数。 缩放结果是使用新输入执行基本块的次数的估计。我们的方法不会造成很大的运行时开销，因为它只需要计算余弦相似度来预测对于新的（不可见的）输入，请选择“输入”_“输入”_“输入问题.5.3整合所有总而言之，以下工作流自动为用户发生。离线模型构建和代码分析。1. 离线构建缩放函数 。 这包括使用代码样本生成训练数据集并收集代码样本的特征（即，工作负载特性）使用一些种子输入。 的构建 只发生一次。准备在线预测的最大值_最小值_最小值和最大值_最小值_最小值。这包括测量DRAM和PM上基本块的执行时间。对于应用程序，此步骤只发生一次。PPoPPZhen Xie，Jie Liu，Jiajia Li，andDong Li2113. 离线应用程序代码分析。这是基于编译器分析，包括获得独立于输入的基本块，获得内存访问模式，用于在线估计内存访问总数（见第4节）。 对于一个应用程序，离线代码分析只发生一次。4. 离线计算输入无关的sten-bandwidth或随机访问模式的带宽在线分析和性能预测。1. 使用基本输入在线收集任务信息。 这包括使用8个性能事件收集任务的工作负载特征，以及使用基本输入计算基本块执行的次数。2. 使用新输入的任务的在线性能预测。 这发生在任务执行之前，包括：（a）估计对数据对象的内存访问次数;（b）预测__和__。运行时系统使用性能建模来预测具有新输入的任务性能。用户可行性。 Advertiser考虑了用户的可行性。所有步骤都是自动化的。离线步骤1和4只构建一次，可用于任何应用程序。对于给定的应用程序，离线步骤2-3只发生一次。在线步骤1-2取决于应用程序和输入，但是自动化的。用户只需要将API插入到应用程序中，而无需更改应用程序代码。可扩展性。 该系统可以很容易地扩展到其他HM系统。 需要三个步骤：（1）收集训练数据，以反映应用程序对不同存储器的性能敏感度;（2）重新构建缩放函数（本工作13分钟），并选择最关键的性能事件;（3）测量新存储器系统中基本块的性能。限制Paddiser需要应用程序源代码，因为它期望用户插入API并使用Spindle编译代码以进行静态分析，从而识别内存 访 问 模 式 。 需 要 应 用 程 序 源 代 码 是 一 个 限 制 的mandiser。 当源代码不可用时，我们可以使用动态二进制插装工具（例如，[37，53]）插入API，拦截内存分配，并生成指令跟踪。然后，我们使用一个工具（例如，[58，59]）以识别迹线的存储器访问模式6负载平衡感知数据迁移数据迁移是基于负载均衡的性能建模。使用性能建模。使用perfor-曼斯建模，我们决定有多少内存访问在每个任务应该在DRAM上，使负载平衡和高性能。 该决策过程可以用背包问题来描述，如果我们把DRAM容量看作背包重量的极限，则每个页面都是背包中的一个项目，背包，将项目（页面）放置在DRAM上后的性能收益作为项目值，页面大小作为项目权重。由于背包问题是NP难的，决定每个任务中有多少内存访问应该在DRAM上是NP难的。 我们引入一个贪婪的启发式算法来解决这个问题。该算法的基本思想如下。任务需要许多轮来逐渐增加DRAM访问（通过页面迁移）并提高性能，直到DRAM空间耗尽。在每一轮中，具有最长执行时间的任务增加其DRAM访问，直到它比第二长任务短。我们在算法1中详细描述了该算法。该算法将性能建模所需的信息作为输入，并输出每个任务的DRAM访问次数。该算法跟踪DRAM分配到每个任务和0（行6）。在初始化之后（第7行和第8行），算法迭代地找到最长任务（第10行）和第二长任务（第11行），并通过增加最长任务的DRAM访问来提高其性能（第14行）。 对于最长的任务，算法迭代地增加其DRAM访问（第13-16行）。 在每次迭代中，DRAM访问的数量增加5%（第14行），然后算法使用性能建模来预测性能（第15行）。DRAM访问的增