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

HAL
open science

Automatic Multi-Versioning of Computation Kernels

Raphaël Colin

► To cite this version:

Raphaël Colin. Automatic Multi-Versioning of Computation Kernels. Conférence francophone d'informatique en Parallélisme, Architecture et Système (COMPAS 2025), Jun 2025, Bordeaux, France. hal-05128992

HAL Id: hal-05128992

https://hal.science/hal-05128992v1

Submitted on 25 Jun 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

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

Distributed under a Creative Commons Attribution 4.0 International License
# Automatic Multi-Versioning of Computation Kernels

Raphaël Colin

Inria,
ICube Laboratory - Pôle API - 300 Bd Sébastien Brant
67400 Illkirch-Graffenstaden - France
raphael.colin@inria.fr

## Abstract

Program optimization is crucial for scientific programs that can run for several days or even weeks. Generating code tailored for a specific target architecture is key to exploiting the hardware with maximum efficiency, both in terms of performance and energy savings, allowing more precise and complete experiments to be run in a shorter time while consuming less energy. Generalist optimization tools have become better over the years, enabling automatic generation of efficient machine code. These tools aim to achieve good performance on average across a range of different programs, and are thus missing optimization decisions that may be beneficial for specific programs, or runs of a program with a given input data. Approaches such as multi-versioning or iterative compilation aim to specialize optimizations to specific programs and input data, but are hard to put into practice, and often only rely on static information for generating code. Our approach aims to leverage knowledge from the execution contexts of a program to derive optimization strategies tailored to these specific execution contexts, and to automatically generate code using known techniques such as polyhedral loop transformations.

**Keywords:** Multi-Versioning, Optimization, Polyhedral Model, Compilation, Runtime Analysis

## 1. Introduction

Scientific software such as numerical simulation programs are energy and time-consuming applications, often deployed on a huge number of compute nodes which are themselves multi-core parallel machines. It is crucial to optimize these applications in order to make their use of computational resources as efficient as possible, both in terms of execution time and energy consumption. Currently, in order to optimize such applications, expert developers can spend time manually optimizing the code. This process is very time consuming, error-prone, and requires expert understanding of the code, the scientific field, and the target architecture. Generalist and specialized compilers are also able to produce high-quality optimized code automatically. In both cases (manual and automatic), optimization choices have to be made, and they are made ahead of execution: either at development-time or at compile-time. Making optimization decisions at this time means that they are based on assumptions made before execution. Such assumptions are not always accurate, and the resulting optimization choices are almost guaranteed to be sub-optimal with regard to the actual behavior of the program during execution. During a run, the program's behavior can also change, for example if multiple
different inputs are being used during a single run, or if the program goes through multiple different execution phases [15]. To address this issue, we propose a new *multi-versioning* approach that uses information available during the execution to drive optimization decisions, and generates versions tailored to specific execution contexts using the polyhedral model. In Section 2, we present multi-versioning and define the concepts of *versions* and *execution context*. In Section 3, an overview of the polyhedral model is given before the design of our new multi-versioning system is presented in Section 4. The system implementation is at a very early stage and unstable for now, thus, no performance results are presented in this paper. Section 5 details the implementation choices made for the system, and Section 6 presents related work. Finally, Section 7 concludes and outlines ideas for future work.

## 2. Multi-Versioning

*Multi-versioning* [4, 9, 11, 16, 10, 5, 1] is an optimization technique that aims to exploit the fact that different versions of a piece of code, or different configurations of a library or runtime system will not show the same performance depending on various conditions in the execution of the program (input data, available hardware, state of the cache, etc.). In this work, we will consider multi-versioning of computation kernels, since they are critical sections of scientific workloads and are thus crucial to optimize. We consider for simplicity that computation kernels are implemented as functions, and that *versions* of a function are functions which do the same work as the original, but are written or optimized differently. They are sometimes called *variants*. For example, a set of different compilers can generate different executables, corresponding to different code variants or versions. A multi-versioning algorithm will attempt to select the best performing version available given certain conditions about the state of the execution.

Section 2.1 will define the notion of *execution context*, then, Section 2.2 will detail how versions can be generated.

