waashk/dblp huggingface dataset:
commutativity analysis for software parallelization: letting program transformations see the big picture. extracting performance from many-core architectures requires software engineers to create multi-threaded applications, which significantly complicates the already daunting task of software development. one solution to this problem is automatic compile-time parallelization, which can ease the burden on software developers in many situations. clearly, automatic parallelization in its present form is not suitable for many application domains and new compiler analyses are needed address its shortcomings. in this paper, we present one such analysis: a new approach for detecting commutative functions. commutative functions are sections of code that can be executed in any order without affecting the outcome of the application, e.g., inserting elements into a set. previous research on this topic had one significant limitation, in that the results of a commutative functions must produce identical memory layouts. this prevented previous techniques from detecting functions like malloc, which may return different pointers depending on the order in which it is called, but these differing results do not affect the overall output of the application. our new commutativity analysis correctly identify these situations to better facilitate automatic parallelization. we demonstrate that this analysis can automatically extract significant amounts of parallelism from many applications, and where it is ineffective it can provide software developers a useful list of functions that may be commutative provided semantic program changes that are not automatable.
impact of virtualization on computer architecture and operating systems. abstract this talk describes how virtualization is changing the way computing is done in the industry today and how it is causing users to rethink how they view hardware, operating systems, and application programs. the talk will describe this new view on computing and the benefits driving users to adopt it. the changing roles for hardware and operating systems will be discussed along with what changes will be needed to efficiently and simply support this new computing model. i will conclude with a discussion of areas where industry could use input from the asplos research community.
assure: automatic software self-healing using rescue points. software failures in server applications are a significant problem for preserving system availability. we present assure, a system that introduces rescue points that recover software from unknown faults while maintaining both system integrity and availability, by mimicking system behavior under known error conditions. rescue points are locations in existing application code for handling a given set of programmer-anticipated failures, which are automatically repurposed and tested for safely enabling fault recovery from a larger class of (unanticipated) faults. when a fault occurs at an arbitrary location in the program, assure restores execution to an appropriate rescue point and induces the program to recover execution by virtualizing the program's existing error-handling facilities. rescue points are identified using fuzzing, implemented using a fast coordinated checkpoint-restart mechanism that handles multi-process and multi-threaded applications, and, after testing, are injected into production code using binary patching. we have implemented an assure linux prototype that operates without application source code and without base operating system kernel changes. our experimental results on a set of real-world server applications and bugs show that assure enabled recovery for all of the bugs tested with fast recovery times, has modest performance overhead, and provides automatic self-healing orders of magnitude faster than current human-driven patch deployment methods.
a program transformation and architecture support for quantum uncomputation. quantum computing's power comes from new algorithms that exploit quantum mechanical phenomena for computation. quantum algorithms are different from their classical counterparts in that quantum algorithms rely on algorithmic structures that are simply not present in classical computing. just as classical program transformations and architectures have been designed for common classical algorithm structures, quantum program transformations and quantum architectures should be designed with quantum algorithms in mind. because quantum algorithms come with these new algorithmic structures, resultant quantum program transformations and architectures may look very different from their classical counterparts.this paper focuses on uncomputation, a critical and prevalent structure in quantum algorithms, and considers how program transformations, and architecture support should be designed to accommodate uncomputation. in this paper,we show a simple quantum program transformation that exposes independence between uncomputation and later computation. we then propose a multicore architecture tailored to this exposed parallelism and propose a scheduling policy that efficiently maps such parallelism to the multicore architecture. our policy achieves parallelism between uncomputation and later computation while reducing cumulative communication distance. our scheduling and architecture allows significant speedup of quantum programs (between 1.8x and 2.8x speedup in shor's factoring algorithm), while reducing cumulative communication distance 26%.
streamray: a stream filtering architecture for coherent ray tracing. the wide availability of commodity graphics processors has made real-time graphics an intrinsic component of the human/computer interface. these graphics cores accelerate the z-buffer algorithm and provide a highly interactive experience at a relatively low cost. however, many applications in entertainment, science, and industry require high quality lighting effects such as accurate shadows, reflection, and refraction. these effects can be difficult to achieve with z-buffer algorithms but are straightforward to implement using ray tracing. although ray tracing is computationally more complex, the algorithm exhibits excellent scaling and parallelism properties. nevertheless, ray tracing memory access patterns are difficult to predict and the parallelism speedup promise is therefore hard to achieve. this paper highlights a novel approach to ray tracing based on stream filtering and presents streamray, a multicore wide simd microarchitecture that delivers interactive frame rates of 15-32 frames/second for scenes of high geometric complexity and exhibits high utilization for simd widths ranging from eight to 16 elements. streamray consists of two main components: the ray engine, which is responsible for stream assembly and employs address generation units that generate addresses to form large simd vectors, and the filter engine, which implements the ray tracing operations with programmable accelerators. results demonstrate that separating address and data processing reduces data movement and resource contention. performance improves by 56% while simultaneously providing 11.63% power savings per accelerator core compared to a design which does not use separate resources for address and data computations.
ultra low-cost defect protection for microprocessor pipelines. the sustained push toward smaller and smaller technology sizes has reached a point where device reliability has moved to the forefront of concerns for next-generation designs. silicon failure mechanisms, such as transistor wearout and manufacturing defects, are a growing challenge that threatens the yield and product lifetime of future systems. in this paper we introduce the bulletproof pipeline, the first ultra low-cost mechanism to protect a microprocessor pipeline and on-chip memory system from silicon defects. to achieve this goal we combine area-frugal on-line testing techniques and system-level checkpointing to provide the same guarantees of reliability found in traditional solutions, but at much lower cost. our approach utilizes a microarchitectural checkpointing mechanism which creates coarse-grained epochs of execution, during which distributed on-line built in self-test (bist) mechanisms validate the integrity of the underlying hardware. in case a failure is detected, we rely on the natural redundancy of instructionlevel parallel processors to repair the system so that it can still operate in a degraded performance mode. using detailed circuit-level and architectural simulation, we find that our approach provides very high coverage of silicon defects (89%) with little area cost (5.8%). in addition, when a defect occurs, the subsequent degraded mode of operation was found to have only moderate performance impacts, (from 4% to 18% slowdown).
ctrigger: exposing atomicity violation bugs from their hiding places. multicore hardware is making concurrent programs pervasive. unfortunately, concurrent programs are prone to bugs. among different types of concurrency bugs, atomicity violation bugs are common and important. existing techniques to detect atomicity violation bugs suffer from one limitation: requiring bugs to manifest during monitored runs, which is an open problem in concurrent program testing. this paper makes two contributions. first, it studies the interleaving characteristics of the common practice in concurrent program testing (i.e., running a program over and over) to understand why atomicity violation bugs are hard to expose. second, it proposes ctrigger to effectively and efficiently expose atomicity violation bugs in large programs. ctrigger focuses on a special type of interleavings (i.e., unserializable interleavings) that are inherently correlated to atomicity violation bugs, and uses trace analysis to systematically identify (likely) feasible unserializable interleavings with low occurrence-probability. ctrigger then uses minimum execution perturbation to exercise low-probability interleavings and expose difficult-to-catch atomicity violation. we evaluate ctrigger with real-world atomicity violation bugs from four sever/desktop applications (apache, mysql, mozilla, and pbzip2) and three splash2 applications on 8-core machines. ctrigger efficiently exposes the tested bugs within 1--235 seconds, two to four orders of magnitude faster than stress testing. without ctrigger, some of these bugs do not manifest even after 7 full days of stress testing. in addition, without deterministic replay support, once a bug is exposed, ctrigger can help programmers reliably reproduce it for diagnosis. our tested bugs are reproduced by ctrigger mostly within 5 seconds, 300 to over 60000 times faster than stress testing.
a probabilistic pointer analysis for speculative optimizations. pointer analysis is a critical compiler analysis used to disambiguate the indirect memory references that result from the use of pointers and pointer-based data structures. a conventional pointer analysis deduces for every pair of pointers, at any program point, whether a points-to relation between them (i) definitely exists, (ii) definitely does not exist, or (iii) maybe exists. many compiler optimizations rely on accurate pointer analysis, and to ensure correctness cannot optimize in the maybe case. in contrast, recently-proposed speculative optimizations can aggressively exploit the maybe case, especially if the likelihood that two pointers alias can be quantified. this paper proposes a probabilistic pointer analysis (ppa) algorithm that statically predicts the probability of each points-to relation at every program point. building on simple control-flow edge profiling, our analysis is both one-level context and flow sensitive-yet can still scale to large programs including the spec 2000 integer benchmark suite. the key to our approach is to compute points-to probabilities through the use of linear transfer functions that are efficiently encoded as sparse matrices.we demonstrate that our analysis can provide accurate probabilities, even without edge-profile information. we also find that-even without considering probability information-our analysis provides an accurate approach to performing pointer analysis.
early experience with a commercial hardware transactional memory implementation. we report on our experience with the hardware transactional memory (htm) feature of two pre-production revisions of a new commercial multicore processor. our experience includes a number of promising results using htm to improve performance in a variety of contexts, and also identifies some ways in which the feature could be improved to make it even better. we give detailed accounts of our experiences, sharing techniques we used to achieve the results we have, as well as describing challenges we faced in doing so.
combinatorial sketching for finite programs. sketching is a software synthesis approach where the programmer develops a partial implementation - a sketch - and a separate specification of the desired functionality. the synthesizer then completes the sketch to behave like the specification. the correctness of the synthesized implementation is guaranteed by the compiler, which allows, among other benefits, rapid development of highly tuned implementations without the fear of introducing bugs.we develop sketch, a language for finite programs with linguistic support for sketching. finite programs include many highperformance kernels, including cryptocodes. in contrast to prior synthesizers, which had to be equipped with domain-specific rules, sketch completes sketches by means of a combinatorial search based on generalized boolean satisfiability. consequently, our combinatorial synthesizer is complete for the class of finite programs: it is guaranteed to complete any sketch in theory, and in practice has scaled to realistic programming problems.freed from domain rules, we can now write sketches as simpleto-understand partial programs, which are regular programs in which difficult code fragments are replaced with holes to be filled by the synthesizer. holes may stand for index expressions, lookup tables, or bitmasks, but the programmer can easily define new kinds of holes using a single versatile synthesis operator.we have used sketch to synthesize an efficient implementation of the aes cipher standard. the synthesizer produces the most complex part of the implementation and runs in about an hour.
isolator: dynamically ensuring isolation in comcurrent programs. in this paper, we focus on concurrent programs that use locks to achieve isolation of data accessed by critical sections of code. we present isolator, an algorithm that guarantees isolation for well-behaved threads of a program that obey a locking discipline even in the presence of ill-behaved threads that disobey the locking discipline. isolator uses code instrumentation, data replication, and virtual memory protection to detect isolation violations and delays ill-behaved threads to ensure isolation. our instrumentation scheme requires access only to the code of well-behaved threads. we have evaluated isolator on several benchmark programs and found that isolator can ensure isolation with reasonable runtime overheads. in addition, we present three general desiderata - safety, isolation, and permissiveness - for any scheme that attempts to ensure isolation, and formally prove that isolator satisfies all of these desiderata.
accelerator: using data parallelism to program gpus for general-purpose uses. gpus are difficult to program for general-purpose uses. programmers can either learn graphics apis and convert their applications to use graphics pipeline operations or they can use stream programming abstractions of gpus. we describe accelerator, a system that uses data parallelism to program gpus for general-purpose uses instead. programmers use a conventional imperative programming language and a library that provides only high-level data-parallel operations. no aspects of gpus are exposed to programmers. the library implementation compiles the data-parallel operations on the fly to optimized gpu pixel shader code and api calls.we describe the compilation techniques used to do this. we evaluate the effectiveness of using data parallelism to program gpus by providing results for a set of compute-intensive benchmarks. we compare the performance of accelerator versions of the benchmarks against hand-written pixel shaders. the speeds of the accelerator versions are typically within 50% of the speeds of hand-written pixel shader code. some benchmarks significantly outperform c versions on a cpu: they are up to 18 times faster than c code running on a cpu.
adaptive set pinning: managing shared caches in chip multiprocessors. as part of the trend towards chip multiprocessors (cmps) for the next leap in computing performance, many architectures have explored sharing the last level of cache among different processors for better performance-cost ratio and improved resource allocation. shared cache management is a crucial cmp design aspect for the performance of the system. this paper first presents a new classification of cache misses - cii: compulsory, inter-processor and intra-processor misses - for cmps with shared caches to provide a better understanding of the interactions between memory transactions of different processors at the level of shared cache in a cmp. we then propose a novel approach, called set pinning, for eliminating inter-processor misses and reducing intra-processor misses in a shared cache. furthermore, we show that an adaptive set pinning scheme improves over the benefits obtained by the set pinning scheme by significantly reducing the number of off-chip accesses. extensive analysis of these approaches with specomp 2001 benchmarks is performed using a full system simulator. our experiments indicate that the set pinning scheme achieves an average improvement of 22.18% in the l2 miss rate while the adaptive set pinning scheme reduces the miss rates by an average of 47.94% as compared to the traditional shared cache scheme. they also improve the performance by 7.24% and 17.88% respectively.
overshadow: a virtualization-based approach to retrofitting protection in commodity operating systems. commodity operating systems entrusted with securing sensitive data are remarkably large and complex, and consequently, frequently prone to compromise. to address this limitation, we introduce a virtual-machine-based system called overshadow that protects the privacy and integrity of application data, even in the event of a total oscompromise. overshadow presents an application with a normal view of its resources, but the os with an encrypted view. this allows the operating system to carry out the complex task of managing an application's resources, without allowing it to read or modify them. thus, overshadow offers a last line of defense for application data. overshadow builds on multi-shadowing, a novel mechanism that presents different views of "physical" memory, depending on the context performing the access. this primitive offers an additional dimension of protection beyond the hierarchical protection domains implemented by traditional operating systems and processor architectures. we present the design and implementation of overshadow and show how its new protection semantics can be integrated with existing systems. our design has been fully implemented and used to protect a wide range of unmodified legacy applications running on an unmodified linux operating system. we evaluate the performance of our implementation, demonstrating that this approach is practical.
efficiency trends and limits from comprehensive microarchitectural adaptivity. increasing demand for power-efficient, high-performance computing requires tuning applications and/or the underlying hardware to improve the mapping between workload heterogeneity and computational resources. to assess the potential benefits of hardware tuning, we propose a framework that leverages synergistic interactions between recent advances in (a) sampling, (b) predictive modeling, and (c) optimization heuristics. this framework enables qualitatively new capabilities in analyzing the performance and power characteristics of adaptive microarchitectures. for the first time, we are able to simultaneously consider high temporal and comprehensive spatial adaptivity. in particular, we optimize efficiency for many, short adaptive intervals and identify the best configuration of 15 parameters, which define a space of 240b point. with frequent sub-application reconfiguration and a fully reconfigurable hardware substrate, adaptive microarchitectures achieve bips3/w efficiency gains of up to 5.3x (median 2.4x) relative to their static counterparts already optimized for a given application. this 5.3x efficiency gain is derived from a 1.6x performance gain and 0.8x power reduction. although several applications achieve a significant fraction of their potential efficiency with as few as three adaptive parameters, the three most significant parameters differ across applications. these differences motivate a hardware substrate capable of comprehensive adaptivity to meet these diverse application requirements.
architectural support for swar text processing with parallel bit streams: the inductive doubling principle. parallel bit stream algorithms exploit the swar (simd within a register) capabilities of commodity processors in high-performance text processing applications such as utf-8 to utf-16 transcoding, xml parsing, string search and regular expression matching. direct architectural support for these algorithms in future swar instruction sets could further increase performance as well as simplifying the programming task. a set of simple swar instruction set extensions are proposed for this purpose based on the principle of systematic support for inductive doubling as an algorithmic technique. these extensions are shown to significantly reduce instruction count in core parallel bit stream algorithms, often providing a 3x or better improvement. the extensions are also shown to be useful for swar programming in other application areas, including providing a systematic treatment for horizontal operations. an implementation model for these extensions involves relatively simple circuitry added to the operand fetch components in a pipelined processor.
capo: a software-hardware interface for practical deterministic multiprocessor replay. while deterministic replay of parallel programs is a powerful technique, current proposals have shortcomings. specifically, software-based replay systems have high overheads on multiprocessors, while hardware-based proposals focus only on basic hardware-level mechanisms, ignoring the overall replay system. to be practical, hardware-based replay systems need to support an environment with multiple parallel jobs running concurrently -- some being recorded, others being replayed and even others running without recording or replay. moreover, they need to manage limited-size log buffers. this paper addresses these shortcomings by introducing, for the first time, a set of abstractions and a software-hardware interface for practical hardware-assisted replay of multiprocessor systems. the approach, called capo, introduces the novel abstraction of the replay sphere to separate the responsibilities of the hardware and software components of the replay system. in this paper, we also design and build capoone, a prototype of a deterministic multiprocessor replay system that implements capo using linux and simulated delorean hardware. our evaluation of 4-processor executions shows that capoone largely records with the efficiency of hardware-based schemes and the flexibility of software-based schemes.