Accelerated performance modeling and tuning of parallel programs

Novel capabilities provided by an ever-diversifying array of modern architectures have increased the dimension of application parameter spaces and the complexity of performance exhibited across them. Despite a wealth of available performance models and automatic performance tuning (autotuning) frameworks, accurate prediction of high-dimensional application performance remains significantly challenging. This dissertation introduces novel techniques to improve the state-of-the-art in performance modeling and autotuning. We first consider the development of a model to estimate the performance of an application across a high-dimensional parameter space. Provided a collection of observed runtimes, as opposed to relying on expert knowledge of application or architecture, we propose and evaluate the use of tensors for modeling an application's performance. Specifically, we use tensors to represent regular grids that discretize the input and configuration domains of an application. Application execution times mapped within grid-cells are averaged and represented by tensor elements. We show that low-rank Canonical-Polyadic (CP) tensor decomposition is effective in approximating these tensors. To account for unobserved grid-cells, we employ tensor completion to optimize a CP decomposition. We then extend our model to provide accurate runtime estimates for problem sizes larger than those present in the observed subdomain. We fit a piecewise-linear model to a positive rank-1 approximation of each factor matrix to achieve this. We consider alternative piecewise/grid-based (P/G) and supervised learning models for a diverse set of applications and demonstrate that these P/G models are significantly more accurate relative to model size. Among P/G models, our tensor models offer higher prediction accuracy and memory-efficiency, and superior extensibility via application-specific loss functions and domain partitioning. We next consider the problem of search across an application's high-dimensional configuration space, for which alternative error metrics and datasets are present. In this setting, we propose and evaluate profiling techniques for accelerating the selection of optimal tuning parameters of MPI applications at scale during runtime. We introduce a framework for approximate autotuning that achieves a desired confidence in each application configuration's performance by constructing confidence intervals to describe the performance of individual kernels (subroutines of benchmarked applications) invoked by the application. Once a kernel's performance is deemed sufficiently predictable for a set of inputs, subsequent invocations are avoided and replaced with a predictive model of the execution time. We then leverage online critical-path analysis to coordinate selective kernel execution and propagate each kernel's statistical profile. This strategy is effective in the presence of frequently-recurring computation and communication kernels, which is characteristic to algorithms in numerical linear algebra. We encapsulate this framework as part of a new profiling tool, Critter, that automates kernel execution decisions and propagates statistical profiles along critical paths of execution.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2024

Author dc:creator

• Hutter, Edward F

Contributors dc:contributor

• Solomonik, Edgar
• Gropp, William
• Mendis, Charith
• Vuduc, Richard
• Li, Xiaoye

• Performance Modeling
• Autotuning

Statement dc:rights

• Copyright 2024 Edward Hutter

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/124368

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F124368