在数据科学中，图是用于映射复杂数据关系的分数的节点和连接线的结构。分析图对于广泛的应用是有用的，例如排序网页、分析社交网络以获得政治见解或者在大脑中绘制神经元结构。
然而，由数十亿个节点和线组成，大的图形可以在大小上达到TB。图形数据通常在多个功率饥饿的服务器上在昂贵的动态随机存取存储器(DRAM)中处理。
麻省理工学院计算机科学和人工智能实验室(CSAIL)的研究人员现在设计了一种设备，使用廉价的闪存--智能手机使用的那种--只使用一台个人计算机处理海量图形。
闪存在处理图形数据时通常比DRAM慢得多。但是研究人员开发了一种由闪存芯片阵列和计算"加速器，"组成的器件，可帮助闪存实现类似DRAM的性能。
驱动设备是一种新的算法，它将所有对图形数据的访问请求排序为一个顺序，闪存可以快速、方便地访问。它还合并了一些请求，以减少排序的开销--合并计算时间、内存、带宽和其他计算资源。
研究人员在运行该设备时，遇到了几个传统的高性能系统，这些系统处理几个大图，其中包括拥有35亿个节点和1280亿条连接线的海量Web数据共享超链接图。为了处理这个图表，传统的系统都需要一个服务器，花费数千美元，包含128 GB的DRAM。研究人员通过将两台设备--总计1G的DRAM和1TB的闪存--插入到一台台式计算机上，从而实现了同样的性能。此外，通过组合几个设备，他们可以处理高达40亿个节点和1280亿条连接线的海量图形，而在128 GB的服务器上，没有其他系统能够处理这些图形。
“底线是，我们可以用更小、更少、更冷的机器来保持性能--比如在温度和功耗方面--”CSAIL研究生、第一位作者Sang-Woo Jun在一篇描述该设备的论文中说。该论文正在国际计算机体系结构研讨会(ISCA)上发表。
该设备可以用于在广泛的应用中削减与图形分析相关的成本和能量，甚至提高性能。例如，研究人员目前正在创建一个能够识别致癌基因的程序。像谷歌这样的主要技术公司也可以利用这些设备来减少他们的能源足迹，使用少得多的机器来运行分析。
“图形处理是一个非常普遍的想法，”约翰逊计算机科学工程教授阿文德(Arvind)说。“页面排名与基因检测有什么共同之处？对我们来说，这是同一个计算问题--只是不同的图表，有着不同的含义。某个人开发的应用程序类型将决定它对社会的影响。”
论文共作者是Cavail研究生书陶徐及AndyWright和SiudiZhang，C帆的两名研究生和电气工程和计算机科学系。
排序和缩减
在图分析中，系统将基本上基于其与其他节点的连接来搜索和更新节点的值，其中包括其他度量。例如，在网页排名中，每个节点表示网页。如果节点A具有高的值并且连接到节点B，则节点B的值也将增加。
传统的系统将所有的图形数据存储在DRAM中，这使得它们在处理数据时快速，而且昂贵且耗电。一些系统将一些数据存储卸载到闪存，这更便宜，但较慢且效率较低，因此它们仍然需要大量的DRAM。
研究人员“设备”运行在研究人员称之为"排序-还原"算法的基础上，它解决了使用闪存作为主要存储源的一个主要问题：废物。
图形分析系统需要访问可能在大规模、稀疏图形结构上彼此非常远的节点。系统通常请求直接访问例如4到8字节的数据以更新节点的值。DRAM提供了非常快速的直接访问。但是，Flash仅在4-8KB的Chunks中访问数据，但仍只更新几个字节。在跨越图形浪费带宽的同时重复每个请求的访问。"如果您需要访问整个8千字节，并仅使用8个字节并丢弃剩余部分，则会放弃1,000倍的性能，"jun说。
排序-减少算法将所有直接访问请求按顺序顺序按标识符排序，这些标识符显示请求的目标，例如将节点A、节点B的所有更新组合在一起，等等。然后，Flash可以同时访问千兆字节大小的数千个请求块，使其效率大大提高。
为了进一步节省计算能力和带宽，该算法同时将数据合并成尽可能小的分组。每当算法记录到匹配的标识符时，它就会将这些标识符加到一个数据包中，例如A1和A2变成A3。它继续这样做，用匹配的标识符创建越来越小的数据包，直到产生最小的数据包来排序。这大大减少了要访问的重复请求的数量。
通过对两个大图的排序约简算法，研究人员将需要更新的总数据减少了约90%。
卸载计算
然而，排序减少算法对于主计算机来说是计算密集型的，因此研究人员在设备中实现了定制加速器。加速器用作主机和闪存芯片之间的中间点，执行算法的所有计算。这将向加速器提供如此多的功率，使得主机可以是管理经排序的数据并执行其它次要任务的低功率PC或膝上型计算机。
"加速器应该帮助主机计算，但我们已经到目前为止[计算]主机变得不重要，"Arvind说。
MIT的工作显示了一种在非常大的图形上执行分析的新方法：他们的工作利用闪存来存储图形并利用“现场可编程门阵列”[定制集成电路]来有效地执行使用闪存所需的分析和数据处理，”奥斯汀分校计算机科学教授KeshavPingali说。在长期运行中，这可能导致在笔记本电脑或台式机上有效处理大量数据的系统，这将彻底改变我们如何进行大数据处理。”
Jun说，因为主机可以如此低功率，所以一个长期的目标是为消费者创建通用的平台和软件库，以便为超出图形分析的应用程序开发自己的算法。"您可以将此平台插入到笔记本电脑中，下载[软件]，并编写简单的程序，在您的笔记本电脑上获得服务器级性能，"说。
进一步探讨