Tiramisu: A Polyhedral Compiler for Expressing Fast and Portable Code

Riyadh Baghdadi; Jessica Ray; Malek Ben Romdhane; Emanuele Del Sozzo; Abdurrahman Akkas; Yunming Zhang; Patricia Suriana; Shoaib Kamil; Saman Amarasinghe

Source-linked AI summary

Tiramisu: A Polyhedral Compiler for Expressing Fast and Portable Code

Riyadh Baghdadi, Jessica Ray, Malek Ben Romdhane, Emanuele Del Sozzo, Abdurrahman Akkas, Yunming Zhang, Patricia Suriana, Shoaib Kamil, Saman Amarasinghe

arXiv:1804.10694v5Apr 27, 2018cs.PLcs.DCcs.MScs.NEcs.PF

TL;DR

Generating efficient code across diverse high-performance architectures requires complex transformations, memory management, communication, and synchronization. Tiramisu addresses this with a polyhedral compiler, a fine-grained scheduling language, and a four-layer IR separating algorithmic structure from transformations, layouts, and communication. Across image-processing, deep-learning, and linear-algebra benchmarks, it matches or outperforms state-of-the-art frameworks and hand-tuned code, including up to 2.3× over Intel MKL.

Problem
Modern high-performance architectures make efficient code generation difficult because optimization requires complex transformations, memory-hierarchy management, communication, and synchronization.
Method
Tiramisu is a C++-embedded polyhedral DSL whose scheduling language controls transformations, data layouts, communication, synchronization, and memory hierarchies through a four-layer IR.
Results
Tiramisu matches or outperforms state-of-the-art frameworks and hand-tuned code across multicore CPUs, GPUs, and distributed systems, reaching up to 2.3× over Intel MKL.
Takeaways & Limitations
Separating algorithms from transformations, layouts, and communication supports one architecture-independent algorithm across multiple hardware backends.

Abstract

from arXiv · show

This paper introduces Tiramisu, a polyhedral framework designed to generate high performance code for multiple platforms including multicores, GPUs, and distributed machines. Tiramisu introduces a scheduling language with novel extensions to explicitly manage the complexities that arise when targeting these systems. The framework is designed for the areas of image processing, stencils, linear algebra and deep learning. Tiramisu has two main features: it relies on a flexible representation based on the polyhedral model and it has a rich scheduling language allowing fine-grained control of optimizations. Tiramisu uses a four-level intermediate representation that allows full separation between the algorithms, loop transformations, data layouts, and communication. This separation simplifies targeting multiple hardware architectures with the same algorithm. We evaluate Tiramisu by writing a set of image processing, deep learning, and linear algebra benchmarks and compare them with state-of-the-art compilers and hand-tuned libraries. We show that Tiramisu matches or outperforms existing compilers and libraries on different hardware architectures, including multicore CPUs, GPUs, and distributed machines.

I. INTRODUCTION

Tiramisu addresses the difficulty of generating high-performance code across increasingly diverse architectures with a polyhedral compiler and extensible scheduling language. Its four-layer IR separates algorithms, transformations, data layouts, and communication, while evaluations report competitive performance across CPUs, GPUs, and distributed systems.

Complex architectures require coordinated code and data-layout transformations, memory-hierarchy management, communication, and synchronization to achieve high performance.
Gemm illustrates why automation is difficult: tuned implementations combine fusion, tiling, vectorization, unrolling, packing, register blocking, prefetching, and architecture-specific memory optimizations.
Tiramisu provides scheduling commands for loop and data-layout transformations, explicit communication and synchronization, and mapping buffers across memory hierarchies.
Unlike interval-based Halide, Tiramisu’s polyhedral representation naturally expresses non-rectangular iteration spaces, cyclic data-flow graphs, and affine transformations such as skewing.
Its four-layer intermediate representation separates the algorithm from code and data-layout transformations, simplifying portability and architecture-specific lowering.
2.3×: Tiramisu outperforms Intel MKL by up to this amount on evaluated deep-learning and linear-algebra kernels, while matching or outperforming state-of-the-art compilers across CPUs, GPUs, and distributed machines.

