CPU speeds double approximately every eighteen months, while main memory speeds double only about every ten years. These diverging rates imply an impending ``Memory Wall", in which memory accesses dominate program performance. An effective way to reduce the observed latency of memory accesses is data prefetching. Data prefetching involves predicting which data the processor will use in the near future and then bring that data into storage locations closer to the execution engine (e.g., caches, dedicated prefetch buffers etc.). Meanwhile, applications are constantly becoming more complex and demanding. This is reflected in programs through the use of various data structures and constructs provided by the programming language. While caches are extremely successful in handling accesses with good locality, the remaining accesses result in costly cache misses. For these reasons, we performed a study that maps the miss stream to several fundamental access types inherent to programming constructs. The results of this study show that pointer-based applications with accesses to linked data structures present the biggest challenge to the memory subsystem. Consequently, they have the biggest potential for speedup when their adverse effects on program performance are removed by data prefetching. For these reasons, in this thesis, we focus on data prefetching techniques targeting pointer-based applications which have irregular access patterns. With a better understanding of the kinds of accesses that cause cache misses, we have developed three prefetching techniques that can handle all these cases. The first technique enhances traditional stream buffer designs by following an address prediction stream instead of a fixed stride as originally proposed. This improves the stream buffers ability to target pointer-based programs. We also explore utilizing a hardware pointer cache to predict the values of pointer loads in order to break down long dependence chains caused by recurrent pointer accesses. This allows overlapping the execution of dependent instructions with the actual memory access, providing significant benefits. Another technique, Speculative Precomputation, attempts to prefetch data ahead of its use, by running a shortened version of the program on a spare multi-threaded hardware context. The final scheme we propose builds upon speculative precomputation and uses the pointer cache for the pointer loads in speculative threads. Furthermore, we add control flow instructions to the speculative threads to guide them down the correct traversal path when multiple next transitions are possible. Our results show considerable benefits when these techniques are utilized together, complementing each other.

Pre-2018 CSE ID: CS2003-0753

An effective method for reducing the effect of load latency in modern processors is data prefetching. One form of hardware-based data prefetching, stream buffers, has been shown to be particularly effective due to its' ability to detect data streams and run ahead of them, prefetching as it goes. Unfortunately, in the past, the applicability of streaming was limited to stride intensive code. In this paper we propose Predictor-Directed Stream Buffers (PSB), which allows the stream buffer to follow a general address prediction stream instead of a fixed stride. A general address prediction stream complicates the allocation of both stream buffer and memory resources, because the predictions generated will not be as reliable as prior sequential next-line and stride-based stream buffer implementations. To address this, we examine using confidence-based techniques to guide the allocation and prioritization of stream buffers and their prefetch requests. Our results show that when using PSB on a benchmark suite heavy in pointer-based applications, PSB provides a 23% speedup on average over the best previous stream buffer implementation, and an improvement of 75% over using no prefetching at all.

Pre-2018 CSE ID: CS2001-0694

In a single second a modern processor can execute billions of instructions. Obtaining a bird's eye view of the behavior of a program at these speeds can be a difficult task when all that is available is cycle by cycle examination. In many programs, behavior is anything but steady state, and understanding the patterns of behavior at run-time can unlock a multitude of optimization opportunities. In this paper we present a unified profiling architecture that can efficiently capture, classify, and predict program behavior on the largest of time scales all at run-time with no support from software. By examining the proportion of instructions that were executed from different sections of code, we can find generic phases that correspond to changes in behavior across many metrics. By classifying phases generically, we avoid the need to identify phases for each optimization, and enable a unified prediction scheme that can forecast future behavior. We examine the ability of our phase tracking architecture to accurately capture the phase behavior of a program's execution with respect to its overall performance (IPC), branch prediction, cache performance, and energy, and show how phase behavior may be captured efficiently using a simple predictor.

Pre-2018 CSE ID: CS2002-0710

Data prefetching effectively reduces the negative effects of long load latencies on the performance of modern processors. Hardware prefetchers employ hardware structures to predict future memory addresses based on previous patterns. Thread-based prefetchers use portions of the actual program code to determine future load addresses for prediction. In this paper, we combine both of these techniques to address the memory performance of pointer-based applications. We combine a thread-based prefetcher, based on speculative precomputation, with a pointer cache. The pointer cache is a new hardware address predictor that tracks pointer transitions. Previously proposed thread-based prefetchers are limited in how far they can run ahead of the main thread in the face of recurrent dependent loads. When combined with the pointer cache, a speculative thread can make better progress ahead of the main thread, rapidly traversing data structures, despite pointer transition cache misses. The pointer cache allows the consumers of a pointer load miss to issue before the data actually arrives. Our results show that using a pointer cache with speculative precomputation achieves a 65% speedup on average over a speculative precompution architecture with a larger L3 cache.

Pre-2018 CSE ID: CS2002-0712

The increasing demand for high performance forces computer architects to employ a plethora of hardware optimizations. These optimizations and new architecture features are often examined with past generation compilers that do not take into account the new architecture optimizations. The use of a complier that is unaware of a set of architecture optimizations may lead to an incorrect estimation of the impact of these new optimizations. This problem is exacerbated for in-order architectures which rely on the complier to assist in scheduling. Our research focuses on efficient techniques for generating a highly optimized and scheduled binary for VLIW and in-order architectures. We propose to use a modified out-of-order simulator to generate a trace scheduled binary for in-order execution. Our constrained out-of-order machine resolves dependencies and allows independent instructions to move above stalled instructions exposing the available parallelism within a program, and performing the appropriate level of loop unrolling and inlining for the architecture. This new trace binary can then be used to guide architectural research, even when there may not yet exist an optimizing compiler for the architecture being evaluated. In this paper we examine the merits of the simulator-based trace optimizer and show how it performs compared to un-scheduled code on an in-order machine.

Pre-2018 CSE ID: CS2002-0711