waashk/dblp huggingface dataset:
temporally silent stores. recent work has shown that silent stores--stores which write a value matching the one already stored at the memory location--occur quite frequently and can be exploited to reduce memory traffic and improve performance. this paper extends the definition of silent stores to encompass sets of stores that change the value stored at a memory location, but only temporarily, and subsequently return a previous value of interest to the memory location. the stores that cause the value to revert are called temporally silent stores. we redefine multiprocessor sharing to account for temporal silence and show that in the limit, up to 45% of communication misses in scientific and commercial applications can be eliminated by exploiting values that change only temporarily. we describe a practical mechanism that detects temporally silent stores and removes the coherence traffic they cause in conventional multiprocessors. we find that up to 42% of communication misses can be eliminated with a simple extension to the mesi protocol. further, we examine application and operating system code to provide insight into the temporal silence phenomenon and characterize temporal silence by examining value frequencies and dynamic instruction distances between temporally silent pairs. these studies indicate that the operating system is involved heavily in temporal silence, in both commercial and scientific workloads, and that while detectable synchronization primitives provide substantial contributions, significant opportunity exists outside these references.
parallel computers for graphics applications. specialized computer architectures can provide better price/performance for executing image processing and graphics applications than general purpose designs. two processors are presented that use parallel simd data paths to support common graphics data structures as primitive operands in arithmetic expressions. a variant of the c language has been implemented to allow high level language coding of user applications on these processors. high level programming support is designed into the processor architecture that implements parallel object data typing and parallel conditional evaluation in hardware.
efficient superscalar performance through boosting. the foremost goal of superscalar processor design is to increase performance through the exploitation of instruction-level parallelism (ilp). previous studies have shown that speculative execution is required for high instruction per cycle (ipc) rates in non-numerical applications. the general trend has been toward supporting speculative execution in complicated, dynamically-scheduled processors. performance, though, is more than just a high ipc rate; it also depends upon instruction count and cycle time. boosting is an architectural technique that supports general speculative execution in simpler, statically-scheduled processors. boosting labels speculative instructions with their control dependence information. this labelling eliminates control dependence constraints on instruction scheduling while still providng full dependence information to the hardware. we have incorporated boosting into a trace-based, global scheduling algorithm that exploits ilp without adversely affecting the instruction count of a program. we use this algorithm and estimates of the boosting hardware involved to evaluate how much speculative execution support is really necessary to achieve good performance. we find that a statically-scheduled superscalar processor using a minimal implementation of boosting can easily reach the performance of a much more complex dynamically-scheduled superscalar processor.
limits on multiple instruction issue. this paper investigates the limitations on designing a processor which can sustain an execution rate of greater than one instruction per cycle on highly-optimized, non-scientific applications. we have used trace-driven simulations to determine that these applications contain enough instruction independence to sustain an instruction rate of about two instructions per cycle. in a straightforward implementation, cost considerations argue strongly against decoding more than two instructions in one cycle. given this constraint, the efficiency in instruction fetching rather than the complexity of the execution hardware limits the concurrency attainable at the instruction level.
understanding and improving operating system effects in control flow prediction. many modern applications result in a significant operating system (os) component. the os component has several implications including affecting the control flow transfer in the execution environment. this paper focuses on understanding the operating system effects on control flow transfer and prediction, and designing architectural support to alleviate the bottlenecks. we characterize the control flow transfer of several emerging applications on a commercial operating system. we find that the exception-driven, intermittent invocation of os code and the user/os branch history interference increase the misprediction in both user and kernel code.we propose two simple os-aware control flow prediction techniques to alleviate the destructive impact of user/os branch interference. the first one consists of capturing separate branch correlation information for user and kernel code. the second one involves using separate branch prediction tables for user and kernel code. we study the improvement contributed by the os-aware prediction to various branch predictors ranging from simple gshare to more elegant agree, multi-hybrid and bi-mode predictors. on 32k entries predictors, incorporating os-aware techniques yields up to 34%, 23%, 27% and 9% prediction accuracy improvement in gshare, multi-hybrid, agree and bi-mode predictors, resulting in up to 8% execution speedup.
fingerprinting: bounding soft-error detection latency and bandwidth. fingerprinting summarizes the history of internal processor state updates into a cryptographic signature. the processors in a dual modular redundant pair periodically exchange and compare fingerprints to corroborate each other's correctness. relative to other techniques, fingerprinting offers superior error coverage and significantly reduces the error-detection latency and bandwidth.
performance directed energy management for main memory and disks. much research has been conducted on energy management for memory and disks. most studies use control algorithms that dynamically transition devices to low power modes after they are idle for a certain threshold period of time. the control algorithms used in the past have two major limitations. first, they require painstaking, application-dependent manual tuning of their thresholds to achieve energy savings without significantly degrading performance. second, they do not provide performance guarantees. in one case, they slowed down an application by 835.this paper addresses these two limitations for both memory and disks, making memory/disk energy-saving schemes practical enough to use in real systems. specifically, we make three contributions: (1) we propose a technique that provides a performance guarantee for control algorithms. we show that our method works well for all tested cases, even with previously proposed algorithms that are not performance-aware. (2) we propose a new control algorithm, performance-directed dynamic (pd), that dynamically adjusts its thresholds periodically, based on available slack and recent workload characteristics. for memory, pd consumes the least energy, when compared to previous hand-tuned algorithms combined with a performance guarantee. however, for disks, pd is too complex and its self-tuning is unable to beat previous hand-tuned algorithms. (3) to improve on pd, we propose a simple, optimization-based, threshold-free control algorithm, performance-directed static (ps). ps periodically assigns a static configuration by solving an optimization problem that incorporates information about the available slack and recent traffic variability to different chips/disks. we find that ps is the best or close to the best across all performanceguaranteed disk algorithms, including hand-tuned versions.
symbiotic jobscheduling for a simultaneous multithreading processor. simultaneous multithreading machines fetch and execute instructions from multiple instruction streams to increase system utilization and speedup the execution of jobs. when there are more jobs in the system than there is hardware to support simultaneous execution, the operating system scheduler must choose the set of jobs to coschedulethis paper demonstrates that performance on a hardware multithreaded processor is sensitive to the set of jobs that are coscheduled by the operating system jobscheduler. thus, the full benefits of smt hardware can only be achieved if the scheduler is aware of thread interactions. here, a mechanism is presented that allows the scheduler to significantly raise the performance of smt architectures. this is done without any advance knowledge of a workload's characteristics, using sampling to identify jobs which run well together.we demonstrate an smt jobscheduler called sos. sos combines an overhead-free sample phase which collects information about various possible schedules, and a symbiosis phase which uses that information to predict which schedule will provide the best performance. we show that a small sample of the possible schedules is sufficient to identify a good schedule quickly. on a system with random job arrivals and departures, response time is improved as much as 17% over a schedule which does not incorporate symbiosis.
architectural support for copy and tamper resistant software. although there have been attempts to develop code transformations that yield tamper-resistant software, no reliable software-only methods are known. this paper studies the hardware implementation of a form of execute-only memory (xom) that allows instructions stored in memory to be executed but not otherwise manipulated. to support xom code we use a machine that supports internal compartments---a process in one compartment cannot read data from another compartment. all data that leaves the machine is encrypted, since we assume external memory is not secure. the design of this machine poses some interesting trade-offs between security, efficiency, and flexibility. we explore some of the potential security issues as one pushes the machine to become more efficient and flexible. although security carries a performance penalty, our analysis indicates that it is possible to create a normal multi-tasking machine where nearly all applications can be run in xom mode. while a virtual xom machine is possible, the underlying hardware needs to support a unique private key, private memory, and traps on cache misses. for efficient operation, hardware assist to provide fast symmetric ciphers is also required.
an empirical analysis of instruction repetition. we study the phenomenon of instruction repetition, where the inputs and outputs of multiple dynamic instances of a static instruction are repeated. we observe that over 80% of the dynamic instructions executed in several programs are repeated and most of the repetition is due to a small number of static instructions. we attempt understand the source of this repetitive behavior by categorizing dynamic program instructions into dynamic program slices at both a global level and a local (within function) level. we observe that repeatability is more an artifact of how computation is expressed, and less of program inputs. function-level analysis suggests that many functions are called with repeated arguments, though almost all of them have side effects. we provide commentary on exploiting the observed phenomenon and its sources in both software and hardware.
reactive synchronization algorithms for multiprocessors. synchronization algorithms that are efficient across a wide range of applications and operating conditions are hard to design because their performance depends on unpredictable run-time factors. the designer of a synchronization algorithm has a choice of protocols to use for implementing the synchronization operation. for example, candidate protocols for locks include test-and-set protocols and queueing protocols. frequently, the best choice of protocols depends on the level of contention: previous research has shown that test-and-set protocols for locks outperform queueing protocols at low contention, while the opposite is true at high contention.this paper investigates reactive synchronization algorithms that dynamically choose protocols in response to the level of contention. we describe reactive algorithms for spin locks and fetch-and-op that choose among several shared-memory and message-passing protocols. dynamically choosing protocols presents a challenge: a reactive algorithm needs to select and change protocols efficiently, and has to allow for the possibility that multiple processes may be executing different protocols at the same time. we describe the notion of consensus objects that the reactive algorithms use to preserve correctness in the face of dynamic protocol changes.experimental measurements demonstrate that reactive algorithms perform close to the best static choice of protocols at all levels of contention. furthermore, with mixed levels of contention, reactive algorithms outperform passive algorithms with fixed protocols, provided that contention levels do not change too frequently. measurements of several parallel applications show that reactive algorithms result in modest performance gains for spin locks and significant gains for fetch-and-op.
value locality and load value prediction. since the introduction of virtual memory demand-paging and cache memories, computer systems have been exploiting spatial and temporal locality to reduce the average latency of a memory reference. in this paper, we introduce the notion of value locality, a third facet of locality that is frequently present in real-world programs, and describe how to effectively capture and exploit it in order to perform load value prediction. temporal and spatial locality are attributes of storage locations, and describe the future likelihood of references to those locations or their close neighbors. in a similar vein, value locality describes the likelihood of the recurrence of a previously-seen value within a storage location. modern processors already exploit value locality in a very restricted sense through the use of control speculation (i.e. branch prediction), which seeks to predict the future value of a single condition bit based on previously-seen values. our work extends this to predict entire 32- and 64-bit register values based on previously-seen values. we find that, just as condition bits are fairly predictable on a per-static-branch basis, full register values being loaded from memory are frequently predictable as well. furthermore, we show that simple microarchitectural enhancements to two modern microprocessor implementations (based on the powerpc 620 and alpha 21164) that enable load value prediction can effectively exploit value locality to collapse true dependencies, reduce average memory latency and bandwidth requirements, and provide measurable performance gains.
tradeoffs in instruction format design for horizontal architectures. with recent improvements in software techniques and the enhanced level of fine grain parallelism made available by such techniques, there has been an increased interest in horizontal architectures and large instruction words that are capable of issuing more that one operation per instruction. this paper investigates some issues in the design of such instruction formats. we study how the choice of an instruction format is influenced by factors such as the degree of pipelining and the instruction's view of the register file. our results suggest that very large instruction words capable of issuing one operation to each functional unit resource in a horizontal architecture may be overkill. restricted instruction formats with limited operation issuing capabilities are capable of providing similar performance (measured by the total number of time steps) with significantly less hardware in many cases.
devirtualizable virtual machines enabling general, single-node, online maintenance. maintenance is the dominant source of downtime at high availability sites. unfortunately, the dominant mechanism for reducing this downtime, cluster rolling upgrade, has two shortcomings that have prevented its broad acceptance. first, cluster-style maintenance over many nodes is typically performed a few nodes at a time, mak-ing maintenance slow and often impractical. second, cluster-style maintenance does not work on single-node systems, despite the fact that their unavailability during maintenance can be painful for organizations. in this paper, we propose a novel technique for online maintenance that uses virtual machines to provide maintenance on single nodes, allowing parallel maintenance over multiple nodes, and online maintenance for standalone servers. we present the microvisor, our prototype virtual machine system that is custom tailored to the needs of online maintenance. unlike general purpose virtual machine environments that induce continual 10-20% over-head, the microvisor virtualizes the hardware only during periods of active maintenance, letting the guest os run at full speed most of the time. unlike past attempts at virtual machine optimization, we do not compromise os transparency. we instead give up generality and tailor our virtual machine system to the minimum needs of online maintenance, eschewing features, such as i/o and memory virtualization, that it does not strictly require. the result is a very thin virtual machine system that induces only 5.6% cpu overhead when virtualizing the hardware, and zero cpu overhead when devirtualized. using the microvisor, we demonstrate an online os upgrade on a live, single-node web server, reducing downtime from one hour to less than one minute.
continual flow pipelines. increased integration in the form of multiple processor cores on a single die, relatively constant die sizes, shrinking power envelopes, and emerging applications create a new challenge for processor architects. how to build a processor that provides high single-thread performance and enables multiple of these to be placed on the same die for high throughput while dynamically adapting for future applications? conventional approaches for high single-thread performance rely on large and complex cores to sustain a large instruction window for memory tolerance, making them unsuitable for multi-core chips. we present continual flow pipelines (cfp) as a new non-blocking processor pipeline architecture that achieves the performance of a large instruction window without requiring cycle-critical structures such as the scheduler and register file to be large. we show that to achieve benefits of a large instruction window, inefficiencies in management of both the scheduler and register file must be addressed, and we propose a unified solution. the non-blocking property of cfp keeps key processor structures affecting cycle time and power (scheduler, register file), and die size (second level cache) small. the memory latency-tolerant cfp core allows multiple cores on a single die while outperforming current processor cores for single-thread applications.
compiler-based prefetching for recursive data structures. software-controlled data prefetching offers the potential for bridging the ever-increasing speed gap between the memory subsystem and today's high-performance processors. while prefetching has enjoyed considerable success in array-based numeric codes, its potential in pointer-based applications has remained largely unexplored. this paper investigates compiler-based prefetching for pointer-based applications---in particular, those containing recursive data structures. we identify the fundamental problem in prefetching pointer-based data structures and propose a guideline for devising successful prefetching schemes. based on this guideline, we design three prefetching schemes, we automate the most widely applicable scheme (greedy prefetching) in an optimizing research compiler, and we evaluate the performance of all three schemes on a modern superscalar processor similar to the mips r10000. our results demonstrate that compiler-inserted prefetching can significantly improve the execution speed of pointer-based codes---as much as 45% for the applications we study. in addition, the more sophisticated algorithms (which we currently perform by hand, but which might be implemented in future compilers) can improve performance by as much as twofold. compared with the only other compiler-based pointer prefetching scheme in the literature, our algorithms offer substantially better performance by avoiding unnecessary overhead and hiding more latency.
sheaved memory: architectural support for state saving and restoration in paged systems. the concept of read-one/write-many paged memory is introduced and given the name sheaved memory. it is shown that sheaved memory is useful for efficiently maintaining checkpoints in main memory and for providing state saving and state restoration for software that includes recovery blocks or similar control structures. the organization of sheaved memory is described in detail, and a design is presented for a prototype sheaved-memory module that can be built easily from inexpensive, off-the-shelf components. the module can be incorporated within many available computers without altering the computers' hardware design. the concept of sheaved memory is simple and appealing, and its potential for use in a number of software contexts is foreseen.
d-sptf: decentralized request distribution in brick-based storage systems. distributed shortest-positioning time first (d-sptf) is a request distribution protocol for decentralized systems of storage servers. d-sptf exploits high-speed interconnects to dynamically select which server, among those with a replica, should service each read request. in doing so, it simultaneously balances load, exploits the aggregate cache capacity, and reduces positioning times for cache misses. for network latencies expected in storage clusters (e.g., 10--200μs), d-sptf performs as well as would a hypothetical centralized system with the same collection of cpu, cache, and disk resources. compared to popular decentralized approaches, d-sptf achieves up to 65% higher throughput and adapts more cleanly to heterogenous server capabilities.
variable length path branch prediction. accurate branch prediction is required to achieve high performance in deeply pipelined, wide-issue processors. recent studies have shown that conditional and indirect (or computed) branch targets can be accuratelypredicted by recording the path, which consists of the target addresses of recent branches, leading up to the branch. in current path based branch predictors, the n most recent target addresses are hashed together to form an index into a table, where n is some fixed integer. the indexed table entry isused to make a prediction for the current branch.this paper introduces a new branch predictor in which the value of n is allowed to vary. by constructing the index into the table using the last n target addresses, and using profiling information to select the proper value of n for each branch, extremely accurate branch prediction is achieved. for the specint95 gee benchmark, this new predictor has a conditional branch misprediction rate of 4.3% given a 4k byte hardware budget. for comparison, the gshare predictor, a predictor known for its high accuracy, has a conditional branch misprediction rate of 8.8% given the same hardware budget. for the indirect branches in gee, the new predictor achieves a misprediction rate of 27.7% when given a hardware budget of 512 bytes, whereas the best competingpredictor achieves a misprediction rate of 44.2% when given the same hardware budget.