MIT开发的新设备帮助数据科学家用“笔记本”分析大规模图形数据

一般来说，在处理图形数据时闪存要比 DRAM 慢得多。但现在，麻省理工学院计算机科学和人工智能实验室 (CSAIL) 的研究者们已经设计出了一种由闪存芯片阵列和计算“加速器”组成的新设备，它使用廉价的闪存（和智能手机里用的类型一样），仅需一台个人电脑就能处理大量图形。

该设备由一种新颖的算法驱动，它把图形数据的所有访问请求进行分类，从而变成便于闪存快速访问的顺序。它还能合并一些请求以减少排序的开销，比如组合的计算时间、内存、带宽和其它计算资源。

研究人员将该设备与几个传统高性能系统放在一起进行比较，来分别处理几个大型图表。其中包括巨大的 Web 数据共享超链接图（Web Data Commons Hyperlink Graph），这个图形拥有 35 亿个结点和 128 亿条连接线。为了处理这个图表，传统系统全都需要一个耗资数千美元的服务器，并且包含 128 千兆字节的 DRAM。

而通过把两个器件（总计 1 千兆字节的 DRAM 和 1 个太字节的闪存）插入台式计算机，新设备实现了同样的性能。此外，通过组合多个设备，他们可以处理大量图形，高达 40 亿个节点和 128 亿条连接线，没有其它系统能在 128 GB 的服务器上操作这么多的信息。

“最重要的是，我们可以用温度更低和能量消耗上更少的机器来保持同样的性能”，CSAIL 的研究生传相佑（Sang-Woo Jun）说。他是介绍该设备的论文的第一作者。

该设备可用于削减与图形分析相关的成本和能耗，甚至可以拓展它的适用范围。比如说，研究人员正在创造一个程序，它可以识别哪些基因会导致癌症。像谷歌这样的大科技公司，也可以通过使用比以前少得多的机器，来减少他们运行分析时所带来的能源消耗。

“图形处理是一个很普遍的概念”，论文的共同作者 Arvind 教授说，“网页排序与基因检测有哪些共同之处呢？对于我们来说，这是相同的计算问题，它们只是具有不同含义的不同图表。某人开发的应用类型，将决定它给社会带来的影响。”

“分类和减少”算法

在图形分析中，系统基于某个结点与其它结点、在其它度量中的关系来寻找和更新结点值。打个比方，在网页排序里，每个结点代表一个网页。如果结点 A 的值很高，并且与结点 B 相联系，那么结点 B 的值也会相应提高。

传统的系统把所有图形数据都储存在 DRAM 里，因此它们处理速度快，但是价格昂贵、耗能多。有一些系统将部分数据内存分流到闪存上，这种方式更便宜，但速度更慢、效率也更低，因此它们仍需要使用大量的 DRAM。

而新研究使用一种被称之为“分类-减少”（sort-reduce）的算法，它解决了把闪存作为主要存储源的一个大问题：浪费。

图形分析系统需要在巨大且松散的图形结构中，访问彼此可能相距很远的结点。系统通常要求直接访问譬如 4 到 8 字节的数据来更新结点的值。DRAM 可以提供非常快速的直接访问，而闪存只访问 4 到 8 千字节的数据块，并且只能更新其中的几个字节。在图表之内跨越时，如果每次访问请求都要重复这一过程，会造成带宽的浪费。“如果你需要访问整个 8 千字节，但是只用了 8 个字节，然后把其余部分乱扔，那么你相当于浪费了整整 1000 倍的性能。”传相佑说。

“分类-减少”算法则采用所有直接访问请求，并且按照标记符号的顺序把它们分类和排序。标记符号会显示请求的目的地，比如说，把各个结点的所有更新都分到一组。于是，闪存能同时访问数千个请求的、千字节大小的数据块，因此工作效率比以前高了许多。

为了进一步节省计算能力和带宽，这个算法同时也会尽可能把数据合并到最小的分组中。只要算法发现了相匹配的标记符，它就将这些数据放到同一个数据包里，例如 A1 和 A2 变成了 A3。它持续这样做，根据匹配的标记符创建越来越小的数据包，直到产生可能范围内最小的数据包来进行排序。这大大减少了访问重复请求的数量。

使用这个算法来处理两个大图形，研究人员把需要在闪存中更新的总数据减少了大约 90%。

计算分流

然而，由于“分类-减少”算法需要在主机上进行高强度计算，于是研究者们在设备里放入了一个定制的加速器。作为主机和闪存芯片的中间点，加速器为算法执行所有运算。于是，很大一部分能耗被分流到了加速器上，主机因而可以成为一台低功耗的个人电脑或笔记本，用于管理分类的数据和执行其它次要任务。

“本来加速器是用来帮助主机的，但我们不小心（在计算上）走得太远，以至于主机变得不重要了”Arvind 说。

图丨Arvind 教授

“麻省理工学院的这个项目展示了一种在非常大的图形上执行分析的新方法：他们利用闪存来储存图形，并且巧妙使用 FPGA 来执行有效使用闪存所需的分析和数据处理”，德克萨斯大学奥斯汀分校的计算机科学教授 Keshav Pingali 说，“长远看来，这可能促生一个能在笔记本或台式电脑上有效处理大量数据的系统，并将彻底改变我们进行大数据处理的方式。”

据传相佑介绍，由于主机耗能很少，他们的长期计划是创建一个通用平台和软件库，让消费者能开发出图形分析之外的、属于他们自己的算法。“你可以把这个平台插到笔记本里，下载软件，并编写简单的程序，从而在自己的电脑上实现服务器级别的性能”，他说。