动态规划是一种能够有效解决经济学、基因分析等领域计算问题的编程技术。但它不仅要求对应的计算机有多个内核或者多个运算单元，而且要求使用者具备一定的编程经验，这一点，一些经济学家和生物学家并不具备。

　　但好消息是，经济学家和生物学家所要面对的编程难题已经有了新的解决方案。来自麻省理工学院（MIT）计算机和人工智能（CSAIL）实验室的研究者以及石溪大学的学者致力于通过一种新系统来解决上述编程问题。

　　

　　这种新系统允许用户用一种更简单的方式去描述他们想要开发的程序，然后，该系统可以自动生成在多核芯片上运行的优化程序版本。另外，它还可以保证新版本程序和单核版本的结果相同，并且更快。

　　在实验中，研究者使用这个系统“并行”执行几个动态规划算法程序，把它们划分到可以在多核芯片上执行。结果表明，其处理速度是早期自动并行执行技术的3～11倍，几乎和计算机科学家人工并行优化的结果一样优越。

　　最近，在题为“系统、编程、语言和应用：软件的人性化”的计算机协会会议上，研究者们展示了他们的新系统。在一些实际问题当中，该系统为动态规划提供了指数级速度提升。因为它储存并且重用了一些计算结果，而不需要重新计算这些结果。“但是，它需要更多内存空间，因为你需要存储这些用于计算的结果”，这篇新论文的第一作者Shachar Itzhaky说，“当你运用它时，你会意识到它并没有达到你理想的速度提升，因为回调存储结果是缓慢的。当然，它仍然比重新计算快。”

　　为了避免以上问题，计算机科学家将对计算结果重新排序，使其以一个特定的顺序执行，减少从内存中回调这个值的次数。这种方法在单核计算机当中相对简单，但在多核计算机中，当多核共享这些计算结果时，内存管理就变得十分复杂了。一个人工优化的动态规划算法的并行版本通常可以达到单核版本的10倍效率。

　　CSAIL研究者的新系统——Bellmania（以动态规划编程的数学家Richard Bellman的名字命名）采用了名为分治递归的并行策略。假设这个并行算法的任务是计算一组矩阵的数目，那么它的第一步可能是将其分成4部分，分别进行计算；接着，它会继续将4个部分再分成4个部分，这就是递归调用的结果。

　　与Itzhaky 一同参与研究的还有来自Edwin Sibley Webster学院的两位电子与计算机科学教授Solar-Lezama，CharlesLeiserson；两位MIT电子与计算机科学研究生RohitSingh，Kuat Yessenov；一位参加MIT本科生研究项目的同学：YongquanLu；一位石溪大学的助教RezaulChowdhury，他曾是雷尔森研究小组的一员。

　　雷尔森研究小组专门研究分支并行技术；Solar-Lezama擅长程序合成和生产代码规范的程序。通过使用Bellmania系统，用户可以简单地描绘程序的第一步——矩阵的划分和运算结果的反复使用。接下来，Bellmania系统会决定如何继续划分问题以及利用运算结果。

　　在递归调用的每一级，Bellmania将产生一个程序去执行这个矩阵一部分任务，将剩余工作丢给并行执行的子程序。每个子程序会执行同样类似的过程，并将部分工作丢给进一步划分的子程序。

　　Bellmania系统决定了每层处理多少数据，子程序处理多少剩余数据。“这样做的目的是安排内存的访问顺序，以至于当你读完一个数据之后，以后不需要再次读取它。” Itzhaky称。

　　找到项目的最有效的划分方案，需要仔细研究各种可能的方案。Solar-Lezama的研究组已经开发了一套工具用于更高效地寻找最优方案。即便如此，Bellmania还是需要15分钟去并行化一个典型的动态规划算法。但这已经比程序员开发同样的项目要快很多了，因为手工开发的代码，总有些复杂的地方难免出错。

　　一位来自佐治亚理工学院的计算机科学教授说：“他们的工作实际上使许多应用的并行执行成为可能。因为他们提供了一个更简单的高级技术去简化某些项目的开发，使它们的系统自动解决如何划分工作并生成低层代码（其质量可与手写代码相媲美）。”另外，他还指出：“这些应用在现实世界中有无数的算法例子，包括：计算生物学、蛋白质组学、网络安全、排序、调度问题、网络流量管理等，这项研究意义非凡！”

　　编译：谢伟伦

　　参考：http://news.mit.edu/2016/faster-programs-easier-programming-multiprocessor-chips-1107

招聘

编辑、视觉设计、实习生（编译）

地点：北京

联系：hr@mittrchina.com

MIT Technology Review 中国唯一版权合作方，任何机构及个人未经许可，不得擅自转载及翻译。

分享至朋友圈才是义举