title: Bandwidth Bandit: Quantitative characterization of memory contention

authors:
David Eklov
Nikos Nikoleris
David Black-Schaffer
Erik Hagersten

abstract: On multicore processors, co-executing applications compete for shared resources, such as cache capacity and memory bandwidth. This leads to suboptimal resource allocation and can cause substantial performance loss, which makes it important to effectively manage these shared resources. This, however, requires insights into how the applications are impacted by such resource sharing. While there are several methods to analyze the performance impact of cache contention, less attention has been paid to general, quantitative methods for analyzing the impact of contention for memory bandwidth. To this end we introduce the Bandwidth Bandit, a general, quantitative, profiling method for analyzing the performance impact of contention for memory bandwidth on multicore machines. The profiling data captured by the Bandwidth Bandit is presented in a bandwidth graph. This graph accurately captures the measured application's performance as a function of its available memory bandwidth, and enables us to determine how much the application suffers when its available bandwidth is reduced. To demonstrate the value of this data, we present a case study in which we use the bandwidth graph to analyze the performance impact of memory contention when co-running multiple instances of single threaded application.


venue: cgo

title: Smart, adaptive mapping of parallelism in the presence of external workload

authors:
Murali Krishna Emani
Zheng Wang
Michael F. P. O'Boyle

abstract: Given the wide scale adoption of multi-cores in main stream computing, parallel programs rarely execute in isolation and have to share the platform with other applications that compete for resources. If the external workload is not considered when mapping a program, it leads to a significant drop in performance. This paper describes an automatic approach that combines compile-time knowledge of the program with dynamic runtime workload information to determine the best adaptive mapping of programs to available resources. This approach delivers increased performance for the target application without penalizing the existing workload. This approach is evaluated on NAS and SpecOMP parallel bench-mark programs across a wide range of workload scenarios. On average, our approach achieves performance gain of 1.5x over a state-of-art scheme on a 12 core machine.


title: Experiences in designing a robust and scalable interpreter profiling framework

authors:
Ian Gartley
Marius Pirvu
Vijay Sundaresan
Nikola Grcevski

abstract: Profile directed feedback (PDF) is a well known technique used to drive many compiler optimizations like basic block ordering and guarded devirtualization. These optimizations are particularly crucial in order to achieve good throughput performance in JEE applications that have a large code footprint. To effectively apply optimizations that rely on profiling information, a just-in-time (JIT) compiler must have access to profiling information that is accurate. One common source of profiling information in a Java virtual machine (JVM) is the interpreter. Typically methods are interpreted as a program ramps up, during which profiling information can be collected. However, obtaining useful and accurate information for large enterprise-class applications can be a challenge because of the memory and performance overhead associated with collecting and processing the large volumes of profiling data that is generated. This paper describes the challenges in maintaining the balance between throughput performance and profiling overhead in a production JIT compiler that is used by the IBM JDK. The scope of the performance overhead in terms of throughput, memory footprint and startup speed for large JEE class applications is introduced and various engineering solutions that were tried are detailed and compared in terms of experimental results. We found that the throughput improvement due to interpreter profiling (IP) can be as high as 58%, whereas the overhead measured in terms of application startup time could cost up to 57%. Our solutions to reducing profiling overhead managed to reduce the startup cost to only a few percent while maintaining the full throughput benefit. By discussing these approaches, this paper offers a balanced and practical overview on how to make PDF work well for enterprise-class applications in a production JIT compiler.


title: Portable mapping of data parallel programs to OpenCL for heterogeneous systems

authors:
Dominik Grewe
Zheng Wang
Michael F. P. O'Boyle

abstract: General purpose GPU based systems are highly attractive as they give potentially massive performance at little cost. Re-alizing such potential is challenging due to the complexity of programming. This paper presents a compiler based approach to automatically generate optimized OpenCL code from data-parallel OpenMP programs for GPUs. Such an approach brings together the benefits of a clear high levellanguage (OpenMP) and an emerging standard (OpenCL) for heterogeneous multi-cores. A key feature of our scheme is that it leverages existing transformations, especially data transformations, to improve performance on GPU architectures and uses predictive modeling to automatically determine if it is worthwhile running the OpenCL code on the GPU or OpenMP code on the multi-core host. We applied our approach to the entire NAS parallel benchmark suite and evaluated it on two distinct GPU based systems: Core i7/NVIDIA GeForce GTX 580 and Core 17/AMD Radeon 7970. We achieved average (up to) speedups of 4.51x and 4.20x (143x and 67x) respectively over a sequential baseline. This is, on average, a factor 1.63 and 1.56 times faster than a hand-coded, GPU-specific OpenCL implementation developed by independent expert programmers.


title: Profile-guided automated software diversity

authors:
Andrei Homescu
Steven Neisius
Per Larsen
Stefan Brunthaler
Michael Franz

abstract: Code-reuse attacks are notoriously hard to defeat, and most current solutions to the problem focus on automated software diversity. This is a promising area of research, as diversity attacks the common denominator enabling code-reuse attacksthe software monoculture. Recent research in this area provides security, but at an unfortunate price: performance overhead. Leveraging previously collected profiling information, compilers can substantially improve subsequent code generation. Traditionally, profile-guided optimization focuses on hot program code, where a program spends most of its execution time. Optimizing rarely executed code does not significantly impact performance, so few optimizations focus on this code. We use profile-guided optimization to reduce the performance overhead of software diversity. The primary insight is that we are free to diversify cold code, but restrict our diversification efforts in hot code. Our work investigates the impact of profiling on an expensive diversification technique: NOP insertion. By differentiating between hot cold and cold code, we optimize NOP insertion overheads from a maximum of 25% down to a negligible 1%, while preserving the security properties of the original defense. Consequently, using our profile-guided diversification technique, even randomization techniques having a high performance overhead become practical.


title: Automatically exploiting cross-invocation parallelism using runtime information

authors:
Jialu Huang
Thomas B. Jablin
Stephen R. Beard
Nick P. Johnson
David I. August

abstract: Automatic parallelization is a promising approach to producing scalable multi-threaded programs for multicore architectures. Many existing automatic techniques only parallelize iterations within a loop invocation and synchronize threads at the end of each loop invocation. When parallel code contains many loop invocations, synchronization can easily become a performance bottleneck. Some automatic techniques address this problem by exploiting cross-invocation parallelism. These techniques use static analysis to partition iterations among threads to avoid crossthread dependences. However, this partitioning is not always achievable at compile-time, because program input determines dependence patterns at run-time. By contrast, this paper proposes DOMORE, the first automatic parallelization technique that uses runtime information to exploit additional cross-invocation parallelism. Instead of partitioning iterations statically, DOMORE dynamically detects crossthread dependences and synchronizes only when necessary. DOMORE consists of a compiler and a runtime library. At compile time, DOMORE automatically parallelizes loops and inserts a custom runtime engine into programs. At run-time, the engine observes dependences and synchronizes iterations only when necessary. For six programs, DOMORE achieves a geomean loop speedup of 2.1× over parallel execution without cross-invocation parallelization and of 3.2 × over sequential execution on eight cores.


title: Skadu: Efficient vector shadow memories for poly-scopic program analysis

authors:
Donghwan Jeon
Saturnino Garcia
Michael Bedford Taylor

abstract: Shadow memory is a critical component of many dynamic program analysis frameworks with applications ranging from memory debugging to computer security. Most recent work has focused on optimizing the execution time of analyses that associate a single tag with each memory address. However, an important new class of dynamic analyses (poly-scopic analyses) requires multiple tags for each memory address. These new analyses place additional burdens on memory shadowing infrastructures, especially with regards to memory overhead. Existing shadow memory infrastructures are either unequipped to handle these additional burdens or result in runtime and memory overheads that make them impractical for all but small inputs. In this paper we propose vector shadow memories (VSMs) as an infrastructure to support poly-scopic analyses. Furthermore we introduce Skadu, a VSM implementation that employs several novel techniques to greatly reduce the runtime and memory overhead associated with the two major challenges of VSMs: tag validation and garbage collection. Our results show that on two separate poly-scopic analyses, memory footprint profiling and hierarchical critical path analysis, Skadu significantly reduces the associated memory overhead: by 14.2× and 11.4× respectively. In both cases, Skadu makes poly-scopic analysis practical for ordinary desktop and laptop machines.


title: Idempotent code generation: Implementation, analysis, and evaluation

authors:
Marc de Kruijf
Karthikeyan Sankaralingam

abstract: Leveraging idempotence for efficient recovery is of emerging interest in compiler design. In particular, identifying semantically idempotent code and then compiling such code to preserve the semantic idempotence property enables recovery with substantially lower overheads than competing software techniques. However, the efficacy of this technique depends on application-, architecture-, and compiler-specific factors that are not well understood. In this paper, we develop algorithms for the code generation of idempotent code regions and evaluate these algorithms considering how they are impacted by these factors. Without optimizing for these factors, we find that typical performance overheads fall in the range of roughly 10-15%. However, manipulating application idempotent region size typically improves the run-time performance of compiled code by 2-10%, differences in the architecture instruction set affect performance by up to 15%, and knowing in the compiler whether control flow side-effects can or cannot occur can impact performance by up to 10%. Overall, we find that, with small idempotent region and careful architecture- and application-specific tuning, it is possible to bring compiler performance overheads consistently down into the single-digit percentage range. The absolute best performance occurs when constructing the largest possible idempotent regions; to this end, however, better compiler support is needed. In the interest of spurring development in this area, we open-source our LLVM compiler implementation and make it available as a research tool.


title: Automatic construction of inlining heuristics using machine learning

authors:
Sameer Kulkarni
John Cavazos
Christian Wimmer
Doug Simon