II. RELATED WORK

Related systems provide automatic optimization or user-controlled scheduling, but their representations and scheduling languages leave gaps in distributed execution or expressive affine transformations. Tiramisu combines polyhedral expressiveness with commands for computation partitioning, data distribution, synchronization, and communication.

Polyhedral compilers with automatic scheduling: Fully automatic polyhedral compilers improve productivity but may produce suboptimal performance because they do not always select the best transformations.
Polyhedral compilers with a scheduling language: AlphaZ, CHiLL, and URUK expose scheduling commands and affine transformations, but their scheduling languages do not target distributed architectures.
Polyhedral compilers with a scheduling language: Tiramisu extends polyhedral scheduling with commands for partitioning computations, synchronizing, and distributing data across nodes.
Non-polyhedral compilers with a scheduling language: Halide uses interval-based iteration spaces, limiting natural representation of non-rectangular domains and complex affine transformations such as iteration-space skewing.
Non-polyhedral compilers with a scheduling language: Halide’s conservative dependence handling can prevent legal loop fusion and restrict programs with cyclic data-flow graphs.
Other comparisons: Tiramisu is complementary to higher-order-function frameworks because its polyhedral model expresses complex affine transformations more directly.

A. Scope of TIRAMISU

TIRAMISU targets data-parallel algorithms over dense arrays in image processing, deep learning, linear algebra, tensor, and stencil workloads. Its scheduling commands control loop transformations, hardware mapping, data movement, memory placement, and synchronization across multicore, GPU, and distributed systems.

Scope: TIRAMISU is designed for data-parallel algorithms expressed as loop nests and sequences of statements over dense arrays.Its target areas include image processing, deep learning, dense linear algebra, tensor operations, and stencil computations.
Algorithm specification: TIRAMISU separates pure algorithm specification from loop optimizations, data layout, and communication.The algorithm is represented through computations with explicit iteration domains and expressions, without initially specifying execution order or data location.
Scheduling commands: Scheduling commands cover loop-nest transformations, hardware mapping, data manipulation, and synchronization operations.Examples include tiling, splitting, vectorization, GPU mapping, memory allocation, copying, barriers, and point-to-point communication.
Scheduling commands: TIRAMISU automatically derives iteration domains and copied data regions for allocation, copying, and synchronization operations.This reduces manual computation when users explore different schedules, including memory transfers from global to shared GPU memory.
Target architectures: The same blur computation can be scheduled for multicore CPUs, GPUs, or distributed CPU nodes using architecture-specific commands.Examples use tiling and parallelization for multicore execution, GPU block/thread mapping and shared-memory caching, and distributed loops with border communication.

IV. THE TIRAMISU IR

TIRAMISU’s multi-layer intermediate representation simplifies scheduling-command implementation by applying transformations in a specific order.

The multi-layer IR applies scheduling transformations in a specific order to simplify implementation.

A. Rationale for a Multi-layer IR

Existing intermediate representations and code-generation systems couple memory layout, scheduling, communication, and synchronization decisions, complicating optimization across architectures. TIRAMISU addresses this coupling with a multi-layer polyhedral IR that separates these concerns.

Rationale: Current intermediate representations use memory to communicate between statements, forcing data-layout choices before optimization and hardware mapping.These memory-based dependencies can restrict later optimizations and require layouts to be undone or changed.
Rationale: GPU shared-memory buffering and distributed communication depend on the optimizations applied to the computation.Tiling choices affect copied data regions and synchronization, as do optimization decisions for distributed send and receive operations.
Solution: TIRAMISU separates the architecture-independent algorithm from loop transformations, data layout, communication, and synchronization across four IR layers.The layers successively specify the algorithm, computation order and placement, intermediate-data storage, and communication or synchronization operations.
Solution: Layer separation lets each compiler phase assume that earlier decisions need not be modified or undone.For example, scheduling can proceed without handling concrete data-layout transformations.
Polyhedral representation: TIRAMISU uses integer sets for iteration domains and maps for memory accesses and transformations.These structures are implemented with the Integer Set Library and use affine constraints and relations between integer sets.

