title: A self-adjusting code cache manager to balance start-up time and memory usage

authors:
Witawas Srisa-an
Myra B. Cohen
Yu Shang
Mithuna Soundararaj

abstract: In virtual machines for embedded devices that use just-in-time compilation, the management of the code cache can significantly impact performance in terms of both memory usage and start-up time. Although improving memory usage has been a common focus for system designers, start-up time is often overlooked. In systems with constrained resources, however, these two performance metrics are often at odds and must be considered together. In this paper, we present an adaptive self-adjusting code cache manager to improve performance with respect to both start-up time and memory usage. It balances these concerns by detecting changes in method compilation rates, resizing the cache after each pitching event. We conduct experiments to validate our proposed system and quantify the impacts that different code cache management techniques have on memory usage and start-up time through two oracle systems. Our results show that the proposed algorithm yields nearly the same start-up times as a hand-tuned oracle and shorter execution times than those of the SSCLI in eight out of ten applications. It also has lower memory usage over time in all but one application.


venue: cgo

title: Statistically regulating program behavior via mainstream computing

authors:
Mark Stephenson
Ram Rangan
Emmanuel Yashchin
Eric Van Hensbergen

abstract: We introduce mainstream computing, a collaborative system that dynamically checks a program--via runtime assertion checks--to ensure that it is running according to expectation. Rather than enforcing strict, statically-defined assertions, our system allows users to run with a set of assertions that are statistically guaranteed to fail at a rate bounded by a user-defined probability, pfail. For example, a user can request a set of assertions that will fail at most 0.5% of the times the application is invoked. Users who believe their usage of an application is mainstream can use relatively large settings for pfail. Higher values of pfail provide stricter regulation of the application which likely enhances security, but will also inhibit some legitimate program behaviors; in contrast, program behavior is unregulated when pfail = 0, leaving the user vulnerable to attack. We show that our prototype is able to detect denial of service attacks, integer overflows, frees of uninitialized memory, boundary violations, and an injection attack. In addition we perform experiments with a mainstream computing system designed to protect against soft errors.


title: Efficient compilation of fine-grained SPMD-threaded programs for multicore CPUs

authors:
John A. Stratton
Vinod Grover
Jaydeep Marathe
Bastiaan Aarts
Mike Murphy
Ziang Hu
Wen-mei W. Hwu

abstract: In this paper we describe techniques for compiling fine-grained SPMD-threaded programs, expressed in programming models such as OpenCL or CUDA, to multicore execution platforms. Programs developed for manycore processors typically express finer thread-level parallelism than is appropriate for multicore platforms. We describe options for implementing fine-grained threading in software, and find that reasonable restrictions on the synchronization model enable significant optimizations and performance improvements over a baseline approach. We evaluate these techniques in a production-level compiler and runtime for the CUDA programming model targeting modern CPUs. Applications tested with our tool often showed performance parity with the compiled C version of the application for single-thread performance. With modest coarse-grained multithreading typical of today's CPU architectures, an average of 3.4x speedup on 4 processors was observed across the test applications.


title: Prospect: a compiler framework for speculative parallelization

authors:
Martin Süßkraut
Thomas Knauth
Stefan Weigert
Ute Schiffel
Martin Meinhold
Christof Fetzer

abstract: Making efficient use of modern multi-core and future many-core CPUs is a major challenge. We describe a new compiler-based platform, Prospect, that supports the parallelization of sequential applications. The underlying approach is a generalization of an existing approach to parallelize runtime checks. The basic idea is to generate two variants of the application: (1) a fast variant having bare bone functionality, and (2) a slow variant with extra functionality. The fast variant is executed sequentially. Its execution is divided into epochs.


title: An adaptive task creation strategy for work-stealing scheduling

authors:
Lei Wang
Huimin Cui
Yuelu Duan
Fang Lu
Xiaobing Feng
Pen-Chung Yew

abstract: Work-stealing is a key technique in many multi-threading programming languages to get good load balancing. The current work-stealing techniques have a high implementation overhead in some applications and require a large amount of memory space for data copying to assure correctness. They also cannot handle many application programs that have an unbalanced call tree or have no definitive working sets.


title: On improving heap memory layout by dynamic pool allocation

authors:
Zhenjiang Wang
Chenggang Wu
Pen-Chung Yew

abstract: Dynamic memory allocation is widely used in modern programs. General-purpose heap allocators often focus more on reducing their run-time overhead and memory space utilization, but less on exploiting the characteristics of their allocated heap objects. This paper presents a lightweight dynamic optimizer, named Dynamic Pool Allocation (DPA), which aims to exploit the affinity of the allocated heap objects and improve their layout at run-time. DPA uses an adaptive partial call chain with heuristics to aggregate affinitive heap objects into dedicated memory regions, called memory pools. We examine the factors that could affect the effectiveness of such layout. We have implemented DPA and measured its performance on several SPEC CPU 2000 and 2006 benchmarks that use extensive heap objects. Evaluations show that it could achieve an average speed up of 12.1% and 10.8% on two x86 commodity machines respectively using GCC -O3, and up to 82.2% for some benchmarks.


title: Minimizing communication in rate-optimal software pipelining for stream programs

authors:
Haitao Wei
Junqing Yu
Huafei Yu
Guang R. Gao

abstract: Stream programming model has been productively applied to a number of important applications domains. Software pipelining is an important code scheduling technique for stream programs. However, the multi-/many-core evolution has presented a new dimension of challenges: that is while searching a best software pipelining schedule how to ensure the communications between processing cores are also minimized? In this paper, we proposed a new solution methodology to address the above problem. Our main contributions include the following. A unified formulation has been proposed that combines the requirement of both rate-optimal software pipelining and the minimization of inter-core communication overhead. This formulation has been developed based on a synchronized dataflow graph model, and is expressed as an integer linear programming problem. A solution testbed has been implemented for the proposed problem formulation on the IBM Cell architecture. This has been realized by extending the Brook stream programming environment with our software pipelining support -- named DFBrook. An experimental study has been conducted to verify the effectiveness of the proposed solution. And a comparison of other scheduling methods has demon-strated the performance superiority of our proposed method.


title: Dynamic interpretation for dynamic scripting languages

authors:
Kevin Williams
Jason McCandless
David Gregg

abstract: Dynamic scripting languages offer programmers increased flexibility by allowing properties of programs to be defined at run-time. Typically, program execution begins with an interpreter where type checks are implemented using conditional statements. Recent JIT compilers have begun removing run-time checks by specializing native code to program properties discovered at JIT time.


title: Linear scan register allocation on SSA form

authors:
Christian Wimmer
Michael Franz

abstract: The linear scan algorithm for register allocation provides a good register assignment with a low compilation overhead and is thus frequently used for just-in-time compilers. Although most of these compilers use static single assignment (SSA) form, the algorithm has not yet been applied on SSA form, i.e., SSA form is usually deconstructed before register allocation. However, the structural properties of SSA form can be used to simplify the algorithm.


title: Level by level: making flow- and context-sensitive pointer analysis scalable for millions of lines of code

authors:
Hongtao Yu
Jingling Xue
Wei Huo
Xiaobing Feng
Zhaoqing Zhang

abstract: We present a practical and scalable method for flow- and context-sensitive (FSCS) pointer analysis for C programs. Our method analyzes the pointers in a program level by level in terms of their points-to levels, allowing the points-to relations of the pointers at a particular level to be discovered based on the points-to relations of the pointers at this level and higher levels. This level-by-level strategy can enhance the scalability of the FSCS pointer analysis in two fundamental ways, by enabling (1) fast and accurate flow-sensitive analysis on full sparse SSA form using a flow-insensitive algorithm and (2) fast and accurate context-sensitive analysis using a full transfer function and a meet function for each procedure.


title: Automatic creation of tile size selection models

authors:
Tomofumi Yuki
Lakshminarayanan Renganarayanan
Sanjay V. Rajopadhye
Charles Anderson
Alexandre E. Eichenberger
Kevin O'Brien

abstract: Tiling is a widely used loop transformation for exposing/exploiting parallelism and data locality. Effective use of tiling requires selection and tuning of the tile sizes. This is usually achieved by hand-crafting tile size selection (TSS) models that characterize the performance of the tiled program as a function of tile sizes. The best tile sizes are selected by either directly using the TSS model or by using the TSS model together with an empirical search. Hand-crafting accurate TSS models is hard, and adapting them to different architecture/compiler, or even keeping them up-to-date with respect to the evolution of a single compiler is often just as hard. Instead of hand-crafting TSS models, can we automatically learn or create them? In this paper, we show that for a specific class of programs fairly accurate TSS models can be automatically created by using a combination of simple program features, synthetic kernels, and standard machine learning techniques. The automatic TSS model generation scheme can also be directly used for adapting the model and/or keeping it up-to-date. We evaluate our scheme on six different architecture-compiler combinations (chosen from three different architectures and four different compilers). The models learned by our method have consistently shown near-optimal performance (within 5% of the optimal on average) across all architecture-compiler combinations.


title: Umbra: efficient and scalable memory shadowing

authors:
Qin Zhao
Derek Bruening
Saman P. Amarasinghe

abstract: Shadow value tools use metadata to track properties of application data at the granularity of individual machine instructions. These tools provide effective means of monitoring and analyzing the runtime behavior of applications. However, the high runtime overhead stemming from fine-grained monitoring often limits the use of such tools. Furthermore, 64-bit architectures pose a new challenge to the building of efficient memory shadowing tools. Current tools are not able to efficiently monitor the full 64-bit address space due to limitations in their shadow metadata translation.


title: Performance is dead, long live performance!