abstract: Method inlining is considered to be one of the most important optimizations in a compiler. However, a poor inlining heuristic can lead to significant degradation of a program's running time. Therefore, it is important that an inliner has an effective heuristic that controls whether a method is inlined or not. An important component of any inlining heuristic are the features that characterize the inlining decision. These features often correspond to the caller method and the callee methods. However, it is not always apparent what the most important features are for this problem or the relative importance of these features. Compiler writers developing inlining heuristics may exclude critical information that can be obtained during each inlining decision. In this paper, we use a machine learning technique, namely neuro-evolution [18], to automatically induce effective inlining heuristics from a set of features deemed to be useful for inlining. Our learning technique is able to induce novel heuristics that significantly out-perform manually-constructed inlining heuristics. We evaluate the heuristic constructed by our neuro-evolutionary technique within the highly tuned Java HotSpot server compiler and the Maxine VM C1X compiler, and we are able to obtain speedups of up to 89% and 114%, respectively. In addition, we obtain an average speedup of almost 9% and 11% for the Java HotSpot VM and Maxine VM, respectively. However, the output of neuro-evolution, a neural network, is not human readable. We show how to construct more concise and read-able heuristics in the form of decision trees that perform as well as our neuro-evolutionary approach.


title: Performance upper bound analysis and optimization of SGEMM on Fermi and Kepler GPUs

authors:
Junjie Lai
André Seznec

abstract: In this paper, we present an approach to estimate GPU applications' performance upper bound based on algorithm analysis and assembly code level benchmarking. As an example, we analyze the potential peak performance of SGEMM (Single-precision General Matrix Multiply) on Fermi (GF110) and Kepler (GK104) GPUs. We try to answer the question of how much optimization space is left for SGEMM and why. According to our analysis, the nature of Fermi (Kepler) instruction set and the limited issue throughput of the schedulers are the main limitation factors for SGEMM to approach the theoretical peak performance. The estimated upper-bound peak performance of SGEMM is around 82.5% of the theoretical peak performance on GTX580 Fermi GPU and 57.6% on GTX680 Kepler GPU. Guided by this analysis and using the native assembly language, on average, our SGEMM implementations achieve about 5% better performance than CUBLAS in CUDA 4.1 SDK for large matrices on GTX580. The achieved performance is around 90% of the estimated upper-bound performance of SGEMM on GTX580. On GTX680, the best performance we achieve is around 77.3% of the estimated performance upper bound. We also describe how to use native assembly language directly in the CUDA runtime source code.


title: Convergence and scalarization for data-parallel architectures

authors:
Yunsup Lee
Ronny Krashinsky
Vinod Grover
Stephen W. Keckler
Krste Asanovic

abstract: Modern throughput processors such as GPUs achieve high performance and efficiency by exploiting data parallelism in application kernels expressed as threaded code. One draw-back of this approach compared to conventional vector architectures is redundant execution of instructions that are common across multiple threads, resulting in energy inefficiency due to excess instruction dispatch, register file accesses, and memory operations. This paper proposes to alleviate these overheads while retaining the threaded programming model by automatically detecting the scalar operations and factoring them out of the parallel code. We have developed a scalarizing compiler that employs convergence and variance analyses to statically identify values and instructions that are invariant across multiple threads. Our compiler algorithms are effective at identifying convergent execution even in programs with arbitrary control flow, identifying two-thirds of the opportunity captured by a dynamic oracle. The compile-time analysis leads to a reduction in instructions dispatched by 29%, register file reads and writes by 31% memory address counts by 47%, and data access counts by 38%.


title: Effective fault localization based on minimum debugging frontier set

authors:
Feng Li
Wei Huo
Congming Chen
Lujie Zhong
Xiaobing Feng
Zhiyuan Li

abstract: In this paper, we present a novel state-based fault-localization approach called DelFal. Assuming the availability of the execution trace which leads to the reported program execution failure, this new approach successively selects sets of trace points to allow the performance of efficient automatic explorations on program execution states in order to help the developer locate programming faults responsible for the observed execution failure. With each of such sets of trace points, the program state at each trace point is symbolically altered, by negating a certain atomic predicate, to see whether the same failure occurs with symbolic execution continuing from the corresponding program point in the source code. The set of trace points is chosen such that the union of the program states is of the minimum size among all candidate sets. Such a set of trace points is called a minimum debugging frontier set (abr. MDFS). Depending on the result from the symbolic execution, the next MDFS is determined by moving forward or backward on the remaining program trace. This process of trace shortening goes on until the offending faulty code is found. The MDFS approach requires the execution failing location to be provided, but the specification of the desired program state is optional. With such specification, it may achieve a more accurate fault report. To evaluate our approach, we tried it on 15 real bugs from real world programs. Results show that our approach is effective in explaining failures within reasonable time.


title: JSWhiz: Static analysis for JavaScript memory leaks

authors:
Jacques A. Pienaar
Robert Hundt

abstract: JavaScript is the dominant language for implementing dynamic web pages in browsers. Even though it is standardized, many browsers implement language and browser bindings in different and incompatible ways. As a result, a plethora of web development frameworks were developed to hide cross-browser issues and to ease development of large web applications. An unwelcome side-effect of these frameworks is that they can introduce memory leaks, despite the fact that JavaScript is garbage collected. Memory bloat is a major issue for web applications, as it affects user perceived latency and may even prevent large web applications from running on devices with limited resources. In this paper we present JSWhiz, an extension to the open-source Closure JavaScript compiler. Based on experiences analyzing memory leaks in Gmail, JSWhiz detects five identified common problem patterns. JSWhiz found a total of 89 memory leaks across Google's Gmail, Docs, Spread-sheets, Books, and Closure itself. It contributed significantly in a recent effort to reduce Gmail memory footprint, which resulted in bloat reduction of 75% at the 99th percentile, and by roughly 50% at the median.


title: SIMD parallelization of applications that traverse irregular data structures

authors:
Bin Ren
Gagan Agrawal
James R. Larus
Todd Mytkowicz
Tomi Poutanen
Wolfram Schulte

abstract: Fine-grained data parallelism is increasingly common in mainstream processors in the form of longer vectors and on-chip GPUs. This paper develops support for exploiting such data parallelism for a class of non-numeric, non-graphic applications, which perform computations while traversing many independent, irregular data structures. While the traversal of any one irregular data structure does not give opportunity for parallelization, traversing a set of these does. However, mapping such parallelism to SIMD units is nontrivial and not addressed in prior work. We address this problem by developing an intermediate language for specifying such traversals, followed by a run-time scheduler that maps traversals to SIMD units. A key idea in our run-time scheme is converting branches to arithmetic operations, which then allows us to use SIMD hardware. In order to make our approach fast, we demonstrate several optimizations including a stream compaction method that aids with control flow in SIMD, a set of layouts that reduce memory latency, and a tiling approach that enables more effective prefetching. Using our approach, we demonstrate significant increases in single-core performance over optimized baselines for two applications.


title: A fast and low-overhead technique to secure programs against integer overflows

authors:
Raphael Ernani Rodrigues
Victor Hugo Sperle Campos
Fernando Magno Quintão Pereira

abstract: The integer primitive type has upper and lower bounds in many programming languages, including C, and Java. These limits might lead programs that manipulate large integer numbers to produce unexpected results due to overflows. There exists a plethora of works that instrument programs to track the occurrence of these overflows. In this paper we present an algorithm that uses static range analysis to avoid this instrumentation whenever possible. Our range analysis contains novel techniques, such as a notion of “future” bounds to handle comparisons between variables. We have used this algorithm to avoid some checks created by a dynamic instrumentation library that we have implemented in LLVM. This framework has been used to detect overflows in hundreds of C/C++ programs. As a testimony of its effectiveness, our range analysis has been able to avoid 25% of all the overflow checks necessary to secure the C programs in the LLVM test suite. This optimization has reduced the runtime overhead of instrumentation by 50%.


title: On the platform specificity of STM instrumentation mechanisms

authors:
Wenjia Ruan
Yujie Liu
Chao Wang
Michael F. Spear

abstract: Supporting atomic blocks (e.g., Transactional Memory (TM)) can have far-reaching effects on language design and implementation. While much is known about the language-level semantics of TM and the performance of algorithms for implementing TM, little is known about how platform characteristics affect the manner in which a compiler should instrument code to achieve efficient transactional behavior. We explore the interaction between compiler instrumentation and the performance of transactions. Through evaluation on ARM/Android, SPARC/Solaris, IA32/Linux and IA32/MacOS, we show that the compiler must consider the platform when determining which analyses, transformations, and optimizations to perform. Implementation issues include how TM library code is reached, how per-thread TM metadata is stored and accessed, and how a library switches between modes of operation. We also show that different platforms favor different TM algorithms, through the introduction of a new TM algorithm for the ARM processor. Our findings will affect compiler and TM library designers: to achieve peak performance for transactions, the compiler must perform platform-dependent analysis, transformation, and optimization, and the interface to the TM library must differ according to platform.


title: Query-directed adaptive heap cloning for optimizing compilers

authors:
Yulei Sui
Yue Li
Jingling Xue

abstract: Andersen's pointer analysis becomes more precise when applied with full heap cloning but unscalable for large, heap-intensive programs. In contrast, k-callsite-sensitive heap cloning can be faster but less precise for some programs. In this paper, we make one step forward by enhancing Andersen's analysis with QUery-Directed Adaptive (QUDA) heap cloning for optimizing compilers. The novelty of our analysis, called QUDA, lies in performing k-callsite-sensitive heap cloning iteratively, starting with k = 0 (without heap cloning), so that an abstract heap object is cloned at iteration k = i + 1 only if some mayalias queries that are not answered positively at iteration k = i may now be answered more precisely. QUDA, which is implemented in Open64, has the same precision as the state-of-the-art, FULCRA, a version of QUDA with exhaustive heap cloning, but is significantly more scalable. For 10 SPEC2000 C benchmarks and 5 C applications (totalling 840 KLOC) evaluated, QUDA takes only 4+ minutes but exhaustive heap cloning takes 42+ minutes to complete. QUDA takes only 75.1 % of the time that Open64 takes on average to compile these 15 programs under “-O2”.


title: Lightweight fault detection in parallelized programs

authors:
Li Tan
Min Feng
Rajiv Gupta

