Since the 1990s, many implementations of polyhedral compilers have been written and distributed, either as source-to-source translating compilers or integrated into wider-purpose compilers. This article provides a survey on those various available implementations as of today, 2024. First, we list and describe most commonly available polyhedral schedulers and compiler implementations. Then, we compare the general-purpose polyhedral compilers using two main criteria—robustness and performance—on the PolyBench/C set of benchmarks.

The study of numerical models for the human body has become a major focus of the research community in biology and medicine. For instance, numerical ionic models of a complex organ, such as the heart, must be able to represent individual cells and their interconnections through ionic channels, forming a system with billions of cells, and requiring efficient code to handle such a large system. The modeling of the electrical system of the heart combines a compute-intensive kernel that calculates the intensity of current flowing through cell membranes, and feeds a linear solver for computing the electrical potential of each cell.

Modern computers keep following the traditional model of addressing memory linearly for their main memory and out-of-core storage. While this model allows efficient row access to row-major 2D matrices, it introduces complexity to perform efficient column access. A common strategy to improve these accesses is to transpose or rotate the matrix beforehand, thus the accessing complexity is centralized in one transformation operation. Further column accesses are performed as row accesses to the transposed matrix therefore they are optimized to the memory model. In this article, we propose an efficient solution to perform in-memory or out-of-core rectangular matrix transposition and rotation by using an out-of-place strategy, reading a matrix from an input file and writing the transformed matrix to another (output) file. An originality of our processing algorithm is to rely on an optimized use of the page cache mechanism. It is parallel, optimized by several levels of tiling and independent of any disk block size. We evaluate our approach on five common storage configurations: HDD, hybrid HDD-SSD, SSD, software RAID 0 of several SSDs, and NVMe. We show that it brings significant performance improvement over a hand-tuned optimized reference implementation developed by the Caldera company and we confront it against the baseline speed of a straight file copy.

Nowadays best performing automatic parallelizers and data locality optimizers for static control programs rely on the polyhedral model. Polyhedral compilation consists of three phases: (1) abstracting the input code into a mathematical view; (2) analyzing and transforming this representation into an optimized alternative; (3) generating the corresponding code while ensuring it is semantically equivalent to the input code. During this last phase, state-of-the-art polyhedral compilers generate only one type of parallelism when targeting multicore shared memory architectures: parallel loops via the OpenMP omp parallel for directive. In this work, we propose to explore how a polyhedral compiler could exploit parallel region constructs. Instead of initializing a new set of threads each time the code enters a parallel loop and synchronizing them when exiting it, the threads are initialized once for all at the entrance of the region of interest, and synchronized only when it is necessary. Technically, we propose to embed the whole region containing parallel loops in an omp parallel construct. Inside the parallel region, the single construct is used when some code needs to be executed sequentially; the for construct is used to distribute loop iterations between threads. Thanks to the power of the polyhedral dependence analysis, we compute when it is valid to add the optional nowait clause, to omit the implicit barrier at the end of a worksharing construct and thus to reduce even more control overhead. Through a set of experiments on the PolyBench benchmarks, we show that resulting codes can overwhelm the performance obtained by the Pluto polyhedral compiler.

Over the past few years, multicore systems have become increasingly powerful and thereby very useful in high-performance computing. However, many applications, such as some linear algebra algorithms, still cannot take full advantage of these systems. This is mainly due to the shortage of optimization techniques dealing with irregular control structures. In particular, the well-known polyhedral model fails to optimize loop nests whose bounds and/or array references are not affine functions. This is more likely to occur when handling sparse matrices in their packed formats. In this article, we propose using 2d-packed layouts and simple affine transformations to enable optimization of triangular and banded matrix operations. The benefit of our proposal is shown through an experimental study over a set of linear algebra benchmarks.

It is often hard to predict the performance of a statically generated code. Hardware availability, hardware specification and problem size may change from one execution context to another. The main contribution of this work is an entirely automatic method aiming to predict execution times of semantically equivalent versions of affine loop nests on GPUs, then, to run the best performing one on GPU or CPU. To make accurate predictions, our framework relies on three consecutive stages: a static code generation, an offline profiling and an online prediction. Different versions are statically generated by PPCG, a source-to-source polyhedral compiler, able to generate CUDA code from static control loops written in C. The code versions differ by their block sizes, tiling and parallel schedule. The profiling code carries out the required measurements on the target machine: throughput between host and device memory, and execution time of the kernels with various parameters. At runtime, we rely on those results to calculate a predicted execution time on GPU. This is followed by a "fastest wins" algorithm, that runs instances of the target code concurrently on CPU and GPU, the first completed kills the other one. We validate this proposal on the polyhedral benchmark suite, showing that the predictions are accurate and that the runtime selection is effective on two different architectures.

