这是PLDI2007上的一篇文章：“Effective automatic parallelization of stencil computation”。
这篇文章就如题目所言，在介绍自动并行化的东西。
这篇文章所要解决的问题是，“规则的计算”。这类计算有着非常规则的模式，基本上就是使用一个多维的嵌套循环在一个多维的数组上进行迭代。这类计算在实际应用中很重要，普遍存在科学/工程计算和多媒体的处理中。而且，这种种嵌套循环很可能是一个程序的性能瓶颈。
在这篇文章中采用计算的多面体模型来刻画这种代码。多面体模型是一个很数学话的模型，针对完美循环嵌套。如果一个完美循环嵌套有n层，那么这个大循环的迭代空间就是n维空间中的一个点集。这个点集可以用一个多面体来刻画。
对这种循环并行化的关键是切片（Tiling），切片是通过指定一组或几组平行的超平面来进行的。这些超平面将迭代空间多面体划分成一系列小多面体。尽可能使得这些小多面体可以并行的执行。但是，这些小多面体之间可能存在着依赖关系，这些依赖可能会阻止并行执行。
文章提出一个新的概念，“并行开始”。其实就是指一系列的小多面体可以同时开始执行。
文中指出，如果原来的迭代空间（没有切片的）存在并行开始的可能性，那么进行文中的优化才能有利可图。Tiling并不能创造并行开始的可能性，相反，它可能引入新方向上的依赖而导致原本有可能并行开始的程序变成不能的。
文章中主要提出了两种新的Tiling的方法。一种是Overlapped Tiling，另外一种是Split Tiling。
前一种的主要思想是：通过冗余的计算，消除Tile之间的依赖关系，使得某个方向上的Tile可以并行开始。
第二中方法的思想是：将每个Tile分成两个小部分，一个部分不依赖于其它的Tile，另一个部分依赖于其它的Tile，首先，并行地执行所有Tile的前者，之后，并行地执行所有Tile的后者。在原文中有三个图示，根据它们，很容易理解这里说得思想。
这篇文章的理论性还是比较强的，它推导了好多公式。而事实上，它提出的Tiling方法则非常简单。那些复杂的公试主要是为了说明1、在什么情况下，这样做可以得到更大的好处（更有效），2、具体进行这个算法的时侯，应该怎么做能找到切分（Tiling）的方法。
最后，文章给出了一些实验的数据。从中可以看出，使用这个方法的效果的确很好，基本上，在同等的时间内，解决问题的规模和处理器的个数可以成线形关系。
在PLDI2007上还有另外一篇讲并行化的文章。那篇文章针对的问题则是“不规则的计算”。比如处理图、链表、树等复杂链接数据结构的程序。那种程序不能使用本文中介绍的方法（由于难以分析依赖性，效果一般很不好）。在那篇文章中使用Transactional Memory的方法对其进行并行化，也能够得到很好的效果。（其实，这里并不是“完全自动”的，它需要程序员给出很少的提示，不过，它要比让程序员自己写多线程的东西，要容易的多。）
看来，并行化的确已经成了一个所有人关心的问题了。当然，基本上讲，这个问题很难。不过，正如一个我认识的人说得“没办法，难，硬着头皮也要上”，因为处理器的发展趋势逼我们这么做。另一个比较有意思的说法是：“悲观的人在机会中看到困难，乐观的人在困难中看到机会”。不知道，这将是谁的机会？
阅读(1364) | 评论(0) | 转发(0) |