### 2.1. Execution Context

In the context of this work, we will call *execution context* the state of execution of a program at a given moment. This state is defined by various parameters (referred to as *context parameters*). Context parameters include but are not limited to: hardware parameters such as the number of available accelerators, the CPU architecture or cache characteristics; as well as software parameters such as function input parameters, state of global variables or the system configuration. A lot of context parameters may be considered, but in order to reason about context, it is necessary to choose a subset of parameters to focus on.

### 2.2. Version Generation

In order to start selecting optimal code versions based on context, it is first necessary to generate such code versions. The generation of various code versions can be done manually, for example by having the developer write multiple variants designed to solve the same problem [13], or by having them optimize the function by hand in different ways. Once these different functions are available, a multi-versioning system could run them and figure out which versions are best for which execution context.

This manual approach however, presents multiple drawbacks: it is cumbersome and time consuming to write all these different versions by hand; some problems do not always have multiple different algorithms that are more or less efficient depending on context; and transforming code by hand can be error-prone, potentially making some versions invalid regarding the se-
semantics of the original code.

Another approach is one based on automatic optimization tools. Such tools exist in general purpose compilers in the form of optimization passes, or exist as standalone programs that are generally designed for specific optimizations. Such automatic optimizations are usually correct in the sense that they do not alter the semantics of the original code. These optimizations can also be configured, each different configuration potentially resulting in a different optimized code, meaning, different versions. For this work, since we are targeting scientific computation kernels which spend the vast majority of their execution time executing loops, we decide to focus on the polyhedral model for version generation.

# 3. Polyhedral Model

## 3.1. Overview

The *polyhedral model* is a mathematical model for representing loop nests. It represents the iteration domain of a loop nest as an n-dimensional polyhedra, where n is the number of nested loops in the target nest. The polyhedral model is only capable of handling specific types of loop nests, called *affine* loop nests. In an affine loop nest, loop bounds and array access expressions are all linear combinations of the indices of the enclosing loops. Some scientific kernels do contain affine loop nests, but a lot of others can contain code which does not fit the criteria for being affine (for example, they can have pointer accesses, or external function calls).

The polyhedral model [6, 2] also models data dependencies between iterations, which means that it can apply loop transformations while ensuring that such data dependencies are not broken, thus preserving the semantics of the original loop nest.

## 3.2. Polyhedral Tools

Multiple automatic tools make use of the polyhedral model in order to optimize loop nests. Examples of such tools are: *Polly* [7], which is integrated in the *LLVM* compiler; *Graphite* [14], which is integrated in the *GCC* compiler; or *Pluto* [2], which is a source-to-source polyhedral optimizer. A tool we are particularly interested in in the context of this work is *Apollo* [3].

Apollo is a compiler based on *clang* which is able to mitigate some of the limitations of classical polyhedral tools. It does so with the help of code instrumentation and runtime analysis. Apollo can analyze the memory access patterns of loops in a program as it is running, in order to build a prediction model for future memory accesses. This prediction model can then be used to compute polyhedral optimizations on a code that could not be handled by static polyhedral tools. Apollo builds the polyhedral representation on its own, and then calls Pluto in order to compute a transformation. Since Pluto can be configured with different flags to control its optimization choices, it can be used in the context of this work to generate different versions for the target kernels. Apollo also relies on the *LLVM* just-in-time compiler, which calls various optimization passes on the code, enabling other opportunities for version generation.

# 4. Multi-Versioning System Design

The Apollo tool presented in Section 3.2 already includes a simple multi-versioning strategy [9]: it works by trying out new Pluto configurations each time the same loop nest is executed, measuring the performance of each configuration, and then always choosing the best performing version on subsequent calls. This system is a first step, but is limited in some ways: it can spend time computing a transformation for an execution context which might never appear later during execution and it does not leverage information present in the execution context
<figure><img src="image_3.png" /><figcaption>Figure 1: Design of the multi-versioning system.</figcaption></figure>

for choosing better transformations. Essentially, the Pluto configurations to be tested are taken
from a fixed set of configurations that is determined before runtime.

This is why we propose a new multi-versioning system. This new system is made of multiple phases, as shown in Figure 1.

