Flow spread measurement provides fundamental statistics that can help network operators better understand flow characteristics and traffic patterns with applications in traffic engineering, cybersecurity and quality of service. Past decades have witnessed tremendous performance improvement for single-flow spread estimation. However, when dealing with numerous flows in a packet stream, it remains a significant challenge to measure per-flow spread accurately while reducing memory footprint. The goal of this paper is to introduce new multi-flow spread estimation designs that incur much smaller processing overhead and query overhead than the state of the art, yet achieves significant accuracy improvement in spread estimation. We formally analyze the performance of these new designs. We implement them in both hardware and software, and use real-world data traces to evaluate their performance in comparison with the state of the art. The experimental results show that our best sketch significantly improves over the best existing work in terms of estimation accuracy, packet processing throughput, and online query throughput.

Measuring flow spread in real time from large, high-rate data streams has numerous practical applications, where a data stream is modeled as a sequence of data items from different flows and the spread of a flow is the number of distinct items in the flow. Past decades have witnessed tremendous performance improvement for single-flow spread estimation. However, when dealing with numerous flows in a data stream, it remains a significant challenge to measure per-flow spread accurately while reducing memory footprint. The goal of this paper is to introduce new multi-flow spread estimation designs that incur much smaller processing overhead and query overhead than the state of the art, yet achieves significant accuracy improvement in spread estimation. We formally analyze the performance of these new designs. We implement them in both hardware and software, and use real-world data traces to evaluate their performance in comparison with the state of the art. The experimental results show that our best sketch significantly improves over the best existing work in terms of estimation accuracy, data item processing throughput, and online query throughput.

State-of-the-art cache compression methods compress multiple neighboring blocks often called as a sector into a single 64-byte block to effectively enlarge the cache capacity. A compressed block is created by storing 4-byte data patterns as dictionary entries and pointers to them for compressing multiple blocks. Furthermore, sector-based tag array maintains one-to-one mapping between tag and data arrays in order to preserve conventional cache access mechanism. We present a dual-block compression method which uses an entire uncompressed block as dictionary and compresses multiple neighboring blocks in a separate companion block to provide a larger dictionary for better compression ratios. Furthermore, we introduce the concept of buddy-set which expands the compressible candidate blocks across two adjacent cache sets to enlarge the scope of compression. Performance evaluations for the last-level cache show that the proposed dual-block compression with expansion of compressible candidates in the buddy-set can enlarge the cache by an average of 60% while current state-of-art compression proposal has only 29% improvement. The proposed scheme demonstrates 8.9% speedup over caches without compression.

Spin-Transfer Torque Magnetoresistive Random-Access Memory (STT-MRAM) is a promising memory technology, which has high density, fast read speed, low leakage power, and non-volatility, and is suitable for multi-core on-chip last-level caches. However, the high write energy and latency, as well as less-than-desirable write endurance of STT-MRAM remain challenges. This paper proposes a new encoded content-aware cache replacement policy to reduce the total switch bits for write, lower the write energy, and improve write endurance. Instead of replacing the LRU block under the conventional pseudo-LRU replacement policy, we select a replacement block near the LRU position, which has the most similar content to the missed block. The selected replacement block can reduce the switch bits without damaging the cache performance. To avoid fetching and comparing the entire block contents, we present a novel content encoding method to encode 64-byte block using just 8 bits, each bit represents 8-byte content. The encoded bit is determined by the presence of a dominant bit value in the 8 bytes. We measure the content similarity using the Hamming distance between the encoded bits of the missed block and the replaced block. Performance evaluation demonstrates that the proposed simple content encoding method is effective with an average of 20.5% reduction in total switch bits, which results in improvement on write endurance and less write energy consumption. These improvements are accomplished with low overhead and minimum impact on the cache performance.

