Accurate branch predictors require multiple cycles to produce a prediction, and that latency hurts processor performance."Ahead prediction" solves the performance problem by starting the prediction early.Unfortunately, this means making the prediction without the directions of the N branches between when the prediction starts and when the relevant branch's prediction is needed.The energy required to consider all 2 𝑛 possible cases increases by 14.6x, making ahead prediction not viable.This paper shows that most of the intermediate branch directions never materialize, reducing the number of observed missing history patterns significantly (usually, only one or two).We modified the TAGE predictor to eliminate those branches from having to be considered.The result, our ahead predictor can produce a performance benefit of 4.4%, while causing an increase in energy consumption of only 1.5x, far less than the 14.6x that was thought to be necessary, and very much viable.

Modern out-of-order cores rely on a large instruction supply from the processor frontend to achieve high performance. This requires building wider pipelines with more accurate branch predictors. However, scaling the pipeline width is becoming more challenging due to limitations on the number of instructions that can be renamed and branches that can be predicted in a single cycle. Moreover, mispredictions reduce the useful fetch bandwidth that can be extracted from a wider frontend. Our work, Alternate Path Fetch (APF), effectively uses a wide frontend by dividing the pipeline into two parallel sections. One processes regular instructions, and the other uses a separate pipeline to Branch Predict, Fetch, Decode, and partially Rename instructions on the alternate path of hard-to-predict (H2P) branches. The pipelines operate simultaneously using a Parallel Fetch scheme we developed. This allows APF to more efficiently utilize the bandwidth of a wider frontend without the overhead associated with building a monolithic, wider pipeline. APF improves performance by reducing the pipeline re-fill delay on branch mispredictions. Unlike other solutions that fully rename and execute instructions on both sides of a branch, we show that stopping after partial Renaming on the alternate path provides better performance through improved coverage and avoids the complexity associated with further processing. APF provides a $5 \%$ geomean speedup over an aggressive 8 -wide out-of-order core.

Out-of-order cores rely on high-accuracy branch predictors to supply useful instructions to the processor backend. However, there remains a large fraction of mispredictions caused by hard-to-predict (H2P) branches that modern predictors have been unable to improve. Precomputation is an alternative to prediction that speculatively executes the dependence chain of a branch earlier to override the branch predictor at Fetch time. However, prior work sacrifices H2P branch coverage and precomputation accuracy to produce timely results. Our work relaxes this timeliness constraint by using precomputation results to issue early misprediction flushes instead of overriding the branch predictor. This allows us to construct a highly accurate precomputation thread with good misprediction coverage, without sacrificing timeliness. The thread is efficient as it utilizes on-core execution resources and re-uses existing hardware for issuing early flushes. Using our Timely, Efficient, and Accurate thread for precomputation yields a 10.1% improvement in performance over an aggressive baseline OoO core.

Row-Hammer (RH) is a DRAM data-disturbance failure that occurs when a row is activated frequently, which causes bit-flips in nearby rows. Row-Hammer is a significant security threat as an attacker can exploit the bit-flips to do privilege escalation and leak confidential data. While several solutions aim to mitigate RH, such solutions depend on the RH threshold and adversarial access patterns. Solutions developed for a given threshold become ineffective for newer devices with lower thresholds, and new attack patterns continue to break existing mitigations. Currently, there is no guaranteed solution for RH, which means that the system remains vulnerable to security threats even in the presence of RH mitigation.In this paper, we contend that simply relying on RH mitigation is insufficient to provide security in the presence of reducing threshold and motivated attackers. We propose SafeGuard, which equips the system with low-cost integrity protection as a defense against potential attacks that break the RH mitigation. As SafeGuard can detect arbitrary failures, it converts the problem of RH bit-flips from a security threat (silent consumption of corrupted data) to a reliability concern (detectable uncorrectable errors caused by integrity violation). We develop SafeGuard for systems that employ ECC modules and show that SafeGuard can provide strong detection to both SECDED (46-bit MAC per cache-line) and Chipkill (32-bit MAC per cache-line) while retaining the correction capability of conventional designs. SafeGuard avoids incurring any storage overheads in DRAM by simply reorganizing the ECC code to operate at a cache-line granularity (64 bytes) instead of a word granularity (8 bytes). Our evaluations show that SafeGuard has a negligible impact on both the system performance (0.7%) and the system reliability due to naturally occurring errors while still providing a strong defense against the security risk of RH by detecting arbitrary bit-flips.

Modern OoO cores achieve high levels of performance using large instruction windows. Scaling the window size improves performance by making visible more of the parallelism present in programs. However, this leads to an exponential increase in area and power. We specify Criticality Driven Fetch (CDF), a new execution paradigm that preferentially fetches, allocates, and executes instructions on the critical path of the program. By skipping over non-critical instructions, critical instructions in the ROB can span a sequential instruction window larger than the size of the ROB. This increases the amount of parallelism that can be extracted from critical instructions, thereby improving performance.

High performance microprocessors require high levels of instruction supply. Branch prediction has been the most important driver of this for nearly 30 years. Unfortunately, modern predictors are increasingly bottlenecked by hard-to-predict data-dependent branches that fundamentally cannot be predicted via a history based approach. Pre-computation of branch instructions has been suggested as a solution, but such schemes require a careful trade-off between timeliness and complexity. This paper introduces Branch Runahead: a low-cost, hardware-only solution that achieves high accuracy while only performing lightweight pre-computation. The result: a reduction in branch MPKI of 47.5% and an average improvement in IPC of 16.9%.

Main memory capacity continues to soar, resulting in TLB misses becoming an increasingly significant performance bottleneck. Current coarse grained page sizes, the solution from Intel, ARM, and others, have not helped enough. We propose Tailored Page Sizes (TPS), a mechanism that allows pages of size 2n, for all n greater than a default minimum. For x86, the default minimum page size is 212(4KB). TPS means one page table entry (PTE) for each large contiguous virtual memory space mapped to an equivalent-sized large contiguous physical frame. To make this work in a clean, seamless way, we suggest small changes to the ISA, the microarchitecture, and the O/S allocation operation. The result: TPS can eliminate approximately 98% of page walk memory accesses and 97% of all L1 TLB misses across a variety of SPEC17 and big data memory intensive benchmarks.

The state-of-the-art branch predictor, TAGE, remains inefficient at identifying correlated branches deep in a noisy global branch history. We argue this inefficiency is a fundamental limitation of runtime branch prediction and not a coincidental artifact due to the design of TAGE. To further improve branch prediction, we need to relax the constraint of runtime only training and adopt more sophisticated prediction mechanisms. To this end, Tarsa et al. proposed using convolutional neural networks (CNNs) that are trained at compile-time to accurately predict branches that TAGE cannot. Given enough profiling coverage, CNNs learn input-independent branch correlations that can accurately predict branches when running a program with unseen inputs. We build on their work and introduce BranchNet, a CNN with a practical on-chip inference engine tailored to the needs of branch prediction. At runtime, BranchNet predicts a few hard-to-predict branches, while TAGE-SC-L predicts the remaining branches. This hybrid approach reduces the MPKI of SPEC2017 Integer benchmarks by 7.6% (and up to 15.7%) when compared to a very large (impractical) MTAGE-SC baseline, demonstrating a fundamental advantage in the prediction capabilities of BranchNet compared to TAGE-like predictors. We also propose a practical resource-constrained variant of BranchNet that improves the MPKI by 9.6% (and up to 17.7%) compared to a 64KB TAGE-SC-L without increasing the prediction latency.

Bank and bank group conflicts are major performance bottlenecks for memory intensive workloads. Idealized experiments show removing bank and bank group conflicts collectively can improve performance by up to 37.5% and by 22.5% on average for our mix of multi-programmed memory intensive workloads. We propose the Duplicon Cache to mitigate bank and bank group conflict penalties by duplicating select lines of data to an alternative bank group, giving the memory controller the freedom to source the data from the bank group which avoids conflicts. The Duplicon Cache is entirely implemented in the memory controller and does not require changes to commodity memory. We identify and address the main challenges associated with duplication: 1) tracking duplicated data efficiently, 2) identifying which data to duplicate, and 3) replacing stale duplicated data while protecting useful ones. Our evaluations show the Duplicon Cache configured with 128MB of storage (out of 16GB of main memory) improves performance by 8.3% while reducing energy by 5.6%.

We have been riding a strong wave of greater and greater performance for decades, to some extent due to the combination of Moore's Law and Dennard scaling. But we are told all this is coming to an end, in part because we can not continue to double the transistor count on the chip and we can not run these things at higher and higher frequencies. Much of the silliness promised by multicore is just that, and not the answer. So, what are we to do? It turns out predication gave us the answer more than 30 years ago. Most of us were not paying attention. Today we have no choice. Predication happened because the compiler, the ISA, and the microarchitecture all cooperated so it could happen. That meant breaking the artificial walls in the transformation hierarchy. If we accept this as something we have to do, there are plenty of opportunities (a) for increased performance (attacking latency instead of just multicore bandwidth) and (b) for better energy efficiency. In this talk I hope to point out some of them, and then ask the obvious question: What do we need to do to make this happen?

On-chip contention increases memory access latency for multi-core processors. We identify that this additional latency has a substantial effect on performance for an important class of latency-critical memory operations: those that result in a cache miss and are dependent on data from a prior cache miss. We observe that the number of instructions between the first cache miss and its dependent cache miss is usually small. To minimize dependent cache miss latency, we propose adding just enough functionality to dynamically identify these instructions at the core and migrate them to the memory controller for execution as soon as source data arrives from DRAM. This migration allows memory requests issued by our new Enhanced Memory Controller (EMC) to experience a 20% lower latency than if issued by the core. On a set of memory intensive quad-core workloads, the EMC results in a 13% improvement in system performance and a 5% reduction in energy consumption over a system with a Global History Buffer prefetcher, the highest performing prefetcher in our evaluation.

Runahead execution pre-executes the application's own code to generate new cache misses. This pre-execution results in prefetch requests that are overwhelmingly accurate (95% in a realistic system configuration for the memory intensive SPEC CPU2006 benchmarks), much more so than a global history buffer (GHB) or stream prefetcher (by 13%/19%). However, we also find that current runahead techniques are very limited in coverage: they prefetch only a small fraction (13%) of all runahead-reachable cache misses. This is because runahead intervals are short and limited by the duration of each full-window stall. In this work, we explore removing the constraints that lead to these short intervals. We dynamically filter the instruction stream to identify the chains of operations that cause the pipeline to stall. These operations are renamed to execute speculatively in a loop and are then migrated to a Continuous Runahead Engine (CRE), a shared multi-core accelerator located at the memory controller. The CRE runs ahead with the chain continuously, increasing prefetch coverage to 70% of runahead-reachable cache misses. The result is a 43.3% weighted speedup gain on a set of memory intensive quad-core workloads and a significant reduction in system energy consumption. This is a 21.9% performance gain over the Runahead Buffer, a state-of-the-art runahead proposal and a 13.2%/13.5% gain over GHB/stream prefetching. When the CRE is combined with GHB prefetching, we observe a 23.5% gain over a baseline with GHB prefetching alone.

