MIT 开发廉价闪存设备,处理图数据性能堪比服务器


新智元编译

来源:MIT

编辑:刘小芹

【新智元导读】麻省理工学院计算机科学与人工智能实验室(CSAIL)的研究人员设计出一种设备,使用廉价的闪存,仅使用一台个人电脑就能处理大量的图形,达到与数千美元的传统服务器一致的性能。研究者认为,这将彻底改变我们处理大数据的方式。

在数据科学的说法中,图(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说:“你可以把这个平台插入笔记本电脑,下载这个软件,然后编写简单的程序,就可以在你的笔记本电脑上获得服务器级的性能。”

原文:http://news.mit.edu/2018/device-allows-personal-computer-process-huge-graphs-0531


原文发布于微信公众号 - 新智元(AI_era)

原文发表时间:2018-06-04

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小文博客

用C语言写贪吃蛇笔记-1

613
来自专栏Script Boy (CN-SIMO)

读《大道至简-- 第二章 是懒人造就了方法》 有感

      社会的进步、科学的发展,无不是靠这些“懒人”。       懒人造就了方法,这句话一点也没错。突然间想想那些聪明的人,大多都是懒人。因为想得多,所以...

1830
来自专栏AI科技大本营的专栏

CS 就业寒冬?这里有一份面试必备基础知识

作者 | 阿司匹林 2017 年国家统计局发布消息称,2016 年信息传输、软件和信息技术服务业的平均工资为 122478 元,首次打败金融业成为新霸主,是全...

3696
来自专栏C语言及其他语言

【图书】嗨翻C语言

内容介绍: 你能从这本书中学到什么? 你有没有想过可以轻松学习C语言?《嗨翻C语言》将会带给你一次这样的全新学习 体验。本书贯以有趣的故事情节、生动形象的图片...

2695
来自专栏FreeBuf

分析无线遥控器信号并制作Hack硬件进行攻击

*原创作者:ZMOM1031,本文属FreeBuf原创奖励计划,未经许可禁止转载 ? 无线遥控器(无线电遥控器)在我们生活中非常常见,应用于各种场景,方...

2218
来自专栏Albert陈凯

函数式编程很难,这正是你要学习它的原因

英文原文:Functional Programming Is Hard,That's Why It's Good   很奇怪不是,很少有人每天都使用函数...

2604
来自专栏Jerry的SAP技术分享

你的项目刚刚启动?是时候考虑Globalization了!

关于这个很长的定语的由来,请参考这篇文章,里面有王聪的背景介绍,包括他种菜的特长:当我用UI5诊断工具时我用些什么。

922
来自专栏编程

如何用SPSS分析问卷?用SPSS分析调查问卷数据的方法

问卷调查是一种针对目标对象群体的意见调查方式。是一种写好一连串的小问题,搜集被调查者的意见、反应、感受,和对事物的认知等等。当研究者想经过社会调查来探究一个现象...

2717
来自专栏大数据挖掘DT机器学习

Excel 有哪些可能需要熟练掌握而很多人不会的技能?

作者:何明科 链接:https://www.zhihu.com/question/21758700/answer/91385842 在咨询公司、VC/PE...

34110
来自专栏人人都是极客

计算机的基本组成

严格来讲计算机从诞生到现在经历了很多阶段,已经发展成为一种自动地、高速地、精确地进行信息处理的电子设备,也是20世纪的重大发明之一。

702

扫码关注云+社区