Spin-Transfer Torque Magnetoresistive Random Access Memory (STT-MRAM) is a promising memory technology, which has high density, low leakage power, fast read speed, and non-volatility, and is suitable for on-chip last-level caches with large capacity. Recently, Multi-Level Cell (MLC) STT-MRAM records two bits in a single cell to further improve the density for building even bigger on-chip caches. However, MLC worsens write energy consumption and endurance. The magnetization directions of its hard and soft domains cannot be flipped to two opposite directions simultaneously, which leads to the two-step transition problem for certain combinations of updating the 2-bit value. The two-step transition incurs extra flip in the soft domains, consume high energy, and negatively impact the life time of MLC STT-MRAM. In this paper, we present a new dimension to alleviate high write energy issue in MLC. During cache replacement, we select among a few candidates blocks close to the LRU position for replacement to lower the write energy with minimum impact on cache performance. We propose a novel block content encoding method to represent whole block with a few bits and use the encoding bits for better cache replacement. After picking the replacement block, we apply intelligent remap of each updated 2-bit values to further reduce the write energy. Performance evaluation results show this content-aware cache replacement can lower the write energy by 26.1% in comparison with MLC caches using regular Pseudo-LRU replacement policy.

Large off-die stacked DRAM caches have been proposed to provide higher effective bandwidth and lower average latency to main memory. Designing a large off-die DRAM cache with conventional block size requires a large tag array which is impractical to fit on-die. Placing the large directory off-die prolong the latency since a tag access is necessary before the data can be accessed. This additional trip also generates extra off-die traffic. In this paper, we present a novel design called Cache Lookaside Table (CLT) to reduce the average access latency and to lessen off-die tag array accesses. The basic approach is to cache a small amount of recently referenced tags on-die. An off-die tag access is avoided when a requested block's tag hits a cached tag. To save on-die space, cached tags are recorded in a large sector for sharing tags with multiple blocks. However, due to the loss of one-to-one physical mapping of the cached tags and the data array, a way pointer is added for each block to indicate its way location. The proposed CLT exploits memory reference locality and provides a fast alternative tag path to capture most of the DRAM cache requests. In comparison with other proposed DRAM caching mechanisms, the on-die CLT approach shows an average performance improvement in the range of 4-15%.

In order to hide long memory latency and alleviate memory bandwidth requirement, a fourth-level cache (L4) is introduced in modern high-performance multi-core systems for supporting parallel computation. However, additional cache level causes higher cache miss penalty since a request needs to go through all levels of caches to reach to the main memory. In this paper, we introduce a new way of using a Bloom Filter (BF) to predict cache misses at any cache level in a multicore system. These misses can runahead to access lower-level caches or memory to reduce the miss penalty. The proposed hashing scheme extends the cache index of the target set and uses it for accessing the BF array to avoid counters in the BF array. Performance evaluation using a set of SPEC2006 benchmarks on 8-core systems with 4-level cache hierarchy shows that using a BF for the third-level (L3) cache to filter and runahead L3 misses, the IPCs can be improved by 4-20% with an average 10.5%. In comparison with the delay-recalibration scheme, the improvement is 3.5-4.8%.

Maintaining hardware cache coherence on future CMPs becomes increasingly important and difficult as the number of cores keeps accelerating in mainstream multicore chips. The simple snooping-bus coherence scheme is not suitable due to its limited scalability. The sparse coherence directory approach may incur extra cache invalidations due to a topological mismatch between the coherence directory and the directories of all cache modules. In this paper, we propose an innovative CMP coherence directory that has three important properties. First, the directory has a simple set-associative design with small associativity. The number of directory entries matches the total number of cache blocks. Second, an augmented Directory Lookaside Table (DLT) allows blocks to be displaced from their primary sets in the coherence directory for alleviating hot-set conflicts. Third, to avoid expensive presence bits, each copy of a block along with the located core ID occupies a separate directory entry. Performance evaluations based on multithreaded and multi-programmed workloads demonstrate significant advantages of the proposed CMP directory over directories with traditional set-associative or skewed associative designs.

The routing and packet forwarding function is at the core of the IP network-layer protocols. The throughput of a router is constrained by the speed at which the routing table lookup can be performed. Hash-based lookup has been a research focus in this area due to its O(1) average lookup time, as compared to other approachs such as trie-based lookup which tends to make more memory accesses. With a series of prior multi-hashing developments, including d-random, 2-left, and d-left, we discover that a new guided multi-hashing approach holds the promise of further pushing the envelope of this line of research to make significant performance improvement beyond what today's best technology can achieve. Our guided multi-hashing approach achieves near perfect load balance among hash buckets, while limiting the number of buckets to be probed for each key (address) lookup, where each bucket holds one or a few routing entries. Unlike the localized optimization by the prior approaches, we utilize the full information of multi-hash mapping from keys to hash buckets for global key-to-bucket assignment. We have dual objectives of lowering the bucket size while increasing empty buckets, which helps to reduce the number of buckets brought from off-chip memory to the network processor for each lookup. We introduce mechanisms to make sure that most lookups only require one bucket to be fetched. Our simulation results show that with the same number of hash functions, the guided multiple-hashing schemes are more balanced than d-left and others, while the average number of buckets to be accessed for each lookup is reduced by 20–50%.

