Title: Sum-product Superoptimization via Relational Equality Saturation
Advisors: Dan Suciu
Abstract:
Machine learning algorithms are commonly specified in linear algebra (LA) expressions. These expressions can be rewritten into more efficient forms, by taking advantage of input properties such as matrix sparsity, as well as program properties such as common sub-expressions and operator fusions. However, existing optimizing compilers struggle to reason about the complex interaction among these properties’ impact on the cost of execution. As a result, they fail to search through the large space of equivalent LA expressions and find the cheapest one to run.
We introduce a technique for optimizing LA expressions with sum, product and aggregate operations, while exploiting matrix sparsity and common sub-expressions, and supporting operator fusion and custom functions. Our optimizer leverages relational algebra as an intermediate representation to completely represent the search space; it then searches for the optimal expression via equality saturation. We integrate the optimizer into SystemML, and our experiments show competitive performance alongside existing optimization heuristics across a spectrum of machine learning tasks, as well as significant speedups in cases where newfound rewrites apply.
Place:
CSE1 (Allen Center) 403
When:
Wednesday, November 20, 2019 - 09:30 to Wednesday, April 17, 2024 - 13:08