title: gpucc: an open-source GPGPU compiler

authors:
Jingyue Wu
Artem Belevich
Eli Bendersky
Mark Heffernan
Chris Leary
Jacques A. Pienaar
Bjarke Roune
Rob Springer
Xuetian Weng
Robert Hundt

abstract: Graphics Processing Units have emerged as powerful accelerators for massively parallel, numerically intensive workloads. The two dominant software models for these devices are NVIDIA’s CUDA and the cross-platform OpenCL standard. Until now, there has not been a fully open-source compiler targeting the CUDA environment, hampering general compiler and architecture research and making deployment difficult in datacenter or supercomputer environments. In this paper, we present gpucc, an LLVM-based, fully open-source, CUDA compatible compiler for high performance computing. It performs various general and CUDA-specific optimizations to generate high performance code. The Clang-based frontend supports modern language features such as those in C++11 and C++14. Compile time is 8% faster than NVIDIA’s toolchain (nvcc) and it reduces compile time by up to 2.4x for pathological compilations (>100 secs), which tend to dominate build times in parallel build environments. Compared to nvcc, gpucc’s runtime performance is on par for several open-source benchmarks, such as Rodinia (0.8% faster), SHOC (0.5% slower), or Tensor (3.7% faster). It outperforms nvcc on internal large-scale end-to-end benchmarks by up to 51.0%, with a geometric mean of 22.9%.


venue: cgo

title: Atomicity violation checker for task parallel programs

authors:
Adarsh Yoga
Santosh Nagarakatte

abstract: Task based programming models (e.g., Cilk, Intel TBB, X10, Java Fork-Join tasks) simplify multicore programming in contrast to programming with threads. In a task based model, the programmer specifies parallel tasks and the runtime maps these tasks to hardware threads. The runtime automatically balances the load using work-stealing and provides performance portability. However, interference between parallel tasks can result in concurrency errors. This paper proposes a dynamic analysis technique to detect atomicity violations in task parallel programs, which could occur in different schedules for a given input without performing interleaving exploration. Our technique leverages the series-parallel dynamic execution structure of a task parallel program to identify parallel accesses. It also maintains access history metadata with each shared memory location to identify parallel accesses that can cause atomicity violations in different schedules. To streamline metadata management, the access history metadata is split into global metadata that is shared by all tasks and local metadata that is specific to each task. The global metadata tracks a fixed number of access histories for each shared memory location that capture all possible access patterns necessary for an atomicity violation. Our prototype tool for Intel Threading Building Blocks (TBB) detects atomicity violations that can potentially occur in different interleavings for a given input with performance overheads similar to Velodrome atomicity checker for thread based programs.


title: Exploiting mixed SIMD parallelism by reducing data reorganization overhead

authors:
Hao Zhou
Jingling Xue

abstract: Existing loop vectorization techniques can exploit either intra- or inter-iteration SIMD parallelism alone in a code region if one part of the region vectorized for one type of parallelism has data dependences (called mixed-parallelism-inhibiting dependences) on the other part of the region vectorized for the other type of parallelism. In this paper, we consider a class of loops that exhibit both types of parallelism (i.e., mixed SIMD parallelism) in its code regions that contain mixed-parallelism-inhibiting data dependences. We present a new compiler approach for exploiting such mixed SIMD parallelism effectively by reducing the data reorganization overhead incurred when one type of parallelism is switched to the other. Our auto-vectorizer is simple and has been implemented in LLVM (3.5.0). We evaluate it on seven benchmarks with mixed SIMD parallelism selected from SPEC and NAS benchmark suites and demonstrate its performance advantages over the state-of-the-art.


title: Software prefetching for indirect memory accesses

authors:
Sam Ainsworth
Timothy M. Jones


title: Taming warp divergence

authors:
Jayvant Anantpur
R. Govindarajan


title: Formalizing the concurrency semantics of an LLVM fragment

authors:
Soham Chakraborty
Viktor Vafeiadis


title: Cross-ISA machine emulation for multicores

authors:
Emilio G. Cota
Paolo Bonzini
Alex Bennée
Luca P. Carloni


title: Synthesizing benchmarks for predictive modeling

authors:
Chris Cummins
Pavlos Petoumenos
Zheng Wang
Hugh Leather


title: Optimistic loop optimization

authors:
Johannes Doerfert
Tobias Grosser
Sebastian Hack


title: Removing checks in dynamically typed languages through efficient profiling

authors:
Gem Dot
Alejandro Martínez
Antonio González


title: A space- and energy-efficient code Compression/Decompression technique for coarse-grained reconfigurable architectures

authors:
Bernhard Egger
Hochan Lee
Duseok Kang
Mansureh S. Moghaddam
Youngchul Cho
Yeonbok Lee
Sukjin Kim
Soonhoi Ha
Kiyoung Choi


title: Dynamic buffer overflow detection for GPGPUs

authors:
Christopher Erb
Mike Collins
Joseph L. Greathouse


title: Discovery and exploitation of general reductions: a constraint based approach

authors:
Philip Ginsbach
Michael F. P. O'Boyle


title: TwinKernels: an execution model to improve GPU hardware scheduling at compile time

authors:
Xiang Gong
Zhongliang Chen
Amir Kavyan Ziabari
Rafael Ubal
David R. Kaeli


title: Automatic detection of extended data-race-free regions

authors:
Alexandra Jimborean
Jonatan Waern
Per Ekemark
Stefanos Kaxiras
Alberto Ros


title: ThinLTO: scalable and incremental LTO

authors:
Teresa Johnson
Mehdi Amini
Xinliang David Li


title: A collaborative dependence analysis framework

authors:
Nick P. Johnson
Jordan Fix
Stephen R. Beard
Taewook Oh
Thomas B. Jablin
David I. August


title: Pointer disambiguation via strict inequalities

authors:
Maroua Maalej
Vitor Paisante
Pedro Ramos
Laure Gonnord
Fernando Magno Quintão Pereira


title: Phase-aware optimization in approximate computing

authors:
Subrata Mitra
Manish K. Gupta
Sasa Misailovic
Saurabh Bagchi


title: Minimizing the cost of iterative compilation with active learning

authors:
William F. Ogilvie
Pavlos Petoumenos
Zheng Wang
Hugh Leather


title: Optimizing function placement for large-scale data-center applications

authors:
Guilherme Ottoni
Bertrand Maher


title: Characterizing data organization effects on heterogeneous memory architectures

authors:
Apan Qasem
Ashwin M. Aji
Gregory Rodgers


title: Incremental whole program optimization and compilation

authors:
Patrick W. Sathyanathan
Wenlei He
Ten H. Tzen


title: Legato: end-to-end bounded region serializability using commodity hardware transactional memory

authors:
Aritra Sengupta
Man Cao
Michael D. Bond
Milind Kulkarni


title: Lift: a functional data-parallel IR for high-performance GPU code generation

authors:
Michel Steuwer
Toomas Remmelg
Christophe Dubach


title: Automatic generation of fast BLAS3-GEMM: a portable compiler approach

authors:
Xing Su
Xiangke Liao
Jingling Xue


title: Parallel associative reductions in halide

authors:
Patricia Suriana
Andrew Adams
Shoaib Kamil


title: Clairvoyance: look-ahead compile-time scheduling

authors:
Kim-Anh Tran
Trevor E. Carlson
Konstantinos Koukos
Magnus Själander
Vasileios Spiliopoulos
Stefanos Kaxiras
Alexandra Jimborean


title: FinePar: irregularity-aware fine-grained workload partitioning on integrated architectures

authors:
Feng Zhang
Bo Wu
Jidong Zhai
Bingsheng He
Wenguang Chen


title: Resilient decentralized Android application repackaging detection using logic bombs

authors:
Qiang Zeng
Lannan Luo
Zhiyun Qian
Xiaojiang Du
Zhoujun Li

abstract: Application repackaging is a severe threat to Android users and the market. Existing countermeasures mostly detect repackaging based on app similarity measurement and rely on a central party to perform detection, which is unscalable and imprecise. We instead consider building the detection capability into apps, such that user devices are made use of to detect repackaging in a decentralized fashion. The main challenge is how to protect repackaging detection code from attacks. We propose a creative use of logic bombs, which are regularly used in malware, to conquer the challenge. A novel bomb structure is invented and used: the trigger conditions are constructed to exploit the differences between the attacker and users, such that a bomb that lies dormant on the attacker side will be activated on one of the user devices, while the repackaging detection code, which is packed as the bomb payload, is kept inactive until the trigger conditions are satisfied. Moreover, the repackaging detection code is woven into the original app code and gets encrypted; thus, attacks by modifying or deleting suspicious code will corrupt the app itself. We have implemented a prototype, named BombDroid, that builds the repackaging detection into apps through bytecode instrumentation, and the evaluation shows that the technique is effective, efficient, and resilient to various adversary analysis including symbol execution, multi-path exploration, and program slicing.


title: Scalable concurrency debugging with distributed graph processing

authors:
Long Zheng
Xiaofei Liao
Hai Jin
Jieshan Zhao
Qinggang Wang

abstract: Existing constraint-solving-based technique enables an efficient and high-coverage concurrency debugging. Yet, there remains a significant gap between the state of the art and the state of the programming practices for scaling to handle long-running execution of programs.


title: Optimal DNN primitive selection with partitioned boolean quadratic programming

authors:
Andrew Anderson
David Gregg

abstract: Deep Neural Networks (DNNs) require very large amounts of computation, and many different algorithms have been proposed to implement their most expensive layers, each of which has a large number of variants with different trade-offs of parallelism, locality, memory footprint, and execution time. In addition, specific algorithms operate much more efficiently on specialized data layouts.