abstract: A popular approach for producing parallel software is to develop a sequential version of an application and then incrementally introduce parallel constructs to parallelize different parts of the application. During the parallelization process, programming errors may be introduced, causing concurrency bugs. In this paper we develop a technique for runtime detection of data dependence faults (i.e., data races and atomicity violations) introduced during parallelization. By leveraging the availability of two versions of the program, the sequential one and the parallelized one, we comparison check dynamic data dependences exercised during executions of the two versions to identify faults. To reduce the cost of comparison checking we develop three optimizations. The first optimization causes only a subset of dynamically exercised data dependences to be comparison checked. The second optimization shows that not all instances of a dynamically exercised data dependence need to be comparison checked. The third optimization shows that static analysis of parallelizing constructs can be exploited to eliminate the need for executing the parallelized version altogether. In addition, our solution is applicable when different program executions on the same input may follow different execution paths, it is effective in situations where the fault introduced manifests itself rarely during execution, and it is also effective in pinpointing the location of the fault in the program. We implemented and evaluated our approach using ten benchmarks. The experimental results indicate an average slowdown of 3× to perform fault detection.


title: Acceldroid: Co-designed acceleration of Android bytecode

authors:
Cheng Wang
Youfeng Wu
Marcelo Cintra

abstract: A hardware/software co-designed processor transparently supports a ubiquitous ISA (e.g. ×86) with diversified and innovative microarchitectural implementations. It leverages co-designed HW features and dynamic binary translation (DBT) SW to morph existing binary programs to scale performance and save power. On such systems, the portable bytecode of modern dynamic languages (e.g. Java, JavaScript, etc.) is first translated into the code in the architecture ISA by the just-in-time (JIT) compilation in the bytecode virtual machine, and then into the code in the internal implementation ISA by the DBT. This not only incurs the translation overheads twice, but also brings significant emulation inefficiency as the DBT does not have the high level bytecode information. In this paper, we present AccelDroid, which accelerates the Android Dalvik bytecode execution on the HW/SW co-designed processor through direct bytecode translation in the DBT. Our experiments on a HW/SW co-designed Transmeta Efficeon machine show that AccelDroid can improve performance by 78% and save energy by 40% for the CaffeineMark 3.0 benchmark suite.


title: Vlock: Lock virtualization mechanism for exploiting fine-grained parallelism in graph traversal algorithms

authors:
Jie Yan
Guangming Tan
Xiuxia Zhang
Erlin Yao
Ninghui Sun

abstract: For graph traversal applications, fine synchronization is required to exploit massive fine parallelism. However, in the conventional solution using fine-grained locks, locks themselves suffer huge memory cost as well as poor locality for inherent irregular access to vertices. In this paper, we propose a novel fine lock solution-vLock. The key idea is lock virtualization that maps the huge logical lock space to a much smaller physical lock space that can reside in cache during the program life cycle. Lock virtualization effectively reduces lock incurred overheads of both memory cost and cache misses. It also achieves high usability in legacy graph programs, as from users's view vLock is the same as lock methods in Pthreads. We implement vLock as a Pthreads-like library and evaluate its performance in four classical graph algorithms (BFS, SSSP, CC, PageRank). Experiments on a SMP system with two Intel Westemere six-core processors show that, compared to conventional fine locks, vLock significantly reduces locks' cache misses and has competitive performance. Particularly, PageRank with vLock has about 20% performance improvement.


title: Hidp: A hierarchical data parallel language

authors:
Yongpeng Zhang
Frank Mueller

abstract: Problem domains are commonly decomposed hierarchically to fully utilize parallel resources in modern microprocessors. Such decompositions can be provided as library routines, written by experienced experts, for general algorithmic patterns. But such APIs tend to be constrained to certain architectures or data sizes. Integrating them with application code is often an unnecessarily daunting task, especially when these routines need to be closely coupled with user code to achieve better performance. This paper contributes HiDP, a high-level hierarchical data parallel language. The purpose of HiDP is to improve the coding productivity of integrating hierarchical data parallelism without significant loss of performance. HiDP is a source-to-source compiler that converts a very concise data parallel language into CUDA C++ source code. Internally, it performs necessary analysis to compose user code with efficient and architecture-aware code snippets. This paper discusses various aspects of HiDP systematically: the language, the compiler and the run-time system with built-in tuning capabilities. They enable HiDP users to express algorithms in less code than low-level SDKs require for native platforms. HiDP also exposes abundant computing resources of modern parallel architectures. Improved coding productivity tends to come with a sacrifice in performance. Yet, experimental results show that the generated code delivers performance very close to handcrafted native GPU code.


title: Profmig: A framework for flexible migration of program profiles across software versions

authors:
Mingzhou Zhou
Bo Wu
Yufei Ding
Xipeng Shen

abstract: Offline program profiling is costly, especially when software update is frequent. In this paper, we initiate a systematic exploration in cross-version program profile migration, which tries to effectively reuse the valid part of the behavior profiles of an old version of a software for a new version. We explore the effects imposed on profile reusability by the various factors in program behaviors, profile formats, and impact analysis, and introduce ProfMig, a framework for flexible migrations of various profiles. We demonstrate the effectiveness of the techniques on migrating loop trip-count profiles and dynamic call graphs. The migration saves significant (48-67% on average) profiling time with less than 10% accuracy compromised for most programs.


title: Efficient Mapping of Irregular C++ Applications to Integrated GPUs

authors:
Rajkishore Barik
Rashid Kaleem
Deepak Majeti
Brian T. Lewis
Tatiana Shpeisman
Chunling Hu
Yang Ni
Ali-Reza Adl-Tabatabai


title: Warm-Up Simulation Methodology for HW/SW Co-Designed Processors

authors:
Aleksandar Brankovic
Kyriakos Stavrou
Enric Gibert
Antonio González


title: Fine-grained Benchmark Subsetting for System Selection

authors:
Pablo de Oliveira Castro
Yuriy Kashnikov
Chadi Akel
Mihail Popov
William Jalby


title: Call Paths for Pin Tools

authors:
Milind Chabbi
Xu Liu
John M. Mellor-Crummey


title: Estimating the Empirical Cost Function of Routines with Dynamic Workloads

authors:
Emilio Coppa
Camil Demetrescu
Irene Finocchi
Romolo Marotta


title: Single Assignment Compiler, Single Assignment Architecture: Future Gated Single Assignment Form*; Static Single Assignment with Congruence Classes

authors:
Shuhan Ding
John Earnest
Soner Önder


title: Hybrid Hexagonal/Classical Tiling for GPUs

authors:
Tobias Grosser
Albert Cohen
Justin Holewinski
P. Sadayappan
Sven Verdoolaege


title: Extending the PCRE Library with Static Backtracking Based Just-in-Time Compilation Support


title: Simplifying Scalable Graph Processing with a Domain-Specific Language

authors:
Sungpack Hong
Semih Salihoglu
Jennifer Widom
Kunle Olukotun


title: Fix the code. Don't tweak the hardware: A new compiler approach to Voltage-Frequency scaling

authors:
Alexandra Jimborean
Konstantinos Koukos
Vasileios Spiliopoulos
David Black-Schaffer
Stefanos Kaxiras


title: Adaptive Mapping and Parameter Selection Scheme to Improve Automatic Code Generation for GPUs

authors:
Juan Carlos Juega
José Ignacio Gómez
Christian Tenllado
Francky Catthoor


title: Security Signature Inference for JavaScript-based Browser Addons

authors:
Vineeth Kashyap
Ben Hardekopf


title: Dynamic and Adaptive Calling Context Encoding

authors:
Jianjun Li
Zhenjiang Wang
Chenggang Wu
Wei-Chung Hsu
Di Xu


title: Portable and Transparent Host-Device Communication Optimization for GPGPU Environments

authors:
Christos Margiolas
Michael F. P. O'Boyle


title: WatchdogLite: Hardware-Accelerated Compiler-Based Pointer Checking

authors:
Santosh Nagarakatte
Milo M. K. Martin
Steve Zdancewic


title: Fluidic Kernels: Cooperative Execution of OpenCL Programs on Multiple Heterogeneous Devices

authors:
Prasanna Pandit
R. Govindarajan


title: Just-In-Time Software Pipelining

authors:
Hongbo Rong
Hyunchul Park
Youfeng Wu
Cheng Wang


title: Static Reference Analysis for GUI Objects in Android Software

authors:
Atanas Rountev
Dacong Yan


title: A Basic Linear Algebra Compiler

authors:
Daniele G. Spampinato
Markus Püschel


title: Partial Escape Analysis and Scalar Replacement for Java

authors:
Lukas Stadler
Thomas Würthinger
Hanspeter Mössenböck


title: Automated Algorithmic Error Resilience for Structured Grid Problems Based on Outlier Detection

authors:
Amoghavarsha Suresh
John Sartori


title: Non-affine Extensions to Polyhedral Code Generation

authors:
Anand Venkat
Manu Shantharam
Mary W. Hall
Michelle Mills Strout


title: DrDebug: Deterministic Replay based Cyclic Debugging with Dynamic Slicing

authors:
Yan Wang
Harish Patil
Cristiano Pereira
Gregory Lueck
Rajiv Gupta
Iulian Neamtiu


title: Optimizing R VM: Allocation Removal and Path Length Reduction via Interpreter-level Specialization

authors:
Haichuan Wang
Peng Wu
David A. Padua


title: Red Fox: An Execution Environment for Relational Query Processing on GPUs

authors:
Haicheng Wu
Gregory F. Diamos
Tim Sheard
Molham Aref
Sean Baxter
Michael Garland
Sudhakar Yalamanchili


title: Software Transactional Memory for GPU Architectures

authors:
Yunlong Xu
Rui Wang
Nilanjan Goswami
Tao Li
Lan Gao
Depei Qian


title: LeakChecker: Practical Static Memory Leak Detection for Managed Languages

authors:
Dacong Yan
Guoqing Xu
Shengqian Yang
Atanas Rountev