abstract: In a world of social networking, security attacks, and hot mobile phones, the importance of application performance appears to have dimin-ished. My own research agenda has shifted from looking at the performance of memory allocation to building runtime systems that are more resilient to data corruption and security attacks. In my talk, I will outline a number of areas where code-generation and runtime tech-niques can be successfully applied to areas for purposes other than performance, such as fault tolerance, reliability, and security. Along the way, I will consider such questions as "Does it really matter if this corruption was caused by a software or hardware error?" and "Is it okay to let a malicious person allocate arbitrary data on my heap?".


title: The language, optimizer, and tools mess

abstract: For many years, new languages promised higher performance in addition to other desirable characteristics such as higher productivity, better static checking, better reusability and composability, etc. However, in practice, virtually no new languages win in performance over historic languages like C and Fortran. Why? Higher level semantics were supposed to provide additional information so that optimizers could perform better analyses and so that conservative analyses could be less conservative.


title: Language and compiler support for auto-tuning variable-accuracy algorithms

authors:
Jason Ansel
Yee Lok Wong
Cy P. Chan
Marek Olszewski
Alan Edelman
Saman P. Amarasinghe

abstract: Approximating ideal program outputs is a common technique for solving computationally difficult problems, for adhering to processing or timing constraints, and for performance optimization in situations where perfect precision is not necessary. To this end, programmers often use approximation algorithms, iterative methods, data resampling, and other heuristics. However, programming such variable accuracy algorithms presents difficult challenges since the optimal algorithms and parameters may change with different accuracy requirements and usage environments. This problem is further compounded when multiple variable accuracy algorithms are nested together due to the complex way that accuracy requirements can propagate across algorithms and because of the size of the set of allowable compositions. As a result, programmers often deal with this issue in an ad-hoc manner that can sometimes violate sound programming practices such as maintaining library abstractions. In this paper, we propose language extensions that expose trade-offs between time and accuracy to the compiler. The compiler performs fully automatic compile-time and installtime autotuning and analyses in order to construct optimized algorithms to achieve any given target accuracy. We present novel compiler techniques and a structured genetic tuning algorithm to search the space of candidate algorithms and accuracies in the presence of recursion and sub-calls to other variable accuracy code. These techniques benefit both the library writer, by providing an easy way to describe and search the parameter and algorithmic choice space, and the library user, by allowing high level specification of accuracy requirements which are then met automatically without the need for the user to understand any algorithm-specific parameters. Additionally, we present a new suite of benchmarks, written in our language, to examine the efficacy of our techniques. Our experimental results show that by relaxing accuracy requirements, we can easily obtain performance improvements ranging from 1.1× to orders of magnitude of speedup.


title: LAR-CC: Large atomic regions with conditional commits

authors:
Edson Borin
Youfeng Wu
Maurício Breternitz Jr.
Cheng Wang

abstract: HW/SW Co-designed systems rely on dynamic binary translation and optimizations for efficient execution of binary code. Due to memory ordering properties and other architectural constraints, most binary optimizations are applied to regions of code that are atomically executed. To ensure that the underlying hardware has enough speculative resources to execute the whole atomic region, these systems typically form short atomic regions, with only 20 to 30 instructions. However, the shorter is the atomic region the smaller is the scope for optimizations. We present LAR-CC, a novel technique that enables HW/SW co-designed systems to optimize large atomic regions and dynamically fit them into the available speculative hardware resources by means of conditional commits. The LAR-CC technique consists of two major components: 1) conditional branch instructions to conditionally skip commit operations; 2) code transformations that replace commit operations by conditional commits and enable optimizations to be applied on the large atomic regions. Our experiments show that LAR-CC can effectively achieve dynamic atomic region sizes larger than 1000 instructions, providing sufficiently large scope to apply many advanced optimizations on HW/SW co-designed systems.


title: Practical memory checking with Dr. Memory

authors:
Derek Bruening
Qin Zhao

abstract: Memory corruption, reading uninitialized memory, using freed memory, and other memory-related errors are among the most difficult programming bugs to identify and fix due to the delay and non-determinism linking the error to an observable symptom. Dedicated memory checking tools are invaluable for finding these errors. However, such tools are difficult to build, and because they must monitor all memory accesses by the application, they incur significant overhead. Accuracy is another challenge: memory errors are not always straightforward to identify, and numerous false positive error reports can make a tool unusable. A third obstacle to creating such a tool is that it depends on low-level operating system and architectural details, making it difficult to port to other platforms and difficult to target proprietary systems like Windows. This paper presents Dr. Memory, a memory checking tool that operates on both Windows and Linux applications. Dr. Memory handles the complex and not fully documented Windows environment, and avoids reporting false positive memory leaks that plague traditional leak locating algorithms. Dr. Memory employs efficient instrumentation techniques; a direct comparison with the state-of-the-art Valgrind Memcheck tool reveals that Dr. Memory is twice as fast as Memcheck on average and up to four times faster on individual benchmarks.


title: The runtime abort graph and its application to software transactional memory optimization

authors:
Dhruva R. Chakrabarti
Prithviraj Banerjee
Hans-Juergen Boehm
Pramod G. Joisha
Robert S. Schreiber

abstract: Programming with atomic sections is a promising alternative to locks since it raises the abstraction and removes deadlocks at the programmer level. However, implementations of atomic sections using software transactional memory (STM) support have significant bookkeeping overheads. Additionally, because of the speculative nature of transactions, aborts can be frequent greatly lowering application performance. Thus regardless of the STM implementation, tools need to be available to programmers that provide insights into the runtime characteristics of an application as well as provide means to improve performance. This paper attempts to identify the source of an abort at the granularity of a transactional memory reference. The resulting abort patterns are captured in the form of a runtime abort graph (RAG). We show how to build this graph efficiently using compiler instrumentation. We then describe a technique that works on the RAG and automatically recommends STM policy changes to improve performance. Detailed experimental results are presented showing the tradeoffs in building the RAG and its use in reducing aborts and improving performance.


title: Extendable pattern-oriented optimization directives

authors:
Huimin Cui
Jingling Xue
Lei Wang
Yang Yang
Xiaobing Feng
Dongrui Fan

abstract: Current programming models and compiler technologies for multi-core processors do not exploit well the performance benefits obtainable by applying algorithm-specific, i.e., semantic-specific optimizations to a particular application. In this work, we propose a pattern-making methodology that allows algorithm-specific optimizations to be encapsulated into “optimization patterns” that are expressed in terms of pre-processor directives so that simple annotations can result in significant performance improvements. To validate this new methodology, a framework, named EPOD, is developed to map such directives to the underlying optimization schemes. We have identified and implemented a number of optimization patterns for three representative computer platforms. Our experimental results show that a pattern-guided compiler can outperform the state-of-the-art compilers and even achieve performance as competitive as hand-tuned code. Thus, such a pattern-making methodology represents an encouraging direction for domain experts' experience and knowledge to be integrated into general-purpose compilers.


title: Highly scalable distributed dataflow analysis

authors:
Joseph L. Greathouse
Chelsea LeBlanc
Todd M. Austin
Valeria Bertacco

abstract: Dynamic dataflow analyses find software errors by tracking meta-values associated with a program's runtime data. Despite their benefits, the orders-of-magnitude slowdowns that accompany these systems limit their use to the development stage; few users would tolerate such overheads. This work extends dynamic dataflow analyses with a novel sampling system which ensures that runtime slowdowns do not exceed a user-defined threshold. While previous sampling methods are inadequate for dataflow analyses, our technique efficiently reduces the number and size of analyzed dataflows. In doing so, it allows individual users to test large, stochastically chosen sets of a process's dataflows. Large populations can therefore, in aggregate, analyze a larger portion of the program than is possible by any single user running a complete, but slow, analysis. In our experimental evaluation, we show that 1 out of every 10 users expose a number of security exploits while only experiencing a 10% performance slowdown, in contrast with the 100× overhead caused by a complete analysis that exposes the same problems.


title: Flow-sensitive pointer analysis for millions of lines of code

authors:
Ben Hardekopf
Calvin Lin

abstract: Many program analyses benefit, both in precision and performance, from precise pointer analysis. An important dimension of pointer analysis precision is flow-sensitivity, which has been shown to be useful for applications such as program verification and static analysis of binary code, among many others. However, flow-sensitive pointer analysis has historically been unable to scale to programs with millions of lines of code. We present a new flow-sensitive pointer analysis algorithm that is an order of magnitude faster than the existing state of the art, enabling for the first time flow-sensitive pointer analysis for programs with millions of lines of code. Our flow-sensitive algorithm is based on a sparse representation of program code created by a staged, flow-insensitive pointer analysis. We explain how this new algorithm is a member of a new family of pointer analysis algorithms that deserves further study.


title: Runtime automatic speculative parallelization

authors:
Ben Hertzberg
Kunle Olukotun

abstract: We present Runtime Automatic Speculative Parallelization (RASP), a technique for the dynamic extraction of speculative threads from a running application in a user-transparent fashion. By leveraging the idle cores in a CMP to analyze, optimize, and participate in the execution of a running sequential program, RASP enables a collection of simpler cores to achieve sequential performance on par with a significantly more complex core. In contrast to other systems for automatic speculative parallelization, RASP uses dynamic binary translation to optimize applications on-the-fly, without any need for recompilation or source code. RASP achieves these speedups without relying on special-purpose hardware support; RASP's dynamic profiling uses a clever variation on conventional performance monitoring, while RASP's speculative execution relies on the same simple hardware support for speculation that has been proposed for simplifying parallel programming. On a simulated cluster of four in-order cores, RASP accelerates SPEC2006 integer benchmarks by an average of 49%, with promising results for scientific and multimedia workloads as well.