Modern General-Purpose computation on Graphics Processing Units (GPGPUs) explore parallelism in applications by building massively parallel architecture and apply multithreading technology to hide the instruction and memory latencies. Such architectures become increasingly popular for parallel applications using CUDA/OpenCL programming languages. In this paper, we investigate thread scheduling algorithms on such highly-threaded GPGPUs. The traditional round-robin scheduling schemes are inefficient in handling instruction execution and memory accesses with disparate latencies. We introduce a new GPGPU thread (warp) scheduling algorithm which enables flexible roundrobin distance for efficiently utilizing multithread parallelism and use program-guided priority shift among concurrent threads (warps) to allow more overlaps between short-latency compute instructions and long-latency memory accesses. Performance evaluations demonstrate that the new scheduling algorithm improves a set of kernel execution times by an average of 12% with 52% reduction on scheduler stall cycles over the fine-granularity round-robin scheme. In this paper, we also accomplish a thorough evaluation of various thread scheduling algorithms based on the amount of hardware threads, the scheduling overhead, and the global memory latency.

Cache misses frequently exhibit repeated streaming behavior, i.e. a sequence of cache misses has a high tendency of being repeated. Correlation-based prefetchers record the missing streams in a history table for accurate prefetching. Saving a large miss history in off-chip DRAM is a practical implementation, but incurs access latency and consumes memory bandwidth which leads to performance degradation. In this paper, we investigate a new data prefetching mechanism based on per-block miss correlation where a miss is correlated with an earlier miss when the two misses are closely encountered both in time and space. The miss correlations are captured dynamically and saved along with the content of the data block using a simple data compression technique. As a result of this novel combination, our scheme provides unbounded correlation history and its prefetch metadata can be fetched together with demand data without incurring additional latency nor consuming any memory bandwidth. Performance evaluations using data-parallel applications demonstrate that prefetchers based on per-block miss correlations can improve IPC by 42-139% with an average of 88% compared to the IPC without prefetching. In comparison with regular stream prefetcher, sampled temporal streaming prefetcher and spatial-temporal memory streaming prefetcher, up to 115%, 99% and 98% IPC improvement can be obtained with an average about 36%, 26% and 27% respectively.

Graphics Processing Units (GPUs) have emerged as a promising platform for parallel computation. With a large number of processor cores and abundant memory bandwidth, GPUs deliver substantial computation power. While providing high computation performance, a GPU consumes high power and needs sufficient power supplies and cooling systems. It is essential to institute an efficient mechanism for evaluating and understanding the power consumption when running real applications on high-end GPUs. In this paper, we present a high-level GPU power consumption model using sophisticated tree-based random forest methods which correlate and predict the power consumption using a set of performance variables. We demonstrate that this statistical model not only predicts the GPU runtime power consumption more accurately than existing regression based approaches, but more importantly, it provides sufficient insights into understanding the correlation of the GPU power consumption with individual performance metrics. We use a GPU simulator that can collect more runtime performance metrics than hardware counters. We measure the power consumption of a wide-range of CUDA kernels on an experimental system with GTX 280 GPU to collect statistical samples for power analysis. The proposed method is applicable to other GPUs as well.

IP lookup is one of the key functions in the design of core routers. Its efficiency determines how fast a router can forward packets. As new content is continuously brought to the Internet, novel routing technologies must be developed to meet the increasing throughput demand. Hash-based lookup schemes are promising because they have low lookup delays and can handle large routing tables. To achieve high throughput, we must choose the hash function to reduce the lookup bandwidth from the off-chip memory where the routing table is stored. The routing table updates also need to be handled to avoid costly re-setup. In this paper, we propose AP-Hash, an approximately perfect hashing approach that not only distributes routing-table entries evenly in the hash buckets but also handles routing table updates with low overhead. We also present an enhanced approach, called AP-Hash-E, which is able to process far more updates before a complete re-setup becomes necessary. Experimental results based on real routing tables show that our new hashing approaches achieve a throughput of 250M packets per second and perform re-setup as few as just once per month.

