The University of Arizona
banner image

CHiLL-I/E: An Inspector/Executor Compilation Framework for Irregular Applications

Irregular applications such as molecular dynamics simulations, n­body simulations, finite element analysis, and big graph analytics constitute a critical and significant portion of scientific computing applications. An irregular application is characterized by having indirect memory accesses such as A[B[i]] that cannot be determined when the application is being compiled, therefore severely limiting the applicability of the large body of work on parallelizing compiler technology. Consequently, irregular applications, which are so important in pushing forward the frontiers of science, place a very large burden on computational and domain scientists in developing high­performance implementations for the ever­changing landscape of parallel architectures.

For regular applications, the parallelizing compiler research community has developed approaches for transforming maintainable code to highly­optimized code specific to a variety of parallel architectures such as multi­core processors and many­core accelerators. Irregular applications have been considered mostly beyond the reach of parallelizing compilers due to information required for optimization only becoming available at execution time. For example, static analysis lacks the necessary information to analyze access patterns within the context of indirect array accesses, e.g. A[B[i]], where the contents of B are determined dynamically.

The goal of this project is to develop a source­to­source compilation and runtime framework to increase the productivity of expert programmers in achieving both high performance and portability on a wide variety of irregular applications. We will employ an inspector/executor paradigm, whereby a runtime inspector will collect information needed for optimization, and an optimized executor will utilize this information to produce tuned, architecture-specific implementations.

Publications

Extending Loop Transformation Frameworks to Irregular Applications, Milind Kulkarni, Louis-Noel Pouchet, and Michelle Mills Strout, PPoPP 2020 Tutorial, February 2020, (html), (BibTEX).

MatRox: Modular approach for improving data locality in Hierarchical (Mat)rix App(Rox)imation, Bangtian Liu, Kazem Cheshmi, Saeed Soori, Michelle Mills Strout, and Maryam Mehri Dehnavi, In PPoPP, February, 2020, (pdf), (BibTEX).

Sparse Computation Data Dependences Simplification for Efficient Compiler-Generated Inspectors, Mahdi Soltan Mohammadi, Tomofumi Yuki, Kazem Cheshmi, Eddie C. Davis, Mary Hall, Maryam Mehri Dehnavi, Payal Nandy, Catherine Olschanowsky, Anand Venkat, and Michelle Mills Strout, Programming Languages Design and Implementation (PLDI), June 2019, (pdf), (BibTEX).

The Sparse Polyhedral Framework: Composing Compiler-Generated Inspector-Executor Code, Michelle Mills Strout, Mary Hall, and Catherine Olschanowsky, Proceedings of the IEEE, November, 2018, (link to pdf), (BibTEX).

ParSy: Inspection and Transformation of Sparse Matrix Computations for Parallelism, Kazem Cheshmi, Shoaib Kamil, Michelle Mills Strout, and Maryam Mehri Dehnavi, In Supercomputing (SC), November, 2018, (pdf), (BibTEX).

Extending Index-Array Properties for Data Dependence Analysis, Mahdi Soltan Mohammadi, Kazem Cheshmi, Maryam Mehri Dehnavi, Anand Venkat, Tomofumi Yuki, and Michelle Mills Strout, Languages and Compilers for Parallel Computing, October 2018, (pdf), (BibTEX).

Sparse Matrix Code Dependence Analysis Simplification at Compile Time, Mahdi Soltan Mohammadi, Kazem Cheshmi, Ganesh Gopalakrishnan, Mary Hall, Maryam Mehri Dehnavi, Anand Venkat, Tomofumi Yuki, and Michelle Mills Strout, arXiv:1807.10852, July 2018, (pdf), (BibTEX).

Transforming Loop Chains via Macro Dataflow Graphs, Eddie C. Davis, Michelle Mills Strout, and Catherine Olschanowsky, Proceedings of the 2018 International Symposium on Code Generation and Optimization (CGO), February 2018, (pdf), (BibTEX).

Sympiler: Transforming Sparse Matrix Codes by Decoupling Symbolic Analysis, Kazem Cheshmi, Maryam Mehri Dehnavi, Shoaib Kamil, and Michelle Mills Strout, In Supercomputing (SC), November, 2017, (pdf), (BibTEX).

Automating Wavefront Parallelization for Sparse Matrix Computations, Anand Venkat, Mahdi Soltan Mohammadi, Hongbo Rong, Rajkishore Barik, Jongsoo Park, Michelle Mills Strout, and Mary Hall, Nominated for a best paper award! In Supercomputing (SC), November, 2016, (pdf), (BibTEX).