Program Optimization with Data-Specific Compilation

点击翻译按钮获取中文摘要

Irregular data structures, as exemplified with sparse matrices, are essential in modern computing: they are central in numerous scientific applications, ranging from physics simulation to graph processing. A key challenge is to deliver high-performance implementations for computations on irregular structures, which typically use additional arrays to store explicitly the coordinates of non-zero elements in the structure. The project's novelties address the next opportunity for code customization by developing a new kind of data-specific compilation approach that is customized to the unique sparsity pattern in the input data structures. This project designs and fully automates data-specific compilation techniques that can discover and exploit hidden regularity in sparse structures, reducing the development cost to produce high-performance implementations. The project's impacts also include novel theoretical results and practical algorithms to model irregular data structures as a union of (piecewise-)regular structures, exploiting this representation for increased application performance. In machine learning, sparsely connected neural networks can directly benefit from this data-specific compilation approach, enabling the development of improved inference implementations for deep networks.Specifically, the project develops new theory and algorithms to represent sparse data structures using unions of hierarchical polyhedra: the list of non-zero coordinates can be compressed into specialized and more compact affine functions that, when evaluated, would generate exactly the input list of coordinates. The investigators target a range of different hardware accelerators based on SIMD engine principles, and facilitate performance portability by using cost-driven yet machine-independent algorithms to search for optimized implementations. Tools produced are made publicly available as open-source BSD-licensed software.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.