@ 2017.07.26 , 17:00
16

新系统大大加速一般并行计算方法

现在大部分台式机都有4核,可以并行处理不同计算任务。但未来的芯片可以有数十核乃至数百核,要利用所有这些核进行并行计算较为困难。

来自麻省理工学院计算机科学与人工智能实验室的研究者提出了一个新系统,不仅使并行程序的效率大大提升,并且也使得更容易实现并行编程。

新系统大大加速一般并行计算方法
credit: 自己仿照原图画的

在该领域的标准检查程序集测试中,研究者的新系统相比采用相同并行策略的现有系统,速度提升了10倍,最大提升88倍。

例如,解决最大流问题的算法已被证实非常难以并行化。经过数十年的研究,一个常见最大流算法的最好并行实现也只能在256个并行处理器上实现8倍加速。而利用研究者的新系统,可实现322倍加速,并且只需要3分之1的代码量。

这一新系统被称为Fractal,基于推测执行这一并行策略实现加速。

MIT电子工程与计算科学助理教授、新论文资深作者Daniel Sanchez说道:“在传统的并行程序中,你需要将工作分解为多个任务。但由于这些任务在共享数据上进行操作,因此需要引入某些同步机制来确保慎重处理这些任务之间的数据依赖性。从1990年代中期到2000年代末,出现了几波关于推测结构的研究热潮。这类系统所做的就是并行执行这些不同的块,如果检测到冲突,就取消并回滚其中某一个。”

在完成之前不断取消计算并非一个很有效的并行策略。但对于很多应用而言,可能会很少取消计算,以至于相比更为传统的并行算法中同步任务所需的复杂检查和更新花费的时间更少。去年,Sanchez的小组提出了一个名为Swarm的系统,将推测并行计算扩展到一类重要的计算问题,涉及图这种搜索数据结构。

不可分的原子

但关于推测架构的研究往往止步于“原子性”问题。正如所有的并行架构那样,推测架构要求程序员将程序划分为多个能同时运行的任务。但在推测架构中,每个这种任务被称为“原子”,意味着似乎应当作为单个整体执行。典型的,每个原子任务被分配给单独处理单元。

原子任务一般相当多。例如网上订一张飞机票,就由多个分离的操作组成,但必须被当成一个原子单元处理。否则就有可能出现程序将一个座位提供给一名顾客然后又提供给了另一个顾客,因为第一名顾客还没有完成支付。

在推测执行中,大型原子任务会引起两方面的低效。第一个是如果必须取消任务,可能必须经过大量计算循环后才行。取消小一点的任务可以花更少的时间。

另一个方面是一个大型原子任务可能包含可以有效并行的内部子程序。但由于这一任务被自身的处理单元所孤立,这些子程序就必须串行运行,浪费了性能改进的机会。

Sanchez 与MIT研究生Suvinay Subramanian、Mark Jeffrey、Maleen Abeydeera、Hyun Ryong Lee、Victor A. Ying以及芯片制造商英伟达的资深杰出研究科学家Joel Emer教授一起研发了Fractal,解决了上述所有问题。该研究已在计算架构国际研讨会(ISCA)上作了报告。

利用Fractal,程序员就能在原子任务的每个子程序中增加一行代码,使这些子程序可以被并行执行。这一般会少许增加程序串行实现的长度,而同步并行任务的实现则会使程序长度增大到3到4倍。Fractal芯片上的电路则处理了这个并行化问题。

时间链

系统的关键是在研究者早先提出的名为Swarm的推测执行系统的电路基础上进行了稍微修改。Swarm被设计来并行执行某些顺序的概念。Swarm中执行的每个任务都会打上一个时间戳,如果两个任务试图访问同一个存储位置,时间戳较晚的那个就会被取消并重新执行。