Runahead execution dynamically expands the instruction window of an out of order processor to generate memory level parallelism (MLP) while the core would otherwise be stalled. Unfortunately, runahead has the disadvantage of requiring the front-end to remain active to supply instructions. We propose a new structure (the Runahead Buffer) for supplying these instructions. We note that cache misses are often caused by repetitive, short dependence chains. We store these dependence chains in the runahead buffer. During runahead, the runahead buffer is used to supply instructions. This generates 2x more MLP than traditional runahead on average because the core can run further ahead. It also saves energy since the front-end can be clock-gated, reducing dynamic energy consumption. Over a no-prefetching/prefetching baseline, the result is a performance benefit of 17.2%/7.8% and an energy reduction of 6.7%/4.5% respectively. Traditional runahead with additional energy optimizations results in a performance benefit of 12.1%/5.9% but an energy increase of 9.5%/5.4%. Finally, we propose a hybrid policy that switches between the runahead buffer and traditional runahead, maximizing performance.

Asymmetric Chip Multiprocessors (ACMPs) are becoming a reality. ACMPs can speed up parallel applications if they can identify and accelerate code segments that are critical for performance. Proposals already exist for using coarse-grained thread scheduling and fine-grained bottleneck acceleration. Unfortunately, there have been no proposals offered thus far to decide which code segments to accelerate in cases where both coarse-grained thread scheduling and fine-grained bottleneck acceleration could have value. This paper proposes Utility-Based Acceleration of Multithreaded Applications on Asymmetric CMPs (UBA), a cooperative software/hardware mechanism for identifying and accelerating the most likely critical code segments from a set of multithreaded applications running on an ACMP. The key idea is a new Utility of Acceleration metric that quantifies the performance benefit of accelerating a bottleneck or a thread by taking into account both the criticality and the expected speedup. UBA outperforms the best of two state-of-the-art mechanisms by 11% for single application workloads and by 7% for two-application workloads on an ACMP with 52 small cores and 3 large cores.

The semiconductor industry has largely gotten off the Moore's law treadmill. Many companies have stopped scaling, realizing that the 65, 45 or 32nm are sufficient for their needs, and relying on foundries to shoulder the risk and capital requirements for advanced nodes. This has resulted in a reduced need for VLSI-oriented research as the industry consolidates and traditional funding sources ramp down. So what does a VLSI researcher do then? Well she or he finds interesting problems to solve in so-called "adjacent" areas. But how does one get started, and how does one find such interesting research areas? This keynote is about two such examples… from VLSI to Proton Radiation Therapy and to Energy Distribution Optimization. It turns out that there are abundant opportunities for those willing to take risks and learn new things. Humanity has invested over $1T in semiconductor R&D, it is time to take that investment and apply its results more broadly!

Performance of multithreaded applications is limited by a variety of bottlenecks, e.g. critical sections, barriers and slow pipeline stages. These bottlenecks serialize execution, waste valuable execution cycles, and limit scalability of applications. This paper proposes Bottleneck Identification and Scheduling in Multithreaded Applications (BIS), a cooperative software-hardware mechanism to identify and accelerate the most critical bottlenecks. BIS identifies which bottlenecks are likely to reduce performance by measuring the number of cycles threads have to wait for each bottleneck, and accelerates those bottlenecks using one or more fast cores on an Asymmetric Chip Multi-Processor (ACMP). Unlike previous work that targets specific bottlenecks, BIS can identify and accelerate bottlenecks regardless of their type. We compare BIS to four previous approaches and show that it outperforms the best of them by 15% on average. BIS' performance improvement increases as the number of cores and the number of fast cores in the system increase.

No abstract available.

Several researchers have recognized in recent years that today's workloads require a micro architecture that can handle single-threaded code at high performance, and multi-threaded code at high throughput, while consuming no more energy than is necessary. This paper proposes Morph Core, a unique approach to satisfying these competing requirements, by starting with a traditional high performance out-of-order core and making minimal changes that can transform it into a highly-threaded in-order SMT core when necessary. The result is a micro architecture that outperforms an aggressive 4-way SMT out-of-order core, "medium" out-of-order cores, small in-order cores, and Core Fusion. Compared to a 2-way SMT out-of-order core, Morph Core increases performance by 10% and reduces energy-delay-squared product by 22%.

Dynamic voltage and frequency scaling (DVFS) can make modern processors more power and energy efficient if we can accurately predict the effect of frequency scaling on processor performance. State-of-the-art DVFS performance predictors, however, fail to accurately predict performance when confronted with realistic memory systems. We propose CRIT+BW, the first DVFS performance predictor designed for realistic memory systems. In particular, CRIT+BW takes into account both variable memory access latency and performance effects of prefetching. When evaluated with a realistic memory system, DVFS realizes 65% of potential energy savings when using CRIT+BW, compared to less than 34% when using previously proposed DVFS performance predictors.

Cache memories have traditionally been designed to exploit spatial locality by fetching entire cache lines from memory upon a miss. However, recent studies have shown that often the number of sub-blocks within a line that are actually used is low. Furthermore, those sub-blocks that are used are accessed only a few times before becoming dead (i.e., never accessed again). This results in considerable energy waste since 1) data not needed by the processor is brought into the cache, and 2) data is kept alive in the cache longer than necessary. We propose the Dead Sub-Block Predictor (DSBP) to predict which sub-blocks of a cache line will be actually used and how many times it will be used in order to bring into the cache only those sub-blocks that are necessary, and power them off after they are touched the predicted number of times. We also use DSBP to identify dead lines (i.e., all sub-blocks off) and augment the existing replacement policy by prioritizing dead lines for eviction. Our results show a 24% energy reduction for the whole cache hierarchy when averaged over the SPEC2000, SPEC2006 and NAS-NPB benchmarks.

Cores in chip-multiprocessors (CMPs) share multiple memory subsystem resources. If resource sharing is unfair, some applications can be delayed significantly while others are unfairly prioritized. Previous research proposed separate fairness mechanisms for each resource. Such resource-based fairness mechanisms implemented independently in each resource can make contradictory decisions, leading to low fairness and performance loss. Therefore, a coordinated mechanism that provides fairness in the entire shared memory system is desirable. This article proposes a new approach that provides fairness in the entire shared memory system, thereby eliminating the need for and complexity of developing fairness mechanisms for each resource. Our technique, Fairness via Source Throttling (FST), estimates unfairness in the entire memory system . If unfairness is above a system-software-set threshold, FST throttles down cores causing unfairness by limiting the number of requests they create and the frequency at which they do. As such, our source-based fairness control ensures fairness decisions are made in tandem in the entire memory system. FST enforces thread priorities/weights, and enables system-software to enforce different fairness objectives in the memory system. Our evaluations show that FST provides the best system fairness and performance compared to three systems with state-of-the-art fairness mechanisms implemented in both shared caches and memory controllers.

Chip multiprocessors (CMPs) share a large portion of the memory subsystem among multiple cores. Recent proposals have addressed high-performance and fair management of these shared resources; however, none of them take into account prefetch requests. Without prefetching, significant performance is lost, which is why existing systems prefetch. By not taking into account prefetch requests, recent shared-resource management proposals often significantly degrade both performance and fairness, rather than improve them in the presence of prefetching.

A primary use of chip-multiprocessor (CMP) systems is to speed up a single application by exploiting thread-level parallelism. In such systems, threads may slow each other down by issuing memory requests that interfere in the shared memory subsystem. This inter-thread memory system interference can significantly degrade parallel application performance. Better memory request scheduling may mitigate such performance degradation. However, previously proposed memory scheduling algorithms for CMPs are designed for multi-programmed workloads where each core runs an independent application, and thus do not take into account the inter-dependent nature of threads in a parallel application.

Due to their massive computational power, graphics processing units (GPUs) have become a popular platform for executing general purpose parallel applications. GPU programming models allow the programmer to create thousands of threads, each executing the same computing kernel. GPUs exploit this parallelism in two ways. First, threads are grouped into fixed-size SIMD batches known as warps, and second, many such warps are concurrently executed on a single GPU core. Despite these techniques, the computational resources on GPU cores are still underutilized, resulting in performance far short of what could be delivered. Two reasons for this are conditional branch instructions and stalls due to long latency operations.

Existing DRAM controllers employ rigid, nonadaptive scheduling and buffer management policies when servicing prefetch requests. Some controllers treat prefetches the same as demand requests, and others always prioritize demands over prefetches. However, none of these rigid policies result in the best performance because they do not take into account the usefulness of prefetches. If prefetches are useless, treating prefetches and demands equally can lead to significant performance loss and extra bandwidth consumption. In contrast, if prefetches are useful, prioritizing demands over prefetches can hurt performance by reducing DRAM throughput and delaying the service of useful requests. This paper proposes a new low hardware cost memory controller, called as Prefetch-Aware DRAM Controller (PADC), that aims to maximize the benefit of useful prefetches and minimize the harm caused by useless prefetches. The key idea is to 1) adaptively prioritize between demands and prefetches, and 2) drop useless prefetches to free up memory system resources, based on prefetch accuracy. Our evaluation shows that PADC significantly outperforms previous memory controllers with rigid prefetch handling policies. Across a wide range of multiprogrammed SPEC CPU 2000/2006 workloads, it improves system performance by 8.2 and 9.9 percent on four and eight-core systems while reducing DRAM bandwidth consumption by 10.7 and 9.4 percent, respectively.

Extracting high performance from Chip Multiprocessors requires that the application be parallelized. A common software technique to parallelize loops is pipeline parallelism in which the programmer/compiler splits each loop iteration into stages and each stage runs on a certain number of cores. It is important to choose the number of cores for each stage carefully because the core-to-stage allocation determines performance and power consumption. Finding the best core-to-stage allocation for an application is challenging because the number of possible allocations is large, and the best allocation depends on the input set and machine configuration.

Cores in a chip-multiprocessor (CMP) system share multiple hardware resources in the memory subsystem. If resource sharing is unfair, some applications can be delayed significantly while others are unfairly prioritized. Previous research proposed separate fairness mechanisms in each individual resource. Such resource-based fairness mechanisms implemented independently in each resource can make contradictory decisions, leading to low fairness and loss of performance. Therefore, a coordinated mechanism that provides fairness in the entire shared memory system is desirable.

Previous research has shown that Staged Execution (SE), i.e., dividing a program into segments and executing each segment at the core that has the data and/or functionality to best run that segment, can improve performance and save power. However, SE's benefit is limited because most segments access inter-segment data, i.e., data generated by the previous segment. When consecutive segments run on different cores, accesses to inter-segment data incur cache misses, thereby reducing performance. This paper proposes Data Marshaling (DM), a new technique to eliminate cache misses to inter-segment data. DM uses profiling to identify instructions that generate inter-segment data, and adds only 96 bytes/core of storage overhead. We show that DM significantly improves the performance of two promising Staged Execution models, Accelerated Critical Sections and producer-consumer pipeline parallelism, on both homogeneous and heterogeneous multi-core systems. In both models, DM can achieve almost all of the potential of ideally eliminating cache misses to inter-segment data. DM's performance benefit increases with the number of cores.