C. The Multi-Layer IR

The TIRAMISU IR begins with an unordered, architecture-independent algorithm and progressively adds execution order, processor placement, and lower-level representation details.

Overview: TIRAMISU’s workflow starts from a pure algorithm and scheduling commands, transforms the first IR layer into lower layers, and generates LLVM or other low-level IR.All four layers use integer sets, while maps represent iteration-domain and data-layout transformations.
Layer I (Abstract Algorithm): Layer I specifies computations without fixing execution timing, processor location, memory layout, or communication.Values are connected through explicit producer-consumer relationships.
Layer I (Abstract Algorithm): A Layer I computation combines an affine iteration domain with the expression evaluated over that domain.The blur example defines by over i, j, and c, then computes an average of three bx values.
Layer I (Abstract Algorithm): Layer I computations are unordered; execution order is specified in Layer II rather than by declaration order.

2) Layer II (Computation Management):

Layer II separates computation ordering from processor assignment, using time and space dimensions to control execution across CPUs, GPUs, and distributed systems.

Computation and processor mapping: Layer II specifies computation execution order and processor assignment without determining intermediate data storage.This separation lets scheduling transformations control execution independently from data-layout transformations.
Execution ordering: Lexicographic ordering of computation tuples determines execution order among computations mapped to the same processor.In the GPU example, gpuB tags map i0 and j0 iterations to corresponding GPU blocks.
Computation and processor mapping: Time dimensions determine relative execution order, while space dimensions determine the processor on which each computation runs.Processor types are represented by tags attached to space dimensions.
Processor tags: TIRAMISU supports processor tags for CPUs, distributed nodes, GPU threads, and GPU blocks.A tagged dimension distributes its iterations over processors of the specified type.
Scheduling transformations: Vectorization and unrolling are scheduling transformations applied to loop dimensions.The vec(s) tag vectorizes a dimension with vector length s, while unroll unrolls it.

3) Layer III (Data Management):

Layer III makes data placement concrete by adding affine computation-to-buffer mappings and explicit buffer management to the execution representation.

Data management: Layer III specifies where intermediate values are stored and adds buffer allocation and deallocation operations.It is generated automatically from Layer II using data-mapping scheduling commands.
Data mappings: Data mappings support structures-of-arrays, arrays-of-structures, dimensional contraction, and nontrivial index rearrangements.Examples include mapping c(i,j) to c(i%2,j%2) or transposing storage to c(j,i).
Data mappings: In the GPU example, by.store_in(c,i,j) stores by(i,j,c) in by[c,i,j] after tiled indices are reconstructed.The resulting relation maps the transformed computation coordinates to the concrete buffer element.
Data mappings: TIRAMISU represents data layout as an affine relation mapping each computation to a buffer element.This supports any data-layout mapping expressible as an affine relation.
Transition to communication: Layer III also precedes Layer IV, where synchronization, communication, and memory-copy operations are added and mapped to the time-space domain.Layer IV concretizes when allocation and deallocation operations occur.

V. COMPILER IMPLEMENTATION

TIRAMISU transforms scheduled computations through four IR layers and lowers the final representation into target-specific code for multicore, GPU, and distributed systems.

Overview: The implementation section provides a high-level overview of code generation because introducing new code-generation techniques is not the paper’s main contribution.The authors refer to prior literature for additional implementation details.
IR transformations: Layer I-to-II scheduling combines loop transformations such as tile and interchange with hardware-mapping commands such as parallelize, vectorize, and gpu.The first command type transforms iteration domains, while the second adds processor tags.
IR transformations: Layer II-to-III augments execution with access relations, buffer allocations, and data-placement decisions.The default mapping is identity unless store_in() specifies another access relation.
IR transformations: Layer III-to-IV translates communication, synchronization, and memory-copy scheduling commands into executable statements.send() and receive() become calls later translated into MPI calls during code generation.
Target code generation: Code generation emits nested loops that visit each Layer IV computation exactly once in lexicographic order, using Cloog through ISL.The resulting AST is traversed to produce lower-level target code.
Target code generation: Backends lower the representation to LLVM IR for CPUs, CUDA for GPU kernels, and MPI-based code for distributed systems.GPU tags become thread and block identifiers, while distributed loops are converted into MPI-rank conditionals.

