论文精读（补一）

HPAC: Evaluating Approximate Computing Techniques on HPC OpenMP Applications

摘要

摩尔定律接近极限，需要高性能计算系统的新范式，近似计算很有前景。本文提出了 HPAC ，具有编译器和运行时支持的框架，用于代码标识和替换，可以权衡 OpenMP 应用程序的准确性和性能。在一些 benchmark 中实现了很好的性能提升，在一些 benchmark 上效果一般，探讨了背后的原因。

介绍

• 摩尔定律接近极限，需要新的计算机范式。近似计算是一个很有前途的方法。
• 近似计算在软硬件方面都实现了很好的性能提升，大量相关论文。
• 近似计算的成功依赖于一些应用可以容忍精度损失，这样的性能调整需要大量的领域知识。
• 非高性能计算的应用场景对结果精度一般不太敏感，但在科学计算中，结果精度的降低可能导致致命的错误。因此该领域的近似计算应用很有限。此外，并行计算又是高性能计算的一部分，研究近似计算在并行计算中的应用很重要。
• HPAC 提供了对 LLVM 编译器和运行时库的拓展，可以与 OpenMP 结合，使用#pragma注释，很方便，可用领域广阔。在8个高性能计算应用上进行了实验，主要研究了并行性和近似性对准确性和性能的影响。主要贡献如下：
  • HPAC 框架使用最先进的近似计算技术，循环穿孔，I/O 记忆化，可以很容易地用在使用 OpenMP 的应用中，拓展性也很好，对未来的近似优化技术是开放的。
  • 基于 Clang/LLVM 的近似计算工具链，健壮的生产级编译器，可用于广泛的 HPC 应用，在8个高性能计算应用上进行了测试。
  • 分析了近似计算在高性能计算中的适用性。

背景

• 循环穿孔：5种策略来跳过循环。
• 输入近似记忆化 iACT：耗时函数的输入输出值存一下以避免多次计算，输入在欧式距离内视作相同的输入。
• 时间近似函数记忆化 TAF：想法：局部性原理，连续调用同样的函数往往会得到相同的结果。一定大小滑动时间窗口内，计算 \(RSD=\frac{\mu}{\sigma}\)，其中 \(\mu\) 为该时间内输出的均值，其中 \(\sigma\) 为该时间内输出的标准差，若该值在阈值内，则接下来的一段（预测窗口）大小的函数调用都不计算，直接返回最后计算得到的函数值。接下来，重新精确计算，并评估局部性，如此反复。
• 这些方法的人工调整和参数组合是很复杂的，很难手动调，HPAC 可以自动调整。

设计

• 整体框架
  • 基于注释的编程模型，可独立使用，也可以与OpenMP结合使用
  • 核心组件
    • 编译器拓展
    • 运行时支持
  • 控制组件
    • 预处理脚本
    • 驱动脚本
• 编程模型
  • 和OpenMP类似基于#pragma approx注释
  • 相关语法
    • perfo(type: expr)：5种类型，1个参数
    • memo(type: exprlist)：类型为 iact 时，后跟表大小和距离阈值两个参数；类型为 TAF 时，后跟滑动窗口大小，稳定阈值，预测窗口大小
    • out/in/inout(locator-list)：指定近似区域； out 两种类型都是需要的， in 只有第一种类型需要
• 编译器拓展
  • 拓展LLVM：拓展parser，创建了新的 AST 节点；遍历 AST 生成 IR ，代码生成阶段 HPAC 调用运行时库函数__approx_exec_call
  • 循环穿孔代码生成：语义分析阶段验证循环是否规范，包括循环变量，上下限，循环条件，步长，循环体；简化循环控制元组，传给运行时，其中利用perfoFn函数作为是否执行的判断；和OpenMP组合，仅识别for和parallel for，规范分析并简化
  • 记忆化代码生成：记忆化主要是运行时实现，代码生成主要是传递信息
• 运行时支持
  • 循环穿孔：主要是调用运行时接口，无额外操作
  • 输入近似记忆化 iACT：借助两个数组来存输入输出，没有提到替换策略，只说了满了不存
  • 时间近似函数记忆化 TAF：拿个数组存输出；两状态自动机，初始数组空，进入计算状态，每算一次存一次，计算\(RSD\)，如果满足小于阈值，进入跳过态，跳过计算预测窗口大小次数的调用，用最新的计算值替换，回到计算状态，没有提到替换策略
  • 上述相关数据都是线程私有的，增加了内存开销，但是避免了同步
• 分析工具
  • 预处理器：解析源代码程序，用宏变量填充近似子句参数，驱动定义宏变量的值，然后编译。工具（预处理）会创建多个实例，一个精确计算实例，对每种近似技术生成一个实例。因为参数定义和编译分离，驱动可以接受一个含有近似技术参数的输入配置文件。建构后执行的结果会存起来。

评估

• 指标
  • 精度：MAPE和MCR
  • benchmark：7个用MAPE，聚类用MCR，仅选热点进行分析
• 近似计算配置元组：近似代码区域，近似技术，近似计算参数；此外实验还有线程数作为参数
• Blackscholes：流式应用程序，时间局部性不好，所以循环穿孔的效果更好
• CFD：整体效果很好，精度损失都不大，循环穿孔效果优异，随机策略精度损失小，加速略差
• HPCCG：效果很差，应用对精度非常敏感
• K-Means：计算欧式距离对精度很敏感；近似计算最近的簇效果尚可
  • 随线程增多，线程中的本地表可以更大，输入近似记忆化效果更好；输出近似化记忆先好后坏
• Leukocyte：无循环，富有弹性
  • HPAC 可能引入负载不平衡，随线程增多加速比例下降；可以用OpenMP的调度缓解问题，但是总工作量较少，限制了调度的效率
• LULESH：TAF效果好，误差小，显著加速
  • 减少访存
• Particlefilter：统计应用，循环穿孔效果较好

见解

• 记忆化策略需要激活策略，找到应用无关的激活函数很有挑战性
• 在输入近似记忆化中，欧氏距离的效果并不好，未来将考虑更多技术
• 记忆化策略比循环穿孔更耗费资源；在不增加额外资源的情况下，循环穿孔能获得更好的性能和输出质量
• TAF不应该用于完全没有时间局部性的应用
• 循环穿孔中，int 和 fini 加速最高，随机策略精度损失最低
• 循环穿孔好理解，也好应用；记忆技术和参数间的作用是复杂的
• 并行性和近似度的相互作用是依赖于应用程序的，但实验表明，它们可以实现性能的提升；某些情况下可以用 OpenMP 的调度策略来环节负载不均的问题
• 这一切当然都符合 Amdahl 定律

总结

• 本文讨论了并行性和近似计算的结合，做了一些实验，得到了一些结论。本文开发了 HPAC 框架，实现了最新的近似技术，可拓展，用户使用良好，方便用户进行评估。未来将研究同一应用在不同近似算法上的表现，以及负载均衡问题。