title: Automating efficient variable-grained resiliency for low-power IoT systems

authors:
Sara S. Baghsorkhi
Christos Margiolas

abstract: New trends in edge computing encourage pushing more of the compute and analytics to the outer edge and processing most of the data locally. We explore how to transparently provide resiliency for heavy duty edge applications running on low-power devices that must deal with frequent and unpredictable power disruptions. Complicating this process further are (a) memory usage restrictions in tiny low-power devices, that affect not only performance but efficacy of the resiliency techniques, and (b) differing resiliency requirements across deployment environments. Nevertheless, an application developer wants the ability to write an application once, and have it be reusable across all low-power platforms and across all different deployment settings. In response to these challenges, we have devised a transparent roll-back recovery mechanism that performs incremental checkpoints with minimal execution time overhead and at variable granularities. Our solution includes the co-design of firmware, runtime and compiler transformations for providing seamless fault-tolerance, along with an auto-tuning layer that automatically generates multiple resilient variants of an application. Each variant spreads application’s execution over atomic transactional regions of a certain granularity. Variants with smaller regions provide better resiliency, but incur higher overhead; thus, there is no single best option, but rather a Pareto optimal set of configurations. We apply these strategies across a variety of edge device applications and measure the execution time overhead of the framework on a TI MSP430FR6989. When we restrict unin- terrupted atomic intervals to 100ms, our framework keeps geomean overhead below 2.48x.


title: AutoPA: automatically generating active driver from original passive driver code

authors:
Jia-Ju Bai
Yu-Ping Wang
Shi-Min Hu

abstract: Original device drivers are often passive in common operating systems, and they should correctly handle synchronization when concurrently invoked by multiple external threads. However, many concurrency bugs have occurred in drivers due to incautious synchronization. To solve concurrency problems, active driver is proposed to replace original passive driver. An active driver has its own thread and does not need to handle synchronization, thus the occurrence probability of many concurrency bugs can be effectively reduced. But previous approaches of active driver have some limitations. The biggest limitation is that original passive driver code needs to be manually rewritten. In this paper, we propose a practical approach, AutoPA, to automatically generate efficient active driver from original passive driver code. AutoPA uses function analysis and code instrumentation to perform automated driver generation, and it uses an improved active driver architecture to reduce performance degradation. We have evaluated AutoPA on 20 Linux drivers. The results show that AutoPA can automatically and successfully generate usable active drivers from original driver code. And generated active drivers can work normally with or without the synchronization primitives in original driver code. To check the effect of AutoPA on driver reliability, we perform fault injection testing on the generated active drivers, and find that all injected concurrency faults are well tolerated and the drivers can work normally. And the performance of generated active drivers is not obviously degraded compared to original passive drivers.


title: The generalized matrix chain algorithm

authors:
Henrik Barthels
Marcin Copik
Paolo Bientinesi

abstract: In this paper, we present a generalized version of the matrix chain algorithm to generate efficient code for linear algebra problems, a task for which human experts often invest days or even weeks of works. The standard matrix chain problem consists in finding the parenthesization of a matrix product M := A1 A2 ⋯ An that minimizes the number of scalar operations. In practical applications, however, one frequently encounters more complicated expressions, involving transposition, inversion, and matrix properties. Indeed, the computation of such expressions relies on a set of computational kernels that offer functionality well beyond the simple matrix product. The challenge then shifts from finding an optimal parenthesization to finding an optimal mapping of the input expression to the available kernels. Furthermore, it is often the case that a solution based on the minimization of scalar operations does not result in the optimal solution in terms of execution time. In our experiments, the generated code outperforms other libraries and languages on average by a factor of about 9. The motivation for this work comes from the fact that—despite great advances in the development of compilers—the task of mapping linear algebra problems to optimized kernels is still to be done manually. In order to relieve the user from this complex task, new techniques for the compilation of linear algebra expressions have to be developed.


title: SGXElide: enabling enclave code secrecy via self-modification

authors:
Erick Bauman
Huibo Wang
Mingwei Zhang
Zhiqiang Lin

abstract: Intel SGX provides a secure enclave in which code and data are hidden from the outside world, including privileged code such as the OS or hypervisor. However, by default, enclave code prior to initialization can be disassembled and therefore no secrets can be embedded in the binary. This is a problem for developers wishing to protect code secrets. This paper introduces SGXElide, a nearly-transparent framework that enables enclave code confidentiality. The key idea is to treat program code as data and dynamically restore secrets after an enclave is initialized. SGXElide can be integrated into any enclave, providing a mechanism to securely decrypt or deliver the secret code with the assistance of a developer-controlled trusted remote party. We have implemented SGXElide atop a recently released version of the Linux SGX SDK, and our evaluation with a number of programs shows that SGXElide can be used to protect the code secrecy of practical applications with no overhead after enclave initialization.


title: Synthesizing an instruction selection rule library from semantic specifications

authors:
Sebastian Buchwald
Andreas Fried
Sebastian Hack

abstract: Instruction selection is the part of a compiler that transforms intermediate representation (IR) code into machine code. Instruction selectors build on a library of hundreds if not thousands of rules. Creating and maintaining these rules is a tedious and error-prone manual process.


title: Register allocation for Intel processor graphics

authors:
Wei-Yu Chen
Guei-Yuan Lueh
Pratik Ashar
Kaiyu Chen
Buqi Cheng

abstract: Register allocation is a well-studied problem, but surprisingly little work has been published on assigning registers for GPU architectures. In this paper we present the register allocator in the production compiler for Intel HD and Iris Graphics. Intel GPUs feature a large byte-addressable register file organized into banks, an expressive instruction set that supports variable SIMD-sizes and divergent control flow, and high spill overhead due to relatively long memory latencies. These distinctive characteristics impose challenges for register allocation, as input programs may have arbitrarily-sized variables, partial updates, and complex control flow. Not only should the allocator make a program spill-free, but it must also reduce the number of register bank conflicts and anti-dependencies. Since compilation occurs in a JIT environment, the allocator also needs to incur little overhead.


title: CollectionSwitch: a framework for efficient and dynamic collection selection

authors:
Diego Costa
Artur Andrzejak

abstract: Selecting collection data structures for a given application is a crucial aspect of the software development. Inefficient usage of collections has been credited as a major cause of performance bloat in applications written in Java, C++ and C#. Furthermore, a single implementation might not be optimal throughout the entire program execution. This demands an adaptive solution that adjusts at runtime the collection implementations to varying workloads.


title: A compiler for cyber-physical digital microfluidic biochips

authors:
Christopher Curtis
Daniel T. Grissom
Philip Brisk

abstract: Programmable microfluidic laboratories-on-a-chip (LoCs) offer the benefits of automation and miniaturization to the life sciences. This paper presents an updated version of the BioCoder language and a fully static (offline) compiler that can target an emerging class of LoCs called Digital Microfluidic Biochips (DMFBs), which manipulate discrete droplets of liquid on a 2D electrode grid. The BioCoder language and runtime execution engine leverage advances in sensor integration to enable specification, compilation, and execution of assays (bio-chemical procedures) that feature online decision-making based on sensory data acquired during assay execution. The compiler features a novel hybrid intermediate representation (IR) that interleaves fluidic operations with computations performed on sensor data. The IR extends the traditional notions of liveness and interference to fluidic variables and operations, as needed to target the DMFB, which itself can be viewed as a spatially reconfigurable array. The code generator converts the IR into the following: (1) a set of electrode activation sequences for each basic block in the control flow graph (CFG); (2) a set of computations performed on sensor data, which dynamically determine the result of each control flow operation; and (3) a set of electrode activation sequences for each control flow transfer operation (CFG edge). The compiler is validated using a software simulator which produces animated videos of realistic bioassay execution on a DMFB.


title: Transforming loop chains via macro dataflow graphs

authors:
Eddie C. Davis
Michelle Mills Strout
Catherine Olschanowsky

abstract: This paper describes an approach to performance optimization using modified macro dataflow graphs, which contain nodes representing the loops and data involved in the stencil computation. The targeted applications include existing scientific applications that contain a series of stencil computations that share data, i.e. loop chains. The performance of stencil applications can be improved by modifying the execution schedules. However, modern architectures are increasingly constrained by the memory subsystem bandwidth. To fully realize the benefits of the schedule changes for improved locality, temporary storage allocation must also be minimized.


title: Biological computation (keynote)

abstract: Unlike engineered systems, living cells self-generate, self-organise and self-repair, they undertake massively parallel operations with slow and noisy components in a noisy environment, they sense and actuate at molecular scales, and most intriguingly, they blur the line between software and hardware. Understanding this biological computation presents a huge challenge to the scientific community. Yet the ultimate destination and prize at the culmination of this scientific journey is the promise of revolutionary and transformative technology: the rational design and implementation of biological function, or more succinctly, the ability to program life.


title: nAdroid: statically detecting ordering violations in Android applications

authors:
Xinwei Fu
Dongyoon Lee
Changhee Jung

abstract: Modern mobile applications use a hybrid concurrency model. In this model, events are handled sequentially by event loop(s), and long-running tasks are offloaded to other threads. Concurrency errors in this hybrid concurrency model can take multiple forms: traditional atomicity and ordering violations between threads, as well as ordering violations between event callbacks on a single event loop.


title: High performance stencil code generation with lift

authors:
Bastian Hagedorn
Larisa Stoltzfus
Michel Steuwer
Sergei Gorlatch
Christophe Dubach

