2040Merchandiser：面向任务并行HPC应用程序的异构内存上的数据放置与负载平衡意识0Zhen Xie zhen.xie@anl.gov加利福尼亚大学墨塞德分校Argonne国家实验室0Jie Liu jliu279@ucmerced.edu加利福尼亚大学墨塞德分校0Jiajia Li jiajia.li@ncsu.edu北卡罗来纳州立大学0Dong Li dli35@ucmerced.edu加利福尼亚大学墨塞德分校0摘要异构内存（HM）的出现为内存消耗大的HPC应用程序提供了一种具有成本效益和高性能的解决方案。在HM上决定数据对象的放置对于实现高性能至关重要。我们揭示了与HM上数据放置相关的性能问题。这个问题表现为任务并行HPC应用程序中任务之间的负载不平衡。问题的根源来自于对并行任务语义不了解以及错误地假设将频繁访问的页面放置到快速内存中总是会带来更好的性能。为了解决这个问题，我们引入了一种负载平衡感知的页面管理系统，名为Merchandiser。Merchandiser在内存分析期间引入任务语义，而不是应用程序无关。使用有限的任务语义，Merchandiser在任务之间有效地建立了协调，以便快速完成所有任务，而不仅仅考虑任何单个任务。Merchandiser的自动化程度很高，以实现高可用性。通过使用内存消耗大的HPC应用程序进行评估，我们展示了Merchandiser减少负载不平衡并实现了平均17.1%和15.4%（最高可达26.0%和23.2%）的性能改进，与基于硬件的解决方案和工业质量的软件解决方案相比。0未经费用许可，允许对本作品的全部或部分内容进行个人或课堂使用，但不得为盈利或商业目的制作或分发副本，并且副本必须带有本通知和第一页的完整引用。必须尊重除作者以外的他人拥有的本作品组成部分的版权。允许进行带有信用的摘要。要复制或重新发布，要在服务器上发布或要重新分发到列表中，需要事先获得特定许可和/或支付费用。请向permissions@acm.org申请权限。PPoPP '23，2023年2月25日至3月1日，加拿大蒙特利尔©2023年版权归所有者/作者所有。发表权许可给ACM。ACM ISBN979-8-4007-0015-6 / 23/02 ... $ 15.00https://doi.org/10.1145/3572848.35774970CCS概念:•计算机系统组织→异构（混合）系统;•计算理论→并行计算模型;•硬件→非易失性内存。0关键词：数据放置，异构内存，并行计算，负载平衡0ACM参考格式：Zhen Xie，Jie Liu，Jiajia Li和DongLi。2023年。Merchandiser：面向任务并行HPC应用程序的异构内存上的数据放置与负载平衡意识。在第28届ACMSIGPLAN年度并行编程原理与实践研讨会（PPoPP'23），2023年2月25日至3月1日，加拿大蒙特利尔。ACM，美国纽约，纽约，14页。https://doi.org/10.1145/3572848.357749701引言许多高性能计算（HPC）应用程序正在变得对内存消耗大。例如，密度矩阵重整化群（DMRG）[6,77]是一种用于获取量子多体系统低能物理的数值算法，当在320×320尺度上解决Hubbard2D模型时，可以在单台机器上消耗1.271TB的内存[21,46]。为了满足这些应用程序的内存需求，大内存系统正在出现。这样一个系统的例子是建立在八个NUMA节点之上并提供高达12TB内存的AmazonEC2高内存实例[31]。大内存系统通常是异构的，这意味着由具有不同延迟和带宽的多个内存组件形成主内存。HM引发了一个数据放置问题。由于快速内存容量较小，而慢速内存性能相对较差，因此必须在快速和慢速内存之间分配和迁移内存页面，以便大部分内存访问可以在快速内存中发生以实现高性能。已经证明，一些HPC应用程序在HM上进行次优数据放置（与仅使用快速内存的解决方案相比）可能遭受高达5.7倍的性能损失[61, 63, 67, 84]。2050PPoPP '23，2023年2月25日至3月1日，加拿大蒙特利尔Zhen Xie，Jie Liu，Jiajia Li和Dong Li0许多解决HM上数据放置问题的解决方案[19, 25, 33, 34, 41,54, 84,86]使用了基于分析引导的优化（PGO）方法。这些解决方案通过定期对内存页面进行采样并跟踪内存访问来识别频繁访问的内存页面（“热页面”）。然后将热页面迁移到快速内存以提高性能。这些解决方案是与应用无关的，也就是说它们不需要应用程序知识或更改应用程序。这些解决方案的成功基于这样一个隐含的假设，即将热页面放置在快速内存中总是会带来更好的性能。然而，我们发现对于许多任务并行的HPC应用程序来说，这并不是真实的。任务并行程序在HPC中很常见。任务并行程序可以是基于MPI的，每个MPI进程执行一个任务。它可以是基于OpenMP的，每个OpenMP线程执行一个任务。在任务之间有同步，任务必须在达到同步点之前完成，然后才能继续计算的其余部分。由于任务之间的同步，快速完成所有任务而不是快速完成单个任务是高性能的关键。HM上的PGO对于任务并行应用程序效果不佳。它们缺乏对于高性能“快速完成所有任务”的视角。它们将热页面迁移到快速内存中，但不考虑哪个任务访问这些内存页面。因此，现有的努力可能会引入负载不平衡:一个任务不必要地在其他任务之前达到同步点并等待其他任务完成，因为该任务的许多页面驻留在快速内存中，导致其执行时间较短。为了揭示HM上的负载不平衡问题，我们在基于Optane的HM上研究了五个HPC应用程序。这个HM由192GBDRAM和1.5TBOptane组成。我们研究了两种代表性的解决方案:一个工业质量的软件解决方案（Intel MemoryOptimizer[16]）和一个硬件解决方案（Optane的内存模式）。我们有两个观察结果（详见评估部分的图5）。•与在同质内存上运行相比，在HM上运行会增加任务之间的性能差异:平均而言，使用MemoryOptimizer和MemoryMode分别增加了17%和16%的性能差异，这表明在使用MemoryOptimizer和MemoryMode后负载不平衡更严重。•使用MemoryOptimizer和MemoryMode后，性能改进很小。与仅使用Optane相比，性能改进仅为4.32%和3.71%，因为最慢的任务阻碍了整体性能。上述性能问题有两个根本原因。首先，PGO解决方案（如MemoryOptimizer）不了解任务并行性。任务之间缺乏协调来共享有限的快速内存空间。这个空间根据对任务的机会性检测热页面进行分配，而不是基于应用程序。0性能分析可能对任务使用快速内存的潜在性能收益进行不公平的评估。它可能不公平地将来自一个任务的太多页面放置到快速内存中，导致负载不平衡。其次，PGO解决方案使用基于随机页面采样的内存分析。随机采样对于避免在大内存系统中分析所有内存页面的巨大开销是有效的。然而，它可能会收集来自一个任务的许多内存访问，这导致该任务的太多页面迁移到快速内存中，导致负载不平衡。我们引入了一种负载平衡感知的HM数据放置系统，名为Merchandiser，来解决这个问题。Merchandiser在内存分析期间引入了任务语义。这意味着Merchandiser在分析期间将内存访问与任务关联起来，而不是应用程序无关。使用有限的任务语义，Merchandiser在任务之间有效地建立了协调。此外，Merchandiser使用任务的历史、细粒度的分析结果来指导相同任务的后续执行中的数据放置。0然而，要实现Merchandiser，我们面临两个挑战。首先，在程序执行期间，任务的输入问题可能会发生变化，从一个输入收集的历史分析结果不能直接用于预测另一个输入的性能，因为内存访问次数的差异。其次，如何在任务之间划分快速内存空间是一个具有挑战性的问题。除非所有任务具有相同的内存访问模式和数据对象大小，否则将快速内存均匀分配给所有任务是不可行的。对于具有新输入的每个任务，我们必须决定哪些对象应该放置在快速内存中，而事先不知道对象的内存访问次数。我们还必须预测迁移后任务的执行时间，以便能够量化和估计负载平衡的有效性。为了应对处理新输入问题的第一个挑战，Merchandiser根据数据对象的内存访问模式对数据对象进行分类，基于此，Merchandiser分析推导出新输入问题的主内存访问次数。在许多HPC应用程序中，内存访问模式在给定任务的输入问题中通常是不变的，对内存访问次数提供可靠的指示。我们还认识到内存访问模式的影响差异，并对不同的模式differently估计内存访问次数。基于估计的内存访问次数，Merchandiser引入性能建模来预测任务在一定部分内存访问发生在快速内存中而其余内存访问发生在慢速内存中时的执行时间。我们的性能建模的新颖之处在于对任务的不同数据放置之间的性能相关性进行建模。特别是，性能建模以一个数据放置的性能作为输入，然后预测另一个数据放置的性能。性能建模基于以上两个性能之间的相关性来建立。2060经销商：面向任务并行HPC应用的HM上的数据放置PPoPP'23，2023年2月25日至3月1日，加拿大蒙特利尔0任务特性。任务特性使用从特定数据放置的单次执行中收集的少数性能事件来表示和量化。为了解决如何将快速内存空间在任务之间分配的挑战，我们引入了一种贪婪启发式算法，以决定如何分配快速内存空间，以最大化所有任务（而不是单个任务）的性能收益。该算法根据性能建模来改变快速内存访问的比例，以找到负载平衡的解决方案。总之，我们的贡献如下。0•我们确定了HM上的一个新的性能问题。•我们在分析过程中引入了任务语义，以实现对任何数据放置的精确性能预测，并引入了一种贪婪启发式算法来指导在HM上的各种数据放置的探索。•Merchandiser使用高可用性的自动化工作流程。与基于硬件的解决方案（Optane的MemoryMode）和行业质量的基于软件的解决方案（MemoryOptimizer[16]）相比，它大大减少了负载不平衡，并实现了平均17.1％和15.4％（最高达26.0％和23.2％）的性能改进。在基于Optane的HM上。02背景异构内存（HM）。我们以IntelOptane持久内存（PM）和DRAM为例来介绍HM。随着其他技术（如CXL[11]和高带宽内存）的出现，HM正在成为一种趋势。PM和DRAM之间存在性能差异。在Optane PM100系列中，PM上顺序和随机读取的内存延迟比DRAM上分别长2.08倍和3.77倍；PM上读取和写入的内存带宽峰值分别比DRAM低3.87倍和4.74倍[36,64]。PM模块可以配置为App Direct Mode或MemoryMode。使用App DirectMode，软件明确控制内存页面在PM和DRAM上的放置。使用MemoryMode，DRAM作为PM的直接映射写回缓存，并由硬件管理。Merchandiser是一种软件解决方案，因此它使用AppDirect Mode。Merchandiser的性能优于Memory Mode。HM上的数据放置。现有的解决方案[2，15，33，34，41，60]通过操作内存分页表项（PTE）进行内存分析以检测热点页面。它们反复扫描PTE或拦截页面保护故障，以检查PTE中的特定位是否被硬件修改。如果是，则记录内存访问并将该位重置以进行未来的分析。使用这种方法可以准确捕捉内存访问。但是，它速度较慢（对数百GB内存进行分析需要几秒钟），并且无法捕捉不同工作负载行为。为了避免长时间的分析时间，对地址空间中的页面进行抽样是自然的选择。然而，对所有任务进行无差别的页面抽样可能导致负载不平衡。0（a）基于MPI的应用（DMRG）01将哈密顿分块02每个MPI排列一个块03块有它们的输入数据（H，PSI）04 for sweep in sweeps:05 S1：构建问题06 S2：解决Davidson函数07 S3：应用SVD更新（H，PSI）08交换边界和同步0(b)基于OpenMP的应用（SpGEMM）01 for (A * B) in an application:02将A按行分成bin03每个bin都有自己的大小和NNZ04#pragma omp parallel05{T1：计算C的NNZ06同步点107 T2：计算C的值08同步点20图1.两个任务并行HPC应用的示例。（NNZ=非零元素的数量）0任务并行的高性能计算应用。我们研究了任务并行的高性能计算应用[22]。在这样的应用中，多个任务并行运行，通常基于MPI或OpenMP。在基于MPI的应用中，每个MPI进程都在处理一个任务，在基于OpenMP的应用中，每个并行区域中的每个OpenMP线程都在处理一个任务。任务之间存在同步。此外，任务可以重复执行，并且每次执行可能使用不同的输入。我们将任务的每次执行称为任务实例。图1.a给出了一个基于MPI的任务并行应用DMRG的示例[6, 21,77]。在DMRG中，首先将一个哈密顿矩阵划分为多个块，每个块分配给一个MPI进程（第1-3行）。然后，每个MPI进程运行一个计算循环，使用分配的块（�）和矩阵乘积状态（���）作为输入，迭代运行DMRG算法（第5-7行）。循环的一次迭代被视为一个任务实例。因此，MPI进程中的任务被重复执行。任务实例使用相同的�但不同的���作为输入。在每次迭代的结束时，MPI进程之间进行全局同步。图1.b给出了基于OpenMP的任务并行应用SpGEMM（�=���）在Ginkgo[5]中的示例。在这个示例中，一个主循环运行多个SpGEMM（�=���）。在主循环的每次迭代中，首先按行将�划分为多个bin，然后有一个OpenMP并行区域，每个线程访问�和一个�的bin来生成�的一部分。在循环的一次迭代中，一个线程处理一个任务实例，在下一次迭代中，该线程处理另一个任务实例，但使用不同的�和�。在OpenMP区域的末尾，有一个隐式的线程同步。我们假设对于给定的任务，算法或内存访问模式在任务实例之间不会发生变化。例如，在图1.a中，在一个MPI进程中，无论���（输入数据）如何变化，第5-7行的算法和内存访问模式保持不变。但是，如果任务实例之间的算法或内存访问模式发生变化，则这些任务实例应该被分类为不同的任务。03概述0商品销售员，如图2所示，使用性能建模来指导HM中的数据放置。性能建模使用任务信息作为输入，其中包括执行2070PPoPP ’23, 2023年2月25日至3月1日，加拿大蒙特利尔，魏振，刘杰，李佳佳，李冬0任务10任务20任务N ...0并行任务应用程序0基准输入0数据迁移0运行时数据迁移0性能预测0分析模型0基于输入的内存访问量化0工作负载特征0访问模式分类0内存访问估计0同步0启发式算法0性能建模0图2.商品销售员概述。基本块的时间和运行时性能事件对决定任务对数据放置的性能敏感性至关重要。任务信息在任务的第一个实例中使用输入问题（称为基准输入）收集，并由性能建模使用，以预测相同任务在新输入下在HM上的各种数据放置下的性能。性能建模集成到运行时系统中，以决定数据迁移是否会引入任务之间的负载不平衡。为了准确预测具有新输入的任务的执行时间，我们的性能建模首先估计对数据对象的内存访问次数（见第4节）。商品销售员通过静态分析对数据对象级别的内存访问模式进行分析，然后根据数据对象大小、从基准输入收集的内存访问次数和内存访问模式进行估计。性能建模预测了具有新输入的任务在HM上的各种数据放置下的执行时间。预测使用估计的内存访问次数、工作负载特征和在同构内存上的执行时间预测（例如，仅PM或DRAM）（见第5节）。工作负载特征是基于每个事件对预测准确性的量化的性能事件中选择的。在输入无关的基本块和离线分析上建立了对同构内存上执行时间的预测。商品销售员使用性能建模的运行时系统以负载平衡意识来决定是否进行数据迁移（见第6节）。在任务执行之前，运行时首先使用一种启发式算法根据性能建模决定每个任务应该发生多少次快速内存访问。然后，利用现有解决方案中的内存分析机制，商品销售员确定是否应该将与每个任务对应的页面从慢速内存迁移到快速内存。04基于输入的内存访问量化0对于一个新的输入问题，估计对数据对象的内存访问是具有挑战性的。在不使用广泛和昂贵的内存分析的情况下，如何捕捉主内存访问的缓存效应以及如何进行估计0在不牢固地与架构细节紧密耦合的情况下实现高可用性是具有挑战性的。我们的解决方案具有两个基本创新点：（1）使用基准输入的有限内存分析来指导估计，这对于简化估计方法和提高可用性是有用的；（2）区分内存访问模式，这对于捕捉缓存效应和提高估计质量是有用的。0我们的估计方法分为三个步骤：（1）使用用户API指定在HM上管理数据对象，（2）对任务中这些对象的内存访问模式进行分类，（3）估计内存访问次数。用户API。在任务并行的HPC应用程序中，大多数内存访问发生在几个主要的数据对象上。例如，图1.a中的�和���（DMRG），以及图1.b中的�，�和�（SpGEMM）。通过API，商品销售员负责放置用户通过API指定的数据对象。我们假设数据对象的大小在任务执行期间的运行时之前是已知的（例如，图1.a中的第3行和图1.b中的第3行）。这个假设在许多HPC应用程序中通常是正确的[4, 44, 57,75,79–81]。商品销售员希望用户使用以下API指定要管理的数据对象：0void *LB_HM_config(void* objects, int*sizes)其中*objects指向一个由用户指定的数据对象列表，用于进行分析和迁移管理，而*sizes指向它们的大小列表（例如，DMRG的PSI数组的长度）。数据对象的大小可以是变量，并且它们的值在任务执行之前是已知的。该API放置在任务执行之前的程序中。在DMRG和SpGEMM的示例中，该API分别放置在图1.a和图1.b中的第5行和第4行之前。请注意，用户在使用API时不需要任何关于哪些数据对象导致负载不平衡的信息。任何数据对象都可以传递给API。内存访问模式的分类。我们对用户指定的数据对象进行对象级内存访问模式分析，并将内存访问分为四种模式。这些模式用以下代码表示（作为循环的主体），其中�是一个循环归纳变量：0• Stream : A[i] = B[i] + C[i] •Strided : A[i*stride] = B[i*stride] • Stencil : A[i] = A[i − 1] + A[i+1]• Random : A[i] = B[C[i]]0流模式表现为在循环中通过任何数组进行步进，其中索引由循环归纳变量确定。该模式还包括增量模式（例如，A[i] =A[i] + d）、归约（例如，x = x +A[i]）和转置（例如，A[i][j] =B[j][i]）。步长模式是流模式的一种更一般情况，其中步长是从应用程序知识中已知的常数。模板模式涉及在循环迭代之间顺序访问数组，并存在循环之间的依赖关系，例如Jacobi和Gauss-Seidel内核中使用的7点模板2080商品销售员：对HM上的任务并行HPC应用程序的数据放置 PPoPP ’23, 2023年2月25日至3月1日，加拿大蒙特利尔0表1.五个应用程序中检测到的访问模式0应用程序SpGEMM WarpX BFS DMRG NWChem-TC0访问模式0随机流0步进模式0随机流0流步进0随机流0随机流0为了使用基准输入进行概要（测量），我们使用以下方法。Merchandiser使用不同的方法在DRAM和PM中对内存访问进行概要（测量），以避免大规模概要（测量）的开销。在PM中，Merchandiser使用MemoryOptimizer中的概要（测量）方法来识别热页面，因为该概要（测量）方法限制了进行概要（测量）的内存页面数量，以使概要（测量）开销较小。在DRAM中，Merchandiser使用Thermostat[3]中的概要（测量）方法。该概要（测量）方法从每个2MB页面中选择一个4KB页面进行概要（测量），并将4KB页面的内存访问次数进行缩放，以表示对2MB页面的内存访问次数。该概要（测量）方法更准确，并可用于识别冷页面以排除出DRAM。当概要（测量）数十GB的DRAM时，这会导致内存访问性能下降不到1%[3]，但是在概要（测量）数百GB或TB的规模下会导致概要（测量）开销很大，从而无法应用于具有大容量的PM。这两种概要（测量）方法都通过操作PTEs来检测内存访问，如第2节所讨论的。0为了估计新输入的内存访问计数，我们使用以下方法。我们假设测得的数据对象的内存访问次数是prof_mem_acc，数据对象的大小是�base。我们还假设要为新输入估计的内存访问次数是esti_mem_acc，数据对象的大小是� new。我们有方程1。0esti_mem_acc = � n0� base × � × prof_mem_acc (1)0�base捕捉到从基准输入到新输入的数据对象大小的变化。esti_mem_acc与该变化成比例（即，新大小与基准大小的比率）。此外，这个比例应该考虑到内存访问模式可能具有与输入有关的特性。0行为并击中可变数量的高速缓存行，导致不同的内存访问次数。 �是一个参数，旨在通过考虑缓存效果来量化不同输入之间的0计算�是具有挑战性的。我们依靠内存访问模式的分类和运行时改进来实现这一点。对于流式和跨步模式，�是通过考虑跨度长度和数据类型来计算的。例如，假设缓存行大小为64字节，数据类型为整数（4字节），假设����和����分别为192字节和128字节，则对于流式模式，����将导致3次内存访问，����将导致2次内存访问（即，����_���_��� = 2）。因此，����� =1。对于流式和跨步模式，如果����或����不能被缓存行大小整除，则会将其舍入到稍大一些的可被整除的大小。我们列举各种跨度长度和数据类型，然后在离线情况下计算相应的�。这些�的值在运行时在方程1中使用，一旦����和����已知。0对于stencil模式，根据模式是否与输入无关，计算�。流行的与输入无关的stencil模式，例如5/7/9点stencil模式，仅基于循环归纳变量更新数据对象的元素。对于这些stencil模式，�在离线情况下进行测量。特别地，我们在循环中对数据对象上的stencil模式运行一个微基准，并使用性能计数器测量stencil代码引起的主存访问次数。我们还计算在程序级别发生的内存访问次数。然后，�是程序级测量与计数器测量之比。如果stencil是与输入相关的，也就是说，stencil在不同的输入下会改变，那么我们将�设置为1，并依靠改进过程来提高�的估计精度，该过程在执行具有新输入的任务期间进行。随输入进行的�的运行时改进是基于方程1的迭代过程（�初始化为1）。给定具有与输入相关的stencil或随机模式的数据对象，使用性能计数器在采样模式下（例如，来自Intel的Precise Event-BasedSampling或来自AMD的Instruction-basedSampling）测量对数据对象的内存访问次数。该模式允许我们将内存访问与特定的内存地址关联起来，通过这种方式与数据对象连接。这种基于性能计数器的测量发生在每次执行任务实例时。使用测得的内存访问计数，�随着任务实例的执行而不断更新，并用于估计下一个任务实例的内存访问次数。处理未知模式。尽管这四种模式在HPC应用中广泛存在，但如果任务中的数据对象具有未知的内存访问模式，那么该访问模式将被视为随机模式，并且�依靠改进过程来提高估计精度。0.000.250.500.751.002090PPoPP '23，2023年2月25日至3月1日，加拿大蒙特利尔，Zhen Xie，Jie Liu，Jiajia Li和Dong Li05性能建模0在HM上建模应用程序性能在各种数据放置方案下是非常复杂的，因为内存访问被分布到DRAM和PM，并且对这种分布的影响的建模取决于工作负载特性和内存性能。为了解决建模挑战，我们的性能模型引入了两个基本创新：（1）通过最佳性能和最差性能来限制性能预测。这两个性能分别在仅DRAM和仅PM上收集，并隐含地捕捉了内存架构对性能的影响（例如，内存级并行性）；（2）基于我们对内存计数的估计（第4节），根据工作负载特性来缩放这两个性能边界。这种基于工作负载特性驱动的性能缩放简化了我们对内存访问模式建模的工作，但显著提高了可用性。0我们的性能建模以以下信息作为输入：（1）新输入的总内存访问次数（����_���_���）。这个数字是估计的所有数据对象次数的累积。（2）使用DRAM和PM分别运行新输入的任务的预测执行时间（����_����_����）和（����_��_����）测了在将一些页面迁移到DRAM上的情况下，任务在新输入上的执行时间。我们使用����_���来表示运行新输入时的DRAM次数，而新输入的预测执行时间是����_������。我们的性能建下原理：（1）����_������应该在����_��_����和����_，DRAM访问次数越多，性能越好。方程2预测了����_������上述原理。0����_������ = (2) ����_��_���� × (1 - �����_���) × �(����, �����_���) + �0在方程2中，PMC是性能监视器计数器；�dram_acc = dram_acc0更好0NWChem-TC的五个执行阶段0图3.当我们改变DRAM访问占总内存访问次数的比例时，性能的变化。0作为NWChem-TC（一种从头计算化学软件包）的一个代表性输入问题，我们测量了NWChem-TC的所有五个执行阶段的性能，并改变了DRAM访问总数占内存访问总数的比例。图3显示了性能相对于仅使用PM的性能的归一化值。当将总内存访问量的一半从PM移动到DRAM时，Writeback和InputProcess（NWChem-TC中的两个执行阶段）的执行时间分别减少了47.5%和26.2%。为了更好地建模� new _ hybrid和� new _pm _only之间的相关性，我们引入了方程2中的相关函数�(∙)。我们将在5.1节中讨论如何构建�(∙)，在5.2节中讨论如何估计在同构内存上的执行时间（即� new _ dram _ only和� new _ pm _ only）。05.1相关函数的构建0我们基于一个原则构建相关函数，即相关函数应包含表明应用程序对HM上数据放置的敏感性的工作负载特征。相关函数接受工作负载特征和DRAM访问总数占主存访问总数的比例（�dram _acc）作为输入。Merchandiser中的相关函数是一个统计模型，我们不使用分析建模的原因有以下几点。首先，分析建模很难捕捉内存访问和计算之间的重叠。这种重叠影响应用程序对内存延迟和带宽的性能敏感性，因此应该被建模。虽然现有的研究工作使用分析建模来模拟重叠[24, 28, 30,78]，但它们建立在详细的体系结构信息（例如内存银行之间的数据分布）和编译器的强力支持的基础上，这限制了它们的可行性。其次，分析建模的复杂性可能会导致较大的运行时开销。我们研究了第7节中列出的统计模型。我们使用性能计数器收集的所有性能事件作为工作负载特征。这些事件被用作模型的输入属性。然后，我们用计算得到的�(∙)的目标值来训练模型。我们选择Gradient Boosted Regressor(GBR)作为最后的相关函数，因为它在我们研究的统计模型中具有最高的建模精度。接下来，我们讨论如何训练模型和生成训练数据。2100Merchandiser：面向任务并行的HPC应用程序在HM上的数据放置 PPoPP '23，2023年2月25日至3月1日，加拿大蒙特利尔0训练数据生成。我们的训练数据包括数千个训练样本。每个训练样本是一个由任务特征（方程2中的PMC）和特定的� dram_acc以及�(∙)的计算值组成的对。为了生成一个训练样本，根据方程2运行一个代码样本来计算�(∙)的目标值。特别地，我们在仅使用PM和仅使用DRAM的情况下，对相同的随机输入运行一个代码样本，并测量性能（用作方程2中的� ��� _ �� _ ��������）。我们改变DRAM上数据对象的分配以生成10个不同的数据放置方式。将每个数据放置方式应用于相同的输入的代码样本，然后测量� ���� _ ���和� ��� _ ������。用测量值来替pm _ only、� new _ dram _ only、� new _ hybrid和� dram _acc，我们得到�(∙)的值。为了生成代码样本，我们使用CERE[10]。CERE是一个基于LLVM的编译器工具，可以自动从程序中提取代码区域（即循环）。我们使用NAS并行基准测试[7]和SPEC 2006FP基准测试[26]来提取281个代码区域作为代码样本。每个训练样本必须包括作为工作负载特征代表的PMC。收集PMC和生成训练样本使用相同的代码，但使用不同的输入。我们之所以使用不同的输入是因为在性能模型（方程2）中，工作负载特征是使用基础输入收集的，但预测的性能是针对与基础输入不同的新输入的。我们将用于收集PMC的输入称为种子输入。工作负载特征的选择。在选择统计模型时，我们使用所有可收集的硬件事件作为工作负载特征，以确保模型选择不受工作负载特征选择的影响。一旦选择了一个模型作为相关函数，我们就减少这些硬件事件作为工作负载特征，因为以下原因。首先，其中一些事件是冲突的，不能同时收集。这意味着我们必须多次运行任务来收集所有这些事件，这限制了我们性能建模的可用性。其次，使用所有事件来构建模型可能会导致更大的运行时开销，并且需要更多的训练数据来获得高的建模精度。我们使用以下方法来选择硬件事件。我们首先使用所有事件（或特征）训练模型，然后删除一个对模型准确性影响最小的硬件事件。我们使用Gini重要性[52]来量化硬件事件的重要性，因为它具有很强的可区分性。删除一个硬件事件后，我们重新训练模型，然后再次删除最不重要的特征。我们继续这个过程，直到删除最不重要的特征后的模型准确性比第二好的模型差。我们选择8个事件来代表工作负载特征：LLC_MPKI、IPC、PRF_Miss、MEM_WCY、L2_LD_Miss、BR_MSP、VEC_INS和L3_LD_Miss（按重要性递减顺序列出）。0LLC_MPKI、IPC和PRF_Miss是最重要的事件。LLC_MPKI表示每千条指令的最后一级缓存缺失次数，它指示任务从内存中获取数据的频率；IPC是每个时钟周期执行的平均指令数，它指示任务是计算密集还是内存密集；PRF_Miss是导致缺失的数据预取的比例与总数据预取次数的比率，它指示数据预取是否成功以及内存访问模式是否高度不规则。总的来说，这三个事件具有很高的区分能力，并且可以指示应用程序性能对数据放置的敏感性，因此可以用来构建一个强大的模型。5.2在同构内存上的性能预测许多工作预测具有不同输入的应用程序的执行时间[29, 47, 55, 56, 65, 73,76]。它们基于一个假设，即工作负载特征（如内存访问模式和控制流）在不同输入之间不会发生变化。我们使用相同的假设，并使用[55]的方法来预测� ��� _ �� _ ����和� ��� _ ���� _ ����。0我们使用[55]中的方法来识别与输入无关的基本块，并在PM和DRAM上离线测量它们的执行时间。在[55]的工作之外，在运行时，Merchandiser使用基础输入计算每个任务中的每个基本块被执行的次数。然后，Merchandiser根据输入数据对象的大小计算基础输入和新输入之间的相似性。特别地，给定包含一个或多个数据对象的输入，我们构建一个向量，向量的每个元素表示输入数据对象的大小。我们通过计算两个向量的余弦相似度[17]来量化基础输入和新输入之间的相似性。我们使用余弦相似度的值来缩放使用基础输入执行基本块的次数。缩放结果是使用新输入执行基本块的次数的估计。我们的方法不会导致大的运行时开销，因为它只需要计算余弦相似度来预测新的（未见过的）输入问题的� ��� _ �� _ ����和� ��� _ ���� _ ����。05.3 将所有内容整合在一起0总之，以下工作流程对用户来说是自动进行的。离线模型构建和代码分析。1.离线构建缩放函数�(∙)。这包括使用代码样本生成训练数据集，并使用一些种子输入收集代码样本的特征（即工作负载特性）。构建�(∙)仅发生一次。2.为在线预测����_����_����和����_��_����做准备。这包括测量DRAM和PM上基本块的执行时间。对于一个应用程序，此步骤只发生一次。2110PPoPP '23，2023年2月25日至3月1日，加拿大蒙特利尔，魁北克，Zhen Xie，Jie Liu，Jiajia Li和Dong Li03.离线应用程序代码分析。这基于编译器分析，包括获取与输入无关的基本块，获取在线估计总内存访问次数的内存访问模式（见第4节）。对于一个应用程序，离线代码分析只发生一次。4. 计算输入无关的sten-cil或随机访问模式下的�的离线计算。0在线分析和性能预测。1.使用基本输入在线收集任务信息。这包括使用8个性能事件收集任务的工作负载特性，并使用基本输入计算基本块执行次数。2.使用新输入进行任务的在线性能预测。这发生在任务执行之前，包括：（a）估计对数据对象的内存访问次数；（b）预测����_��_����和����_����_����。运行时系统使用性能。用户可行性。Merchandiser考虑用户可行性。所有步骤都是自动化的。离线步骤1和4仅构建一次，可用于任何应用程序。离线步骤2-3对于给定应用程序仅发生一次。在线步骤1-2是应用程序和输入相关的，但是是自动化的。用户只需要在应用程序中插入API而无需更改应用程序代码。可扩展性。Merchandiser可以轻松扩展到其他HM系统。需要三个步骤：（1）收集训练数据以反映应用程序对不同内存的性能敏感性；（2）重新构建缩放函数（本文中为13分钟）并选择最关键的性能事件；（3）在新的内存系统中测量基本块的性能。0限制：Merchandiser需要应用程序源代码，因为它期望用户插入一个API并使用Spindle进行静态分析来识别内存访问模式。要求应用程序源代码是Merchandiser的限制。当源代码不可用时，我们可以使用动态二进制插装工具（例如[37,53]）插入API，拦截内存分配并生成指令跟踪。然后，我们使用工具（例如[58,59]）来识别跟踪的内存访问模式。6.0数据迁移基于具有负载平衡意识的性能建模。使用性能建模，我们决定每个任务中有多少内存访问应该在DRAM上，以实现负载平衡和高性能。决策过程可以看作是一个背包问题，如果我们将DRAM容量视为背包重量的限制，将每个页面视为背包中的一个项目0背包问题，将项目（页面）放置在DRAM上后的性能收益作为项目价值，将页面大小作为项目重量。由于背包问题是NP难问题，决定每个任务中有多少内存访问应该在DRAM上是NP难的。我们引入了一种贪婪启发式算法来解决这个问题。算法的基本思想如下。任务需要多轮逐渐增加DRAM访问（通过页面迁移）并提高性能，直到DRAM空间用尽为止。在每一轮中，执行时间最长的任务增加其DRAM访问，直到它的执行时间小于第二长的任务。我们在算法1中详细描述了该算法。算法以性能建模所需的信息作为输入，并输出每个任务的DRAM访问次数。算法跟踪每个任务的DRAM分配，并将其初始化为0（第6行）。初始化后（第7行和第8行），算法迭代地找到最长的任务（第10行）和第二长的任务（第11行），并通过增加其DRAM访问来改善最长任务的性能（第14行）。对于最长的任务，算法迭代地增加其DRAM访问（第13-16行）。在每次迭代中，DRAM访问次数增加5%（第14行），然后算法使用性能建模
我的内容管理
收起
我的收益 登录查看自己的收益
我的积分
登录查看自己的积分
我的C币
登录后查看C币余额
我的收藏 
我的下载 
下载帮助 
