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

  • swap_vertical_circlelibrary_booksReferences (0)
  • swap_vertical_circlecloud_downloadDownloads (0)
    Files marked with an asterix (*) can only be downloaded by users that have the appropriate product license. The license must be active and you must be logged into your account.