The system first needs to instrument the target functions in order to create entry-points for the runtime. Once the program starts, the system enters a first phase of context collection: registering the values of context parameters each time a target function is called. It then moves on to an analysis phase, where each context parameter is checked to see whether they are a constant, if they evolve in a predictable way, or if they intervene in important parts of the target function (in places such as loop bounds for example). The extracted information is then used to optimize the code in different ways, for example by doing function specialization, searching for an optimal tile size or unroll factor, or by inserting software prefetching instructions. The current implementation is a work in progress, where only tile size selection is implemented. For a concrete example of how varying tile sizes and loop unroll factors can generate multiple different code versions, see Appendix A.

Once the different versions are generated, they are evaluated and associated with a certain ex-
ecution context, so that next time this specific execution context reappears, the best found ver-
sion for this specific context can be directly executed. The whole process can then be restarted
from the first phase in order to catch new execution contexts that might be different from pre-
vious ones.

With this method, execution contexts are first analyzed to see if it is relevant to spend time gen-
erating and evaluating optimized versions tailored for these contexts. The information gath-
ered from execution contexts can then be used to choose configurations to be tested, instead
of always testing from a list of predetermined configurations. Version generation and evalua-
tion can also be done separately from the execution of the original code. This also makes the
version generation independent of calls to the original function: time can be spent looking for
an optimized version, even during an execution phase that does not call the original function
for a long time, so that once the original code starts executing the target function again, new
optimized versions might already have been generated and evaluated.

**4.1. Dedicating Resources to Multi-Versioning**

Generating and evaluating versions separately from the original code can also allow the multi-versioning system to take advantage of resources that are usually unclaimed by the original program. Using a greater number of computation units for a parallel computation does not
always lead to better performance, and there is usually a point at which performance starts to degrade, and where adding more parallel processing units is not as efficient as before. These resources can therefore be used by the multi-versioning system to generate and evaluate new code versions in parallel, potentially resulting in better optimized and more efficient code in the long run. The number of processing units dedicated to this task then becomes a meta-optimization parameter that has to be selected, either manually or automatically. Some programs can also have back-up phases doing heavy I/O operations. In this case, much of the processing resources could be idle, making them available to the multi-versioning system.

# 5. Implementation

The implementation of the multi-versioning system is incomplete for now: context analysis is limited to function parameters, with loop tiling being the only optimization used for multi-versioning (for tile size selection). Nonetheless, key points of the current implementation are presented in the current section.

## 5.1. Apollo

The implementation of the new system is done in Apollo, as this tool already contains useful utilities for instrumenting code with LLVM optimization passes and for modifying the execution during runtime by using just-in-time compilation. Apollo also has utilities for building prediction models for memory accesses which can be re-purposed to predict the evolution of context parameters. For example, if some parts of the execution context seem to evolve linearly, or in another predictable way, it is possible to generate an optimized version tailored to this potential future context. Once this execution context appears during normal execution, the optimized version can be used directly. This idea can result in high overhead, but this overhead can be mitigated by using processing resources that are normally unused by the application, or by strategically generating versions during advantageous execution phases.

## 5.2. User Interface

In order to enable multi-versioning for target functions, the user simply has to insert a pragma apollo kernel directive above the function. Optionally, the function body can contain a pragma apollo dcop directive telling Apollo to optimize a loop inside the function like shown in Listing 1. Having the dcop directive allows the multi-versioning system to use polyhedral transformations for version generation by using Apollo and Pluto.

```c
#pragma apollo kernel
void computation_kernel(/* ... */)
{
    #pragma apollo dcop
    for (/* ... */)
    {
        /* ... */
    }
}
```

<caption>Listing 1: Example use of pragma directives on a computation kernel.</caption>

## 5.3. Implementation Details

During compilation, multiple steps have to be taken in order to allow the runtime to take over during the execution of the code. Hook functions have to be inserted inside the original code to call the multi-versioning runtime. In order to transfer some context parameters such as function parameters from the original code to the runtime, wrapper functions also have to be generated. This is due to the fact that the runtime cannot know the signature of the target functions in advance, but it needs to have access to a function with a known signature to be
able to make a call. Two wrapper functions are generated at compile time: a *collection wrapper* and a *call wrapper*.

