设备允许个人计算机处理大图

在数据科学的说法中，图形是节点和连接线的结构，用于映射复杂数据关系的分数。分析图表对于广泛的应用程序非常有用，例如对网页进行排名，分析社交网络以获取政治见解，或绘制大脑中的神经元结构。

然而，由数十亿个节点和线组成，大图可以达到太字节的大小。的图形数据在跨多个耗电服务器昂贵的动态随机存取存储器(DRAM)通常处理。

麻省理工学院计算机科学与人工智能实验室(CSAIL)的研究人员现在设计了一种设备，该设备使用廉价的闪存存储 - 智能手机中使用的类型 - 仅使用一台个人计算机处理大量图形。

在处理图形数据时，闪存通常比DRAM慢得多。但研究人员开发出一种由闪存芯片阵列和计算“加速器”组成的设备，可帮助闪存实现类似DRAM的性能。

为设备供电是一种新颖的算法，可以将图形数据的所有访问请求按顺序排序，闪存可以快速轻松地访问。它还合并了一些请求以减少开销 - 组合计算时间，内存，带宽和其他计算资源的排序。

研究人员针对几个处理几个大型图形的传统高性能系统运行该设备，其中包括大量的Web Data Commons Hyperlink Graph，它有35亿个节点和1280亿个连接线。为了处理该图，传统系统都需要一台价值数千美元且包含128千兆字节DRAM的服务器。研究人员通过将两台设备(总计1千兆字节的DRAM和1兆字节的闪存)插入台式计算机，实现了相同的性能。此外，通过组合多个设备，他们可以处理大量图形 - 高达40亿个节点和1280亿个连接线 - 这是其他系统无法在128千兆字节服务器上处理的。

“最重要的是，我们可以在更低，更少，更冷的情况下保持性能，如温度和功耗 - 机器，”CSAIL研究生Sang-Woo Jun和描述该设备的论文的第一作者Sang-Woo Jun说。正在国际计算机体系结构研讨会(ISCA)上发表。

该设备可用于降低与图形分析相关的成本和能源，甚至可以在广泛的应用中提高性能。例如，研究人员目前正在创建一个可以识别导致癌症的基因的程序。谷歌等大型科技公司也可以通过使用更少的机器来运行分析来利用这些设备来减少能源占用。

“图形处理是一个普遍的想法，”共同作者，计算机科学工程的约翰逊教授Arvind说。“页面排名与基因检测有什么共同之处?对于我们来说，它是相同的计算问题 - 只是具有不同含义的不同图表。某人开发的应用程序类型将决定它对社会的影响。”

论文的共同作者是CSAIL研究生Shuotao Xu，Andy Wright和Sizhuo Zhang，CSAIL的两名研究生和电气工程与计算机科学系。

在图形分析中，系统将基本上根据与其他节点的连接以及其他度量来搜索和更新节点的值。例如，在网页排名中，每个节点代表一个网页。如果节点A具有高值并连接到节点B，则节点B的值也将增加。

传统系统将所有图形数据存储在DRAM中，这使得它们能够快速处理数据，但也昂贵且耗电。一些系统将一些数据存储卸载到闪存，这更便宜但速度更慢且效率更低，因此它们仍然需要大量的DRAM。

研究人员的设备依赖于研究人员所称的“排序 - 减少”算法，该算法解决了使用闪存作为主要存储源的一个主要问题：浪费。

图形分析系统需要访问跨越庞大，稀疏图形结构的彼此相距很远的节点。系统通常要求直接访问例如4到8个字节的数据以更新节点的值。DRAM提供了非常快速的直接访问。但是，Flash只访问4到8千字节块的数据，但仍然只更新几个字节。跳过图表时重复对每个请求的访问会浪费带宽。“如果你需要访问整个8千字节，并且只使用8个字节然后扔掉其余部分，你最终会丢掉1000倍的性能，”Jun说。

sort-reduce算法改为采用所有直接访问请求，并按标识符顺序对它们进行排序，标识符显示请求的目的地 - 例如将节点A的所有更新，节点B的所有更新等组合在一起，依此类推。然后，Flash可以同时访问数千个请求的千字节大小的块，从而提高效率。

为了进一步节省计算能力和带宽，该算法同时将数据合并到可能的最小分组中。每当算法记录匹配标识符时，它将它们加到单个数据包中 - 例如A1和A2变为A3。它继续这样做，创建越来越小的具有匹配标识符的数据包，直到它产生最小的可能数据包进行排序。这大大减少了重复的访问请求数量。

在两个大图上使用sort-reduce算法，研究人员将需要在闪存中更新的总数据减少了大约90%。

卸载计算

然而，sort-reduce算法对于主机来说是计算密集型的，因此研究人员在设备中实现了自定义加速器。加速器充当主机和闪存芯片之间的中间点，执行算法的所有计算。这会给加速器带来如此大的功率，主机可以是低功率PC或笔记本电脑，管理分类数据并执行其他小任务。

“加速器应该可以帮助主机计算，但是我们已经[计算]到目前为止主机变得不重要了，”Arvind说。

“麻省理工学院的工作展示了一种在非常大的图形上执行分析的新方法：他们的工作利用闪存存储图形并利用”现场可编程门阵列“[定制集成电路]以巧妙的方式执行分析和有效使用闪存所需的数据处理，“得克萨斯大学奥斯汀分校计算机科学教授Keshav Pingali说。“从长远来看，这可能会导致系统能够在笔记本电脑或台式机上高效处理大量数据，这将彻底改变我们进行大数据处理的方式。”

Jun表示，由于主机功能如此低，Jun的长期目标是为消费者创建一个通用平台和软件库，为超出图形分析的应用开发自己的算法。“你可以将这个平台插入笔记本电脑，下载[软件]，并编写简单的程序，以便在笔记本电脑上获得服务器级性能，”他说。