Qubit Mapping is a critical task in Quantum Compilation, as modern Quantum Processing Units (QPUs) are constrained to nearest-neighbor interactions defined by a qubit coupling graph. This compiler pass repairs the connectivity of two-qubit gates whose operands are not adjacent by inserting SWAP gates that move the state of qubits between directly connected qubits. Deciding when to introduce SWAPs while minimizing their count is critical because the error in quantum programs increases exponentially with the circuit latency, measured in number of gates along the critical path of the circuit. Prior work for this problem relied on heuristics and exact methods that partition the circuit into two or more layers, but failed to exploit valuable dependence information in any form.This paper introduces a novel qubit mapping algorithm based on the weight of transitive dependences. The introduced mapper models quantum circuits with affine abstractions, thereby providing the ability to compute transitive dependences. In turn, the newfound information is used to partition circuits by dependence distances and compute, efficiently, distinct weights for each layer. We evaluate the efficiency of our mapper on IBM and Rigetti QPUs, using the large datasets from the QUEKO and QASMBench benchmark suites, and against four baseline tools (QMAP, Sabre, Cirq and TKET), demonstrating notable improvements in circuit depth and swap count while delivering competitive scalability.

Tensor computations are an important class of operations widely used in domains such as computational chemistry, machine learning, and various types of physical simulations that demand distributed-memory clusters. Recent work has shown that generating efficient mappings for multi-operator Directed Acyclic Graphs of distributed-memory tensor computations is possible by leveraging non-linear formulations underpinned by Satisfiability Modulo Theories (SMT) solvers. However, this approach is sensitive to the problem size, grid shape, and count of Processing Elements (PEs) given.

We introduce a two-level scheme to generate GPUaware MPI/NCCL code for distributed tensor computations. Our generator takes the specification of a linearized Directed Acyclic Graph (DAG) of tensor operators and produces a global mapping solution that considers MPI communication (inter and intranode) and the local computation. The core of our generator is a new bit-vector representation that compactly models mappings as well as communication directions along the grid. We incorporate the 2-level mapping decisions into a non-linear formulation which is optimized in an iterative fashion with the Z3 SMT solver. The new mapper supports both NVIDIA NCCL, MVAPICH-gdr, allowing for better portability. We demonstrate the efficiency of our mapping generator on a set of matrix- and tensor- DAGs, on two multi-GPU clusters with NVLink or PCIe intra-node interconnect, and compare against the COSMA library and CTF framework, achieving speedups ranging from 2.6× (over COSMA) to 18× (over CTF).

Distributed-memory programs that use the Message Passing Interface (MPI) often introduce various kinds of correctness anomalies. This work focuses on the type of anomalies detectable through data-flow modeling. We present a new tool and Domain-Specific Language to describe the data-flow of computations based on collective operations, such as the broadcast or all-gather in MPI. Our tool, CollectCall, models key aspects of distributed-memory algorithms, namely the processor space, symbolic communicators, data, its partitioning and mapping, and a set of communication primitives. Using these concepts, we build constraint systems that model the initial data placement and communication steps of the algorithm. Systems are built and solved with the Z3 SMT and the Integer Set Library (ISL) to decide the correctness of sequences of collective operations. We formalize the correctness requirements for a class of collective communication operations, and demonstrate the effectiveness of our approach on several micro-benchmarks and on well-known distributed algorithms from the literature while comparing against ITAC, MPI-Checker and PSE, state-of-the-art tools.

The Fourier transform is an ubiquitous mathematical operation used in a multitude of scientific applications. Most distributed Fourier transform libraries provide rigid implementations that force developers of high performance applications to mold their code around the Fourier computation, omitting opportunities for minimizing communication across the Fourier transforms and the surrounding computation. In this work, we introduce a new automatic approach to generate distributed mappings for multi-dimensional Fourier operations, offering a solution to this problem. Our approach decides how to decompose, map, and schedule the computation as smaller and lower-dimensional parallel operations. We design and implement a novel non-linear iterative formulation that optimizes across Fourier and linear algebra operations. Our scheme leverages the Z3 SMT solver to minimize the number of communication steps across key MPI collectives, while selecting the grid shape. We evaluate the effectiveness of our new scheme and demonstrate 2 × -31 × speedups over coupled heFFTe and COSMA solutions.