To improve the performance of a single application on Chip Multiprocessors (CMPs), the application must be split into threads which execute concurrently on multiple cores. In multi-threaded applications, critical sections are used to ensure that only one thread accesses shared data at any given time. Critical sections can serialize the execution of threads, which significantly reduces performance and scalability.

Linked data structure (LDS) accesses are critical to the performance of many large scale applications. Techniques have been proposed to prefetch such accesses. Unfortunately, many LDS prefetching techniques 1) generate a large number of useless prefetches, thereby degrading performance and bandwidth efficiency, 2) require significant hardware or storage cost, or 3) when employed together with stream-based prefetchers, cause significant resource contention in the memory system. As a result, existing processors do not employ LDS prefetchers even though they commonly employ stream-based prefetchers. This paper proposes a low-cost hardware/software cooperative technique that enables bandwidth-efficient prefetching of linked data structures. Our solution has two new components: 1) a compiler-guided prefetch filtering mechanism that informs the hardware about which pointer addresses to prefetch, 2) a coordinated prefetcher throttling mechanism that uses run-time feedback to manage the interference between multiple prefetchers (LDS and stream-based) in a hybrid prefetching system. Evaluations show that the proposed solution improves average performance by 22.5% while decreasing memory bandwidth consumption by 25% over a baseline system that employs an effective stream prefetcher on a set of memory- and pointer-intensive applications. We compare our proposal to three different LDS/correlation prefetching techniques and find that it provides significantly better performance on both single-core and multi-core systems, while requiring less hardware cost.

The challenge for the microarchitect has always been (with very few notable domain-specific exceptions) how to translate the continually increasing processing power provided by Moore's Law into increased performance, or more recently into similar performance at lower cost in energy. The mechanisms in the past (almost entirely) kept the interface intact and used the increase in transistor count to improve the performance of the microarchitecture of the uniprocessor. When that became too hard, we went to larger and larger on-chip caches. Both are consistent with the notion that ldquoabstractions are good.rdquo At some point, we got overwhelmed with too many transistors; predictably, multi-core was born. As the transistor count continues to skyrocket, we are faced with two questions: what should be on the chip, and how should the software interface to it. If we expect to continue to take advantage of what process technology is providing, I think we need to do several things, starting with rethinking the notion of abstraction and providing multiple interfaces for the programmer.

Languages featuring automatic memory management (garbage collection) are increasingly used to write all kinds of applications because they provide clear software engineering and security advantages. Unfortunately, garbage collection imposes a toll on performance and introduces pause times, making such languages less attractive for high-performance or real-time applications. Much progress has been made over the last five decades to reduce the overhead of garbage collection, but it remains significant.

Aggressive prefetching is very beneficial for memory latency tolerance of many applications. However, it faces significant challenges in multi-core systems. Prefetchers of different cores on a chip multiprocessor (CMP) can cause significant interference with prefetch and demand accesses of other cores. Because existing prefetcher throttling techniques do not address this prefetcher-caused inter-core interference, aggressive prefetching in multi-core systems can lead to significant performance degradation and wasted bandwidth consumption.

DRAM systems achieve high performance when all DRAM banks are busy servicing useful memory requests. The degree to which DRAM banks are busy is called DRAM Bank-Level Parallelism (BLP). This paper proposes two new cost-effective mechanisms to maximize DRAM BLP. BLP-Aware Prefetch Issue (BAPI) issues prefetches into the on-chip Miss Status Holding Registers (MSHRs) associated with each core in a multi-core system such that the requests can be serviced in parallel in different DRAM banks. BLP-Preserving Multi-core Request Issue (BPMRI) does the actual loading of the DRAM controller's request buffers so that requests from the same core can be serviced in parallel, minimizing the serialization of each core's concurrent requests. When combined, BAPI and BPMRI improve system performance by 11.7% on a 4-core CMP system for a wide variety of multiprogrammed workloads. BAPI and BPMRI also complement various existing DRAM scheduling and prefetching algorithms, and can be used in conjunction with them.

The challenge for the microarchitect has always been (with very few notable domain-specific exceptions) how to translate the continually increasing processing power provided by Moore's Law into increased performance, or more recently into similar performance at lower cost in energy. The mechanisms in the past (almost entirely) kept the interface intact and used the increase in transistor count to improve the performance of the microarchitecture of the uniprocessor. When that became too hard, we went to larger and larger on-chip caches. Both are consistent with the notion that abstractions are good. At some point, we got overwhelmed with too many transistors; predictably, multi-core was born. As the transistor count continues to skyrocket, we are faced with two questions: what should be on the chip, and how should the software interface to it. If we expect to continue to take advantage of what process technology is providing, I think we need to do several things, starting with rethinking the notion of abstraction and providing multiple interfaces for the programmer.

Indirect branches have become increasingly common in modular programs written in modern object-oriented languages and virtual-machine-based runtime systems. Unfortunately, the prediction accuracy of indirect branches has not improved as much as that of conditional branches. Furthermore, previously proposed indirect branch predictors usually require a significant amount of extra hardware storage and complexity, which makes them less attractive to implement. This paper proposes a new technique for handling indirect branches, called Virtual Program Counter (VPC) prediction. The key idea of VPC prediction is to use the existing conditional branch prediction hardware to predict indirect branch targets, avoiding the need for a separate storage structure. Our comprehensive evaluation shows that VPC prediction improves average performance by 26.7 percent and reduces average energy consumption by 19 percent compared to a commonly used branch target buffer based predictor on 12 indirect branch intensive C/C++ applications. Moreover, VPC prediction improves the average performance of the full set of object-oriented Java DaCapo applications by 21.9 percent, while reducing their average energy consumption by 22 percent. We show that VPC prediction can be used with any existing conditional branch prediction mechanism and that the accuracy of VPC prediction improves when a more accurate conditional branch predictor is used.

Indirect jump instructions are used to implement increasingly-common programming constructs such as virtual function calls, switch-case statements, jump tables, and interface calls. The performance impact of indirect jumps is likely to increase because indirect jumps with multiple targets are difficult to predict even with specialized hardware.

Extracting high-performance from the emerging Chip Multiprocessors (CMPs) requires that the application be divided into multiple threads. Each thread executes on a separate core thereby increasing concurrency and improving performance. As the number of cores on a CMP continues to increase, the performance of some multi-threaded applications will benefit from the increased number of threads, whereas, the performance of other multi-threaded applications will become limited by data-synchronization and off-chip bandwidth. For applications that get limited by data-synchronization, increasing the number of threads significantly degrades performance and increases on-chip power. Similarly, for applications that get limited by off-chip bandwidth, increasing the number of threads increases on-chip power without providing any performance improvement. Furthermore, whether an application gets limited by data-synchronization, or bandwidth, or neither depends not only on the application but also on the input set and the machine configuration. Therefore, controlling the number of threads based on the run-time behavior of the application can significantly improve performance and reduce power.

Fetch gating mechanisms have been proposed to gate the processor pipeline to reduce the wasted energy consumption due to wrong-path (i.e. mis-speculated) instructions. These schemes assume that all wrong-path instructions are useless for processor performance and try to eliminate the execution of all wrong-path instructions. However, wrong-path memory references can be useful for performance by providing prefetching benefits for later correct-path operations. Therefore, eliminating wrong-path instructions without considering the usefulness of wrong-path execution can significantly reduce performance as well as increase overall energy consumption. This paper proposes a comprehensive, low-cost speculation control mechanism that takes into account the usefulness of wrong-path execution, while effectively reducing the energy consumption due to useless wrong-path instructions. One component of the mechanism is a simple, novel wrong-path usefulness predictor (WPUP) that can accurately predict whether or not wrong-path execution will be beneficial for performance. The other component is a novel branch-count based fetch gating scheme that requires very little hardware cost to detect if the processor is on the wrong path. The key idea of our speculation control mechanism is to gate the processor pipeline only if (1) the number of outstanding branches is above a dynamically-determined threshold and (2) the WPUP predicts that wrong-path execution will not be beneficial for performance. Our results show that our proposal eliminates most of the performance loss incurred by fetch gating mechanisms that assume wrong-path execution is useless, thereby both improving performance and reducing energy consumption while requiring very little (51- byte) hardware cost.

There is still much performance to be gained by out-of-order processors with wider issue widths. However, traditional methods of increasing issue width do not scale; that is, they drastically increase design complexity and power requirements. This paper introduces the braid, a compile-time identified entity that enables the execution core to scale to wider widths by exploiting the small fanout and short lifetime of values produced by the program. Braid processing requires identification by the compiler, minor extensions to the ISA, and support by the microarchitecture. The result from processing braids is performance within 9% of a very aggressive conventional out-of-order microarchitecture with almost the complexity of an in-order implementation.

Existing DRAM controllers employ rigid, non-adaptive scheduling and buffer management policies when servicing prefetch requests. Some controllers treat prefetch requests the same as demand requests, others always prioritize demand requests over prefetch requests. However, none of these rigid policies result in the best performance because they do not take into account the usefulness of prefetch requests. If prefetch requests are useless, treating prefetches and demands equally can lead to significant performance loss and extra bandwidth consumption. In contrast, if prefetch requests are useful, prioritizing demands over prefetches can hurt performance by reducing DRAM throughput and delaying the service of useful requests. This paper proposes a new low-cost memory controller, called Prefetch-Aware DRAM Controller (PADC), that aims to maximize the benefit of useful prefetches and minimize the harm caused by useless prefetches. To accomplish this, PADC estimates the usefulness of prefetch requests and dynamically adapts its scheduling and buffer management policies based on the estimates. The key idea is to 1) adaptively prioritize between demand and prefetch requests, and 2) drop useless prefetches to free up memory system resources, based on the accuracy of the prefetcher. Our evaluation shows that PADC significantly outperforms previous memory controllers with rigid prefetch handling policies on both single- and multi-core systems with a variety of prefetching algorithms. Across a wide range of multiprogrammed SPEC CPU 2000/2006 workloads, it improves system performance by 8.2%on a 4-core system and by 9.9%on an 8-core system while reducing DRAM bandwidth consumption by 10.7% and 9.4% respectively.

Dynamic predication has been proposed to reduce the branch misprediction penalty due to hard-to-predict branch instructions. A proposed dynamic predication architecture, the diverge-merge processor (DMP), provides large performance improvements by dynamically predicating a large set of complex control-flow graphs that result in branch mispredictions. DMP requires significant support from a profiling compiler to determine which branch instructions and control-flow structures can be dynamically predicated. However, previous work on dynamic predication did not extensively examine the tradeoffs involved in profiling and code generation for dynamic predication architectures. This paper describes compiler support for obtaining high performance in the diverge-merge processor. We describe new profile-driven algorithms and heuristics to select branch instructions that are suitable and profitable for dynamic predication. We also develop a new profile-based analytical cost-benefit model to estimate, at compile-time, the performance benefits of the dynamic predication of different types of control-flow structures including complex hammocks and loops. Our evaluations show that DMP can provide 20.4% average performance improvement over a conventional processor on SPEC integer benchmarks with our optimized compiler algorithms, whereas the average performance improvement of the best-performing alternative simple compiler algorithm is 4.5%. We also find that, with the proposed algorithms, DMP performance is not significantly affected by the differences in profile- and run-time input data sets