Fractal也给每个原子任务分配自身的时间戳。但如果原子任务中还有可并行的子程序,子程序的时间戳就包含所在任务的时间戳。另外如果这个子程序还包含可并行的子程序,第二级子程序的时间戳就包含第一级子程序的时间戳,以此类推。按照这种方式,子程序的顺序就保留了原子任务的顺序。

由于任务会不断向下级衍生子程序,串联的时间戳就可能变得特别长以致于特殊设计的存储电路都无法处理。但在这种情况下,Fractal就简单地将时间戳火车的前部移到存储中。这就意味着Fractal总是工作在其已经鉴定的最低一级、最细化的任务,避免了取消大型、高层原子任务的问题。

论文原文:Fractal: An Execution Model for Fine-Grain Nested Speculative Parallelism

本文译自 phys,由译者 CliffBao 基于创作共用协议(BY-NC)发布。Larry Hardesty


给这篇稿打赏,让译者更有动力
支付宝打赏 [x]
您的大名: 打赏金额:

4.4
赞一个 (5)

TOTAL COMMENTS: 16+1

  1. 马赛克
    @4 weeks ago
    3518443

    难事就交给专家去搞

  2. 怪事
    @4 weeks ago
    3518448

    这个字我会我会!

    [11] XX [0] 回复 [0]
  3. 3518459

    以时间戳来确定并行任务的数据前后顺序

    么?

  4. cesium
    @4 weeks ago
    3518469

    并且也使得更容易进行并行程序编程
    速度提升了10倍,最大提升88倍
    取消计算出现的次数可能会很少,以至于相比更为传统的并行算法中同步任务所需的复杂检查和更新花费的时间更少
    每个这种任务被称为“原子”,意味着似乎应当作为单个整体执行
    Swarm被设计来以并行程序执行某些顺序的概念

    我觉得译者如果不会说中文的话不必勉强

    [21] XX [15] 回复 [0]
  5. dullgull
    @4 weeks ago
    3518479

    煎蛋还有ISCA 的论文。。长见识了。

    [10] XX [0] 回复 [0]
  6. 3518480

    每年都有新研究,每年都不会商业化生产,已经没兴趣了

  7. 3518487

    怎么了要取消分时系统?

  8. 萌豕
    @4 weeks ago
    3518514

    每个字都认……啊不,甚至有的字都不认识_(:3 」∠)_

  9. 3518518

    Rick and Morty

  10. lbSeevdo
    @4 weeks ago
    3518524

    谢谢小编带来的科普文章,不过相对纯文字,我觉得煎蛋小学堂这种视频科普大家更喜欢,小编可以试试和制作视频的小编制作小学堂。作为小学堂的脑残粉,表示已经好久没看到新的小学堂了/(ㄒoㄒ)/~~

  11. 3518573

    这个不算科普吧,就是一个编程问题,可能因为翻译的原因有些难看懂,其实就是我们的CPU上都是有多个线程同时在跑的,如果多个线程想同时操作同一个地址的内存数据时就需要排队,不然就会互相把数据改乱,产生不可预测的结果,但排队的话就会浪费时间降低性能。所以我们的操作系统和编程语言做了很多排队机制,编程上叫做锁,锁住一片内存区域。上面这篇论文提高性能好像是把锁由软件层面实现替换成硬件层面去实现,就这样。

    [20] XX [0] 回复 [0]
  12. 3518579

    人类距离大规模灭绝又进一步啦~可喜可贺

  13. 大坝
    @4 weeks ago
    3518613

    具体实现方法将会给所有分布式系统包括分布式数据库以巨大启发,说是IT革命也不为过

  14. 3518689

    真正对这个新系统运行机制感兴趣的人,大部分都懂英文原文

  15. 大鼻子
    @4 weeks ago
    3518729

    就是把原子任务里面的质子任务再进行并行化优化,更加提前检测冲突节省回滚时间,执行更深层的并行也是加速的一大因素。

  16. Butters
    @3 weeks ago
    3522195

    啥??啥啥啥???

发表评论


24H最赞