The spread of a source host is the number of distinct destinations that it has sent packets to during a measurement period. A spread estimator is a software/hardware module on a router that inspects the arrival packets and estimates the spread of each source. It has important applications in detecting port scans and distributed denial-of-service (DDoS) attacks, measuring the infection rate of a worm, assisting resource allocation in a server farm, determining popular Web contents for caching, to name a few. The main technical challenge is to fit a spread estimator in a fast but small memory (such as SRAM) in order to operate it at the line speed in a high-speed network. In this paper, we design a new spread estimator that delivers good performance in tight memory space where all existing estimators no longer work. The new estimator not only achieves space compactness, but operates more efficiently than the existing ones. Its accuracy and efficiency come from a new method for data storage, called virtual vectors, which allow us to measure and remove the errors in spread estimation. We also propose several ways to enhance the range of spread values that the estimator can measure. We perform extensive experiments on real Internet traces to verify the effectiveness of the new estimator .

New generations of video, voice, high-performance computing and social networking applications have continuously driven the development of novel routing technologies for higher packet forwarding speeds to meet the future Internet demand. One of the fundamental design issues for core routers is fast routing table lookup, which is a key problem at the network layer of the Internet protocol suite. It is difficult to scale the current TCAM-based or trie-based solutions for future routing tables due to increasing table size, longer prefix length, and demands for higher throughput. This paper focuses on hash-based lookup solutions that have the potential of offering high throughput at one memory access per packet. We design the first deterministic multi-hashing scheme with small indexing overhead, which evenly distributes address prefixes to hash buckets for routing-information storage. We minimize both the size of each bucket and the number of buckets that need to be fetched to the network processor for packet forwarding. Consequently, near-optimal routing throughput is achieved. Performance evaluations demonstrate that the proposed deterministic multi-hashing scheme can maintain a constant lookup rate of over 250 million packets per second with today's commodity SRAM, which is much faster than the existing hashing schemes.

Traversal through a Linked Data Structure (LDS) in applications encounters heavy cache misses and severe performance degradation. Due to tight load-load dependences in LDS traversal, the chance of overlapping the cache misses in exploiting the memory-level parallelism is slim. Furthermore, the irregularity of the missing block addresses makes it difficult for accurate data prefetching without recording a huge miss history. In this paper, we present a semantics-aware approach to dynamically identify pointer links in each node for traversal to the next node. Accurate LDS prefetching based on the node semantics can be accomplished with minimum history information. In addition, we evaluate three hardware-based leap prefetching methods to timely fetch the nodes further ahead in the traversal path for overcoming the lateness in LDS prefetching. Performance evaluations based on LDS intensive applications show that with an integrated stream/stride prefetcher, semantics-aware prefetcher improves performance over without prefetching by 45%. In comparison with the stream prefetcher, a dependence-based prefetcher, and a content-directed prefetcher, the average improvement is 20%, 16%, and 23% respectively.

On NVIDIA's many-core GPUs, there is no synchronization function among parallel thread blocks. When fine-granularity of data communication and synchronization is required for large-scale parallel programs executed by multiple thread blocks, frequent host synchronization are necessary, and they incur a significant overhead. We investigate a class of applications which uses a chaotic version of iterative methods to obtain numerical solutions for partial differential equations (PDE). Such a fast PDE solver is parallelized on GPUs with multiple thread blocks. In this parallel implementation, although frequent data communication is needed between adjacent thread blocks, a precise order of the data communication is not necessary. Separate communication threads are used for periodically exchanging the boundary values with adjacent thread blocks through the global memory. Since a precise order of the data communication is not required, the computation and the communication threads can be overlapped to alleviate the communication overhead. Performance measurements of two popular applications, Poisson image editing from computer graphics and shape from shading from computer vision, on Tesla C1060 show that a speedup of 4–5 times is achievable for both applications in comparison with the solution using host synchronization.

