学界 | MIT CSAIL提出并行计算系统Fractal,能实现88倍加速

AI科技评论按:MIT News最新报道,MIT CSAIL(麻省理工学院计算机科学与人工智能实验室)已经开发出了一个新系统Fractal,这个系统不仅能使并行程序运行起来更有效率,也使得编码更加容易。

现在,大多数台式电脑的芯片都会配置四核或者更多核的CPU,这种配置能保证计算机可以并行运行不同的计算任务。在未来,芯片里可能会有几十个甚至数百个核,如何利用并行性是一个艰巨的挑战。

MIT CSAIL 的研究人员已经开发出了一种新系统,这个系统不仅能使并行程序提升运行效率,也使编码更加简单。

以一组基准算法测试作为标准时,当采用相同的并行策略,在大多数情况下,这个新系统比目前系统的速度快十多倍,最大能达到目前系统的88倍。

将最大流问题的算法进行并行处理是非常困难的。经过几十年的研究,在256个并行处理器上,常见的最大流算法的并行计算最快也只能实现8倍的加速。而有了这个新系统,将能实现322倍的加速,并且代码长度是之前代码的三分之一。

这个新系统被称为“Fractal”,它是通过一个叫做预测执行(speculative execution)的并行策略来实现加速的。

“在传统的并行程序中,你需要将你的工作分成多个任务,” Daniel Sanchez表示。他是麻省理工学院电气工程和计算机科学助理教授,另外也是这篇新论文(Fractal: An Execution Model for Fine-Grain Nested Speculative Parallelism)的资深作者。“但因为这些任务是使用共享数据,所以需要引入一些同步机制来保证数据具有相关性。从90年代中期到2000年代末,许多人对投机架构(speculative architectures)进行了一波又一波的研究。这些研究系统能并行执行不同的数据块,一旦发现冲突,就会中止程序再重新执行。”"

在计算完成之前频繁中止程序并不是一个很有效的并行化策略。不过对于许多应用程序,中止计算的情况并不常见,这比在传统并行方案的同步任务中所需的检查和更新浪费的时间少得多。去年, Sanchez的小组报导了一个称为 Swarm 的系统,这个系统将投机并行扩展成一类重要的计算问题,涉及搜索数据结构,例如对图表的搜索。

不能简化的原子

然而,对投机架构的研究往往局限于原子性(atomicity)问题上。正如所有并行架构,投机架构要求程序员把程序分成多个任务,这样就能同时运行。但是在投机架构中,每个任务都是“原子级的(atomic)”,这意味着它必须作为整体来执行。通常,每个原子任务都有一个独立的处理单元,这样能更有效地独立运行。

原子级的任务通常有很多步骤。举个例子,在线预订机票的任务包含很多步,这些步骤都必须被看作不同的原子单元。如果要将两个任务当作同一个原子单元,那么这两个任务就无法被执行。例如,在这样的程序下,仅仅只是因为第一位顾客还没有完成支付,有可能座位就被分配给了另一位预订的顾客。

  • 在投机执行中,大的原子级任务有两个地方效率比较低下。
  • 第一是如果想中止任务,得花费大量的计算时间。中止小一点的任务花费的时间相对会少一点。
  • 第二是大的原子级任务内部可能会有能并行运行的子程序,但是由于这些任务是在特定的处理单元独立运行,因此这些子程序只能被连续执行。这样一来,性能就得不到提升。

Fractal是由Sanchez与麻省理工学院的研究生Suvinay Subramanian、Mark Jeffrey、Maleen Abeydeera、Hyun Ryong Lee、Victor A. Ying,以及英伟达杰出的高级研究科学家Joel Emer共同研发的,这一系统解决了如上提到的两个问题。这些研究人员在这周的ISCA上向麻省理工学院电气工程和计算机科学部详述了它的原理。

有了Fractal,程序员在原子任务里只需在每个子程序里添加一行代码,就可以实现并行执行。程序的长度也只增加若干百分点。在以前,如果需要实现同步并行任务,程序长度得增加300—400个百分点。将电路嵌入分形芯片,就可以进行并行化处理了。

