<figure><img src="image_1.png" /></figure>

<figure><img src="image_2.png" /></figure>

Assessment of the
Effectiveness of
ML-based Performance Models
for Compiler Optimization

Fabrice Rastello

INRIA and UGA

Fabrice.rastello@inria.fr
Once upon a time...

<figure><img src="image_3.png" /></figure>

There was a poor compiler guy. Working hard. No time for coffee
No much outcome.

...Till he saw an apparition
Introduction

<figure><img src="image_4.png" /></figure>

ML will make him rich!

He will use his compiler expertise to optimize ML

And come talk at C4ML...
Introduction

<figure><img src="image_5.png" /></figure>

Still working hard. No time to drink coffee...
And did not work that well (can't come to C4ML)
...So he decided ML would do the job for him
Introduction

<figure><img src="image_6.png" /></figure>

He drinks coffee...

Came to C4ML to advocate changing the name to ML4CC4ML
# Introduction. Layout

<figure><img src="image_7.png" /></figure>

## Part 1: Advocate the change of name from C4ML to ML4CC4ML

- Classical compiler approach (roofline model based « one-shot »)

- Througput model

- Operational intensity model

- Evaluation

## Part 2: Precise what mean by ML

- General infrastructure. Main pillars

- Ansor as a starting point. Raised questions

- Illustration through experiments
# Part 1. Approach

<figure><img src="image_8.png" /></figure>

* Lesson from Ansor: Can exploit specific pattern of deep learning computation kernels + specific tile sizes

* Expertize in low level + data movement: Should be piece of cake
  ⇒ Use roofline model approach.

* **peak perf** == throughput model (Intel IACA)

* **OI** == analytically derived (polyhedral model)

<figure><img src="image_9.png" /></figure>
# Part 1. Approach

<figure><img src="image_10.png" /></figure>

* Lesson from Ansor: Can exploit specific pattern of deep learning computation kernels + specific tile sizes

* Expertize in low level + data movement: Should be piece of cake
  ⇒ Use roofline model approach.

* **peak perf** == throughput model (Intel IACA)

* **OI** == analytically derived (polyhedral model)

<figure><img src="image_11.png" /></figure>
# Part 1. Approach

<figure><img src="image_12.png" /></figure>

* Lesson from Ansor: Can exploit specific pattern of deep learning computation kernels + specific tile sizes

* Expertize in low level + data movement: Should be piece of cake
  ⇒ Use roofline model approach.

* **peak perf** == throughput model (Intel IACA)

* **OI** == analytically derived (polyhedral model)

<figure><img src="image_13.png" /></figure>
# Part 1. Throughput model

<figure><img src="image_14.png" /></figure>

* Basic block. Infinite loop around. L1 resident accesses.
⇒ Predict number of cycles per iterations

* Several approaches:

* Behavioral model (Intel IACA, uICA, LLVM-MCA)

* Context free measure model (BHive)

* Learned model (Ithemal, Granite)

* Behavioral+learned model (GUS, PALMED++)
# Part 1. OI model

<figure><img src="image_15.png" /></figure>

* Affine loop body. Simplified cache model (fully associative).
  ⇒ Approximate the ratio: #ComputedFlops / #MovedBytes

1. Compute footprint for every tile/loop level (Barvinok)

2. Find loop level that saturates given cache level.

3. Assume full reuse of overlapping data between consecutive tiles of surrounding loop.

4. Derive analytical formula (multivariate polynomial)
# Part 1. Evaluation. Throughput

<figure><img src="image_16.png" /></figure>

* Benchmarking:

* Innermost loop: Polybench. Loop transformations

* L1 resident loops only

* GCC with many compiler options

* Skylake

<figure><img src="image_17.png" /></figure>
# Part 1. Evaluation. Throughput

<figure><img src="image_18.png" /></figure>

* Precision of % peak perf estimation for uICA:

* Estimated IPC

* Dynamic analysis to normalize to Flop per iteration

* Manual analysis to normalize to peak perf

⇒ Mostly over estimated

⇒ Cannot be used for « one-shot »

⇒ Empirically select micro-kernels such that perf > 0.85 x machine peak perf

<figure><img src="image_19.png" /></figure>
# Part 1. Evaluation. OI

<figure><img src="image_20.png" /></figure>

* Precision of OI as performance predictor

* MobilNet_2 (did for many others)

* Randomized tiling variants (with selected micro-kernels)

* For each variant:

* Compute operational intensity. Normalize to % of peak perf using actual machine bandwidth (green diagonal)

* Measure actual perf. Normalize to % of peak perf

* Scatter plot: normalized OI (x-axis) versus; normalized perf (y-axis)
    ⇒ Can't be used for « one-shot »

<figure><img src="image_21.png" /></figure>
## Part 2. General infrastructure.

<figure><img src="image_22.png" /></figure>

<figure><img src="image_23.png" /></figure>

* **Main pillars:**

* Expertise (search space, neighbourhood, prior distribution...)

* Learning (prediction, uncertainty)

* Exploitation (to find the best)

* Exploration (to improve our knowledge)
## Part 2. Ansor (simplified).

<figure><img src="image_24.png" /></figure>

<figure><img src="image_25.png" /></figure>

### Remarks/Questions:

* Good because of high expertise?

* Exploration only due to randomization (model that overfits)?

* Role of model?

* Would a model of uncertainty help?
# Part 2. Discussion: Expertise

* Performance distribution on search space w/o vectorization imposed.

⇒ 50 measures: 20% faster

⇒ Performance distribution on search space matters!

<figure><img src="image_26.png" /></figure>

<figure><img src="image_27.png" /></figure>

No vectorization
constraint

<figure><img src="image_28.png" /></figure>

With vectorization
constraint

<figure><img src="image_29.png" /></figure>

Best solution so far
# Part 2. Discussion: Expertise

* Neighborhood / prior on distance (Euclidian vs Hamming)

* Distance (x-axis) and performance (y-axis)

⇒ No correlation with naive Euclidian distance

<figure><img src="image_30.png" /></figure>

Distance correlation between input dx and target dY for euclidean input metric (p=10%)

<figure><img src="image_31.png" /></figure>

Euclidian distance

Distance correlation between input dx and target dY for hamming input metric (p=20%)

<figure><img src="image_32.png" /></figure>

Hamming distance
# Part 2. Discussion. Explore/exploite

<figure><img src="image_33.png" /></figure>

**Exploration/exploitation:** prediction model & uncertainty model

1. Pure random: no model (**naive** exploration)

2. Random walk **from best**: (exploration from initial sampling; local exploration from random walk; exploitation by starting from the best)

3. Walk driven by **prediction** model (RF, XGB): idem but exploits the model

4. Walk driven by prediction+**uncertainty** model (RF, GP): better exploration

<figure><img src="image_34.png" /></figure>
# Part 2. Discussion. Explore/exploit

<figure><img src="image_35.png" /></figure>

**Exploration/exploitation:** prediction model & uncertainty model

1. Pure random: no model (**naive** exploration)

2. Random walk **from best**: (exploration from initial sampling; local exploration from random walk; exploitation by starting from the best)

3. Walk driven by **prediction** model (RF, XGB): idem but exploits the model

4. Walk driven by prediction+**uncertainty** model (RF, GP): better exploration

<figure><img src="image_36.png" /></figure>
# Conclusion.

<figure><img src="image_37.png" /></figure>

## Concluding remarks:

* Sequential optimization seems great! We need compiler infrastructure to allow for « transactional partial lowering & execution ». Possible in MLIR?

* Expertize is crucial. Hardness is not due to size of space but to distribution of performance and « smoothness »

* Hyperparameters for trading exploration/exploitation is challenging (more than actual precision of model)

## Did not talk (but have some idea):

* Do not evaluate precision of a model (MSE & Kendall tau) but evaluate its ability to take good decisions (precision, recall as a function of targeted performance)

* Expose improvement of optimizer as a Pareto normalized to pure random

* Multi-armed bandit is a different objective

* Generalizing to optimizing the full graph on multi-accelerators with distributed memory is challenging
## References.

<figure><img src="image_38.png" /></figure>

**Thanks to:**

* Christophe Guillon, Hugo Pompougnac, Guillaume Iooss, Mariana Vargas Vieira, P. Sadayappan, Albert Cohen, DALL.E

**References:**

* Assessment of the Effectiveness of ML-based Performance Models for Compiler Optimization. arXiv 2024 (to appear)

* Performance bottlenecks detection through microarchitectural sensitivity. arXiv 2024

* CesASMe and Staticdeps: static detection of memory-carried dependencies for code analyzers. arXiv 2024

* Autotuning Convolutions Is Easier Than You Think. ACM TACO 2023

* PALMED: Throughput Characterization for Superscalar Architectures. CGO 2022

* IOOpt: automatic derivation of I/O complexity bounds for affine programs. PLDI 2021

* Analytical cache modeling and tilesize optimization for tensor contractions. SC 2019