title: Run-Time Support for Optimizations Based on Escape Analysis

authors:
Thomas Kotzmann
Hanspeter Mössenböck

abstract: We implemented a new escape analysis algorithm for Sun Microsystems' Java HotSpottrade VM. The results are used to replace objects with scalar variables, to allocate objects on the stack, and to remove synchronization. This paper deals with the representation of optimized objects in the debugging information and with reallocation and garbage collection support for a safe execution of optimized methods. Assignments to fields of parameters that can refer to both stack and heap objects are associated with an extended write barrier which skips card marking for stack objects. The traversal of objects during garbage collection uses a wrapper that abstracts from stack objects and presents their pointer fields as root pointers to the garbage collector


venue: cgo

title: Evaluating Heuristic Optimization Phase Order Search Algorithms

authors:
Prasad A. Kulkarni
David B. Whalley
Gary S. Tyson

abstract: Program-specific or function-specific optimization phase sequences are universally accepted to achieve better overall performance than any fixed optimization phase ordering. A number of heuristic phase order space search algorithms have been devised to find customized phase orderings achieving high performance for each function. However, to make this approach of iterative compilation more widely accepted and deployed in mainstream compilers, it is essential to modify existing algorithms, or develop new ones that find near-optimal solutions quickly. As a step in this direction, in this paper we attempt to identify and understand the important properties of some commonly employed heuristic search methods by using information collected during an exhaustive exploration of the phase order search space. We compare the performance obtained by each algorithm with all others, as well as with the optimal phase ordering performance. Finally, we show how we can use the features of the phase order space to improve existing algorithms as well as devise new, and better performing search algorithms.


title: Shadow Profiling: Hiding Instrumentation Costs with Parallelism

authors:
Tipp Moseley
Alex Shye
Vijay Janapa Reddi
Dirk Grunwald
Ramesh Peri

abstract: In profiling, a tradeoff exists between information and overhead. For example, hardware-sampling profilers incur negligible overhead, but the information they collect is consequently very coarse. Other profilers use instrumentation tools to gather temporal traces such as path profiles and hot memory streams, but they have high overhead. Runtime and feedback-directed compilation systems need detailed information to aggressively optimize, but the cost of gathering profiles can outweigh the benefits. Shadow profiling is a novel method for sampling long traces of instrumented code in parallel with normal execution, taking advantage of the trend of increasing numbers of cores. Each instrumented sample can be many millions of instructions in length. The primary goal is to incur negligible overhead, yet attain profile information that is nearly as accurate as a perfect profile. The profiler requires no modifications to the operating system or hardware, and is tunable to allow for greater coverage or lower overhead. We evaluate the performance and accuracy of this new profiling technique for two common types of instrumentation-based profiles: interprocedural path profiling and value profiling. Overall, profiles collected using the shadow profiling framework are 94% accurate versus perfect value profiles, while incurring less than 1% overhead. Consequently, this technique increases the viability of dynamic and continuous optimization systems by hiding the high overhead of instrumentation and enabling the online collection of many types of profiles that were previously too costly


title: Compiler-Directed Variable Latency Aware SPM Management to CopeWith Timing Problems

authors:
Ozcan Ozturk
Guilin Chen
Mahmut T. Kandemir
Mustafa Karaköy

abstract: This paper proposes and experimentally evaluates a compiler-driven approach that operates an on-chip scratch-pad memory (SPM) assuming different latencies for the different SPM lines. Our goal is to reduce execution cycles without creating any reliability problems due to variations in access latencies. The proposed scheme achieves its goal by evaluating the reuse of different data items and adopting a reuse and latency aware data-to-SPM placement. It also employs data migration within SPM when it helps to cut down the number of execution cycles further. We also discuss an alternate scheme that can reduce latency of select SPM locations by controlling a circuit level mechanism in software to further improve performance. We implemented our approach within an optimizing compiler and tested its effectiveness through extensive simulations. Our experiments with twelve embedded application codes show that the proposed approach performs much better than the worst-case based design paradigm (16.2% improvement on the average) and comes close (within 5.7%) to an hypothetical best-case design (i.e., one with no process variation) where every SMP locations uniformly have low latency


title: Iterative Optimization in the Polyhedral Model: Part I, One-Dimensional Time

authors:
Louis-Noël Pouchet
Cédric Bastoul
Albert Cohen
Nicolas Vasilache

abstract: Emerging microprocessors offer unprecedented parallel computing capabilities and deeper memory hierarchies, increasing the importance of loop transformations in optimizing compilers. Because compiler heuristics rely on simplistic performance models, and because they are bound to a limited set of transformations sequences, they only uncover a fraction of the peak performance on typical benchmarks. Iterative optimization is a maturing framework to address these limitations, but so far, it was not successfully applied complex loop transformation sequences because of the combinatorics of the optimization search space. We focus on the class of loop transformation which can be expressed as one-dimensional affine schedules. We define a systematic exploration method to enumerate the space of all legal, distinct transformations in this class. This method is based on an upstream characterization, as opposed to state-of-the-art downstream filtering approaches. Our results demonstrate orders of magnitude improvements in the size of the search space and in the convergence speed of a dedicated iterative optimization heuristic


title: Structure Layout Optimization for Multithreaded Programs

authors:
Easwaran Raman
Robert Hundt
Sandya Mannarswamy

abstract: Structure layout optimizations seek to improve runtime performance by improving data locality and reuse. The structure layout heuristics for single-threaded benchmarks differ from those for multi-threaded applications running on multiprocessor machines, where the effects of false sharing need to be taken into account. In this paper we propose a technique for structure layout transformations for multithreaded applications that optimizes both for improved spatial locality and reduced false sharing, simultaneously. We develop a semi-automatic tool that produces actual structure layouts for multi-threaded programs and outputs the key factors contributing to the layout decisions. We apply this tool on the HP-UX kernel and demonstrate the effects of these transformations for a variety of already highly hand-tuned key structures with different set of properties. We show that naive heuristics can result in massive performance degradations on such a highly tuned application, while our technique generally avoids those pitfalls. The improved structures produced by our tool improve performance by up to 3.2% over a highly tuned baseline


title: Persistent Code Caching: Exploiting Code Reuse Across Executions and Applications

authors:
Vijay Janapa Reddi
Dan Connors
Robert Cohn
Michael D. Smith

abstract: Run-time compilation systems are challenged with the task of translating a program's instruction stream while maintaining low overhead. While software managed code caches are utilized to amortize translation costs, they are ineffective for programs with short run times or large amounts of cold code. Such program characteristics are prevalent in real-life computing environments, ranging from graphical user interface (GUI) programs to large-scale applications such as database management systems. Persistent code caching addresses these issues. It is described and evaluated in an industry-strength dynamic binary instrumentation system - Pin. The proposed approach improves the intra-execution model of code reuse by storing and reusing translations across executions, thereby achieving inter-execution persistence. Dynamically linked programs leverage inter-application persistence by using persistent translations of library code generated by other programs. New translations discovered across executions are automatically accumulated into the persistent code caches, thereby improving performance over time. Inter-execution persistence improves the performance of GUI applications by nearly 90%, while inter-application persistence achieves a 59% improvement. In more specialized uses, the SPEC2K INT benchmark suite experiences a 26% improvement under dynamic binary instrumentation. Finally, a 400% speedup is achieved in translating the Oracle database in a regression testing environment


title: Microarchitecture Sensitive Empirical Models for Compiler Optimizations

authors:
Kapil Vaswani
Matthew J. Thazhuthaveetil
Y. N. Srikant
P. J. Joseph

abstract: This paper proposes the use of empirical modeling techniques for building microarchitecture sensitive models for compiler optimizations. The models we build relate program performance to settings of compiler optimization flags, associated heuristics and key microarchitectural parameters. Unlike traditional analytical modeling methods, this relationship is learned entirely from data obtained by measuring performance at a small number of carefully selected compiler/microarchitecture configurations. We evaluate three different learning techniques in this context viz. linear regression, adaptive regression splines and radial basis function networks. We use the generated models to a) predict program performance at arbitrary compiler/microarchitecture configurations, b) quantify the significance of complex interactions between optimizations and the microarchitecture, and c) efficiently search for 'optimal' settings of optimization flags and heuristics for any given micro architectural configuration. Our evaluation using benchmarks from the SPEC CPU2000 suites suggests that accurate models (< 5% average error in prediction) can be generated using a reasonable number of simulations. We also find that using compiler settings prescribed by a model-based search can improve program performance by as much as 19% (with an average of 9.5%) over highly optimized binaries


title: SuperPin: Parallelizing Dynamic Instrumentation for Real-Time Performance

authors:
Steven Wallace
Kim M. Hazelwood

abstract: Dynamic instrumentation systems have proven to be extremely valuable for program introspection, architectural simulation, and bug detection. Yet a major drawback of modern instrumentation systems is that the instrumented applications often execute several orders of magnitude slower than native application performance. In this paper, we present a novel approach to dynamic instrumentation where several non-overlapping slices of an application are launched as separate instrumentation threads and executed in parallel in order to approach real-time performance. A direct implementation of our technique in the Pin dynamic instrumentation system results in dramatic speedups for various instrumentation tasks - often resulting in order-of-magnitude performance improvements. Our implementation is available as part of the Pin distribution, which has been downloaded over 10,000 times since its release


title: Code Generation and Optimization for Transactional Memory Constructs in an Unmanaged Language

authors:
Cheng Wang
Wei-Yu Chen
Youfeng Wu
Bratin Saha
Ali-Reza Adl-Tabatabai