abstract: Stencil computations are widely used from physical simulations to machine-learning. They are embarrassingly parallel and perfectly fit modern hardware such as Graphic Processing Units. Although stencil computations have been extensively studied, optimizing them for increasingly diverse hardware remains challenging. Domain Specific Languages (DSLs) have raised the programming abstraction and offer good performance. However, this places the burden on DSL implementers who have to write almost full-fledged parallelizing compilers and optimizers.


title: Conflict-free vectorization of associative irregular applications with recent SIMD architectural advances

authors:
Peng Jiang
Gagan Agrawal

abstract: Irregular applications that involve indirect memory accesses were traditionally considered unsuitable for SIMD processing. Though some progress has been made in recent years, the existing approaches require either expensive data reorganization or favorable input distribution to deliver good performance. In this work, we propose a novel vectorization approach called in-vector reduction that can efficiently accelerate a class of associative irregular applications. This approach exploits associativity in the irregular reductions to resolve the data conflicts within SIMD vectors. We implement in-vector reduction with the new conflict detecting instructions that are supported in Intel AVX-512 instruction set and provide a programming interface to facilitate the vectorization of such associative irregular applications. Compared with previous approaches, in-vector reduction eliminates a large part of the overhead of data reorganization and achieves high SIMD utilization even under adverse input distributions. The evaluation results show that our approach is efficient in vectorizing a diverse set of irregular applications, including graph algorithms, particle simulation codes, and hash-based aggregation. Our vectorization achieves 1.5x to 5.5x speedups over the original sequential codes on a single core of Intel Xeon Phi and outperforms a competing approach, conflict-masking based vectorization, by 1.4x to 11.8x.


title: DeLICM: scalar dependence removal at zero memory cost

authors:
Michael Kruse
Tobias Grosser

abstract: Increasing data movement costs motivate the integration of polyhedral loop optimizers in the standard flow (-O3) of production compilers. While polyhedral optimizers have been shown to be effective when applied as source-to-source transformation, the single static assignment form used in modern compiler mid-ends makes such optimizers less effective. Scalar dependencies (dependencies carried over a single memory location) are the main obstacle preventing effective optimization. We present DeLICM, a set of transformations which, backed by a polyhedral value analysis, eliminate problematic scalar dependences by 1) relocating scalar memory references to unused array locations and by 2) forwarding computations that otherwise cause scalar dependences. Our experiments show that DeLICM effectively eliminates dependencies introduced by compiler-internal canonicalization passes, human programmers, optimizing code generators, or inlining -- without the need for any additional memory allocation. As a result, polyhedral loop optimizations can be better integrated into compiler pass pipelines which is essential for metaprogramming optimization.


title: Dominance-based duplication simulation (DBDS): code duplication to enable compiler optimizations

authors:
David Leopoldseder
Lukas Stadler
Thomas Würthinger
Josef Eisl
Doug Simon
Hanspeter Mössenböck

abstract: Compilers perform a variety of advanced optimizations to improve the quality of the generated machine code. However, optimizations that depend on the data flow of a program are often limited by control-flow merges. Code duplication can solve this problem by hoisting, i.e. duplicating, instructions from merge blocks to their predecessors. However, finding optimization opportunities enabled by duplication is a non-trivial task that requires compile-time intensive analysis. This imposes a challenge on modern (just-in-time) compilers: Duplicating instructions tentatively at every control flow merge is not feasible because excessive duplication leads to uncontrolled code growth and compile time increases. Therefore, compilers need to find out whether a duplication is beneficial enough to be performed.


title: Local memory-aware kernel perforation

authors:
Daniel Maier
Biagio Cosenza
Ben H. H. Juurlink

abstract: Many applications provide inherent resilience to some amount of error and can potentially trade accuracy for performance by using approximate computing. Applications running on GPUs often use local memory to minimize the number of global memory accesses and to speed up execution. Local memory can also be very useful to improve the way approximate computation is performed, e.g., by improving the quality of approximation with data reconstruction techniques. This paper introduces local memory-aware perforation techniques specifically designed for the acceleration and approximation of GPU kernels. We propose a local memory-aware kernel perforation technique that first skips the loading of parts of the input data from global memory, and later uses reconstruction techniques on local memory to reach higher accuracy while having performance similar to state-of-the-art techniques. Experiments show that our approach is able to accelerate the execution of a variety of applications from 1.6× to 3× while introducing an average error of 6%, which is much smaller than that of other approaches. Results further show how much the error depends on the input data and application scenario, the impact of local memory tuning and different parameter configurations.


title: Look-ahead SLP: auto-vectorization in the presence of commutative operations

authors:
Vasileios Porpodas
Rodrigo C. O. Rocha
Luís F. W. Góes

abstract: Auto-vectorizing compilers automatically generate vector (SIMD) instructions out of scalar code. The state-of-the-art algorithm for straight-line code vectorization is Superword-Level Parallelism (SLP). In this work we identify a major limitation at the core of the SLP algorithm, in the performance-critical step of collecting the vectorization candidate instructions that form the SLP-graph data structure. SLP lacks global knowledge when building its vectorization graph, which negatively affects its local decisions when it encounters commutative instructions. We propose LSLP, an improved algorithm that can plug-in to existing SLP implementations, and can effectively vectorize code with arbitrarily long chains of commutative operations. LSLP relies on short-depth look-ahead for better-informed local decisions. Our evaluation on a real machine shows that LSLP can significantly improve the performance of real-world code with little compilation-time overhead.


title: Analyzing and optimizing task granularity on the JVM

authors:
Andrea Rosà
Eduardo Rosales
Walter Binder

abstract: Task granularity, i.e., the amount of work performed by parallel tasks, is a key performance attribute of parallel applications. On the one hand, fine-grained tasks (i.e., small tasks carrying out few computations) may introduce considerable parallelization overheads. On the other hand, coarse-grained tasks (i.e., large tasks performing substantial computations) may not fully utilize the available CPU cores, resulting in missed parallelization opportunities. In this paper, we provide a better understanding of task granularity for applications running on a Java Virtual Machine. We present a novel profiler which measures the granularity of every executed task. Our profiler collects carefully selected metrics from the whole system stack with only little overhead, and helps the developer locate performance problems. We analyze task granularity in the DaCapo and ScalaBench benchmark suites, revealing several inefficiencies related to fine-grained and coarse-grained tasks. We demonstrate that the collected task-granularity profiles are actionable by optimizing task granularity in two benchmarks, achieving speedups up to 1.53x.


title: Lightweight detection of cache conflicts

authors:
Probir Roy
Shuaiwen Leon Song
Sriram Krishnamoorthy
Xu Liu

abstract: In memory hierarchies, caches perform an important role in reducing average memory access latency. Minimizing cache misses can yield significant performance gains. As set-associative caches are widely used in modern architectures, capacity and conflict cache misses co-exist. These two types of cache misses require different optimization strategies. While cache misses are commonly studied using cache simulators, state-of-the-art simulators usually incur hundreds to thousands of times a program's execution runtime. Moreover, a simulator has difficulty in simulating complex real hardware. To overcome these limitations, measurement methods are proposed to directly monitor program execution on real hardware via performance monitoring units. However, existing measurement-based tools either focus on capacity cache misses or do not distinguish capacity and conflict cache misses. In this paper, we design and implement CCProf, a lightweight measurement-based profiler that identifies conflict cache misses and associates them with program source code and data structures. CCProf incurs moderate runtime overhead that is at least an order of magnitude lower than simulators. With the evaluation on a number of representative programs, CCProf is able to guide optimizations on cache conflict misses and obtain nontrivial speedups.


title: CUDAAdvisor: LLVM-based runtime profiling for modern GPUs

authors:
Du Shen
Shuaiwen Leon Song
Ang Li
Xu Liu

abstract: General-purpose GPUs have been widely utilized to accelerate parallel applications. Given a relatively complex programming model and fast architecture evolution, producing efficient GPU code is nontrivial. A variety of simulation and profiling tools have been developed to aid GPU application optimization and architecture design. However, existing tools are either limited by insufficient insights or lacking in support across different GPU architectures, runtime and driver versions. This paper presents CUDAAdvisor, a profiling framework to guide code optimization in modern NVIDIA GPUs. CUDAAdvisor performs various fine-grained analyses based on the profiling results from GPU kernels, such as memory-level analysis (e.g., reuse distance and memory divergence), control flow analysis (e.g., branch divergence) and code-/data-centric debugging. Unlike prior tools, CUDAAdvisor supports GPU profiling across different CUDA versions and architectures, including CUDA 8.0 and Pascal architecture. We demonstrate several case studies that derive significant insights to guide GPU code optimization for performance improvement.


title: Loop transformations leveraging hardware prefetching

authors:
Savvas Sioutas
Sander Stuijk
Henk Corporaal
Twan Basten
Lou J. Somers

abstract: Memory-bound applications heavily depend on the bandwidth of the system in order to achieve high performance. Improving temporal and/or spatial locality through loop transformations is a common way of mitigating this dependency. However, choosing the right combination of optimizations is not a trivial task, due to the fact that most of them alter the memory access pattern of the application and as a result interfere with the efficiency of the hardware prefetching mechanisms present in modern architectures. We propose an optimization algorithm that analytically classifies an algorithmic description of a loop nest in order to decide whether it should be optimized stressing its temporal or spatial locality, while also taking hardware prefetching into account. We implement our technique as a tool to be used with the Halide compiler and test it on a variety of benchmarks. We find an average performance improvement of over 40% compared to previous analytical models targeting the Halide language and compiler.


title: Qubit allocation

authors:
Marcos Yukio Siraichi
Vinícius Fernandes dos Santos
Caroline Collange
Fernando Magno Quintão Pereira