title: Accelerating Dynamic Detection of Uses of Undefined Values with Static Value-Flow Analysis

authors:
Ding Ye
Yulei Sui
Jingling Xue


title: DeltaPath: Precise and Scalable Calling Context Encoding

authors:
Qiang Zeng
Junghwan Rhee
Hui Zhang
Nipun Arora
Guofei Jiang
Peng Liu


title: Getting in control of your control flow with control-data isolation

authors:
William Arthur
Ben Mehne
Reetuparna Das
Todd M. Austin

abstract: Computer security has become a central focus in the information age. Though enormous effort has been expended on ensuring secure computation, software exploitation remains a serious threat. The software attack surface provides many avenues for hijacking; however, most exploits ultimately rely on the successful execution of a control-flow attack. This pervasive diversion of control flow is made possible by the pollution of control flow structure with attacker-injected runtime data. Many control-flow attacks persist because the root of the problem remains: runtime data is allowed to enter the program counter. In this paper, we propose a novel approach: Control-Data Isolation. Our approach provides protection by going to the root of the problem and removing all of the operations that inject runtime data into program control. While previous work relies on CFG edge checking and labeling, these techniques remain vulnerable to attacks such as heap spray, read, or GOT attacks and in some cases suffer high overheads. Rather than addressing control-flow attacks by layering additional complexity, our work takes a subtractive approach; subtracting the primary cause of contemporary control-flow attacks. We demonstrate that control-data isolation can assure the integrity of the programmer's CFG at runtime, while incurring average performance overheads of less than 7% for a wide range of benchmarks.


title: HELIX-UP: relaxing program semantics to unleash parallelization

authors:
Simone Campanoni
Glenn H. Holloway
Gu-Yeon Wei
David M. Brooks

abstract: Automatic generation of parallel code for general-purpose commodity processors is a challenging computational problem. Nevertheless, there is a lot of latent thread-level parallelism in the way sequential programs are actually used. To convert latent parallelism into performance gains, users may be willing to compromise on the quality of a program's results. We have developed a parallelizing compiler and runtime that substantially improve scalability by allowing parallelized code to briefly sidestep strict adherence to language semantics at run time. In addition to boosting performance, our approach limits the sensitivity of parallelized code to the parameters of target CPUs (such as core-to-core communication latency) and the accuracy of data dependence analysis.


title: A parallel abstract interpreter for JavaScript

authors:
Kyle Dewey
Vineeth Kashyap
Ben Hardekopf

abstract: We investigate parallelizing flow- and context-sensitive static analysis for JavaScript. Previous attempts to parallelize such analyses for other languages typically start with the traditional framework of sequential dataflow analysis, and then propose methods to parallelize the existing sequential algorithms within this framework. However, we show that this approach is non-optimal and propose a new perspective on program analysis based on abstract interpretation that separates the analysis into two components: (1) an embarrassingly parallel state exploration of a state transition system; and (2) a separate component that controls the size of the state space by selectively merging states, thus injecting sequential dependencies into the system. This perspective simplifies the parallelization problem and exposes useful opportunities to exploit the natural parallelism of the analysis. We apply our insights to parallelize a JavaScript abstract interpreter. Because of JavaScript's dynamic nature and tricky semantics, static analysis of JavaScript is difficult to scale — one of our benchmarks with only 2.8 KLOC takes over 22 hours to analyze using the sequential JavaScript abstract interpreter. Thus, JavaScript is an excellent case study for the benefits of our approach. Our resulting parallel implementation sees significant benefits on real-world JavaScript programs, with speedups between 2-Ax on average with a superlinear maximum of 36.9× on 12 hardware threads.


title: Characterizing and enhancing global memory data coalescing on GPUs

authors:
Naznin Fauzia
Louis-Noël Pouchet
P. Sadayappan

abstract: Effective parallel programming for GPUs requires careful attention to several factors, including ensuring coalesced access of data from global memory. There is a need for tools that can provide feedback to users about statements in a GPU kernel where non-coalesced data access occurs, and assistance in fixing the problem. In this paper, we address both these needs. We develop a two-stage framework where dynamic analysis is first used to detect and characterize uncoalesced accesses in arbitrary PTX programs. Transformations to optimize global memory access by introducing coalesced access are then implemented, using feedback from the dynamic analysis or using a model-driven approach. Experimental results demonstrate the use of the tools on a number of benchmarks from the Rodinia and Polybench suites.


title: Checking correctness of code generator architecture specifications

authors:
Niranjan Hasabnis
Rui Qiao
R. Sekar

abstract: Modern instruction sets are complex, and extensions are proposed to them frequently. This makes the task of modelling architecture specifications used by the code generators of modern compilers complex and error-prone. Given the important role played by the compilers, it is necessary that they are tested thoroughly, so that most of the bugs are detected early on. Unfortunately, modern compilers such as GCC do not target testing of individual components of a compiler, but instead perform end-to-end testing. In this paper, we target the problem of checking correctness of the architecture specifications used by code generators of modern compilers. Our solution leverages the architecture of modern compilers where a language-specific front-end compiles source-code into an intermediate representation (IR), which is then translated by the compiler's code generator into assembly code. Hence our approach is to test code generators by testing the equivalence of IR snippets and the corresponding assembly code generated. For this purpose, we have developed an efficient, architecture-neutral test case generation strategy. Using our prototype implementation, we performed correctness checking of 140 assembly instructions (80 general-purpose and 60 SSE out of around 600×86 instructions) of GCC's ×86 code generator, and found semantic differences in 39 of them, at least one of which has already been fixed by the GCC community in response to our report. We believe that our approach can be invaluable when developing support for a new architecture, as well as during frequent updates made to existing architectures such as ×86 for the purpose of supporting new instructions.


title: Optimizing binary translation of dynamically generated code

authors:
Byron Hawkins
Brian Demsky
Derek Bruening
Qin Zhao

abstract: Dynamic binary translation serves as a core technology that enables a wide range of important tools such as profiling, bug detection, program analysis, and security. Many of the target applications often include large amounts of dynamically generated code, which poses a special performance challenge in maintaining consistency between the source application and the translated application. This paper introduces two approaches for optimizing binary translation of JITs and other dynamic code generators. First we present a system of efficient source code annotations that allow developers to demarcate dynamic code regions and identify code changes within those regions. The second technique avoids the annotation and source code requirements by automatically inferring the presence of a JIT and instrumenting its write instructions with translation consistency operations. We implemented these techniques in DynamoRIO and demonstrate performance improvements over the state-of-the-art DBT systems on JIT applications as high as 7.3× over base DynamoRIO and Pin.


title: Improving GPGPU energy-efficiency through concurrent kernel execution and DVFS

authors:
Qing Jiao
Mian Lu
Huynh Phung Huynh
Tulika Mitra

abstract: Current generation GPUs can accelerate high-performance, compute-intensive applications by exploiting massive thread-level parallelism. The high performance, however, comes at the cost of increased power consumption. Recently, commercial GPGPU architectures have introduced support for concurrent kernel execution to better utilize the computational/memory resources and thereby improve overall throughput. In this paper, we argue and experimentally validate the benefits of concurrent kernels towards energy-efficient execution. We design power-performance models to carefully select the appropriate kernel combinations to be executed concurrently, the relative contributions of the kernels to the thread mix, along with the frequency choices for the cores and the memory to achieve high performance per watt metric. Our experimental evaluation shows that the concurrent kernel execution in combination with DVFS can improve energy-efficiency by up to 34.5% compared to the most energy-efficient sequential execution.


title: Locality-centric thread scheduling for bulk-synchronous programming models on CPU architectures

authors:
Hee-Seok Kim
Izzat El Hajj
John A. Stratton
Steven S. Lumetta
Wen-mei W. Hwu

abstract: With heterogeneous computing on the rise, executing programs efficiently on different devices from a single source code has become increasingly important. OpenCL, having a bulk-synchronous programming model, has been proposed as a framework for writing such performance-portable programs. Execution order of work-items in a program is unconstrained except at barrier synchronization events, giving some freedom to an implementation when scheduling work-items between synchronization points. Many OpenCL (and CUDA) compilers have been designed for targeting multicore CPU architectures. However, scheduling work-items in prior work has been done with primary focus on correctness and vectorization. To the best of our knowledge, no existing implementations consider the impact of work-item scheduling on data locality. We propose an OpenCL compiler that performs data-locality-centric work-item scheduling. By analyzing the memory addresses accessed in loops within a kernel, our technique can make better decisions on how to schedule work-items to construct better memory access patterns, thereby improving performance. Our approach achieves geomean speedups of 3.32× over AMD's and 1.71 × over Intel's implementations on Parboil and Rodinia benchmarks.


title: A graph-based higher-order intermediate representation

authors:
Roland Leißa
Marcel Köster
Sebastian Hack

abstract: Many modern programming languages support both imperative and functional idioms. However, state-of-the-art imperative intermediate representations (IRs) cannot natively represent crucial functional concepts (like higher-order functions). On the other hand, functional IRs employ an explicit scope nesting, which is cumbersome to maintain across certain transformations. In this paper we present Thorin: a higher-order, functional IR based on continuation-passing style that abandons explicit scope nesting in favor of a dependency graph. This makes Thorin an attractive IR for both imperative as well as functional languages. Furthermore, we present a novel program transformation to eliminate the overhead caused by higher-order functions. The main component of this transformation is lambda mangling: an important transformation primitive in Thorin. We demonstrate that lambda mangling subsumes many classic program transformations like tail-recursion elimination, loop unrolling or (partial) inlining. In our experiments we show that higher-order programs translated with Thorin are consistently as fast as C programs.


title: Automatic data placement into GPU on-chip memory resources

authors:
Chao Li
Yi Yang
Zhen Lin
Huiyang Zhou