Caches are organized at a line-size granularity to exploit spatial locality. However, when spatial locality is low, many words in the cache line are not used. Unused words occupy cache space but do not contribute to cache hits. Filtering these words can allow the cache to store more cache lines. We show that unused words in a cache line are unlikely to be accessed in the less recent part of the LRU stack. We propose line distillation (LDIS), a technique that retains only the used words and evicts the unused words in a cache line. We also propose distill cache, a cache organization to utilize the capacity created by LDIS. Our experiments with 16 memory-intensive benchmarks show that LDIS reduces the average misses for a 1MB 8-way L2 cache by 30% and improves the average IPC by 12%

High performance processors employ hardware data prefetching to reduce the negative performance impact of large main memory latencies. While prefetching improves performance substantially on many programs, it can significantly reduce performance on others. Also, prefetching can significantly increase memory bandwidth requirements. This paper proposes a mechanism that incorporates dynamic feedback into the design of the prefetcher to increase the performance improvement provided by prefetching as well as to reduce the negative performance and bandwidth impact of prefetching. Our mechanism estimates prefetcher accuracy, prefetcher timeliness, and prefetcher-caused cache pollution to adjust the aggressiveness of the data prefetcher dynamically. We introduce a new method to track cache pollution caused by the prefetcher at run-time. We also introduce a mechanism that dynamically decides where in the LRU stack to insert the prefetched blocks in the cache based on the cache pollution caused by the prefetcher. Using the proposed dynamic mechanism improves average performance by 6.5% on 17 memory-intensive benchmarks in the SPEC CPU2000 suite compared to the best-performing conventional stream-based data prefetcher configuration, while it consumes 18.7% less memory bandwidth. Compared to a conventional stream-based data prefetcher configuration that consumes similar amount of memory bandwidth, feedback directed prefetching provides 13.6% higher performance. Our results show that feedback-directed prefetching eliminates the large negative performance impact incurred on some benchmarks due to prefetching, and it is applicable to stream-based prefetchers, global-history-buffer based delta correlation prefetchers, and PC-based stride prefetchers

Indirect branches have become increasingly common in modular programs written in modern object-oriented languages and virtual machine based runtime systems. Unfortunately, the prediction accuracy of indirect branches has not improved as much as that of conditional branches. Furthermore, previously proposed indirect branch predictors usually require a significant amount of extra hardware storage and complexity, which makes them less attractive to implement.

The commonly used LRU replacement policy is susceptible to thrashing for memory-intensive workloads that have a working set greater than the available cache size. For such applications, the majority of lines traverse from the MRU position to the LRU position without receiving any cache hits, resulting in inefficient use of cache space. Cache performance can be improved if some fraction of the working set is retained in the cache so that at least that fraction of the working set can contribute to cache hits. We show that simple changes to the insertion policy can significantly reduce cache misses for memory-intensive workloads. We propose the LRU Insertion Policy (LIP) which places the incoming line in the LRU position instead of the MRU position. LIP protects the cache from thrashing and results in close to optimal hitrate for applications that have a cyclic reference pattern. We also propose the Bimodal Insertion Policy (BIP) as an enhancement of LIP that adapts to changes in the working set while maintaining the thrashing protection of LIP. We finally propose a Dynamic Insertion Policy (DIP) to choose between BIP and the traditional LRU policy depending on which policy incurs fewer misses. The proposed insertion policies do not require any change to the existing cache structure, are trivial to implement, and have a storage requirement of less than two bytes. We show that DIP reduces the average MPKI of the baseline 1MB 16-way L2 cache by 21%, bridging two-thirds of the gap between LRU and OPT.

Static compilers use profiling to predict run-time program behavior. Generally, this requires multiple input sets to capture wide variations in run-time behavior. This is expensive in terms of resources and compilation time. We introduce a new mechanism, 2D-profiling, which profiles with only one input set and predicts whether the result of the profile would change significantly across multiple input sets. We use 2D-profiling to predict whether a branch's prediction accuracy varies across input sets. The key insight is that if the prediction accuracy of an individual branch varies significantly over a profiling run with one input set, then it is more likely that the prediction accuracy of that branch varies across input sets. We evaluate 2D-profiling with the SPEC CPU 2000 integer benchmarks and show that it can identify input-dependent branches accurately.

The document was not made available for publication as part of the conference proceedings.

Performance loss due to long-latency memory accesses can be reduced by servicing multiple memory accesses concurrently. The notion of generating and servicing long-latency cache misses in parallel is called Memory Level Parallelism (MLP). MLP is not uniform across cache misses - some misses occur in isolation while some occur in parallel with other misses. Isolated misses are more costly on performance than parallel misses. However, traditional cache replacement is not aware of the MLP-dependent cost differential between different misses. Cache replacement, if made MLP-aware, can improve performance by reducing the number of performance-critical isolated misses. This paper makes two key contributions. First, it proposes a framework for MLP-aware cache replacement by using a runtime technique to compute the MLP-based cost for each cache miss. It then describes a simple cache replacement mechanism that takes both MLP-based cost and recency into account. Second, it proposes a novel, low-hardware overhead mechanism called Sampling Based Adaptive Replacement (SBAR), to dynamically choose between an MLP-aware and a traditional replacement policy, depending on which one is more effective at reducing the number of memory related stalls. Evaluations with the SPEC CPU2000 benchmarks show that MLP-aware cache replacement can improve performance by as much as 23%.

This paper proposes a new processor architecture for handling hard-to-predict branches, the diverge-merge processor (DMP). The goal of this paradigm is to eliminate branch mispredictions due to hard-to-predict dynamic branches by dynamically predicating them without requiring ISA support for predicate registers and predicated instructions. To achieve this without incurring large hardware cost and complexity, the compiler provides control-flow information by hints and the processor dynamically predicates instructions only on frequently executed program paths. The key insight behind DMP is that most control-flow graphs look and behave like simple hammock (if-else) structures when only frequently executed paths in the graphs are considered. Therefore, DMP can dynamically predicate a much larger set of branches than simple hammock branches. Our evaluations show that DMP out performs a baseline processor with an aggressive branch predictor by 19.3% on average over SPEC integer 95 and 2000 benchmarks, through a reduction of 38% in pipeline flushes due to branch mispredictions, while consuming 9.0% less energy. We also compare DMP with previously proposed predication and dual-path/multipath execution paradigms in terms of performance, complexity, and energy consumption, and find that DMP is the highest performance and also the most energy-efficient design

This paper investigates the problem of partitioning a shared cache between multiple concurrently executing applications. The commonly used LRU policy implicitly partitions a shared cache on a demand basis, giving more cache resources to the application that has a high demand and fewer cache resources to the application that has a low demand. However, a higher demand for cache resources does not always correlate with a higher performance from additional cache resources. It is beneficial for performance to invest cache resources in the application that benefits more from the cache resources rather than in the application that has more demand for the cache resources. This paper proposes utility-based cache partitioning (UCP), a low-overhead, runtime mechanism that partitions a shared cache between multiple applications depending on the reduction in cache misses that each application is likely to obtain for a given amount of cache resources. The proposed mechanism monitors each application at runtime using a novel, cost-effective, hardware circuit that requires less than 2kB of storage. The information collected by the monitoring circuits is used by a partitioning algorithm to decide the amount of cache resources allocated to each application. Our evaluation, with 20 multiprogrammed workloads, shows that UCP improves performance of a dual-core system by up to 23% and on average 11% over LRU-based cache partitioning

While runahead execution is effective at parallelizing independent long-latency cache misses, it is unable to parallelize dependent long-latency cache misses. To overcome this limitation, this paper proposes a novel hardware technique, address-value delta (AVD) prediction. An AVD predictor keeps track of the address (pointer) load instructions for which the arithmetic difference (i.e., delta) between the effective address and the data value is stable. If such a load instruction incurs a long-latency cache miss during runahead execution, its data value is predicted by subtracting the stable delta from its effective address. This prediction enables the preexecution of dependent instructions, including load instructions that incur long-latency cache misses. We analyze why and for what kind of loads AVD prediction works and describe the design of an implementable AVD predictor. We also describe simple hardware and software optimizations that can significantly improve the benefits of AVD prediction and analyze the interaction of AVD prediction with runahead efficiency techniques and stream-based data prefetching. Our analysis shows that AVD prediction is complementary to these techniques. Our results show that augmenting a runahead processor with a simple, 16-entry AVD predictor improves the average execution time of a set of pointer-intensive applications by 14.3 percent (7.5 percent excluding benchmark health).

Summary form only given. Moore's law continues to thrive, - one billion transistors on each silicon die with a 10 GHz clock is close at hand. But Pentium 4 follow-ons, we are told, have been canceled. Another important chip manufacturer has canceled its top of the line processor. On the other hand, Intel has made some provocative statements with Pentium M. IBM has done likewise with Power 5. Can we continue to harness the raw technology available on the chip? If so, where are we going to look for solutions, and what does this mean for the microprocessor for high performance implementations ten years from now?.

The increasing transient fault rate necessitates on-chip fault tolerance techniques in future processors. The speed gap between the processor and the memory is also increasing, causing the processor to stay idle for hundreds of cycles while waiting for a long-latency cache miss to be serviced. Even in the presence of aggressive prefetching techniques, future processors are expected to waste significant processing bandwidth waiting for main memory. This paper proposes microarchitecture-based introspection (MBI), a transient-fault detection technique, which utilizes the wasted processing bandwidth during long-latency cache misses for redundant execution of the instruction stream. MBI has modest hardware cost, requires minimal modifications to the existing microarchitecture, and is particularly well suited for memory-intensive applications. Our evaluation reveals that the time redundancy of MBI results in an average IPC reduction of only 7.1 %for memory-intensive benchmarks in the SPEC CPU2000 suite. The average IPC reduction for the entire suite is 14.5%.

Runahead execution is a technique that improves processor performance by pre-executing the running application instead of stalling the processor when a long-latency cache miss occurs. Previous research has shown that this technique significantly improves processor performance. However, the efficiency of runahead execution, which directly affects the dynamic energy consumed by a runahead processor, has not been explored. A runahead processor executes significantly more instructions than a traditional out-of-order processor, sometimes without providing any performance benefit, which makes it inefficient. In this paper, we describe the causes of inefficiency in runahead execution and propose techniques to make a runahead processor more efficient, thereby reducing its energy consumption and possibly increasing its performance. Our analyses and results provide two major insights: (1) the efficiency of runahead execution can be greatly improved with simple techniques that reduce the number of short, overlapping, and useless runahead periods, which we identify as the three major causes of inefficiency; (2) simple optimizations targeting the increase of useful prefetches generated in runahead mode can increase both the performance and efficiency of a runahead processor. The techniques we propose reduce the increase in the number of instructions executed due to runahead execution from 26.5% to 6.2%, on average, without significantly affecting the performance improvement provided by runahead execution.