title: MAO - An extensible micro-architectural optimizer

authors:
Robert Hundt
Easwaran Raman
Martin Thuresson
Neil Vachharajani

abstract: Performance matters, and so does repeatability and predictability. Today's processors' micro-architectures have become so complex as to now contain many undocumented, not understood, and even puzzling performance cliffs. Small changes in the instruction stream, such as the insertion of a single NOP instruction, can lead to significant performance deltas, with the effect of exposing compiler and performance optimization efforts to perceived unwanted randomness. This paper presents MAO, an extensible micro-architectural assembly to assembly optimizer, which seeks to address this problem for x86/64 processors. In essence, MAO is a thin wrapper around a common open source assembler infrastructure. It offers basic operations, such as creation or modification of instructions, simple data-flow analysis, and advanced infra-structure, such as loop recognition, and a repeated relaxation algorithm to compute instruction addresses and lengths. This infrastructure enables a plethora of passes for pattern matching, alignment specific optimizations, peep-holes, experiments (such as random insertion of NOPs), and fast prototyping of more sophisticated optimizations. MAO can be integrated into any compiler that emits assembly code, or can be used standalone. MAO can be used to discover micro-architectural details semi-automatically. Initial performance results are encouraging.


title: A trace-based Java JIT compiler retrofitted from a method-based compiler

authors:
Hiroshi Inoue
Hiroshige Hayashizaki
Peng Wu
Toshio Nakatani

abstract: This paper describes our trace-based JIT compiler (trace-JIT) for Java developed from a production-quality method-based JIT compiler (method-JIT). We first describe the design and implementation of our trace-JIT with emphasis on how we retrofitted a method-JIT as a trace-based compiler. Then we show that the trace-JIT often produces better quality code than the method-JIT by extending the compilation scope. Forming longer traces that span multiple methods turns out to be more powerful than method inlining in extending the compilation scope. It reduces method-invocation overhead and also offers more compiler optimization opportunities. However, the trace-JIT incurs additional runtime overhead compared to the method-JIT that may be offset by gains from the improved code quality. Overall, our trace-JIT achieved performance roughly comparable to the baseline method-JIT. We also discuss the issues in trace-based compilation from the viewpoint of compiler optimizations. Our results show the potentials of trace-based compilation as an alternative or complementary approach to compiling languages with mature method-based compilers.


title: Link-time optimization for power efficiency in a tagless instruction cache

authors:
Timothy M. Jones
Sandro Bartolini
Jonas Maebe
Dominique Chanet

abstract: The instruction cache is a critical component in any microprocessor. It must have high performance to enable fetching of instructions on every cycle. However, current designs waste a large amount of energy on each access as tags and data banks from all cache ways are consulted in parallel to fetch the correct instructions as quickly as possible. Existing approaches to reduce this overhead remove unnecessary accesses to the data banks or to the ways that are not likely to hit. However, tag hunks still need to be checked. This paper considers a new hybrid hardware and linker-assisted approach to tagless instruction caching. Our novel cache architecture, supported by the compilation toolchain, removes the need for tag checks entirely for the majority of cache accesses. The linker places frequently-executed instructions in specific program regions that are then mapped into the cache without the need for tag checks. This requires minor hardware modifications, no ISA changes and works across cache configurations. Our approach keeps the software and hardware independent, resulting in both backward and forward compatibility. evaluation on a superscalar processor with and without SMI' support shows power savings of 66% within the instruction cache with no loss of performance. This translates to a 49% saving when considering the combined power of the instruction cache and translation lookaside buffer, which is involved in managing our tagless scheme.


title: Neighborhood-aware data locality optimization for NoC-based multicores

authors:
Mahmut T. Kandemir
Yuanrui Zhang
Jun Liu
Taylan Yemliha

abstract: Data locality optimization is a critical issue for NoC (network-on-chip) based multicore systems. In this paper, focusing on a two-dimensional NoC-based multicore and data-intensive multithreaded applications, we first discuss a data locality aware scheduling algorithm for any given computation-to-core mapping, and then propose an integrated mapping+scheduling algorithm that performs both tasks together. Both our algorithms consider temporal (time-wise) and spatial (neighborhood-aware) data reuse, and try to minimize distance-to-data in on-chip cache accesses. We test the effectiveness of our compiler algorithms using a set of twelve application programs. Our experiments indicate that the proposed algorithms achieve significant improvements in data access latencies (42.7% on average) and overall execution times (24.1% on average). We also conduct a sensitivity analysis where we change the number of cores, on-chip cache capacities, and data movement (migration) strategies. These experiments show that our proposed algorithms generate consistently good results.


title: Whole-function vectorization

authors:
Ralf Karrenberg
Sebastian Hack

abstract: Data-parallel programming languages are an important component in today's parallel computing landscape. Among those are domain-specific languages like shading languages in graphics (HLSL, GLSL, RenderMan, etc.) and “general-purpose” languages like CUDA or OpenCL. Current implementations of those languages on CPUs solely rely on multi-threading to implement parallelism and ignore the additional intra-core parallelism provided by the SIMD instruction set of those processors (like Intel's SSE and the upcoming AVX or Larrabee instruction sets). In this paper, we discuss several aspects of implementing dataparallel languages on machines with SIMD instruction sets. Our main contribution is a language- and platform-independent code transformation that performs whole-function vectorization on low-level intermediate code given by a control flow graph in SSA form. We evaluate our technique in two scenarios: First, incorporated in a compiler for a domain-specific language used in realtime ray tracing. Second, in a stand-alone OpenCL driver. We observe average speedup factors of 3.9 for the ray tracer and factors between 0.6 and 5.2 for different OpenCL kernels.


title: Automatic parallelization of fine-grained meta-functions on a chip multiprocessor

authors:
Sanghoon Lee
James Tuck

abstract: Due to the importance of reliability and security, prior studies have proposed inlining meta-functions into applications for detecting bugs and security vulnerabilities. However, because these software techniques add frequent, finegrained instrumentation to programs, they often incur large runtime overheads. In this work, we consider an automatic thread extraction technique for removing these fine-grained checks from a main application and scheduling them on helper threads. In this way, we can leverage the resources available on a CMP to reduce the latency and overhead of fine-grained checking codes. Our parallelization strategy automatically extracts meta-functions from the main application and executes them in customized helper threads-threads constructed to mirror relevant fragments of the main program's behavior in order to keep communication and overhead low. To get good performance, we consider optimizations that reduce communication and balance work among many threads. We evaluate our parallelization strategy on Mudflap, a pointer-use checking tool in GCC. To show the benefits of our technique, we compare it to a manually parallelized version of Mudflap. We run our experiments on an architectural simulator with support for fast queueing operations. On a subset of SPECint 2000, our automatically parallelized code is only 29% slower, on average, than the manually parallelized version on a simulated 8-core system. Furthermore, two applications achieve better speedups using our algorithms than with the manual approach. Also, our approach introduces very little overhead in the main program-it is kept under 100%, which is more than a 5.3× reduction compared to serial Mudflap.


title: Formally verifying a compiler: Why? How? How far?

abstract: Given the complexity and sophistication of code generation and optimization algorithms, and the difficulty of systematically testing a compiler, it is unsurprising that bugs occur in compilers and cause miscompilation: incorrect executable code is silently generated from a correct source program. The formal verification of a compiler is a radical solution to the miscompilation issue. By applying formal methods (program proof) to the compiler itself, compiler verification proves, with mathematical certainty, that the generated executable code behaves exactly as prescribed by the semantics of the source program.


title: Dynamic register promotion of stack variables

authors:
Jianjun Li
Chenggang Wu
Wei-Chung Hsu

abstract: Dynamic Binary Translation (DBT) has been widely used in various applications. Although new architectures and micro-architectures often create performance opportunities for programmers and compilers, such performance opportunities may not be exploited by legacy executables. For example, the additional general-purpose and XMM registers in the Intel64 architecture do not benefit the IA-32 binaries. In this paper, we designed and developed a DBT system to dynamically promote stack variables in the source binaries to the additional registers of the target architecture. One of the most challenging problems is how to deal with the possible but rare memory aliases between promoted stack variables and other implicit memory references. We devised a runtime alias detection approach based on the page protection mechanism in Linux and a novel stack switching method to catch memory aliases at run-time. This approach is much less expensive than traditional approaches like inserting address checking instructions. On an Intel64 platform, our DBT system with speculative stack variable promotion has sped up several SPEC CPU2006 benchmarks in IA-32 code, with the largest performance gain over 45%.


title: Pinpointing data locality problems using data-centric analysis

authors:
Xu Liu
John M. Mellor-Crummey

abstract: In modern computer architectures, access latency varies considerably between different levels in the memory hierarchy. Consequently, applications with data access patterns that don't reuse much data in fast levels of the hierarchy incur additional delays. To improve the performance of complex, data-intensive applications, developers need tools that help them understand the causes of poor memory hierarchy utilization. While most performance tools associate metrics with functions or statements, in this paper we explore data-centric analyses that associate metrics not only with data accesses but also with data objects themselves. Our contributions are three-fold. First, we propose several refinements to existing data-centric techniques that enable accurate and low-overhead measurements. Second, we combine data-centric analysis with call path profiling; this combination of techniques relates inefficient access patterns back to data objects across complete dynamic call chains. Third, we developed a graphical user interface that gracefully presents our analysis results using a multiplicity of views, which helps users identify problematic accesses and data structures. We demonstrate the utility of our approach by showing how our tool identifies problematic data access patterns in several HPC applications and a pair of the SPEC CPU2006 benchmarks.


title: On-chip cache hierarchy-aware tile scheduling for multicore machines