abstract: Transactional memory offers significant advantages for concurrency control compared to locks. This paper presents the design and implementation of transactional memory constructs in an unmanaged language. Unmanaged languages pose a unique set of challenges to transactional memory constructs - for example, lack of type and memory safety, use of function pointers, aliasing of local variables, and others. This paper describes novel compiler and runtime mechanisms that address these challenges and optimize the performance of transactions in an unmanaged environment. We have implemented these mechanisms in a production-quality C compiler and a high-performance software transactional memory runtime. We measure the effectiveness of these optimizations and compare the performance of lock-based versus transaction-based programming on a set of concurrent data structures and the SPLASH-2 benchmark suite. On a 16 processor SMP system, the transaction-based version of the SPLASH-2 benchmarks scales much better than the coarse-grain locking version and performs comparably to the fine-grain locking version. Compiler optimizations significantly reduce the overheads of transactional memory so that, on a single thread, the transaction-based version incurs only about 6.4% overhead compared to the lock-based version for the SPLASH-2 benchmark suite. Thus, our system is the first to demonstrate that transactions integrate well with an unmanaged language, and can perform as well as fine-grain locking while providing the programming ease of coarse-grain locking even on an unmanaged environment


title: Compiler-Managed Software-based Redundant Multi-Threading for Transient Fault Detection

authors:
Cheng Wang
Ho-Seop Kim
Youfeng Wu
Victor Ying

abstract: As transistors become increasingly smaller and faster with tighter noise margins, modern processors are becoming increasingly more susceptible to transient hardware faults. Existing hardware-based redundant multi-threading (HRMT) approaches rely mostly on special-purpose hardware to replicate the program into redundant execution threads and compare their computation results. In this paper, we present a software-based redundant multi-threading (SRMT) approach for transient fault detection. Our SRMT technique uses compiler to automatically generate redundant threads so they can run on general-purpose chip multi-processors (CMPs). We exploit high-level program information available at compile time to optimize data communication between redundant threads. Furthermore, our software-based technique provides flexible program execution environment where the legacy binary codes and the reliability-enhanced codes can co-exist in a mix-and-match fashion, depending on the desired level of reliability and software compatibility. Our experimental results show that compiler analysis and optimization techniques can reduce data communication requirement by up to 88% of HRMT. With general-purpose intra-chip communication mechanisms in CMP machine, SRMT overhead can be as low as 19%. Moreover, SRMT technique achieves error coverage rates of 99.98% and 99.6% for SPEC CPU2000 integer and floating-point benchmarks, respectively. These results demonstrate the competitiveness of SRMT to HRMT approaches


title: Ubiquitous Memory Introspection

authors:
Qin Zhao
Rodric M. Rabbah
Saman P. Amarasinghe
Larry Rudolph
Weng-Fai Wong

abstract: Modern memory systems play a critical role in the performance of applications, but a detailed understanding of the application behavior in the memory system is not trivial to attain. It requires time consuming simulations and detailed modeling of the memory hierarchy, often using long address traces. It is increasingly possible to access hardware performance counters to count relevant events in the memory system, but the measurements are coarse-grained and better suited for performance summaries than providing instruction level feedback. The availability of a low cost, online, and accurate methodology for deriving finegrained memory behavior profiles can prove extremely useful for runtime analysis and optimization of programs. This paper presents a new methodology for Ubiquitous Memory Introspection (UMI). It is an online and lightweight methodology that uses fast mini-simulations to analyze short memory access traces recorded from frequently executed code regions. The simulations provide profiling results at varying granularities, down to that of a single instruction or address. UMI naturally complements runtime optimizations and enables new opportunities for online memory specific optimizations. We present a prototype runtime system implementing UMI. The prototype has an average runtime overhead of 14%. This overhead is only 1% more than a state of the art binary instrumentation tool. We used 32 benchmarks, including the full suite of SPEC CPU2000 benchmarks, for evaluation. We show that the mini-simulations accurately reflect the cache performance of two existing memory systems, an Intel Pentium 4 and an AMD Athlon MP (K7). We also demonstrate that UMI predicts delinquent load instructions with an 88% rate of accuracy for applications with a relatively high number of cache misses, and 61% overall. The online profiling results are used at runtime to implement a simple software prefetching strategy that achieves an overall speedup of 64% in the best case.


title: Fast liveness checking for ssa-form programs

authors:
Benoit Boissinot
Sebastian Hack
Daniel Grund
Benoît Dupont de Dinechin
Fabrice Rastello

abstract: Liveness analysis is an important analysis in optimizing compilers. Liveness information is used in several optimizations and is mandatory during the code-generation phase. Two drawbacks of conventional liveness analyses are that their computations are fairly expensive and their results are easily invalidated by program transformations. We present a method to check liveness of variables that overcomes both obstacles. The major advantage of the proposed method is that the analysis result survives all program transformations except for changes in the control-flow graph. For common program sizes our technique is faster and consumes less memory than conventional data-flow approaches. Thereby, we heavily make use of SSA-form properties, which allow us to completely circumvent data-flow equation solving. We evaluate the competitiveness of our approach in an industrial strength compiler. Our measurements use the integer part of the SPEC2000 benchmarks and investigate the liveness analysis used by the SSA destruction pass. We compare the net time spent in liveness computations of our implementation against the one provided by that compiler. The results show that in the vast majority of cases our algorithm, while providing the same quality of information, needs less time: an average speed-up of 16%.


title: Prefetching irregular references for software cache on cell

authors:
Tong Chen
Tao Zhang
Zehra Sura
Marc González Tallada

abstract: The IBM Single Source Research Compiler for the Cell processor (the SSC Research Compiler) was developed to manage the complexity of programming the heterogeneous multicore Cell processor. The compiler accepts conventional source programs as input, and automatically generates binaries that execute on both the PPU and SPU cores available on a Cell chip. The compiler uses a software cache and direct buffers to manage data in the small local memory of SPUs. However, irregular references, such as a[ind[i]], often become performance bottle-necks. These references are accessed through software cache, usually with high miss rates. To solve this problem, we propose a method to prefetch irregular references accessed through a software cache that is built upon hardware such as Cell. This method includes code transformation in the compiler and a runtime library component for the software cache. Our design simplifies the synchronization required when prefetching into software cache, overlaps DMA operations for misses, and avoids frequent context switching to the miss handler. It also minimizes the cache pollution caused by prefetching, by looking both forwards and backwards through the sequence of addresses to be prefetched. We evaluated our prefetching method using the NAS benchmarks. We found that when applicable, our prefetching can improve the performance of some benchmarks by 2 times on average, and by close to 4 times in the best case. We also present data to show the impact of different configurations and optimizations when prefetching in a software cache.


title: Modulo scheduling for highly customized datapaths to increase hardware reusability

authors:
Kevin Fan
Hyunchul Park
Manjunath Kudlur
Scott A. Mahlke

abstract: In the embedded domain, custom hardware in the form of ASICs is often used to implement critical parts of applications when performance and energy efficiency goals cannot be met with software implementations on a general purpose processor or DSP. The downsides of using ASICs include high non-recurring engineering costs, inability to accommodate changes in the application after production, and inability to reuse hardware for new applications. However, by allowing a degree of post-programmability, the hardware can retain high performance and energy efficiency while increasing flexibility and reusability. The difficulty with programmable custom hardware lies in mapping new applications onto an existing datapath that is both sparse and irregular. This paper proposes a constraint-driven modulo scheduler that maps software-pipelineable loops onto programmable loop accelerator hardware. The scheduler is able to target accelerators with widely varying levels of datapath functional capability and connectivity, and thus, varying degrees of programmability. The paper investigates the ability of the scheduler to map new loops onto existing hardware, which depends on both the degree of programmability of the hardware as well as the similarity of the new loop to the original loop for which the hardware was designed.


title: Parallelism by design: data analysis with sawzall

abstract: Very large data sets - telephone call records, network logs, high-resolution satellite images, or web document repositories - are not easily analyzed using traditional database techniques. They may be simply too large, grow too fast, or may not fit well in a database schema. They tend to span multiple disks and machines. On the other hand, these large data sets often have a flat and regular structure that permits distributed filtering and aggregation.


title: Phase-based adaptive recompilation in a JVM

authors:
Dayong Gu
Clark Verbrugge

abstract: Modern JIT compilers often employ multi-level recompilation strategies as a means of ensuring the most used code is also the most highly optimized, balancing optimization costs and expected future performance. Accurate selection of code to compile and level of optimization to apply is thus important to performance. In this paper we investigate the effect of an improved recompilation strategy for a Java virtual machine. Our design makes use of a lightweight, low-level profiling mechanism to detect high-level, variable length phases in program execution. Phases are then used to guide adaptive recompilation choices, improving performance. We develop both an offline implementation based on trace data and a self-contained online version. Our offline study shows an average speedup of 8.7% and up to 21%, and our online system achieves an average speedup of 4.4%, up to 18%. We subject our results to extensive analysis and show that our design achieves good overall performance with high consistency despite the existence of many complex and interacting factors in such an environment.


title: Compiling for vector-thread architectures

authors:
Mark Hampton
Krste Asanovic

abstract: Vector-thread (VT) architectures exploit multiple forms of parallelism simultaneously. This paper describes a compiler for the Scale VT architecture, which takes advantage of the VT features. We focus on compiling loops, and show how the compiler can transform code that poses difficulties for traditional vector or VLIW processors, such as loops with internal control flow or cross-iteration dependences, while still taking advantage of features not supported by multithreaded designs, such as vector memory instructions. We evaluate the compiler using several embedded benchmarks and show that we can obtain substantial speedups over a single-issue, in-order scalar machine.