As processor speeds increase and memory latency becomes more critical, intelligent design and management of secondary caches becomes increasingly important. The efficiency of current set-associative caches is reduced because programs exhibit a non-uniform distribution of memory accesses across different cache sets. We propose a technique to vary the associativity of a cache on a per-set basis in response to the demands of the program. By increasing the number of tag-store entries relative to the number of data lines, we achieve the performance benefit of global replacement while maintaining the constant hit latency of a set-associative cache. The proposed variable-way, or V-Way, set-associative cache achieves an average miss rate reduction of 13% on sixteen benchmarks from the SPEC CPU2000 suite. This translates into an average IPC improvement of 8%.

Predicated execution has been used to reduce the number of branch mispredictions by eliminating hard-to-predict branches. However, the additional instruction overhead and additional data dependencies due to predicated execution sometimes offset the performance advantage of having fewer mispredictions. We propose a mechanism in which the compiler generates code that can be executed either as predicated code or non-predicated code (i.e., code with normal conditional branches). The hardware decides whether the predicated code or the non-predicated code is executed based on a run-time confidence estimation of the branch's prediction. The code generated by the compiler is the same as predicated code, except the predicated conditional branches are NOT removed - they are left intact in the program code. These conditional branches are called wish branches. The goal of wish branches is to use predicated execution for hard-to-predict dynamic branches and branch prediction for easy-to-predict dynamic branches, thereby obtaining the best of both worlds. We also introduce a class of wish branches, called wish loops, which utilize predication to reduce the misprediction penalty for hard-to-predict backward (loop) branches. We describe the semantics, types, and operation of wish branches along with the software and hardware support required to generate and utilize them. Our results show that wish branches decrease the average execution time of a subset of SPEC INT 2000 benchmarks by 14.2% compared to traditional conditional branches and by 13.3% compared to the best-performing predicated code binary.

While runahead execution is effective at parallelizing independent long-latency cache misses, it is unable to parallelize dependent long-latency cache misses. To overcome this limitation, this paper proposes a novel technique, address-value delta (AVD) prediction. An AVD predictor keeps track of the address (pointer) load instructions for which the arithmetic difference (i.e., delta) between the effective address and the data value is stable. If such a load instruction incurs a long-latency cache miss during runahead execution, its data value is predicted by subtracting the stable delta from its effective address. This prediction enables the pre-execution of dependent instructions, including load instructions that incur long-latency cache misses. We describe how, why, and for what kind of loads AVD prediction works and evaluate the design tradeoffs in an implementable AVD predictor. Our analysis shows that stable AVDs exist because of patterns in the way data structures are allocated in memory. Our results show that augmenting a runahead processor with a simple, 16-entry AVD predictor improves the average execution time of a set of pointer-intensive applications by 12.1%.

High-performance, out-of-order execution processors spend a significant portion of their execution time on the incorrect program path even though they employ aggressive branch prediction algorithms. Although memory references generated on the wrong path do not change the architectural state of the processor, they affect the arrangement of data in the memory hierarchy. This paper examines the effects of wrong-path memory references on processor performance. It is shown that these references significantly affect the IPC (instructions per cycle) performance of a processor. Not modeling them leads to errors of up to 10 percent (4 percent on average) in IPC estimates for the SPEC CPU2000 integer benchmarks on an out-of-order processor and errors of up to 63 percent on a runahead-execution processor. In general, the error in the IPC increases with increasing memory latency and instruction window size. We find that wrong-path references are usually beneficial for performance because they prefetch data that is used by later correct-path references. L2 cache pollution is found to be the most significant negative effect of wrong-path references. Code examples are shown to provide insights into how wrong-path references affect performance. We also show that it is crucial to model wrong-path references to accurately estimate the performance improvement provided by runahead execution.

Quantitative evaluation of next-generation computer architectures and processor enhancements is possible only by running simulations. However, since the insights that are gained through simulation are predicated on the accuracy of the simulation results, and since the design decisions for future processor architectures -- which cost billions of dollars to design and implement -- are based on those insights, periodic examination of the simulation process becomes a necessity, rather than a luxury. Accordingly, this panel discusses the deficiencies of existing simulators, benchmarks, and simulation methodologies and techniques, and, in addition, what future directions are available for each.

Provides an abstract of the keynote presentation and a brief professional biography of the presenter. The complete presentation was not made available for publication as part of the conference proceedings.

Control and data speculation are widely used to improve processor performance. Correct speculation can reduce execution time, but incorrect speculation can lead to increased execution time and greater energy consumption. This paper proposes a mechanism to leverage unexpected program behavior, called wrong-path events, that occur during periods of incorrect speculation. A wrong-path event is an instance of illegal or unusual program behavior that is more likely to occur on the wrong path than on the correct path, such as a NULL pointer dereference. When a wrong-path event occurs, the processor can predict that it is on the wrong path and speculatively initiate misprediction recovery. The purpose of the proposed mechanism is to improve the effectiveness of speculative execution in a processor by helping to insure that the processor remain "on the correct path" throughout periods of speculative execution. We describe a set of wrong-path events which can be used as strong indicators of misprediction. We find that on average 5% of the mispredicted branches in the SPEC2000 integer benchmarks produce a wrong-path event an average of 51 cycles before the branch is executed. We show that once a wrong-path event occurs, it is possible to accurately predict which unresolved branch in the processor is mispredicted using a simple, novel prediction mechanism. We discuss the advantages and shortcomings of wrong-path events and propose new areas for future research.

High-performance processors employ aggressive speculation and prefetching techniques to increase performance. Speculative memory references caused by these techniques sometimes bring data into the caches that are not needed by correct execution. This paper proposes the use of the first-level caches as filters that predict the usefulness of speculative memory references. With the proposed technique, speculative memory references bring data only into the first-level caches rather than all levels in the cache hierarchy. The processor monitors the use of the cache blocks in the first-level caches and decides which blocks to keep in the cache hierarchy based on the usefulness of cache blocks. It is shown that a simple implementation of this technique usually outperforms inclusive and exclusive baseline cache hierarchies commonly used by today's processors and results in IPC performance improvements of up to 9.2% on the SPEC2000 integer benchmarks.

Today's high performance processors tolerate long latency operations by means of out-of-order execution. However, as latencies increase, the size of the instruction window must increase even faster if we are to continue to tolerate these latencies. We have already reached the point where the size of an instruction window that can handle these latencies is prohibitively large in terms of both design complexity and power consumption. And, the problem is getting worse. This paper proposes runahead execution as an effective way to increase memory latency tolerance in an out-of-order processor without requiring an unreasonably large instruction window. Runahead execution unblocks the instruction window blocked by long latency operations allowing the processor to execute far ahead in the program path. This results in data being prefetched into caches long before it is needed. On a machine model based on the Intel/spl reg/ Pentium/spl reg/ processor, having a 128-entry instruction window, adding runahead execution improves the IPC (instructions per cycle) by 22% across a wide range of memory intensive applications. Also, for the same machine model, runahead execution combined with a 128-entry window performs within 1% of a machine with no runahead execution and a 384-entry instruction window.

The high clock frequencies of modern superscalar processors make the wire delay incurred in moving data across the processor chip a significant concern. As frequencies continue to increase, it will become more difficult for a centralized first level data cache to supply the timely data bandwidth required by superscalar processors.This paper presents a complete solution for the partitioning of the first level of the memory hierarchy. The first level data cache is split into several independent partitions, which are arbitrarily distributable across the processor die. After being decoded, memory instructions are sent to the reservation stations of the functional unit adjacent to the cache partition that they are most likely to access. The partition assignments for both static instructions and cache data are dynamically changed to adapt to data access patterns. A data cache line is permitted to reside in only one partition at a time, allowing each store to update only a single partition, and allowing the partitioning and simplification of the memory disambiguation logic. The partitioned cache achieves a reduction in cache access latency through a combination of reduced wire delay and reduced cache array size. A partitioned cache with eight 8KB direct-mapped partitions maintains a hit rate greater than that of a 32KB direct-mapped cache. A machine utilizing the partitioned cache outperforms a machine with a conventional 64KB direct-mapped cache by 4.5% and a machine with a 64KB 8-way set-associative cache by 7.0%, when cache latencies estimated through the use of the CACTI cache simulation tool are taken into account.

Network processors are being asked to perform increasingly complex operations on packets of information at faster and faster rates. Because processor performance and memory cycle times are not keeping up with this demand, there is a fundamental need for simultaneous processing of multiple packets, and the degree of this parallelism is increasing. Sometimes a dependency exists between two packets currently being operated on, and as the ratio of packet processing time to packet transmission time increases, these dependencies are more likely to impact performance. Thus, the way packet dependencies are handled will become critical. In this paper we show that there is potentially a dramatic difference in performance between optimal and non-optimal solutions. We argue that this is the key challenge that must be addressed in highly parallel network processors. We discuss how work in thread level speculation relates to this problem and describe a practical hardware implementation that requires little or no changes to software and with near optimal performance.

This paper evaluates the use of redundant binary and pipelined 2's complement adders in out-of-order execution cores. Redundant binary adders reduce the ADD latency to less than half that of traditional 2's complement adders, allowing higher core clock frequencies and greater execution bandwidth (in instructions per second). Pipelined 2's complement adders allow a higher clock frequency, but do not reduce the ADD latency. Machines with redundant binary adders are compared to machines with 2's complement adders and the same execution bandwidth and bypass network complexity. Results show that on the SPECint95 benchmarks, the average IPC of an 8-wide machine with 1-cycle redundant binary adders is 9% higher than a machine using 2-cycle pipelined adders. Pipelined functional units and multi-cycle register files may require multi-level bypass networks to guarantee that an instruction's result is available any cycle after it is produced. Multi-level bypass networks require large fan-in input mixes that increase cycle time. This paper shows that one level of bypass paths in a multi-level bypass network can be removed while still achieving within 3% to 1% of the IPC of a machine with a full bypass network.

Branch misprediction penalties continue to increase as microprocessor cores become wider and deeper. Thus, improving branch prediction accuracy remains an important challenge. Simultaneous subordinate microthreading (SSMT) provides a means to improve branch prediction accuracy. SSMT machines run multiple, concurrent microthreads in support of the primary thread. We propose to dynamically construct microthreads that can speculatively and accurately pre-compute branch outcomes along frequently mispredicted paths. The mechanism is intended to be implemented entirely in hardware. We present the details for doing so. We show how to select the right paths, how to generate accurate predictions, and how to get this information in a timely way. We achieve an average gain of 8.4% (42% maximum) over a very aggressive baseline machine on the SPECint95 and SPECint2000 benchmark suites.