abstract: In May of 2016, IBM Research has made a quantum processor available in the cloud to the general public. The possibility of programming an actual quantum device has elicited much enthusiasm. Yet, quantum programming still lacks the compiler support that modern programming languages enjoy today. To use universal quantum computers like IBM's, programmers must design low-level circuits. In particular, they must map logical qubits into physical qubits that need to obey connectivity constraints. This task resembles the early days of programming, in which software was built in machine languages. In this paper, we formally introduce the qubit allocation problem and provide an exact solution to it. This optimal algorithm deals with the simple quantum machinery available today; however, it cannot scale up to the more complex architectures scheduled to appear. Thus, we also provide a heuristic solution to qubit allocation, which is faster than the current solutions already implemented to deal with this problem.


title: Program generation for small-scale linear algebra applications

authors:
Daniele G. Spampinato
Diego Fabregat-Traver
Paolo Bientinesi
Markus Püschel

abstract: We present SLinGen, a program generation system for linear algebra. The input to SLinGen is an application expressed mathematically in a linear-algebra-inspired language (LA) that we define. LA provides basic scalar/vector/matrix additions/multiplications and higher level operations including linear systems solvers, Cholesky and LU factorizations. The output of SLinGen is performance-optimized single-source C code, optionally vectorized with intrinsics. The target of SLinGen are small-scale computations on fixed-size operands, for which a straightforward implementation using optimized libraries (e.g., BLAS or LAPACK) is known to yield suboptimal performance (besides increasing code size and introducing dependencies), but which are crucial in control, signal processing, computer vision, and other domains. Internally, SLinGen uses synthesis and DSL-based techniques to optimize at a high level of abstraction. We benchmark our program generator on three prototypical applications: the Kalman filter, Gaussian process regression, and an L1-analysis convex solver, as well as basic routines including Cholesky factorization and solvers for the continuous-time Lyapunov and Sylvester equations. The results show significant speed-ups compared to straightforward C with Intel icc and clang with a polyhedral optimizer, as well as library-based and template-based implementations.


title: SIMD intrinsics on managed language runtimes

authors:
Alen Stojanov
Ivaylo Toskov
Tiark Rompf
Markus Püschel

abstract: Managed language runtimes such as the Java Virtual Machine (JVM) provide adequate performance for a wide range of applications, but at the same time, they lack much of the low-level control that performance-minded programmers appreciate in languages like C/C++ . One important example is the intrinsics interface that exposes instructions of SIMD (Single Instruction Multiple Data) vector ISAs (Instruction Set Architectures). In this paper we present an automatic approach for including native intrinsics in the runtime of a managed language. Our implementation consists of two parts. First, for each vector ISA, we automatically generate the intrinsics API from the vendor-provided XML specification. Second, we employ a metaprogramming approach that enables programmers to generate and load native code at runtime. In this setting, programmers can use the entire high-level language as a kind of macro system to define new high-level vector APIs with zero overhead. As an example use case we show a variable precision API. We provide an end-to-end implementation of our approach in the HotSpot VM that supports all 5912 Intel SIMD intrinsics from MMX to AVX-512 . Our benchmarks demonstrate that this combination of SIMD and metaprogramming enables developers to write high-performance, vectorized code on an unmodified JVM that outperforms the auto-vectorizing HotSpot just-in-time (JIT) compiler and provides tight integration between vectorized native code and the managed JVM ecosystem.


title: Synthesizing programs that expose performance bottlenecks

authors:
Luca Della Toffola
Michael Pradel
Thomas R. Gross

abstract: Software often suffers from performance bottlenecks, e.g., because some code has a higher computational complexity than expected or because a code change introduces a performance regression. Finding such bottlenecks is challenging for developers and for profiling techniques because both rely on performance tests to execute the software, which are often not available in practice. This paper presents PerfSyn, an approach for synthesizing test programs that expose performance bottlenecks in a given method under test. The basic idea is to repeatedly mutate a program that uses the method to systematically increase the amount of work done by the method. We formulate the problem of synthesizing a bottleneck-exposing program as a combinatorial search and show that it can be effectively and efficiently addressed using well known graph search algorithms. We evaluate the approach with 147 methods from seven Java code bases. PerfSyn automatically synthesizes test programs that expose 22 bottlenecks. The bottlenecks are due to unexpectedly high computational complexity and due to performance differences between different versions of the same code.


title: CVR: efficient vectorization of SpMV on x86 processors

authors:
Biwei Xie
Jianfeng Zhan
Xu Liu
Wanling Gao
Zhen Jia
Xiwen He
Lixin Zhang

abstract: Sparse Matrix-vector Multiplication (SpMV) is an important computation kernel widely used in HPC and data centers. The irregularity of SpMV is a well-known challenge that limits SpMV’s parallelism with vectorization operations. Existing work achieves limited locality and vectorization efficiency with large preprocessing overheads. To address this issue, we present the Compressed Vectorization-oriented sparse Row (CVR), a novel SpMV representation targeting efficient vectorization. The CVR simultaneously processes multiple rows within the input matrix to increase cache efficiency and separates them into multiple SIMD lanes so as to take the advantage of vector processing units in modern processors. Our method is insensitive to the sparsity and irregularity of SpMV, and thus able to deal with various scale-free and HPC matrices. We implement and evaluate CVR on an Intel Knights Landing processor and compare it with five state-of-the-art approaches through using 58 scale-free and HPC sparse matrices. Experimental results show that CVR can achieve a speedup up to 1.70 × (1.33× on average) and a speedup up to 1.57× (1.10× on average) over the best existing approaches for scale-free and HPC sparse matrices, respectively. Moreover, CVR typically incurs the lowest preprocessing overhead compared with state-of-the-art approaches.


title: Poker: permutation-based SIMD execution of intensive tree search by path encoding

authors:
Feng Zhang
Jingling Xue

abstract: We propose POKER, a permutation-based vectorization approach for vectorizing multiple queries over B+-trees. Our key insight is to combine vector loads and path-encoding-based permutations to alleviate memory latency while keeping the number of key comparisons needed for a query to a minimum. Implemented as a C++ template library, POKER represents a general-purpose solution for vectorizing the queries over indexing trees on multi-core processors equipped with SIMD units. For a set of five representative benchmarks evaluated with 24 configurations each, POKER outperforms the state-of-the-art by 2.11x with one single thread and 2.28x with eight threads on an Intel Broadwell processor that supports 256-bit AVX2, on average.


title: May-happen-in-parallel analysis with static vector clocks

authors:
Qing Zhou
Lian Li
Lei Wang
Jingling Xue
Xiaobing Feng

abstract: May-Happen-in-Parallel (MHP) analysis computes whether two statements in a multi-threaded program may execute concurrently or not. It works as a basis for many analyses and optimization techniques of concurrent programs. This paper proposes a novel approach for MHP analysis, by statically computing vector clocks. Static vector clocks extend the classic vector clocks algorithm to handle the complex control flow structures in static analysis, and we have developed an efficient context-sensitive algorithm to compute them. To the best of our knowledge, this is the first attempt to compute vector clocks statically. Using static vector clocks, we can drastically improve the efficiency of existing MHP analyses, without loss of precision: the performance speedup can be up to 1828X, with a much smaller memory footprint (reduced by up to 150X). We have implemented our analysis in a static data race detector, and experimental results show that our MHP analysis can help remove up to 88% of spurious data race pairs.


title: Smokestack: Thwarting DOP Attacks with Runtime Stack Layout Randomization

authors:
Misiker Tadesse Aga
Todd M. Austin

abstract: Memory corruption vulnerabilities in type-unsafe languages are often exploited to perform a control-flow hijacking attack, in which an attacker uses vulnerabilities to corrupt control data in the program to eventually gain control over the execution of the program. However, widespread adoption of control-flow attack defenses such as Control-flow Integrity (CFI) has led attackers to exploit memory errors to corrupt non-control data that can not be detected by these defenses. Non-control data attacks can be used to corrupt security critical data or leak sensitive information. Moreover, recent attacks such as data-oriented programming (DOP) have generalized non-control data attacks to achieve Turing-complete computation capabilities within the programmer-specified control-flow graph, leaving previously proposed control-flow protections unable to stop these attacks.In this paper, we present a stack-layout randomization scheme that can effectively thwart DOP attacks. Our approach, called Smokestack, provides each function invocation with a randomly permuted ordering of the local stack organization. In addition, we utilize true-random value sources combined with disclosure-resistant pseudo-random number generation to ensure that an adversary cannot anticipate a function-s invocation permutation of automatic variables. Our evaluation on SPEC benchmarks and various real-world applications shows that Smokestack can stop DOP attacks with minimal overhead.


title: Tiramisu: A Polyhedral Compiler for Expressing Fast and Portable Code

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

abstract: 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 commands 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.


title: Multi-target Compiler for the Deployment of Machine Learning Models

authors:
Oscar Castro-López
Inés Fernando Vega López

abstract: The deployment of machine learning models into production environments is a crucial task. Its seamless integration with the operational system can be quite challenging as it must adhere to the same software requirements such as memory management, latency, and scalability as the rest of the system. Unfortunately, none of these requirements are taken into consideration when inferring new models from data. A straightforward approach for deployment consists of building a pipeline connecting the modeling tools to the operational system. This approach follows a client-server architecture and it may not address the design requirements of the software in production, especially the ones related to efficiency. An alternative is to manually generate the source code implementing the model in the programming language that was originally used to develop the software in production. However, this approach is usually avoided because it is a time-consuming and error-prone task. To circumvent the aforementioned problems, we propose to automate the process of machine learning model deployment. For this, we have developed a special-purpose compiler. Machine learning models can be formally defined using a standard language. We use this formal description as an input for our compiler, which translates it into the source code that implements the model. Our proposed compiler generates code for different programming languages. Furthermore, with this compiler we can generate source code that exploits specific characteristics of the systems hardware architecture such as multi-core CPUs and graphic processing cards. We have conducted experiments that indicate that automated code generation for deploying machine learning models is, not only feasible but also efficient.