### 5.3.1. Collection Wrapper

This wrapper function is called at the top of the target function body. It has the exact same signature as the target function, and contains code that packs the input parameter values in a buffer before passing that buffer to the runtime. This allows the runtime to do execution context collection each time the target function is called in the original code.

### 5.3.2. Call Wrapper

This wrapper function essentially does the reverse job of the collection wrapper: it takes a buffer of parameters as an input, and then unpacks these parameters and uses the unpacked values to call the original target function. This allows the runtime to call the target function whenever need, and is used to run the target function during the version generation and evaluation phase.

## 6. Related Work

In [13], the authors present an autotuning framework which is guided by the developer: the *features* used to characterize the execution context are defined by the user instead of being automatically collected and analyzed. The framework uses machine learning in order to select pre-existing code variants instead of generating variants automatically. In [10], machine learning is also used to select code variants, but in this case, the multi-versioning system is specifically focused on the OpenMP *metadirective* directive. Features are also selected by the user, and the version selection is essentially limited to the decision to run a parallel loop on CPU or GPU. Another tool coincidentally named *Apollo* is presented in [1]. This tool automatically selects configuration parameters for kernels expressed using *RAJA* [8], while our multi-versioning system can be applied to normal C or C++ loop nests. The rewrite-rule systems of functional languages are leveraged in [12] to generate optimized versions of parallel codes which are then selected dynamically according to characteristics of the execution context, assuming the execution context fits some constraints.

## 7. Conclusion

In this paper, we have made the case for more adaptive optimization choices tailored to specific execution contexts in scientific codes. We argue that observing the values of various parameters during the execution of a performance-critical section of code (called a computation kernel) can help choose better optimization parameters than those chosen statically by developers or classical optimization tools. We have proposed multi-versioning as a way to address this lack of context-aware optimizations, and propose a new multi-versioning system. This system is implemented in the existing speculative polyhedral compiler Apollo, and leverages the power of the polyhedral model in order to generate optimized code versions specific to execution contexts. In the future, this work could be extended to do multi-versioning on GPU kernels, since more and more scientific workloads are being offloaded to GPUs. This work has focused on execution time as a performance metric, but an interesting subject for future work might be to use multi-versioning as a means to reduce the energy consumption of scientific programs.
Acknowledgment

As part of the "France 2030" initiative, this work has benefited from a national grant managed by the French National Research Agency (Agence Nationale de la Recherche) attributed to the Exa-Soft project of the NumPEx PEPR program, under the reference ANR-22-EXNU-0003.

Bibliography

1. Beckingsale (D.), Pearce (O.), Laguna (I.) et Gamblin (T.). – Apollo: Reusable Models for Fast, Dynamic Tuning of Input-Dependent Code. – In *2017 IEEE International Parallel and Distributed Processing Symposium (IPDPS)*, pp. 307–316, Orlando, FL, USA, mai 2017. IEEE.

2. Bondhugula (U.), Hartono (A.), Ramanujam (J.) et Sadayappan (P.). – A practical automatic polyhedral parallelizer and locality optimizer. – In *Proceedings of the 29th ACM SIGPLAN Conference on Programming Language Design and Implementation*, pp. 101–113, Tucson AZ USA, juin 2008. ACM.

3. Caamaño (J. M. M.), Sukumaran-Rajam (A.), Baloian (A.), Selva (M.) et Clauss (P.). – APOLLO: Automatic speculative POLyhedral Loop Optimizer. – p. 8, janvier 2017.

4. Chen (X.) et Long (S.). – Adaptive Multi-versioning for OpenMP Parallelization via Machine Learning. – In *2009 15th International Conference on Parallel and Distributed Systems*, pp. 907–912, décembre 2009. – ISSN: 1521-9097.

5. Diniz (P. C.) et Rinard (M. C.). – Dynamic feedback: an effective technique for adaptive computing. – In *Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, PLDI '97*, PLDI '97, pp. 71–84, New York, NY, USA, mai 1997. Association for Computing Machinery.

