UC Santa Cruz

Most systems that test and verify parallel programming, such as data race detectors and software transactional memory systems, require instrumenting loads and stores in an application. This can cause a very significant runtime and memory overhead compared to executing uninstrumented code. Multithreaded programming typically allows any thread to perform loads and stores at any location in the process's address space independently. Most of these unsynchronized memory accesses are non-conflicting in nature; that is, the values read from or written to memory are only used by a single thread. We propose Section Based Program Analysis (SBPA), a novel way to decompose the program into disjoint sections to identify non-conflicting loads and stores during program compilation.

We combine SBPA with improved context sensitive alias analysis, loop specific optimizations and a few user directives to further increase the effectiveness of SBPA. We implemented SBPA for a deterministic execution runtime environment, and were able to eliminate 63% of dynamic memory access instrumentations. We also integrated SBPA with ThreadSanitizer, a state of the art dynamic race detector, and achieved a speed-up of 2.74 times on a geometric mean basis. Lastly, we show that SBPA is also effective in static race detection.