title: IGC: The Open Source Intel Graphics Compiler

authors:
Anupama Chandrasekhar
Gang Chen
Po-Yu Chen
Wei-Yu Chen
Junjie Gu
Peng Guo
Shruthi Hebbur Prasanna Kumar
Guei-Yuan Lueh
Pankaj Mistry
Wei Pan
Thomas Raoux
Konrad Trifunovic

abstract: With increasing general purpose programming capability, GPUs have become the mainstay for a wide variety of compute intensive tasks from cloud to edge computing. Because of its availability on nearly every desktop and mobile processor that Intel ships, Intel integrated GPU offers a plethora of opportunities for researchers and application developers to make significant real-world impact. In this paper we present the Intel Graphics Compiler (IGC), the LLVM-based production compiler for Intel HD and Iris graphics. IGC supports all major graphics and compute APIs, and its OpenCL compute stack including compute runtime, compiler frontend and backend, and architecture specification is fully open-source, giving a unique opportunity for developers to optimize the entire stack. We highlight several custom optimizations that address the challenges for GPU compilation. Examples include SIMD size selection, divergence analysis, instruction scheduling, addressing mode selection, and redundant copy elimination. These optimizations take advantage of features in the Intel GPU architecture such as a larger register file, indirect register addressing, and multiple memory addressing modes. Experimental results show that our optimizations deliver significant speedup on a number of OpenCL benchmarks; compared to the baseline, we see a geometric mean of 12% speed up across benchmarks with a peak gain of 45%.


title: A Shared BTB Design for Multicore Systems

authors:
Moumita Das
Ansuman Banerjee
Bhaskar Sardar

abstract: With increasing use of runtime polymorphism and reliance on runtime type interpretation, the presence and importance of indirect branches has seen a considerable rise in recent workloads. Evidently, accurate target prediction for indirect branches has emerged as an important problem. While direction prediction of direct branches has received considerable research attention leading to efficient prediction policies and hardware structures implemented inside modern processors, proposals for target prediction for indirect branches has been relatively few. The problem of accurate target prediction for indirect branches is significantly tough since these transfer control to an address stored in a register that is known only at runtime. Unlike conditional direct branches, indirect branches can have more than two targets to be resolved at runtime, for which prediction requires a full 32-bit/64-bit address to be predicted, in contrast to just a taken or not-taken decision as needed for direction prediction of direct branches. Recent research shows indirect branches, being mispredicted more frequently, can start to dominate the overall branch misprediction cost. In modern processors, the only hardware structure available to facilitate target address prediction for indirect branches is a fixed-size Branch Target Buffer (BTB). BTB is often designed as a set associative cache for storing recent target addresses for branch instructions encountered during execution, with a motivation of being able to reuse the same addresses for future instances, thereby saving latency cycles. Evidently, designing efficient indexing schemes and replacement mechanisms for BTB structures is crucial, more so, for indirect branches, since these serve as the only prediction handle. In this paper, our objective is to examine a hierarchical BTB design for multicores with total size comparable to what exists today, with a motivation towards possible improvement of prediction accuracy by facilitating collaborative constructive learning between programs executing in different cores that encounter similar histories. Specifically, we wish to propose the concept of a small on-chip L1 BTB inside each core, supported by a larger off-chip L2 BTB shared among the cores. Our motivation towards a hierarchical BTB design is twofold. On one hand, in a multiprogramming environment, where the same program is executed in multiple cores, on different test cases, there is a significant potential of target information reuse for indirect branches, as is evident from our experiments on SPEC 2006 workloads. This is typically useful for machine learning based workloads where the training phase is often executed in different cores with the same neural network being trained on different training sets. On the other hand, with different programs in different cores, there is some chance of reuse as well, due to sharing of system libraries. The essence of our idea rests on the fact that programs executed in different cores have similar history patterns that can similarly influence the target addresses. Our design aims to decrease on the on-chip L1 BTB size while investing more storage for the off-chip shared L2 BTB. Suitable allocation and replacement policies support our hierarchical design. Initial experiments show expected accuracy benefits.


title: Translating Traditional SIMD Instructions to Vector Length Agnostic Architectures

authors:
Sheng-Yu Fu
Wei-Chung Hsu

abstract: One interesting trend of SIMD architecture is towards Vector Length Agnostic (VLA) designs. For example, ARM new vector ISA, Scalable Vector Extension (SVE), and RISC-V vector extension are adopting such a direction. VLA decouples the vector register length from the compiled binary so that the same executable could run on different implementations of vector length. However, in the current application world, the majority of SIMD code is fixed-length based, such as ARM-NEON, x86- SSE, x86-AVX, and traditional vector machines. Therefore, how to migrate legacy SIMD code to VLA architecture would be an interesting and important technical challenge.


title: Code Generation from Formal Models for Automatic RTOS Portability

authors:
Renata Martins Gomes
Marcel Baunach

abstract: Current approaches for portability of real-time operating systems (RTOSs) for embedded systems are largely based on manual coding, which is arduous and error prone. With increasing dependability requirements for cyber physical systems, specially within the Internet of Things (IoT), along with the expected great diversity of hardware platforms, software platforms will only remain competitive in the long run if they guarantee correct operation and easy deployment to every hardware platform. In this scenario, a new approach to the development and portability of RTOSs that guarantees correct implementations for all current and future devices and hardware architectures becomes indispensable.We present a framework for automatic RTOS portability that integrates model-based design and formal methods into dependable embedded software development. We focus specially on modeling the interaction between software and hardware in order to generate low-level code. This enables automatic portability for hardware-related parts of the OS (i.e., context switching, memory management, security aspects, etc,) as well as for on-chip peripheral drivers (i.e., timers, I/O, etc.).With our framework we will be able to prove the consistency of the refinements as well as that the RTOS model fulfills various functional and non-functional requirements. Automatic code generation guarantees that the model is correctly translated to machine language, avoiding implementation mistakes common to manual coding. Changes on the software, for bug fixes or testing of new concepts, for example, do not require knowledge of the target architectures, since they are done on the model and are immediately reflected in all implementations upon code generation, assuring consistency across platforms.


title: Automatic Generation of Warp-Level Primitives and Atomic Instructions for Fast and Portable Parallel Reduction on GPUs

authors:
Simon Garcia De Gonzalo
Sitao Huang
Juan Gómez-Luna
Simon D. Hammond
Onur Mutlu
Wen-Mei Hwu

abstract: Since the advent of GPU computing, GPU hardware has evolved at a fast pace. Since application performance heavily depends on the latest hardware improvements, performance portability is extremely challenging for GPU application library developers. Portability becomes even more difficult when new low-level instructions are added to the ISA (e.g., warp shuffle instructions) or the microarchitectural support for existing instructions is improved (e.g., atomic instructions). Library developers, besides re-tuning the code for new hardware features, deal with the performance portability issue by hand-writing multiple algorithm versions that leverage different instruction sets and microarchitectures. High-level programming frameworks and Domain Specific Languages (DSLs) do not typically support lowlevel instructions (e.g., warp shuffle and atomic instructions), so it is painful or even impossible for these programming systems to take advantage of the latest architectural improvements. In this work, we design a new set of high-level APIs and qualifiers, as well as specialized Abstract Syntax Tree (AST) transformations for high-level programming languages and DSLs. Our transformations enable warp shuffle instructions and atomic instructions (on global and shared memories) to be easily generated. We show a practical implementation of these transformations by building on Tangram, a high-level kernel synthesis framework. Using our new language and compiler extensions, we implement parallel reduction, a fundamental building block used in a wide range of algorithms. Parallel reduction is representative of the performance portability challenge, as its performance heavily depends on the latest hardware improvements. We compare our synthesized parallel reduction to another high-level programming framework and a hand-written high-performance library across three generations of GPU architectures, and show up to 7.8× speedup (2× on average) over hand-written code.


title: Decoding CUDA Binary

authors:
Ari B. Hayes
Fei Hua
Jin Huang
Yan-Hao Chen
Eddy Z. Zhang

abstract: NVIDIA's software does not offer translation of assembly code to binary for their GPUs, since the specifications are closed-source. This work fills that gap. We develop a systematic method of decoding the Instruction Set Architectures (ISAs) of NVIDIA's GPUs, and generating assemblers for different generations of GPUs. Our framework enables cross-architecture binary analysis and transformation. Making the ISA accessible in this manner opens up a world of opportunities for developers and researchers, enabling numerous optimizations and explorations that are unachievable at the source-code level. Our infrastructure has already benefited and been adopted in important applications including performance tuning, binary instrumentation, resource allocation, and memory protection.


title: Translating CUDA to OpenCL for Hardware Generation using Neural Machine Translation

authors:
Yonghae Kim
Hyesoon Kim

abstract: Hardware generation from high-level languages like C/C++ has been one of the dreams of software and hardware engineers for decades. Several high-level synthesis (HLS) or domain-specific languages (DSLs) have been developed to reduce the gap between high-level languages and hardware descriptive languages. However, each language tends to target some specific applications or there is a big learning curve in learning DSLs, which ends up having many program languages and tool chains.To address these challenges, we propose the use of a source-to-source translation to pick and choose which framework to use so that the hardware designer chooses the best target HLS/DSL that can be synthesized to the best performing hardware. In this work, we present source-to-source translation between CUDA to OpenCL using NMT, which we call PLNMT. The contribution of our work is that it develops techniques to generate training inputs. To generate a training dataset, we extract CUDA API usages from CUDA examples and write corresponding OpenCL API usages. With a pair of API usages acquired, we construct API usage trees that helps users find unseen usages from new samples and easily add them to a training input. Our initial results show that we can translate many applications from benchmarks such as CUDA SDK, polybench-gpu, and Rodinia. Furthermore, we show that translated kernel code from CUDA applications can be run in the OpenCL FPGA framework, which implies a new direction of HLS.


