Detail

Parallel Programming Refinements for Irregular Applications

General-purpose processors will be many-core processors in which the number of cores are expected to double every 1.5 years and it is likely that these cores will be heterogeneous in functionality.
The move towards many-core architectures shifts the burden of improving program execution speed from chip manufactures to software developers, requiring a fundamental change in the way software is developed and maintained. In many-core systems, applications must be parallelized in order to take full advantage of available processing power. Performance portability will also be very important.

It is well known that using libraries or combinations of compiler directives/ thread libraries to write threaded code can be difficult. Some estimates point to a tripling of software costs. Communication libraries such as MPI are too expensive for the mass market and most current knowledge about parallel programming is confined to “regular programs”, i.e., programs that manipulate dense matrices. However, most many-core applications are likely to be “irregular”, dealing with pointer-based data structures such as lists, trees, and graphs. Little is known about patterns of parallelism and locality in irregular programs and there are very few languages constructs and tools for assisting programmers in developing such classes of programs.
Recently the Galois project performed a number of case studies of irregular programs that show that many of these programs have a generalized form of data-parallelism called “amorphous data-parallelism”. The Galois group is building a system for exploiting amorphous data-parallelism on many-core processors. The programming model for this system is sequential Java, augmented with constructs called Galois set iterators. Preliminary results are promising but it is unlikely that an automatic system like Galois will always be able to produce high-quality parallel code for every application and on every platform. Thus, it is necessary to design and implement programming models for writing explicitly parallel programs for irregular applications. These models must also permit expression of locality of reference, which is important even on sequential platforms.
Programming paradigms promoting separation of concerns can play a crucial role to address the development complexity of parallel applications. This project will explore the idea of promoting the separation of parallelization concerns from domain specific and platform specific concerns, with the aim to improve reusability, enable independent evolution and increase the flexibility to switch and to compose parallelization strategies. Decomposition of parallelization concerns into high level features (fine-grained refinements that add implementation detail, such as parallelism or the use of particular data structures) will make it possible to synthesize/tune applications for each class of target platforms and/or problems by selecting the set of features to attain the best performance. We aim to identify and modularize refinements that parallelize computations in programs, and to be able to compose such refinements to map base programs to efficient, platformspecific, parallel applications. We start with a base program, specified in a platform independent manner, and progressively increment its functionality towards a more platform specific version. Aspect and feature oriented programming (AOP/FOP) are two approaches for separation of concerns that will be used as a starting point to implement those refinements. Thus, in our proposed approach, parallel programming abstractions are application refinements. The proposed approach will be validated by making Galois an extensible run-time platform, by allowing the addition of new program refinements and identifying the conditions under which such new refinements can be effectively used. We will use existing case studies of Galois, but also a new case study that implements a ray tracer, where parallelism and locality of references will be expressed as program refinements.