The spread of a source host is the number of distinct destinations that it has sent packets to during a measurement period. A spread estimator is a software/hardware module on a router that inspects the arrival packets and estimates the spread of each source. It has important applications in detecting port scans and DDoS attacks, measuring the infection rate of a worm, assisting resource allocation in a server farm, determining popular Web contents for caching, to name a few. The main technical challenge is to fit a spread estimator in a fast but small memory (such as SRAM) in order to operate it at the line speed in a high-speed network. In this paper, we design a new spread estimator that delivers good performance in tight memory space where all existing estimators no longer work. The new estimator not only achieves space compactness but operates more efficiently than the existing ones. Its accuracy and efficiency come from a new method for data storage, called virtual vectors, which allow us to measure and remove the errors in spread estimation. We perform experiments on real Internet traces to verify the effectiveness of the new estimator.

Performance trade-offs between fast data access by local data replication and cache capacity maximization by global data sharing have been extensively studied for many-core Chip Multiprocessors (CMPs). Costly simulations over a wide spectrum of the design space are generally required to gain insight for a sound design. To lower the cost, we develop an abstract model for understanding the performance impact of data replication on CMP caches. To overcome the lack of real-time interactions among multiple cores in the model, we further develop an efficient single-pass stack simulation to study the performance of CMP cache organizations with various degrees of data replication. The global stack logically incorporates a shared stack and per-core private stacks; shared/private reuse (stack) distances can be collected in a single-pass simulation. With the reuse distances, one can calculate the performance of CMP cache organizations with various degrees of data replication. We verify both the model and the stack simulation against execution-driven simulations with commercial multithreaded workloads. The results show that the abstract model provides accurate information about performance trade-offs of data replication. The stack simulation accurately predicts the performance of various cache organizations with 2-9 percent error margins using only about 8 percent of the simulation time.

Intelligent sharing cache space among multiple cores on a Chip Multiprocessor (CMP) has become an important research topic. There are many design options to trade off and many possible performance metrics to evaluate. It generally requires costly simulations to gain insights over a wide-spectrum of cache sharing and partitioning methods. In this paper, we use an efficient single-pass stack simulation method to understand the effectiveness of cache sharing through natural competition (i. e. shared cache) and through static or dynamic cache partitioning, such as equal partition, utility-based partition, etc. The results demonstrate that cache occupancy through natural competition favors the core with more frequently misses. It may take away the needed space for other cores and increase the overall miss ratio. Furthermore, we find that the existing cache partitioning schemes based on fixed-length portioning phases may not be optimal compared with the scheme that allows variable phase lengths.

As chip multiprocessor (CMP) has become the mainstream in processor architectures, Intel and AMD have introduced their dual-core processors to the PC market. In this paper, performance studies on an Intel Core 2 Duo, an Intel Pentium D and an AMD Athlon 64times2 processor are reported. According to the design specifications, key derivations exist in the critical memory hierarchy architecture among these dual-core processors. In addition to the overall execution time and throughput measurement using both multiprogrammed and multi-threaded workloads, this paper provides detailed analysis on the memory hierarchy performance and on the performance scalability between single and dual cores. Our results indicate that for the best performance and scalability, it is important to have (1) fast cache-to-cache communication, (2) large L2 or shared capacity, (3) fast L2 to core latency, and (4) fair cache resource sharing. Three dual-core processors that we studied have shown benefits of some of these factors, but not all of them. Core 2 Duo has the best performance for most of the workloads because of its microarchitecture features such as shared L2 cache. Pentium D shows the worst performance in many aspects due to its technology-remap of Pentium 4.