6. Feautrier (P.) et Lengauer (C.). – Polyhedron Model. In: *Encyclopedia of Parallel Computing*, éd. par Padua (D.), pp. 1581–1592. – Boston, MA, Springer US, 2011.

7. Grosser (T.), Groesslinger (A.) et Lengauer (C.). – Polly – Performing Polyhedral Optimizations on a Low-Level Intermediate Representation. *Parallel Processing Letters*, vol. 22, n 04, décembre 2012, p. 1250010.

8. Hornung (R.) et Keasler (J.). – *The RAJA Portability Layer: Overview and Status*. – Rapport technique nLLNL-TR-661403, 1169830, septembre 2014.

9. Lazcano (R.), Madroñal (D.), Juarez (E.) et Clauss (P.). – Runtime multi-versioning and specialization inside a memoized speculative loop optimizer. – In *Proceedings of the 29th International Conference on Compiler Construction*, pp. 96–107, San Diego CA USA, février 2020. ACM.

10. Liao (C.), Wang (A.), Georgakoudis (G.), de Supinski (B. R.), Yan (Y.), Beckingsale (D.) et Gamblin (T.). – Extending OpenMP for Machine Learning-Driven Adaptation. – In *Accelerator Programming Using Directives: 8th International Workshop, WACCPD 2021, Virtual Event, November 14, 2021, Proceedings*, pp. 49–69, Berlin, Heidelberg, novembre 2021. Springer-Verlag.

11. Luo (L.), Chen (Y.), Wu (C.), Long (S.) et Fursin (G.). – Finding representative sets of optimizations for adaptive multiversioning applications. – In *International Workshop on Statistical and Machine learning approaches to Architectures and compilaTion*, janvier 2009.

12. Munksgaard (P.), Breddam (S. L.), Henriksen (T.), Gieseke (F. C.) et Oancea (C.). – Dataset Sensitive Autotuning of Multi-versioned Code Based on Monotonic Properties: Autotuning in Futhark. In: *Trends in Functional Programming*, éd. par Zsók (V.) et Hughes (J.), pp. 3–23. – Cham, Springer International Publishing, 2021. Series Title: Lecture Notes in Computer Science.
13. Muralidharan (S.), Shantharam (M.), Hall (M.), Garland (M.) et Catanzaro (B.). – Nitro: A Framework for Adaptive Code Variant Tuning. – In *2014 IEEE 28th International Parallel and Distributed Processing Symposium*, pp. 501–512, mai 2014. – ISSN: 1530-2075.

14. Pop (S.), Cohen (A.), Bastoul (C.), Girbal (S.), Silber (G.-A.) et Vasilache (N.). – GRAPHITE: Polyhedral Analyses and Optimizations for GCC. – In *Proceedings of the GCC Developers' Summit 2006*, juin 2006.

15. Sherwood (T.), Perelman (E.), Hamerly (G.) et Calder (B.). – Automatically characterizing large scale program behavior. – In *Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, ASPLOS X, ASPLOS X*, pp. 45–57, New York, NY, USA, octobre 2002. Association for Computing Machinery.

16. Zangerl (P.), Thoman (P.) et Fahringer (T.). – Characterizing Performance and Cache Impacts of Code Multi-versioning on Multicore Architectures. – In *2017 25th Euromicro International Conference on Parallel, Distributed and Network-based Processing (PDP)*, pp. 209–213, mars 2017. – ISSN: 2377-5750.

## A. Matrix multiplication code versions

This section presents some examples of what it looks like to optimize a kernel with different optimization parameters in order to obtain different code versions. The goal is to show on a concrete example how changing optimization parameters can yield different code versions (four versions are shown in this case). The examples are shown on C source code for clarity, but versioning done in Apollo is usually done on the polyhedral representation of the code, or on the intermediate representation (IR). The following source code is presented for illustrative purposes, as the versioned code in Apollo is never represented with C source code in this manner.

The source code was obtained using the Pluto polyhedral compiler for tiling and unrolling. Some code is simplified or skipped, and variable names are changed for legibility.

In the following listings, codes are tiled and values highlighted in **red**, **green** and **cyan** represent the size of tiles in each dimension. Values highlighted in **yellow** represent the unroll factor of unrolled loops.