abstract: Although graphics processing units (GPUs) rely on thread-level parallelism to hide long off-chip memory access latency, judicious utilization of on-chip memory resources, including register files, shared memory, and data caches, is critical to application performance. However, explicitly managing GPU on-chip memory resources is a non-trivial task for application developers. More importantly, as on-chip memory resources vary among different GPU generations, performance portability has become a daunting challenge. In this paper, we tackle this problem with compiler-driven automatic data placement. We focus on programs that have already been reasonably optimized either manually by programmers or automatically by compiler tools. Our proposed compiler algorithms refine these programs by revising data placement across different types of GPU on-chip resources to achieve both performance enhancement and performance portability. Among 12 benchmarks in our study, our proposed compiler algorithm improves the performance by 1.76× on average on Nvidia GTX480, and by 1.61× on average on GTX680.


title: Data provenance tracking for concurrent programs

authors:
Brandon Lucia
Luis Ceze

abstract: We propose Last Writer Slicing (LWS), a mechanism for tracking data provenance information in multithreaded code in a production setting. Last writer slices dynamically track provenance of values by recording the thread and operation that last wrote each variable. We show that this information complements core dumps and greatly improves debugability. We also propose communication traps (CTraps), an extensible framework that uses LWS to interpose on operations that lead to inter-thread communication. We show how to use CTraps to implement multiple dynamic analysis tools for mulithreaded programs. Our evaluation on server programs and PARSEC benchmarks shows that LWS has low run time overheads (0-15%) for many applications, including mem-cached, LevelDB, MySQL, and Apache. Our debugging case studies of real, buggy programs shows that LWS are indeed useful for debugging.


title: EMEURO: a framework for generating multi-purpose accelerators via deep learning

authors:
Lawrence C. McAfee
Kunle Olukotun

abstract: Approximate computing is a very promising design paradigm for crossing the CPU power wall, primarily driven by the potential to sacrifice output quality for significant gains in performance, energy, and fault tolerance. Unfortunately, existing solutions have primarily either focused on new programming models, or new hardware designs, leaving significant room between these two ends for software-based optimizations. To fill this void, additional efforts should target the compilation and runtime stages, which have a critical impact on controlling the interactions of the many approximate subcomputations to form a well-optimized application. This paper presents EMEURO, a neural-network (NN) based emulation and acceleration platform. By restructuring algorithms to have the same data flow as a NN, EMEURO is able to achieve significant speedup across several domains with minimal design effort. EMEURO uses novel NN-based approximate computing techniques, including methods for efficiently searching the high-dimension subroutine space, and fine-grain control of error during runtime. EMEURO is able to achieve 7×-109× maximum speedup over the original algorithm with 0.1%-10% approximation error.


title: Approximating flow-sensitive pointer analysis using frequent itemset mining

authors:
Vaivaswatha Nagaraj
R. Govindarajan

abstract: Pointer alias analysis is a well researched problem in the area of compilers and program verification. Many recent works in this area have focused on flow-sensitivity due to the additional precision it offers. However, a flow-sensitive analysis is computationally expensive, thus, preventing its use in larger programs. In this work, we observe that a number of object sets, consisting of tens to hundreds of objects appear together and frequently in many points-to sets. By approximating each of these object sets by a single object, we can speedup computation of points-to sets. Although the proposed approach incurs a slight loss in precision, it is shown to be safe. We use a well known data mining technique called frequent itemset mining to find these frequently occurring objects. We compare our approximation to a fully flow-sensitive pointer analysis on a set of ten benchmarks. We measure precision loss using two common client analysis queries and report an average precision loss of 0.25% on one measure and 1.40% on the other. The proposed approach results in a speedup of upto 12.9× (and an average speedup of 6.2×) in computing the points-to sets.


title: Scalable conditional induction variables (CIV) analysis

authors:
Cosmin E. Oancea
Lawrence Rauchwerger

abstract: Subscripts using induction variables that cannot be expressed as a formula in terms of the enclosing-loop indices appear in the low-level implementation of common programming abstractions such as Alter, or stack operations and pose significant challenges to automatic parallelization. Because the complexity of such induction variables is often due to their conditional evaluation across the iteration space of loops we name them Conditional Induction Variables (CIV). This paper presents a flow-sensitive technique that summarizes both such CIV-based and affine subscripts to program level, using the same representation. Our technique requires no modifications of our dependence tests, which is agnostic to the original shape of the subscripts, and is more powerful than previously reported dependence tests that rely on the pairwise disambiguation of read-write references. We have implemented the CIV analysis in our parallelizing compiler and evaluated its impact on five Fortran benchmarks. We have found that that there are many important loops using CIV subscripts and that our analysis can lead to their scalable parallelization. This in turn has led to the parallelization of the benchmark programs they appear in.


title: Snapshot-based loading-time acceleration for web applications

authors:
JinSeok Oh
Soo-Mook Moon

abstract: Web applications (apps) are programmed using HTML, CSS, and JavaScript. Web apps allow a faster app development based on existing web technology and a better portability since they are runnable on any device where a web browser is installed. Unfortunately, web apps are involved with a performance issue due to JavaScript, because its dynamic typing, function object, and prototype are difficult to execute efficiently, so even just-in-time compilers do not help much. In this paper, we propose a new approach to accelerate a web app, especially its loading time. Generally, running an app is composed of app loading to initialize the app, followed by event-driven computation. If the same job needs to be done to load an app, especially the execution of the same JavaScript code, it will be better to save the JavaScript execution state in advance and to start the app from the saved state. In fact, app loading is often involved with the initialization of the web framework such as j Query [1], Enyo [2], or Ext JS [3] where many JavaScript objects are created. Also, app-specific objects are created during app loading. If we save the initialized state of these objects in the form of a snapshot and start app loading by restoring the objects from the snapshot, we would accelerate app loading. We actually implemented the idea for the above three web frameworks, which lead to a 77% reduction of their initialization time. This can reduce the whole app loading time for an Enyo app by at least 20%, which could be noticed tangibly.


title: Optimizing the flash-RAM energy trade-off in deeply embedded systems

authors:
James Pallister
Kerstin Eder
Simon J. Hollis

abstract: Deeply embedded systems often have the tightest constraints on energy consumption, requiring that they consume tiny amounts of current and run on batteries for years. However, they typically execute code directly from flash, instead of the more energy efficient RAM. We implement a novel compiler optimization1that exploits the relative efficiency of RAM by statically moving carefully selected basic blocks from flash to RAM. Our technique uses integer linear programming, with an energy cost model to select a good set of basic blocks to place into RAM, without impacting stack or data storage. We evaluate our optimization on a common ARM microcontroller and succeed in reducing the average power consumption by up to 41% and reducing energy consumption by up to 22%, while increasing execution time. A case study is presented, where an application executes code then sleeps for a period of time. For this example we show that our optimization could allow the application to run on battery for up to 32% longer. We also show that for this scenario the total application energy can be reduced, even if the optimization increases the execution time of the code.


title: PSLP: padded SLP automatic vectorization

authors:
Vasileios Porpodas
Alberto Magni
Timothy M. Jones

abstract: The need to increase performance and power efficiency in modern processors has led to a wide adoption of SIMD vector units. All major vendors support vector instructions and the trend is pushing them to become wider and more powerful. However, writing code that makes efficient use of these units is hard and leads to platform-specific implementations. Compiler-based automatic vectorization is one solution for this problem. In particular the Superword-Level Parallelism (SLP) vectorization algorithm is the primary way to automatically generate vector code starting from straight-line scalar code. SLP is implemented in all major compilers, including GCC and LLVM. SLP relies on finding sequences of isomorphic instructions to pack together into vectors. However, this hinders the applicability of the algorithm as isomorphic code sequences are not common in practice. In this work we propose a solution to overcome this limitation. We introduce Padded SLP (PSLP), a novel vectorization algorithm that can vectorize code containing non-isomorphic instruction sequences. It injects a near-minimal number of redundant instructions into the code to transform non-isomorphic sequences into isomorphic ones. The padded instruction sequence can then be successfully vectorized. Our experiments show that PSLP improves vectorization coverage across a number of kernels and full benchmarks, decreasing execution time by up to 63%.


title: Branch prediction and the performance of interpreters: don't trust folklore

authors:
Erven Rohou
Bharath Narasimha Swamy
André Seznec

abstract: Interpreters have been used in many contexts. They provide portability and ease of development at the expense of performance. The literature of the past decade covers analysis of why interpreters are slow, and many software techniques to improve them. A large proportion of these works focuses on the dispatch loop, and in particular on the implementation of the switch statement: typically an indirect branch instruction. Folklore attributes a significant penalty to this branch, due to its high misprediction rate. We revisit this assumption, considering state-of-the-art branch predictors and the three most recent Intel processor generations on current interpreters. Using both hardware counters on Has well, the latest Intel processor generation, and simulation of the IT-TAGE, we show that the accuracy of indirect branch prediction is no longer critical for interpreters. We further compare the characteristics of these interpreters and analyze why the indirect branch is less important than before.


title: Locality aware concurrent start for stencil applications

authors:
Sunil Shrestha
Guang R. Gao
Joseph B. Manzano
Andrés Márquez
John Feo

abstract: Stencil computations are at the heart of many physical simulations used in scientific codes. Thus, there exists a plethora of optimization efforts for this family of computations. Among these techniques, tiling techniques that allow concurrent start have proven to be very efficient in providing better performance for these critical kernels. Nevertheless, with many core designs being the norm, these optimization techniques might not be able to fully exploit locality (both spatial and temporal) on multiple levels of the memory hierarchy without compromising parallelism. It is no longer true that the machine can be seen as a homogeneous collection of nodes with caches, main memory and an interconnect network. New architectural designs exhibit complex grouping of nodes, cores, threads, caches and memory connected by an ever evolving network-on-chip design. These new designs may benefit greatly from carefully crafted schedules and groupings that encourage parallel actors (i.e. threads, cores or nodes) to be aware of the computational history of other actors in close proximity. In this paper, we provide an efficient tiling technique that allows hierarchical concurrent start for memory hierarchy aware tile groups. Each execution schedule and tile shape exploit the available parallelism, load balance and locality present in the given applications. We demonstrate our technique on the Intel Xeon Phi architecture with selected and representative stencil kernels. We show improvement ranging from 5.58% to 31.17% over existing state-of-the-art techniques.