时间链

这个系统的关键是对电路的细微改进,这种改进在这些研究员的早期投机执行系统 Swarm 中已经实现了。

在Swarm中执行的每个任务都会分配一个时间戳,如果两个任务尝试访问相同的存储单元,时间戳晚一点的那个任务将会被中止,然后重新执行。

Fractal中的每个原子任务也会分配自己的时间戳。但如果原子任务里有并行子程序,子程序的时间戳里会包含这个任务的时间戳。另外,如果子程序里还有并行的子程序,那么后面那个子程序的时间戳里包含前面子程序的时间戳,以此类推。通过这种方式,子程序的排序里都包含原子任务的排序。

当一个任务里包含子程序,子程序里又不断包含其他子程序,这对于存储他们的专用电路来说,子程序里串联的时间戳太长了。在这种情况下,Fractal只存储时间戳序列的最前列。这意味着Fractal只执行定义好的最低级别、最细粒化的任务,这样能避免中止大的、高级别的原子任务。

论文地址:http://people.csail.mit.edu/sanchez/papers/2017.fractal.isca.pdf

via MIT News,AI 科技评论编译

原文发布于微信公众号 - AI科技评论(aitechtalk)

原文发表时间:2017-07-04

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏大数据和云计算技术

有向图的环和有向无环图

本篇主要分享关于有向图的环和有向无环图(DAG,估计做大数据的同学到处都可以看到),所以相关概念我就不做详细介绍了。

1295
来自专栏Data Analysis & Viz

乱炖“简书交友”数据之代码

上一篇文章乱炖数据之2700余篇“简书交友”专题文章数据的花式玩法发布后,不少人想学习下代码,由于此前不曾在GitHub上开源过,流程还不熟悉,再者本项目中很多...

511
来自专栏张善友的专栏

C#数学计算包 Math.NET

Math.NET的目标是为提供一款自身包含清晰框架的符号运算和数学运算/科学运算,它是C#开发的开源类库。Math.NET含了一个支持线性代数的解析器,分析复杂...

2205
来自专栏PHP实战技术

ThinkPHP连续签到小案例

小伙伴们平时做网站开发的时候,是不是也遇到过会员连续签到送积分,比如我有一个加积分的规则是针对连续签到的,那么我们在实现这个功能的时候,我们面对...

41710
来自专栏PPV课数据科学社区

如何使用R语言解决可恶的脏数据

在数据分析过程中最头疼的应该是如何应付脏数据,脏数据的存在将会对后期的建模、挖掘等工作造成严重的错误,所以必须谨慎的处理那些脏数据。 脏数据的存在形式主要有如下...

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

用pandas 进行投资分析

让我们进行一个常见的分析,您可能自己就可以完成这个分析。假设您想分析股票绩效,那么您可以: 在 Yahoo 金融专区找一支股票。 下载历史数据,保存为 CSV ...

2695
来自专栏媒矿工厂

【视频编码】 Content Aware ABR技术(十一)

在本系列前面的帖子中,我们连续梳理了Netflix、YouTube、Beamr、EuclidIQ、Bitmovin、Harmonic、V-Nova、Cisco、...

1101
来自专栏aoho求索

由Consul谈到Raft

在前一篇文章consul配置与实战中,介绍了consul的一些内幕及consul配置相关,并对项目中的一些实际配置进行展示。这篇文章重点介绍consul中所涉及...

3568
来自专栏有趣的Python和你

玩转itchat,实现好友信息可视化、聊天机器人及性别模型构建

前些日子,女朋友拿我手机玩,说我微信好友女生多,当时我就不服了(跪着认错了),然后两人一个个统计性别,我微信好友不算多,但也有300来个,人工统计实在费事,之后...

981
来自专栏PPV课数据科学社区

技术丨从Hadoop到Spark,看大数据框架发展之路

谈到大数据框架,不得不提Hadoop和 Spark,今天我们进行历史溯源,帮助大家了解Hadoop和Spark的过去,感应未来。 在Hadoop出现前人们采用什...

2749

扫码关注云+社区