```
1   for (ii=0; ii<= (N-1) / 32 ); ii++)
2   for (jj=0; jj<= (N-1) / 32 ); jj++)
3   for (kk=0; kk<= (N-1) / 32 ); kk++)
4   for (i=32 *ii; i<=min (N-1, 32 *ii+ (32 -1))); i++)
5   for (j=32 *jj; j<=min (N-1, 32 *jj+ (32 -1))); j++)
6   for (k=32 *kk; k<=min (N-1, 32 *kk+ (32 -1))); k++)
7       Matrix_C[i][j] += Matrix_A[i][k] * Matrix_B[k][j];
```

<caption>Listing A.1: Matrix multiplication code with tiles of size 32x32x32</caption>

```
1   for (ii=0; ii<= (N-1) / 32 ); ii++)
2   for (jj=0; jj<= (N-1) / 64 ); jj++)
3   for (kk=0; kk<= (N-1) / 128 ); kk++)
4   for (i=32 *ii; i<=min (N-1, 32 *ii+ (32 -1))); i++)
```
```c
for (j=64*jj; j<=min(N-1, 64*jj+(64-1)); j++)
    for (k=128*kk; k<=min(N-1, 128*kk+(128-1)); k++)
        Matrix_C[i][j] += Matrix_A[i][k] * Matrix_B[k][j];
```

<caption>Listing A.2: Matrix multiplication code with tiles of size 32x64x128</caption>

```c
for (ii=0; ii<= (N-1) / 64; ii++)
    for (jj=0; jj<= (N-1) / 256; jj++)
        for (kk=0; kk<= (N-1) / 512; kk++)
            for (i=64*ii; i<=min(N-1, 64*ii+(64-1))-(4-1); i+=4)
                for (j=256*jj; j<=min(N-1, 256*jj+(256-1)); j++)
                    for (k=512*kk; k<=min(N-1, 512*kk+(512-1)); k++) {
                        Matrix_C[i][j] += Matrix_A[i][k] * Matrix_B[k][j];
                        Matrix_C[i+1][j] += Matrix_A[i+1][k] * Matrix_B[k][j];
                        Matrix_C[i+2][j] += Matrix_A[i+2][k] * Matrix_B[k][j];
                        Matrix_C[i+3][j] += Matrix_A[i+3][k] * Matrix_B[k][j];
                    }

// Code for handling leftover iterations due to loop
// unrolling is skipped for brevity
```

<caption>Listing A.3: Matrix multiplication code with tiles of size 64x256x512 and a loop unroll factor of 4 on the i loop.</caption>

```c
for (ii=0; ii<= (N-1) / 64; ii++)
    for (jj=0; jj<= (N-1) / 256; jj++)
        for (kk=0; kk<= (N-1) / 512; kk++)
            for (i=64*ii; i<=min(N-1, 64*ii+(64-1))-(8-1); i+=8)
                for (j=256*jj; j<=min(N-1, 256*jj+(256-1)); j++)
                    for (k=512*kk; k<=min(N-1, 512*kk+(512-1)); k++) {
                        Matrix_C[i][j] += Matrix_A[i][k] * Matrix_B[k][j];
                        Matrix_C[i+1][j] += Matrix_A[i+1][k] * Matrix_B[k][j];
                        Matrix_C[i+2][j] += Matrix_A[i+2][k] * Matrix_B[k][j];
                        Matrix_C[i+3][j] += Matrix_A[i+3][k] * Matrix_B[k][j];
                        Matrix_C[i+4][j] += Matrix_A[i+4][k] * Matrix_B[k][j];
                        Matrix_C[i+5][j] += Matrix_A[i+5][k] * Matrix_B[k][j];
                        Matrix_C[i+6][j] += Matrix_A[i+6][k] * Matrix_B[k][j];
                        Matrix_C[i+7][j] += Matrix_A[i+7][k] * Matrix_B[k][j];
                    }

// Code for handling leftover iterations due to loop
// unrolling is skipped for brevity
```

<caption>Listing A.4: Matrix multiplication code with tiles of size 64x256x512 and a loop unroll factor of 8 on the i loop.</caption>