Research has shown that precomputation microthreads can be useful for improving branch prediction and prefetching. However, it is not obvious how to provide the necessary microarchitectural support, and few details have been given in the literature. By judiciously constraining microthreads, we can easily adapt a superscalar machine to support many simultaneous microthreads. The nature of precomputation microthreads also requires efficient usage of resources. Our proposed implementation addresses this issue by dynamically identifying and aborting useless microthreads.

Pipelining allows processors to exploit parallelism. Unfortunately, critical loops-pieces of logic that must evaluate in a single cycle to meet IPC (Instructions Per Cycle) goals-prevent deeper pipelining. In today's processors, one of these loops is the instruction scheduling (wakeup and select) logic [10]. This paper describes a technique that pipelines this loop by breaking it into two smaller loops: a critical, single-cycle loop for wakeup; and a noncritical, potentially multi-cycle, loop for select. For the 12 SPECint*2000 benchmarks, a machine with two-cycle select logic (i.e., three-cycle scheduling logic) using this technique has an average IPC 15% greater than a machine with three-cycle pipelined conventional scheduling logic, and an IPC within 3% of a machine of the same pipeline depth and one-cycle (ideal) scheduling logic. Since select accounts for more than half the scheduling latency [10], this technique could significantly increase clock frequency while having minimal impact on IPC.

The premise of this panel is that most introductory Computer Science courses are too narrowly focused on teaching students a programming language. This is a controversy that has been debated for years, but in recent years seems to have been forgotten. The writers of Computing Curricula 1991 stated:"Many feel that the amount of attention traditionally paid to the syntax of a programming language in the first course is excessive, and ought to be replaced with a more balanced introduction to the discipline. For these reasons, PR: Introduction to a Programming Language is defined as a separate knowledge unit in Part II, but is not a required part of the common requirements. "[1]This panel will present a review of current, typical first year courses and evidence for the case against focusing those courses on the teaching of a programming language. Next, each panelist will present his or her philosophy for a first course, followed by details of the courses at their school that implement their view, and conclude with outcomes and evidence of success of the courses.The panel includes four experienced CS-1/CS-2 educators, two of whom are members of the Computing Curriculum 2001 Pedagogy Focus Group on Introductory Courses and Topics (including the chair), and two of whom are authors of introductory texts that do not focus on teaching a programming language.

The first microprocessor the Intel 4004, showed up in 1971. It contained 2300 transistors and operated at a clockfrequency of 108 kHz. Today, 30 years later the microprocessor contains almost 200 million transistors, operating at a frequency of more than 1 GHz. In five years, those numbers are expected to grow to more than a billion transistors on a single chip, operating at a clockfrequency of from 6 to 10 GHz. The evolution of the microprocessor from where it started in 1971 to where it is today and where it is likely to be in five years, has come about because of several contributing forces. Our position is that this evolution did not just happen, that each step forward came as a result of one of three things, and always within the context of a computer architect making tradeoffs. The three things are: 1) new requirements; 2) bottlenecks; and 3) good fortune. I call them collectively agents for evolution. This article attempts to do three things: describe a basic framework for the field of microprocessors, show some of the important developments that have come along in the 30 years since the arrival of the first microprocessor and finally, suggest some of the new things you can expect to see in a high-performance microprocessor in the next five years.

A machine's performance is the product of its IPC (Instructions Per Cycle) and clock frequency. Recently, S. Palacharla et al. (1997) warned that the dynamic instruction scheduling logic for current machines performs an atomic operation. Either you sacrifice IPC by pipelining this logic, thereby eliminating its ability to execute dependent instructions in consecutive cycles. Or you sacrifice clock frequency by not pipelining it, performing this atomic operation in a single long cycle. Both alternatives are unacceptable for high performance. The paper offers a third, acceptable, alternative: pipelined scheduling with speculative wakeup. This technique pipelines the scheduling logic without eliminating its ability to execute dependent instructions in consecutive cycles. With this technique, you sacrifice little IPC, and no clock frequency. Our results show that on the SPECint95 benchmarks, a machine using this technique has an average IPC that is 13% greater than the IPC of a baseline machine that pipelines the scheduling logic but sacrifices the ability to execute dependent instructions in consecutive cycles, and within 2% of the IPC of a conventional machine that uses single cycle scheduling logic.

Metadata updates, such as file creation and block allocation, have consistently been identified as a source of performance, integrity, security, and availability problems for file systems. Soft updates is an implementation technique for low-cost sequencing of fine-grained updates to write-back cache blocks. Using soft updates to track and enforce metadata update dependencies, a file system can safely use delayed writes for almost all file operations. This article describes soft updates, their incorporation into the 4.4BSD fast file system, and the resulting effects on the sytem. We show that a disk-based file system using soft updates achieves memory-based file system performance while providing stronger integrity and security guarantees than most disk-based file systems. For workloads that frequently perform updates on metadata (such as creating and deleting files), this improves performance by more than a factor of two and up to a factor of 20 when compared to the conventional synchronous write approach and by 4-19% when compared to an aggressive write-ahead logging approach. In addition, soft updates can improve file system availablity by relegating crash-recovery assistance (e.g., the fsck utility) to an optional and background role, reducing file system recovery time to less than one second.

Current work in Simultaneous Multithreading provides little benefit to programs that aren't partitioned into threads. We propose Simultaneous Subordinate Microthreading (SSMT) to correct this by spawning subordinate threads that perform optimizations on behalf of the single primary thread. These threads, written in microcode, are issued and executed concurrently with the primary thread. They directly manipulate the microarchitecture to improve the primary thread's branch prediction accuracy, cache hit rate, and prefetch effectiveness. All contribute to the performance of the primary thread. This paper introduces SSMT and discusses its potential to increase performance. We illustrate its usefulness with an SSMT machine that executes subordinate microthreads to improve the branch prediction of the primary thread. We show simulation results for the SPECint95 benchmarks.

In this paper, we examine some critical design features of a trace cache fetch engine for a 16-wide issue processor and evaluate their effects on performance. We evaluate path associativity, partial matching, and inactive issue, all of which are straightforward extensions to the trace cache. We examine features such as the fill unit and branch predictor design. In our final analysis, we show that the trace cache mechanism attains a 28 percent performance improvement over an aggressive single block fetch mechanism and a 15 percent improvement over a sequential multiblock mechanism.

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.

Pipeline flushes due to branch mispredictions is one of the most serious problems facing the designer of a deeply pipelined, superscalar processor. Many branch predictors have been proposed to help alleviate this problem, including two-level adaptive branch predictors and hybrid branch predictors. Numerous studies have shown which predictors and configurations best predict the branches in a given set of benchmarks. Some studies have also investigated effects, such as pattern history table interference, that can be detrimental to the performance of these predictors. However, little research has been done on which characteristics of branch behavior make predictors perform well. In this paper we investigate and quantify reasons why branches are predictable. We show that some of this predictability is not captured by the two-level adaptive branch predictors. An understanding of the predictability of branches may lead to insights ultimately resulting in better or less complex predictors. We also investigate and quantify what function of the branches in each benchmark is predictable using each of the methods described in this paper.

The increasing widths of superscalar processors are placing greater demands upon the fetch mechanism. The trace cache meets these demands by placing logically contiguous instructions in physically contiguous storage. As a result, the trace cache delivers instructions at a high rate by supplying multiple fetch blocks each cycle. In this paper we examine two techniques to improve the number of instructions delivered each cycle by the trace cache. The first technique, branch promotion, dynamically converts strongly biased branches into branches with static predictions. Because these promoted branches require no dynamic prediction, the branch predictor suffers less from the negative effects of interference. Branch promotion unlocks the potential of the second technique: trace packing. With trace packing, trace segments are packed with as many instructions as will fit, without regard to naturally occurring fetch block boundaries. With both techniques, the effective fetch rate of the trace cache jumps up 17% over a trace cache which implements neither on a machine where the execution engine has a very aggressive memory disambiguator; the performance of a machine using branch promotion and trace packing is on average 11% higher than a machine using neither technique.

The fill unit is the structure which collects blocks of instructions and combines them into multi-block segments for storage in a trace cache. In this paper we expand the role of the fill unit to include four dynamic optimizations: (1) Register move instructions are explicitly marked, enabling them to be executed within the decode logic, (2) Immediate values of dependent instructions are combined, if possible, which removes a step in the dependency chain. (3) Dependent pairs of shift and add instructions are combined into scaled add instructions. (4) Instructions are arranged within the trace segment to minimize the impact of the latency through the operand bypass network. Together these dynamic trace optimizations improve performance on the SPECint95 benchmarks by more than 17% and over all the benchmarks studied by slightly more than 18%.

We describe a system-level simulation model and show that it enables accurate predictions of both I/O subsystem and overall system performance. In contrast, the conventional approach for evaluating the performance of an I/O subsystem design, which is based on standalone subsystem models, is often unable to accurately predict performance changes because it is too narrow in scope. In particular, conventional methodology treats all I/O requests equally, ignoring differences in how individual requests' response times affect system behavior (including both system performance and the subsequent I/O workload). We introduce the concept of request criticality to describe these feedback effects and show that real I/O workloads are not approximated well by either open or closed input models. Because conventional methodology ignores this fact, it often leads to inaccurate performance predictions and can thereby lead to incorrect conclusions and poor design choices. We illustrate these problems with real examples and show that a system-level model, which includes both the I/O subsystem and other important system components (e.g., CPUs and system software), properly captures the feedback and subsequent performance effects.

As the issue rate and pipeline depth of high performance superscalar processors increase, the amount of speculative work issued also increases. Because speculative work must be thrown away in the event of a branch misprediction, wide-issue, deeply pipelined processors must employ accurate branch predictors to effectively exploit their performance potential. Many existing branch prediction schemes are capable of accurately predicting the direction of conditional branches. However, these schemes are ineffective in predicting the targets of indirect jumps achieving, on average, a prediction accuracy rate of 51.8% for the SPECint95 benchmarks. In this paper, we propose a new prediction mechanism, the target cache, for predicting indirect jump targets. For the perl and gcc benchmarks, this mechanism reduces the indirect jump misprediction rate by 93.4% and 63.35% and the overall execution time by 14% and 5%.

Deeply pipelined, superscalar processors require accurate branch prediction to achieve high performance. Two-level branch predictors have been shown to achieve high prediction accuracy. It has also been shown that branch interference is a major contributor to the number of branches mispredicted by two-level predictors.This paper presents a new method to reduce the interference problem called agree prediction, which reduces the chance that two branches aliasing the same PHT entry will interfere negatively. We evaluate the performance of this scheme using full traces (both user and supervisor) of the SPECint95 benchmarks. The result is a reduction in the misprediction rate of gcc ranging from 8.62% with a 64K-entry PHT up to 33.3% with a 1K-entry PHT.