B. Support for Non-Affine Iteration Spaces

TIRAMISU handles non-affine accesses, bounds, and conditionals through conservative representations, then evaluates the compiler across deep learning and linear-algebra benchmarks.

Non-affine iteration spaces: Non-affine accesses, loop bounds, and conditionals are represented using predicates and over-approximated access sets.Conditionals are reinserted during code generation, and the authors report that these approximations do not hamper performance.
Evaluation: The evaluation covers deep learning and linear algebra benchmarks, including Conv, VGG, sgemm, HPCG, and Baryon.Comparisons use Intel MKL except for HPCG and Baryon, which use reference implementations.
Evaluation: 30× repetitions with median execution time were used for experiments on multicore CPUs, GPUs, and distributed systems.The setup included a 16-node cluster, dual-socket 24-core CPUs, and an NVIDIA Tesla K40 GPU.
Benchmark results: TIRAMISU matches Intel MKL performance on sgemm using extensive tiling, vectorization, unrolling, packing, register blocking, and auto-tuning.Separating full and partial tiles was described as crucial for vectorization, unrolling, and reducing control overhead.
Benchmark results: TIRAMISU’s Conv code outperforms Intel MKL by specializing common fixed filter sizes and enabling compile-time unrolling.Specialized filters include 3 × 3, 5 × 5, 7 × 7, 9 × 9, and 11 × 11.
Benchmark results: The VGG implementation achieves a 2.3× speedup over Intel MKL through loop fusion, fixed-size filters, and improved data locality.Baryon speedup comes from vectorization using array expansion and scatter/gather operations.

B. Image Processing Benchmarks

TIRAMISU matches or exceeds competing frameworks across image-processing benchmarks on multicore CPUs, GPUs, and distributed systems. Its advantages arise from precise polyhedral representations and explicit control over fusion, memory, communication, and synchronization.

Evaluation setup: The evaluation covers edgeDetector, cvtColor, conv2D, warpAffine, gaussian, nb, and ticket #2373, comparing TIRAMISU with Halide and PENCIL.
Single-node multicore: TIRAMISU matches Halide on four single-node multicore benchmarks, including cases with non-affine array accesses and conditionals.
Single-node multicore: Halide cannot implement edgeDetector and ticket #2373, while TIRAMISU handles cyclic and triangular iteration domains through its polyhedral representation.Halide’s interval-based representation over-approximates the triangular domain in ticket #2373, causing generated code to fail.
Single-node multicore: 3.77× speedup over Halide is achieved for nb on multicore CPUs through loop fusion enabled by dependence analysis.Fusion improves data locality by combining loops that update the same buffer, a transformation Halide cannot apply in this case.
GPU: On GPUs, TIRAMISU improves conv2D and gaussian using constant memory and achieves 1.7× speedup over Halide for nb through loop fusion.The GPU timings include data-copy and kernel-execution times; copy times are the same for TIRAMISU and Halide in the filter benchmarks.
Distributed: TIRAMISU is faster than distributed Halide in every compared case, reaching 3.25× speedup for conv2D.Explicit send() and receive() commands specify exact communication volumes and avoid unnecessary packing; distributed TIRAMISU also scales across 2, 4, 8, and 16 nodes.

VII. CONCLUSION

TIRAMISU combines a polyhedral compiler with scheduling commands and a four-layer intermediate representation for targeting multicore CPUs, GPUs, and distributed systems. Evaluation shows generated code matching or outperforming state-of-the-art frameworks and hand-tuned code.

TIRAMISU provides scheduling commands for multicore CPUs, GPUs, and distributed systems, with a four-layer IR separating algorithm, computation placement, data layout, and communication.