"Separating Algorithm and Implementation via programming Model Injection," Michelle Strout, Colorado State University

Abstract

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

Web Page

More details about this project can be found at SAIMI Web Page [1].

Presentations and Talks

SAIMI Quad Chart from October 2012 File:QUAD ASCR SAIMI-2012.pdf

SAIMI Handout from October 2012 File:SAIMI-handout-Oct-2012.pdf

“Compilers for Regular and Irregular Stencils: Shared Problems and Solutions,” presented at the Workshop on Optimizing Stencil Computations (WOSC) associated with OOPSLA, October 27, 2013.

“Bulk Synchronous to Asynchronous Parallelism: Using Loop Chains and Full Sparse Tiling to Get There,” presented at Australian National University, August 16, 2013.

“Automating Run-Time Reordering Transformations with the Sparse Polyhedral Framework (SPF),” presented at Australian National University in Canberra, July 12, 2012.

“Automating Run-Time Reordering Transformations with the Sparse Polyhedral Framework (SPF) and Arbitrary Task Graphs,” presented at Imperial College in London, November 21, 2011.

“SAIMI: Separating the Algorithm from the Implementation Details,” presented at the DOE ASCAC Meeting , August 24, 2011.

“AutotuningNeedsforRun-TimeReorderingTransformations,”presentedattheCScADSAutotuning Workshop, August 8, 2011.

“SAIMI and SPF: Separating the Algorithm from the Implementation Details in Sparse Computa- tions,” presented at 2011 DOE Scientific Discovery through Advanced Computing (SciDAC) confer- ence, July 12, 2011.

Papers

An Approach for Code Generation in the Sparse Polyhedral Framework, Michelle Mills Strout, Alan LaMielle, Larry Carter, Jeanne Ferrante, Barbara Kreaseck, and Catherine Olschanowsky, Colorado State University Tech Report #CS-13-109, December, 2013.

Generalizing Run-time Tiling with the Loop Chain Abstraction, Michelle Mills Strout, Fabio Luporini, Christopher D. Krieger, Carlo Bertolli, Gheorghe-Teodor Bercea, Catherine Olschanowsky, J. Ramanujam, and Paul H.J. Kelly, To appear in 28th IEEE International Parallel and Distributed Processing Symposium (IPDPS), May 19-23, 2014.

Non-affine Extensions to Polyhedral Code Generation, Anand Venkat, Manu Shantharam, Mary Hall, and Michelle Mills Strout, To appear in International Symposium on Code Generation and Optimization (CGO), Feb 15-19, 2014.

Compilers for Regular and Irregular Stencils: Some Shared Problems and Solutions, Michelle Mills Strout, Proceedings of Workshop on Optimizing Stencil Computations (WOSC), October 27, 2013.

An optimization-based approach to lookup table program transformations, Chris Wilcox and Michelle Mills Strout and James Bieman, Journal of Software: Evolution and Process, September 2013.

Programming Abstractions to Separate Concerns in Semi-Regular Grids, Andrew Stone and Michelle Mills Strout, In Proceedings of the 27th International Conference on Supercomputing (ICS), June 10, 2013.

Loop Chaining: A Programming Abstraction For Balancing Locality and Parallelism, Christopher D. Krieger, Michelle Mills Strout, Catherine Olschanowsky, Andrew Stone, Stephen Guzik, Xinfeng Gao, Carlo Bertolli, Paul H.J. Kelly, Gihan Mudalige, Brian Van Straalen, and Sam Williams, In Proceedings of the 18th International Workshop on High-Level Parallel Programming Models and Supportive Environments (HIPS), May, 20, 2013.

On the Scalability of Loop Tiling Techniques, Dave G. Wonnacott and Michelle Mills Strout, Proceedings of the 3rd International Workshop on Polyhedral Compilation Techniques (IMPACT), January 21, 2013.

Executing Optimized Irregular Applications Using Task Graphs Within Existing Parallel Models, Christopher D. Krieger and Michelle Mills Strout, Proceedings of the Second Workshop on Irregular Applications: Architectures and Algorithms (IA^3) held in conjunction with SC12, November 11, 2012.

Optimizing Expression Selection for Lookup Table Program Transformation, Chris Wilcox and Michelle Mills Strout and James Bieman, Proceedings of the 12th IEEE International Working Conference on Source Code Analysis and Manipulation (SCAM), September 2012.

On the Scalability of Loop Tiling Techniques, David G. Wonnacott and Michelle Mills Strout, Dept. of Computer Science, Haverford College, Haverford PA Technical report 2012-01, August 2012.

A Fast Parallel Graph Partitioner for Shared Memory Inspector/Executor Strategies, Christopher D. Krieger and Michelle Mills Strout, Proceedings of the 25th International Workshop on Languages and Compilers for Parallel Computing (LCPC), September 2012.

Set and Relation Manipulation for the Sparse Polyhedral Framework, Michelle Mills Strout, Geri George, and Catherine Olschanowsky, Proceedings of the 25th International Workshop on Languages and Compilers for Parallel Computing (LCPC), September 2012.

Establishing a Miniapp as a Programmability Proxy, Andrew I. Stone, John M. Dennis, and Michelle Mills Strout, Poster paper in Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), February 2012.

Parameterized Loop Tiling, Lakshminarayanan Renganarayana, Daegon Kim, Michelle Mills Strout, and Sanjay Rajopadhye, ACM Transactions on Programming Languages and Systems (TOPLAS), May 2012.

Tool support for software lookup table optimization, Chris Wilcox, Michelle Mills Strout, and James Bieman, Journal of Scientific Programming, December 2011.

Evaluating the Separation of Algorithm and Implementation within Existing Programming Models, Michelle Mills Strout, Christopher Krieger, Andrew Stone, Christopher Wilcox, John Dennis, and James Bieman, Proceedings of SciDAC, July 2011.

The CGPOP Miniapp, Version 1.0, Andrew I. Stone, John M. Dennis, and Michelle Mills Strout, Technical Report CS-11-103, July 2011.

Evaluating Coarray Fortran with the CGPOP Miniapp, Andrew I. Stone, John M. Dennis, and Michelle Mills Strout, Partitioned Global Address Space Conference, October 2011.

Mesa: Automatic Generation of Lookup Table Optimizations, Chris Wilcox, Michelle Mills Strout, and James Bieman, Proceedings of the 4th International Workshop on Multicore Software Engineering, May 2011.

Steps Toward Simplifying Sparse Matrix Data Structures, Stephanie Dinkins, Barbara Kreaseck, and Michelle Mills Strout, Proceedings of the Colorado Celebration of Women in Computing (CCWIC), Nov 4-5, 2010.

Performance Evaluation of an Irregular Application Parallelized in Java, Christopher Krieger and Michelle Mills Strout, The Proceedings of the First International Workshop on Parallel Software Tools and Tool Infrastructures (PSTI), 2010.

Qualitative Evaluation Criteria for Parallel Programming Models, Christopher Krieger, Andrew I. Stone, and Michelle Mills Strout, The Proceedings of the Fun Ideas and Thoughts Session at PLDI (FIT), 2010.

Mechanisms that Separate Algorithms from Implementations for Parallel Patterns, Christopher D. Krieger and Andrew Stone and Michelle Mills Strout, Workshop on Parallel Programming Patterns (ParaPLOP), March 2010.

Enabling Code Generation within the Sparse Polyhedral Framework, Alan LaMielle and Michelle Mills Strout, Technical Report CS-10-102 Colorado State University, March 2010.