In this paper, we present a Thread-Level Speculation (TLS) framework whose main feature is to be able to speculatively parallelize a sequential loop nest in various ways, by re-scheduling its iterations. The transformation to be applied is selected at runtime with the goal of minimizing the number of rollbacks and maximizing performance. We perform code transformations by applying the polyhedral model that we adapted for speculative and runtime code parallelization. For this purpose, we design a parallel code pattern which is patched by our runtime system according to the profiling information collected on some execution samples. Adaptability is ensured by considering chunks of code of various sizes, that are launched successively, each of which being parallelized in a different manner, or run sequentially, depending on the currently observed behavior for accessing memory.

The polyhedral model is a well-known compiler optimization framework for the analysis and transformation of affine loop nests. We present a new method to solve a difficult geometric operation that is raised by this model: the integer affine transformation of parametric ℤ-polytopes. The result of such a transformation is given by a worst-case exponential union of ℤ-polytopes. We also propose a polynomial algorithm (for fixed dimension), to count points in arbitrary unions of a fixed number of parametric ℤ-polytopes. We implemented these algorithms and compared them to other existing algorithms, for a set of applications to loop nest analysis and optimization.

Runtime code analysis and optimization is becoming a main strategy used to face the ever extending and changing variety of processor architectures and execution environments that an application can meet. Particularly with the advent of multicore processors, efficient program optimizations, such as adaptive and speculative parallelism, require accurate and advanced runtime analyses, which inevitably incur a time overhead that has to be minimized. In this paper, we present VMAD, a virtual machine (VM) that handles x86_54 binary files, which are especially tailored at compile time to include instructions and data for code instrumentation and for the VM. VMAD enables low level profiling initiated by the programmer from the source code, through the insertion of a dedicated pragma delimiting the regions of interest. This approach provides the programmer a direct view of the actual execution behavior of the source code. To our knowledge, VMAD is the first proposal providing low-level instrumentation initiated from the source code, with almost negligible runtime overhead.

Memory size reduction and memory accesses optimization are crucial issues for embedded systems. In the context of affine programs, these two challenges are classically tackled by array linearization, cache access optimization and memory size computation. Their formalization in the polyhedral model reduce to solving the following problem: count the number of solutions of a Presburger formula. In this paper we propose a novel algorithm that answers this question. We solve the Presburger formula whose solution is a union of parametric Z-polytopes and we propose an algorithm to count points in such a union of parametric Z-polytopes. These algorithms were implemented and we compare them to other existing methods.

Many optimization techniques, including several targeted specifically at embedded systems, depend on the ability to calculate the number of elements that satisfy certain conditions. If these conditions can be represented by linear constraints, then such problems are equivalent to counting the number of integer points in (possibly) parametric polytopes. It is well known that this parametric count can be represented by a set of Ehrhart polynomials. Previously, interpolation was used to obtain these polynomials, but this technique has several disadvantages. Its worst-case computation time for a single Ehrhart polynomial is exponential in the input size, even for fixed dimensions. The worst-case size of such an Ehrhart polynomial (measured in bits needed to represent the polynomial) is also exponential in the input size. Under certain conditions this technique even fails to produce a solution.Our main contribution is a novel method for calculating Ehrhart polynomials analytically. It extends an existing method, based on Barvinok's decomposition, for counting the number of integer points in a non-parametric polytope. Our technique always produces a solution and computes polynomially-sized Ehrhart polynomials in polynomial time (for fixed dimensions).

In the area of automatic parallelization of programs, analyzing and transforming loop nests with parametric affine loop bounds requires fundamental mathematical results. The most common geometrical model of iteration spaces, called the polytope model, is based on mathematics dealing with convex and discrete geometry, linear programming, combinatorics and geometry of numbers. In this paper, we present an automatic method for computing the number of integer points contained in a convex polytope or in a union of convex polytopes. The procedure consists of first, computing the parametric vertices of a polytope defined by a set of parametric linear constraints, and then computing the Ehrhart polynomial, i.e. a parametric expression of the number of integer points. The paper is illustrated with the computation of the maximum available parallelism of a given loop nest.