[HPC/Model]A Regression-Based Ap

论文题目：A Regression-Based Approach to Scalability Prediction
文章时间：2008年以前
会议/期刊：ISC 2008
作者背景： The University of Georgia LLNL lab
笔记时间：2021年10月10日周日
论文地址：https://dl.acm.org/doi/10.1145/1375527.1375580

本文想用一个黑盒的方法预测，并行程序随着规模增加，运行时间的变化的预测模型。
误差使用的是相对误差，
模型利用了最简单的线性对数模型，还用了log^2模型，预测效果在6%-17.3%之间。

一个很基础的方法。
我们能从中学习到什么呢？
一个新的研究方向？并行程序scalability的性能预测？

2.3
在并行程序规模增加的时候，计算和通讯的变化程度是不一致的。如何将这个变化建模出来？
本文提出了2个技巧。

在负载均衡做的好的应用中，计算占比随着processor的数量增加而增加，而通讯的变化是随着应用变化的，它可能随着processor的增加而增加，也可能减少。

一个方法是在使用不同processor中的最大计算时间，通讯时间在不同的processor中选一个固定值。
另一个方法是关注并行代码执行中的critical path，即最长没有blocking的path。这条路径上的通讯就是单纯的通讯时间。

第三章 实验方法论

我们选择好了7个并行代码。五个来自NAS，2个来自Blue。

小规模的p选择了1/8，1/4，1/2

实验结果其实不是很好。

第五章 相关工作

神经网络模型的工作，误差在10%左右，分段多项式回归也有相似的结果，不同于先前基于回归的方法，我们通过对计算和通讯的分离，实现了对更大规模的扩展。

还有很多黑盒的建模方法存在。有用泰勒展开来近似扩展的，这是一个可以和本文工作相辅相成的方法。
还有部分执行的办法，但是该办法局限于运行系统。
还有一个通过静态和动态分析在不同的架构上预测性能，之后扩展成性能瓶颈分析。但是这个工作需要编译器的支持。
我们的工作只需要考虑PMPI库。

MetaSim提供了一个性能模拟框架，它利用指令机制收集内存traces，然后支持不同架构上的内存性能模拟。该工作也可以利用MPItrace来建模网络性能。但是这个工作不支持scaling的预测。

也有白盒的工作，对代码和机器状态的信息进行了详细的分析。
也有类似本文的黑盒工作，但是他们需要很多的effort，对应用和架构进行仔细的分析。
还有一些白盒的工作需要修改代码来预测结果。

还有很多工作聚焦于分析建模。最有名的模型有LogP和BSP模型。LogP模型使用延迟，开销，gap和处理器的个数来决定并行算法，BSP模型使用supersteps 来表示计算的阶段。

还有一些MPI风性能分析工具。本文使用Schulz的代码查找critical path。

六，总结

本文的主要idea是，利用多参数回归模型和小规模运行的数据来预测大规模运行的性能。
我们的方法效果还不错，开销也很小。

future work
更大规模的结果预测；负载不均衡的环境预测；最适合的小规模训练是多少；调研一个巨累方法预测内存结构对计算时间的影响；对通讯细粒度建模。