| Data analytics in many modern applications often spend a large number of cycles on unnecessary computations, while such redundant computations have been hidden in the useful instructions of the applications and are elusive for those automatic code optimizations developed over the past decades. Many algorithms have been manually designed for each specific application, however, none of them are automatic/semi-automatic or generally applicable. My research resides at the intersection of Compiler Technology and (Big) Data Analytics, pioneering the efforts of raising the level of automatic program optimizations from implementations to algorithms, and from instructions to formulas. In particular, we find that the algorithm generated by such automatic High-Level Program Optimization matches or outperforms the algorithms manually designed by the domain experts, and thus could have saved decades of manual effort by domain experts.;Enabling such High-Level Program Optimizations, in general, faces three fundamental challenges: (1) the requirement of the high-level semantics of the application, which is often hidden in the low-level implementation; (2) the requirement of knowledge of beneficial and legal higher-level transformations that could change large blocks of code; and (3) the need for efficient ways to explore the enormous space of algorithmic or other higher-level transformation choices. My thesis shows how these challenges can be addressed through the development of proper abstractions, new optimization algorithms, and an innovative two-level learning algorithm design. The enabled High-Level Program Optimizations frequently lower the practical computational complexities of applications, boosting their performance by up to several orders of magnitude. |
