Accelerated performance modeling and tuning of parallel programs

Hutter, Edward F

Permalink

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

Description

Title

Accelerated performance modeling and tuning of parallel programs

Author(s)

Hutter, Edward F

Issue Date

2024-04-24

Director of Research (if dissertation) or Advisor (if thesis)

Solomonik, Edgar

Doctoral Committee Chair(s)

Solomonik, Edgar

Committee Member(s)

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

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Performance modeling
• Autotuning

Abstract

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.

Graduation Semester

2024-05

Type of Resource

Thesis

Copyright and License Information

Copyright 2024 Edward Hutter

Owning Collections