title: Reactive tiling

authors:
Jithendra Srinivas
Wei Ding
Mahmut T. Kandemir

abstract: To fully exploit the power of emerging multicore architectures, managing shared resources (i.e., caches) across applications and over time is critical. However, to our knowledge, most prior efforts view this problem from the OS/hardware side, and do not consider whether applications themselves can also participate in this process of managing shared resources. In this paper, we show how an application can react to OS/hardware-based resource management decisions by adapting itself (called reactive application), with the goal of maximizing the utilization of the shared resources allocated to it. Specifically, we present a framework that can generate code for adaptive (reactive) tiling, and propose an execution model in which a reactive application can react to the modulations in its cache space allocations to prevent its performance from degrading. One can expect two potential benefits from this approach. First, matching tile size to available cache capacity dynamically (during execution) improves performance of the target application. Second and equally important, better utilization of shared cache space reduces pressure on other applications (co-runners) that execute concurrently with the target application. Our experimental results show that the proposed scheme improves the performance of applications (over the best static tiles) by 8.4%, on average, when using synthetic cache allocations. Further with dynamic cache allocations determined by the utility-based cache partitioning (a state-of-the-art cache partitioning scheme), it improves performance of a set of eleven HPC applications by 11.3%.


title: MemorySanitizer: fast detector of uninitialized memory use in C++

authors:
Evgeniy Stepanov
Konstantin Serebryany

abstract: This paper presents MemorySanitizer, a dynamic tool that detects uses of uninitialized memory in C and C++. The tool is based on compile time instrumentation and relies on bit-precise shadow memory at run-time. Shadow propagation technique is used to avoid false positive reports on copying of uninitialized memory. MemorySanitizer finds bugs at a modest cost of 2.5× in execution time and 2× in memory usage; the tool has an optional origin tracking mode that provides better reports with moderate extra overhead. The reports with origins are more detailed compared to reports from other similar tools; such reports contain names of local variables and the entire history of the uninitialized memory including intermediate stores. In this paper we share our experience in deploying the tool at a large scale and demonstrate the benefits of compile-time instrumentation over dynamic binary instrumentation.


title: Optimizing and auto-tuning scale-free sparse matrix-vector multiplication on Intel Xeon Phi

authors:
Wai Teng Tang
Ruizhe Zhao
Mian Lu
Yun Liang
Huynh Phung Huyng
Xibai Li
Rick Siow Mong Goh

abstract: Recently, the Intel Xeon Phi coprocessor has received increasing attention in high performance computing due to its simple programming model and highly parallel architecture. In this paper, we implement sparse matrix vector multiplication (SpMV) for scale-free matrices on the Xeon Phi architecture and optimize its performance. Scale-free sparse matrices are widely used in various application domains, such as in the study of social networks, gene networks and web graphs. We propose a novel SpMV format called vectorized hybrid COO+CSR (VHCC). Our SpMV implementation employs 2D jagged partitioning, tiling and vectorized prefix sum computations to improve hardware resource utilization, and thus overall performance. As the achieved performance depends on the number of vertical panels, we also develop a performance tuning method to guide its selection. Experimental results demonstrate that our SpMV implementation achieves an average 3× speedup over Intel MKL for a wide range of scale-free matrices.


title: HERMES: a fast cross-ISA binary translator with post-optimization

authors:
Xiaochun Zhang
Qi Guo
Yunji Chen
Tianshi Chen
Weiwu Hu

abstract: In the era of mobile and cloud computing, cross-ISA (Instruction Set Architecture) binary translation attracts increasing attentions due to the ISA diversity of computing platforms. To easily adapt to vast guest- and host-ISAs with minimal porting efforts, existing cross-ISA binary translators (e.g., QEMU) are typically built upon ISA-independent Intermediate Representation (IR). Although IR conceals the architectural details of different IS As, it also prevents enforcing several effective ISA-specific optimizations, which results in severe performance degradation. To improve the performance of cross-ISA binary translation without loss of portability, we present a fast cross-ISA binary translator, Hermes, by conducting post-optimization on the translated code, rather than on the IR as conventional binary translators do. The proposed post-optimization technique uses Host-specific Data Dependence Graph (HDDG) to significantly eliminate redundant instructions, including arithmetic, load/store and call/return-emulation instructions. To validate our approach, we implement Hermes on a commercial MIPS host system for both ×86 and ARM guest. Compared with QEMU dynamic binary translator, HERMES improves the performance by a factor of 3.14× and 5.18× for ×86 and ARM guest, respectively. Compared with state-of-the-art static binary translator, HERMES achieves comparable performance, while it reduces the translation overhead by 185×.


title: On performance debugging of unnecessary lock contentions on multicore processors: a replay-based approach

authors:
Long Zheng
Xiaofei Liao
Bingsheng He
Song Wu
Hai Jin

abstract: Locks have been widely used as an effective synchronization mechanism among processes and threads. However, we observe that a large number of false inter-thread dependencies (i.e., unnecessary lock contentions) exist during the program execution on multicore processors, thereby incurring significant performance overhead. This paper presents a performance debugging framework, PerfPlay, to facilitate a comprehensive and in-depth understanding of the performance impact of unnecessary lock contentions. The core technique of our debugging framework is trace replay. Specifically, PerfPlay records the program execution trace, on the basis of which the unnecessary lock contentions can be identified through trace analysis. We then propose a novel technique of trace transformation to transform these identified unnecessary lock contentions in the original trace into the correct pattern as a new trace free of unnecessary lock contentions. Through replaying both traces, PerfPlay can quantify the performance impact of unnecessary lock contentions. To demonstrate the effectiveness of our debugging framework, we study five real-world programs and PARSEC benchmarks. Our experimental results demonstrate the significant performance overhead of unnecessary lock contentions, and the effectiveness of PerfPlay in identifying the performance critical unnecessary lock contentions in real applications.


title: Trace-based affine reconstruction of codes

authors:
Gabriel Rodríguez
José M. Andión
Mahmut T. Kandemir
Juan Touriño

abstract: Complete comprehension of loop codes is desirable for a variety of program optimizations. Compilers perform static code analyses and transformations, such as loop tiling or memory partitioning, by constructing and manipulating formal representations of the source code. Runtime systems observe and characterize application behavior to drive resource management and allocation, including dependence detection and parallelization, or scheduling. However, the source codes of target applications are not always available to the compiler or runtime system in an analyzable form. It becomes necessary to find alternate ways to model application behavior. This paper presents a novel mathematical framework to rebuild loops from their memory access traces. An exploration engine traverses a tree-like solution space, driven by the access strides in the trace. It is guaranteed that the engine will find the minimal affine nest capable of reproducing the observed sequence of accesses by exploring this space in a brute force fashion, but most real traces will not be tractable in this way. Methods for an efficient solution space traversal based on mathematical properties of the equation systems which model the solution space are proposed. The experimental evaluation shows that these strategies achieve efficient loop reconstruction, processing hundreds of gigabytes of trace data in minutes. The proposed approach is capable of correctly and minimally reconstructing 100% of the static control parts in PolyBench/C applications. As a side effect, the trace reconstruction process can be used to efficiently compress trace files. The proposed tool can also be used for dynamic access characterization, predicting over 99% of future memory accesses.


title: Opening polyhedral compiler's black box

authors:
Lénaïc Bagnères
Oleksandr Zinenko
Stéphane Huot
Cédric Bastoul

abstract: While compilers offer a fair trade-off between productivity and executable performance in single-threaded execution, their optimizations remain fragile when addressing compute-intensive code for parallel architectures with deep memory hierarchies. Moreover, these optimizations operate as black boxes, impenetrable for the user, leaving them with no alternative to time-consuming and error-prone manual optimization in cases where an imprecise cost model or a weak analysis resulted in a bad optimization decision. To address this issue, we propose a technique allowing to automatically translate an arbitrary polyhedral optimization, used internally by loop-level optimization frameworks of several modern compilers, into a sequence of comprehensible syntactic transformations as long as this optimization focuses on scheduling loop iterations. This approach opens the black box of the polyhedral frameworks enabling users to examine, refine, replay and even design complex optimizations semi-automatically in partnership with the compiler.


title: A black-box approach to energy-aware scheduling on integrated CPU-GPU systems

authors:
Rajkishore Barik
Naila Farooqui
Brian T. Lewis
Chunling Hu
Tatiana Shpeisman

abstract: Energy efficiency is now a top design goal for all computing systems, from fitness trackers and tablets, where it affects battery life, to cloud computing centers, where it directly impacts operational cost, maintainability, and environmental impact. Today's widespread integrated CPU-GPU processors combine a CPU and a GPU compute device with different power-performance characteristics. For these integrated processors, hardware vendors implement automatic power management policies that are typically not exposed to the end-user. Furthermore, these policies often vary between different processor generations and SKUs. As a result, it is challenging to design a generally-applicable energy-aware runtime to schedule work onto both the CPU and GPU of such integrated CPU-GPU processors to optimize energy consumption. We propose a new black-box scheduling technique to reduce energy use by effectively partitioning work across the CPU and GPU cores of integrated CPU-GPU processors. Our energy-aware scheduler combines a power model with information about the runtime behavior of a specific workload. This power model is computed once for each processor to characterize its power consumption for different kinds of workloads. On two widely different platforms, a high-end desktop system and a low-power tablet, our energy-aware runtime yields an energy-delay product that is 96% and 93%, respectively, of the near-ideal Oracle energy-delay product on a diverse set of workloads.


title: Have abstraction and eat performance, too: optimized heterogeneous computing with parallel patterns

authors:
Kevin J. Brown
HyoukJoong Lee
Tiark Rompf
Arvind K. Sujeeth
Christopher De Sa
Christopher R. Aberger
Kunle Olukotun