authors:
Jun Liu
Yuanrui Zhang
Wei Ding
Mahmut T. Kandemir

abstract: Iteration space tiling and scheduling is an important technique for optimizing loops that constitute a large fraction of execution times in computation kernels of both scientific codes and embedded applications. While tiling has been studied extensively in the context of both uniprocessor and multiprocessor platforms, prior research has paid less attention to tile scheduling, especially when targeting multicore machines with deep on-chip cache hierarchies. In this paper, we propose a cache hierarchy-aware tile scheduling algorithm for multicore machines, with the purpose of maximizing both horizontal and vertical data reuses in on-chip caches, and balancing the workloads across different cores. This scheduling algorithm is one of the key components in a source-to-source translation tool that we developed for automatic loop parallelization and multithreaded code generation from sequential codes. To the best of our knowledge, this is the first effort that develops a fully-automated tile scheduling strategy customized for on-chip cache topologies of multicore machines. The experimental results collected by executing twelve application programs on three commercial Intel machines (Nehalem, Dunnington, and Harpertown) reveal that our cache-aware tile scheduling brings about 27.9% reduction in cache misses, and on average, 13.5% improvement in execution times over an alternate method tested.


title: Dynamically accelerating client-side web applications through decoupled execution

authors:
Mojtaba Mehrara
Scott A. Mahlke

abstract: The emergence and wide adoption of Web applications have moved the client-side component, often written in JavaScript, to the forefront of computing on the Web. Web application developers try to move more computation to the client side to avoid unnecessary network traffic and make the applications more responsive. Therefore, JavaScript applications are becoming larger and more computation intensive. Trace-based just-in-time compilation have been proposed to address the performance bottleneck in these applications. In this paper, we exploit the extra processing power in multicore systems to further improve the performance of trace-based execution of JavaScript programs. In trace-based engines, a considerable portion of execution time is spent on running guards which are operations inserted in the native code to check if the properties assumed by the compiled code actually hold during execution. We introduce ParaGuard to off-load these guards to another thread, while speculatively executing the main trace. In a manner similar to what happens in current trace-based JITs, if a check fails, ParaGuard aborts the native trace execution and reverts back to interpreting the JavaScript bytecode. We also propose several optimizations including guard branch aggregation and profile-based snapshot elimination to further improve the performance of our technique. We show that ParaGuard can achieve an average of 15% performance improvement over current trace-based compilers using an extra processor on commodity multicore processors.


title: Prioritizing constraint evaluation for efficient points-to analysis

authors:
Rupesh Nasre
Ramaswamy Govindarajan

abstract: Pervasive use of pointers in large-scale real-world applications continues to make points-to analysis an important optimization-enabler. Rapid growth of software systems demands a scalable pointer analysis algorithm. A typical inclusion-based points-to analysis iteratively evaluates constraints and computes a points-to solution until a fixpoint. In each iteration, (i) points-to information is propagated across directed edges in a constraint graph G and (ii) more edges are added by processing the points-to constraints. We observe that prioritizing the order in which the information is processed within each of the above two steps can lead to efficient execution of the points-to analysis. While earlier work in the literature focuses only on the propagation order, we argue that the other dimension, that is, prioritizing the constraint processing, can lead to even higher improvements on how fast the fixpoint of the points-to algorithm is reached. This becomes especially important as we prove that finding an optimal sequence for processing the points-to constraints is NP-Complete. The prioritization scheme proposed in this paper is general enough to be applied to any of the existing points-to analyses. Using the prioritization framework developed in this paper, we implement prioritized versions of Andersen's analysis, Deep Propagation, Hardekopf and Lin's Lazy Cycle Detection and Bloom Filter based points-to analysis. In each case, we report significant improvements in the analysis times (33%, 47%, 44%, 20% respectively) as well as the memory requirements for a large suite of programs, including SPEC 2000 benchmarks and five large open source programs.


title: Intel's Array Building Blocks: A retargetable, dynamic compiler and embedded language

authors:
Chris J. Newburn
Byoungro So
Zhenying Liu
Michael D. McCool
Anwar M. Ghuloum
Stefanus Du Toit
Zhi-Gang Wang
Zhaohui Du
Yongjian Chen
Gansha Wu
Peng Guo
Zhanglin Liu
Dan Zhang

abstract: Our ability to create systems with large amount of hardware parallelism is exceeding the average software developer's ability to effectively program them. This is a problem that plagues our industry. Since the vast majority of the world's software developers are not parallel programming experts, making it easy to write, port, and debug applications with sufficient core and vector parallelism is essential to enabling the use of multi- and many-core processor architectures. However, hardware architectures and vector ISAs are also shifting and diversifying quickly, making it difficult for a single binary to run well on all possible targets. Because of this, retargetability and dynamic compilation are of growing relevance. This paper introduces Intel®Array Building Blocks (ArBB), which is a retargetable dynamic compilation framework. This system focuses on making it easier to write and port programs so that they can harvest data and thread parallelism on both multi-core and heterogeneous many-core architectures, while staying within standard C++. ArBB interoperates with other programming models to help meet the demands we hear from customers for a solution with both greater programmer productivity and good performance. This work makes contributions in language features, compiler architecture, code transformations and optimizations. It presents performance data from the current beta release of ArBB and quantitatively shows the impact of some key analyses, enabling transformations and optimizations for a variety of benchmarks that are of interest to our customers.


title: Vapor SIMD: Auto-vectorize once, run everywhere

authors:
Dorit Nuzman
Sergei Dyshel
Erven Rohou
Ira Rosen
Kevin Williams
David Yuste
Albert Cohen
Ayal Zaks

abstract: Just-in-Time (JIT) compiler technology offers portability while facilitating target- and context-specific specialization. Single-Instruction-Multiple-Data (SIMD) hardware is ubiquitous and markedly diverse, but can be difficult for JIT compilers to efficiently target due to resource and budget constraints. We present our design for a synergistic auto-vectorizing compilation scheme. The scheme is composed of an aggressive, generic offline stage coupled with a lightweight, target-specific online stage. Our method leverages the optimized intermediate results provided by the first stage across disparate SIMD architectures from different vendors, having distinct characteristics ranging from different vector sizes, memory alignment and access constraints, to special computational idioms. We demonstrate the effectiveness of our design using a set of kernels that exercise innermost loop, outer loop, as well as straight-line code vectorization, all automatically extracted by the common offline compilation stage. This results in performance comparable to that provided by specialized monolithic offline compilers. Our framework is implemented using open-source tools and standards, thereby promoting interoperability and extendibility.


title: Predictive modeling in a polyhedral optimization space

authors:
Eunjung Park
Louis-Noël Pouchet
John Cavazos
Albert Cohen
P. Sadayappan

abstract: Significant advances in compiler optimization have been made in recent years, enabling many transformations such as tiling, fusion, parallelization and vectorization on imperfectly nested loops. Nevertheless, the problem of finding the best combination of loop transformations remains a major challenge. Polyhedral models for compiler optimization have demonstrated strong potential for enhancing program performance, in particular for compute-intensive applications. But existing static cost models to optimize polyhedral transformations have significant limitations, and iterative compilation has become a very promising alternative to these models to find the most effective transformations. But since the number of polyhedral optimization alternatives can be enormous, it is often impractical to iterate over a significant fraction of the entire space of polyhedrally transformed variants. Recent research has focused on iterating over this search space either with manually-constructed heuristics or with automatic but very expensive search algorithms (e.g., genetic algorithms) that can eventually find good points in the polyhedral space. In this paper, we propose the use of machine learning to address the problem of selecting the best polyhedral optimizations. We show that these models can quickly find high-performance program variants in the polyhedral space, without resorting to extensive empirical search. We introduce models that take as input a characterization of a program based on its dynamic behavior, and predict the performance of aggressive high-level polyhedral transformations that includes tiling, parallelization and vectorization. We allow for a minimal empirical search on the target machine, discovering on average 83% of the search-space-optimal combinations in at most 5 runs. Our end-to-end framework is validated using numerous benchmarks on two multi-core platforms.


title: Automated locality optimization based on the reuse distance of string operations

authors:
Silvius Rus
Raksit Ashok
Xinliang David Li

abstract: String operations such as memcpy, memset and memcmp account for a nontrivial amount of Google datacenter resources. String operations hurt processor cache efficiency when the data accessed is not reused shortly thereafter. Such cache pollution can be avoided by using nontemporal memory access to bypass L2/L3 caches. As reuse distance varies greatly across different memcpy static call contexts in the same program, an efficient solution needs to be call context sensitive. We propose a novel solution to this problem using the page protection mechanism to measure reuse distance and the GCC feedback directed optimization mechanism to generate nontemporal memory access instructions at the appropriate static code contexts. First, the compiler inserts instrumentation for calls to string operations. Then a run time library measures reuse distance using the page protection mechanism during a representative profiling run. The compiler finally generates calls to specialized string operations that use nontemporal operations for the arguments with large reuse distance. We present a full implementation and initial results including speedup on large datacenter applications.


title: Using machines to learn method-specific compilation strategies

authors:
Ricardo Nabinger Sanchez
José Nelson Amaral
Duane Szafron
Marius Pirvu
Mark G. Stoodley

abstract: Support Vector Machines (SVMs) are used to discover method-specific compilation strategies in Testarossa, a commercial Just-in-Time (JiT) compiler employed in the IBM®J9 Java™ Virtual Machine. The learning process explores a large number of different compilation strategies to generate the data needed for training models. The trained machine-learned model is integrated with the compiler to predict a compilation plan that balances code quality and compilation effort on a per-method basis. The machine-learned plans outperform the original Testarossa for start-up performance, but not for throughput performance, for which Testarossa has been highly hand-tuned for many years.


