论文部分内容阅读
并行计算是当前计算机技术发展的趋势。随着多核和众核技术的发展，越来越多的软件和应用程序需要使用多线程语言编写。众所周知，并行程序远远比串行程序难编写，非常容易出现各种各样的错误，例如死锁、原子性违反等等。数据竞争是引起并行程序错误的主要原因之一。并行程序非常容易出现数据竞争;有一部分数据竞争是由于程序员的疏漏导致的，而另外一部分数据竞争则是程序员刻意引入，用来实现微妙而复杂的并行算法。不同性质和种类的数据竞争会引发不同的问题，它们需要被区别对待。 本文对并行程序中的数据竞争问题展开研究，主要创新和贡献如下: 1.提出数据竞争分类理论:根据数据竞争引起的问题的性质对数据竞争进行分类，并给出每一类数据竞争的形式化定义。 2.给出一种用户自定义同步的严格定义，一般性的回答了如下两个问题: 1)什么样的冲突访存构成这种用户自定义同步？ 2)其他冲突的访存如何正确地被这种用户自定义同步机制同步了？ 3.提出一个新的内存一致性模型，称为无问题竞争模型(Buggy-Race-Free Model,BRFM)。BRFM对属于Buggy-Race-Free的程序维护顺序一致性语义，而让其他（含有Buggy Races的）程序的语义是未定义的。在BRFM模型下，由用户自定义同步编程引入的通信竞争和非顺序一致性竞争可以正确地执行。 4.实现了一个静态分析工具来对Java程序中存在的数据竞争进行分类。实验结果表明该分析工具可以有效地发现潜在可能出错的数据竞争。 5.提出了一个新的分析并行程序中并行区域的MHP(May Happen in Parallel)算法，对Java程序中的start/join同步机制进行分析。与已有的算法相比，新算法抛弃了“子线程只会被父线程等待结束”这一冗余假设，以非耦合的方式来分别处理start同步与join同步;在计算控制信息(dominator)时，新算法不必像已有的算法那样构造全程序的控制流图，显著地提高了算法的扩展性。与已有的MHP算法相比，新的算法设计逻辑更加简洁、完备，时间复杂度更小。实验结果表明，新算法的开销仅占已有的MHP算法开销的0.14％。