title: A Code Generator for High-Performance Tensor Contractions on GPUs

authors:
Jinsung Kim
Aravind Sukumaran-Rajam
Vineeth Thumma
Sriram Krishnamoorthy
Ajay Panyala
Louis-Noël Pouchet
Atanas Rountev
P. Sadayappan

abstract: Tensor contractions are higher dimensional generalizations of matrix-matrix multiplication. They form the compute-intensive core of many applications in computational science and data science. In this paper, we describe a high-performance GPU code generator for arbitrary tensor contractions. It exploits domain-specific properties about data reuse in tensor contractions to devise an effective code generation schema, coupled with an effective model-driven search, to determine parameters for mapping of computation to threads and staging of data through the GPU memory hierarchy. Experimental evaluation using a set of tensor contraction benchmarks demonstrates performance improvement and/or significantly reduced code generation time over other state-of-the-art tensor contraction libraries and code generators.


title: Tensor Algebra Compilation with Workspaces

authors:
Fredrik Kjolstad
Willow Ahrens
Shoaib Kamil
Saman P. Amarasinghe

abstract: This paper shows how to extend sparse tensor algebra compilers to introduce temporary tensors called workspaces to avoid inefficient sparse data structures accesses. We develop an intermediate representation (IR) for tensor operations called concrete index notation that specifies when sub-computations occur and where they are stored. We then describe the workspace transformation in this IR, how to programmatically invoke it, and how the IR is compiled to sparse code. Finally, we show how the transformation can be used to optimize sparse tensor kernels, including sparse matrix multiplication, sparse tensor addition, and the matricized tensor times Khatri-Rao product (MTTKRP). Our results show that the workspace transformation brings the performance of these kernels on par with hand-optimized implementations. For example, we improve the performance of MTTKRP with dense output by up to 35%, and enable generating sparse matrix multiplication and MTTKRP with sparse output, neither of which were supported by prior tensor algebra compilers.


title: Extending LLVM for Lightweight SPMD Vectorization: Using SIMD and Vector Instructions Easily from Any Language

authors:
Robin Kruppe
Julian Oppermann
Lukas Sommer
Andreas Koch

abstract: Popular language extensions for parallel programming such as OpenMP or CUDA require considerable compiler support and runtime libraries and are therefore only available for a few programming languages and/or targets. We present an approach to vectorizing kernels written in an existing general-purpose language that requires minimal changes to compiler front-ends. Programmers annotate parallel (SPMD) code regions with a few intrinsic functions, which then guide an ordinary automatic vectorization algorithm. This mechanism allows programming SIMD and vector processors effectively while avoiding much of the implementation complexity of more comprehensive and powerful approaches to parallel programming. Our prototype implementation, based on a custom vectorization pass in LLVM, is integrated into C, C++ and Rust compilers using only 29-37 lines of frontend-specific code each.


title: White-Box Program Tuning

authors:
Wen-Chuan Lee
Yingqi Liu
Peng Liu
Shiqing Ma
Hongjun Choi
Xiangyu Zhang
Rajiv Gupta

abstract: Many programs or algorithms are largely parameterized, especially those based on heuristics. The quality of the results depends on the parameter setting. Different inputs often have different optimal settings. Program tuning is hence of great importance. Existing tuning techniques treat the program as a black-box and hence cannot leverage the internal program states to achieve better tuning. We propose a white-box tuning technique that is implemented as a library. The user can compose complex program tuning tasks by adding a small number of library calls to the original program and providing a few callback functions. Our experiments on 13 widely-used real-world programs show that our technique substantially improves data processing results and outperforms OpenTuner, the state-of-the-art black-box tuning technique.


title: Accelerating GPU Computing at Runtime with Binary Optimization

authors:
Guangli Li
Lei Liu
Xiaobing Feng

abstract: Nowadays, many applications use GPUs (Graphics Processing Units) to achieve high performance. When we use GPU servers, the idle CPU resource of the servers is often ignored. In this paper, we explore the idea: using the idle CPU resource to speed up GPU programs. We design a dynamic binary optimization framework for accelerating GPU computing at runtime. A template-based binary optimization method is proposed to optimize kernels, which can avoid the high cost of kernel compilation. This method replaces determined variables with constant values and generates an optimized binary kernel. Based on the analysis results of optimization opportunities, we replace the original kernels with optimized kernels during program execution. The experimental results show that it is feasible to accelerate GPU programs via binary optimization. After applying binary optimization to five convolution layers of deep neural networks, the average performance improvement can reach 20%.


title: Automatic Equivalence Checking for Assembly Implementations of Cryptography Libraries

authors:
Jay P. Lim
Santosh Nagarakatte

abstract: This paper presents an approach and a tool, CASM-VERIFY, to automatically check the equivalence of highly optimized assembly implementations of cryptographic algorithms. The key idea of this paper is to decompose the equivalence checking problem into several small sub-problems using a combination of concrete and symbolic evaluation. Given a reference and an optimized implementation, CASM-VERIFY concretely executes the two implementations on randomly generated inputs and identifies likely equivalent variables. Subsequently, it uses symbolic verification using an SMT solver to determine whether the identified variables are indeed equivalent. Further, it decomposes the original query into small sub-queries using a collection of optimizations for memory accesses. These techniques enable CASM-VERIFY to verify the equivalence of assembly implementations (e.g., x86 and SSE) of various algorithms such as SHA-256, ChaCha20, and AES-128 for a message block.


title: CSOD: Context-Sensitive Overflow Detection

authors:
Hongyu Liu
Sam Silvestro
Xiaoyin Wang
Lide Duan
Tongping Liu

abstract: Buffer overflow is possibly the most well-known memory issue. It can cause erratic program behavior, such as incorrect outputs and crashes, and can be exploited to issue security attacks. Detecting buffer overflows has drawn significant research attention for almost three decades. However, the prevalence of security attacks due to buffer overflows indicates that existing tools are still not widely utilized in production environments, possibly due to their high performance overhead or limited effectiveness. This paper proposes CSOD, a buffer overflow detection tool designed for the production environment. CSOD proposes a novel context-sensitive overflow detection technique that can dynamically adjust its detection strategy based on the behavior of different allocation calling contexts, enabling it to effectively detect overflows in millions of objects via four hardware watchpoints. It can correctly report root causes of buffer over-writes and over-reads, without any additional manual effort. Furthermore, CSOD only introduces 6.7% performance overhead on average, which makes it appealing as an always-on approach for production software.


title: Kernel Fusion/Decomposition for Automatic GPU-Offloading

authors:
Alok Mishra
Martin Kong
Barbara M. Chapman

abstract: 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.


title: Quantifying and Reducing Execution Variance in STM via Model Driven Commit Optimization

authors:
Girish Mururu
Ada Gavrilovska
Santosh Pande

abstract: Simplified parallel programming coupled with an ability to express speculative computation is realized with Software Transactional Memory (STM). Although STMs are gaining popularity because of significant improvements in parallel performance, they exhibit enormous variation in transaction execution with non-repeatable performance behavior which is unacceptable in many application domains, especially in which frame rates and responsiveness should be predictable. In other domains reproducible transactional behavior helps towards system provisioning. Thus, reducing execution variance in STM is an important performance goal that has been mostly overlooked. In this work, we minimize the variance in execution time of threads in STM by reducing non-determinism exhibited due to speculation. We define the state of STM, and we use it to first quantity non-determinism and then generate an automaton that models the execution behavior of threads in STM. We finally use the state automaton to guide the STM to avoid non-predictable transactional behavior thus reducing non-determinism in roll-backs which in turn results in reduction in variance. We observed average reduction of variance in execution time of threads up to 74% in 16 cores and 53% in 8 cores by reducing non-determinism up to 24% in 16 cores and 44% in 8 cores, respectively, on STAMP benchmark suite while experiencing average slowdown of 4.8% in 8 cores and 19.2% in 16 cores. We also reduced the variance in frame rate by maximum of 65% on a version of real world game Quake3 without degradation in timing.


title: Understanding RDMA Behavior in NUMA Systems

authors:
Jacob Nelson
Roberto Palmieri

abstract: Most high performance computing clusters are nowadays composed of large multicore machines that expose Non-Uniform Memory Access (NUMA), and they are interconnected using modern communication paradigms, such as Remote Direct Memory Access (RDMA). In this work we perform a study outlining the performance impact of these two technologies, NUMA and RDMA, when combined. Findings show that system's software architecture should be designed for NUMA and RDMA; otherwise major performance penalties occur.


title: Automatic Parallelization of Irregular x86-64 Loops

authors:
Brandon Neth
Michelle Mills Strout

abstract: Productivity languages such as Python and R are growing in popularity especially in the development of data analysis algorithms. While these languages provide powerful tools to accelerate the development process, they incur heavy overhead due to their interpreted nature. One approach to remove this overhead is to specialize the interpreter for a given script. Then, loops in the specialized code can be parallelized to further improve performance. In contrast to previous work that targets LLVM loops with affine memory access patterns, we are investigating the problem of parallelizing loops with irregular access patterns at the x86 level. To do so, we split hot loops into a sequential master thread that sends tasks to parallel worker threads.