title: Cole: compiler optimization level exploration

authors:
Kenneth Hoste
Lieven Eeckhout

abstract: Modern compilers implement a large number of optimizations which all interact in complex ways, and which all have a different impact on code quality, compilation time, code size, energy consumption, etc. For this reason, compilers typically provide a limited number of standard optimization levels, such as -O1, -O2, -O3 and -Os, that combine various optimizations providing a number of trade-offs between multiple objective functions (such as code quality, compilation time and code size). The construction of these optimization levels, i.e., choosing which optimizations to activate at each level, is a manual process typically done using high-level heuristics based on the compiler developer's experience.


title: Prediction and trace compression of data access addresses through nested loop recognition

authors:
Alain Ketterlin
Philippe Clauss

abstract: This paper describes an algorithm that takes a trace (i.e., a sequence of numbers or vectors of numbers) as input, and from that produces a sequence of loop nests that, when run, produces exactly the original sequence. The input format is suitable for any kind of program execution trace, and the output conforms to standard models of loop nests. The first, most obvious, use of such an algorithm is for program behavior modeling for any measured quantity (memory accesses, number of cache misses, etc.). Finding loops amounts to detecting periodic behavior and provides an explanatory model. The second application is trace compression, i.e., storing the loop nests instead of the original trace. Decompression consists of running the loops, which is easy and fast. A third application is value prediction. Since the algorithm forms loops while reading input, it is able to extrapolate the loop under construction to predict further incoming values. Throughout the paper, we provide examples that explain our algorithms. Moreover, we evaluate trace compression and value prediction on a subset of the SPEC2000 benchmarks.


title: Near-optimal instruction selection on dags

authors:
David Ryan Koes
Seth Copen Goldstein

abstract: Instruction selection is a key component of code generation. High quality instruction selection is of particular importance in the embedded space where complex instruction sets are common and code size is a prime concern. Although instruction selection on tree expressions is a well understood and easily solved problem, instruction selection on directed acyclic graphs is NP-complete. In this paper we present NOLTIS, a near-optimal, linear time instruction selection algorithm for DAG expressions. NOLTIS is easy to implement, fast, and effective with a demonstrated average code size improvement of 5.1% compared to the traditional tree decomposition and tiling approach.


title: Branch-on-random

authors:
Edward Lee
Craig B. Zilles

abstract: We propose a new instruction, branch-on-random, that is like a standard conditional branch, except rather than specifying the condition on which the branch should be taken, it specifies a frequency at which the branch should be taken. We show that branch-on-random is useful for reducing the overhead of program instrumentation, via sampling. Specifically, branch-on-random provides an order-of-magnitude reduction in execution time overhead compared to previously proposed software-only frameworks for instrumentation sampling.


title: Fault-safe code motion for type-safe languages

authors:
Brian R. Murphy
Vijay Menon
Florian T. Schneider
Tatiana Shpeisman
Ali-Reza Adl-Tabatabai

abstract: Compilers for Java and other type-safe languages have historically worked to overcome overheads and constraints imposed by runtime safety checks and precise exception semantics. We instead exploit these safety properties to perform code motion optimizations that are even more aggressive than those possible in unsafe languages such as C++.


title: Parallel-stage decoupled software pipelining

authors:
Easwaran Raman
Guilherme Ottoni
Arun Raman
Matthew J. Bridges
David I. August

abstract: In recent years, the microprocessor industry has embraced chip multiprocessors (CMPs), also known as multi-core architectures, as the dominant design paradigm. For existing and new applications to make effective use of CMPs, it is desirable that compilers automatically extract thread-level parallelism from single-threaded applications. DOALL is a popular automatic technique for loop-level parallelization employed successfully in the domains of scientific and numeric computing. While DOALL generally scales well with the number of iterations of the loop, its applicability is limited by the presence of loop-carried dependences. A parallelization technique with greater applicability is decoupled software pipelining (DSWP), which parallelizes loops even in the presence of loop-carried dependences. However, the scalability of DSWP is limited by the size of the loop body and the number of recurrences it contains, which are usually smaller than the loop iteration count.


title: Spice: speculative parallel iteration chunk execution

authors:
Easwaran Raman
Neil Vachharajani
Ram Rangan
David I. August

abstract: The recent trend in the processor industry of packing multiple processor cores in a chip has increased the importance of automatic techniques for extracting thread level parallelism. A promising approach for extracting thread level parallelism in general purpose applications is to apply memory alias or value speculation to break dependences amongst threads and executes them concurrently.


title: Issues and challenges in compiling for graphics processors