The future chip-multiprocessors (CMPs) with a large number of cores faces difficult issues in efficient utilizing on-chip storage space. Tradeoffs between data accessibility and effective on-chip capacity have been studied extensively. It requires costly simulations to understand a wide-spectrum of design spaces. In this paper, we first develop an abstract model for understanding the performance impact with respect to the degree of data replication. To overcome the lack of real-time interactions among multiple cores in the abstract model, we propose an efficient single-pass stack simulation method to study the performance of a variety of cache organizations on CMPs. The proposed global stack logically incorporates a shared stack and per-core private stacks to collect shared/private reuse (stack) distances for every memory reference in a single simulation pass. With the collected reuse distances, performance in terms of hits/misses and average memory access times can be calculated for multiple cache organizations. The basic stack simulation results can further derive other CMP cache organizations with various degrees of data replication. We verify both the modeling and the stack results against individual execution-driven simulations that consider realistic cache parameters and delays using a set of commercial multithreaded workloads. We also compare the simulation time saving with the stack simulation. The results show that stack simulation can accurately model the performance of various studied cache organizations with 2-9% error margins using only about 8% of the simulation time. The results also show that the effectiveness of various techniques for optimizing the CMP on-chip storage is closely related to the working sets of the workloads as well as the total cache sizes

Modern out-of-order processors with non-blocking caches exploit Memory-Level Parallelism (MLP) by overlapping cache misses in a wide instruction window. The exploitation of MLP, however, can be limited due to long-latency operations in producing the base address of a cache miss load. When the parent instruction is also a cache miss load, a serialization of the two loads must be enforced to satisfy the load-load data dependence.In this paper, we propose a mechanism that dynamically captures the load-load data dependences at runtime. A special Preload is issued in place of the dependent load without waiting for the parent load, thus effectively overlapping the two loads. The Preload provides necessary information for the memory controller to calculate the correct memory address upon the availability of the parent's data to eliminate any interconnect delay between the two loads. Performance evaluations based on SPEC2000 and Olden applications show that significant speedups up to 40% with an average of 16% are achievable using the Preload. In conjunction with other aggressive MLP exploitation methods, such as runahead execution, the Preload can make more significant improvement with an average of 22%.

Due to shared cache contentions and interconnect delays, data prefetching is more critical in alleviating penalties from increasing memory latencies and demands on chip-multiprocessors (CMPs). Through deep analysis of SPEC2000 applications, we find that a part of the nearby data memory references often exhibit highly-repeated patterns with long, but equal block reuse distance. These references can form a coterminous group (CG). Coterminous locality is introduced as that when a member in a CG is referenced, the remaining members will likely be referenced in the near future. Based on the coterminous locality behavior, we implement a novel CG data prefetcher on CMPs. Performance evaluations show that the proposed prefetcher can accurately cover up to 40-50% of the total misses, and result in 50-60% of potential performance improvement for several selected workload mixes

Data communications between producer instructions and consumer instructions through memory incur extra delays that degrade processor performance. We introduce a new storage media with a novel addressing mechanism to avoid address calculations. Instead of a memory address, each load and store is assigned a signature for accessing the new storage. A signature consists of the color of the base register along with its displacement value. A unique color is assigned to a register whenever the register is updated. When two memory instructions have the same signature, they address to the same memory location. This memory signature can be formed early in the processor pipeline. A small signature buffer, addressed by the memory signature, can be established to permit stores and loads bypassing normal memory hierarchy for fast data communication. Performance evaluations based on an Alpha 21264-like pipeline using SPEC2000 integer benchmarks show that an IPC (instruction-per-cycle) improvement of 13-18% is possible using a small 8-entry signature buffer.

An increasing cache latency in next-generation processors incurs profound performance impacts in spite of advanced out-of-order execution techniques. One way to circumvent this cache latency problem is to predict load values at the onset of pipeline execution by exploiting either the load value locality or the address correlation of stores and loads. In this paper, we describe a new load value speculation mechanism based on the program syntax correlation of stores and loads. We establish a symbolic cache (SC) , which is accessed in early pipeline stages to achieve a zero-cycle load. Instead of using memory addresses, the SC is accessed by the encoding bits of base register ID plus the displacement directly from the instruction code. Performance evaluations using SPEC95 and SPEC2000 integer programs on SimpleScalar simulation tools show that the SC achieves higher prediction accuracy in comparison with other load value speculation methods, especially when hardware resources are limited.

