K.-S. Ha, E.-K. Ryu (Korea), S.-W. Lee (Sweden), and K.-Y. Yoo (Korea)
parallel programming, data race detection, restructuring, serializing, on the fly
Data race could result in unintended non-deterministic executions of the parallel program on the shared memory. So, detecting races, particularly first data races, is important for debugging explicit shared memory parallel programs. To detect data races parallel programs with nested loops and inter-thread coordination, it must guarantee the order of synchronization operations in an execution instance. We address post/wait synchronization, the most powerful type of synchronization for which efficient race detection is possible. In this paper, we propose a restructuring algorithm that guarantee ordering execution instance and preserve the semantics of original program, being possible sequential monitoring and eliminating space overhead. The space complexity of our algorithm requires O(s + nt) where n is the number of total operations, s is the number of synchronization operations and t is the number of parallel threads in the execution. This algorithm makes on-the-fly detection of parallel program with nested loops and inter-thread coordination more easily in space complexity.
Important Links:
Go Back
