Approximate Data Dependence Graph Generation Using Adaptive Sampling

Identifying data dependence among loop iterations is a fundamental step in the parallelisation process. Generally, code instrumentation provides for such information at the expense of high runtime performance penalty. This paper proposes an efficient method that trades slight accuracy reduction with significant performance gain to generate an approximate dependence graph. The proposed method relies on replicating the loop under test, providing for instrumented and not instrumented code versions, and adaptively switching between them, as well as deciding on the analysis detail, depending on the stability of measured dependence distances. Moreover, the method utilises random sampling, decreasing the chances of missing dependent irregular memory accesses. An initial performance investigation of the method is conducted using the Pin binary instrumentation tools; results on selected PolyBench kernels shows up to 8.5x improvement in instrumentation time, with no missed dependencies in 14 kernels, and 45% missed dependencies in one kernel.