waashk/dblp huggingface dataset:
leak pruning. managed languages improve programmer productivity with type safety and garbage collection, which eliminate memory errors such as dangling pointers, double frees, and buffer overflows. however, because garbage collection uses reachability to over-approximate live objects, programs may still leak memory if programmers forget to eliminate the last reference to an object that will not be used again. leaks slow programs by increasing collector workload and frequency. growing leaks eventually crash programs. this paper introduces leak pruning, which keeps programs running by predicting and reclaiming leaked objects at run time. it predicts dead objects and reclaims them based on observing data structure usage patterns. leak pruning preserves semantics because it waits for heap exhaustion before reclaiming objects and poisons references to objects it reclaims. if the program later tries to access a poisoned reference, the virtual machine (vm) throws an error. we show leak pruning has low overhead in a java vm and evaluate it on 10 leaking programs. leak pruning does not help two programs, executes five substantial programs 1.6-81x longer, and executes three programs, including a leak in eclipse, for at least 24 hours. in the worst case, leak pruning defers fatal errors. in the best case, it keeps leaky programs running with preserved semantics and consistent throughput.
gordon: using flash memory to build fast, power-efficient clusters for data-intensive applications. as our society becomes more information-driven, we have begun to amass data at an astounding and accelerating rate. at the same time, power concerns have made it difficult to bring the necessary processing power to bear on querying, processing, and understanding this data. we describe gordon, a system architecture for data-centric applications that combines low-power processors, flash memory, and data-centric programming systems to improve performance for data-centric applications while reducing power consumption. the paper presents an exhaustive analysis of the design space of gordon systems, focusing on the trade-offs between power, energy, and performance that gordon must make. it analyzes the impact of flash-storage and the gordon architecture on the performance and power efficiency of data-centric applications. it also describes a novel flash translation layer tailored to data intensive workloads and large flash storage arrays. our data show that, using technologies available in the near future, gordon systems can out-perform disk-based clusters by 1.5× and deliver up to 2.5× more performance per watt.
efficiently exploring architectural design spaces via predictive modeling. architects use cycle-by-cycle simulation to evaluate design choices and understand tradeoffs and interactions among design parameters. efficiently exploring exponential-size design spaces with many interacting parameters remains an open problem: the sheer number of experiments renders detailed simulation intractable. we attack this problem via an automated approach that builds accurate, confident predictive design-space models. we simulate sampled points, using the results to teach our models the function describing relationships among design parameters. the models produce highly accurate performance estimates for other points in the space, can be queried to predict performance impacts of architectural changes, and are very fast compared to simulation, enabling efficient discovery of tradeoffs among parameters in different regions. we validate our approach via sensitivity studies on memory hierarchy and cpu design spaces: our models generally predict ipc with only 1-2% error and reduce required simulation by two orders of magnitude. we also show the efficacy of our technique for exploring chip multiprocessor (cmp) design spaces: when trained on a 1% sample drawn from a cmp design space with 250k points and up to 55x performance swings among different system configurations, our models predict performance with only 4-5% error on average. our approach combines with techniques to reduce time per simulation, achieving net time savings of three-four orders of magnitude.
complete information flow tracking from the gates up. for many mission-critical tasks, tight guarantees on the flow of information are desirable, for example, when handling important cryptographic keys or sensitive financial data. we present a novel architecture capable of tracking all information flow within the machine, including all explicit data transfers and all implicit flows (those subtly devious flows caused by not performing conditional operations). while the problem is impossible to solve in the general case, we have created a machine that avoids the general-purpose programmability that leads to this impossibility result, yet is still programmable enough to handle a variety of critical operations such as public-key encryption and authentication. through the application of our novel gate-level information flow tracking method, we show how all flows of information can be precisely tracked. from this foundation, we then describe how a class of architectures can be constructed, from the gates up, to completely capture all information flows and we measure the impact of doing so on the hardware implementation, the isa, and the programmer.
geiger: monitoring the buffer cache in a virtual machine environment. virtualization is increasingly being used to address server management and administration issues like flexible resource allocation, service isolation and workload migration. in a virtualized environment, the virtual machine monitor (vmm) is the primary resource manager and is an attractive target for implementing system features like scheduling, caching, and monitoring. however, the lackof runtime information within the vmm about guest operating systems, sometimes called the semantic gap, is a significant obstacle to efficiently implementing some kinds of services.in this paper we explore techniques that can be used by a vmm to passively infer useful information about a guest operating system's unified buffer cache and virtual memory system. we have created a prototype implementation of these techniques inside the xen vmm called geiger and show that it can accurately infer when pages are inserted into and evicted from a system's buffer cache. we explore several nuances involved in passively implementing eviction detection that have not previously been addressed, such as the importance of tracking disk block liveness, the effect of file system journaling, and the importance of accounting for the unified caches found in modern operating systems.using case studies we show that the information provided by geiger enables a vmm to implement useful vmm-level services. we implement a novel working set size estimator which allows the vmm to make more informed memory allocation decisions. we also show that a vmm can be used to drastically improve the hit rate in remote storage caches by using eviction-based cache placement without modifying the application or operating system storage interface. both case studies hint at a future where inference techniques enable a broad new class of vmm-level functionality.
dmp: deterministic shared memory multiprocessing. current shared memory multicore and multiprocessor systems are nondeterministic. each time these systems execute a multithreaded application, even if supplied with the same input, they can produce a different output. this frustrates debugging and limits the ability to properly test multithreaded code, becoming a major stumbling block to the much-needed widespread adoption of parallel programming. in this paper we make the case for fully deterministic shared memory multiprocessing (dmp). the behavior of an arbitrary multithreaded program on a dmp system is only a function of its inputs. the core idea is to make inter-thread communication fully deterministic. previous approaches to coping with nondeterminism in multithreaded programs have focused on replay, a technique useful only for debugging. in contrast, while dmp systems are directly useful for debugging by offering repeatability by default, we argue that parallel programs should execute deterministically in the field as well. this has the potential to make testing more assuring and increase the reliability of deployed multithreaded software. we propose a range of approaches to enforcing determinism and discuss their implementation trade-offs. we show that determinism can be provided with little performance cost using our architecture proposals on future hardware, and that software-only approaches can be utilized on existing systems.
a new idiom recognition framework for exploiting hardware-assist instructions. modern processors support hardware-assist instructions (such as trt and trot instructions on ibm zseries) to accelerate certain functions such as delimiter search and character conversion. such special instructions have often been used in high performance libraries, but they have not been exploited well in optimizing compilers except for some limited cases. we propose a new idiom recognition technique derived from a topological embedding algorithm [4] to detect idiom patterns in the input program more aggressively than in previous approaches. our approach can detect a pattern even if the code segment does not exactly match the idiom. for example, we can detect a code segment that includes additional code within the idiom pattern. we implemented our new idiom recognition approach based on the java just-in-time (jit) compiler that is part of the j9 java virtual machine, and we supported several important idioms for special hardware-assist instructions on the ibm zseries and on some models of the ibm pseries. to demonstrate the effectiveness of our technique, we performed two experiments. the first one is to see how many more patterns we can detect compared to the previous approach. the second one is to see how much performance improvement we can achieve over the previous approach. for the first experiment, we used the java compatibility kit (jck) api tests. for the second one we used ibm xml parser, specjvm98, and spcjbb2000. in summary, relative to a baseline implementation using exact pattern matching, our algorithm converted 75% more loops in jck tests. we also observed significant performance improvement of the xml parser by 64%, of specjvm98 by 1%, and of specjbb2000 by 2% on average on a z990. finally, we observed the jit compilation time increases by only 0.32% to 0.44%.
adapting to intermittent faults in multicore systems. future multicore processors will be more susceptible to a variety of hardware failures. in particular, intermittent faults, caused in part by manufacturing, thermal, and voltage variations, can cause bursts of frequent faults that last from several cycles to several seconds or more. due to practical limitations of circuit techniques, cost-effective reliability will likely require the ability to temporarily suspend execution on a core during periods of intermittent faults. we investigate three of the most obvious techniques for adapting to the dynamically changing resource availability caused by intermittent faults, and demonstrate their different system-level implications. we show that system software reconfiguration has very high overhead, that temporarily pausing execution on a faulty core can lead to cascading livelock, and that using spare cores has high fault-free cost. to remedy these and other drawbacks of the three baseline techniques, we propose using a thin hardware/firmware layer to manage an overcommitted system -- one where the os is configured to use more virtual processors than the number of currently available physical cores. we show that this proposed technique can gracefully degrade performance during intermittent faults of various duration with low overhead, without involving system software, and without requiring spare cores.
predictor virtualization. many hardware optimizations rely on collecting information about program behavior at runtime. this information is stored in lookup tables. to be accurate and effective, these optimizations usually require large dedicated on-chip tables. although technology advances offer an increased amount of on-chip resources, these resources are allocated to increase the size of on-chip conventional cache hierarchies. this work proposes predictor virtualization, a technique that uses the existing memory hierarchy to emulate large predictor tables. we demonstrate the benefits of this technique by virtualizing a state-of-the-art data prefetcher. full-system, cycle-accurate simulations demonstrate that the virtualized prefetcher preserves the performance benefits of the original design, while reducing the on-chip storage dedicated to the predictor table from 60kb down to less than one kilobyte.
merge: a programming model for heterogeneous multi-core systems. in this paper we propose the merge framework, a general purpose programming model for heterogeneous multi-core systems. the merge framework replaces current ad hoc approaches to parallel programming on heterogeneous platforms with a rigorous, library-based methodology that can automatically distribute computation across heterogeneous cores to achieve increased energy and performance efficiency. the merge framework provides (1) a predicate dispatch-based library system for managing and invoking function variants for multiple architectures; (2) a high-level, library-oriented parallel language based on map-reduce; and (3) a compiler and runtime which implement the map-reduce language pattern by dynamically selecting the best available function implementations for a given input and machine configuration. using a generic sequencer architecture interface for heterogeneous accelerators, the merge framework can integrate function variants for specialized accelerators, offering the potential for to-the-metal performance for a wide range of heterogeneous architectures, all transparent to the user. the merge framework has been prototyped on a heterogeneous platform consisting of an intel core 2 duo cpu and an 8-core 32-thread intel graphics and media accelerator x3000, and a homogeneous 32-way unisys smp system with intel xeon processors. we implemented a set of benchmarks using the merge framework and enhanced the library with x3000 specific implementations, achieving speedups of 3.6x -- 8.5x using the x3000 and 5.2x -- 22x using the 32-way system relative to the straight c reference implementation on a single ia32 core.
accurate and efficient regression modeling for microarchitectural performance and power prediction. we propose regression modeling as an efficient approach for accurately predicting performance and power for various applications executing on any microprocessor configuration in a large microarchitectural design space. this paper addresses fundamental challenges in microarchitectural simulation cost by reducing the number of required simulations and using simulated results more effectively via statistical modeling and inference.specifically, we derive and validate regression models for performance and power. such models enable computationally efficient statistical inference, requiring the simulation of only 1 in 5 million points of a joint microarchitecture-application design space while achieving median error rates as low as 4.1 percent for performance and 4.3 percent for power. although both models achieve similar accuracy, the sources of accuracy are strikingly different. we present optimizations for a baseline regression model to obtain (1) application-specific models to maximize accuracy in performance prediction and (2) regional power models leveraging only the most relevant samples from the microarchitectural design space to maximize accuracy in power prediction. assessing sensitivity to the number of samples simulated for model formulation, we find fewer than 4,000 samples from a design space of approximately 22 billion points are sufficient. collectively, our results suggest significant potential in accurate and efficient statistical inference for microarchitectural design space exploration via regression models.
rapidmrc: approximating l2 miss rate curves on commodity systems for online optimizations. miss rate curves (mrcs) are useful in a number of contexts. in our research, online l2 cache mrcs enable us to dynamically identify optimal cache sizes when cache-partitioning a shared-cache multicore processor. obtaining l2 mrcs has generally been assumed to be expensive when done in software and consequently, their usage for online optimizations has been limited. to address these problems and opportunities, we have developed a low-overhead software technique to obtain l2 mrcs online on current processors, exploiting features available in their performance monitoring units so that no changes to the application source code or binaries are required. our technique, called rapidmrc, requires a single probing period of roughly 221 million processor cycles (147 ms), and subsequently 124 million cycles (83 ms) to process the data. we demonstrate its accuracy by comparing the obtained mrcs to the actual l2 mrcs of 30 applications taken from speccpu2006, speccpu2000, and specjbb2000. we show that rapidmrc can be applied to sizing cache partitions, helping to achieve performance improvements of up to 27%.
mapping esterel onto a multi-threaded embedded processor. the synchronous language esterel is well-suited for programming control-dominated reactive systems at the system level. it provides non-traditional control structures, in particular concurrency and various forms of preemption, which allow to concisely express reactive behavior. as these control structures cannot be mapped easily onto traditional, sequential processors, an alternative approach that has emerged recently makes use of special-purpose reactive processors. however, the designs proposed so far have limitations regarding completeness of the language support, and did not really take advantage of compile-time knowledge to optimize resource usage.this paper presents a reactive processor, the kiel esterel processor 3a (kep3a), and its compiler. the kep3a improves on earlier designs in several areas; most notable are the support for exception handling and the provision of context-dependent preemption handling instructions. the kep3a compiler presented here is to our knowledge the first for multi-threaded reactive processors. the translation of esterel's preemption constructs onto kep3a assembler is straightforward; however, a challenge is the correct and efficient representation of esterel's concurrency. the compiler generates code that respects data and control dependencies using the kep3a priority-based scheduling mechanism. we present a priority assignment approach that makes use of a novel concurrent control flow graph and has a complexity that in practice tends to be linear in the size of the program. unlike earlier esterel compilation schemes, this approach avoids unnecessary context switches by considering each thread's actual execution state at run time. furthermore, it avoids code replication present in other approaches.
powernap: eliminating server idle power. data center power consumption is growing to unprecedented levels: the epa estimates u.s. data centers will consume 100 billion kilowatt hours annually by 2011. much of this energy is wasted in idle systems: in typical deployments, server utilization is below 30%, but idle servers still consume 60% of their peak power draw. typical idle periods though frequent--last seconds or less, confounding simple energy-conservation approaches. in this paper, we propose powernap, an energy-conservation approach where the entire system transitions rapidly between a high-performance active state and a near-zero-power idle state in response to instantaneous load. rather than requiring fine-grained power-performance states and complex load-proportional operation from each system component, powernap instead calls for minimizing idle power and transition time, which are simpler optimization goals. based on the powernap concept, we develop requirements and outline mechanisms to eliminate idle power waste in enterprise blade servers. because powernap operates in low-efficiency regions of current blade center power supplies, we introduce the redundant array for inexpensive load sharing (rails), a power provisioning approach that provides high conversion efficiency across the entire range of powernap's power demands. using utilization traces collected from enterprise-scale commercial deployments, we demonstrate that, together, powernap and rails reduce average server power consumption by 74%.
avio: detecting atomicity violations via access interleaving invariants. this article proposes an innovative concurrent-program invariant that captures programmers' atomicity assumptions. it describes a tool with two implementations, one in software and the other using hardware support, that can automatically extract such invariants and detect atomicity bugs.
dftl: a flash translation layer employing demand-based selective caching of page-level address mappings. recent technological advances in the development of flash-memory based devices have consolidated their leadership position as the preferred storage media in the embedded systems market and opened new vistas for deployment in enterprise-scale storage systems. unlike hard disks, flash devices are free from any mechanical moving parts, have no seek or rotational delays and consume lower power. however, the internal idiosyncrasies of flash technology make its performance highly dependent on workload characteristics. the poor performance of random writes has been a cause of major concern, which needs to be addressed to better utilize the potential of flash in enterprise-scale environments. we examine one of the important causes of this poor performance: the design of the flash translation layer (ftl), which performs the virtual-to-physical address translations and hides the erase-before-write characteristics of flash. we propose a complete paradigm shift in the design of the core ftl engine from the existing techniques with our demand-based flash translation layer (dftl), which selectively caches page-level address mappings. we develop a flash simulation framework called flashsim. our experimental evaluation with realistic enterprise-scale workloads endorses the utility of dftl in enterprise-scale storage systems by demonstrating: (i) improved performance, (ii) reduced garbage collection overhead and (iii) better overload behavior compared to state-of-the-art ftl schemes. for example, a predominantly random-write dominant i/o trace from an oltp application running at a large financial institution shows a 78% improvement in average response time (due to a 3-fold reduction in operations of the garbage collector), compared to a state-of-the-art ftl scheme. even for the well-known read-dominant tpc-h benchmark, for which dftl introduces additional overheads, we improve system response time by 56%.
instruction scheduling for a tiled dataflow architecture. this paper explores hierarchical instruction scheduling for a tiled processor. our results show that at the top level of the hierarchy, a simple profile-driven algorithm effectively minimizes operand latency. after this schedule has been partitioned into large sections, the bottom-level algorithm must more carefully analyze program structure when producing the final schedule.our analysis reveals that at this bottom level, good scheduling depends upon carefully balancing instruction contention for processing elements and operand latency between producer and consumer instructions. we develop a parameterizable instruction scheduler that more effectively optimizes this trade-off. we use this scheduler to determine the contention-latency sweet spot that generates the best instruction schedule for each application. to avoid this application-specific tuning, we also determine the parameters that produce the best performance across all applications. the result is a contention-latency setting that generates instruction schedules for all applications in our workload that come within 17% of the best schedule for each.