abstract: High performance in modern computing platforms requires programs to be parallel, distributed, and run on heterogeneous hardware. However programming such architectures is extremely difficult due to the need to implement the application using multiple programming models and combine them together in ad-hoc ways. To optimize distributed applications both for modern hardware and for modern programmers we need a programming model that is sufficiently expressive to support a variety of parallel applications, sufficiently performant to surpass hand-optimized sequential implementations, and sufficiently portable to support a variety of heterogeneous hardware. Unfortunately existing systems tend to fall short of these requirements. In this paper we introduce the Distributed Multiloop Language (DMLL), a new intermediate language based on common parallel patterns that captures the necessary semantic knowledge to efficiently target distributed heterogeneous architectures. We show straightforward analyses that determine what data to distribute based on its usage as well as powerful transformations of nested patterns that restructure computation to enable distribution and optimize for heterogeneous devices. We present experimental results for a range of applications spanning multiple domains and demonstrate highly efficient execution compared to manually-optimized counterparts in multiple distributed programming models.


title: Validating optimizations of concurrent C/C++ programs

authors:
Soham Chakraborty
Viktor Vafeiadis

abstract: We present a validator for checking the correctness of LLVM compiler optimizations on C11 programs as far as concurrency is concerned. Our validator checks that optimizations do not change memory accesses in ways disallowed by the C11 and/or LLVM memory models. We use a custom C11 concurrent program generator to trigger multiple LLVM optimizations and evaluate the efficacy of our validator. Our experiments highlighted the difference between the C11 and LLVM memory models, and uncovered a number of previously unknown compilation errors in the LLVM optimizations involving the C11 concurrency primitives.


title: Exploiting recent SIMD architectural advances for irregular applications

authors:
Linchuan Chen
Peng Jiang
Gagan Agrawal

abstract: A broad class of applications involve indirect or datadependent memory accesses and are referred to as irregular applications. Recent developments in SIMD architectures – specifically, the emergence of wider SIMD lanes, combination of SIMD parallelism with many-core MIMD parallelism, and more flexible programming APIs – are providing new opportunities as well as challenges for this class of applications. In this paper, we propose a general opti- mization methodology, to effectively optimize different subclasses of irregular applications. Based on the observation that all applications with indirect memory accesses can be viewed as sparse matrix computations, we design an optimization methodology, which includes three sub-steps: 1) locality enhancement through tiling, 2) data access pattern identification, and 3) write conflict removal at both SIMD and MIMD levels. This method has been applied to unstructured grids, molecular dynamics, and graph applications, in addition to sparse matrix computations. The speedups achieved by our single threaded vectorized code over serial code is up to 9.05, whereas the overall speedup while utilizing both SIMD and MIMD (61 cores in Intel Xeon Phi) with our approach is up to 467.1. Further optimization using matrix reordering on irregular reductions and graph algorithms is able to achieve an incremental speedup of up to 1.69, though at a relatively high preprocessing cost. Moreover, SpMM using our approach outperforms routines from a highly optimized commercial library by up to 2.81x.


title: AutoFDO: automatic feedback-directed optimization for warehouse-scale applications

authors:
Dehao Chen
Xinliang David Li
Tipp Moseley

abstract: AutoFDO is a system to simplify real-world deployment of feedback-directed optimization (FDO). The system works by sampling hardware performance monitors on production machines and using those profiles in to guide optimization. Profile data is stale by design, and we have implemented compiler features to deliver stable speedup across releases. The resulting performance is a geomean of 10.5% improvement on our benchmarks. AutoFDO achieves 85% of the gains of traditional FDO, despite imprecision due to sampling and information lost in the compilation pipeline. The system is deployed to hundreds of binaries at Google, and it is extremely easy to enable; users need only to add some flags to their release build. To date, AutoFDO has increased the number of FDO users at Google by 8X and has doubled the number of cycles spent in FDO-optimized binaries. Over half of CPU cycles used are now spent in some flavor of FDO-optimized binaries.


title: Flexible on-stack replacement in LLVM

authors:
Daniele Cono D'Elia
Camil Demetrescu

abstract: On-Stack Replacement (OSR) is a technique for dynamically transferring execution between different versions of a function at run time. OSR is typically used in virtual machines to interrupt a long-running function and recompile it at a higher optimization level, or to replace it with a different one when a speculative assumption made during its compilation no longer holds. In this paper we present a framework for OSR that introduces novel ideas and combines features of existing techniques that no previous solution provided simultaneously. New features include OSR with compensation code to adjust the program state during a transition and the ability to fire an OSR from arbitrary locations in the code. Our approach is platform-independent as the OSR machinery is entirely encoded at a compiler’s intermediate representation level. We implement and evaluate our technique in the LLVM compiler infrastructure, which is gaining popularity as Just-In-Time (JIT) compiler in virtual machines for dynamic languages such as Javascript, MATLAB, Python, and Ruby. As a case study of our approach, we show how to improve the state of the art in the optimization of the feval instruction, a performance-critical construct of the MATLAB language.


title: BlackBox: lightweight security monitoring for COTS binaries

authors:
Byron Hawkins
Brian Demsky
Michael B. Taylor

abstract: After a software system is compromised, it can be difficult to understand what vulnerabilities attackers exploited. Any information residing on that machine cannot be trusted as attackers may have tampered with it to cover their tracks. Moreover, even after an exploit is known, it can be difficult to determine whether it has been used to compromise a given machine. Aviation has long-used black boxes to better understand the causes of accidents, enabling improvements that reduce the likelihood of future accidents. Many attacks introduce abnormal control flows to compromise systems. In this paper, we present BlackBox, a monitoring system for COTS software. Our techniques enable BlackBox to efficiently monitor unexpected and potentially harmful control flow in COTS binaries. BlackBox constructs dynamic profiles of an application's typical control flows to filter the vast majority of expected control flow behavior, leaving us with a manageable amount of data that can be logged across the network to remote devices. Modern applications make extensive use of dynamically generated code, some of which varies greatly between executions. We introduce support for code generators that can detect security-sensitive behaviors while allowing BlackBox to avoid logging the majority of ordinary behaviors. We have implemented BlackBox in DynamoRIO. We evaluate the runtime overhead of BlackBox, and show that it can effectively monitor recent versions of Microsoft Office and Google Chrome. We show that in ROP, COOP, and state- of-the-art JIT injection attacks, BlackBox logs the pivotal actions by which the attacker takes control, and can also blacklist those actions to prevent repeated exploits.


title: Portable performance on asymmetric multicore processors

authors:
Ivan Jibaja
Ting Cao
Stephen M. Blackburn
Kathryn S. McKinley

abstract: Static and dynamic power constraints are steering chip manufacturers to build single-ISA Asymmetric Multicore Processors (AMPs) with big and small cores. To deliver on their energy efficiency potential, schedulers must consider core sensitivity, load balance, and the critical path. Applying these criteria effectively is challenging especially for complex and non-scalable multithreaded applications. We demonstrate that runtimes for managed languages, which are now ubiquitous, provide a unique opportunity to abstract over AMP complexity and inform scheduling with rich semantics such as thread priorities, locks, and parallelism— information not directly available to the hardware, OS, or application. We present the WASH AMP scheduler, which (1) automatically identifies and accelerates critical threads in concurrent, but non-scalable applications; (2) respects thread priorities; (3) considers core availability and thread sensitivity; and (4) proportionally schedules threads on big and small cores to optimize performance and energy. We introduce new dynamic analyses that identify critical threads and classify applications as sequential, scalable, or non-scalable. Compared to prior work, WASH improves performance by 20% and energy by 9% or more on frequency-scaled AMP hardware (not simulation). Performance advantages grow to 27% when asymmetry increases. Performance advantages are robust to a complex multithreaded adversary independently scheduled by the OS. WASH effectively identifies and optimizes a wider class of workloads than prior work.


title: NRG-loops: adjusting power from within applications

authors:
Melanie Kambadur
Martha A. Kim

abstract: NRG-Loops are source-level abstractions that allow an application to dynamically manage its power and energy through adjustments to functionality, performance, and accuracy. The adjustments, which come in the form of truncated, adapted, or perforated loops, are conditionally enabled as runtime power and energy constraints dictate. NRG-Loops are portable across different hardware platforms and operating systems and are complementary to existing system-level efficiency techniques, such as DVFS and idle states. Using a prototype C library supported by commodity hardware energy meters (and with no modifications to the compiler or operating system), this paper demonstrates four NRG-Loop applications that in 2-6 lines of source code changes can save up to 55% power and 90% energy, resulting in up to 12X better energy efficiency than system-level techniques


title: Re-constructing high-level information for language-specific binary re-optimization

authors:
Toshihiko Koju
Reid Copeland
Motohiro Kawahito
Moriyoshi Ohara

abstract: In this paper, we show a binary optimizer can achieve competitive performance relative to a state-of-the-art source code compiler by re-constructing high-level information (HLI) from binaries. Recent advances in compiler technologies have resulted in a large performance gap between binaries compiled with old compilers and those compiled with latest ones. This motivated us to develop a binary optimizer for old binaries using a compiler engine for a latest source code compiler. However, a traditional approach to naively convert machine instructions into an intermediate representation (IR) of the compiler engine, does not allow us to take full advantage of optimization techniques available in the compiler. This is because the HLI, such as information about variables and their data types, is not available in such an IR. To address this issue, we have devised a technique to re-construct the HLI from binaries by using contextual information. This contextual information is a set of knowledge about specific compilation technologies, such as the conventions of data structures, the patterns of instruction sequences, and the semantics of runtime routines. With this technique, our binary optimizer has improved the performance of binaries generated from an older compiler by 40.1% on average in the CPU time for a set of benchmarks, which is close to the one due to a source-code recompilation with the same compiler engine, 55.2% on average.


title: IPAS: intelligent protection against silent output corruption in scientific applications

authors:
Ignacio Laguna
Martin Schulz
David F. Richards
Jon Calhoun
Luke N. Olson

