MIT CSAIL提出并行计算系统Fractal，能实现88倍加速

据外媒MIT News最新报道，MIT CSAIL（麻省理工学院计算机科学与人工智能实验室）已经开发出了一个新系统Fractal，这个系统不仅能使并行程序运行起来更有效率，也使得编码更加容易。雷锋网对这篇新闻进行了翻译，原文如下。

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

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://news.mit.edu/2017/speedup-parallel-computing-algorithms-0630

来源：雷锋网