论文题目：Idle Period Propagation in Message-Passing Applications
文章时间：2016年12月
会议/期刊：HPCC 2016
作者背景：KTH 瑞典皇家理工，计算机学院
笔记时间：2021年10月25日周一
论文地址：https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=7828475
引用：8+
Abs
MPI应用的不同进程中不可避免的存在idle period。当额进程的idle time 是很好理解的，可能来资源系统或者架构的随机延迟，然而空闲时间是如何从一个进程转移到另一个进程的目前尚未明确。理解如何产生，就可以避免发生。为了理解传播模式，我们引入了一个方法论来trace空闲时间，当一个进程在等待数据从原发传过来。我们在三个系统上做了实验，我们确信空闲时间在不同的进程间移动并且有着不同的阶段。我们的方法可以识别自同步现象。
第一章
HPC中一个非常引人注目的课题是，随机的系统噪声和idle time是如何传播和影响系统性能的。事实上，实验证明随机的延迟在单个进程上发生在纳秒到微妙的级别，在不同进程间传播后，最终达到毫秒级延迟。尽管许多研究都在试图理解噪声是如何参数和影响单个进程的，导致噪声在大规模并行作业的不同进程间传播的机制还尚未明确。对噪声传播的完整理解可以使应用开发者在设计并行通讯时避免噪声的传播和性能的下降。
大多数并行科学计算软件遵循领域拆分的策略。这些应用大人物拆分成小的领域，指定子领域的工作到一个进程中。例如，当一个热力学公式需要有限差分技术时，整个模拟过程分解为一个在求解空间的计算网格，问题的变量来资源网格的点。整个计算网格随后被划分为更小的网格，这些变量的计算被分配到不同的进程上。在每个计算的循环中，每个进程只更新自己网格上的点数据。然而计算过程中，需要同步来交换邻居的数据。
因此，MPI程序需要在计算阶段和通信阶段中变换。理想情况下，每个进程在相同的时间计算完成，然后交换数据。然而现实中，软件硬件都可能造成计算速度的不一致，比如温度就是一个很重要的影响因素。提前完成的任务需要等后面的任务，这个等待的时间就是idle time。单个进程的idle time 好理解，但是不同进程间不是由通信造成的idle time的传播是一个尚未明确的问题。
对MPI程序的模拟表明，一个进程等其他进程时会产生idle time ，但是这个idle time 会在不同的进程间传播成wave[1]。
在超算中，产生delay的原因主要有两种
- 进程的不平衡
不同的进程的计算量可能不同。设备温度，系统噪声，os抖动都困难造成延迟。点对点通信的本地隐式的同步使得idle time 在通信进程间传播
2.共享资源
当两个进程同时使用网卡时，会造成很大的性能下降
本文的目的是研究idle time 在不同进程间的传播。提出了一个通用的方法来追踪idle time。
1.我们通过实验证明idle wave在MPI程序中的存在。模拟实验证明它的存在，但是没有实际实验证明。
2.我们展示了idle wave的不同阶段。
- 我们第一个展示出MPI应用可以自同步，展示具有相同频率但不同阶段的空闲时期。
第二章 相关工作
先前基于模拟的idle在多个进程间传播工作，是基于特定通讯模式的，如邻居通信和集合通讯。LogGOPSim模拟器预测了MPI进程间的wave传播速度依赖于平均计算时间和网络参数。蒙特卡洛模拟器表明特定类型的集合操作有着隐藏进程不平衡的属性且可以最小化idle传播时间。不同于他们的研究，本文用实验追踪了idle的传播。
本课题的研究方案，噪声注入和模拟。系统噪声主要是由内核调度器产生的，相关的研究和解决方案都很多。
研究工作把os噪声分为高频短时间和低频高时间噪声，对HPC中的应用影响不同。有工作是作者部分的。
对系统噪声工作的拓展可以导致一些micro and lightweight kernels (LWKs)的发展。一些工作的主要目的是预测HPC系统的性能和可扩展型。
这里的相关工作看得我一头雾水，这些工作的内在联系是什么，是怎么联系起来的，
第三章 方法论和实验准备
3.1 trace data
为了研究idle periods的传播时间，我们需要首先测量单个进程的idle时间，当它等待接受远程进程发送的消息并且随后重建所有进程间idle period的传播。本文工作，等待数据的时间被测量为等待一个接受任务的完成。直接测量费杜泽的MPI操作很直接，始于MPI_Irecv，终于MPI_Wait，而在应用层直接测量阻塞通讯是不容易的。因此，我们写了一个扩展库，将MPI_Recv自动拆分成MPI_Irecv+MPI_Wait，并且测量等待的循环次数，使用 Time Stamp Counter (TSC) and the instruction RDTSC。
我们比较了 100次替换和不替换的性能差别，发现差异小于0.01%。我们收集每个应用的idle time ，重新组织idle time的传播。
我们注意到可能使用MPI外部的性能计数器来识别polling the message queue需要的时间。MPI_3的版本有MPI_T来提供计数的接口。然而本文写出的来的时候还没有。这个可以留到未来去做。
3.2 MPI 软件介绍
3.3 测试环境
介绍三个硬件平台
第四章 结果
我们分析了trace数据，并且识别出MPI进程间的idle出阿波。我们发现两个系统self-synchronization的证据。
4.1 idle period的传播
我们研究了在256个进程上100次计算循环的短期执行过程，idle period少，很哪可视化。
idle trace揭示了初始阶段硬件拓扑依赖关系，我们可以从图中清晰看出每个process的硬件关系，我们用线区分不同的节点和不同socket的进程。
在idle time传播的过程中，我们可以看到三个阶段
1， 在socket内部浮现的过程
2，idle wave
3，idle period mixing
我们在三个系统中都观察到类似的三阶段。一个直接的对比如图三所示。
4.2 MPI应用中的elf-Synchronization现象
对两个系统的分析可知，在一段时间后，系统会出现较长时间的idle periods。初始阶段的随机idle periods快速的传播到长规模的结构化idle periods。
分析所有的idle periods可知，尽管三个系统的软硬件都不同，但是他们的idle period非常相似。
第五章 讨论和结论
我们经验性地知道空闲时间在不同的进程间传递。然而传播机制和整体的影响还不明确。
本文的工作中，我们引入一个方法论来追踪MPI应用的空闲时间，使用MPI中阻塞的点对点通信。我们在三个不同的软硬件系统上做了实验，我们发现进程间的自同步表现出一组进程显著慢于其他的进程。
我们的方法允许应用开发者理解MPI应用中噪声的传播，指导他们设计并行通讯模式，来避免噪声传播和性能的减少。
我们提出的方法论适用于任何MPI程序，然而本文只在阻塞的通讯上做了实验。非阻塞的通讯允许计算和传输的overlap。然而现实中，计算和传输不可能完全覆盖，这种情况下，依然存在空闲时间。
在MPI系统中，集合通讯基于点对点通信。阻塞的集合通讯也受噪声的影响。未来的工作将聚焦于空闲时间在集合通讯上的传播，阻塞的集合通讯将被分成非阻塞的集合和一个同步操作。
我们的工作表明需要更多的长期的实验来观察自同步现象。我们在不同的超算系统上发现，旧系统的idle time 在新系统上是一样的。这表明idle 时间的传播问题对于当前和未来的系统都是一个重要的问题。