title: Phase-based tuning for better utilization of performance-asymmetric multicore processors

authors:
Tyler Sondag
Hridesh Rajan

abstract: The latest trend towards performance asymmetry among cores on a single chip of a multicore processor is posing new challenges. For effective utilization of these performance-asymmetric multicore processors, code sections of a program must be assigned to cores such that the resource needs of code sections closely matches resource availability at the assigned core. Determining this assignment manually is tedious, error prone, and significantly complicates software development. To solve this problem, we contribute a transparent and fully-automatic process that we call phase-based tuning which adapts an application to effectively utilize performance-asymmetric multicores. Compared to the stock Linux scheduler we see a 36% average process speedup, while maintaining fairness and with negligible overheads.


title: A HW/SW co-designed heterogeneous multi-core virtual machine for energy-efficient general purpose computing

authors:
Youfeng Wu
Shiliang Hu
Edson Borin
Cheng Wang

abstract: It is increasingly challenging to improve single thread performance because power/energy consumption becomes a major barrier to achieve significantly higher performance for general purpose cores. General purpose processors are designed to perform well in a wide variety of market segments, at the cost of having significantly lower performance-per-watt than special purpose processors targeting limited applications or market segments. In this paper, we propose a HW/SW co-designed heterogeneous multi-core virtual machine, called TwinPeaks, which integrates a set of less general but power efficient cores and uses dynamic binary optimization to schedule code regions to run on the most efficient cores. Our experiment and analysis indicate that TwinPeaks with a wide in-order core and a narrow out-of-order core may achieve 108% performance at ~71% energy of a big 4-wide out-of-order core.


title: Acculock: Accurate and efficient detection of data races

authors:
Xinwei Xie
Jingling Xue

abstract: Happens-before detectors are precise but can be too conservative to detect certain data races in repeated test runs as they are sensitive to thread interleaving. By making the opposite tradeoffs, lockset detectors can detect more races but are not precise (by reporting false positives). For both types of detectors, happens-before detectors run more slowly as they use expensive vector clocks. Existing hybrid race detectors (combining lockset and happens-before) alleviate some of the limitations in both analysis techniques at the cost of additional analysis overhead. Recently, due to FastTrack, epoch-based happens-before and lockset detectors now exhibit comparable performance. It is the time to rethink how to design a hybrid race detector to balance precision and coverage, by leveraging the lightweightness of epoch clocks. Acculock is the first such a solution. Acculock analyzes a program by reasoning about the subset of the happens-before relation observed with lock acquires and releases excluded, thereby reducing its sensitivity to thread interleaving. When such a weaker happens-before relation is violated, Acculock applies a new efficient lockset algorithm to enforce a lock-based synchronization discipline by distinguishing the locks protecting reads and writes. The key motivation behind is to ensure that Acculock can improve happens-before detectors by discovering also data races in alternate thread interleavings when analyzing one program execution while limiting false warnings thus incurred in a controlled manner. In addition, Acculock achieves these objectives by maintaining comparable performance as FastTrack, the fastest happens-before detector. All these properties of Acculock are validated and confirmed by comparing it against six other detectors, all implemented in Jikes RVM using 11 benchmark programs.


title: Automated programmable control and parameterization of compiler optimizations

abstract: We present a framework which effectively combines programmable control by developers, advanced optimization by compilers, and flexible parameterization of optimizations to achieve portable high performance. We have extended ROSE, a C/C++/Fortran source-to-source optimizing compiler, to automatically analyze scientific applications and discover optimization opportunities. Instead of directly generating optimized code, our optimizer produces parameterized scripts in POET, an interpreted program transformation language, so that developers can freely modify the optimization decisions by the compiler and add their own domain-specific optimizations if necessary. The auto-generated POET scripts support extra optimizations beyond those available in the ROSE optimizer. Additionally, all the optimizations are parameterized at an extremely fine granularity, so the scripts can be ported together with their input code and automatically tuned for different architectures. Our results show that this approach is highly effective, and the code optimized by the auto-generated POET scripts can significantly outperform those optimized using the ROSE optimizer alone.


title: Deferred methods: accelerating dynamic program analysis on multicores

authors:
Danilo Ansaloni
Walter Binder
Abbas Heydarnoori
Lydia Y. Chen

abstract: Parallelization is attractive for speeding up dynamic program analysis on multicores. However, inter-thread communication overhead may outweigh any benefit from parallel execution. We propose deferred methods, a high-level Java framework to accelerate dynamic analysis on multicores. To minimize inter-thread communication overhead, invocations to analysis methods are automatically aggregated in thread-local buffers that are processed when full. In contrast to other approaches, our framework supports custom buffer processing strategies, eases pre-processing of buffers to reduce contention on shared data structures, and offers a synchronization mechanism to wait for the completion of previously invoked deferred methods. We also present a novel adaptive buffer processing strategy that parallelizes the analysis only when the observed workload leaves some CPU cores under-utilized. Using a profiler as case study, we show that deferred methods with the adaptive buffer processing strategy yield an average speedup of factor 4.09 on a quad-core machine. The speedup stems both from parallelization and from reduced contention.


title: HELIX: automatic parallelization of irregular programs for chip multiprocessing

authors:
Simone Campanoni
Timothy M. Jones
Glenn H. Holloway
Vijay Janapa Reddi
Gu-Yeon Wei
David M. Brooks

abstract: We describe and evaluate HELIX, a new technique for automatic loop parallelization that assigns successive iterations of a loop to separate threads. We show that the inter-thread communication costs forced by loop-carried data dependences can be mitigated by code optimization, by using an effective heuristic for selecting loops to parallelize, and by using helper threads to prefetch synchronization signals. We have implemented HELIX as part of an optimizing compiler framework that automatically selects and parallelizes loops from general sequential programs. The framework uses an analytical model of loop speedups, combined with profile data, to choose loops to parallelize. On a six-core Intel® Core i7-980X, HELIX achieves speedups averaging 2.25 x, with a maximum of 4.12x, for thirteen C benchmarks from SPEC CPU2000.


title: DeadSpy: a tool to pinpoint program inefficiencies

authors:
Milind Chabbi
John M. Mellor-Crummey

abstract: Software systems often suffer from various kinds of performance inefficiencies resulting from data structure choice, lack of design for performance, and ineffective compiler optimization. Avoiding unnecessary operations, and in particular memory accesses, is desirable. In this paper, we describe DeadSpy --- a tool that dynamically detects every dead write to memory in a given execution and provides actionable feedback to the programmer. This tool provides a methodical way to identify dead writes, which is a common symptom of performance inefficiencies. Our analysis of the SPEC CPU2006 benchmarks showed that the fraction of dead writes is surprisingly high. In fact, we observed that the SPEC CPU2006 gcc benchmark has 61% dead writes on average across its reference inputs. DeadSpy pinpoints source lines contributing to such inefficiencies. In several case studies with high dead writes, simple code restructuring to eliminate dead writes improved their performance significantly. For gcc, avoiding dead writes improved its running time by as much as 28% for some inputs and 14% on average. We recommend dead write elimination as an important step in performance tuning.


title: Light-weight bounds checking

authors:
Niranjan Hasabnis
Ashish Misra
R. Sekar

abstract: Memory errors in C and C++ programs continue to be one of the dominant sources of security problems, accounting for over a third of the high severity vulnerabilities reported in 2011. Wide-spread deployment of defenses such as address-space layout randomization (ASLR) have made memory exploit development more difficult, but recent trends indicate that attacks are evolving to overcome this defense. Techniques for systematic detection and blocking of memory errors can provide more comprehensive protection that can stand up to skilled adversaries, but unfortunately, these techniques introduce much higher overheads and provide significantly less compatibility than ASLR. We propose a new memory error detection technique that explores a part of the design space that trades off some ability to detect bounds errors in order to obtain good performance and excellent backwards compatibility. On the SPECINT 2000 benchmark, the runtime overheads of our technique is about half of that reported by the fastest previous bounds-checking technique. On the compatibility front, our technique has been tested on over 7 million lines of code, which is much larger than that reported for previous bounds-checking techniques.


title: HQEMU: a multi-threaded and retargetable dynamic binary translator on multicores

authors:
Ding-Yong Hong
Chun-Chen Hsu
Pen-Chung Yew
Jan-Jan Wu
Wei-Chung Hsu
Pangfeng Liu
Chien-Min Wang
Yeh-Ching Chung

abstract: Dynamic binary translation (DBT) is a core technology to many important applications such as system virtualization, dynamic binary instrumentation and security. However, there are several factors that often impede its performance: (1) emulation overhead before translation; (2) translation and optimization overhead, and (3) translated code quality. On the dynamic binary translator itself, the issues also include its retargetability to support guest applications from different instruction-set architectures (ISAs) to host machines also with different ISAs, an important feature for system virtualization. In this work, we take advantage of the ubiquitous multicore platforms, using multithreaded approach to implement DBT. By running the translators and the dynamic binary optimizers on different threads on different cores, it could off-load the overhead caused by DBT on the target applications; thus, afford DBT of more sophisticated optimization techniques as well as the support of its retargetability. Using QEMU (a popular retargetable DBT for system virtualization) and LLVM (Low Level Virtual Machine) as our building blocks, we demonstrated in a multi-threaded DBT prototype, called HQEMU, that it could improve QEMU performance by a factor of 2.4X and 4X on the SPEC 2006 integer and floating point benchmarks for x86 to x86-64 emulations, respectively, i.e. it is only 2.5X and 2.1X slower than native execution of the same benchmarks on x86-64, as opposed to 6X and 8.4X slowdown on QEMU. For ARM to x86-64 emulation, HQEMU could gain a factor of 2.4X speedup over QEMU for the SPEC 2006 integer benchmarks.