Loop tiling is a high-order transformation used to increase data locality and performance. While previous work has considered its application to several domains and architectures, its potential impact on energy efficiency has been largely ignored. In this work, we present an Energy-Aware Tile Size Selection Scheme (EATSS) for affine programs targeting GPUs. We automatically derive non-linear integer formulations for affine programs and use the Z3 solver to find effective tile sizes that meet architectural resource constraints, while maximizing performance and minimizing energy consumption. Our approach builds on the insight that reducing the liveness of in-cache data, together with exploiting automatic power scaling, can lead to substantial gains in performance and energy efficiency. We evaluate EATSS on NVIDIA Xavier and GA100 GPUs, and report median performance-per-Watt improvement relative to PPCG on several affine kernels. On Polybench kernels, we achieve 1.5 × and 1.2 × improvement and obtain up to 6.3 × improvement on non-Polybench high-dimensional affine kernels.

While considerable research has been directed at automatic parallelization for shared-memory platforms, little progress has been made in automatic parallelization schemes for distributed-memory systems. We introduce an innovative approach to automatically produce distributed-memory parallel code for an important subclass of affine tensor computations common to Coupled Cluster (CC) electronic structure methods, neuro-imaging applications, and deep learning models.

This paper introduces QRANE, a tool that produces the affine intermediate representation (IR) from a quantum program expressed in Quantum Assembly language such as OpenQASM. QRANE finds subsets of quantum gates prescribed by the same operation type and linear relationships, and constructs a structured program representation expressed with polyhedral iteration domains and access relations, all while preserving the original semantics of the quantum program. We explore various policies for deciding amongst different delinearization strategies and discuss their effect on the quality of the reconstruction. Our evaluation demonstrates the high coverage and efficiency obtained with QRANE while enabling research on the benefits of affine transformations for large quantum circuits. Specifically, QRANE reconstructs affine iteration domains of up to 6 dimensions and up to 184 points per domain.

Memristive devices promise an alternative approach toward non-Von Neumann architectures, where specific computational tasks are performed within the memory devices. In the machine learning (ML) domain, crossbar arrays of resistive devices have shown great promise for ML inference, as they allow for hardware acceleration of matrix multiplications. But, to enable widespread adoption of these novel architectures, it is critical to have an automatic compilation flow as opposed to relying on a manual mapping of specific kernels on the crossbar arrays. We demonstrate the programmability of memristor-based accelerators using the new compiler design principle of multilevel rewriting, where a hierarchy of abstractions lowers programs level-by-level and perform code transformations at the most suitable abstraction. In particular, we develop a prototype compiler, which progressively lowers a mathematical notation for tensor operations arising in ML workloads, to fixed-function memristor-based hardware blocks.

Loop tiling is a key high-level transformation which is known to maximize locality in loop intensive programs. It has been successfully applied to a number of applications including tensor contractions, iterative stencils and machine learning. This technique has also been extended to a wide variety of computational domains and architectures. The performance achieved with this critical transformation largely depends on a set of inputs given, the tile sizes, due to the complex trade-off between locality and parallelism. This problem is exacerbated in GPGPU architectures due to limited hardware resources such as the available shared-memory.

Despite years of research, the optimization strategy of loop-level optimization frameworks remains fragile when addressing modern and heterogeneous architectures. Furthermore, optimizers act as an opaque operation, a black-box, to the users, forcing them to tedious an error-prone manual optimization if imprecise cost models are used. Current solutions, to drive loop-level optimizers rely on pragmas or bake the transformations recipes in the source code using imperative embedded scripting. But, the optimization of programs via a sequence of imperative directives is unlikely to solve this problem fully as expressing optimization is still an error-prone and time-consuming task for the users. The ideal solution would be a declarative approach that allows the users to opt-in if the optimizer has made a poor optimization decision but avoid baking the transformation script within a given application or bind it to a particular loop nest. Based on such an idea, we propose LoopOpt, an interactive tool that enables users to design optimizations in partnership with the compiler in a declarative way. Thus, our approach opens the polyhedral black-box allowing users to design complex optimizations sequences in a declarative way.

