LogP模型中基于评估的自适应MPI集合操作.docx

A.A. Paznikov et al. / Procedia Computer Science 186 (2021) 323–330 PAGE 329 PAGE 330 A.A. Paznikov et al. / Procedia Computer Science 186 (2021) 323–330 LogP模型中基于评估的自适应MPI集合操作 摘要 以MPI(消息传递接口)为代表的消息传递模型是分布式计算机系统的主要并行编程工具。大多数MPI程序包含集体通信，它涉及并行程序的所有进程。集体沟通的有效性对程序执行的总时间有很大影响。在本工作中，我们以屏障同步为例考虑了集体通信的自适应算法的设计问题，屏障同步是最常见的集体通信类型之一。我们开发了自适应屏障同步算法，在中央计数器、组合树和传播屏障等算法中，次优地选择了并行MPI程序中的屏障同步方案。自适应算法在LogP模型中选择执行时间评估最小的障碍算法。LogP模型考虑了计算资源的性能和点对点通信的互连。该算法已在MPI中实现。给出了在集群系统上的实验结果，分析了算法选择对LogP参数值的依赖性。特别地，对于少于20个进程的数量，自适应算法选择组合树，而对于更多的进程，自适应算法选择传播屏障。与最常见的确定障碍算法相比，开发的算法将障碍同步的平均时间减少了4%。 关键词:集体；集体交流；屏障；屏障同步；分布式计算机系统；LogPMPI并行程序设计 1。 介绍 分布式计算机系统是目前高性能数据处理的主要工具。分布式计算机系统是基本计算机的集合。与通信网络(互连)通信。基本计算机可以被表示为具有专用加速器的处理器核、处理器或多核SMP/NUMA节点(例如。图形处理器或类似至强融核的多核处理器)。一个系统中基本计算机的数量可能超过几百万，特别是在分散的地理分布系统中[1，2]。例如，Summit超级计算机(TOP500第一名)包含超过1000万个处理器内核。这类系统的大多数并行程序都是在以MPI(消息传递接口)标准为代表的消息传递模型中开发的。 现有的大部分MPI程序包括涉及并行程序所有进程的集体通信(集体)。集合占并行程序总执行时间的很大一部分[3]。因此，集合操作的效率显著影响并行程序的可扩展性，因此设计新的集合用于消息传递以及其他并行编程模型，如PGAS [4，5]，RMA [6，7]或混合(如MPI+Threads) [8，9]和actor [10]模型在今天是迫切的。集体优化工作的主要方向是设计基于点对点通信的新的可扩展的集体算法。 屏障同步(Barrier)是MPI中最常见的集合之一。屏障实现了进程的等待，等待所有进程到达程序中某个确定点的时刻(图。1). 屏障包括捕获和释放阶段。当一个进程到达捕获阶段时，它开始等待其余的进程。在所有进程被捕获之后，它们将被同时释放 图。1.屏障同步 2。 相关作品 屏障同步现有的主要算法有中心计数器[11]、布鲁克算法(蝴蝶屏障)[12]、组合树[13]、锦标赛[14]和传播屏障[13]。当前的大部分努力旨在改进这些算法。 工作[15]提出了组合树算法的自适应版本，以最小化每个树节点中的开销，包括捕获和释放阶段。在[16]中开发的算法旨在无限带宽网络。工作[17]提出了一种功耗优化方法和一种基于LogP模型的处理器频率缩放方法。文献[18]提供了中心计数器、组合树、传播障碍和锦标赛算法的验证方法。作者的工作[19]分析了Java中屏障同步算法的效率。论文[20]提出了使用LogP模型优化分层计算机系统上集体通信的方法。 MPICH [21]库使用传播屏障，而Open MPI [22]实现了自适应方案，根据进程数量选择中央计数器或组合树算法(大量进程选择组合树)。 障碍算法的确定选择的主要缺点是无人算法不能保证最小的通信时间。关于这一点，我们可以使用自适应方法，在程序执行过程中实现算法的动态选择。在选择算法时，我们需要考虑消息大小、进程间的通信强度以及计算机系统的体系结构属性。 现有的大多数用于MPI通信的自适应方案使用霍克尼模型来评估通信时间。该模型没有考虑现代CS中点对点通信的实现，因为它没有对网络流水线和计算/通信重叠进行建模。在这项工作中，我们使用LogP模型[23]来高精度地评估点对点通信时间。在设计算法时，我们尽量减少障碍同步的时间。 请注意，LogP模型是LogGP [24]、PLogP [25]、LogGPS [26]、LogGOPS [27]等从动模型的基础。 3。 LogP模型 LogP模型的主要参数是(图。2):L–通信环境的延迟(上限)；o–通信开销(发送或接收单个消息的时间)；g–间隙(通信带宽，发送或接收两个连续消息之间的最小间隔)；p–处理器数量。 为简单起见，将m