Relaxed Consistency Deterministic Execution in Hardware and Software
Principal Investigator: Luis Ceze
Nondeterminism is one of the main reasons that parallel programming is so difficult. Bugs can vanish when programs are rerun or run under a debugger, thwarting attempts at their removal. Stress testing is a common practice to flush out rare defects, though it consumes extensive processing power and offers no real guarantees of discovering bugs. Deployment can similarly expose new issues that are difficult to reproduce. Finally, nondeterminism thwarts attempts at replicating multithreaded programs for fault-tolerance, as the replicas can diverge silently.
Our work at UW has shown how to provide determinism for arbitrary parallel programs, which eliminates these problems, making debugging and replication possible and making testing more valuable and efficient. The crucial question for deterministic execution remains its performance cost. To this end, we have designed a new deterministic execution algorithm which uses memory consistency relaxations to improve latency and scalability. This approach affords a natural hardware/software implementation, leveraging private caches to cheaply enforce thread isolation while leaving the policy of when to make updates visible under software control. Finally, we eliminated the dependence on always-on micro-architectural speculation that previous deterministic hardware relied upon, greatly simplifying the design of deterministic multiprocessors while retaining good performance.
Exclusive or nonexclusive license
For more info, contact: Laura Dorsey