Efficiently Detecting Races in Cilk Programs That Use Reducer Hyperobjects

A multithreaded Cilk program that is ostensibly deterministic may nevertheless behave nondeterministically due to programming er-rors in the code. For a Cilk program that uses reducers, a general reduction mechanism supported in various Cilk dialects, such pro-gramming errors are especially challenging to debug, because the errors can expose the nondeterminism in how the Cilk runtime sys-tem 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, de-tects view-read races, which occur when the program attempts to retrieve a value out of a reducer when the read may result a nonde-terministic value, such as before all previously spawned subcompu-tations that might update the reducer have necessarily returned. Th