Efficiently Detecting Races in Cilk Programs That Use Reducer Hyperobjects
Efficiently Detecting Races in Cilk Programs That Use Reducer Hyperobjects
复制标题
有效检测使用Reducer超对象的Cilk程序中的竞争
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
T. Schardl
中科院分区：
文献类型：
--
作者：
I. Lee;T. Schardl
表面上是确定性的多线程CILK程序可能由于代码中的编程错误而行为不确定。对于使用还原器的CILK程序，在各种CILK方言中支持的一般还原机制，此类编程错误在调试中尤其具有挑战性，因为这些错误可能会在CILK运行时系统如何管理还原器方面暴露出非确定性。我们确定了两种独特的种族类型，这些种族是由于在CILK程序中不正确使用还原器而引起的，并提出了两种算法来捕获它们。第一种算法称为对等点算法，检测到查看读取的种族，当程序试图在读取可能导致不确定的值时试图从还原器中检索值时发生，例如，如前所有先前产卵的子分组器可能更新可能更新还原器一定要返回。第二种算法称为SP+算法，检测确定性竞赛，即使在逻辑上写入内存位置与对该位置的另一个访问，即使在赛车内进行赛内存位置与还原相关的情况也是如此。两种算法都是正确的，渐近地有效的，并且可以在实践中有效地实施。我们已经在原型种族检测器Rader中实现了这两个算法。运行对等式时，RADER会在没有仪器的情况下运行基准测试，从而产生2.32的几何均值乘法开销。运行SP+时，RADER会产生16.76的几何均值乘法开销。
A multithreaded Cilk program that is ostensibly deterministic may nevertheless behave nondeterministically due to programming errors in the code. For a Cilk program that uses reducers, a general reduction mechanism supported in various Cilk dialects, such programming errors are especially challenging to debug, because the errors can expose the nondeterminism in how the Cilk runtime system manages a reducer. We identify two unique types of races that arise from incorrect use of reducers in a Cilk program and present two algorithms to catch them. The first algorithm, called the Peer-Set algorithm, detects view-read races, which occur when the program attempts to retrieve a value out of a reducer when the read may result a nondeterministic value, such as before all previously spawned subcomputations that might update the reducer have necessarily returned. The second algorithm, called the SP+ algorithm, detects determinacy races, instances where a write to memory location occurs logically in parallel with another access to that location, even when the raced-on memory locations relate to reducers. Both algorithms are provably correct, asymptotically efficient, and can be implemented efficiently in practice. We have implemented both algorithms in our prototype race detector, Rader. When running Peer-Set, Rader incurs a geometric-mean multiplicative overhead of 2.32 over running the benchmark without instrumentation. When running SP+, Rader incurs a geometric-mean multiplicative overhead of 16.76.