waashk/dblp huggingface dataset:
stealth prefetching. prefetching in shared-memory multiprocessor systems is an increasingly difficult problem. as system designs grow to incorporate larger numbers of faster processors, memory latency and interconnect traffic increase. while aggressive prefetching techniques can mitigate the increasing memory latency, they can harm performance by wasting precious interconnect bandwidth and prematurely accessing shared data, causing state downgrades at remote nodes that force later upgrades.this paper investigates stealth prefetching, a new technique that utilizes information from coarse-grain coherence tracking (cgct) for prefetching data aggressively, stealthily, and efficiently in a broadcast-based shared-memory multiprocessor system. stealth prefetching utilizes cgct to identify regions of memory that are not shared by other processors, aggressively fetches these lines from dram in open-page mode, and moves them close to the processor in anticipation of future references. our analysis with commercial, scientific, and multiprogrammed workloads show that stealth prefetching provides an average speedup of 20% over an aggressive baseline system with conventional prefetching.
computation spreading: employing hardware migration to specialize cmp cores on-the-fly. in canonical parallel processing, the operating system (os) assigns a processing core to a single thread from a multithreaded server application. since different threads from the same application often carry out similar computation, albeit at different times, we observe extensive code reuse among different processors, causing redundancy (e.g., in our server workloads, 45-65% of all instruction blocks are accessed by all processors). moreover, largely independent fragments of computation compete for the same private resources causing destructive interference. together, this redundancy and interference lead to poor utilization of private microarchitecture resources such as caches and branch predictors.we present computation spreading (csp), which employs hardware migration to distribute a thread's dissimilar fragments of computation across the multiple processing cores of a chip multiprocessor (cmp), while grouping similar computation fragments from different threads together. this paper focuses on a specific example of csp for os intensive server applications: separating application level (user) computation from the os calls it makes.when performing csp, each core becomes temporally specialized to execute certain computation fragments, and the same core is repeatedly used for such fragments. we examine two specific thread assignment policies for csp, and show that these policies, across four server workloads, are able to reduce instruction misses in private l2 caches by 27-58%, private l2 load misses by 0-19%, and branch mispredictions by 9-25%.
heapmd: identifying heap-based bugs using anomaly detection. we present the design, implementation, and evaluation of heapmd, a dynamic analysis tool that finds heap-based bugs using anomaly detection. heapmd is based upon the observation that, in spite of the evolving nature of the heap, several of its properties remain stable. heapmd uses this observation in a novel way: periodically, during the execution of the program, it computes a suite of metrics which are sensitive to the state of the heap. these metrics track heap behavior, and the stability of the heap reflects quantitatively in the values of these metrics. the "normal" ranges of stable metrics, obtained by running a program on multiple inputs, are then treated as indicators of correct behaviour, and are used in conjunction with an anomaly detector to find heap-based bugs. using heapmd, we were able to find 40 heap-based bugs, 31 of them previously unknown, in 5 large, commercial applications.
kendo: efficient deterministic multithreading in software. although chip-multiprocessors have become the industry standard, developing parallel applications that target them remains a daunting task. non-determinism, inherent in threaded applications, causes significant challenges for parallel programmers by hindering their ability to create parallel applications with repeatable results. as a consequence, parallel applications are significantly harder to debug, test, and maintain than sequential programs. this paper introduces kendo: a new software-only system that provides deterministic multithreading of parallel applications. kendo enforces a deterministic interleaving of lock acquisitions and specially declared non-protected reads through a novel dynamically load-balanced deterministic scheduling algorithm. the algorithm tracks the progress of each thread using performance counters to construct a deterministic logical time that is used to compute an interleaving of shared data accesses that is both deterministic and provides good load balancing. kendo can run on today's commodity hardware while incurring only a modest performance cost. experimental results on the splash-2 applications yield a geometric mean overhead of only 16% when running on 4 processors. this low overhead makes it possible to benefit from kendo even after an application is deployed. programmers can start using kendo today to program parallel applications that are easier to develop, debug, and test.
unbounded page-based transactional memory. exploiting thread level parallelism is paramount in the multicore era. transactions enable programmers to expose such parallelism by greatly simplifying the multi-threaded programming model. virtualized transactions (unbounded in space and time) are desirable, as they can increase the scope of transactions' use, and thereby further simplify a programmer's job. however, hardware support is essential to support efficient execution of unbounded transactions. in this paper, we introduce page-based transactional memory to support unbounded transactions. we combine transaction bookkeeping with the virtual memory system to support fast transaction conflict detection, commit, abort, and to maintain transactions' speculative data.
anomaly-based bug prediction, isolation, and validation: an automated approach for software debugging. software defects, commonly known as bugs, present a serious challenge for system reliability and dependability. once a program failure is observed, the debugging activities to locate the defects are typically nontrivial and time consuming. in this paper, we propose a novel automated approach to pin-point the root-causes of software failures. our proposed approach consists of three steps. the first step is bug prediction, which leverages the existing work on anomaly-based bug detection as exceptional behavior during program execution has been shown to frequently point to the root cause of a software failure. the second step is bug isolation, which eliminates false-positive bug predictions by checking whether the dynamic forward slices of bug predictions lead to the observed program failure. the last step is bug validation, in which the isolated anomalies are validated by dynamically nullifying their effects and observing if the program still fails. the whole bug prediction, isolation and validation process is fully automated and can be implemented with efficient architectural support. our experiments with 6 programs and 7 bugs, including a real bug in the gcc 2.95.2 compiler, show that our approach is highly effective at isolating only the relevant anomalies. compared to state-of-art debugging techniques, our proposed approach pinpoints the defect locations more accurately and presents the user with a much smaller code set to analyze.
tradeoffs in transactional memory virtualization. for transactional memory (tm) to achieve widespread acceptance, transactions should not be limited to the physical resources of any specific hardware implementation. tm systems should guarantee correct execution even when transactions exceed scheduling quanta, overflow the capacity of hardware caches and physical memory, or include more independent nesting levels than what is supported in hardware. existing proposals for tm virtualization are either incomplete or rely on complex hardware implementations, which are an overkill if virtualization is invoked infrequently in the common case.we present extended transactional memory (xtm), the first tm virtualization system that virtualizes all aspects of transactional execution (time, space, and nesting depth). xtm is implemented in software using virtual memory support. it operates at page granularity, using private copies of overflowed pages to buffer memory updates until the transaction commits and snapshots of pages to detect interference between transactions. we also describe two enhancements to xtm that use limited hardware support to address key performance bottlenecks.we compare xtm to hardwarebased virtualization using both real applications and synthetic microbenchmarks. we show that despite being software-based, xtm and its enhancements are competitive with hardware-based alternatives. overall, we demonstrate that xtm provides a complete, flexible, and low-cost mechanism for practical tm virtualization.
efficient online validation with delta execution. software systems are constantly changing. patches to fix bugs and patches to add features are all too common. every change risks breaking a previously working system. hence administrators loathe change, and are willing to delay even critical security patches until after fully validating their correctness. compared to off-line validation, on-line validation has clear advantages since it tests against real life workloads. yet unfortunately it imposes restrictive overheads as it requires running the old and new versions side-by-side. moreover, due to spurious differences (e.g. event timing, random number generation, and thread interleavings), it is difficult to compare the two for validation. to allow more effective on-line patch validation, we propose a new mechanism, called delta execution, that is based on the observation that most patches are small. delta execution merges the two side-by-side executions for most of the time and splits only when necessary, such as when they access different data or execute different code. this allows us to perform on-line validation not only with lower overhead but also with greatly reduced spurious differences, allowing us to effectively validate changes. we first validate the feasibility of our idea by studying the characteristics of 240 patches from 4 server programs; our examination shows that 77% of the changes should not be expected to cause large changes and are thereby feasible for delta execution. we then implemented delta execution using dynamic instrumentation. using real world patches from 7 server applications and 3 other programs, we compared our implementation of delta execution against a traditional side-by-side on-line validation. delta execution outperformed traditional validation by up to 128%; further, for 3 of the changes, spurious differences caused the traditional validation to fail completely while delta execution succeeded. this demonstrates that delta execution can allow administrators to use on-line validation to confidently ensure the correctness of the changes they apply.
a spatial path scheduling algorithm for edge architectures. growing on-chip wire delays are motivating architectural features that expose on-chip communication to the compiler. edge architectures are one example of communication-exposed microarchitectures in which the compiler forms dataflow graphs that specify how the microarchitecture maps instructions onto a distributed execution substrate. this paper describes a compiler scheduling algorithm called spatial path scheduling that factors in previously fixed locations - called anchor points - for each placement. this algorithm extends easily to different spatial topologies. we augment this basic algorithm with three heuristics: (1) local and global alu and network link contention modeling, (2) global critical path estimates, and (3) dependence chain path reservation. we use simulated annealing to explore possible performance improvements and to motivate the augmented heuristics and their weighting functions. we show that the spatial path scheduling algorithm augmented with these three heuristics achieves a 21% average performance improvement over the best prior algorithm and comes within an average of 5% of the annealed performance for our benchmarks.
dispersing proprietary applications as benchmarks through code mutation. industry vendors hesitate to disseminate proprietary applications to academia and third party vendors. by consequence, the benchmarking process is typically driven by standardized, open-source benchmarks which may be very different from and likely not representative of the real-life applications of interest. this paper proposes code mutation, a novel technique that mutates a proprietary application to complicate reverse engineering so that it can be distributed as a benchmark. the benchmark mutant then serves as a proxy for the proprietary application. the key idea in the proposed code mutation approach is to preserve the proprietary application's dynamic memory access and/or control flow behavior in the benchmark mutant while mutating the rest of the application code. to this end, we compute program slices for memory access operations and/or control flow operationstrimmed through constant value and branch profiles; and subsequently mutate the instructions not appearing in these slices through binary rewriting. our experimental results using spec cpu2000 and mibench benchmarks show that code mutation is a promising technique that mutates up to 90% of the static binary, up to 50% of the dynamically executed instructions, and up to 35% of the at run time exposed inter-operation data dependencies. the performance characteristics of the mutant are very similar to those of the proprietary application across a wide range of microarchitectures and hardware implementations.
no "power" struggles: coordinated multi-level power management for the data center. power delivery, electricity consumption, and heat management are becoming key challenges in data center environments. several past solutions have individually evaluated different techniques to address separate aspects of this problem, in hardware and software, and at local and global levels. unfortunately, there has been no corresponding work on coordinating all these solutions. in the absence of such coordination, these solutions are likely to interfere with one another, in unpredictable (and potentially dangerous) ways. this paper seeks to address this problem. we make two key contributions. first, we propose and validate a power management solution that coordinates different individual approaches. using simulations based on 180 server traces from nine different real-world enterprises, we demonstrate the correctness, stability, and efficiency advantages of our solution. second, using our unified architecture as the base, we perform a detailed quantitative sensitivity analysis and draw conclusions about the impact of different architectures, implementations, workloads, and system design choices.
hardware counter driven on-the-fly request signatures. today's processors provide a rich source of statistical informationon application execution through hardware counters. in this paper, we explore the utilization of these statistics as request signaturesin server applications for identifying requests and inferring high-level request properties (e.g., cpu and i/o resource needs). our key finding is that effective request signatures may be constructed using a small amount of hardware statistics while the request is still in an early stage of its execution. such on-the-fly request identification and property inference allow guided operating system adaptation at request granularity (e.g., resource-aware request scheduling and on-the-fly request classification). we address the challenges of selecting hardware counter metrics for signature construction and providing necessary operating system support for per-request statistics management. our implementation in the linux 2.6.10 kernel suggests that our approach requires low overhead suitable for runtime deployment. our on-the-fly request resource consumption inference (averaging 7%, 3%, 20%, and 41% prediction errors for four server workloads, tpc-c, tpc-h, j2ee-based rubis, and a trace-driven index search, respectively) is much more accurate than the online running-average based prediction (73-82% errors). its use for resource-aware request scheduling results in a 15-70% response time reduction for three cpu-bound applications. its use for on-the-fly request classification and anomaly detection exhibits high accuracy for the tpc-h workload with synthetically generated anomalous requests following a typical sql-injection attack pattern.
hybrid transactional memory. transactional memory (tm) promises to substantially reduce the difficulty of writing correct, efficient, and scalable concurrent programs. but "bounded" and "best-effort" hardware tm proposals impose unreasonable constraints on programmers, while more flexible software tm implementations are considered too slow. proposals for supporting "unbounded" transactions in hardware entail significantly higher complexity and risk than best-effort designs.we introduce hybrid transactional memory (hytm), an approach to implementing tmin software so that it can use best effort hardware tm (htm) to boost performance but does not depend on htm. thus programmers can develop and test transactional programs in existing systems today, and can enjoy the performance benefits of htm support when it becomes available.we describe our prototype hytm system, comprising a compiler and a library. the compiler allows a transaction to be attempted using best-effort htm, and retried using the software library if it fails. we have used our prototype to "transactify" part of the berkeley db system, as well as several benchmarks. by disabling the optional use of htm, we can run all of these tests on existing systems. furthermore, by using a simulated multiprocessor with htm support, we demonstrate the viability of the hytm approach: it can provide performance and scalability approaching that of an unbounded htm implementation, without the need to support all transactions with complicated htm support.
maximum benefit from a minimal htm. a minimal, bounded hardware transactional memory implementation significantly improves synchronization performance when used in an operating system kernel. we add htm to linux 2.4, a kernel with a simple, coarse-grained synchronization structure. the transactional linux 2.4 kernel can improve performance of user programs by as much as 40% over the non-transactional 2.4 kernel. it closes 68% of the performance gap with the linux 2.6 kernel, which has had significant engineering effort applied to improve scalability. we then extend our minimal htm to a fast, unbounded transactional memory with a novel technique for coordinating hardware transactions and software synchronization. overflowed transactions run in software, with only a minimal coupling between hardware and software systems. there is no performance penalty for overflow rates of less than 1%. in one instance, at 16 processors and an overflow rate of 4%, performance degrades from an ideal 4.3x to 3.6x.
a performance counter architecture for computing accurate cpi components. a common way of representing processor performance is to use cycles per instruction (cpi) `stacks' which break performance into a baseline cpi plus a number of individual miss event cpi components. cpi stacks can be very helpful in gaining insight into the behavior of an application on a given microprocessor; consequently, they are widely used by software application developers and computer architects. however, computing cpi stacks on superscalar out-of-order processors is challenging because of various overlaps among execution and miss events (cache misses, tlb misses, and branch mispredictions).this paper shows that meaningful and accurate cpi stacks can be computed for superscalar out-of-order processors. using interval analysis, a novel method for analyzing out-of-order processor performance, we gain understanding into the performance impact of the various miss events. based on this understanding, we propose a novel way of architecting hardware performance counters for building accurate cpi stacks. the additional hardware for implementing these counters is limited and comparable to existing hardware performance counter architectures while being significantly more accurate than previous approaches.
twindrivers: semi-automatic derivation of fast and safe hypervisor network drivers from guest os drivers. in a virtualized environment, device drivers are often run inside a virtual machine (vm) rather than in the hypervisor, for reasons of safety and reduction in software engineering effort. unfortunately, this approach results in poor performance for i/o-intensive devices such as network cards. the alternative approach of running device drivers directly in the hypervisor yields better performance, but results in the loss of safety guarantees for the hypervisor and incurs additional software engineering costs. in this paper we present twindrivers, a framework which allows us to semi-automatically create safe and efficient hypervisor drivers from guest os drivers. the hypervisor driver runs directly in the hypervisor, but its data resides completely in the driver vm address space. a software virtual memory mechanism allows the driver to access its vm data efficiently from the hypervisor running in any guest context, and also protects the hypervisor from invalid memory accesses from the driver. an upcall mechanism allows the hypervisor to largely reuse the driver support infrastructure present in the vm. the twindriver system thus combines most of the performance benefits of hypervisor-based driver approaches with the safety and software engineering benefits of vm-based driver approaches. using the twindrivers hypervisor driver, we are able to improve the guest domain networking throughput in xen by a factor of 2.4 for transmit workloads, and 2.1 for receive workloads, both in cpu-scaled units, and achieve close to 64-67 of native linux throughput.
exploiting coarse-grained task, data, and pipeline parallelism in stream programs. as multicore architectures enter the mainstream, there is a pressing demand for high-level programming models that can effectively map to them. stream programming offers an attractive way to expose coarse-grained parallelism, as streaming applications (image, video, dsp, etc.) are naturally represented by independent filters that communicate over explicit data channels.in this paper, we demonstrate an end-to-end stream compiler that attains robust multicore performance in the face of varying application characteristics. as benchmarks exhibit different amounts of task, data, and pipeline parallelism, we exploit all types of parallelism in a unified manner in order to achieve this generality. our compiler, which maps from the streamit language to the 16-core raw architecture, attains a 11.2x mean speedup over a single-core baseline, and a 1.84x speedup over our previous work.