学界 | 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 条评论
登录 后参与评论

相关文章

来自专栏Crossin的编程教室

【Python 第39课】 用文件保存游戏(1)

到目前为止,python最入门的语法我们都已经有所涉及,相信大家一路学过来,多少也能写出一些小程序。在接下来的课程中,我会基于实例来更深入地介绍python。 ...

2995
来自专栏数据科学与人工智能

【Python环境】为什么要选择Python语言实现机器学习算法?

基于以下三个原因,我们选择Python作为实现机器学习算法的编程语言:(1) Python的语法清晰;(2) 易于操作纯文本文件;(3) 使用广泛,存在大量的开...

1878
来自专栏企鹅号快讯

程序员的花样编程,你到底行不行?

【导读】:说到 C/C++ 代码技巧,也许会有童鞋说 ,这是属于 C/C++ 程序员离职前恶搞之类的抖机灵。即便想,也不能干。别忘了有这样一句编程名言:「在编写...

1965
来自专栏机器之心

资源 | OpenAI开源机器人模拟Python库mujoco-py:可高效处理并行模拟

选自OpenAI 机器之心编译 参与:黄小天 OpenAI 宣布开源一个高性能的 Python 库,它可用于使用 MuJoCo 引擎(在上年的机器人研究中开发出...

3104
来自专栏数据小魔方

excel数据分析库系列|抽样设计

今天开始跟大家分享excel数据分析库系列——抽样设计! 作为微软excel中一直以来隐藏的最深最上档次的功能组件,excel数据分析工具库需要用户手动调用并开...

3157
来自专栏机器人网

基于嵌入式Linux的移动机器人控制系统

随着科学技术的发展和社会的需要,移动机器人技术得到了迅速发展,正在渗透到各行各业中,使人们的生活更加便利。现今以单片机为核心的移动机器人存在处理数据量有限、控制...

3135
来自专栏机器之心

腾讯Angel 1.0正式版发布:基于Java与Scala的机器学习高性能计算平台

机器之心报道 Tencent 深度学习是近些年来人工智能技术发展的核心,伴随而来的机器学习框架平台也层出不穷。到现在,一家科技巨头没有一个主导的机器学习平台都不...

2805
来自专栏瓜大三哥

matlab GUI基础5

高级文件I/O——图像和视频文件 函数说明imread说明图像文件imwrite写入图像文件imfinfo获取图像文件的信息imshow显示图像imformat...

2347
来自专栏ACM算法日常

PAT-CCCC练习:L2-001.紧急救援

作为一个城市的应急救援队伍的负责人,你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速...

441
来自专栏Linuxer的专栏

宋宝华:火焰图 全局视野的 Linux 性能剖析

火焰图的火焰首先来自于根,然后以火苗的形式往上面窜。可以把从靠近地面的根到顶上的每个火苗,想想成一个调用栈。由于火苗有很多根,这正好也和现实生活中程序的执行逻辑...

1190

扫描关注云+社区