title: Dynamically managed data for CPU-GPU architectures

authors:
Thomas B. Jablin
James A. Jablin
Prakash Prabhu
Feng Liu
David I. August

abstract: GPUs are flexible parallel processors capable of accelerating real applications. To exploit them, programmers must ensure a consistent program state between the CPU and GPU memories by managing data. Manually managing data is tedious and error-prone. In prior work on automatic CPU-GPU data management, alias analysis quality limits performance, and type-inference quality limits applicability. This paper presents Dynamically Managed Data (DyManD), the first automatic system to manage complex and recursive data-structures without static analyses. By replacing static analyses with a dynamic run-time system, DyManD overcomes the performance limitations of alias analysis and enables management for complex and recursive data-structures. DyManD-enabled GPU parallelization matches the performance of prior work equipped with perfectly precise alias analysis for 27 programs and demonstrates improved applicability on programs not previously managed automatically.


title: An automatic code overlaying technique for multicores with explicitly-managed memory hierarchies

authors:
Choonki Jang
Jun Lee
Sangmin Seo
Jaejin Lee

abstract: The explicitly-managed memory hierarchies, where a hierarchy of distinct memories is exposed to the programmer and managed explicitly by software, are not only found in typical embedded processors but also found in a class of high performance multicore architectures. Code overlay techniques have been widely used to execute a program whose code is bigger than the available code memory in the system. To generate an efficient overlaid executable with maximum storage savings as well as minimum performance overhead, the overlay structure should be designed carefully. In this paper, we propose an efficient code overlay technique that automatically generates an overlay structure for a given memory size for multicores with explicitly-managed memory hierarchies. We observe that finding an efficient overlay structure with minimum memory copying and run-time check overhead is similar to the problem that finds a code placement with minimum conflict misses in the instruction cache. Our algorithm exploits the temporal-ordering information between functions during program execution. The information is obtained from profiling the program. Experimental results with 11 parallel applications on the Cell BE processor indicate that our approach is effective and promising.


title: Dynamic compilation of data-parallel kernels for vector processors

authors:
Andrew Kerr
Gregory Frederick Diamos
Sudhakar Yalamanchili

abstract: Modern processors enjoy augmented throughput and power efficiency through specialized functional units leveraged via instruction set extensions. These functional units accelerate performance for specific types of operations but must be programmed explicitly. Moreover, applications targeting these specialized units will not take advantage of future ISA extensions and tend not to be portable across multiple ISAs. As architecture designers increasingly rely on heterogeneity for performance improvements, the challenges of leveraging specialized functional units will only become more critical. In particular, exploiting software parallelism without sacrificing portability across the spectrum of commodity and multi-core SIMD processors remains elusive.


title: Automatic speculative DOALL for clusters

authors:
Hanjun Kim
Nick P. Johnson
Jae W. Lee
Scott A. Mahlke
David I. August

abstract: Automatic parallelization for clusters is a promising alternative to time-consuming, error-prone manual parallelization. However, automatic parallelization is frequently limited by the imprecision of static analysis. Moreover, due to the inherent fragility of static analysis, small changes to the source code can significantly undermine performance. By replacing static analysis with speculation and profiling, automatic parallelization becomes more robust and applicable. A naïve automatic speculative parallelization does not scale for distributed memory clusters, due to the high bandwidth required to validate speculation. This work is the first automatic speculative DOALL (Spec-DOALL) parallelization system for clusters. We have implemented a prototype automatic parallelization system, called Cluster Spec-DOALL, which consists of a Spec-DOALL parallelizing compiler and a speculative runtime for clusters. Since the compiler optimizes communication patterns, and the runtime is optimized for the cases in which speculation succeeds, Cluster Spec-DOALL minimizes the communication and validation overheads of the speculative runtime. Across 8 benchmarks, Cluster Spec-DOALL achieves a geomean speedup of 43.8x on a 120-core cluster, whereas DOALL without speculation achieves only 4.5x speedup. This demonstrates that speculation makes scalable fully-automatic parallelization for clusters possible.


title: Panacea: towards holistic optimization of MapReduce applications

authors:
Jun Liu
Nishkam Ravi
Srimat T. Chakradhar
Mahmut T. Kandemir

abstract: MapReduce has emerged as one of the most popular programming models for data parallel enterprise applications. Despite advances in runtime, the opportunities for optimizing MapReduce applications remain largely unexplored. In this paper, we present a framework for performing holistic compiler optimizations on legacy MapReduce applications. We have identified and implemented two optimizations and evaluated them with a set of Hadoop applications on a cluster of Xeon servers. Our experiments show that performance gains of more than 3X can be achieved without user involvement.


title: PinADX: an interface for customizable debugging with dynamic instrumentation

authors:
Gregory Lueck
Harish Patil
Cristiano Pereira

abstract: Dynamic binary instrumentation systems have become popular frameworks for building custom program analysis tools. For example, Pin [8], Valgrind [9], and DynamoRIO [5] have been used to build a variety of memory checking, thread checking, cache simulation, and profiling tools. However, there has been little emphasis on building custom debugging tools with these frameworks. We introduce PinADX, a set of debugging extensions to the Pin instrumentation framework that allow easy development of custom debugger features on both Linux and Windows. This paper presents the PinADX API, demonstrates its use in a simple debugger extension, discusses the implementation details in the Pin instrumentation system, and shows that the performance is better than a native debugger for some typical debugging tasks. We believe that dynamic instrumentation technology is a powerful tool for building advanced debugging features and that an easy to use API will greatly facilitate the development of such features.


title: Matching memory access patterns and data placement for NUMA systems

authors:
Zoltan Majó
Thomas R. Gross

abstract: Many recent multicore multiprocessors are based on a nonuniform memory architecture (NUMA). A mismatch between the data access patterns of programs and the mapping of data to memory incurs a high overhead, as remote accesses have higher latency and lower throughput than local accesses. This paper reports on a limit study that shows that many scientific loop-parallel programs include multiple, mutually incompatible data access patterns, therefore these programs encounter a high fraction of costly remote memory accesses. Matching the data distribution of a program to the individual data access patterns is possible, however it is difficult to find a data distribution that matches all access patterns.


title: Reconciling transactional conflicts with compiler's help

authors:
Sandya S. Mannarswamy
R. Govindarajan

abstract: Software transactional memory(STM) is a promising programming paradigm for shared memory multithreaded programs. While STM offers the promise of being less error-prone and more programmer friendly compared to traditional lock-based synchronization, it also needs to be competitive in performance in order for it to be adopted in mainstream software. A major source of performance overheads in STM is transactional aborts. Conflict resolution and aborting a transaction typically happens at the transaction level which has the advantage that it is automatic and application agnostic. However it has a substantial disadvantage in that STM declares the entire transaction as conflicting and hence aborts it and re-executes it fully, instead of partially re-executing only those part(s) of the transaction, which have been affected due to the conflict. This "Re-execute Everything" approach has a significant adverse impact on STM performance.


title: Efficient bottom-up heap analysis for symbolic path-based data access summaries

authors:
Ivan Matosevic
Tarek S. Abdelrahman

abstract: We propose a heap analysis for extracting data access summaries based on symbolic access paths (SAPs) of methods in object-oriented languages. The analysis takes advantage of the insight that typical programs access dynamic data structures in regular manners. We combine this insight with a bottom-up approach that computes a local summary for each basic block, loop, and method in the program, which is then encapsulated into an abstract block in order to efficiently handle the higher levels of the analysis. We solve the problem of the dependence of local analysis results on the global heap aliasing by inferring the sets of aliases on which the correctness of the local results is predicated. Experimental evaluation for Java shows that for typical programs that use dynamic data structures, our analysis runs in a fast single pass and produces useful results.


title: Compiling for automatically generated instruction set extensions

authors:
Alastair Colin Murray
Björn Franke

abstract: The automatic generation of instruction set extensions (ISEs) to provide application-specific acceleration for embedded processors has been a productive area of research in recent years. The use of automatic algorithms, however, results in instructions that are radically different from those found in conventional Isas. This has resulted in a gap between the hardware's capabilities and the compiler's ability to exploit them. This paper proposes an innovative high-level compiler pass that uses subgraph isomorphism checking to exploit these complex instructions. Our extended code generator also enables the reuse of Ises designed for one application in another, which may be a newer version of the same application or a different one from the same domain. Operating in a separate pass permits computationally expensive techniques to be applied that are uniquely suited for mapping complex instructions, but unsuitable for conventional instruction selection. We demonstrate that this targeted use of an expensive algorithm effectively controls overall compilation time. The existing, mature, compiler back-end can then handle the remainder of the compilation. Instructions are automatically produced for 179 benchmarks, resulting in a total of 1965 unique instructions. The high-level pass integrated into the open-source Gcc compiler is able to use the instructions produced for each benchmark to obtain an average speed-up of 1.26 for the Encore extensible processor.


title: Using graph-based program characterization for predictive modeling

authors:
Eunjung Park
John Cavazos
Marco A. Alvarez

abstract: Using machine learning has proven effective at choosing the right set of optimizations for a particular program. For machine learning techniques to be most effective, compiler writers have to develop expressive means of characterizing the program being optimized. The current state-of-the-art techniques for characterizing programs include using a fixed-length feature vector of either source code features extracted during compile time or performance counters collected when running the program. For the problem of identifying optimizations to apply, models constructed using performance counter characterizations of a program have been shown to outperform models constructed using source code features. However, collecting performance counters requires running the program multiple times, and this "dynamic" method of characterizing programs can be specific to inputs of the program. It would be preferable to have a method of characterizing programs that is as expressive as performance counter features, but that is "static" like source code features and therefore does not require running the program.