abstract: This paper presents IPAS, an instruction duplication technique that protects scientific applications from silent data corruption (SDC) in their output. The motivation for IPAS is that, due to natural error masking, only a subset of SDC errors actually affects the output of scientific codes—we call these errors silent output corruption (SOC) errors. Thus applications require duplication only on code that, when affected by a fault, yields SOC. We use machine learning to learn code instructions that must be protected to avoid SOC, and, using a compiler, we protect only those vulnerable instructions by duplication, thus significantly reducing the overhead that is introduced by instruction duplication. In our experiments with five workloads, IPAS reduces the percentage of SOC by up to 90% with a slowdown that ranges between 1.04x and 1.35x, which corresponds to as much as 47% less slowdown than state-of-the-art instruction duplication techniques.


title: Cheetah: detecting false sharing efficiently and effectively

authors:
Tongping Liu
Xu Liu

abstract: False sharing is a notorious performance problem that may occur in multithreaded programs when they are running on ubiquitous multicore hardware. It can dramatically degrade the performance by up to an order of magnitude, significantly hurting the scalability. Identifying false sharing in complex programs is challenging. Existing tools either incur significant performance overhead or do not provide adequate information to guide code optimization. To address these problems, we develop Cheetah, a profiler that detects false sharing both efficiently and effectively. Cheetah leverages the lightweight hardware performance monitoring units (PMUs) that are available in most modern CPU architectures to sample memory accesses. Cheetah develops the first approach to quantify the optimization potential of false sharing instances without actual fixes, based on the latency information collected by PMUs. Cheetah precisely reports false sharing and provides insightful optimization guidance for programmers, while adding less than 7% runtime overhead on average. Cheetah is ready for real deployment.


title: Portable and transparent software managed scheduling on accelerators for fair resource sharing

authors:
Christos Margiolas
Michael F. P. O'Boyle

abstract: Accelerators, such as Graphic Processing Units (GPUs), are popular components of modern parallel systems. Their energy-efficient performance make them attractive components for modern data center nodes. However, they lack control for fair resource sharing amongst multiple users. This paper presents a runtime and Just In Time compiler that enable resource sharing control and software managed scheduling on accelerators. It is portable and transparent, requiring no modification or recompilation of existing systems or user applications. We provide an extensive evaluation of our scheme with over 40,000 different workloads on 2 platforms and we deliver fairness improvements ranging from 6.8x to 13.66x. In addition, we also deliver system throughput speedups ranging from 1.13x to 1.31x.


title: Communication-aware mapping of stream graphs for multi-GPU platforms

authors:
Dong Nguyen
Jongeun Lee

abstract: Stream graphs can provide a natural way to represent many applications in multimedia and DSP domains. Though the exposed parallelism of stream graphs makes it relatively easy to map them to GP (General Purpose)-GPUs, very large stream graphs as well as how to best exploit multi-GPU platforms to achieve scalable performance poses great challenges for stream graph mapping. Previous work considers either a single GPU only or is based on a crude heuristic that achieves a very low degree of workload balancing, and thus shows only limited scalability. In this paper we present a highly scalable GP-GPU mapping technique for large stream graphs with the following highlights: (1) an accurate GPU performance estimation model for subsets of stream graphs, (2) a novel partitioning heuristic exploiting stream graph's structural properties, and (3) ILP (Integer Linear Programming) formulation of the mapping problem. Our experimental results on a real GPU platform demonstrate that our technique can generate scalable performance for up to 4 GPUs with large stream graphs, and can generate highly optimized multi-GPU code especially for compute-bound ones.


title: Symbolic range analysis of pointers

authors:
Vitor Paisante
Maroua Maalej
Leonardo Barbosa e Oliveira
Laure Gonnord
Fernando Magno Quintão Pereira

abstract: Alias analysis is one of the most fundamental techniques that compilers use to optimize languages with pointers. However, in spite of all the attention that this topic has received, the current state-of-the-art approaches inside compilers still face challenges regarding precision and speed. In particular, pointer arithmetic, a key feature in C and C++, is yet to be handled satisfactorily. This paper presents a new alias analysis algorithm to solve this problem. The key insight of our approach is to combine alias analysis with symbolic range analysis. This combination lets us disambiguate fields within arrays and structs, effectively achieving more precision than traditional algorithms. To validate our technique, we have implemented it on top of the LLVM compiler. Tests on a vast suite of benchmarks show that we can disambiguate several kinds of C idioms that current state-of-the-art analyses cannot deal with. In particular, we can disambiguate 1.35x more queries than the alias analysis currently available in LLVM. Furthermore, our analysis is very fast: we can go over one million assembly instructions in 10 seconds.


title: StructSlim: a lightweight profiler to guide structure splitting

authors:
Probir Roy
Xu Liu

abstract: Memory access latency continues to be a dominant bottleneck in a large class of applications on modern architectures. To optimize memory performance, it is important to utilize the locality in the memory hierarchy. Structure splitting can significantly improve memory locality. However, pinpointing inefficient code and providing insightful guidance for structure splitting is challenging. Existing tools typically leverage heavyweight memory instrumentations, which hinders the applicability of these tools for real long-running programs. To address this issue, we develop StructSlim, a profiler to pinpoint top candidates that benefit from structure splitting. StructSlim makes three unique contributions. First, it adopts lightweight address sampling to collect and analyze memory traces. Second, StructSlim employs a set of novel methods to determine memory access patterns to guide structure splitting. We also formally prove that our method has high accuracy even with sparse memory access samples. Third, StructSlim scales on multithreaded machines. StructSlim works on fully optimized, unmodified binary executables independently from their compiler and language, incurring around 7% runtime overhead. To evaluate StructSlim, we study seven sequential and parallel benchmarks. With the guidance of StructSlim, we are able to significantly improve all these benchmarks; the speedup is up to 1.37x.


title: A basic linear algebra compiler for structured matrices

authors:
Daniele G. Spampinato
Markus Püschel

abstract: Many problems in science and engineering are in practice modeled and solved through matrix computations. Often, the matrices involved have structure such as symmetric or triangular, which reduces the operations count needed to perform the computation. For example, dense linear systems of equations are solved by first converting to triangular form and optimization problems may yield matrices with any kind of structure. The well-known BLAS (basic linear algebra subroutine) interface provides a small set of structured matrix computations, chosen to serve a certain set of higher level functions (LAPACK). However, if a user encounters a computation or structure that is not supported, she loses the benefits of the structure and chooses a generic library. In this paper, we address this problem by providing a compiler that translates a given basic linear algebra computation on structured matrices into optimized C code, optionally vectorized with intrinsics. Our work combines prior work on the Spiral-like LGen compiler with techniques from polyhedral compilation to mathematically capture matrix structures. In the paper we consider upper/lower triangular and symmetric matrices but the approach is extensible to a much larger set including blocked structures. We run experiments on a modern Intel platform against the Intel MKL library and a baseline implementation showing competitive performance results for both BLAS and non-BLAS functionalities.


title: Sparse flow-sensitive pointer analysis for multithreaded programs

authors:
Yulei Sui
Peng Di
Jingling Xue

abstract: For C programs, flow-sensitivity is important to enable pointer analysis to achieve highly usable precision. Despite significant recent advances in scaling flow-sensitive pointer analysis sparsely for sequential C programs, relatively little progress has been made for multithreaded C programs. In this paper, we present FSAM, a new Flow-Sensitive pointer Analysis that achieves its scalability for large Multithreaded C programs by performing sparse analysis on top of a series of thread interference analysis phases. We evaluate FSAM with 10 multithreaded C programs (with more than 100K lines of code for the largest) from Phoenix-2.0, Parsec-3.0 and open-source applications. For two programs, raytrace and x264, the traditional data-flow-based flow-sensitive pointer analysis is un- scalable (under two hours) but our analysis spends just under 5 minutes on raytrace and 9 minutes on x264. For the rest, our analysis is 12x faster and uses 28x less memory.


title: Inference of peak density of indirect branches to detect ROP attacks

authors:
Mateus Tymburibá
Rubens E. A. Moreira
Fernando Magno Quintão Pereira

abstract: A program subject to a Return-Oriented Programming (ROP) attack usually presents an execution trace with a high frequency of indirect branches. From this observation, several researchers have proposed to monitor the density of these instructions to detect ROP attacks. These techniques use universal thresholds: the density of indirect branches that characterizes an attack is the same for every application. This paper shows that universal thresholds are easy to circumvent. As an alternative, we introduce an inter-procedural semi-context-sensitive static code analysis that estimates the maximum density of indirect branches possible for a program. This analysis determines detection thresholds for each application; thus, making it more difficult for attackers to compromise programs via ROP. We have used an implementation of our technique in LLVM to find specific thresholds for the programs in SPEC CPU2006. By comparing these thresholds against actual execution traces of corresponding programs, we demonstrate the accuracy of our approach. Furthermore, our algorithm is practical: it finds an approximate solution to a theoretically undecidable problem, and handles programs with up to 700 thousand assembly instructions in 25 minutes.


title: Towards automatic significance analysis for approximate computing

authors:
Vassilis Vassiliadis
Jan Riehme
Jens Deussen
Konstantinos Parasyris
Christos D. Antonopoulos
Nikolaos Bellas
Spyros Lalis
Uwe Naumann

abstract: Several applications may trade-off output quality for energy efficiency by computing only an approximation of their output. Current approaches to software-based approximate computing often require the programmer to specify parts of the code or data structures that can be approximated. A largely unaddressed challenge is how to automate the analysis of the significance of code for the output quality. To this end, we propose a methodology and toolset for automatic significance analysis. We use interval arithmetic and algorithmic differentiation in our profile-driven yet mathematical approach to evaluate the significance of input and intermediate variables for the output of a computation. Our methodology effectively matches decisions of a domain expert in significance characterization for a set of benchmarks, and in some cases offers new insights. Evaluation of the software infrastructure on a multicore x86 platform shows energy reduction (from 31% up to 91% with a mean of 56% compared to fully accurate execution, with graceful quality degradation.