Most quantum compiler transformations and qubit allocation techniques to date are either peep-hole focused or rely on sliding windows that depend on a number of external parameters including the topology of the quantum processor. Thus, global optimization criteria are still lacking. In this article, we explore the synergies and impact of affine loop transformations in the context of qubit allocation and mapping. With this goal in mind, we designed and implemented AXL , a domain specific language and source-to-source compiler for quantum circuits that can be directly described with affine relations. We conduct an extensive evaluation spanning circuits from the recently introduced QUEKO benchmark suite, eight quantum circuits taken from the literature, three distinct coupling graphs, four affine transformations (including the Pluto dependence distance minimization and Feautrier’s minimum latency algorithms), four qubit allocators, and two back-end quantum compilers. Our results demonstrate that affine transformations using global optimization criteria can cooperate effectively in several scenarios with quantum qubit mapping algorithms to reduce the circuit depth, size and allocation time.

To this day, polyhedral optimizing compilers use either extremely rigid (but accurate) cost models, one-size-fits-all general-purpose heuristics, or auto-tuning strategies to traverse and evaluate large optimization spaces. In this paper, we introduce an adaptive and automatic scheduler that permits to generate novel loop transformation sequences (or recipes) capable of delivering strong performance for a variety of different architectures without relying on auto-tuning, nor on pre-determined transformation strategies. We evaluate our approach using the Polybench/C benchmark suite against two modern state-of-the-art optimizers on three different architectures: An AMD ThreadRipper, an Intel Xeon Phi, and an Intel Xeon Platinum. Our results provide evidence that a set of high-level objectives backed up by an automatic adaptive scheduler (i.e., not hard-wired) is capable of achieving competitive performance, while only resorting to evaluating a handful of tuned variants.

We present a novel framework to automatically derive highly efficient parametric multi-way recursive divide&conquer algorithms for a class of dynamic programming (DP) problems. Standard two-way or any fixed R-way recursive divide&conquer algorithms may not fully exploit many-core processors. To run efficiently on a given machine, the value of R may need to be different for every level of recursion based on the number of processors available and the sizes of memory/caches at different levels of the memory hierarchy. The set of R values that work well on a given machine may not work efficiently on another machine with a different set of machine parameters. To improve portability and efficiency, Multi-way Autogen generates parametric multi-way recursive divide&conquer algorithms where the value of R can be changed on the fly for every level of recursion. We present experimental results demonstrating the performance and scalability of the parallel programs produced by our framework.

The massively parallel architecture of GPU accelerators are being harnessed to expedite computational workloads in cutting edge scientific research. Unfortunately writing applications for GPUs requires extensive knowledge of the underlying architecture, the application and the interfacing programming model. Moreover, (re-)writing kernels using lower-level programming models such as CUDA and OpenCL is a burden for application scientists. A more appealing strategy is to leverage a programming model layered on directive-based optimization: OpenMP, whose recent specification significantly extends its accelerator functionalities. Despite this, it is still quite challenging to optimize large scale applications, since “pragmatizing” each kernel is a repetitive and complex task. In large scale applications most of the operations could be small, don't have enough computational work to justify a GPU execution, deeply buried in the library specification, or evenly spread throughout the application. Thus, we seek to design and build a compiler framework that can automatically and profitably offload regions of code with these characteristics. The driving principle of our work resides in generating numerous kernel variants that result from fusing and/or decomposing existing function bodies. We analyze the program's call graph to determine the “proximity” of kernel calls and evaluate the degree of data reuse among adjacent or “close-enough” calls. When such patterns are detected we generate several scenarios, until producing a single variant whose footprint is near the capacity of the GPU. To compare the potential performance among the various kernel variants generated, we are designing an adaptive cost model. The precision of this cost model will depend upon the analyzability of the program. We are also building upon existing cost models like Baghsorkhi et al.'s model which proposed a work flow graph based analytical model and a recent Hong et al.'s model which propose the use of abstract kernel emulations to help identify the performance bottlenecks of a GPU program execution. Along with these we introduce GPU initialization and data transfer cost to the model. Once the profitable kernel variants are detected, we automatically insert pertinent OpenMP directives and provide a newly generated code supporting GPU offloading.

