Programming model and software system for exploiting parallelism in irregular programs

摘要

Systems and methods for parallelizing applications that operate on irregular data structures. In an embodiment, the methods and systems enable programmers to use set iterators to express algorithms containing amorphous data parallelism. Parallelization can be achieved by speculatively executing multiple iterations of the iterator in parallel. Conflicts between speculatively executing iterations can be detected and handled using information in class libraries.

主权项

1. A method for automatically exploiting amorphous data-parallelism in computer programs, comprising:
generating sequential code comprising at least one optimistic iterator that highlights opportunities for exploiting amorphous data-parallelism; wherein the optimistic iterator comprises: an enumeration of work-set elements that permits additional work-set elements to be added to work-set during enumeration; and an order constraint on the enumeration that is one of, one order only, no order, or partial order; providing the sequential code and a library to a parallel code compiler, resulting in compiled code, wherein the library comprises user specified properties, and wherein the user specified properties comprises atomicity properties for a plurality of methods, commutativity properties for the plurality of methods, undo procedures for the plurality of methods, and locality properties for the plurality of methods, and wherein the locality properties for the plurality of methods comprise partitioning of objects into multiple logical partitions and specifying for each method a programmatic way of determining which logical partitions the plurality of methods access; providing the compiled code to a runtime system for parallel execution, wherein the runtime system is configured to evaluate, at run-time, commutativity of at least two iterations of the at least one optimistic iterator based on the commutativity properties.