Grace Dinh

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2023-293

December 22, 2023

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2023/EECS-2023-293.pdf

Obtaining good performance for tensor problems requires computing an architecture-specific mapping from the algorithm to the target hardware. Choosing a mapping requires optimizing an objective function over a large, nonconvex space; this objective function represents a performance metric which may be modeled, simulated, or (if possible) measured. Each such objective function incurs different tradeoffs in terms of speed, accuracy, and the strength of results that can be formally proven, and as a result requires its own optimization methods. In this dissertation, we describe optimization approaches for several performance objectives.

• In a simple abstract memory hierarchy model, we derive an unconditional communication lower bound for "projective" tensor operations (which includes most dense linear algebra) and convolutions. We show that this can always be attained (up to a constant factor) by solving a mathematical optimization problem, and that these methods provide significant benefits in practice, halving the communication volume in one case.

• We extend these lower bound techniques - and corresponding algorithms - to handle combinations of communication and convolution for randomized matrix multiplication.

• We then describe how to incorporate support for additional mapping decisions and to account for more architectural information by extending our optimization-based approach to support analytical performance models. While these performance models are too complex to prove strong lower bounds for, empirical results show that optimization-based methods can find more performant mappings using significantly less runtime and sample complexity than pure search-based methods.

Advisors: James Demmel

---

BibTeX citation:

@phdthesis{Dinh:EECS-2023-293,
    Author= {Dinh, Grace},
    Title= {Optimization-Based Mappers and Lower Bounds for Tensor Problems},
    School= {EECS Department, University of California, Berkeley},
    Year= {2023},
    Month= {Dec},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2023/EECS-2023-293.html},
    Number= {UCB/EECS-2023-293},
    Abstract= {Obtaining good performance for tensor problems requires computing an architecture-specific mapping from the algorithm to the target hardware. Choosing a mapping requires optimizing an objective function over a large, nonconvex space; this objective function represents a performance metric which may be modeled, simulated, or (if possible) measured. Each such objective function incurs different tradeoffs in terms of speed, accuracy, and the strength of results that can be formally proven, and as a result requires its own optimization methods. In this dissertation, we describe optimization approaches for several performance objectives.

• In a simple abstract memory hierarchy model, we derive an unconditional communication lower bound for "projective" tensor operations (which includes most dense linear algebra) and convolutions. We show that this can always be attained (up to a constant factor) by solving a mathematical optimization problem, and that these methods provide significant benefits in practice, halving the communication volume in one case.

• We extend these lower bound techniques - and corresponding algorithms - to handle combinations of communication and convolution for randomized matrix multiplication.

• We then describe how to incorporate support for additional mapping decisions and to account for more architectural information by extending our optimization-based approach to support analytical performance models. While these performance models are too complex to prove strong lower bounds for, empirical results show that optimization-based methods can find more performant mappings using significantly less runtime and sample complexity than pure search-based methods.},
}

EndNote citation:

%0 Thesis
%A Dinh, Grace 
%T Optimization-Based Mappers and Lower Bounds for Tensor Problems
%I EECS Department, University of California, Berkeley
%D 2023
%8 December 22
%@ UCB/EECS-2023-293
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2023/EECS-2023-293.html
%F Dinh:EECS-2023-293