ACM通信
点/对位
论计算模型:要点:我们必须把计算模型扩展到考虑成本和地点
来源:盖蒂图片社
几十年来，我们一直使用RAM(随机存取存储器)2和PRAM(并行RAM)模型5同时用渐近分析来衡量算法的复杂性。RAM和PRAM模型处理所有操作，从一个整数加到一个全局内存负载作为单位成本。这种近似在计算的早期是合适的，当时计算和通信的成本是相当的。然而，随着时间的推移，先进的半导体技术导致算术和逻辑的成本下降了数量级，而通信成本的下降速度要慢得多。因此，今天从主内存中获取两个32位的单词会消耗1.3nJ的能量，而执行一个32位的添加操作(需要两个32位的单词作为输入)只会减少20fJ 64,000倍的能量。像RAM或PRAM这样的计算模型，如果将这两种操作等同对待，就不能很好地估计计算成本，因此也就不能很好地比较其他算法。
通信是计算的主要成本。无论我们认为成本是能量还是时间，现代计算都以通信为主。32位的添加操作只需要20fJ和150ps。将两个32位字移动到此操作1mm需要1.9pJ和400ps。移动64位40mm从角落到角落的400mm2芯片需要77pJ和16ns。发射芯片需要320pJ，延时6ns / m。
虽然内存访问是昂贵的操作，但几乎所有访问内存的成本都是通信成本。读取或写入单个位单元所需的时间和精力可以忽略不计。存储器访问的绝大多数时间和精力是由于通信:将地址移动到比特单元，并将数据从比特单元移动到消费者。由于通信占主导地位，访问小型本地内存比访问全局内存要便宜得多。例如，片内SRAM存储器是由8KB (64Kb)子阵列构建的。从子阵列访问64b的开销为0.64pJ，占用300ps。访问256MB内存(大约100mm2)由这些子阵列构建的成本为58pJ和12.3ns，其中57.4pJ和12ns是由于通信，每路15mm，共30mm。因为通信完全控制了计算的成本，我们的计算模型必须考虑通信，为了做到这一点，它必须有一个位置模型。
考虑这样一个问题:计算一张表格的总和，这个表格要适合一个4x4阵列的256核处理器芯片的片上存储器，每个芯片的边长为16mm。每个核心位于2MB SRAM阵列的中心，可以以1mm(往返)的通信成本(1.9pJ和400ps的64b访问)访问本地阵列。对于本地芯片的1/16次访问，随机访问将产生21.3mm的片上通信成本，而对于离芯片的15/16次访问，平均随机访问能量为680pJ，额外的640pJ +21.3mm成本。使用位置模型，我们可以让每个核心对其本地内存中的256K个单词求和，然后将结果转发到树上去计算最终的总和。我们可以通过随机放置线程和数据来执行相同的计算。随机放置的计算的代价是本地计算的354倍。PRAM模型认为局部计算和随机计算的代价是相等的，尽管代价有数量级的差异。
商店或验算。算法和通信之间的巨大能量差异常常决定是否存储或重新计算一个中间值。训练多层感知器(MLP)需要在反向传播步骤中每个层的激活值。如果片上内存不足，激活可以存储到片外内存，每16b激活(写+读)的成本为640pJ, O(n)操作中n是这一层的激活数。另外，激活也可以通过执行矩阵-向量乘法来重新计算。n2)计算，花费160fJ/MAC。PRAM模型建议存储中间结果——偏爱O(n)储存于O(n2) M × v，而对于小于n= 4000，重新计算的成本更低。对于一个典型的MLPn= 256，重新计算的代价要低16倍。
不变的因素。在PRAM模型下，求和例子的渐近复杂度为O(n)，以供本地及随机个案参考。230倍的能量差只是一个常量，添加操作和全局内存访问之间64000倍的成本差也是一个常量。
随着摩尔定律的终结，特定领域的架构正在成为继续提升计算性能的主要候选者。
然而，常数因素确实很重要，特别是当渐近复杂性相同时。本地计算便宜230倍。就像你不会满足于花230倍多的钱买杂货一样，你也不应该因为你使用的是一个不完整的计算模型而花230倍多的钱。大的常数因子甚至可以克服渐近复杂度的差异(这就是为什么Strassen的O(n2.8矩阵乘法6很少使用)。我们的店铺O(n) vs. recompute O(n2)示例，其中对于典型值，较高的渐近复杂性代价较低。
缓存不够。现代计算机使用缓存存储器来提高局部性。缓存在存在时间局部性(即重用)的情况下工作得很好。然而，对于像这里的求和例子这样的计算，它们没有帮助。每个单词只访问一次，没有重用。许多批量大小为1的HPC代码和神经网络模型都有相同的问题。
领域特定的体系结构突出问题。随着摩尔定律的终结，领域特定架构(DSAs)正在成为继续扩展计算性能的主要候选者。3.，4通过消除与通用cpu相关的大部分开销，dsa使算法和通信之间的巨大差距更加明显。CPU的开销将32b的add操作的20fJ变成了80pJ的add指令。相比之下，1.2nJ内存访问只比64,000倍贵15倍。通过DSA消除了这种开销，揭示了算法和通信之间的全部差距。
计算模型是用于性能编程的。在某些情况下，比如用户界面代码，程序员专注于功能而不考虑成本。在这些情况下，naïve代码是速度不够快而且不需要计算模型(RAM、PRAM或其他)来估计成本和比较备选方案。然而，在其他情况下，如训练神经网络模型、执行大型科学模拟和运行优化，成本是至关重要的。效率低下的算法浪费了大量的能量和昂贵的计算时间。正是在这些案例中性能的编程我们需要一个计算模型来估计成本和比较备选方案，而这个计算模型需要反映当今计算硬件以通信为主的特性。
地球要求我们更有效率。2018年，仅数据中心计算机的用电量就占全球用电量的1%，据估计，到2030年，这一数字将增长到3%-13%。1世界上有这么大一部分的能源用于计算，我们有责任设计有效的计算，以最大限度地减少计算的碳足迹。提高效率的第一步是拥有一个精确的模型来分析算法，这样我们就可以为给定的问题选择最有效的算法。我们不能再忽视算术和通信之间的常数因素差异或随着距离的增加而增加的能量。
一种简单、准确的计算模型。对PRAM模型做两个简单的改变就能解决它的两个主要问题。为了解释算术操作(如加法)和内存访问之间的巨大开销差异，我们给它们分配了不同的开销。算术操作仍然是单位成本，但内存操作的成本更高，与距离成正比。每个处理元素和每个存储器分配一个位置l∈l和距离函数D:l×l⇒R定义为确定发送消息或在两个位置之间进行内存访问的成本。
我们可以使用不同的距离函数来模拟不同的计算目标。二维曼哈顿距离模拟了片上通信。位置是x, y距离是两个坐标之间的曼哈顿距离。当任何一个坐标跨越一个芯片边界时，芯片外通信可以通过添加额外的距离来建模(如这里的示例)。
通过让我们推断计算的真实成本，这种并行显式通信模型(PECM)将允许我们设计更高效的计算，并在这样做时减少计算的碳足迹。
参考文献
1.Anders, A.和Edler, T.:到2030年通信技术的全球用电量趋势。挑战6， 1(2015)， 117-157。
2.库克，S.A.和Reckhow, R.A.时间限制随机存取机。计算机系统科学学报， 4(1973年4月)，354-375。
3.Dally, w.j.， Yatish, T.和Han, S.领域特定的硬件加速器。Commun。ACM 63， 7(2020年7月)，48-57。
4.Hennessy, J.L.和Patterson, D.A.计算机架构的新黄金时代。Commun。ACM 62， 2(2019年2月)，48-60。
数字图书馆是由计算机协会出版的。版权所有©2022 ACM股份有限公司
没有发现记录