在数据科学的说法中，图（graph）是指用于映射大量复杂的数据关系的节点（nodes）和连接线（connecting lines）的结构。分析graph在许多应用中非常有用，例如网页排名、分析社交网络以获取政治见解，或者绘制大脑的神经元结构。
然而，由数十亿个节点和线组成的大型 graphs 大小可以达到TB级。通常来说，图数据的处理需要跨多个耗电量大的服务器，在昂贵的动态随机存取存储器（DRAM）中进行。
最近，麻省理工学院计算机科学与人工智能实验室（CSAIL）的研究人员设计出一种设备，使用廉价的闪存（智能手机中使用的那种），仅使用一台个人电脑就能处理大量的图形。
该设备包含一个闪存芯片阵列（图中黑色的8个芯片）和一个计算“加速器”（芯片阵列左边）。研究人员提出一种新算法，将图形数据的所有访问请求排序为闪存可以轻松访问的顺序，同时合并一些请求以减少排序开销。
闪存芯片阵列+计算加速器，在个人电脑达到服务器级性能
在处理图数据时，闪存通常比DRAM慢得多。但研究人员开发出一种由闪存芯片阵列和计算“加速器”组成的设备，可以使闪存达到类似于DRAM的性能。
驱动该设备的是一种新的算法，它可以将图数据的所有访问请求排序为闪存可以快速、轻松访问的顺序。它还将一些请求合并，以减少排序的开销——组合计算时间、内存、带宽和其他计算资源。
研究人员使用该设备与几个传统的高性能系统一起处理几个大型图，包括庞大的Web Data Commons Hyperlink Graph，该Graph有35亿个节点和1280亿个连接线。为了处理这个Graph，传统的系统需要耗资数千美元的服务器，以及128GB的DRAM。研究人员将两台新设备（总计1GB的DRAM和1TB的闪存）接入台式电脑，获得了同样的性能。此外，通过合并几个设备，可以处理更大的图——多达40亿个节点和1280亿个连接线——而其他系统无法在128G的服务器上处理这些图。
研究人员将两台设备（总计1GB的DRAM和1TB的闪存）接入一台台式电脑，获得了与数千美元的传统服务器同样的性能。
CSAIL的研究生、论文第一作者Sang-Woo Jun说：“最重要的是，我们可以用更小功耗、更少、温度更低的设备保持一样的性能。”该研究发表在今年的国际计算机体系结构研讨会（ISCA）上。
该设备可以用于降低与图形分析相关的成本和能耗，甚至可以在许多应用中提高性能。例如，研究人员目前正在开发一个程序，可以识别导致癌症的基因。谷歌等大型科技公司也可以利用这些设备，通过使用更少的机器来运行分析，以减少能源消耗。
“图形处理（graph processing）是一个很普遍的想法，”该研究的合作者、计算机科学工程系教授Arvind说，“网页排名和基因检测有什么共同之处呢？对我们来说，它们是相同的计算问题，只不过不同的graph表达的含义不同。”
论文合著者还有CSAIL的两名研究生Shuotao Xu和Andy Wright，以及电子工程与计算机科学系的Sizhuo Zhang。
sort-reduce算法
在图分析中，系统根据节点与其他节点的连接以及其他度量指标来搜索和更新节点的值。例如，在网页排名中，每个节点代表一个网页。如果节点A具有较高的值并连接到节点B，那么节点B的值也会增加。
传统的系统将所有图数据存储在DRAM中，这使得它们在处理数据时速度很快，但也导致成本昂贵而且耗电。有些系统将部分数据存储卸载到闪存上，这种方式更便宜，但速度更慢，效率更低，因此仍需要大量的DRAM。
CSAIL研发的新设备运行在被称为“sort-reduce”的算法上，该算法解决了使用闪存作为主要存储源的一个主要问题：浪费。
图分析系统需要通过大量的、稀疏的图结构访问彼此间距离很远的节点。系统通常请求直接访问4到8字节的数据，以更新节点的值。DRAM提供了非常快速的直接访问。然而，闪存只能访问4KB到8KB的数据块，但仍然只更新几个字节。在跳过图形时，重复访问每个请求会浪费带宽。
sort-reduce算法转而采用所有的直接访问请求，并按照标识符的顺序对它们进行排序，标识符显示请求的目的地——例如将节点A的所有更新分成一组，全部分配给节点B。这样，闪存就可以同时访问数千个kilobyte大小的chunks的请求，从而大大提高效率。
为了进一步节省计算力和带宽，该算法同时将数据合并到尽可能最小的分组中。只要算法记录了匹配的标识符，它就将这些数据加载到一个数据包中——例如将A1和A2合并成A3。这种做法重复多遍，用匹配的标识符创建越来越小的数据包，直到产生可进行排序的最小数据包。这大大减少了访问重复请求的数量。
研究人员在两个大型graphs上使用 sort-reduce 算法，将需要在闪存中更新的全部数据减少了大约90%。
定制加速器
然而，对于主机来说， sort-reduce算法的计算量很大。因此，研究人员在设备中添加一个定制加速器。加速器在主机和闪存芯片之间充当中间点，执行算法的所有计算。这为加速器大大减少了电量消耗，以至于可以用一个低功耗的PC或笔记本电脑作为主机，用来管理已排序的数据并执行其他次要任务。
Arvind说：“加速器本来是用来帮助主机进行计算的，但是目前的结果显示，主机变得不那么重要了。”
“MIT的这个工作展示了一种在非常大的图上执行分析的新方法：利用闪存存储图形，并利用FPGA（定制的集成电路）以巧妙的办法执行所需的数据处理和分析，“德克萨斯大学奥斯汀分校计算机科学教授Keshav Pingali说，“从长远来看，这可能使得系统能够在笔记本电脑或台式机上有效地处理大量数据，这将彻底改变我们处理大数据的方式。”
MIT的研究人员说，由于主机的耗能很低，他们的长期目标是创建一个通用的平台和软件库，以便用户为图分析之外的应用开发自己的算法。Jun说：“你可以把这个平台插入笔记本电脑，下载这个软件，然后编写简单的程序，就可以在你的笔记本电脑上获得服务器级的性能。”
原文发布时间为：2018-06-4
本文作者：刘小芹
本文来自云栖社区合作伙伴新智元，了解相关信息可以关注“AI_era”。