title: BOLT: A Practical Binary Optimizer for Data Centers and Beyond

authors:
Maksim Panchenko
Rafael Auler
Bill Nell
Guilherme Ottoni

abstract: Performance optimization for large-scale applications has recently become more important as computation continues to move towards data centers. Data-center applications are generally very large and complex, which makes code layout an important optimization to improve their performance. This has motivated recent investigation of practical techniques to improve code layout at both compile time and link time. Although post-link optimizers had some success in the past, no recent work has explored their benefits in the context of modern data-center applications. In this paper, we present BOLT, an open-source post-link optimizer built on top of the LLVM framework. Utilizing sample-based profiling, BOLT boosts the performance of real-world applications even for highly optimized binaries built with both feedback-driven optimizations (FDO) and link-time optimizations (LTO). We demonstrate that post-link performance improvements are complementary to conventional compiler optimizations, even when the latter are done at a whole-program level and in the presence of profile information. We evaluated BOLT on both Facebook data-center workloads and open-source compilers. For data-center applications, BOLT achieves up to 7.0% performance speedups on top of profile-guided function reordering and LTO. For the GCC and Clang compilers, our evaluation shows that BOLT speeds up their binaries by up to 20.4% on top of FDO and LTO, and up to 52.1% if the binaries are built without FDO and LTO.


title: Super-Node SLP: Optimized Vectorization for Code Sequences Containing Operators and Their Inverse Elements

authors:
Vasileios Porpodas
Rodrigo C. O. Rocha
Evgueni Brevnov
Luís F. W. Góes
Timothy G. Mattson

abstract: SLP Auto-vectorization converts straight-line code into vector code. It scans input code for groups of instructions that can be combined into vectors and replaces them with their corresponding vector instructions. This work introduces Super-Node SLP (SN-SLP), a new SLP-style algorithm, optimized for expressions that include a commutative operator (such as addition) and its corresponding inverse element (subtraction). SN-SLP uses the algebraic properties of commutative operators and their inverse elements to enable additional transformations that extend auto-vectorization to cases difficult for state-of-the-art auto-vectorizing compilers. We implemented SN-SLP in LLVM. Our evaluation on a real system demonstrates considerable performance improvements of benchmark code with no significant change in compilation time.


title: An Optimization-Driven Incremental Inline Substitution Algorithm for Just-in-Time Compilers

authors:
Aleksandar Prokopec
Gilles Duboscq
David Leopoldseder
Thomas Würthinger

abstract: Inlining is one of the most important compiler optimizations. It reduces call overheads and widens the scope of other optimizations. But, inlining is somewhat of a black art of an optimizing compiler, and was characterized as a computationally intractable problem. Intricate heuristics, tuned during countless hours of compiler engineering, are often at the core of an inliner implementation. And despite decades of research, well established inlining heuristics are still missing. In this paper, we describe a novel inlining algorithm for JIT compilers that incrementally explores a program's call graph, and alternates between inlining and optimizations. We devise three novel heuristics that guide our inliner: adaptive decision thresholds, callsite clustering, and deep inlining trials. We implement the algorithm inside Graal, a dynamic JIT compiler for the HotSpot JVM. We evaluate our algorithm on a set of industry-standard benchmarks, including Java DaCapo, Scalabench, Spark-Perf, STMBench7 and other benchmarks, and we conclude that it significantly improves performance, surpassing state-of-the-art inlining approaches with speedups ranging from 5% up to 3×.


title: From Loop Fusion to Kernel Fusion: A Domain-Specific Approach to Locality Optimization

authors:
Bo Qiao
Oliver Reiche
Frank Hannig
Jürgen Teich

abstract: Optimizing data-intensive applications such as image processing for GPU targets with complex memory hierarchies requires to explore the tradeoffs among locality, parallelism, and computation. Loop fusion as one of the classical optimization techniques has been proven effective to improve locality at the function level. Algorithms in image processing are increasing their complexities and generally consist of many kernels in a pipeline. The inter-kernel communications are intensive and exhibit another opportunity for locality improvement at the system level. The scope of this paper is an optimization technique called kernel fusion for data locality improvement. We present a formal description of the problem by defining an objective function for locality optimization. By transforming the fusion problem to a graph partitioning problem, we propose a solution based on the minimum cut technique to search fusible kernels recursively. In addition, we develop an analytic model to quantitatively estimate potential locality improvement by incorporating domain-specific knowledge and architecture details. The proposed technique is implemented in an image processing DSL and source-to-source compiler called Hipacc, and evaluated over six image processing applications on three Nvidia GPUs. A geometric mean speedup of up to 2.52 can be observed in our experiments.


title: Function Merging by Sequence Alignment

authors:
Rodrigo C. O. Rocha
Pavlos Petoumenos
Zheng Wang
Murray Cole
Hugh Leather

abstract: Resource-constrained devices for embedded systems are becoming increasingly important. In such systems, memory is highly restrictive, making code size in most cases even more important than performance. Compared to more traditional platforms, memory is a larger part of the cost and code occupies much of it. Despite that, compilers make little effort to reduce code size. One key technique attempts to merge the bodies of similar functions. However, production compilers only apply this optimization to identical functions, while research compilers improve on that by merging the few functions with identical control-flow graphs and signatures. Overall, existing solutions are insufficient and we end up having to either increase cost by adding more memory or remove functionality from programs. We introduce a novel technique that can merge arbitrary functions through sequence alignment, a bioinformatics algorithm for identifying regions of similarity between sequences. We combine this technique with an intelligent exploration mechanism to direct the search towards the most promising function pairs. Our approach is more than 2.4x better than the state-of-the-art, reducing code size by up to 25%, with an overall average of 6%, while introducing an average compilation-time overhead of only 15%. When aided by profiling information, this optimization can be deployed without any significant impact on the performance of the generated code.


title: Generation of In-Bounds Inputs for Arrays in Memory-Unsafe Languages

authors:
Marcus Rodrigues
Breno Guimarães
Fernando Magno Quintão Pereira

abstract: This paper presents a technique to generate in-bounds inputs for arrays used in memory-unsafe programming languages, such as C and C++. We show that most memory indexation found in actual C programs follows patterns that are easy to analyze statically. Based on this observation, we show how symbolic range analysis can be used to establish contracts between the arguments of a function and the arrays used within that function. To demonstrate the effectiveness of our ideas, we use them to implement Griffin-TG, a tool to stress-test C programs whose source code might be partially available. We show how Griffin-TG improves Aprof, a well-known algorithmic profiling tool, and we show how it lets us enrich PolyBench with a large set of new inputs.


title: Reasoning about the Node.js Event Loop using Async Graphs

authors:
Haiyang Sun
Daniele Bonetta
Filippo Schiavio
Walter Binder

abstract: With the popularity of Node.js, asynchronous, event-driven programming has become widespread in server-side applications. While conceptually simple, event-based programming can be tedious and error-prone. The complex semantics of the Node.js event loop, coupled with the different flavors of asynchronous execution in JavaScript, easily leads to bugs. This paper introduces a new model called Async Graph to reason about the runtime behavior of applications and their interactions with the Node.js event loop. Based on the model, we have developed AsyncG, a tool to automatically build and analyze the Async Graph of a running application, and to identify bugs related to all sources of asynchronous execution in Node.js. AsyncG is compatible with the latest ECMAScript language features and can be (de)activated at runtime. In our evaluation, we show how AsyncG can be used to identify bugs in real-world Node.js applications.


title: Locus: A System and a Language for Program Optimization

authors:
Thiago S. F. X. Teixeira
Corinne Ancourt
David A. Padua
William Gropp

abstract: We discuss the design and the implementation of Locus, a system and a language to orchestrate the optimization of applications. The increasing complexity of machines and the large space of program variants, produced by the many transformations available, conspire to make compilers deliver unsatisfactory performance. As a result, optimization experts must intervene to manually explore the space of program variants seeking the best version for each target machine. This intervention is unproductive, and maintaining and managing sequences of transformations as new architectures are adopted and new application features are incorporated is challenging.Locus allows collections of program transformation sequences to be specified separately from the application code. The language is able to represent in a clear notation complex collections of transformations that are applied to code regions selected by the programmer. The system integrates multiple optimization modules as well as search modules that facilitate the efficient traversal of the space of program variants. Locus is intended to help experts in the optimization process, specially for complex, long-lived applications that are to be executed on different environments. Four examples are presented to illustrate the power and simplicity of the language. Although not the primary focus of this paper, the examples also show that exploring the space of variants typically leads to better performing codes than those produced by conventional compiler optimizations that are based on heuristics.


title: Transforming Query Sequences for High-Throughput B+ Tree Processing on Many-Core Processors

authors:
Ruiqin Tian
Junqiao Qiu
Zhijia Zhao
Xu Liu
Bin Ren

abstract: The throughput of B+ tree query processing is critical to many databases, file systems, and cloud applications. Based on bulk synchronous parallel (BSP), latch-free B+ tree query processing has shown promise by processing queries in small batches and avoiding the use of locks. As the number of cores on CPUs increases, it becomes possible to process larger batches in parallel without adding any extra delays. In this work, we argue that as the batch size increases, there will be more optimization opportunities exposed beyond parallelism, especially when the query distributions are highly skewed. These include the opportunities of avoiding the evaluations of a large ratio of redundant or unnecessary queries. To rigorously exploit the new opportunities, this work introduces a query sequence analysis and transformation framework - QTrans. QTrans can systematically reason about the redundancies at a deep level and automatically remove them from the query sequence. QTrans has interesting resemblances with the classic data-flow analysis and transformation that have been widely used in compilers. To confirm its benefits, this work integrates QTrans into an existing BSP-based B+ tree query processing system, PALM tree, to automatically eliminate redundant and unnecessary queries1. Evaluation shows that, by transforming the query sequence, QTrans can substantially improve the throughput of query processing on both real-world and synthesized datasets, up to 16X.


