SecBCache: Evaluating Banked Interleaved Word-Granularity Sector Cache for gather/scatter Operations on Sparse Data

现代计算机的瓶颈往往不在于其计算速度之快，而在于其移动数据的速度之快。在高性能计算领域，机器需要处理诸如绘制疾病传播图、分析社交网络或模拟气候变化等复杂问题，其中最常见的任务并非进行数值计算，而是从内存中获取数据。当处理“稀疏”（sparse）数据时，情况尤其如此——这个术语描述的是那些大部分潜在空间都是空白的信息。想象一张巨大的电子表格，其中只有零星分布的几个单元格包含数字，而其余部分都是空白。当计算机试图读取这些分散的数字时，它通常必须以一种不可预测的方式在内存系统中跳跃，这种过程被称为间接访问（indirect access）。由于这些跳跃是随机的，计算机无法轻易预测下一步需要什么数据，这使得将信息从存储器移动到处理器的任务成为了一个主要的瓶alock（瓶颈），拖慢了整个系统的速度并浪费了能量。

要理解为什么这很困难，必须了解目前的计算机是如何存储数据的。标准计算机内存是按固定大小的块进行组织的，非常类似于一家只一次借出一整本书，即使读者只需要其中一页的图书馆。当计算机请求特定数据时，内存系统会获取整个数据块，即所谓的缓存行（cache line），其大小通常为 64 字节。如果计算机只需要该块中的一两个数字，那么其余的数据也会被抓取并存储，从而造成不必要的消耗和数据通道的拥堵。对于“稀疏”工作负载，这种低效性会演变成严重的问题，因为在这种情况下，计算机可能需要从内存的不同部分收集数十个无关的数字来执行单次计算。在这些场景中，计算机在移动无用数据上花费的时间比在实际工作上花费的时间还要多。

来自新墨西哥州立大学、劳伦斯伯克利国家实验室和佛罗里达国际大学的研究小组提出了一种处理此问题的新方法，称为 SecBCache。他们的研究重点是用于科学模拟和机器学习的一种特定计算机架构，在这些领域，数据的访问模式通常是分散且不规则的。研究人员设计了一个专门的内存组件，改变了数据获取和存储的规则。该设计不再每次抓取一个大的固定数据块，而是允许计算机仅获取并存储其真正需要的微小、特定的信息片段。他们使用一个详细的现代处理器计算机模拟器测试了这个想法，运行了用于图分析和矩阵乘法的真实世界数据集。结果表明，这种新方法可以显著减少计算机写入其内存的数据量，降低运行这些任务所需的能量，并有可能提高访问信息的速度，且无需更改编程语言或计算机理解的基础指令。

研究人员创新的核心在于他们如何重新组织内存存储。他们将标准的、大型的内存块分解成更小的、8 字节大小的块，称之为子扇区（subsectors）。在传统系统中，如果计算机需要一个数字，它必须加载整个块。在新的 SecBCache 系统中，内存被分为八个独立的节（banks/sections），可以同时进行访问。当计算机需要收集一系列分散的数字时，它可以同时向这些不同的节发送请求，仅获取所需的特定 8 字节块。这类似于一个图书馆，它不再是把整本书交给你，而是有八位不同的职员，可以在同一时刻从不同的书中为你抽出你需要的单页。这种设计使计算机能够避免获取无用数据的浪费，同时仍能保持标准内存系统的速度和组织性。

为了验证这个想法在实践中是否可行，研究人员使用名为 gem5 的工具构建了一个虚拟版本的计算机处理器，该工具可以极其详细地模拟硬件的行为。他们编写程序让这台虚拟计算机运行两种常见的科学任务：广度优先搜索（一种探索社交媒体连接或道路地图等网络的方法）和稀路矩阵乘法（一种涉及大型数字网格乘法的物理和工程计算，其中大部分条目为零）。他们使用 16 个不同的真实世界数据集对这些任务进行了测试，范围涵盖从电子邮件网络到电网模型。对于每项任务，他们都将新的 SecBCache 设计与使用传统大块数据的标准常规内存缓存进行了对比。

模拟结果显示出显著的效率差异。在标准系统中，计算机经常获取一个完整的数据块，但最终使用的却不到一半，在某些情况下甚至只有 18%。这意味着对于检索到的每一份有用数据，系统都在浪费能量和带宽来移动数倍的无用数据。SecBCache 设计通过仅获取所需的特定 8 字节片段消除了这种浪费。对于图搜索任务，新设计减少了写入内存存储的数据量，中位数降幅为 63%。对于矩阵乘法任务，这种减少更为剧烈，写入数据的中位数降幅达到了 80%。这意味着对于测试的许多数据集，新系统写入的数据仅为旧系统的极小部分，大幅削减了减慢计算机速度的内部流量。