The increasing widths of superscalar processors are placing greater demands upon the fetch mechanism. The trace cache meets these demands by placing logically contiguous instructions in physically contiguous storage. It is capable of supplying multiple fetch blocks each cycle. We examine two fetch and issue techniques, partial matching and inactive issue, that improve the overall performance of the trace cache by improving the effective fetch rate. We show that for the SPECint95 benchmarks partial matching increases the overall performance by 12% and adding inactive issue increases performance by 15%. Furthermore we apply these two techniques to issue blocks from trace segments which contain multiple execution paths. We conclude with a performance comparison between a trace cache implementing partial matching and inactive issue and an aggressive single block fetch mechanism. The trace cache increases performance by an average of 25% over the instruction cache.

In conventional processors, each instruction cache fetch brings in a group of instructions. Upon encountering an instruction cache miss, the processor will wait until the instruction cache miss is serviced before continuing to fetch any new instructions. The paper presents a new technique, called out-of-order issue, which allows the processor to temporarily ignore the instructions associated with the instruction cache miss. The processor attempts to fetch the instructions that follow the group of instructions associated with the miss. These instructions are then decoded and written into the processor's reservation stations. Later, after the instruction cache miss has been serviced, the instructions associated with the miss are decoded and written into the reservation stations. (We use the term issue to indicate the act of writing instructions into the reservation stations. With this technique, instructions are not written into the reservation stations in program order. Hence, the term out-of-order issue.) We introduce the concept of out-of-order issue, describe its implementation, and present some initial data showing the performance gains possible with out-of-order issue.

Pipeline stalls due to conditional branches represent one of the most significant impediments to realizing the performance potential of deeply pipelined, superscalar processors. Many branch predictors have been proposed to help alleviate this problem, including the Two-Level Adaptive Branch Predictor, and more recently, two-component hybrid branch predictors.In a less idealized environment, such as a time-shared system, code of interest involves context switches. Context switches, even at fairly large intervals, can seriously degrade the performance of many of the most accurate branch prediction schemes. In this paper, we introduce a new hybrid branch predictor and show that it is more accurate (for a given cost) than any previously published scheme, especially if the branch histories are periodically flushed due to the presence of context switches.

To exploit larger amounts of instruction level parallelism, processors are being built with wider issue widths and larger numbers of functional units. Instruction fetch rate must also be increased in order to effectively exploit the performance potential of such processors. Block-structured ISAs provide an effective means of increasing the instruction fetch rare. We define an optimization, called block enlargement, that can be applied to a block-structured ISA to increase the instruction fetch rate of a processor that implements that ISA. We have constructed a compiler that generates block-structured ISA code, and a simulator that models the execution of that code on a block-structured ISA processor. We show that for the SPECint95 benchmarks, the block-structured ISA processor executing enlarged atomic blocks outperforms a conventional ISA processor by 12% while using simpler microarchitectural mechanisms to support wide-issue and dynamic scheduling.

Very accurate branch prediction is an important requirement for achieving high performance on deeply pipelined, superscalar processors. To improve on the prediction accuracy of current single-scheme branch predictors, hybrid (multiple-scheme) branch predictors have been proposed (McFarling (1993), Chang et al. (1994)). These predictors combined multiple single-scheme predictors into a single predictor. They use a selection mechanism to decide for each branch, which single-scheme predictor to use. The performance of a hybrid predictor depends on its single-scheme predictor components and its selection mechanism. Using known single-scheme predictors and selection mechanisms, this paper identifies the most effective hybrid predictor implementation. In addition, it introduces a new selection mechanism, the 2-level selector, which further improves the performance of the hybrid branch predictor.

Sophisticated disk scheduling algorithms require accurate, detailed disk drive specifications, including data about mechanical delays, on-board caching and prefetching algorithms, command and protocol overheads, and logical-to-physical block mappings. Comprehensive disk models used in storage subsystem design require similar levels of detail. We describe a suite of general-purpose algorithms and techniques for acquiring the necessary information from a SCSI disk drive. Using only the ANSI-standard interface, we demonstrate how the important parameter values of a modern SCSI drive can be determined accurately and efficiently.

Provides an overview of the technical articles and features presented in this issue.

There is wide agreement that one of the most important impediments to the performance of current and future pipelined superscalar processors is the presence of conditional branches in the instruction stream. Speculative execution seems to be one solution of choice to the branch problem, but speculative work is discarded if a branch is mispredicted. Therefore, we need a very accurate branch predictor; 95% accuracy is not good enough. This paper proposes branch classification to help improve the accuracy of branch predictors. Branch classification allows an individual branch instruction to be associated with the branch predictor best suited to predict its direction. Using this approach, a hybrid branch predictor can be constructed such that each component branch predictor predicts those branches for which it is best suited. This paper suggests one classification scheme, analyzes several branch predictors, and proposes a hybrid branch predictor that achieves higher prediction accuracy than any branch predictor previously reported in the literature.

Recent research (A.R. Talcott, W. Yamamoto, M.J. Serrano, R.C. Wood, and M. Nemirovsky, Proc. 21st Annual Int. Symposium Comput. Archit., pp. 12-21, 1994) has suggested that the branch history register need not contain the outcomes of the most recent branches in order for the two-level adaptive branch predictor to work well. From this result, it is tempting to conclude that the branch history register need not be speculatively updated. This paper revisits this work and explains when the most recent branch outcomes can be omitted without significantly affecting performance. It also explains why this result does not imply that speculative updating is not important. This paper shows that because the number of unresolved branches present in the machine varies during program execution, branch predictors without speculative updating perform significantly worse than branch predictors with speculative updating.

A superscalar implementation of a conventional instruction set architecture (ISA) requires N(N-1) comparators to determine dependencies between the N instructions issuing concurrently and 2N register file read ports to handle the 2 operands that each instruction can potentially source. On the other hand, if the compiler is allowed to specify part of the renaming tag, we show that we can eliminate the comparators needed to detect data dependencies between instructions issuing concurrently, and we can reduce the number of read ports from 16 to about 7 without losing performance. Finally, we show that this approach more efficiently implements predicated execution than can be done with a conventional ISA on a machine that renames registers.

Disk subsystem performance can be dramatically improved by dynamically ordering, or scheduling, pending requests. Via strongly validated simulation, we examine the impact of complex logical-to-physical mappings and large prefetching caches on scheduling effectiveness. Using both synthetic workloads and traces captured from six different user environments, we arrive at three main conclusions: (1) Incorporating complex mapping information into the scheduler provides only a marginal (less than 2%) decrease in response times for seek-reducing algorithms. (2) Algorithms which effectively utilize prefetching disk caches provide significant performance improvements for workloads with read sequentiality. The cyclical scan algorithm (C-LOOK), which always schedules requests in ascending logical order, achieves the highest performance among seek-reducing algorithms for such workloads. (3) Algorithms that reduce overall positioning delays produce the highest performance provided that they recognize and exploit a prefetching cache.

Improvements in disk access time have lagged behind improvements in microprocessor and main memory speeds. This disparity has made the storage subsystem a major bottleneck for many applications. Disk arrays that can service multiple disk requests simultaneously are being used to satisfy increasing throughput requirements. Higher throughput rates can be achieved by increasing the number of disks in an array. This increases the number of actuators that are available to service separate requests. It also spreads the data among more disk drives, reducing the seek time as the number of cylinders utilized on each disk drive decreases. The result is an increase in throughput that exceeds the increase in the number of disks. This suggests a tradeoff between the space utilization of disks in an array and the throughput of the array.>

High performance computer implementation today is increasingly directed toward parallelism in the hard-

Recent attention to speculative execution as a mecha-nism for increasing performance of single instruction streams has demanded substantially better branch prediction than what has been previously available. We [1, 2] and Pan, So, and Rahmeh [4] have both proposed variations of the same aggressive dynamic branch pre-dictor for handling those needs. We call the basic model Two-Level Adaptive Branch Prediction; Pan, So, and Rahmeh call it Correlation Branch Prediction. In this paper, we adopt the terminology of [2] and show that there are really nine variations of the same basic model. We compare the nine variations with respect to the amount of history information kept. We study the effects of different branch history lengths and pattern history table configurations. Finally, we evaluate the cost effectiveness of the nine variations. 1

Pipelining is a major technique used in high performance processors. But its effectiveness is reduced by the branch instructions. A new organization for implementing branch instructions is presented: the Multiple Instruction Decode Effective Execution (MIDEE) organization. All the pipeline depths may be addressed using this organization. MIDEE is based on the use of double fetch and decode, early computation of the target address for branch instructions and two instruction queues. The double fetch-decode concerns a pair of instructions stored at consecutive addresses. These instructions are then decoded simultaneously, but no execution hardware is duplicated; only useful instructions are effectively executed. A pair of instruction queues are used between the fetch-decode stages and execution stages; this allows to hide branch penalty and most of the instruction cache misses penalty. Trace driven simulations show that the performance of deep pipeline processor may dramatically be improved when the MIDEE organization is implemented: branch penalty is reduced and pipeline stall delay due to instruction cache misses is also decreased.>

Presents a comparison of superscalar and decoupled access/execute architectures. Both architectures attempt to exploit instruction-level parallelism by issuing multiple instructions per cycle, employing dynamic scheduling to maximize performance. Simulation results are presented for four different configurations, demonstrating that the architectural queues of the decoupled machines provide similar functionality to register renaming, dynamic loop unrolling, and out-of-order execution of the superscalar machines with significantly less complexity.>

Input/output subsystem performance is currently receiving considerable research attention. Significant effort has been focused on reducing average I/O response times and increasing throughput for a given workload. This work has resulted in tremendous advances in I/O subsystem performance. It is unclear, however, how these improvements will be reflected in overall system performance. The central problem lies in the fact that the current method of study tends to treat all I/O requests aa equally important. We introduce a three class taxonomy of I/O requests based on their effects on system performance. We denote the three classes time-critical, time-limited, and time-noncritical. A system-level, trace-driven simulation model has been developed for the purpose of studying disk scheduling algorithms. By incorporating knowledge of I/O classes, algorithms tuned for system performance rather than I/O subsystem performance may be developed. Traditional I/O subsystem simulators would rate such algorithms unfavorably because they produce suboptimal subsystem performance. By studying the I/O subsystem via global, system-level simulation, one can more easily identify changes that will improve overall system performance.

Several disk array architectures have been proposed to provide high throughput for transaction processing applications. When a single disk in a redundant array fails, the array continues to operate, albeit in a degraded mode with a corresponding reduction in performance. In addition, the lost data must be rebuilt to a spare disk in a timely manner to reduce the probability of permanent data loss. Several researchers have proposed and examined algorithms for rebuilding the failed disk in a disk array with parity.

