ACM通信
研究突出了
技术视角:并行的抽象
寻找对老问题的新见解?Milind Kulkarni等人的以下研究论文解决了编写并行应用程序的常见问题，并使用了一种基于数据抽象的新方法来实现一些具有挑战性的程序的并行化。回到30多年的基础工作Owicki葛瑞斯并行程序的语义,并通过几十年的自动并行化Fortran和C程序,重点研究和商业社区一直在推理在具体层面的读和写操作:如果两个迭代循环访问相同的变量,和至少一个执行写操作,然后迭代不能并行执行。当与静态编译时方法相结合时，必要的保守分析技术意味着许多循环不能并行化，特别是对于具有基于指针的数据结构的程序。
随着计算机行业押注于多核，对并行软件问题解决方案的需求达到了一个新的关键水平。并行研究已经复兴，其中大部分关注于使用推测技术的并行的动态发现。作者通过将循环构造与冲突分析和回滚机制相结合来构建动态并行发现的思想，以支持推测并行。本文所描述的伽罗瓦系统既有有序循环，也有无序循环，但在这两种情况下都向用户呈现串行语义。Galois使用类型系统进一步控制这种循环的行为。使用传统投机并行模型的对象是所谓的“捕获并保持”类的实例，因为运行时系统在整个迭代过程中保持一个锁，以确保迭代看起来是串行执行的。
但有一类有趣的算法即使在存在冲突的访问时也允许正确的行为。例如，分支和绑定搜索可以以任何顺序进行，但必须更新表示当前绑定的变量的值。作者还添加了推测执行:允许程序员在对象交换中指定两个方法调用，这意味着它们可以安全地重新排序。在分支和绑定示例中，如果为绑定定义了一个类，只使用读取绑定的操作和对新发现的绑定执行max操作来单调地更新它，则更新操作彼此交换。此外，对抽象值没有影响，但对底层状态有“有益的副作用”的方法将在抽象级别上交换，尽管有冲突的访问。
具有交换性规范的类称为“捕获-释放”类，因为实现只在方法调用期间持有锁，以确保操作的原子性，而不是在整个迭代过程中持有锁。迭代的序列化是通过方法的交换性来保证的，如果发现了抽象冲突，则通过回滚来保证。
与无序循环相结合的交换性规范给出了介于显式并行和顺序编程之间的编程模型，因为程序员可以提供许多重排序操作的机会，但程序仍然具有串行语义。并行化一些复杂的不规则应用程序所需的最后一个概念是，在捕获-释放类上具有副作用的方法必须具有反向方法，以便在发现抽象级冲突的情况下“撤消”这些影响。这允许并行地执行迭代，只要已知所涉及的方法可以交换，就可能存在对变量的读和写冲突。如果在两个非交换的方法调用之间发现抽象冲突，运行时层将使用已执行操作的逆操作回滚其中一个迭代。
作者成功地将这些思想应用于两个复杂的并行化问题:非结构化网格细化算法和数据挖掘中的聚类算法。这两个问题都涉及到不规则的控制流和基于指针的数据结构，使得它们对于静态并行方法或甚至基于具体冲突检测的推测并行都难以处理。
这篇论文用这两个引人注目的例子展示了一般的想法，概念既新颖又发人深省。像面向对象这样的抽象机制通常被认为是性能和并行化的阻碍，但在这种方法中，数据抽象为交换性提供了规范点，因此是并行化的关键。作者在示例和总体方法中提出了许多有趣的语义问题，对于那些对并行编程的新视角感兴趣的人，我强烈推荐本文。
©2009 acm 0001-0782/09/0900 $10.00
允许为个人或课堂使用本作品的全部或部分制作数字或硬拷贝，但不得为盈利或商业利益而复制或分发，且副本在首页上附有本通知和完整的引用。以其他方式复制、重新发布、在服务器上发布或重新分发到列表，需要事先获得特定的许可和/或付费。
数字图书馆是由计算机协会出版的。版权所有©2009 ACM, Inc.
没有找到条目