Modern polyhedral compilers excel at aggressively optimizing codes with static control parts, but the state-of-practice to find high-performance polyhedral transformations especially for different hardware targets still largely involves auto-tuning. In this work we propose a novel customizable polyhedral scheduling technique, with the aim of delivering high performance for several hardware targets. We design constraints and objectives that model several crucial aspects of performance such as stride optimization or the trade-off between parallelism and reuse, while considering important architectural features of the target machine. We evaluate our work using the PolyBench/C benchmark suite and experimentally validate it against large optimization spaces generated with the Pluto compiler on 3 representative architectures: an IBM Power9, an Intel Xeon Phi and an Intel Core-i9. Our results show we can achieve comparable or superior performance to Pluto on the majority of benchmarks, without implementing tiling in the source code nor using experimental autotuning.

Applications running on clusters of shared-memory computers are often implemented using OpenMP+MPI. Productivity can be vastly improved using task-based programming, a paradigm where the user expresses the data and control-flow relations between tasks, offering the runtime maximal freedom to place and schedule tasks. While productivity is increased, high-performance execution remains challenging: the implementation of parallel algorithms typically requires specific task placement and communication strategies to reduce internode communications and exploit data locality. In this work, we present a new macro-dataflow programming environment for distributed-memory clusters, based on the Intel Concurrent Collections (CnC) runtime. Our language extensions let the user define virtual topologies, task mappings, task-centric data placement, task and communication scheduling, etc. We introduce a compiler to automatically generate Intel CnC C++ run-time, with key automatic optimizations including task coarsening and coalescing. We experimentally validate our approach on a variety of scientific computations, demonstrating both productivity and performance.

Fully polarimetric Radarsat-2 imagery from wet and dry conditions over the South African Lowveld is compared to assess its value for fuel moisture mapping. Imagery was acquired at two different dates, in May (end of summer, wet) and in August (mid of winter, dry). Sample plots were classified into two broad Lowveld site types (herbaceous-dominated and shrub and tree-dominated). Linear and circular polarized backscatters, polarimetric discriminators and polarimetric decomposition parameters were computed to find suitable parameters for fuel moisture estimation. The results show a significant distinction between wet and dry conditions for C-HH, C-HV, C-RR, and C-LL, all Freeman-Durden and van Zyl decomposition parameters and some polarimetric discriminators (dmin, Prmax, Prmin, Smax, Smin). In almost all cases the normalized difference between wet and dry condition is lower for the shrub and tree-dominated sites. The Freeman-Durden double bounce scattering decomposition parameter performs best in both site types.

The freedom to reorder computations involving associative operators has been widely recognized and exploited in designing parallel algorithms and to a more limited extent in optimizing compilers.

Task-parallel languages are increasingly popular. Many of them provide expressive mechanisms for intertask synchronization. For example, OpenMP 4.0 will integrate data-driven execution semantics derived from the StarSs research language. Compared to the more restrictive data-parallel and fork-join concurrency models, the advanced features being introduced into task-parallel models in turn enable improved scalability through load balancing, memory latency hiding, mitigation of the pressure on memory bandwidth, and, as a side effect, reduced power consumption. In this article, we develop a systematic approach to compile loop nests into concurrent, dynamically constructed graphs of dependent tasks. We propose a simple and effective heuristic that selects the most profitable parallelization idiom for every dependence type and communication pattern. This heuristic enables the extraction of interband parallelism (cross-barrier parallelism) in a number of numerical computations that range from linear algebra to structured grids and image processing. The proposed static analysis and code generation alleviates the burden of a full-blown dependence resolver to track the readiness of tasks at runtime. We evaluate our approach and algorithms in the PPCG compiler, targeting OpenStream, a representative dataflow task-parallel language with explicit intertask dependences and a lightweight runtime. Experimental results demonstrate the effectiveness of the approach.

Data locality and parallelism are critical optimization objectives for performance on modern multi-core machines. Both coarse-grain parallelism (e.g., multi-core) and fine-grain parallelism (e.g., vector SIMD) must be effectively exploited, but despite decades of progress at both ends, current compiler optimization schemes that attempt to address data locality and both kinds of parallelism often fail at one of the three objectives.