abstract: Graphics has been one of the best success stories of parallel processing. Using a unique combination of specialized hardware and aspecialized programming model, game developers routinely write high performance code using millions of threads. Each Generation of graphic processors (GPU's) delivers higher performance and is more programmable then the last. Unlike CPU's, these processors are designed from the beginning to run highly parallel programs and fit a different programming model. We would claim that a GPU is much more like a traditional supercomputer then a desktop processor.


title: Program optimization space pruning for a multithreaded gpu

authors:
Shane Ryoo
Christopher I. Rodrigues
Sam S. Stone
Sara S. Baghsorkhi
Sain-Zee Ueng
John A. Stratton
Wen-mei W. Hwu

abstract: Program optimization for highly-parallel systems has historically been considered an art, with experts doing much of the performance tuning by hand. With the introduction of inexpensive, single-chip, massively parallel platforms, more developers will be creating highly-parallel applications for these platforms, who lack the substantial experience and knowledge needed to maximize their performance. This creates a need for more structured optimization methods with means to estimate their performance effects. Furthermore these methods need to be understandable by most programmers. This paper shows the complexity involved in optimizing applications for one such system and one relatively simple methodology for reducing the workload involved in the optimization process.


title: Accurate critical path prediction via random trace construction

authors:
Pierre Salverda
Charles Tucker
Craig B. Zilles

abstract: We present a new approach to performing program analysis through profile-guided random generation of instruction traces. Using hardware support available in commercial processors, we profile the behavior of individual instructions. Then, in conjunction with the program binary, we use that information to fabricate short (1,000-instruction) traces by randomly evaluating branches in proportion to their profiled behavior. We demonstrate our technique in the context of critical path analysis, showing it can achieve the same accuracy as a hardware critical path predictor, but with lower hardware requirements. Key to achieving this accuracy is correctly identifying memory dependences in the fabricated trace, for which purpose we use a form of abstract interpretation to identify aliasing store-load pairs without explicitly profiling them. We also demonstrate that our approach is very tolerant of the quality of profile information available.


title: Code optimization of parallel programs: evolutionary vs. revolutionary approaches

abstract: Code optimization has a rich history that dates back over half a century. Over the years, it has contributed deep innovations to address challenges posed by new computer system and programming language features. Examples of the former include optimizations for improved register utilization, instruction-level parallelism, vector parallelism, multiprocessor parallelism and memory hierarchy utilization. Examples of the latter include optimizations for procedural, object-oriented, functional and domain-specific languages as well as dynamic optimization for managed runtimes. These optimizations have contributed significantly to programmer productivity by reducing the effort that programmers need to spend on hand-implementing code optimizations and by enabling code to be more portable, especially as programming models and computer architectures change. While compiler frameworks are often able to incorporate new code optimizations in an evolutionary manner, there have been notable periods in the history of compilers when more revolutionary changes were necessary. Examples of such paradigm shifts in the history of compilers include interprocedural whole program analysis, coloring-based register allocation, static single assignment form, array dependence analysis, pointer alias analysis, loop transformations, adaptive profile-directed optimizations, and dynamic compilation. The revolutionary nature of these shifts is evidenced by the fact that production-strength optimization frameworks (especially those in industry) had to be rewritten from scratch or significantly modified to support the new capabilities. In this talk, we claim that the current multicore trend in the computer industry is forcing a new paradigm shift in compilers to address the challenge of code optimization of parallel programs, regardless of whether the parallelism is implicit or explicit in the programming model. All computers --- embedded, mainstream, and high-end --- are now being built from multicore processors with little or no increase in clock speed per core. This trend poses multiple challenges for compilers for future systems as the number of cores per socket continues to grow, and the cores become more heterogeneous. In addition, compilers have to keep pace with emerging parallel programming models embodied in a proliferation of new libraries and new languages.


title: Efficient fine-grained binary instrumentationwith applications to taint-tracking

authors:
Prateek Saxena
R. Sekar
Varun Puranik

abstract: Fine-grained binary instrumentations, such as those for taint-tracking, have become very popular in computer security due to their applications in exploit detection, sandboxing, malware analysis, etc. However, practical application of taint-tracking has been limited by high performance overheads. For instance, previous software based techniques for taint-tracking on binary code have typically slowed down programs by a factor of 3 or more. In contrast, source-code based techniques have achieved better performance using high level optimizations. Unfortunately, these optimizations are difficult to perform on binaries since much of the high level program structure required by such static analyses is lost during the compilation process. In this paper, we address this challenge by developing static techniques that can recover some of the higher level structure from x86 binaries. Our new static analysis enables effective optimizations, which are applied in the context of taint tracking. As a result, we achieve a substantial reduction in performance overheads as compared to previous works.


title: Removing redundancy via exception check motion

authors:
Vijay Sundaresan
Mark G. Stoodley
Pramod Ramarao

abstract: Partial redundancy elimination aims to reduce the number of times an expression is computed more than once. The traditional Lazy Code Motion (LCM) algorithm formulated by Knoop, Ruthing and Steffen, through its reliance on unordered bit vectors, is severely limited in its ability to remove redundancy when precise exception semantics are required because bit vectors cannot express the order of exception checks. This paper describes our new PRE algorithm Exception Check Motion that uses the LCM algorithm to treat and optimize exception checks in a similar way to any other expression. Unlike earlier techniques that can remove only the compare instruction of a partially redundant exception check, our solution can eliminate both the compare and trap instructions without any run time code patching or expensive recovery operations. Since it is the trap instructions that restrict subsequent code motions, our technique gives downstream optimizations more flexibility to improve the performance of the resulting code once the partially redundant checks are eliminated. Our analysis has been implemented in the IBM® Testarossa (TR) just-in-time (JIT) compiler in the IBM Developer Kit for Java Release 5.0 as part of the J9 Virtual Machine. We measure performance improvements up to 7.6% and averaging 2.5% across 22 SPEC and DaCapo benchmarks on 4-way IBM pSeries (PowerPC) hardware.


title: Comprehensive path-sensitive data-flow analysis

authors:
Aditya V. Thakur
R. Govindarajan

abstract: Data-flow analysis is an integral part of any aggressive optimizing compiler. We propose a framework for improving the precision of data-flow analysis in the presence of complex control-flow. We initially perform data-flow analysis to determine those control-flow merges which cause the loss in data-flow analysis precision. The control-flow graph of the program is then restructured such that performing data-flow analysis on the resulting restructured graph gives more precise results. The proposed framework is both simple, involving the familiar notion of product automata, and also general, since it is applicable to any forward data-flow analysis. Apart from proving that our restructuring process is correct, we also show that restructuring is effective in that it necessarily leads to more optimization opportunities. Furthermore, the framework handles the trade-off between the increase in data-flow precision and the code size increase inherent in the restructuring. We show that determining an optimal restructuring is NP-hard, and propose and evaluate a greedy strategy. The framework has been implemented in the Scale research compiler, and instantiated for the specific problem of Constant Propagation. On the SPECINT 2000 benchmark suite we observe an average speedup of 4% in the running times over Wegman-Zadeck conditional constant propagation algorithm and 2% over a purely path profile guided approach.


title: Automatic array inlining in java virtual machines

authors:
Christian Wimmer
Hanspeter Mössenböck

abstract: Array inlining expands the concepts of object inlining to arrays. Groups of objects and arrays that reference each other are placed consecutively in memory so that their relative offsets are fixed, i.e. they are colocated. This allows memory loads to be replaced by address arithmetic, which reduces the costs of field and array accesses. We implemented this optimization for Sun Microsystems' Java HotSpot VM. The optimization is performed automatically and requires no actions on the part of the programmer.


title: Latency-tolerant software pipelining in a production compiler

authors:
Sebastian Winkel
Rakesh Krishnaiyer
Robyn Sampson

abstract: In this paper we investigate the benefit of scheduling non-critical loads for a higher latency during software pipelining. "Non-critical" denotes those loads that have sufficient slack in the cyclic data dependence graph so that increasing the scheduling distance to their first use can only increase the number of stages of the software pipeline, but should not increase the lengths of the individual stages, the initiation interval (II). The associated cost is in many cases negligible, but the memory stall reduction due to improved latency coverage and load clustering in the schedule can be considerable.


title: Pipa: pipelined profiling and analysis on multi-core systems

authors:
Qin Zhao
Ioana Cutcutache
Weng-Fai Wong

abstract: Dynamic instrumentation systems are gaining popularity as means of constructing customized program profiling and analysis tools. However, dynamic instrumentation based analysis tools still suffer from performance problems. The overhead of such systems can be broken down into two components - the overhead of dynamic instrumentation and the time consumed in the user-defined analysis tools. While important progress has been made in reducing the performance penalty of the dynamic instrumentation itself, less attention has been paid to the user-defined component. In this paper, we present PiPA - Pipelined Profiling and Analysis, which is a novel technique for parallelizing dynamic program profiling and analysis by taking advantage of multi-core systems. We implemented a prototype of PiPA using the dynamic instrumentation system DynamoRIO. Our experiments show that PiPA is able to speed up the overall profiling and analysis tasks significantly. Compared to the more than 100x slowdown of Cachegrind and the 32x slowdown of Pin dcache, we achieved a mere 10.5x slowdown on an 8-core system.


title: Perfdiff: a framework for performance difference analysis in a virtual machine environment

authors:
Xiaotong Zhuang
Suhyun Kim
Mauricio J. Serrano
Jong-Deok Choi

abstract: Although applications running on virtual machines, such as Java, can achieve platform independence, performance evaluation and analysis becomes difficult due to extra intermediate layers and the dynamic nature of virtual execution environment.


title: Techniques for Region-Based Register Allocation

abstract: Register allocation is an important component of every compiler and numerous studies have investigated ways to improve allocation quality or reduce allocation time. However, techniques proposed to reduce register allocation time tend to have a detrimental impact on application run-time. In this paper we propose three enhancements to region-based register allocation that not only provide scalable allocation times across multiple applications, but also improve application run-time. We have developed a register pressure based model to determine when using multiple regions is profitable, proposed the use of different regions for each register class, and designed a new region formation algorithm. Our implementation in HP-UX C/C++/Fortran production compilers led to 29% allocation time and 1.4% run-time improvements over a global allocator on the SPEC2006FP suite of benchmarks.


title: Workload Reduction for Multi-input Feedback-Directed Optimization

authors:
Paul Berube
José Nelson Amaral
Rayson Ho
Raúl Silvera

abstract: Feedback-directed optimization is an effective technique to improve program performance, but it may result in program performance and compiler behavior that is sensitive to both the selection of inputs used for training and the actual input in each run of the program. Cross-validation over a workload of inputs can address the input-sensitivity problem, but introduces the need to select a representative workload of minimal size from the population of available inputs. We present a compiler-centric clustering methodology to group similar inputs so that redundant inputs can be eliminated from the training workload. Input similarity is determined based on the compile-time code transformations made by the compiler after training separately on each input. Differences between inputs are weighted by a performance metric based on cross-validation in order to account for code transformation differences that have little impact on performance. We introduce theCrossErrormetric that allows the exploration of correlations between transformations based on the results of clustering. The methodology is applied to several SPEC benchmark programs, and illustrated using selected case studies.


title: Revisiting Out-of-SSA Translation for Correctness, Code Quality and Efficiency

authors:
Benoit Boissinot
Alain Darte
Fabrice Rastello
Benoît Dupont de Dinechin
Christophe Guillon

abstract: Static single assignment (SSA) form is an intermediate program representation in which many code optimizations can be performed with fast and easy-to-implement algorithms. However, some of these optimizations create situations where the SSA variables arising from the same original variable now have overlapping live ranges. This complicates the translation out of SSA code into standard code. There are three issues to consider: correctness, code quality (elimination of copies), and algorithm efficiency (speed and memory footprint). Briggs et al. proposed patches to correct the initial approach of Cytron et al. A cleaner and more general approach was proposed by Sreedhar et al., along with techniques to reduce the number of generated copies. We propose a new approach based on coalescing and a precise view of interferences, in which correctness and optimizations are separated. Our approach is provably correct and simpler to implement, with no patches or particular cases as in previous solutions, while reducing the number of generated copies. Also, experiments with SPEC CINT2000 show that it is 2x faster and 10x less memory-consuming than the Method III of Sreedhar et al., which makes it suitable for just-in-time compilation.


title: Communication-Sensitive Static Dataflow for Parallel Message Passing Applications

abstract: Message passing is a very popular style of parallel programming, used in a wide variety of applications and supported by many APIs, such as BSD sockets, MPI and PVM. Its importance has motivated significant amounts of research on optimization and debugging techniques for such applications. Although this work has produced impressive results, it has also failed to fulfill its full potential. The reason is that while prior work has focused on runtime techniques, there has been very little work on compiler analyses that understand the properties of parallel message passing applications and use this information to improve application performance and quality of debuggers.This paper presents a novel compiler analysis framework that extends dataflow to parallel message passing applications on arbitrary numbers of processes. It works on an extended control-flow graph that includes all possible inter-process interactions of any numbers of processes. This enables dataflow analyses built on top of this framework to incorporate information about the application's parallel behavior and communication topology. The parallel dataflow framework can be instantiated with a variety of specific dataflow analyses as well as abstractions that can tune the accuracy of communication topology detection against its cost. The proposed framework bridges the gap between prior work on parallel runtime systems and sequential dataflow analyses, enabling new transformations, runtime optimizations and bug detection tools that require knowledge of the application's communication topology. We instantiate this framework with two different symbolic analyses and show how these analyses can detect different types of communication patterns, which enables the use of dataflow analyses on a wide variety of real applications.


title: Stream Compilation for Real-Time Embedded Multicore Systems

authors:
Yoonseo Choi
Yuan Lin
Nathan Chong
Scott A. Mahlke
Trevor N. Mudge

abstract: Multicore systems have not only become ubiquitous in the desktop and server worlds, but are also becoming the standard in the embedded space. Multicore offers programmability and flexibility over traditional ASIC solutions. However, many of the advantages of switching to multicore hinge on the assumption that software development is simpler and less costly than hardware development. However, the design and development of correct, high-performance, multi-threaded programs is a difficult challenge for most programmers. Stream programming is one model that has wide applicability in the multimedia, signal processing, and networking domains. Streaming is convenient for developers because it separates the creation of actors, or functions that operate on packets of data, from the flow of data through the system. However, stream compilers are generally ineffective for embedded systems because they do not handle strict resource or timing constraints. Specifically, real-time deadlines and memory size limitations are not handled by conventional stream partitioning and scheduling techniques. This paper introduces the SPIR compiler that orchestrates the execution of streaming applications with strict memory and timing constraints. Software defined radio or SDR is chosen as the application space to illustrate the effectiveness of the compiler for mapping applications onto the IBM Cell platform.


title: Two-Level Dictionary Code Compression: A New Scheme to Improve Instruction Code Density of Embedded Applications

authors:
Mikael Collin
Mats Brorsson

abstract: Dictionary code compression is a technique which has been studied as a method to reduce the energy consumed in the instruction fetch path of processors. Instructions or instruction sequences in the code are replaced with short code words. These code words are later used to index a dictionary which contains the original uncompressed instruction or an entire sequence. In this paper, we present a new method which improves on code density compared to previously published dictionary methods. It uses a two-level dictionary design and is capable of handling compression of both individual instructions and code sequences of 2-16 instructions. The two dictionaries are in separate pipeline stages and work together to decompress sequences and instructions. The impact on storage size for the dictionaries is rather small as the sequences in the dictionary are stored as individually compressed instructions, instead of normal instructions. Compared to previous dictionary code compression methods we achieve improved dynamic compression rate, potential for better performance with reasonable static compression rate and with still small dictionary size suitable for context switching.


title: A Fast and Precise Static Loop Analysis Based on Abstract Interpretation, Program Slicing and Polytope Models

authors:
Paul Lokuciejewski
Daniel Cordes
Heiko Falk
Peter Marwedel

abstract: A static loop analysis is a program analysis computing loop iteration counts. This information is crucial for different fields of applications. In the domain of compilers, the knowledge about loop iterations can be exploited for aggressive loop optimizations like Loop Unrolling. A loop analyzer also provides static information about code execution frequencies which can assist feedback-directed optimizations. Another prominent application is the static worst-case execution time (WCET) analysis which relies on a safe approximation of loop iteration counts. In this paper, we propose a framework for a static loop analysis based on Abstract Interpretation, a theory of a sound approximation of program semantics. To accelerate the analysis, we preprocess the analyzed code using Program Slicing, a technique that removes statements irrelevant for the loop analysis. In addition, we introduce a novel polytope-based loop evaluation that further significantly reduces the analysis time. The efficiency of our loop analyzer is evaluated on a large number of benchmarks. Results show that 99% of the considered loops could be successfully analyzed in an acceptable amount of time. This study points out that our methodology is best suited for real-world problems.


title: A Practical Approach to Hardware Performance Monitoring Based Dynamic Optimizations in a Production JVM

authors:
John Cuthbertson
Sandhya Viswanathan
Konstantin Bobrovsky
Alexander Astapchuk
Eric Kaczmarek
Uma Srinivasan

abstract: While the concept of online profile directed dynamic optimizations using hardware performance monitoring unit (PMU) data is not new, it has seen fairly limited or no use in commercial JVMs. The main reason behind this fact is the set of significant challenges involved in (1) obtaining low overhead and usable profiling support from the underlying platform (2) the complexity of filtering, interpreting and using precise PMU events online in a JVM environment (3) demonstrating the total runtime benefit of PMU data based optimizations above and beyond regular online profile based optimizations. In this paper we address all three challenges by presenting a practical framework for PMU data collection and use within a high performance product JVM on a highly scalable server platform. Our experiments with JavaTM workloads using the SunTM HotspotTM JDK 1.6 JVM on the Intel ® Itanium ® platform indicate that the hardware data collection overhead (less than 0.5%) is not as significant as the challenge of extracting the precise information for optimization purposes. We demonstrate the feasibility of mapping the instruction IP address based hardware event information to the runtime components as well as the JIT server compiler internal data structures for use in optimizations within a dynamic environment. We also evaluated the additional performance potential of optimizations such as object co-location during garbage collection and global instruction scheduling in the JIT compiler with the use of PMU generated load latency information. Experimental results show performance improvements of up to 14% with an average of 2.2% across select Java server benchmarks such as SPECjbb2005[16], SPECjvm2008[17] and Dacapo[18]. These benefits were observed over and above those provided by profile guided server JVM optimizations in the absence of hardware PMU data.


title: Detecting and Eliminating Potential Violations of Sequential Consistency for Concurrent C/C++ Programs

authors:
Yuelu Duan
Xiaobing Feng
Lei Wang
Chao Zhang
Pen-Chung Yew

abstract: When a concurrent shared-memory program written with a sequential consistency (SC) model is run on a machine implemented with a relaxed consistency (RC) model, it could cause SC violations that are very hard to debug. To avoid such violations, programmers need to provide explicit synchronizations or insert fence instructions. In this paper, we propose a scheme to detect and eliminate potential SC violations by combining Shasha/Snir's conflict graph and delay set theory with existing data race detection techniques. For each execution, we generate a race graph, which contains the improperly synchronized conflict accesses, called race accesses, and race cycles formed with those accesses. As a race cycle would probably lead to a non-sequential-consistent execution, we call it a potential violation of sequential consistency (PVSC) bug. We then compute the race delays of race cycles, and suggest programmers to insert fences into source code to eliminate PVSC bugs. We further convert a race graph into a PC race graph, and improves cycle detection and race delay computation to O(n2), where n is the number of race access instructions. We evaluate our approach with the SPLASH-2 benchmarks, two large real-world applications (MySQL and Apache), and several multi-threaded Cilk programs. The results show that (1) the proposed approach could effec-tively detect PVSC bugs in real-world applications with good scalability; (2) it retains most of the performance of the concurrent program after inserting required fence instructions, with less than 6.3% performance loss; and (3) the additional cost of our approach over traditional race detection techniques is quite low, with 3.3% on average.


title: Fast Track: A Software System for Speculative Program Optimization

authors:
Kirk Kelsey
Tongxin Bai
Chen Ding
Chengliang Zhang

abstract: Fast track is a software speculation system that enables unsafe optimization of sequential code. It speculatively runs optimized code to improve performance and then checks the correctness of the speculative code by running the original program on multiple processors. We present the interface design and system implementation for Fast Track. It lets a programmer or a profiling tool mark fast-track code regions and uses a run-time system to manage the parallel execution of the speculative process and its checking processes and ensures the correct display of program outputs. The core of the run-time system is a novel concurrent algorithm that balances exploitable parallelism and available processors when the fast track is too slow or too fast. The programming interface closely affects the run-time support. Our system permits both explicit and implicit end markers for speculatively optimized code regions as well as extensions that allow the use of multiple tracks and user designed correctness checking. We discuss the possible uses of speculative optimization and demonstrate the effectiveness of our prototype system by examples of unsafe semantic optimization and a general system for fast memory-safety checking, which is able to reduce the checking time by factors between 2 and 7 for large sequential code on a 8-CPU system.


title: Transparent Debugging of Dynamically Optimized Code

authors:
Naveen Kumar
Bruce R. Childers
Mary Lou Soffa

abstract: Debugging programs at the source level is essential in the software development cycle. With the growing importance of dynamic optimization, there is a clear need for debugging support in the presence of runtime code transformation. This paper presents a framework, called DeDoc, and lightweight techniques that allow debugging at the source level for programs that have been transformed by a trace-based binary dynamic optimizer. Our techniques provide full transparency and hide from the user the effect of dynamic optimizations on code statements and data values. We describe and evaluate an implementation of DeDoc and its techniques that interface a dynamic optimizer with a native debugger. Our experimental results indicate that DeDoc is able to report over 96% of values, that are otherwise not reportable due to code transformations, and incurs less than 1% performance overhead.


title: Automatic Feature Generation for Machine Learning Based Optimizing Compilation

authors:
Hugh Leather
Edwin V. Bonilla
Michael F. P. O'Boyle

abstract: Recent work has shown that machine learning can automate and in some cases outperform hand crafted compiler optimizations. Central to such an approach is that machine learning techniques typically rely upon summaries or features of the program. The quality of these features is critical to the accuracy of the resulting machine learned algorithm; no machine learning method will work well with poorly chosen features. However, due to the size and complexity of programs, theoretically there are an infinite number of potential features to choose from. The compiler writer now has to expend effort in choosing the best features from this space. This paper develops a novel mechanism to automatically find those features which most improve the quality of the machine learned heuristic. The feature space is described by a grammar and is then searched with genetic programming and predictive modeling. We apply this technique to loop unrolling in GCC 4.3.1 and evaluate our approach on a Pentium 6. On a benchmark suite of 57 programs, GCC's hard-coded heuristic achieves only 3% of the maximum performance available, while a state of the art machine learning approach with hand-coded features obtains 59%. Our feature generation technique is able to achieve 76% of the maximum available speedup, outperforming existing approaches.


title: An Evaluation of Misaligned Data Access Handling Mechanisms in Dynamic Binary Translation Systems

authors:
Jianjun Li
Chenggang Wu
Wei-Chung Hsu

abstract: Binary translation (BT) has been an important approach to migrate application software across instruction set architectures (ISAs). Some architectures, such as X86, allow misaligned data accesses (MDAs), while most modern architectures have the alignment restriction that requires data to be aligned in memory on natural boundaries. In a binary translation system, where the source ISA allows MDA and the target ISA does not, memory operations must be carefully translated to satisfy the alignment restriction. Naive translation will cause frequent misaligned data access traps to occur at runtime on the target machine, and severely slow down the migrated application.This paper evaluates different approaches in handling MDA in binary translation systems. It also proposes a new mechanism to deal with MDAs. Measurements based on SPEC CPU2000 and CPU2006 benchmark show that the proposed approach can significantly outperform existing methods.


title: Perflint: A Context Sensitive Performance Advisor for C++ Programs

authors:
Lixia Liu
Silvius Rus

abstract: We present perflint, a new industrial strength open source analysis tool that identifies suboptimal use patterns of the C++ standard library. Simply by recompiling and running on a representative input set, programmers receive context sensitive performance advice on their use of standard library data structures and algorithms. Our solution consists of collecting traces of relevant library operations and state during program execution, and then recognizing patterns for which there is a faster alternative, based on a model made of performance guarantees in the C++ language standard and machine knowledge. perflint has already found hundreds of suboptimal patterns in a set of large C++ benchmarks. In one case, following the advice and changing one line of code resulted in 17% program run time reduction.


title: Cross-Input Learning and Discriminative Prediction in Evolvable Virtual Machines

authors:
Feng Mao
Xipeng Shen

abstract: Modern languages like Java and C# rely on dynamic optimizations in virtual machines for better performance. Current dynamic optimizations are reactive. Their performance is constrained by the dependence on runtime sampling and the partial knowledge of the execution. This work tackles the problems by developing a set of techniques that make a virtual machine evolve across production runs. The virtual machine incrementally learns the relation between program inputs and optimization strategies so that it proactively predicts the optimizations suitable for a new run. The prediction is discriminative, guarded by confidence measurement through dynamic self-evaluation. We employ an enriched extensible specification language to resolve the complexities in program inputs. These techniques, implemented in Jikes RVM, produce significant performance improvement on a set of Java applications.


title: Scenario Based Optimization: A Framework for Statically Enabling Online Optimizations

authors:
Jason Mars
Robert Hundt

abstract: Online optimization allows the continuous restructuring and adaptation of an executing application using live information about its execution environment. The further advancement of performance monitoring hardware presents new opportunities for online optimization techniques. While managed runtime environments lend themselves nicely to online and dynamic optimizations, such techniques remain difficult to successfully achieve at the binary level. Binary level dynamic optimizers introduce virtual layers which at the binary level produces overhead that is often prohibitive. Another challenge comes from the lack of source level information that can significantly aid optimization.In this paper we present a new static/dynamic collaborative approach to online optimization that takes advantage of the strength of static optimization and the adaptive nature of dynamic optimization techniques. We call this hybrid optimization framework Scenario Based Optimization (SBO). Statically we multiversion and specialize functions for different dynamic scenarios that can be identified by monitoring micro-architectural events. Using these events to infer the current scenario, we dynamically reroute execution to the relevant code tuned to that scenario. We have implemented our static SBO infrastructure in GCC 4.3.1 and designed our dynamic introspection engine using the Perfmon2 infrastructure. To demonstrate the effectiveness of our scenario based optimization framework we have designed an SBO optimization we call the Online Aiding and Abetting of Aggressive Optimizations (OAAAO). Using SPEC2006 this optimization shows a speedup of 7% to 10% for a number of benchmarks and in our best case (h264ref) a 17% speedup over native execution compiled at the -O2 optimization level.


title: OptiScope: Performance Accountability for Optimizing Compilers

authors:
Tipp Moseley
Dirk Grunwald
Ramesh Peri

abstract: Compilers employ many aggressive code transformations to achieve highly optimized code. However, because of complex target architectures and unpredictable optimization interactions, these transformations may not always be beneficial. Current analysis methods measure performance at the application level and ignore optimization effects at the function and loop level. To better measure and understand these effects, we present OptiScope, a compiler independent tool to identify performance opportunities by comparing programs built with different compilers or optimization flags. The analysis includes hundreds of different metrics and uses a novel loop correlation technique for binary programs (produced from the same source by different compilers) to isolate measurements to specific regions. We present several case studies using OptiScope to identify key differences between different compiler suites, versions, and target architectures. The examples demonstrate performance improvement opportunities between 32.5% to 893% on select regions of SPEC 2006 benchmarks.


title: Wave Propagation and Deep Propagation for Pointer Analysis

authors:
Fernando Magno Quintão Pereira
Daniel Berlin

abstract: This paper describes two new algorithms for solving inclusion based points-to analysis. The first algorithm, the wave propagation method, is a modified version of an early technique presented by Pearce et al; however, it greatly improves on the running time of its predecessor. The second algorithm, the deep propagation method, is a more light-weighted analysis, that requires less memory. We have compared these algorithms with three state-of-the-art techniques by Hardekopf-Lin, Heintze-Tardieu and Pearce-Kelly-Hankin. Our experiments show that deep propagation has the best average execution time across a suite of 17 well-known benchmarks, the lowest memory requirements in absolute numbers, and the fastest absolute times for benchmarks under 100,000 lines of code. The memory-hungry wave propagation has the fastest absolute running times in a memory rich execution environment, matching the speed of the best known points-to analysis algorithms in large benchmarks.


title: Profiling k-Iteration Paths: A Generalization of the Ball-Larus Profiling Algorithm

authors:
Subhajit Roy
Y. N. Srikant

abstract: The Ball-Larus path-profiling algorithm is an efficient technique to collect acyclic path frequencies of a program. However, longer paths — those extending across loop iterations — describe the runtime behaviour of programs better. We generalize the Ball-Larus profiling algorithm for profiling k-iteration paths — paths that can span up to to k iterations of a loop. We show that it is possible to number such k-iteration paths perfectly, thus allowing for an efficient profiling algorithm for such longer paths. We also describe a scheme for mixed-mode profiling: profiling different parts of a procedure with different path lengths. Experimental results show that k-iteration profiling is realistic.


title: Procedural Abstraction with Reverse Prefix Trees

authors:
Stefan Schäckeler
Weijia Shang

abstract: For memory constrained environments like embedded systems, optimization for size is often as important as, if not more important than, optimization for execution speed. A common technique for compacting code is procedural abstraction. Equivalent code fragments are identified and abstracted into a procedure. The standard algorithm for identifying these fragments is based on suffix trees. We propose in this paper the calculation of suffix trees over the program text not in the common top-down fashion, but reversed, i.e. bottom-up. With this simple modification, not only equivalent fragments can be identified, but also fragments equivalent to (possibly often differently long) suffixes of the longest fragments. A longest fragment is then abstracted, and all fragments are replaced by procedure calls to their corresponding start instruction somewhere in the abstracted procedure. This allows us to harvest more and longer fragments than with standard suffix trees, improving code size reductions on average by 8.277% over standard suffix trees.


title: Building Approximate Calling Context from Partial Call Traces

authors:
Mauricio J. Serrano
Xiaotong Zhuang

abstract: We present an approach for building calling context information useful for program understanding, performance analysis and optimizations. Our approach exploits a lightweight profiling mechanism providing partial call traces. The goal is to reconstruct calling context information as accurately as possible, and to help the user navigate through it. We propose three steps to merge partial call traces into a smaller number of partial calling context trees. We intend to minimize errors such that the final partial contexts represent actual components of the real calling context tree with a very high probability. The first step concatenates call traces based on their common sequences. The second step converts call traces into partial calling context trees, and the last step merges partial context trees through maximal matching. To gauge how well the merged trees represent the full calling context tree, several criteria are presented. Our results indicate that call traces are successfully merged into a small number of large calling context trees. The merged trees are highly accurate.We have also developed a semi-automatic tool to navigate across partial calling context trees for program understanding and performance analysis purposes. Our results for several Java benchmarks show that our merging strategies exhibit a maximum 1% inaccuracy when compared to the exact solution.


title: Reducing Memory Ordering Overheads in Software Transactional Memory

authors:
Michael F. Spear
Maged M. Michael
Michael L. Scott
Peng Wu

abstract: Most research into high-performance software transactional memory (STM) assumes that transactions will run on a processor with a relatively strict memory model, such as Total Store Ordering (TSO). To execute these algorithms correctly on processors with relaxed memory models, explicit fence instructions may be required on every transactional access, and neither the processor nor the compiler may be able to safely reorder transactional reads. The overheads of fence instructions and read serialization are a significant but unstudied source of latency for STM, with impact on the tradeoffs among different STM systems and on the optimizations that may be possible for any given system. Straightforward ports of STM runtimes from strict to relaxed machines may fail to realize the latter's performance potential. We explore the implementation of STM for machines with relaxed memory consistency using two recent high-performance STM systems. We propose compiler optimizations that can safely eliminate many fence instructions. Using these techniques, we obtain a reduction of up to 89% in the number of fences, and 20% in per-transaction latency, for common transactional benchmarks.


title: Software Pipelined Execution of Stream Programs on GPUs

authors:
Abhishek Udupa
R. Govindarajan
Matthew J. Thazhuthaveetil

abstract: The StreamIt programming model has been proposed to exploit parallelism in streaming applications on general purpose multi-core architectures. This model allows programmers to specify the structure of a program as a set of filters that act upon data, and a set of communication channels between them. The StreamIt graphs describe task, data and pipeline parallelism which can be exploited on modern graphics processing units (GPUs), as they support abundant parallelism in hardware. In this paper, we describe the challenges in mapping StreamIt to GPUs and propose an efficient technique to software pipeline the execution of stream programs on GPUs. We formulate this problem - both scheduling and assignment of filters to processors - as an efficient integer linear program (ILP), which is then solved using ILP solvers. We also describe a novel buffer layout technique for GPUs which facilitates exploiting the high memory bandwidth available in GPUs. The proposed scheduling utilizes both the scalar units in GPU, to exploit data parallelism, and multiprocessors, to exploit task and pipeline parallelism. Further it takes into consideration the synchronization and bandwidth limitations of GPUs, and yields speedups between 1.87X and 36.83X over a single threaded CPU.


title: Computer Generation of General Size Linear Transform Libraries

authors:
Yevgen Voronenko
Frédéric de Mesmay
Markus Püschel

abstract: The development of high-performance libraries has become extraordinarily difficult due to multiple processor cores, vector instruction sets, and deep memory hierarchies. Often, the library has to be reimplemented and reoptimized, when a new platform is released. In this paper we show how to automatically generate general input-size libraries for the domain of linear transforms. The input to our generator is a formal specification of the transform and the recursive algorithms the library should use; the output is a library that supports general input size, is vectorized and multithreaded, provides an adaptation mechanism for the memory hierarchy, and has excellent performance, comparable to or better than the best human-written libraries. Further, we show that our library generator enables various customizations; one example is the generation of Java libraries.


title: ESoftCheck: Removal of Non-vital Checks for Fault Tolerance

authors:
Jing Yu
María Jesús Garzarán
Marc Snir

abstract: As semiconductor technology scales into the deep submicron regime the occurrence of transient or soft errors will increase. This will require new approaches to error detection. Software checking approaches are attractive because they require little hardware modification and can be easily adjusted to fit different reliability and performance requirements. Unfortunately, software checking adds a significant performance overhead. In this paper we present ESoftCheck, a set of compiler optimization techniques to determine which are the vital checks, that is, the minimum number of checks that are necessary to detect an error and roll back to a correct program state. ESoftCheck identifies the vital checks on platforms where registers are hardware-protected with parity or ECC, when there are redundant checks and when checks appear in loops. ESoftCheck also provides knobs to trade reliability for performance based on the support for recovery and the degree of trustiness of the operations. Our experimental results on a Pentium 4 show that ESoftCheck can obtain 27.1% performance improvement without losing fault coverage.


title: Alchemist: A Transparent Dependence Distance Profiling Infrastructure

authors:
Xiangyu Zhang
Armand Navabi
Suresh Jagannathan

abstract: Effectively migrating sequential applications to take advantage of parallelism available on multicore platforms is a well-recognized challenge. This paper addresses important aspects of this issue by proposing a novel profiling technique to automatically detect available concurrency in C programs. The profiler, called Alchemist, operates completely transparently to applications, and identifies constructs at various levels of granularity (e.g., loops, procedures, and conditional statements) as candidates for asynchronous execution. Various dependences including read-after-write (RAW), write-after-read (WAR), and write-after-write (WAW), are detected between a construct and its continuation, the execution following the completion of the construct. The time-ordered distance between program points forming a dependence gives a measure of the effectiveness of parallelizing that construct, as well as identifying the transformations necessary to facilitate such parallelization. Using the notion of post-dominance, our profiling algorithm builds an execution index tree at run-time. This tree is used to differentiate among multiple instances of the same static construct, and leads to improved accuracy in the computed profile, useful to better identify constructs that are amenable to parallelization. Performance results indicate that the profiles generated by Alchemist pinpoint strong candidates for parallelization, and can help significantly ease the burden of application migration to multicore environments.


title: Parameterized tiling revisited

authors:
Muthu Manikandan Baskaran
Albert Hartono
Sanket Tavarageri
Thomas Henretty
J. Ramanujam
P. Sadayappan

abstract: Tiling, a key transformation for optimizing programs, has been widely studied in literature. Parameterized tiled code is important for auto-tuning systems since they often execute a large number of runs with dynamically varied tile sizes. Previous work on tiled code generation has addressed parameterized tiling for the sequential context, and the parallel case with fixed compile-time constants for tile sizes. In this paper, we revisit the problem of generating tiled code using parametric tile sizes. We develop a systematic approach to formulate tiling transformations through manipulation of linear inequalities and develop a novel approach to overcoming the fundamental obstacle faced by previous approaches regarding generation of parallel parameterized tiled code. To the best of our knowledge, the approach proposed in this paper is the first compile-time solution to the problem of parallel parameterized code generation for affine imperfectly nested loops. Experimental results demonstrate the effectiveness of the implemented system.


title: TAO: two-level atomicity for dynamic binary optimizations

authors:
Edson Borin
Youfeng Wu
Cheng Wang
Wei Liu
Maurício Breternitz Jr.
Shiliang Hu
Esfir Natanzon
Shai Rotem
Roni Rosner

abstract: Dynamic binary translation is a key component of Hardware/Software (HW/SW) co-design, which is an enabling technology for processor microarchitecture innovation. There are two well-known dynamic binary optimization techniques based on atomic execution support. Frame-based optimizations leverage processor pipeline support to enable atomic execution of hot traces. Region level optimizations employ transactional-memory-like atomicity support to aggressively optimize large regions of code. In this paper we propose a two-level atomic optimization scheme which not only overcomes the limitations of the two approaches, but also boosts the benefits of the two approaches effectively. Our experiment shows that the combined approach can achieve a total of 21.5% performance improvement over an aggressive out-of-order baseline machine and improve the performance over the frame-based approach by an additional 5.3%.


title: Automatic parallelization of simulink applications

authors:
Arquimedes Canedo
Takeo Yoshizawa
Hideaki Komatsu

abstract: The parallelization of Simulink applications is currently a responsibility of the system designer and the superscalar execution of the processors. State-of-the-art Simulink compilers excel at producing reliable and production-quality embedded code, but fail to exploit the natural concurrency available in the programs and to effectively use modern multi-core architectures. The reason may be that many Simulink applications are replete with loop-carried dependencies that inhibit most parallel computing techniques and compiler transformations.


title: Taming hardware event samples for FDO compilation

authors:
Dehao Chen
Neil Vachharajani
Robert Hundt
Shih-wei Liao
Vinodha Ramasamy
Paul Yuan
Wenguang Chen
Weimin Zheng

abstract: Feedback-directed optimization (FDO) is effective in improving application runtime performance, but has not been widely adopted due to the tedious dual-compilation model, the difficulties in generating representative training data sets, and the high runtime overhead of profile collection. The use of hardware-event sampling to generate estimated edge profiles overcomes these drawbacks. Yet, hardware event samples are typically not precise at the instruction or basic-block granularity. These inaccuracies lead to missed performance when compared to instrumentation-based [email protected] In this paper, we use multiple hardware event profiles and supervised learning techniques to generate heuristics for improved precision of basic-block-level sample profiles, and to further improve the smoothing algorithms used to construct edge profiles. We demonstrate that sampling-based FDO can achieve an average of 78% of the performance gains obtained using instrumentation-based exact edge profiles for SPEC2000 benchmarks, matching or beating instrumentation-based FDO in many cases. The overhead of collection is only 0.74% on average, while compiler based instrumentation incurs 6.8%-53.5% overhead (and 10x overhead on an industrial web search application), and dynamic instrumentation incurs 28.6%-1639.2% overhead.


title: An efficient software transactional memory using commit-time invalidation

authors:
Justin Emile Gottschlich
Manish Vachharajani
Jeremy G. Siek

abstract: To improve the performance of transactional memory (TM), researchers have found many eager and lazy optimizations for conflict detection, the process of determining if transactions can commit. Despite these optimizations, nearly all TMs perform one aspect of lazy conflict detection in the same manner to preserve serializability. That is, they perform commit-time validation, where a transaction is checked for conflicts with previously committed transactions during its commit phase. While commit-time validation is efficient for workloads that exhibit limited contention, it can limit transaction throughput for contending workloads.


title: Speculative parallelization of partial reduction variables

authors:
Liang Han
Wei Liu
James Tuck

abstract: Reduction variables are an important class of cross-thread dependence that can be parallelized by exploiting the associativity and commutativity of their operation. In this paper, we define a class of shared variables called partial reduction variables (PRV). These variables either cannot be proven to be reductions or they violate the requirements of a reduction variable in some way.


title: Automated just-in-time compiler tuning

authors:
Kenneth Hoste
Andy Georges
Lieven Eeckhout

abstract: Managed runtime systems, such as a Java virtual machine (JVM), are complex pieces of software with many interacting components. The Just-In-Time (JIT) compiler is at the core of the virtual machine, however, tuning the compiler for optimum performance is a challenging task. There are (i) many compiler optimizations and options, (ii) there may be multiple optimization levels (e.g., -O0, -O1, -O2), each with a specific optimization plan consisting of a collection of optimizations, (iii) the Adaptive Optimization System (AOS) that decides which method to optimize to which optimization level requires fine-tuning, and (iv) the effectiveness of the optimizations depends on the application as well as on the hardware platform. Current practice is to manually tune the JIT compiler which is both tedious and very time-consuming, and in addition may lead to suboptimal performance.


title: Decoupled software pipelining creates parallelization opportunities

authors:
Jialu Huang
Arun Raman
Thomas B. Jablin
Yun Zhang
Tzu-Han Hung
David I. August

abstract: Decoupled Software Pipelining (DSWP) is one approach to automatically extract threads from loops. It partitions loops into long-running threads that communicate in a pipelined manner via inter-core queues. This work recognizes that DSWP can also be an enabling transformation for other loop parallelization techniques. This use of DSWP, called DSWP+, splits a loop into new loops with dependence patterns amenable to parallelization using techniques that were originally either inapplicable or poorly-performing. By parallelizing each stage of the DSWP+ pipeline using (potentially) different techniques, not only is the benefit of DSWP increased, but the applicability and performance of other parallelization techniques are enhanced. This paper evaluates DSWP+ as an enabling framework for other transformations by applying it in conjunction with DOALL, LOCALWRITE, and SpecDOALL to individual stages of the pipeline. This paper demonstrates significant performance gains on a commodity 8-core multicore machine running a variety of codes transformed with DSWP+.


title: Exploiting statistical correlations for proactive prediction of program behaviors

authors:
Yunlian Jiang
Eddy Z. Zhang
Kai Tian
Feng Mao
Malcom Gethers
Xipeng Shen
Yaoqing Gao

abstract: This paper presents a finding and a technique on program behavior prediction. The finding is that surprisingly strong statistical correlations exist among the behaviors of different program components (e.g., loops) and among different types of program level behaviors (e.g., loop trip-counts versus data values). Furthermore, the correlations can be beneficially exploited: They help resolve the proactivity-adaptivity dilemma faced by existing program behavior predictions, making it possible to gain the strengths of both approaches--the large scope and earliness of offline-profiling--based predictions, and the cross-input adaptivity of runtime sampling-based predictions.


title: Hybrid Java compilation and optimization for digital TV software platform

authors:
Dong-Heon Jung
Soo-Mook Moon
Hyeong-Seok Oh

abstract: The Java software platform for the interactive digital TV (DTV) is composed of the system/middleware classes statically installed on the DTV set-top box and the xlet classes dynamically downloaded from the TV stations, where xlets are executed only when the TV viewer initiates the interaction. In order to achieve high performance on this dual-component, user-initiated system, existing just-in-time compilation is not enough, but idle-time compilation and optimization as well as ahead-of-time compilation are also needed, requiring a hybrid compilation and optimization environment. We constructed such a hybrid environment for a commercial DTV software platform and experimented with real, on-air xlet applications. Our experimental results show that the proposed hybrid environment can improve the DTV Java performance by as much as an average of 150%, compared to the JITC-only environment.


title: Integrated instruction selection and register allocation for compact code generation exploiting freeform mixing of 16- and 32-bit instructions

authors:
Tobias J. K. Edler von Koch
Igor Böhm
Björn Franke

abstract: For memory constrained embedded systems code size is at least as important as performance. One way of increasing code density is to exploit compact instruction formats, e.g. ARM Thumb, where the processor either operates in standard or compact instruction mode. The ARCompact ISA considered in this paper is different in that it allows freeform mixing of 16- and 32-bit instructions without a mode switch. Compact 16-bit instructions can be used anywhere in the code given that additional register constraints are satisfied. In this paper we present an integrated instruction selection and register allocation methodology and develop two approaches for mixed-mode code generation: a simple opportunistic scheme and a more advanced feedback-guided instruction selection scheme. We have implemented a code generator targeting the ARCompact ISA and evaluated its effectiveness against the ARC750D embedded processor and the EEMBC benchmark suite. On average, we achieve a code size reduction of 16.7% across all benchmarks whilst at the same time improving performance by on average 17.7%.


title: Lightweight feedback-directed cross-module optimization

authors:
Xinliang David Li
Raksit Ashok
Robert Hundt

abstract: Cross-module inter-procedural compiler optimization (IPO) and Feedback-Directed Optimization (FDO) are two important compiler techniques delivering solid performance gains. The combination of IPO and FDO delivers peak performance, but also multiplies both techniques' usability problems. In this paper, we present LIPO, a novel static IPO framework, which integrates IPO and FDO. Compared to existing approaches, LIPO no longer requires writing of the compiler's intermediate representation, eliminates the link-time inter-procedural optimization phase entirely, and minimizes code re-generation overhead, thus improving scalability by an order of magnitude. Compared to an FDO baseline, and without further specific tuning, LIPO improves performance of SPEC2006 INT by 2.5%, and of SPEC2000 INT by 4.4%, with up to 23% for one benchmarks. We confirm our scalability results on a set of large industrial applications, demonstrating 2.9% performance improvements on average. Compile time overhead for full builds is less than 30%, incremental builds take a few seconds on average, and storage requirements increase by only 24%, all compared to the FDO baseline.


title: Towards program optimization through automated analysis of numerical precision

authors:
Michael D. Linderman
Matthew Ho
David L. Dill
Teresa H. Meng
Garry P. Nolan

abstract: Reducing the arithmetic precision of a computation has real performance implications, including increased speed, decreased power consumption, and a smaller memory footprint. For some architectures, e.g., GPUs, there can be such a large performance difference that using reduced precision is effectively a requirement. The tradeoff is that the accuracy of the computation will be compromised. In this paper we describe a proof assistant and associated static analysis techniques for efficiently bounding numerical and precision-related errors. The programmer/compiler can use these bounds to numerically verify and optimize an application for different input and machine configurations. We present several case study applications that demonstrate the effectiveness of these techniques and the performance benefits that can be achieved with rigorous precision analysis.


title: Contention aware execution: online contention detection and response

authors:
Jason Mars
Neil Vachharajani
Robert Hundt
Mary Lou Soffa

abstract: Cross-core application interference due to contention for shared on-chip and off-chip resources pose a significant challenge to providing application level quality of service (QoS) guarantees on commodity multicore micro-architectures. Unexpected cross-core interference is especially problematic when considering latency-sensitive applications that are present in the web service data center application domains, such as web-search. The commonly used solution is to simply disallow the co-location of latency-sensitive applications and throughput-oriented batch applications on a single chip, leaving much of the processing capabilities of multicore micro-architectures underutilized. In this work we present a Contention Aware Execution Runtime (CAER) environment that provides a lightweight runtime solution that minimizes cross-core interference due to contention, while maximizing utilization. CAER leverages the ubiquitous performance monitoring capabilities present in current multicore processors to infer and respond to contention and requires no added hardware support. We present the design and implementation of the CAER environment, two separate contention detection heuristics, and approaches to respond to contention online. We evaluate our solution using the SPEC2006 benchmark suite. Our experiments show that when allowing co-location with CAER, as opposed to disallowing co-location, we are able to increase the utilization of the multicore CPU by 58% on average. Meanwhile CAER brings the overhead due to allowing co-location from 17% down to just 4% on average.


title: There are at least two sides to every heterogeneous system

abstract: Since there are at least two sides to every heterogeneous system, optimizing for heterogeneous systems is inherently an exercise in manag-ing complexity, balanced trade-offs and layering. Efforts to make the hardware simple may result in software complexity, unless there's an abstracting software layer involved. Different customer-driven usage models make it challenging to offer a layered but consistent pro-gramming model, a cost-effective set of performance features and a flexibly-capable systems software stack. And often, the very reasons why heterogeneous systems exist drives them to change over time, making them difficult to target from a code generation perspective.


title: Coloring-based coalescing for graph coloring register allocation

authors:
Rei Odaira
Takuya Nakaike
Tatsushi Inagaki
Hideaki Komatsu
Toshio Nakatani

abstract: Graph coloring register allocation tries to minimize the total cost of spilled live ranges of variables. Live-range splitting and coalescing are often performed before the coloring to further reduce the total cost. Coalescing of split live ranges, called sub-ranges, can decrease the total cost by lowering the interference degrees of their common interference neighbors. However, it can also increase the total cost because the coalesced sub-ranges can become uncolorable. In this paper, we propose coloring-based coalescing, which first performs trial coloring and next coalesces all copyrelated sub-ranges that were assigned the same color. The coalesced graph is then colored again with the graph coloring register allocation. The rationale is that coalescing of differently colored sub-ranges could result in spilling because there are some interference neighbors that prevent them from being assigned the same color. Experiments on Java programs show that the combination of live-range splitting and coloring-based coalescing reduces the static spill cost by more than 6% on average, comparing to the baseline coloring without splitting. In contrast, well-known iterated and optimistic coalescing algorithms, when combined with splitting, increase the cost by more than 20%. Coloring-based coalescing improves the execution time by up to 15% and 3% on average, while the existing algorithms improve by up to 12% and 1% on average.


title: PinPlay: a framework for deterministic replay and reproducible analysis of parallel programs

authors:
Harish Patil
Cristiano Pereira
Mack Stallcup
Gregory Lueck
James Cownie

abstract: Analysis of parallel programs is hard mainly because their behavior changes from run to run. We present an execution capture and deterministic replay system that enables repeatable analysis of parallel programs. Our goal is to provide an easy-to-use framework for capturing, deterministically replaying, and analyzing execution of large programs with reasonable runtime and disk usage. Our system, called PinPlay, is based on the popular Pin dynamic instrumentation system hence is very easy to use. PinPlay extends the capability of Pin-based analysis by providing a tool for capturing one execution instance of a program (as log files called pinballs) and by allowing Pin-based tools to run off the captured execution. Most Pintools can be trivially modified to work off pinballs thus doing their usual analysis but with a guaranteed repeatability. Furthermore, the capture/replay works across operating systems (Windows to Linux) as the pinball format is independent of the operating system. We have used PinPlay to analyze and deterministically debug large parallel programs running trillions of instructions. This paper describes the design of PinPlay and its applications for analyses such as simulation point selection, tracing, and debugging.


title: Large program trace analysis and compression with ZDDs

authors:
Graham D. Price
Manish Vachharajani

abstract: Prior work has shown that reduced, ordered, binary decision diagrams (BDDs) can be a powerful tool for program trace analysis and visualization. Unfortunately, it can take hours or days to encode large traces as BDDs. Further, techniques used to improve BDD performance are inapplicable to large dynamic program traces. This paper explores the use of ZDDs for compressing dynamic trace data. Prior work has show that ZDDs can represent sparse data sets with less memory compared to BDDs. This paper demonstrates that (1) ZDDs do indeed provide greater compression for sets of dynamic traces (25% smaller than BDDs on average), (2) with proper tuning, ZDDs encode sets of dynamic trace data over 9x faster than BDDs, and (3) ZDDs can be used for all prior applications of BDDs for trace analysis and visualization.