As the issue rate and depth of pipelining of high performance Superscalar processors increase, the importance of an excellent branch predictor becomes more vital to delivering the potential performance of a wide-issue, deep pipelined microarchitecture. We propose a new dynamic branch predictor (Two-Level Adaptive Branch Prediction) that achieves substantially higher accuracy than any other scheme reported in the literature. The mechanism uses two levels of branch history information to make predictions, the history of the last k branches encountered, and the branch behavior for the last s occurrences of the specific pattern of these k branches. We have identified three variations of the Two-Level Adaptive Branch Prediction, depending on how finely we resolve the history information gathered. We compute the hardware costs of implementing each of the three variations, and use these costs in evaluating their relative effectiveness. We measure the branch prediction accuracy of the three variations of two-Level Adaptive Branch Prediction, along with several other popular proposed dynamic and static prediction schemes, on the SPEC benchmarks. We show that the average prediction accuracy for Two-Level Adaptive Branch Prediction is 97 percent, while the other known schemes achieve at most 94.4 percent average prediction accuracy. We measure the effectiveness of different prediction algorithms and different amounts of history and pattern information. We measure the costs of each variation to obtain the same prediction accuracy.

Article Single instruction stream parallelism is greater than two Share on Authors: Michael Butler Department of Electrical Engineering and Computer Science, The University of Michigan, Ann Arbor, Michigan Department of Electrical Engineering and Computer Science, The University of Michigan, Ann Arbor, MichiganView Profile , Tse-Yu Yeh Department of Electrical Engineering and Computer Science, The University of Michigan, Ann Arbor, Michigan Department of Electrical Engineering and Computer Science, The University of Michigan, Ann Arbor, MichiganView Profile , Yale Patt Department of Electrical Engineering and Computer Science, The University of Michigan, Ann Arbor, Michigan Department of Electrical Engineering and Computer Science, The University of Michigan, Ann Arbor, MichiganView Profile , Mitch Alsup Motorola Incorporated, Microprocessor and Memory Technology Group, 6501 William Cannon Drive West, Austin, Texas Motorola Incorporated, Microprocessor and Memory Technology Group, 6501 William Cannon Drive West, Austin, TexasView Profile , Hunter Scales Motorola Incorporated, Microprocessor and Memory Technology Group, 6501 William Cannon Drive West, Austin, Texas Motorola Incorporated, Microprocessor and Memory Technology Group, 6501 William Cannon Drive West, Austin, TexasView Profile , Michael Shebanow Motorola Incorporated, Microprocessor and Memory Technology Group, 6501 William Cannon Drive West, Austin, Texas Motorola Incorporated, Microprocessor and Memory Technology Group, 6501 William Cannon Drive West, Austin, TexasView Profile Authors Info & Claims ISCA '91: Proceedings of the 18th annual international symposium on Computer architectureApril 1991 Pages 276–286https://doi.org/10.1145/115952.115980Online:01 April 1991Publication History 98citation1,234DownloadsMetricsTotal Citations98Total Downloads1,234Last 12 Months81Last 6 weeks43 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

ABSTMCTIt has been suggested that non-scientific code has very little parallelism not already exploited by existing processors.In this paper we show that contrary to this notion, there is actually a significant amount of unexploited parallelism in typical general purpose code.In order to exploit this parallelism, a combination of hardware and software techniques must be applied.We analyze three techniques: dynamic scheduling, speculative execution and basic block enlargement.We will show that indeed for narrow instruction words 1itde is to be gained b y appl yi ng these techniques.However, as the number of simultaneous operations increases, it beeomes possible to achieve speedups of three to six on realistic processors. 1

Aml A&X, Michiga%l 48309-2322 4.6 instructions per cycle, and degradation of between 1 and 17 percent over the ideal memory system.

Article Free Access Share on Two-level adaptive training branch prediction Authors: Tse-Yu Yeh Department of Electrical Engineering and Computer Science, The University of Michigan, Ann Arbor, Michigan Department of Electrical Engineering and Computer Science, The University of Michigan, Ann Arbor, MichiganView Profile , Yale N. Patt Department of Electrical Engineering and Computer Science, The University of Michigan, Ann Arbor, Michigan Department of Electrical Engineering and Computer Science, The University of Michigan, Ann Arbor, MichiganView Profile Authors Info & Claims MICRO 24: Proceedings of the 24th annual international symposium on MicroarchitectureSeptember 1991 Pages 51–61https://doi.org/10.1145/123465.123475Online:01 September 1991Publication History 483citation5,042DownloadsMetricsTotal Citations483Total Downloads5,042Last 12 Months372Last 6 weeks42 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

In this paper we identify three types of atomic units, or indivisible units of work: architectural atomic units (defined by architecture level interrupts and exceptions), compiler atomic units (defined by compiler code generation) and execution atomic units (defined by run-time interruptibility). We discuss trade-offs for these units and show that size has different performance implications depending on the atomic unit. We simulate a number of different implementations of the VAX architecture, focusing on different execution atomic unit sizes. We show that significant performance benefits can be achieved by having large execution atomic units in dynamically scheduled machines.

We describe the Parallel Unification Machine (PLUM), a Prolog processor that exploits fine grain parallelism using multiple function units executing in parallel. In most cases the execution of bookkeeping instructions is almost completely overlapped by unification, and the performance of the processor is limited only by the available unification parallelism. We present measurements from a register transfer level simulator of PLUM. These results show that PLUM with 3 Unification Units achieves an average speedup of approximately 3.4 over the Berkeley VLSI-PLM, which is usually regarded as the current highest performance special purpose, pipelined Prolog processor. Measurements that show the effects of multiple Unification Units and memory access time on performance are also presented.

An area that should provide opportunities for obtaining improvements in the performance of Prolog programming is explored: the microarchitecture of the uniprocessor engine. Alternative execution models are examined for a uniprocessor microengine, and their performance is measured on 14 separate benchmark programs; the resulting data is presented and analyzed. The author also examines the program size explosion that results from compiling directly to a low-level instrument assembly. The characteristics of an optimal microarchitecture are identified and opportunities for further improvement at the microengine level are discussed.>

Simulations of scientific programs running on traditional scientific computer architectures show that execution with hundreds of registers can be more than twice as fast as execution with only eight registers. In addition, execution with a small number of fast registers and hundreds of slower registers can be as fast as execution with hundreds of fast registers. A hierarchical organization of fast and slow registers is presented, register-allocation strategies are discussed, and a novel, indirect, register-addressing mechanism is described.

We have developed a tool based on microcode modifications to a VAX 8600 which allows a wide variety of operating system measurements to be taken with minimal perturbation and without the need to modify any operating system software. A trace of interrupts, exceptions, system calls and context switches is generated as a side-effect to normal execution. In this paper we describe the tool we have developed and present some results we have gathered under both UNIX 4.3 BSD and VAX/VMS V4.5. We compare the process fork behavior of two different command shells under UNIX, look at context switch rates for interactive and batch workloads and generate a histogram for network interrupt service time.

Out-of-order execution and branch prediction are two mechanisms that can be used profitably in the design of Supercomputers to increase performance. Unfortunately this means there must be some kind of repair mechanism, since situations do occur that require the computing engine to repair to a known previous state. One way to handle this is by checkpoint repair. In this paper we derive several properties of checkpoint repair mechanisms. In addition, we provide algorithms for performing checkpoint repair that incur very little overhead in time and modest cost in hardware. We also note that our algorithms require no additional complexity or time for use with write back cache memory systems than they do with write through cache memory systems, contrary to statements made by previous researchers.

There is an apparent conflict between the hardware requirements for fast parallel execution and the hardware requirements for fast serial execution. For example, fast vector execution is achieved by maintaining high execution concurrency over extended periods of time. With many operations executing in parallel, the time to carry out individual operations is much less important than the average execution concurrency.

Out-or-order execution and branch prediction are two mechanisms that can be used profitably in the design of supercomputers to increase performance. Proper exception handling and branch prediction miss handling in an out-of-order execution machine do require some kind of repair mechanism which can restore the machine to a known previous state. In this paper we present a class of repair mechanisms using the concept of checkpointing. We derive several properties of checkpoint repair mechanisms. In addition, we provide algorithms for performing checkpoint repair that incur little overhead in time and modest cost in hardware. We also note that our algorithms require no additional complexity or time for use with write-back cache memory systems than they do with write-through cache memory systems, contrary to statements made by previous researchers.

Our recent work in microarchitecture has identified a new model of execution, restricted data flow, in which data flow techniques are used to coordinate out-of-order execution of sequential instruction streams. We believe that the restricted data flow model has great potential for implementing very high performance computing engines. This paper defines a minimal functionality variant of our model, which we are calling HPSm. The instruction set, data path, timing and control of HPSm are all described. A simulator for HPSm has been written, and some of the Berkeley RISC benchmarks have been executed on the simulator. We report the measurements obtained from these benchmarks, along with the measurements obtained for the Berkeley RISC II. The results are encouraging.

article Free Access Share on Performance studies of a Prolog machine architecture Authors: T. P. Dobry Computer Science Division, University of California,Berkeley, Berkeley, California Computer Science Division, University of California,Berkeley, Berkeley, CaliforniaView Profile , A. M. Despain Computer Science Division, University of California,Berkeley, Berkeley, California Computer Science Division, University of California,Berkeley, Berkeley, CaliforniaView Profile , Y. N. Patt Computer Science Division, University of California,Berkeley, Berkeley, California Computer Science Division, University of California,Berkeley, Berkeley, CaliforniaView Profile Authors Info & Claims ACM SIGARCH Computer Architecture NewsVolume 13Issue 3June 1985 pp 180–190https://doi.org/10.1145/327070.327161Published:01 June 1985Publication History 60citation339DownloadsMetricsTotal Citations60Total Downloads339Last 12 Months35Last 6 weeks7 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The VAX-11/7801 was designed specifically to implement the VAX architecture. As such, it does not support the IEEE standard for floating point arithmetic. A project was undertaken to provide this support by modifying the 11/780 microarchitecture. Our objective was to produce a microengine that would efficiently execute the VAX instruction set, modified to handle VAX floating point instructions in accordance with the IEEE standard. Our methodology was to make minimal changes to the 11/780 hardware, relying primarily on changes to the microcode. This paper describes the modifications required to implement the IEEE standard, examines the various design alternatives available to us, presents measurements of our implementation, and analyzes our results. We also offer some comments on the matter of retrofitting an existing architecture to a new unintended use.

A universal logic module (ULM) with interconnected external terminals contains m input terminals and s auxiliary function terminals. The module implements the function U( Z1, Z2,...,Zm) such that every Boolean function of n variables f( x1, x2,* .* * X,n) can be realized by an appropriate substitution of an element of 5= { xl,x1,x2,x2,...,Xn,xn,g1,g2,..., gs} for each zj. An improved lower bound on the minimum number of terminals of a ULM of this type is derived. It is shown that certain of the " best-known" designs are in fact optimal. Improved designs are presented for ULM's of nine and ten arguments.

The doubly chained tree structure is an efficient device for organizing a file that must be searched and updated frequently. This paper considers a variation to the doubly chained tree which is more representative of a file in which the data is partitioned into blocks or pages. In this model the cost of searching the next node is 1 if the node is reachable from the same root (i.e., on the same page), and is k if the next node is the next root (i. e., on a different page). An algorithm for constructing doubly chained trees having any number of terminal nodes N, with minimal average search length, is developed. A simple closed expression is derived for the minimum average search time as a function of the number of terminal nodes N and the parameter k. A proof of optimality is also included.