What is the Cost of Weak Determinism?

We analyze the fundamental performance impact of enforc-ing a fixed order of synchronization operations to achieve weak deterministic execution. Our analysis is in three parts, performed on a real system using the SPLASH-2 and PAR-SEC benchmarks. First, we quantify the impact of various sources of nondeterminism on execution of data-race-free programs. We find that thread synchronization is the preva-lent source of nondeterminism, sometimes affecting program output. Second, we divorce the implementation overhead of a system imposing a specific synchronization order from the impact of enforcing this order. We show that this fundamen-tal cost of determinism is small (slowdown of 4 % on average and 32 % in the worst case) and we identify application char-acteristics responsible for this cost. Finally, we evaluate this cost under perturbed execution conditions. We find that de-manding determinism when threads face such conditions can cause almost 2x slowdown