title: WCET-aware static locking of instruction caches

authors:
Sascha Plazar
Jan C. Kleinsorge
Peter Marwedel
Heiko Falk

abstract: In the past decades, embedded system designers moved from simple, predictable system designs towards complex systems equipped with caches. This step was necessary in order to bridge the increasingly growing gap between processor and memory system performance. Static analysis techniques had to be developed to allow the estimation of the cache behavior and an upper bound of the execution time of a program. This bound is called worst-case execution time (WCET). Its knowledge is crucial to verify whether hard real-time systems satisfy their timing constraints, and the WCET is a key parameter for the design of embedded systems.


title: Phase guided profiling for fast cache modeling

authors:
Andreas Sembrant
David Black-Schaffer
Erik Hagersten

abstract: Statistical cache models are powerful tools for understanding application behavior as a function of cache allocation. However, previous techniques have modeled only the average application behavior, which hides the effect of program variations over time. Without detailed time-based information, transient behavior, such as exceeding bandwidth or cache capacity, may be missed. Yet these events, while short, often play a disproportionate role and are critical to understanding program behavior.


title: On-demand dynamic summary-based points-to analysis

authors:
Lei Shang
Xinwei Xie
Jingling Xue

abstract: Static analyses can be typically accelerated by reducing redundancies. Modern demand-driven points-to or alias analysis techniques rest on the foundation of Context-Free Language (CFL) reachability. These techniques achieve high precision efficiently for a small number of queries raised in small programs but may still be too slow in answering many queries for large programs in a context-sensitive manner.


title: Compiling for niceness: mitigating contention for QoS in warehouse scale computers

authors:
Lingjia Tang
Jason Mars
Mary Lou Soffa

abstract: As the class of datacenters recently coined as warehouse scale computers (WSCs) continues to leverage commodity multicore processors with increasing core counts, there is a growing need to consolidate various workloads on these machines to fully utilize their computation power. However, it is well known that when multiple applications are co-located on a multicore machine, contention for shared memory resources can cause severe cross-core performance interference. To ensure that the quality of service (QoS) of user-facing applications does not suffer from performance interference, WSC operators resort to disallowing co-location of latency-sensitive applications with other applications. This policy translates to low machine utilization and millions of dollars wasted in WSCs.


title: Efficient and accurate data dependence profiling using software signatures

authors:
Rajeshwar Vanka
James Tuck

abstract: Speculative optimizations relax conservative constraints, like ambiguous memory-carried dependences that will rarely occur at runtime, to allow compilers to generate higher performing code. Data dependence profiling enables these techniques by providing runtime dependence information. However, prior data dependence profilers (DDPs) tend to be slow or have significant inaccuracy. Such techniques try to track all pairs of dependences that occur at runtime. To have high accuracy, it usually requires significant storage and performance overhead. Of course, accuracy can be sacrificed via sampling or fixed size storage to provide higher performance; but, these knobs are tough to control and often lead to a significant loss in accuracy. Hence, we search for a better trade-off between speed and accuracy, and we achieve this by considering a new approach based on efficient set operations using software signatures.


title: Micro-specialization: dynamic code specialization of database management systems

authors:
Rui Zhang
Saumya Debray
Richard T. Snodgrass

abstract: Database management systems (DBMSes) form a cornerstone of modern IT infrastructure, and it is essential that they have excellent performance. Much of the work to date on optimizing DBMS performance has emphasized ensuring efficient data access from secondary storage. This paper shows that DBMSes can also benefit significantly from dynamic code specialization. Our approach focuses on the iterative query evaluation loops typically used by such systems. Query evaluation involves extensive references to the relational schema, predicate values, and join types, which are all invariant during query evaluation, and thus are subject to dynamic value-based code specialization.


title: Runtime asynchronous fault tolerance via speculation

authors:
Yun Zhang
Soumyadeep Ghosh
Jialu Huang
Jae W. Lee
Scott A. Mahlke
David I. August

abstract: Transient faults are emerging as a critical reliability concern in modern microprocessors. Redundant hardware solutions are commonly deployed to detect transient faults, but they are less flexible and cost-effective than software solutions. However, software solutions are rendered impractical because of high performance overheads. To address this problem, this paper presents Runtime Asynchronous Fault Tolerance via Speculation (RAFT), the fastest transient fault detection technique known to date. Serving as a layer between the application and the underlying platform, RAFT automatically generates two symmetric program instances from a program binary. It detects transient faults in a non-invasive way and exploits high-confidence value speculation to achieve low runtime overhead. Evaluation on a commodity multicore system demonstrates that RAFT delivers a geomean performance overhead of 2.83% on a set of 30 SPEC CPU benchmarks and STAMP benchmarks. Compared with existing transient fault detection techniques, RAFT exhibits the best performance and fault coverage, without requiring any change to the hardware or the software applications.


title: Auto-generation and auto-tuning of 3D stencil codes on GPU clusters

authors:
Yongpeng Zhang
Frank Mueller

abstract: This paper develops and evaluates search and optimization techniques for auto-tuning 3D stencil (nearest-neighbor) computations on GPUs. Observations indicate that parameter tuning is necessary for heterogeneous GPUs to achieve optimal performance with respect to a search space. Our proposed framework takes a most concise specification of stencil behavior from the user as a single formula, auto-generates tunable code from it, systematically searches for the best configuration and generates the code with optimal parameter configurations for different GPUs. This auto-tuning approach guarantees adaptive performance for different generations of GPUs while greatly enhancing programmer productivity. Experimental results show that the delivered floating point performance is very close to previous handcrafted work and outperforms other auto-tuned stencil codes by a large margin.


title: Hierarchical overlapped tiling

authors:
Xing Zhou
Jean-Pierre Giacalone
María Jesús Garzarán
Robert H. Kuhn
Yang Ni
David A. Padua

abstract: This paper introduces hierarchical overlapped tiling, a transformation that applies loop tiling and fusion to conventional loops. Overlapped tiling is a useful transformation to reduce communication overhead, but it may also generate a significant amount of redundant computation. Hierarchical overlapped tiling performs overlapped tiling hierarchically to balance communication overhead and redundant computation, and thus has the potential to provide better performance.


title: Scan detection and parallelization in "inherently sequential" nested loop programs

authors:
Yun Zou
Sanjay V. Rajopadhye

abstract: Most automatic parallelizers are based on detection of independent computations, and most of them cannot do anything if there is a true dependence between computations. However, this can be surmounted for programs that perform prefix computations (scans). We present a method for automatically parallelizing such "inherently sequential" programs. Our method, which handles arbitrarily nested loops, identifies situations where the computation performed by the loop body is equivalent to a matrix vector product over a semi-ring. We also deal with mutually dependent variables in the loop. Our method is implemented in a polyhedral program transformation and code generation system and generates OpenMP code. We also present strategies to improve the performance of the generated code, an analytical performance model for the expected speedup, as well as a method to choose the parallelization parameters optimally. We show experimentally that the scan parallelizations performed by our system are effective, yielding linear (iso-efficient) speedup in situations where no other parallelism is available.


title: Runtime dependence computation and execution of loops on heterogeneous systems

authors:
Jayvant Anantpur
R. Govindarajan

abstract: GPUs have been used for parallel execution of DOALL loops. However, loops with indirect array references can potentially cause cross iteration dependences which are hard to detect using existing compilation techniques. Applications with such loops cannot easily use the GPU and hence do not benefit from the tremendous compute capabilities of GPUs. In this paper, we present an algorithm to compute at runtime the cross iteration dependences in such loops. The algorithm uses both the CPU and the GPU to compute the dependences. Specifically, it effectively uses the compute capabilities of the GPU to quickly collect the memory accesses performed by the iterations by executing the slice functions generated for the indirect array accesses. Using the dependence information, the loop iterations are levelized such that each level contains independent iterations which can be executed in parallel. Another interesting aspect of the proposed solution is that it pipelines the dependence computation of the future level with the actual computation of the current level to effectively utilize the resources available in the GPU. We use NVIDIA Tesla C2070 to evaluate our implementation using benchmarks from Polybench suite and some synthetic benchmarks. Our experiments show that the proposed technique can achieve an average speedup of 6.4x on loops with a reasonable number of cross iteration dependences.


title: Schnauzer: scalable profiling for likely security bug sites

authors:
William Arthur
Biruk Mammo
Ricardo Rodríguez Jorge
Todd M. Austin
Valeria Bertacco

abstract: Software bugs comprise the greatest threat to computer security today. Though enormous effort has been expended on eliminating security exploits, contemporary testing techniques are insufficient to deliver software free of security vulnerabilities. In this paper we propose a novel approach to security vulnerability analysis: dynamic control frontier profiling. Security exploits are often buried in rarely executed code paths hidden just beyond the path space explored by end-users. Therefore, we develop Schnauzer, a distributed sampling technology to discover the dynamic control frontier, which forms the line of demarcation between dynamically executed and unseen paths. This frontier may then be used to direct tools (such as white-box fuzz testers) to attain a level of testing coverage currently unachievable. We further demonstrate that the dynamic control frontier paths are a rich source of security bugs, sensitizing many known security exploits.


title: Defensive loop tiling for shared cache

authors:
Bin Bao
Chen Ding