title: Optimizing RNA-RNA Interaction Computations

abstract: RNA-RNA (Ribo-Nucleic Acid) Interactions (RRI) has led to significant successes in Cancer treatment. However, programs that model these interactions are computationally and memory intensive: for sequences of lengths N and M, space is Θ(N2M2), and the time is Θ(N3M3). Conducting genomewide RNA-RNA interactions can take forever. Therefore, there is a need to speed up these computations. On examining two RRI applications (piRNA and IRIS), we find that the dominant computations fit the polyhedral model, a widely accepted tool for loop nest optimization. Applying existing automatic polyhedral tools on this whole application is near to impossible. Hence, we analyzed a surrogate kernel that captures the main dependence pattern found in piRNA and IRIS. But even on this kernel, a stateof-the-art automatic polyhedral, Pluto does not significantly improve the performance of the baseline implementation. Whereas, with simple manual loop permutation and skewing techniques, we were able to achieve an average of 17× (sequential) and 112× (parallel on a 6-core Intel Broadwell processor) speed-up over the baseline. This performance represents 75% (respectively, 88%) of attainable single-core and multi-core L1 bandwidth. Preliminary results from tiling show that there is a room for two-three fold improvement when the data foot-print required to compute the inner three loop dimensions fit in the main memory.


title: Janus: Statically-Driven and Profile-Guided Automatic Dynamic Binary Parallelisation

authors:
Ruoyu Zhou
Timothy M. Jones

abstract: We present Janus, a framework that addresses the challenge of automatic binary parallelisation. Janus uses same-ISA dynamic binary modification to optimise application binaries, controlled by static analysis with judicious use of software speculation and runtime checks that ensure the safety of the optimisations. A static binary analyser first examines a binary executable, to determine the loops that are amenable to parallelisation and the transformations required. These are encoded as a series of rewrite rules, the steps needed to convert a serial loop into parallel form. The Janus dynamic binary modifier reads both the original executable and rewrite rules and carries out the transformations on a per-basic-block level just-in-time before execution. Lifting static analysis out of the runtime enables the global and profile-guided views of the application; ambiguities from static binary analysis can in turn be addressed through a combination of dynamic runtime checks and speculation guard against data dependence violations. It allows us to parallelise even those loops containing dynamically discovered code. We demonstrate Janus by parallelising a range of optimised SPEC CPU 2006 benchmarks, achieving average speedups of 2.1$\times$ and 6.0$\times$ in the best case.


title: A Tool for Performance Analysis of GPU-Accelerated Applications

authors:
Keren Zhou
John M. Mellor-Crummey

abstract: Architectures for High-Performance Computing (HPC) now commonly employ accelerators such as Graphics Processing Units (GPUs). High-level programming abstractions for accelerated computing include OpenMP as well as RAJA and Kokkos—programming abstractions based on C++ templates. Such programming models hide GPU architectural details and generate sophisticated GPU code organized as many small procedures. For example, a dot product kernel expressed using RAJA atop NVIDIA’s thrust templates yields 35 procedures. Existing performance tools are ill-suited for analyzing such complex kernels because they lack a comprehensive profile view. At best, tools such as NVIDIA’s nvvp provide a profile view that shows only limited CPU calling contexts and omits both calling contexts and loops in GPU code. To address this problem, we extended Rice University’s HPCToolkit to build a complete profile view for GPU-accelerated applications.


title: ATMem: adaptive data placement in graph applications on heterogeneous memories

authors:
Yu Chen
Ivy Bo Peng
Zhen Peng
Xu Liu
Bin Ren

abstract: Active development in new memory devices, such as non-volatile memories and high-bandwidth memories, brings heterogeneous memory systems (HMS) as a promising solution for implementing large-scale memory systems with cost, area, and power limitations. Typical HMS consists of a small-capacity high-performance memory and a large-capacity low-performance memory. Data placement on such systems plays a critical role in performance optimization. Existing efforts have explored coarse-grained data placement in applications with dense data structures; however, a thorough study of applications that are based on graph data structures is still missing.


title: Type freezing: exploiting attribute type monomorphism in tracing JIT compilers

authors:
Lin Cheng
Berkin Ilbeyi
Carl Friedrich Bolz-Tereick
Christopher Batten

abstract: Dynamic programming languages continue to increase in popularity. While just-in-time (JIT) compilation can improve the performance of dynamic programming languages, a significant performance gap remains with respect to ahead-of-time compiled languages. Existing JIT compilers exploit type monomorphism through type specialization, and use runtime checks to ensure correctness. Unfortunately, these checks can introduce non-negligible overhead. In this paper, we present type freezing, a novel software solution for exploiting attribute type monomorphism. Type freezing "freezes" type monomorphic attributes of user-defined types, and eliminates the necessity of runtime type checks when performing reads from these attributes. Instead, runtime type checks are done when writing these attributes to validate type monomorphism. We implement type freezing as an extension to PyPy, a state-of-the-art tracing JIT compiler for Python. Our evaluation shows type freezing can improve performance and reduce dynamic instruction count for those applications with a significant number of attribute accesses.


title: Automatic generation of high-performance quantized machine learning kernels

authors:
Meghan Cowan
Thierry Moreau
Tianqi Chen
James Bornholt
Luis Ceze

abstract: Quantization optimizes machine learning inference for resource constrained environments by reducing the precision of its computation. In the extreme, even single-bit computations can produce acceptable results at dramatically lower cost. But this ultra-low-precision quantization is difficult to exploit because extracting optimal performance requires hand-tuning both high-level scheduling decisions and low-level implementations. As a result, practitioners settle for a few predefined quantized kernels, sacrificing optimality and restricting their ability to adapt to new hardware.


title: The design and implementation of the wolfram language compiler

authors:
Abdul Dakkak
Tom Wickham-Jones
Wen-Mei Hwu

abstract: The popularity of data- and scientific-oriented applications, abundance of on-demand compute resources, and scarcity of domain expert programmers have given rise to high-level scripting languages. These high-level scripting languages offer a fast way to translate ideas into code, but tend to pay a heavy performance overhead. In order to alleviate the performance penalty, each implementation of these languages often offers a compilation path to a subset of the language.


title: Speculative reconvergence for improved SIMT efficiency

authors:
Sana Damani
Daniel R. Johnson
Mark Stephenson
Stephen W. Keckler
Eddie Q. Yan
Michael McKeown
Olivier Giroux

abstract: GPUs perform most efficiently when all threads in a warp execute the same sequence of instructions convergently. However, when threads in a warp encounter a divergent branch, the hardware serializes the execution of diverged paths. We consider a class of convergence opportunities wherein multiple threads are expected to eventually execute a given segment of code, but not all threads arrive at the same time, resulting in serialized duplicate execution of common code subsequences such as function calls and loop bodies. Our goal is to promote convergence by helping threads that execute common code arrive together before allowing execution to proceed. We propose a new user-guided compiler mechanism, Speculative Reconvergence, to help identify and exploit previously untapped convergence opportunities that increase SIMT efficiency and improve performance. For the set of workloads we study, we see improvements ranging from 10% to 3× in both SIMT efficiency and in performance.


title: SIMD support in .NET: abstract and concrete vector types and operations

authors:
Carol Eidt
Tanner Gooding

abstract: This paper describes SIMD (Single Instruction Multiple Data) APIs for .NET that expose the parallel execution capabilities available on modern processors. These APIs include both platform-independent and platform-specific APIs that expose the SIMD capabilities available on the target hardware. The platform-independent APIs abstract both the element type and length of the maximum width vector available on the target hardware, while the platform-specific APIs are a more direct mapping to the target instructions. The APIs are consumable by high-level languages such as C# and F#, and the just in time compiler (JIT) for .NET translates the operations to the appropriate hardware instructions directly in the referencing method, avoiding overhead due to calls or managed/native transitions.


title: NeuroVectorizer: end-to-end vectorization with deep reinforcement learning

authors:
Ameer Haj-Ali
Nesreen K. Ahmed
Theodore L. Willke
Yakun Sophia Shao
Krste Asanovic
Ion Stoica

abstract: One of the key challenges arising when compilers vectorize loops for today’s SIMD-compatible architectures is to decide if vectorization or interleaving is beneficial. Then, the compiler has to determine the number of instructions to pack together and the interleaving level (stride). Compilers are designed today to use fixed-cost models that are based on heuristics to make vectorization decisions on loops. However, these models are unable to capture the data dependency, the computation graph, or the organization of instructions. Alternatively, software engineers often hand-write the vectorization factors of every loop. This, however, places a huge burden on them, since it requires prior experience and significantly increases the development time.


title: Efficient nursery sizing for managed languages on multi-core processors with shared caches

authors:
Mohamed Ismail
G. Edward Suh

abstract: In modern programming languages, automatic memory management has become a standard feature for allocating and freeing memory. In this paper, we show that the performance of today’s managed languages can degrade significantly due to cache contention among multiple concurrent applications that share a cache. To address this problem, we propose to change the programs’ memory access patterns by adjusting the nursery size. We propose Dynamic Nursery Allocator (DNA), an online dynamic scheme that automatically adjusts the nursery sizes of multiple managed-language programs running concurrently without any prior knowledge or offline profiling. The experimental results on a native Intel machine show that DNA can significantly improve the system throughput by 16.3% on average and as much as 73% over today’s nursery sizing scheme when four applications run concurrently sharing the last-level cache.