多核环境下内存拥塞抑制方案在沙特国王大学学报

沙特国王大学学报一种有效的多核环境下内存拥塞抑制方案Navin ManiUpadhyay，Ravi Shankar Singh印度北方邦瓦兰赛印度理工学院（Banaras Hindu University）计算机科学与工程系阿提奇莱因福奥文章历史记录：收到2020年2020年4月15日修订2020年5月31日接受在线预订2020年保留字：高性能计算MPI进程布局内存拥塞NUMA架构多核MPI-R例程A B S T R A C T在现代NUMA系统中，内核数量的增加导致共享缓存和内存控制器严重拥塞。因此，在本文中，我们提出了一种方法（RCLB），这是能够减少内存拥塞与调和本地通信。它可以防止内存控制器上的负载不平衡，从而使用MPI通信模式识别通过集群应用的数据流量。所提出的方法在MPI应用程序的运行时的性能分析技术的一个小的修改实验结果表明，该方法在基于内存的测试（CLB）中获得了12.65-23%的带宽提升©2020作者由爱思唯尔公司出版代表沙特国王大学这是一个开放的访问CC BY-NC-ND许可证下的文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍在过去的几十年里，处理器中的核心数量已经增加基于放置在处理器上的这些核心，可以容易地对系统进行分类，因为所有处理器的核心不一定以顺序方式连接。可能有一些处理器它们只能共享一个可供其组使用的缓存在这样的体系结构中，存储器共享问题可能由于几个原因而发生最重要的原因是内存拥塞，这是HPC的最大问题。如果系统的规模增加，则存储器拥塞将增加（Engel等人，2015年）。将系统的标度性分为两类：强标度性和弱标度性。强标度系统在其处理器之间具有并行通信安排，而在弱标度系统中，并行处理可能是一个挑战。从而减少内存拥塞*通讯作者。电子邮件地址：iitbhu.ac.in（新墨西哥州）Upadhyay）。沙特国王大学负责同行审查制作和主办：Elsevier从弱标度系统中分离出来是本文的主要目标，从而使性能得到提高。此外，这种核心在高性能计算和大规模多处理系统环境中非常有用。在这样的环境中，每个处理器可以是一个或多于一个处理器组的一部分。这样的处理器核心组被称为节点，并且它们与公共共享存储器、存储器控制器和多个互连链路相关联。 值得注意的是，所有存储器控制器在逻辑上由物理上所有组中可用的所有处理器核心共享1.1. 内存拥塞问题内存拥塞与网络中所有连接节点之间的资源分配有关。连接将是这样的，节点可以在可接受的性能水平上操作事务。在这种情况下，当需求超过或将工作只是接近的能力，网络资源。网络资源包括链路带宽、内存大小和所有中间节点的处理能力。然而，即使对于低负载，资源分配也是必要的，但是当负载增加时，问题变得具有挑战性。由于单个节点上的大量负载，公平性问题将https://doi.org/10.1016/j.jksuci.2020.05.0111319-1578/©2020作者。由爱思唯尔公司出版代表沙特国王大学这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.com新墨西哥州Upadhyay，R.S.Singh/ Journal of King Saud University3865发生，并且低开销将增加，这降低了性能。为了使问题更清楚和更容易理解，图1示出了所提出的具有四个节点和十二个处理器的架构：（每个节点四个处理器），这与MulyaAgung 等 人 提出 的 问 题 相同 。 （ 2017 ） 和 Mulya Agung et al.（2019年）。每个节点都与一个本地DRAM和一个内存控制器连接。所有节点都可以通过内存控制器和互连链路访问数据。这些控制器通常是高速连接，例如QP互连（Ziakas和Baum，2010）。然而，这些节点通过高速互连连接，但另一个连接的节点需要比父数据 节 点 更 高 的 延 迟 （ Bailey ， 1994;Boboon-Wickizer ， 2008;Corbet，2012; David和Trigonakis，2013; Lennis，2013）。内存延迟取决于数据的位置，从哪里获取数据。因此，为了明确地表达数据移动，这项工作使用MPI来编写其提出的算法。基于论文中讨论 的 问 题 （ Mulya Agung 等 人 ， 2017; MulyaAgung 等 人 ，2019），本文讨论了可用于不同内核的进程放置策略：CG、FT、LU 和 MG （ Cappello 等 人 ， 2000; Bailey 等 人 ， 1991; Bailey ，1994）。放置方法是基于NUMA的系统的关键任务（Tan Li等人，2017），但它可以通过在MPI进程中可用的映射技术与运行的处理器来实现（Cappello等人，2000年）。每个映射都有一个唯一的ID号，称为MPI秩。实际上，MPI的进程管理器根据它们的映射将每个MPI因此，所有的常规工作都能够在本地访问数据，以减少执行期间发生的损失。由于布局方法采用通信模式匹配，因此采用MPI布局策略改进了局部性数据访问技术。这些通信模式被映射到底层硬件。如果在任何节点处的处理器核的数量都不大，则可以通过减少在存储器控制器处访问的通信模式的数量来提高性能。FabienGaud和Baptiste Lepers（2015）最近提出了一项研究，以优化内存控制器的内存拥塞在这项研究中，他们提出了现代系统的性能显着增加。他们提出的方法的缺点是存储器控制器的延迟较长在现代NUMA系统中，由于访问需要更长的物理距离穿越才能到达一个节点到另一个节点，因此在执行期间，如果任何节点中的核的数量增加，则在任何连接的存储器控制器处的存储器拥塞因此，协调局部性和拥塞成为现代NUMA系统中的挑战性问题（Tan Li等人，2017年）。本文提出了一种通过MPI进程布局技术解决内存拥塞问题的方法1.2. 动机基于科学计算的过程需要更多的共享内存、节点间的事务处理以及良好的管理员来处理来自世界各地的大量数据天气预报、地震预报、深海研究等计算，需要将高速和可扩展性作为一个重要组成部分，将高端计算技术与高性能网络和广域存储管理技术相结合。在这样的系统中，由于它们是并行工作的，任何进程都可以到达任何节点，并在退出之前可以在多个节点上执行这可能只是因为并行计算系统的动态特性根据需求增加一些节点，站在理想的位置。结果，在重负载节点处的等待时间增加，并且系统的性能将降低。这可能是因为重负载节点处的内存队列已满，并且无法将进一步处理的请求入队。这种情况导致内存不可用问题，这通常发生在执行此类需要大量数据处理的科学计算期间。在这种情况下，几个处理请求在短时间内到达节点。因此，大多数计算不能在各自的截止日期内完成。因此，平衡对于减少这种NUMA系统中的存储器拥塞将变得重要。因此，这个问题促使我们解决内存拥塞问题，并努力解决它。1.3. 贡献该方法通过监测通信模式来考虑拥塞的位置，分析互连链路上的通信流量，然后为放置的进程确定正确的映射这些任务是提前完成的，因此处理器之间的负载不平衡也会减少。提出了一种基于MPI的负载均衡减少拥塞算法（RCLB），该算法确定了节点间的进程映射，减少了内存控制器的内存拥塞本文还将所提出的方法与一些现有的布局方法CG、MG、LU和FT（Cappello等人，2000; Bailey等人，1991; Bailey，1994）。所提出的方法还包括一个低级别的在线监测工具来捕获数据，MPI通信模式，数据聚类和数据流量的地方。最后，为了验证的目的，性能评估，通过仿真和实验进行了。评估结果表明，通过该方法计算的进程放置实现了比两个贪婪策略（Packed和Socket-span）和一个局部优化方法（Tree-match）更少的执行时间（Emmanuel Jeannot和Tessier，2014）。1.4. 论文组织本文的其余部分组织如下。第二节介绍了相关的工作。第三节讨论了前提条件（符号、定义和假设）。第四节说明问题陈述和公式化。第5节详细研究了所提出的算法。在第6节中，逐步解释了所提出的算法。在第7节中，验证所提出的方法的实验进行了分析和讨论。最后，第8节给出了结论和未来的指导方针。2. 相关工作本节介绍了一些最近的文献调查，以便通过阅读本节，人们可以很容易地了解工作的水平，并找出迄今为止在这一领域所做的工作的可能性。在这方面，我们将调查分为三类。第一种是基于MPI进程放置，第二种是基于负载平衡，第三种是基于现代NUMA系统上的内存放置（Tan Li等人， 2017年）。负载平衡：在这方面，许多研究人员已经做了一些工作。然而，每一个拟议的工作是重要的，这是非常困难的，包括所有的工作在这里。因此，我们在本文中增加了一些最近的和先进的工作。Bhatele和Kumar（2009）和Mulya Agung等人（2019）提出了分子动力学应用负载平衡算法的优势。另一位作者Pilla和Ribeiro（2012）提出了一种负载的分层方法●3866新墨西哥州Upadhyay，R.S.Singh/ Journal of King Saud UniversityFig. 1. 二手机器的连接拓扑。在并行多核系统上的平衡，他们发现了一个重要的结果。对于CPU负载表征，HwTo-poLB（Pilla等人， 2012）和Treematch LB（Jeannot等人， 2013）已经在他们提出的算法中计算了网络链路的时延。他们使用了Charm++和任务迁移技术。任务放置领域的另一项工作已经完成（Mercier和Clet-Ortega，2009; Majo和Gross，2011;Rodrigues等人，2010），其中他们已经发现了改善负载平衡的良好调度结果。另一位作者Mercier（Mercier和Clet-Ortega，2009）试图通过结合硬件的层次信息（Pellegrini和Roman，1996 ） 来 改 进 MPI 进 程 的 放 置 Hwloc （ FrancoisBroquedis 和JeromeClet-Ortega，2010）已经收集了一些NUMA机器，在这些机器上，Jeannot（Jeannot等人，2010）已经工作并提出了一种改进NUMA系统性能的分层方法。上述工作与拟议工作的主要区别如下：- 所提出的工作是能够通过分析通信模式来平衡内存控制器上的流量。- 进程在启动时分配，因此处理器核心不需要迁移时间。因此，它不依赖于特定的运行时。过程放置：许多研究者在相关研究中做了一些重要的工作，本文将介绍这些工作。MPI框架（Chen例如，2006）用于基于性能简档来处理集群的不同节点。许多研究人员都认为，形成了相关研究中的几部重要著作，通过本文进行介绍。MPI框架（Chen等人，2006）用于基于性能简档来处理集群的不同节点。Hendrickson等人提出了一种基于图的划分方法，在优化工艺映射方面取得了显著的效果。Zhang等人（2009）和Ma等人提出了另一种算法。他们发现大部分的工作依赖于离线的剖析技术.他们还分析了进程和核心之间的通信轨迹（Mulya Agung等人，2017; Emmanuel Jeannot和Tessier，2014; Chen等人，2006; Zhang等人，2009年）。一位作者Emmanuel Jeannot和Tessier（2014）提出了一种基于树匹配的算法，该算法并不那么先进，但与所选问题相似（Mulya Agung等人，2019年）。在这项工作中，他们预测了NUMA体系结构的通信模式。Mahato和Singh（2017）以及Iman Faraji和Afsahi（2016）提出了一种类似的先进方法。他们已经计算了负载平衡和内存拥塞的进程布局。另一位作者Tan Li等人（2017）介绍了一种对树匹配技术进行比较研究的方法。他们使用了一种基于图的划分算法来跟踪通信模式。这种方法的缺点仅仅是需要离线剖析技术。离线剖析技术本质上是高开销和耗时的。Upadhyay和Singh（2018）在离线剖面技术的基础上提出了另一种方法。所提出的方法不具有这些类型的缺点，因为它在运行时动态映射。我们注意到上述相关工作与拟议工作之间的两个关键区别。●新墨西哥州Upadhyay，R.S.Singh/ Journal of King Saud University3867- 它不采用通信跟踪机制，因为通信模式已被MPI例程直接跟踪- 相关的工作主要集中在数据访问机制：本地访问或远程访问。一般来说，我们可以说，这项工作的重点是MPI进程使用基于NUMA系统的布局方法它直接映射通信模式，减少内存拥塞。内存放置：一些研究人员已经完成了与其他架构相关的更多工作。Iman Faraji和Afsahi（2016）提出了基于CUDA的此类技术的一些类似工作。该包装器公开API调用，通过与多个批处理系统同步来最大限度地减少通信成本，这覆盖了CUDA上运行的某些设备管理。研 究 人 员 还 提 出 了 一 种 基 于 MPI 进 程 的 GPUs 拓 扑 感 知 选 择（Mahato和Singh，2017; ImanFaraji和Afsahi，2016）方案，以减少内存拥塞。通过使用SCOTCH库和图映射算法，Iman Faraji和Afsahi（2016）提出了一种用于MPI库和应用程序的离线分析技术。另一位研究人员Greengard（2016）也提出了他的工作，以最大限度地减少通信成本，而不考虑调度作业的性能干扰。在性能的基础上 ，一些研究 人员已经研 究了用于低 级资源的调 度算法（Brendan Burns等人，2016年分配和最小化David Lo et al.，2016年）以及基于CPU的工作负载分布（Akshat Verma和Neogi，2008年;AlexandruIosup和Epema，2011年; YaakoubEl-Khamra等人， 2010）以及基于GPU的工作负载分配（OnurKayiran等人，2014; Wu和Hong，2013）。然而，所有这些论文都描述了CPU应用程序的性能瓶颈。一位作者Dashti等人（2013）提出了一种不同于所有算法的内存放置算法（本节前面提到）。他们提出的算法能够recc- onciling的数据位置和减少内存拥塞。唯一的关键区别是Dashti等人（2013）使用他们的算法作为Linux内核策略，用于动态内存分配以避免拥塞。3. 符号、定义、缩写和假设3.1. . 基本定义NAS并行基准（Bailey等人，1991年）：NAS并行基准程序是一组程序，作为NASA数值空气动力学模拟（NAS）计划的一部分，最初用于评估超级计算机。它们模仿大规模计算的计算和数据移动特性NAS并行基准测试套件由5个内核（EP、MG、FT、CG、IS）和3个伪应用程序（LU、SP、BT）组成。NPB实现在MPI中编写并由NASA分发多网格（MG）内核（Bailey等人，1991; Bailey，1994）：MG是一个简化的多重网格内核。MG使用高度结构化的（短距离和长距离）通信。默认条目是未修改的NPB内核，因此通过每个节点上的多个MPI进程来实现每个节点使用多个处理器MG基准在一系列级别上进行计算共轭梯度（CG）核（Bailey等人，1991; Bailey，1994）：CG中的一种共轭梯度法，用于计算大型稀疏对称正定矩阵的最小特征值的近似值。这个内核是典型的非结构化网格计算，因为它测试不规则的长距离通信，采用非结构化矩阵向量乘法。傅立叶变换（FT）内核（Bailey等人，1991; Bailey，1994）：FT内核使用FFT求解三维偏微分方程解。该内核执行许多频谱码的本质。这是对所有通信性能的严格测试。下-上（LU）高斯-赛德尔核（Bailey等人，1991;Bailey，1994）：下-上（LU）高 斯 - 赛 德 尔 ， 使 用 三 种 不 同 的 算 法 求 解 非 线 性偏 微 分 方 程 （ PD E ） 的 合 成 系 统 ， 分 别 涉 及 块 三 对 角 ， 标量 五 对 角 和 对 称 连 续 超 松 弛 （ SS O R ） 求 解 器 内 核 。Uncore：Uncore是Intel用来描述微处理器功能的一个术语，这些功能不在核心中，但必须与核心紧密连接才能实现高性能。非核心功能包括QP互连控制器、L3缓存、监听代理管道、片上存储器控制器和Thunderbolt控制器。LLC（Beckmann and Sanchez，2016）：LLC（末级缓存）是内存层次结构中位于主存（DRAM）之前的最后一级，也是延迟最长的一级。这里缺少的任何内存请求都必须由本地或远程DRAM提供服务，延迟很大。LLC未命中度量显示具有突出LLC未命中的周期与所有周期的比率IPC（Vikas Agarwal等人，（2000年）：在计算机体系结构中，每周期指令数（IPC），通常称为每时钟指令数，是处理器性能的一个方面：每个时钟周期执行的平均指令数。它是每条指令周期的乘法逆。记忆延迟（Bailey等人，1991; Bailey，1994; VikasAgarwal等人，内存延迟（英语：Memory latency）是指从请求一个字节或一个字到处理器检索到该字节或字之间的时间。内存控制器不平衡（Cheng，2013）：内存控制器不平衡是所有节点上内存控制器带宽利用率的标准差。拟合优度（Bailey等人，1991; Bailey，1994; MulyaAgung等人，2017; Mulya Agung等人，2019年）：拟合优度检验是一种统计假设检验，用于查看样本数据与正态分布总体的分布拟合程度。换句话说，这个测试显示你的样本数据是否代表你期望在实际人群中找到的数据，或者它是否有某种程度的偏差。拟合优度确定观测值与正态分布情况下模型预期值之间的差异。3.2. 使用的符号本文中使用的所有符号都列在表1中，这将是理解问题公式和其他使用的描述所必需的。在各个章节中，还根据其用途详细描述了这些公式。3.3. 使用的缩写本文中使用的所有缩写及其含义汇总在表2●●●●●●●●●●●●3868新墨西哥州Upadhyay，R.S.Singh/ Journal of King Saud UniversityLþ ¼表1使用符号的详细信息。符号意味着额外信息M内存带宽由于缓存层（L3）已经支持，因此存储拥塞并不严重（Georg Hager，2010）。但在弱标度系统中，存储器拥塞变得至关重要。因此，本工作的重点是在交换过程中发生的拥塞问题，i互连数量Sx处理速度，处理器tx问题的执行时间X集群中关联处理器的总体性能x互连处理器的独立性能-–––xi[xi<$12X通过存储器控制器和互连链路在不同节点之间传输数据。最初，工作负载分布在不同的MPI应用程序，支持并行执行。这些MPI应用程序还可以在执行期间发送和接收消息。交换数据的分布可能是不规则的，因此它不能总是与所有其他MPI进程以相同的方向进行通信。值得注意的是，传输的时间和数据量可能会因其可扩展性而异。为了找到架构的可伸缩性性能，可以使用可伸缩性矩阵。可伸缩性矩阵取决于N节点数量算法限制，瓶颈，启动开销和W总数据传输方向h单个处理器数据传输方向l之间的比率快速和慢速CPUc用于缩放系统的AWN性能优势-hi[hi12W––1： 33KAWK1： 6通信可伸缩性矩阵有两个重要的标准，即串行和并行分数。对于可伸缩性矩阵中的一个简单模型，如果问题大小（工作量）为1，则s p为1，即运行时。s是不可并行部分，p是完全可并行部分。为了使其更全面，图1显示了一个场景，其中两组CPU通过互连方法直接连接，并使用前面在第1节中提到的内存控制器框架。基于所示的架构在图1中，并行应用可以描述为（Georg Hager，2010）3.4. 假设本文所需的所有假设汇总于表3中。4. 问题公式化表3并行计算架构的假设。并行假设计算优先级进程协调是网络、主机和进程的同质性是网络速度快网络可靠性高主机速度快主机可靠性高在系统设计中，我们有两个可扩展性标准：（1）弱结垢;（2）强结垢。在强标度中，表2所用缩写的详细信息。缩写意义额外信息NUMA非一致性内存访问–RCLB通过负载平衡该方法MPI消息传递接口编程语言NAS空气动力学数值模拟来评估超级计算机CLB负载均衡记忆测验DRAM”Dynamic Random Access类型的RAMQP棉被包装互连技术CG共轭梯度核–FT傅立叶变换核–陆上下高斯-赛德尔核–MG多网格内核–LB负载平衡–CUDA计算统一设备架构并行计算平台与APIAPI应用编程接口–GPU图形处理单元–苏格兰威士忌图书馆用于顺序和并行图划分的软件包和库静态映射和聚类，顺序网格和超图分区，SSOR对称逐次过松弛以及顺序和并行稀疏矩阵块排序–PDEs偏微分方程–LLC末级高速缓存–IPC每周期–NPB空气动力数值模拟并行基准–OpenMP开放式多处理API支持多平台共享内存多处理编程在C、C++和Fortran所有节点（可实现增益）Lp主上样–和处理器a;b标准化值–S0所有可能的解决方案或切片S0¼½SN0½ [SN1[½SN2;。 . . ;[SNx]新墨西哥州Upadhyay，R.S.Singh/ Journal of King Saud University3869vðÞð Þv¼ð Þð Þð2 Þð Þ ðÞ联系我们2 Þ× ð 2 Þ× × ð 2Fð Þ ðÞPpNð Þ¼¼电话：+86-21 -6888888传真：+86-21-6888888AwN1-slN]1cN]ð9ÞfN由方程式（1）T是任务，N是集群中部署的工作者或节点的数量，p是完全可并行化的分数，f是固定的问题。基于Eq。（1），如果问题的大小是可变的，那么我们需要的运行时间量，已显示在方程。（2）Eq. （3）分别。Ts¼spNa2l½s1-sN]½lclN]的EQ。（9）中，将正鲁棒尺度系统的概念引入到所提出的方法中，其需要被优化。从等式（9），如果增长是稳定的，那么系数c可能是负的，结果可能推断出lN的某个偶然值。因此，本文采用了非负平方优化技术。在这种技术中，不允许系数c变为负值，并且最小的存储器流量将变得可追踪。Ts¼spNa-13因此，基于可扩展性定律，固定概率的串行性能XminXN12ks-Mik其中;xNP0;8N¼ 1; 2; 3;.. . ;n：100lem大小由Eq. （4）、第四季第1集不从等式（10），我们的目标是减少内存拥塞。如前所述，对于任何NUMA系统，f s可以用两种不同的方式交换：要么在同一个节点或者在不同的节点上在第一种情况下，数据交换包括并行性能由等式（1）计算（5）、S p1f<$TpNs1-s存储器控制器上的通信流量，而在第二种情况，数据交换包括通信业务在互连链路和内存控制器上都有。誓，如果通信流量超过的EQ。（5）将取决于加速。我们考虑了一个有p个相同处理器的CPU大小为n的工作负载已在p上执行。设处理器的处理速度为Sx，问题大小为x。因此，处理速度用公式表示为（6）作为：内存控制器的带宽，那么就会发生内存拥塞在我们的情况下，通信模式可以根据内存控制器的带宽而变化，因为某些MPI进程可能会在内存控制器上引发大量流量，带宽从100减小到0。因此，S x问题的x问题的执行时间txð6Þ并且在互连链路和存储器控制器之间发生负载不平衡。因此基于等式（5）Eq.我们可以说，加速比可以是超线性的，并且可以从问题的大小与执行该问题所需的时间之间的比率获得。因此，在本文中，我们将需要计算其基于图1所示架构的新虚拟集群的加速比。在此基础上，计算了所提算法对系统的内存拥塞情况。 从图1，如果我们把x看作几个处理器，M看作带内存控制器的CPU（以带宽（%）为单位），i看作CPU之间的互连，那么总性能几乎等于互连处理器的性能，即总存储器拥塞（存储器控制器上的业务），表示为：xMi：8x2X7其中X是集群中相关联的处理器的性能，其包含具有数据传输方向h的所有互连节点的节点数量。基于Eq。在等式（7）中，x的映射取决于单独的存储器控制器带宽，如（（xM1XM2...XM（i））与数据传输方向和速率相关联。因此，可以说x X是一个向量，几乎等于总内存和互连链接数的乘积因为，所有输入实例都基于图1所示的架构以度量形式定向。1.一、处理器的列顺序（映射为：P0;P2;P8;P10;.. . P5;P7;P13;P15）包含一个行式分布的单阶由于单阶分布，所有具有数据传输方向h的系统都是严格弱标度系统，因为功N是Gustafson标度的众所周知的推导，并且在这种情况下，8小时2分对于这样的系统，加速可以定义为：SxN½ s1-sN]=lcN½s1-sN：8我们可以很容易地说，同一节点上的存储器拥塞高于不同节点。为了减少同一节点上的内存开销（在弱伸缩系统上），我们需要分配所有的CPU，即使至少满足一个约束因此，对于最小的X，本文映射了一个更好的方法，以提高集群的利用率，减少内存拥塞。5. 该算法5.1. 算法算法1和算法2基于MPI_Bcast、MPI_Gather和MPI_Reduce算法，考虑了应用程序的拥塞和局部性。配售策略的执行分四个步骤进行，如下：1. 在第一步中，通过对所使用的硬件部件的调查，检索了关于节点拓扑、冗余控制器、互连链路的信息为了执行此操作，我们使用了一个基于OpenMP的便携式硬件定位（HWLOC）工具便携式硬件本地性工具评估现有系统的拓扑结构，并在树结构中对其建模，这些信息片段对于这样的映射算法非常有用，这些映射算法在MPI进程和系统因此，我们也将这些信息用于我们提出的算法1和2。2. 在第二步中，最大的考虑是基于MPI的应用程序。在这一步中，我们有gath-L-11cN=l通过使用所提出的算法来研究通信模式从等式为了估计可实现的增益，我们假设s是小于1的可忽略的串行部分，即，cN>cIN=I。 然而，通信开销甚至可以随着N而增加，但是增量必须稳定而不是线性的。所以，Eq。（8）导致Eq。（9）求出可实现的增益。Rithm 1.在该算法中，一个初步的剖析技术也被用来收集有关目标节点的信息。 分析技术在两个不同的领域发挥作用：空间和时间领域。我们提出的方法（算法1）认为这两个域收集通信，2.3870新墨西哥州Upadhyay，R.S.Singh/ Journal of King Saud University算法1：收集节点信息和通信模式（NIC）算法2：通过负载均衡减少拥塞（RCLB）感染模式。在这两种情况下，MPI过程的执行及其排名可能会有所不同。但在我们的例子中，它被认为是两个域的常数。通信模式包括不同的参数数据：时间序列，时间戳跟踪，消息数量和所有MPI应用程序的大小。我们正在使用由Bosilca等人（2017）开发的MPI通信工具的在线动态监控，该工具适用于MPI和OpenMP。虽然这个工具被归类为一个低级的监控工具，但它仍然在使用。GeorgeBosilca等人通过添加更多的管理层再次改进了这个监控框架。这个工具能够来追踪这两种情况下的通信模式：点对点或集体。此外，它有一些限制，使它可以跟踪有限数量的进程在一起，执行模式不会受到干扰。3. 在第三步中，为了分析存储器拥塞，需要时间序列数据。一旦从上一步骤中获得数据，调查报告就会确定通信事件的地点和时间一般来说，一个亲-CESS由两个应用程序进行通信。这些应用程序同时在同一节点上执行。因此，存储器拥塞发生在存储器控制器及其互连链路处。利用MPI进程排序技术和通信事件的时间跟踪，可以识别出这对存储控制器和互连链路在所提出的算法2中，进程以成对的形式分组，即，进程的总数和节点的总数已经映射在一起。这些组可以在不同的节点上同时进行处理，也可以在不同的时间戳进行通信。4. 在第四步中，我们应用了K-均值聚类技术来获得组，因为在程序开始时，组对进程是未知的。在这种聚类方法中，通信模式需要一个额外的参数K来指定对。此参数对内存控制器点的通信量有积极影响。因此，它成为重要的是要估计的数量对进程作为一个组提前。在这里，K-means聚类技术新墨西哥州Upadhyay，R.S.Singh/ Journal of King Saud University3871●¼ ðÞ1/1XXL不p从K = 2开始，然后开始向估计算法增加：拟合优度检验。随着K值的增加，进程对的时间戳变小。最后，我们根据相同的时间戳映射了同一分类组中的MPI层与核之间的通信模式。基于这四个步骤，实现了算法（1和2）。6. 将算法6.1. 算法一：收集节点信息和通信模式（NIC）在算法1中，目标函数是减少处理器上的负载。 输入函数xi乘以Mt;k;S0;x作为输入传递到该算法，其中M是具有时间的存储器带宽，迭代索引，可能的解和互连处理器的个体该过程是接收dem_Signal，在算法2中，我们对参与的处理器总数应用MPI_Bcast，并计算单个处理器上的分布负载。最后，我们收集了关于处理器和存储器控制 器 和 互 连 链 路 处 的 拥 塞 的 在 该 算 法 中 ， 我 们 使 用 C 库 集 成MPI_Bcast和MPI_Gather函数。在从算法1获得处理器对的数目之后，RCLB算法执行具有和它们各自的核的进程之间的匹配。匹配因子保证了存储器控制器和互连链路上的缩减率和负载平衡。负载平衡是通过使用上述等式来完成的。（11）Eq. （十二）、衡量MPI在我们的工作中，我们已经提出了一些重要的信息，大量的数据集的大规模通信。我们已经提出了基于并行算法的结果，广泛用于各种MPI-并行实现。我们使用了优化的算法源代码，特别是对大小。它还能够评估数据加载时间和等待时间。等式（13）定义了具有X个处理器的集群的负载。输入参数与所有关联节点。这里，通信开销甚至可以随N而增加，但增量必须是载荷C×X×RkMpið13Þ稳定性优于线性。因此，我们将非零系数与相关节点N相加。下一步是决定Clus- ter_Size，这是工作节点的数量和它们拥有的处理器数量的比率。然后，在下一步中，我们在MPI_Bcast例程的帮助下在所有关联节点之间广播消息在下一步中，我们已经迭代地计算了所有处理器的执行时间，并部分存储在内部通信节点中。我们正在根据它们的参与计算所有处理器级别然后，在最后一个循环中，我们计算了集群上的最终负载然后，MPI_R-educe例程通过load系数调用load函数，减少分布负载，并将聚合结果存储在处理器中。在运行此算法时，通信模式可能会根据内核的配置而多次变化。如前所述，放置策略基于本质上是静态的MPI过程，因此它支持执行的理想映射。因此，存储器控制器和互连的链路需要优先级列表，用于基于从高到低的通信量进行优化。本文计算了两种方法。第一个度量是基于进程对组的负载。该度量被定义为加权度量Wp，其包含基于每个组的消息的归一化数量及其大小的总和。其中，Wp由以下等式定义：（十一）、其中k是具有不同的系统组件组合的组中的对的数目，所述不同的系统组件组合具有x个处理器。 Mpi是该组中配对处理器的值。RCLB算法通过构造大小为n的桶来分配存储器控制器的负载这些桶由节点表示基于负载，所有处理器被分类并放置在每个桶中。在放置进程时，使用贪婪基于该技术，不允许桶保持多个具有相同秩的进程在一起，并且单个进程不能使用多个桶。在该过程中，处理器对以优先级顺序执行，即，从最小到最大。同样的程序也适用于团体。该任务通过以下步骤（第15至18行）实现（MulyaAgung等人，2017;Mulya Agung等人， 2019年，在Algorithm2.在不违反桶从每组中选择两个进程并将其放入单个桶中。这一程序以循环方式进行。6.3.复杂性分析本节研究所提出的方法的运行时复杂度Wp¼ampnMi1/1Spb.b.SI1/1ð11Þ耗氧物质我们评估了提出的模型的基础上，两个参数：● 基于计算权重：始终更改最佳其中mp是由对p交换的消息的数量;sp是由对p交换的消息的大小，并且n是所有组中的对的数量。消息数量和消息大小的归一化值分别由a和b第二个度量是Lc，它是组c的负载：NPC解决方案，我们需要一个连续的递归过程，该过程在非负最小二乘优化算法的帮助下运行（Tang et al.，2011年）。由于假设数据是连续运行和加载的，类似的一类优化算法需要几乎恒定的运行时间进行迭代。这一步随着每一级的输入数据从基本到高级而变化。因此，我们可以说，这个模型需要OmaxLc¼1/1Wpi12时间● 基于计算信号的分布：让我们假设所有其中Npc是组c中的对的数量，Wpi是组c中第i对的Wp的值。6.2. 算法二：● 通过负载均衡减少拥塞（RCLB）连接到集群的处理器在思想上是相同的。基于可达增益的模型的复杂度为O（Nn）. 在每一个MPI进程中，不同的节点关注同一个思想。MPI节点上最后一次加载x时，需要取Nn×NRank，由x¼My计算。所以在这种情况下，复杂度将与Y^Mw相同。因为已知X3872新墨西哥州Upadhyay，R.S.Singh/ Journal of King Saud UniversitypMPI编程中的方程的复杂性可以在HPC通信环境中以非零代价潜在场景来计算，其花费几乎（O N n<$N n K）时间。一般来说，在大带宽和小延迟的限制下，改进的加速比是处理器速度慢的并行计算机的有利工作模式因此，我们已经找到了理论证据，证明用缓慢的处理器建造大型机器确实是有用的，我们的系统比训练机先进得多7. 仿真与结果分析本节讨论实验结果并验证所实现的性能。本文中提出的所有结果都是基于所提出的方法，其次是两个实验。基于Real 系统 ：第 一个 实验在 基于Intel Xeon Phi 200 系列 的NUMA系统上进行。7.1. 实验装置第一个实验的实验设置：至强融核7210系统配备有64个核心，128GB的主内存和两个基于英特尔的7210处理器的16个核心，每个处理器运行的最大Turbo频率为1.50 GHz。该系统由四个节点组成，每个节点有八个核心，处理器频率为1.30 GHz。所有节点经由QP互连（Ziakas等人，2010年）。节点的连接拓扑如图1所示。所有的实验都是使用MPI 和 OpenMP 来 完 成 的 。 我 们 使 用 了 四 个 NAS 并 行 基 准 测 试（NPB）内核在我们的实验。它们列在下面：多网格（MG）内核（Bailey等人，1991年）：不规则通信的多网格（MG）内核。共轭梯度（CG）核（Bailey等人， 1991年）：共轭梯度（CG）内核的不规则内存访问和通信。傅立叶变换（FT）内核（Bailey等人，1991年）：傅立叶变换（FT）内核的所有对所有的通信模式。下-上（LU）高斯-赛德尔核（ Bailey 等 人 ， 1991 年 ） ： Lower-Upper Gauss-Seidel 内 核（LU），具有不规则内存访问的求解器。我们比较了RCLB三个进程布局算法：Packed，Socket-span和Treematch。Packed非常接近于logical恒等式，并且支持贪婪方法。例如：要映射一个常数值，需要考虑n个数字的计算步骤。Socket-span用于将进程映射到不同节点的核心。Socket-span策略中的过程这种类型的设施由MPI以循环方式提供。树匹配也是一种布局策略，它根据进程在内核之间的分布来映射进程。我们使用Treematch v0.4来完成这个任务。在这里，消息的数量具有相同程度的贡献工作w所提出的RCLB算法。我们已经习惯了NPB的类别（Bailey等人， 1991）即，C和D.在NPB内核中，这些类被用作平均和大问题大小。 用于该实验的系统具有28 个处理器，因此执行MG 、 CG 和 FT 内核的进程的数量（