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

现在大部分台式机都有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 编辑发布。Larry Hardesty

赞一个 (6)