Concentration of design effort for current single-chip commercial-off-the-shelf (COTS) microprocessors has been directed towards performance. Reliability has not been the primary focus. As supply voltage scales to accommodate technology scaling and to lower power consumption, transient errors are more likely to be introduced. The basic idea behind any error tolerance scheme involves some type of redundancy. Redundancy techniques can be categorized in three general categories: (1) hardware redundancy, (2) information redundancy, and (3) time redundancy. Existing time redundant techniques for improving reliability of a superscalar processor utilize the otherwise unused hardware resources as much as possible to hide the overhead of program re-execution and verification. However, our study reveals that re-executing of long latency operations contributes to performance loss. We suggest a method to handle short and long latency instructions in slightly different ways to reduce the performance degradation. Our goal is to minimize the hardware overhead and performance degradation while maximizing the fault detection coverage. Experimental studies through microarchitecture simulation are used to compare performance lost due to the proposed scheme with non-fault tolerant design and different existing time redundant fault tolerant schemes. Fourteen integer and floating-point benchmarks are simulated with 1.8/spl sim/13.3% performance loss when compared with non-fault-tolerant superscalar processor.

A processor must know a load instruction's latency to schedule the load's dependent instructions at the correct time. Unfortunately, modern processors do not know this latency until well after the dependent instructions should have been scheduled to avoid pipeline bubbles between themselves and the load. One solution to this problem is to predict the load's latency, by predicting whether the load will hit or miss in the data cache. Existing cache hit/miss predictors, however, can only correctly predict about 50% of cache misses.This paper introduces a new hit/miss predictor that uses a Bloom Filter to identify cache misses early in the pipeline. This early identification of cache misses allows the processor to more accurately schedule instructions that are dependent on loads and to more precisely prefetch data into the cache. Simulations using a modified SimpleScalar model show that the proposed Bloom Filter is nearly perfect, with a prediction accuracy greater than 99% for the SPECint2000 benchmarks. IPC (Instructions Per Cycle) performance improved by 19% over a processor that delayed the scheduling of instructions dependent on a load until the load latency was known, and by 6% and 7% over a processor that always predicted a load would hit the cache and with a counter-based hit/miss predictor respectively. This IPC reaches 99.7% of the IPC of a processor with perfect scheduling.

An increasing cache latency in next-generation processors incurs profound performance impacts in spite of advanced out-of-order execution techniques. One way to circumvent this cache latency problem is to predict the load values at the onset of pipeline execution by exploiting either the load value locality or the address correlation of stores and loads. We describe a new load value speculation mechanism based on the program syntax correlation of stores and loads. We establish a symbolic cache, which is accessed by the content of memory load and store instructions in early pipeline stages to achieve a zero-cycle load. The performance evaluation using SPEC95 and SPEC2000 integer programs with SimpleScalar tools shows that the symbolic cache provides higher accuracy than both the memory renaming and the value prediction scheme, especially when hardware resources are limited.

An increasing cache latency in future processors incurs profound performance impacts in spite of advanced out-of-order execution techniques. In this paper, we describe an early address resolution mechanism that accurately resolves both regular and irregular load addresses. The basic idea is to build dynamic dependence links from the instruction that updates the base register to the consumer load instructions. Once a new base address is available, it triggers calculations of the new load addresses for dependent loads. Furthermore, the exact cache location of the requested data is predicted based on the newly resolved load address. As a result, this direct load can access the data cache directly to achieve a zero-cycle load latency. Performance evaluation using SPEC integer programs shows that the dynamic dependence links can be established accurately. Combined with a stride-based predictor, the proposed early address resolution achieves about 97% average accuracy with less than 1% misprediction. Based on a modified SimpleScalar model, the proposed method can potentially improve the IPC by about 18%.

As the performance gap between processors and main memory continues to widen, increasingly aggressive implementations of cache memories are needed to bridge the gap. In this paper, we consider some of the issues that are involved in the implementation of highly optimized cache memories and survey the techniques that can be used to help achieve the increasingly stringent design targets and constraints of modern processors. In particular, we consider techniques that enable the cache to be accessed quickly and still achieve a good hit ratio. We also consider issues such as area cost and bandwidth requirements. Trace-driven simulations of a TPC-C-like workload and selected applications from the SPEC95 benchmark suite are used in the paper to compare the performance of some of the techniques.

