This project will implement irregular applications on parallel computers by embedding ideas of nested data parallelism into an object-oriented programming language (Java), thus providing an architecture-independent programming system for sparse and irregular applications. It will investigate the following fundamental issues: linguistic mechanisms to express concurrency, compilation techniques to enable parallel execution, and the enrichment of the nested data-parallel model. Data parallelism expresses concurrency through operations over the elements of a collection; nested data parallelism allows the elements of a collection to themselves be collections, and extends the model to irregular domains such as graphs and trees. Objects provide data abstraction, encapsulation of state, inheritance, and communication. This project will integrate nested data parallelism with Java using a combination of class libraries, source-to-source preprocessing, and the concurrency mechanisms of Java. This project will carry out the following activities. The claim of expressiveness will be demonstrated by writing several irregular applications (chosen from irregular mesh solvers, tree-structured n-body methods, particle-in-cell codes, and direct and iterative sparse matrix computations) in Java augmented with a "for each" construct. Compilation techniques will be developed for nested data parallelism embedded in Java. This will explore the tradeoffs between two techniques: the synchronous technique of flattening, and anasynchronous approach involving preprocessing the nested parallelism into standard Java, exploiting the built-in support for concurrency in the language. The nested data-parallel model will be enhanced in ways such as adding new collection types (e.g., graphs and trees) and providing compiled communication operations (e.g., match and move).
