TY - GEN
T1 - Sparse computation data dependence simplification for efficient compiler-generated inspectors
AU - Mohammadi, Mahdi Soltan
AU - Davis, Eddie C.
AU - Nandy, Payal
AU - Yuki, Tomofumi
AU - Hall, Mary
AU - Olschanowsky, Catherine
AU - Strout, Michelle Mills
AU - Cheshmi, Kazem
AU - Dehnavi, Maryam Mehri
AU - Venkat, Anand
N1 - Funding Information:
This material is based upon work supported by the National Science Foundation under Grant No. NSF CCF-1563732. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author and do not necessarily reflect the views of the National Science Foundation. We would also like to acknowledge Ganesh Gopalakrishnan for his contributions to an earlier version of this paper.
Publisher Copyright:
© 2019 Association for Computing Machinery. ACM
PY - 2019/6/8
Y1 - 2019/6/8
N2 - This paper presents a combined compile-time and runtime loop-carried dependence analysis of sparse matrix codes and evaluates its performance in the context of wavefront paral-lellism. Sparse computations incorporate indirect memory accesses such as x[col[j]] whose memory locations cannot be determined until runtime. The key contributions of this paper are two compile-time techniques for significantly reducing the overhead of runtime dependence testing: (1) identifying new equality constraints that result in more efficient runtime inspectors, and (2) identifying subset relations between dependence constraints such that one dependence test subsumes another one that is therefore eliminated. New equality constraints discovery is enabled by taking advantage of domain-specific knowledge about index arrays, such as col[j]. These simplifications lead to automatically-generated inspectors that make it practical to parallelize such computations. We analyze our simplification methods for a collection of seven sparse computations. The evaluation shows our methods reduce the complexity of the runtime inspectors significantly. Experimental results for a collection of five large matrices show parallel speedups ranging from 2x to more than 8x running on a 8-core CPU.
AB - This paper presents a combined compile-time and runtime loop-carried dependence analysis of sparse matrix codes and evaluates its performance in the context of wavefront paral-lellism. Sparse computations incorporate indirect memory accesses such as x[col[j]] whose memory locations cannot be determined until runtime. The key contributions of this paper are two compile-time techniques for significantly reducing the overhead of runtime dependence testing: (1) identifying new equality constraints that result in more efficient runtime inspectors, and (2) identifying subset relations between dependence constraints such that one dependence test subsumes another one that is therefore eliminated. New equality constraints discovery is enabled by taking advantage of domain-specific knowledge about index arrays, such as col[j]. These simplifications lead to automatically-generated inspectors that make it practical to parallelize such computations. We analyze our simplification methods for a collection of seven sparse computations. The evaluation shows our methods reduce the complexity of the runtime inspectors significantly. Experimental results for a collection of five large matrices show parallel speedups ranging from 2x to more than 8x running on a 8-core CPU.
KW - Data dependence simplification
KW - Dependence analysis
KW - Inspector-executor strategies
KW - Presburger arithmetic with uninterpreted functions
KW - SMT solvers
KW - Sparse matrices
UR - http://www.scopus.com/inward/record.url?scp=85067677186&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85067677186&partnerID=8YFLogxK
U2 - 10.1145/3314221.3314646
DO - 10.1145/3314221.3314646
M3 - Conference contribution
AN - SCOPUS:85067677186
T3 - Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI)
SP - 594
EP - 609
BT - PLDI 2019 - Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation
A2 - McKinley, Kathryn S.
A2 - Fisher, Kathleen
PB - Association for Computing Machinery
T2 - 40th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2019
Y2 - 22 June 2019 through 26 June 2019
ER -