近日CSAIL发布了一个可加速一般并行化计算的系统 Fractal，该系统在相同并行化策略中要比传统方法快10倍左右，特定的能达到88倍的加速。
新系统 Fractal 通过推测性执行并行化策略实现88倍的加速。
如今大多数台式电脑的芯片都有 4 个「核心」或处理单元，它们可以并行地处理不同的计算任务。但未来的芯片可能有数十个或上百个物理核心，因此利用所有的并行资源将变得十分困难。
MIT 计算机科学和人工智能实验室（CSAIL）的研究员最近开发出一种新型系统，它不仅可以让并行化程序更高效地运行，同时还可以令编程更加简单。
在一组基准算法测试中，研究者的新系统平均在采用相同并行策略时比现有系统实现的加速达到了 10 倍，并且最高加速比达到了 88 倍。我们知道可以解决非常重要问题的最大流算法（max-flow algorithm）已经被证明很难并行化。即使经过数十年的研究，普通最大流算法的最优并行化实现在 256 个并行处理单元中仍然只能达到 8 倍的加速。而采用研究者的新系统，加速达到了 322 倍，并且只需要三分之一的代码就可以实现。
新系统 Fractal 通过推测执行（speculative execution）并行策略实现加速。MIT 电气工程与计算机科学助理教授，新论文的资深作者 Daniel Sanchez 表示：「在传统并行程序中，我们需要将整个工作分割为几个任务。但因为这些任务是在共享数据的情况下操作的，我们需要额外引入一些同步来确保这些任务的数据相关性能得到体现。过去我们研究过几波推测性架构（speculative architectures），这些系统会平行地处理不同的块，并且如果它们检测到计算冲突，那么就会中止并重新计算。」
在完成计算前频繁地中断计算并不会是一个比较有效的并行化策略。但是对于大多数应用来说，中断计算是很少见的，因此它比常规并行方案中同步任务所需要的复杂检查和更新时间更短。去年，Sanchez 团队报告了一个称之为 Swarm 的系统，该系统将推测执行并行化推广到一系列重要的计算问题中，并涉及到搜索图形数据结构。
然而，推测性架构的研究往往依赖于「原子性」问题。如同所有的并行化架构，推测性架构要求开发者将程序分割为任务，然后才能同时运行。但是在推测性架构中，每一个任务都是一个「原子」，意味着其可能可以作为一个整体而执行。通常，每一个原子型任务可以分配到单独的处理单元，并能有效的运行。
原子型任务通常是相当实质的。如在线预订飞机票，其中每一个独立的操作都可以看作一个原子型单元。因此程序也不会因为客户没有付款而将该座位提供给另一位乘客。
通过推测执行（speculative execution），大型原子型任务（atomic tasks）引入了两个低效机制。第一个是如果任务必须中止，那么它可能会在执行完大量计算循环后再进行中止。因此中止较小任务是浪费的时间也越小。
另外一个就是一个大型原子型任务可能是拥有内部子例程（subroutines）的，它可以进行有效地并行化。但是由于任务和它自己的处理单元是分离的，那些子例程必须被连续地执行，这就浪费了性能提升的机会。
分形体（Fractal）——这是 Sanchez 和麻省理工的研究生 Suvinay Subramanian，Mark Jeffrey，Maleen Abeydeera，Hyun Ryong Lee 和 Victor A. Ying，还有 Joel Emer——元件制造商英伟达的研究科学家，共同进行研发以解决上述两个问题的系统。这些来自麻省理工电气工程与计算机科学系的研究人员，在一篇论文中描述了此系统，他们也在这周进行的 International Symposium on Computer Architecture（计算机体系结构国际学术研讨会）上介绍了此内容。
通过利用分形体（Fractal），一个程序员可以在一个原子型任务中为每一个子例程添加一行代码，从而可以被并行执行。这将会使一个程序的序列版本的长度增加几个百分点。然而如果直接对并行任务进行同步处理，通常会增加 300 到 400 个百分点。将回路直接和分形体元件进行硬连线就可以处理并行任务。
时间链
本系统的关键是对 Swarm 内的回路——也就是研究者们先前的推测执行系统，做出了略微改变。Swarm 的设计是为了在并行程序中强制执行一些连续指令的概念。每一个在 Swarm 中被执行的任务都会收到一个时间标记，如果两个任务试图获取相同的存储单元，那么获得时间标记较晚的那一个会被中止并且重新执行。
分形体（Fractal），是为了给每一个原子型任务分配其独有的时间标记。但是如果一个原子型任务有一个可并行的子例程（subroutine），这个子例程的时间标记也会包括产生此子例程的母任务。而且如果接下来，此子例程也有一个可并行的子例程，那么第二个子例程的时间标记也会涵盖第一个子例程，以此类推。用这个办法，子例程的次序会对原子任务的次序进行保存。
由于任务会产生子例程，子例程又会产生子例程，对用来存储它们的专用回路来说，被连接起来的时间标记会变得很长。然而，在那种情况下，分形体（Fractal）只是简单地把时间标记列的前端移动到存储器当中。这意味着分形体（Fractal）总是在最低等级下进行工作，最底层的任务已经被认证，这就避免了大型和高等级原子型任务的中止问题。
原文链接：https://phys.org/news/2017-07-greatly-common-parallel-computing-algorithms.html
