CHiLL-I/E: An Inspector/Executor Compilation Framework for
Irregular Applications
Irregular applications such as molecular dynamics simulations, nbody
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
highperformance implementations for the everchanging landscape of parallel
architectures.
For regular applications, the parallelizing compiler research
community has developed approaches for transforming maintainable code to
highlyoptimized code specific to a variety of parallel architectures such as
multicore processors and manycore 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 sourcetosource 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.
@misc{ppopp2020tutorial,
title={Extending Loop Transformation Frameworks to Irregular Applications},
author={Milind Kulkarni and Louis-Noel Pouchet and Michelle Mills Strout},
year={2020},
booktitle={ACM SIGPLAN symposium on
Principles and practices of parallel programming (PPoPP)}
}
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).
@inproceedings{Liu2020,
Author = {Bangtian Liu and Kazem Cheshmi and Saeed Soori and
Michelle Mills Strout and Maryam Mehri Dehnavi},
Booktitle = {Proceedings of the ACM SIGPLAN symposium on
Principles and practices of parallel programming (PPoPP)},
Title = {MatRox: Modular approach for improving data locality
in Hierarchical (Mat)rix App(Rox)imation},
Year = {2020}}
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).
@inproceedings{Mohammadi19,
Author = {Mahdi Soltan Mohammadi and Tomofumi Yuki and Kazem Cheshmi and Eddie C. Davis and Mary Hall and Maryam Mehri Dehnavi and Payal Nandy and Catherine Olschanowsky and Anand Venkat and Michelle Mills Strout},
Booktitle = {Programming Languages Design and Implementation (PLDI)},
Title = {Sparse Computation Data Dependences Simplification for Efficient Compiler-Generated Inspectors},
DOI = {https://doi.org/10.1145/3314221.3314646},
Artifact = {https://doi.org/10.5281/zenodo.2644665},
Year = {2019}}
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).
@ARTICLE{8436444,
author={M. M. Strout and M. Hall and C. Olschanowsky},
journal={Proceedings of the IEEE},
title={The Sparse Polyhedral Framework: Composing Compiler-Generated Inspector-Executor Code},
year={2018},
volume={106},
number={11},
pages={1921-1934},
keywords={Sparse matrices;High performance computing;Runtime;Dynamic compiler;Optimization;Intermediate representations;irregular computations;program optimization and parallelization;sparse matrices},
doi={10.1109/JPROC.2018.2857721},
ISSN={0018-9219},
month={Nov},}
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).
@inproceedings{Cheshmi2018,
Address = {New York, NY, USA},
Author = {Cheshmi, Kazem and Dehnavi, Maryam Mehri and
Kamil, Shoaib and Strout, Michelle Mills},
Booktitle = {Proceedings of the International Conference for
High Performance Computing, Networking, Storage and Analysis},
Publisher = {ACM},
Series = {SC '18},
Title = {ParSy: Inspection and Transformation of Sparse
Matrix Computations for Parallelism},
Year = {2018}}
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).
@inproceedings{Mohammadi2018,
Author = {Mahdi Soltan Mohammadi and Kazem Cheshmi and Maryam Mehri Dehnavi and Anand Venkat and Tomofumi Yuki and Michelle Mills Strout},
Booktitle = {Languages and Compilers for Parallel Computing (LCPC)},
Title = {Extending Index-Array Properties for Data Dependence Analysis},
Year = {2018}}
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).
@misc{mohammadi2018sparse,
title={Sparse Matrix Code Dependence Analysis Simplification at Compile Time},
author={Mahdi Soltan Mohammadi and Kazem Cheshmi and Ganesh Gopalakrishnan and Mary Hall and Maryam Mehri Dehnavi and Anand Venkat and Tomofumi Yuki and Michelle Mills Strout},
year={2018},
eprint={1807.10852},
archivePrefix={arXiv},
primaryClass={cs.PL}
}
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).
@inproceedings{Davis2018,
Address = {New York, NY, USA},
Author = {Davis, Eddie C. and Strout, Michelle Mills and Olschanowsky, Catherine},
Booktitle = {Proceedings of the 2018 International Symposium on Code Generation and Optimization (CGO)},
Pages = {265--277},
Publisher = {ACM},
Series = {CGO 2018},
Title = {Transforming Loop Chains via Macro Dataflow Graphs},
Year = {2018},
DOI = {https://doi.org/10.1145/3168832}
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).
@inproceedings{Cheshmi2017,
Address = {New York, NY, USA},
Author = {Cheshmi, Kazem and Kamil, Shoaib and Strout,
Michelle Mills and Dehnavi, Maryam Mehri},
Booktitle = {Proceedings of the International Conference for
High Performance Computing, Networking, Storage and Analysis},
Pages = {13:1--13:13},
Publisher = {ACM},
Series = {SC '17},
Title = {Sympiler: Transforming Sparse Matrix Codes by Decoupling
Symbolic Analysis},
Year = {2017}}
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).
@inproceedings{VenkatSC16,
Author = {Anand Venkat and Mahdi Soltan Mohammadi and
Hongbo Rong and Rajkishore Barik and Jongsoo
Park and Michelle Mills Strout and Mary Hall.},
Booktitle = {In Supercomputing (SC)},
Month = {November},
Title = {Automating Wavefront Parallelization for Sparse
Matrix Computations},
Year = {2016}}