Memory references exhibit locality and are therefore not uniformly distributed across the sets of a cache. This skew reduces the effectiveness of a cache because it results in the caching of a considerable number of less-recently-used lines which are less likely to be re-referenced before they are replaced. In this paper, we describe a technique that dynamically identifies these less-recently-used lines and effectively utilizes the cache frames they occupy to more accurately approximate the global least-recently-used replacement policy while maintaining the fast access time of a direct-mapped cache. We also explore the idea of using these underutilized cache frames to reduce cache misses through data prefetching. In the proposed design, the possible locations that a line can reside in is not predetermined. Instead, the cache is dynamically partitioned into groups of cache lines. Because both the total number of groups and the individual group associativity adapt to the dynamic reference pattern, we call this design the adaptive group-associative cache. Performance evaluation using trace-driven simulations of the TPC-C benchmark and selected programs from the SPEC95 benchmark suite shows that the group-associative cache is able to achieve a hit ratio that is consistently better than that of a 4-way set-associative cache. For some of the workloads, the hit ratio approaches that of a fully-associative cache.

There are two concurrent paths in a typical cache access -one through the data array and the other through the tag array. In most cases, the path through the tag array is significantly longer than that through the data array. In this paper, we propose a new scheme that exploits this imbalance in the tag and data paths to improve overall cache performance. Under this scheme, an additional tag directory, the full-map block directory, is used to provide an alternate tag path to speed up cache access for almost all the memory requests. This scheme is based on the observation that spatial locality exists on a cache line basis i.e. cache lines near one another tend to be referenced together. Performance evaluation using the TPC-C benchmark and the SPEC92 benchmark suite demonstrates that this scheme has the potential to improve overall system performance by more than 20%.

There are two concurrent paths in a typical cache access --- one through the data array and the other through the tag array. The path through the data array drives the selected set out of the array. The path through the tag array determines cache hit/miss and, for set-associative caches, selects the appropriate line from within the selected set. In both directmapped and set-associative caches, the path through the tag array is significantly longer than that through the data array. In this paper, we propose a path balancing technique to help match the delays of the tag and data paths. The basic idea behind this technique is to employ a separate subset of the tag array to decouple the one-to-one relationship between address tags and cache lines so as to achieve a design that provides higher performance. Performance evaluation using both TPC-C and SPEC92 benchmarks shows that this path balancing technique offers impressive improvements in overall system performance over conventional cache...

Private caches are critical components in high per formance multiprocessor systems. However, it has been found that, when executing a parallel program, individual processors are very difficult to attain high cache hit ratio from one program section to another; therefore sophisti cated software coherence schemes are not cost effective. In this study, trace-driven simulation has been used to evaluate various less sophisticated compiler and software techniques which can enhance this inter-section locality in parallel executions. We found that the locality can be substantially im proved through the following ways of altering the sched uling of iterations in parallel DO loops among the executing processors: i) assignment of iterations in chunks, ii) reversed execution of parallel loops, and Hi) interchange inner and outer loops. These can be done manually by a programmer or automatically by a parallelizing compiler. Moreover, we also propose a software coherence scheme which can attain the maxi mum inter-section locality for read-only shared data.

The authors propose design techniques that may significantly simplify the cache access path, and hence offer the opportunity of shorter cycle time or fewer pipeline stages. Their proposals are based on highly accurate prediction methods that allow them to efficiently resolve address translation information early in the pipe.>

An approach to workload sampling in which, instead of selection of memory references based on the time parameter, sample decisions are based on where the cache is accessed. More specifically, the sampling heuristics are focused on analysis for set-associative caches. The validity of the heuristics is supported with empirical data. Four sampling policies are discussed, and simulation results based on a commercial database transaction workload are presented. Observations from simulation studies with SPEC 1.0 uniprogram benchmarks are also described. An environment in which congruence class sampling may be useful is illustrated.>

Techniques for sampling of cache congruence classes are considered. A sampling policy that selects on the basis of where a reference hits the cache (physically) instead of when a reference arrives is examined. The notion of weighted misses is used to provide some meaningful interpretations of the miss ratios associated with workload partitioning.>

Parallel execution of nonvectorizable uniform recurrences is considered. When naively scheduled, such recurrences could create unacceptable communication and synchronization on a multiprocessor. The minimum-distance method partitions such recurrences into totally independent computations without increasing redundancy or perturbing numerical stability. The independent computations are well suited for execution on a multiprocessor, but they may not utilize all available processors. How extra processors can be applied to the independent computations is addressed. The methods are especially attractive for multiprocessors comprised of clusters.>