Internally Deterministic Parallel Algorithms Can Be Fast

The virtues of deterministic parallelism have been argued for decades and many forms of deterministic parallelism have been described and analyzed. Here, the authors are concerned with one of the strongest forms, requiring that for any input there is a unique dependence graph representing a trace of the computation annotated with every operation and value. This has been referred to as internal determinism, and implies a sequential semantics - i.e., considering any sequential traversal of the dependence graph is sufficient for analyzing the correctness of the code.

Provided by: Association for Computing Machinery Topic: Cloud Date Added: Feb 2012 Format: PDF

Download Now

Find By Topic