SAIMI: Separating Algorithm and Implementation via programming Model Injection
(Spring 2011 handout)The problem we are tackling is that parallel programming implementation details often obfuscate the original algorithm and make later algorithm maintenance difficult. Our idea is to provide separate interfaces for the specification of algorithms and the implementation details such as how to schedule the algorithms on parallel computer systems. We propose to inject programming models into existing host languages and provide high-level implementation abstractions to prevent algorithm obfuscation due to performance tuning. The definition of an injectable programming model is still evolving, but an initial definition is a programming abstraction like the polyhedral model or task graphs. These programming abstractions can be injected using pragmas and are constrained enough to enable the orthogonal specification of implementation details.
We will develop injectable programming models for specifying performance critical algorithms such as dense and sparse matrix computations, task graph computations, stencil computations, and lookup tables. We envision high-level, orthogonal implementation abstractions that will enable application and performance programmers to specify the implementation for each algorithm differently for each target architecture. Our research plan is to (1) evaluate existing mechanisms for orthogonally specifying implementation details, (2) raise the level of abstraction for implementation specification in existing mechanisms for a set of injectable programming models, and (3) develop libraries and preprocessors capable of composing orthogonal algorithm and implementation specifications. We will evaluate the programmability and performance of our approach on performance-critical computations in various small, medium, and large scientific computing benchmarks written in C++.