除了节省空间外，研究人员还观察了这种设计对内存访问速度的影响。由于新系统可以同时访问多个节，它具有并行处理多个请求的潜力。然而，研究人员指出，实际的速度增益取决于数据的分布情况。他们创建了一个数学模型来估算访问数据所需的时间，计算了两种情况：一切运行完美的最佳情况，以及请求因等待同一个节而卡住的最坏情况。在保守的最坏情况假设下，该模型预测新系统将使图搜索任务的内存访问延迟降低 2-6%，并将矩阵乘法任务的延迟降低 50%。这些数字代表的是内存系统本身响应的时间，而不是计算机完成整个程序的总时间，但它们表明内存子系统在获取处理器所需数据方面的速度有了显著提升。

研究人员还检查了构建这样一个系统的物理成本。他们使用标准的行业工具来估算新内存设计的尺寸和功耗。他们发现，管理这些较小、分节数据的额外硬件所占用的空间最多仅为计算机内存层级总面积的 2.46%。这是一个非常小的足迹，表明该设计可以添加到现代处理器中，而不会占用显著空间。此外，由于新系统向内存阵列写入的数据少得多，因此它消耗的能量也更少。模拟显示，对于测试的每一个数据集，内存系统的动态能耗都下降了，降幅从百分之几到超过 80% 不等，具体取决于数据的稀疏程度。

这项工作最重要的方面之一是，它不需要程序员重写代码或学习新的方式来告诉计算机做什么。研究人员设计 SecBCache 是为了兼容现有的用于收集和散布数据的指令。在现代处理器中，存在特定的命令允许单条指令加载多个非连续的片段。新的内存系统只是通过确保仅移动必要的数据，使这些现有命令变得更加高效。唯一需要的改变是一个简单的软件标记，用于告知计算机哪些部分的内存包含此类分散数据，从而允许硬件自动将这些请求路由到新系统。这种方法避免了对复杂新编程模型或专门硬件加速器的需求，而后者往往难以被整个行业采用。

研究还强调了该方法在何处可能不是那么有效。在数据非常密集且可预测的情况下（例如，当计算机读取一系列紧挨着的数字时），传统的获取大块数据的方式运作得非常好。在这些特定场景下，新系统有时表现稍差，因为它必须逐个获取每个片段，失去了大块数据带来的“免费”数据优势。然而，研究人员强调，他们的设计专门针对日益增长的涉及稀疏、不规则数据的类别，这类数据在人工智能和大数据的分析领域正变得越来越普遍。对于这些应用，仅获取所需数据的能力超过了获取所有数据的收益。

研究人员谨慎地区分了直接测量的内容与估算的内容。写入数据的减少量和能量节省量是从内存系统的模拟中直接测量的。然而，访问速度的改进则是通过一个数学模型推导出来的，该模型估算了如果系统能够同时处理多个请求时会如何表现。虽然模拟显示硬件可以处理这些请求，但模型提供了一个基于不同部分被同时请求频率的延迟范围。研究人员指出，这些是模拟的延迟而非最终应用的保证加速，但它们有力地表明内存子系统的瓶颈将会减轻。

在计算机科学的宏观背景下，这项工作解决了计算方式正在发生的根本转变。随着机器从简单的线性计算转向复杂的、数据驱动的任务，关于内存应如何工作的旧假设正变得不再适用。始终获取大块数据的想法是那个数据密集且可预测时代的遗产。SecBCache 设计展示了一个未来，在那里的内存系统将更加灵活，能够适应现代算法的不规则需求。通过证明构建一个既高效又兼容现有软件的内存系统是可行的，研究人员为提高下一代科学和分析工具的性能提供了一条切实可行的路径。

研究结论认为，虽然没有一种方案能适用于所有的计算问题，但处理稀疏、间接数据访问这一特定挑战可以通过针对性的架构变革来解决。研究人员证明，通过将内存分解为更小的、可独立访问的片段，并以允许并行访问的方式进行组织，可以大幅减少当前系统中存在的能量和带宽浪费。这种方法不需要对我们如何编写计算机程序进行革命，而是对硬件如何处理我们已经要求其处理的数据进行进化。随着对处理大规模、复杂数据集的需求不断增长，像 SecBCache 这样的设计可能会成为保持计算机快速且节能的关键，确保移动数据的瓶颈不会阻碍计算本身的潜力。