Siddhartha Chatterjee - US grants

This project will develop a set of tools that will automatically map data and computation for HPF programs, thereby reducing the programming time and effort required for producing efficient and portable parallel programs. The system of tools will use the alignment-distribution graph as the internal representation of Fortran 90 (and HPF) programs and use graph-theoretic, linear- algebraic and discrete optimization techniques to determine alignment and distribution of arrays that minimize program completion time. The system will not be limited to the `owner- computes` rule often employed by HPF compilers, but will choose the computation rules that minimize running time of the program. The system will also provide a back-end for generating code for message passing systems, and a graphical user interface for debugging and visual feedback. The project will develop algorithms for inter-procedural layout analysis, and heuristics for reducing the complexity of analysis algorithms. The educational component of this project will develop undergraduate courses with laboratory emphasizing experiment design, measurement and use of statistical analysis.

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).

This award supports Dr. Jan Prins, co-PI Siddhartha Chatterjee, and a graduate student from the University of North Carolina-Chapel Hill in a collaboration with Stefan Jªhnichen of the Department of Communications and Software Engineering at the Technical University of Berlin. The collaboration will study high-performance computing with the aim of integrating nested parallelism into the High Performance Fortran (HPF) and Fortran 95 programming languages. (HPF is a variant of Fortran 95 specifically targeted for programming high-performance parallel computers in a way that does not depend on the computer architecture.) The time is right to incorporate this new technology into Fortran so that applications can take advantage of the capability without disrupting ongoing development. Nested parallelism enables the expression of adaptive and sparse solution techniques necessary to performing increasingly large and precise scientific computations. The collaboration combines the complementary strengths and facilities of the two research groups.