高可扩展性的MHP 分析算法

并行发生(may happen in parallel,简称MHP)分析计算并行程序中哪些语句可以并行执行,它是并行分析技术的重要组成部分.提出一种针对Java 程序的新颖的MHP分析算法.与已有算法相比,新算法抛弃了“子线程只会被父线程等待同步”的假设,以非耦合的方式分别处理start 同步和join 同步;新算法的处理逻辑虽然更加简单,但却更加完备;在计算控制信息时,新算法不必像已有算法那样通过内联构造全局的控制流图,显著地提高了算法的扩展性.新的MHP 算法被用来过滤静态数据竞争检测中虚假的数据竞争.在14 个Java 测试程序上的实验结果表明,新的MHP 算法计算控制信息的开销远远小于已有算法.

Highly Scalable MHP Analysis Algorithm

May happen in parallel (MHP) analysis decides whether a pair of statements in a parallel program can be executed concurrently; it plays an important part in parallel analyses. This paper proposes a novel may-happen-in-parallel analysis algorithm for Java programs. Compared with the existing MHP algorithm, the new alogrithm discards the unnecessary assumption that a child thread can only be join-synchronized by its parent thread, and processes start-synchronization and join-synchronization independently in a decoupled way. This makes the processing logic of the algorithm more concise and more complete than that of the existing algorithm. When computing dominator information, the new algorithm has better scalability for it does not need to construct the global flow graph for the program by inlining, which is needed by the existing algorithms. The new MHP analysis algorithm is used to sift false warnings reported by a static data race detection tool. The experimental results on 14 Java programs show that the time of computing dominator information of the new MHP analysis is much shorter than that of the existing algorithm.