abstract: Loop tiling is a compiler transformation that tailors an application's working set to fit in a cache hierarchy. On today's multicore processors, part of the hierarchy especially the last level cache (LLC) is shared. The available cache space in shared cache changes depending on co-run applications. Furthermore on machines with an inclusive cache hierarchy, the interference in the shared cache can cause evictions in the private cache, a problem known as the inclusion victims. This paper presents defensive tiling, a set of compiler techniques to estimate the effect of cache sharing and then choose the tile sizes that can provide robust performance in co-run environments. The goal of the transformation is to optimize the use of the cache while at the same time guarding against interference. It is entirely a static technique and does not require program profiling. The paper shows how it can be integrated into a production-quality compiler and evalutes its effect on a set of tililing benchmarks for both program co-run and solo-run performance, using both simulation and testing on real systems.


title: Improving data access efficiency by using a tagless access buffer (TAB)

authors:
Alen Bardizbanyan
Peter Gavin
David B. Whalley
Magnus Själander
Per Larsson-Edefors
Sally A. McKee
Per Stenström

abstract: The need for energy efficiency continues to grow for many classes of processors, including those for which performance remains vital. Data cache is crucial for good performance, but it also represents a significant portion of the processor's energy expenditure. We describe the implementation and use of a tagless access buffer (TAB) that greatly improves data access energy efficiency while slightly improving performance. The compiler recognizes memory reference patterns within loops and allocates these references to a TAB. This combined hardware/software approach reduces energy usage by (1) replacing many level-one data cache (L1D) accesses with accesses to the smaller, more power-efficient TAB; (2) removing the need to perform tag checks or data translation lookaside buffer (DTLB) lookups for TAB accesses; and (3) reducing DTLB lookups when transferring data between the L1D and the TAB. Accesses to the TAB occur earlier in the pipeline, and data lines are prefetched from lower memory levels, which result in a small performance improvement. In addition, we can avoid many unnecessary block transfers between other memory hierarchy levels by characterizing how data in the TAB are used. With a combined size equal to that of a conventional 32-entry register file, a four-entry TAB eliminates 40% of L1D accesses and 42% of DTLB accesses, on average. This configuration reduces data-access related energy by 35% while simultane-ously decreasing execution time by 3%.


title: Practical lock/unlock pairing for concurrent programs

authors:
Hyoun Kyu Cho
Terence Kelly
Yin Wang
Stéphane Lafortune
Hongwei Liao
Scott A. Mahlke

abstract: In the multicore era, developers face increasing pressure to parallelize their programs. However, building correct and efficient concurrent programs is substantially more difficult than building sequential ones. To address the multicore challenge, numerous tools have been developed to assist multithreaded programmers, including static and dynamic bug detectors, automated bug fixers, and optimization tools. Many of these tools rely on or benefit from the precise identification of critical sections, i.e., sections where the thread of execution holds at least one lock. For languages where critical sections are not lexically scoped, e.g., C/C++, static analysis often fails to pair up lock and unlock calls correctly. In this paper, we propose a practical lock/unlock pairing mechanism that combines static analysis with dynamic instrumentation to identify critical sections in POSIX multithreaded C/C++ programs. Our method first applies a con-servative inter-procedural path-sensitive dataflow analysis to pair up all lock and unlock calls. When the static analysis fails, our method makes assumptions about the pairing using common heuristics. These assumptions are checked at runtime using lightweight instrumentation. Our experiments show that only one out of 891 lock/unlock pairs violates our assumptions at runtime and the instrumentation imposes negligible overhead of 3.34% at most, for large open-source server programs. Overall, our mechanism can pair up 98.2% of all locks including 7.1 % of them paired speculatively.


title: Instant profiling: Instrumentation sampling for profiling datacenter applications

authors:
Hyoun Kyu Cho
Tipp Moseley
Richard E. Hank
Derek Bruening
Scott A. Mahlke

abstract: Profile-guided optimization possesses huge potential to save costs for datacenters. Hardware performance monitoring units enable profiling with negligible overhead and they have been proven to be effective to help programmers find code regions to optimize by monitoring datacenter applications continuously on live traffic. However, these hardware features are inflexible and often buggy, limiting the types of data that can be gathered. Instrumentation-based profiling can complement or replace hardware functionality by providing more flexible and targeted information gathering. Unfortunately, the overhead of existing instrumentation mechanisms prevents their use in production runs. In order to be used in datacenters, we need a profiling mechanism to impose overheads of less than a few percent, in terms of both throughput and latency, while still generating meaningful profile data. This paper presents instant profiling, an instrumentation sampling technique using dynamic binary translation. Instead of instrumenting the entire execution, instant profiling periodically interleaves native execution and instrumented execution according to configurable profiling duration and frequency parameters. It further reduces the latency degradation of initial profiling phases by pre-populating a software code cache. We evaluate the performance and effectiveness of this new profiling technique on the SPEC CINT2006 benchmark suite and two datacenter application benchmarks. We show that it is well-suited for deployment to datacenters by incurring less than 6% slowdown and 3% computational overhead on average.


title: Pertinent path profiling: Tracking interactions among relevant statements

authors:
Ramshankar Chouhan
Subhajit Roy
Surender Baswana

abstract: Acyclic path profiles are an indispensable tool geared towards multiple ends, with applications spanning from compiler optimizations to software engineering. Though such profiles provide an usable approximation to the program trace, many a times programmers are more interested in uncovering high-level interactions among a set of pertinent statements - not so much in the overall control-flow profile of the program. We propose a new profiling technique, Pertinent Path Profiling, which attempts to unveil such high-level interactions efficiently: given a control-flow graph and a set of pertinent basic-blocks (containing the relevant statements, Pertinent Path Profiling uniquely and efficiently identifies these high-level interactions, revealing execution demeanors that are otherwise difficult to discover via current control-flow profiling schemes. Additionally, if the number of pertinent basic-blocks is small, most of the time our algorithm yields much smaller path-frequency tables than those obtained by acyclic path profilers: if we are interested in a pertinent path profile with about 30% of the basic-blocks marked pertinent, most functions shrink their path-tables to about 15% of that of the acyclic path profiler. We illustrate a couple of possible applications of this new technology and provide experimental results on a set of benchmark programs to testify the utility of this new profiling technique.


title: Just-in-time value specialization

authors:
Igor Rafael de Assis Costa
Péricles Rafael Oliveira Alves
Henrique Nazaré Santos
Fernando Magno Quintão Pereira

abstract: JavaScript emerges today as one of the most important programming languages for the development of client-side web applications. Therefore, it is essential that browsers be able to execute JavaScript programs efficiently. However, the dynamic nature of this programming language makes it very challenging to achieve this much needed efficiency. In this paper we propose parameter-based value specialization as a way to improve the quality of the code produced by JIT engines. We have empirically observed that almost 60% of the JavaScript functions found in the world's 100 most popular websites are called only once, or are called with the same parameters. Capitalizing on this observation, we adapt a number of classic compiler optimizations to specialize code based on the runtime values of function's actual parameters. We have implemented the techniques proposed in this paper in IonMonkey, an industrial quality JavaScript JIT compiler developed in the Mozilla Foundation. Our experiments, run across three popular JavaScript benchmarks, SunSpider, V8 and Kraken, show that, in spite of its highly speculative nature, our optimization pays for itself. As an example, we have been able to speedup SunSpider by 5.38%, and to reduce the size of its native code by 16.72%.


title: Locality-aware mapping and scheduling for multicores

authors:
Wei Ding
Yuanrui Zhang
Mahmut T. Kandemir
Jithendra Srinivas
Praveen Yedlapalli

abstract: This paper presents a cache hierarchy-aware code mapping and scheduling strategy for multicore architectures. Our mapping strategy determines a loop iteration-to-core mapping by taking into account application data access patterns and on-chip cache hierarchy. It employs a novel concept called “core vectors” to obtain a mapping matrix which exploits data reuses at different layers of the cache hierarchy based on their reuse distances, with the goal of maximizing data locality at each level, while minimizing data dependences across the cores. Our scheduling strategy on the other hand determines a schedule for the iterations assigned to each core, with the goal of reducing data reuse distances across the cores for dependence-free loop nests. Our experimental evaluation shows that the proposed mapping scheme reduces miss rates at all levels of caches and application execution time significantly, and when supported by scheduling, the reduction in cache miss rates and execution time become much larger.


title: A polynomial spilling heuristic: Layered allocation

authors:
Boubacar Diouf
Albert Cohen
Fabrice Rastello

abstract: Register allocation is one of the most important, and one of the oldest compiler optimizations. It aims to map temporary variables to machine registers, and defaults to explicit load/store from memory when necessary. The latter option is referred to as spilling. This paper addresses the minimization of the spill code overhead, one of the difficult problems in register allocation. We devised a heuristic, polynomial approach called layered. It is rooted in the recent advances in decoupled register allocation. As opposed to conventional incremental spilling, our method incrementally allocates clusters of variables. We demonstrate its quasi-optimiality on standard benchmarks and on two architectures.


title: Hydra: Automatic algorithm exploration from linear algebra equations

authors:
Alexandre Duchateau
David A. Padua
Denis Barthou

abstract: Hydra accepts an equation written in terms of operations on matrices and automatically produces highly efficient code to solve these equations. Processing of the equation starts by tiling the matrices. This transforms the equation into either a single new equation containing terms involving tiles or into multiple equations some of which can be solved in parallel with each other. Hydra continues transforming the equations using tiling and seeking terms that Hydra knows how to compute or equations it knows how to solve. The end result is that by transforming the equations Hydra can produce multiple solvers with different locality behavior and/or different parallel execution profiles. Next, Hydra applies empirical search over this space of possible solvers to identify the most efficient version. In this way, Hydra enables the automatic production of efficient solvers requiring very little or no coding at all and delivering performance approximating that of the highly tuned library routines such as Intel's MKL.