With severe challenges facing computer technology scaling, parallel hardware accelerators have become increasingly attractive solutions to continued performance scaling. However, performance scaling is limited for irregular, input-dependent workloads. Often, static analysis is infeasible and overheads can outweigh benefits, resulting sometimes in weaker performance than a serial counterpart.

In this paper, we devise a framework to infer a smartphone user's location and walking routes in an indoor environment, using only the information from inertial measurement unit (IMU) sensors like gyroscope and accelerometer. To overcome the shortcoming of estimation drift over time in common PDR (pedestrian dead reckoning)-IMU systems, we propose a map-aided system which uses the map elements to help correct the user's position. We generate a map based on the environment parameters and a map matching algorithm is applied to find the most likely location of the user. The reading from the IMU sensors contains amounts of noise when user is walking, therefore we propose an edge detection algorithm based on the pruned exact linear time (PELT) model to smooth the piece-wise signals and identify the time frame when the user is making a turn. We evaluate our system when the smartphone is held either in the user's hand or in the backpack, and the system is able to give the correct walking path in both cases.

We have developed a full system x86 simulator for teaching computer architecture, with graphical interfaces allowing the internal components of the simulated computer to be observed and modified at runtime, and utilities for designing and simulating custom processors. In this presentation we show how we used the simulator in our computer organization and computer architecture classes to teach assembly programming, I/O, and processor design.

In this paper a new architecture, Speculative-Aware Execution (SAE) is presented that employs speculative-awareness as a means of mitigating the drawbacks of speculative execution which are: useless work (uses speculative values so it produces incorrect results or is done on the wrong path) and redundant work (produces results previously obtained). In order to achieve this, SAE tries to partition the dynamic instruction stream into two disjoint parallel threads: A speculative thread that is partially speculative-aware (p-thread) as it records its speculative state and uses it to avoid useless work (using speculative values) but have no account for its control-flow violations; and a fully speculative-aware thread (f-thread) that has full record of p-thread's speculations, and so can steer p-thread away from incorrect control-flow paths and can accurately identify p-thread's correct work and avoid it, otherwise it would be redundant. By eliminating useless and redundant works, SAE outperforms existing architectures that share similar high-level micro-architecture while incurring only minor hardware additions/changes. Detailed experimental results confirm that SAE indeed reduces the number of useless and redundant computations. We also report an average performance improvement of 18% for the SPEC_INT2000 benchmarks.

This paper presents HMMer-Cell, an implementation of the computationally intensive bioinformatics application HMMER on the Cell/B.E. multiprocessor architecture. The core of the HMMER workload is the Plan7 Viterbi algorithm, which has a memory requirement of O(N*M) where N is the length of the HMM and M is the length of the input sequence length. The main challenge in implementing the Plan7 Viterbi algorithm on the novel Cell/B.E. multiprocessor is the limited local storage space of the Cell/B.E. SPEs (synergistic processing element). We describe our approach to modifying the Viterbi algorithm to reduce the space complexity from 0(M*N) to O(N). We then proceed to discuss design considerations such as task parallelization and code partitioning, in addition to other optimizations we used to implement HMMer-Cell. We demonstrate near-linear speedup when processing relatively larger HMM profiles; and compare our results to those obtained on commodity x86 processors.

Microprocessors are becoming increasingly susceptible to soft errors due to the current trends of semiconductor technology scaling. Traditional redundant multi-threading architectures provide good fault tolerance by re-executing all the computations. However, such a full re-execution significantly increases the demand on the processor resources, resulting in severe performance degradation. To address this problem, this paper introduces a correctness criticality based filter checker, which prioritizes the verification candidates so as to selectively do verification. Binary Correctness Criticality (BCC) and Likelihood of Correctness Criticality (LoCC) are metrics that quantify whether an instruction is important for reliability or how likely an instruction is correctness-critical, respectively. A likelihood of correctness criticality is computed by a value vulnerability factor, which is defined by the numerically significant bit-width used to compute a result. The proposed technique is accomplished by exploiting information redundancy of compressing computationally useful data bits. Based on the likelihood of correctness criticality test, the filter checker mitigates the verification workload by bypassing instructions that are unimportant for correct execution. Extensive measurements prove that the LoCC metric yields quite a wide distribution of values, indicating that it has the potential to differentiate diverse degrees of correctness criticality. Experimental results show that the proposed scheme accelerates a traditional fully-fault-tolerant processor by 1.7 times, while it reduces the soft error rate to 18% of that of a non-fault-tolerant processor.

Recent research has shown that forwarding speculative data to other processors before it is requested can improve the performance of multiprocessor systems. The most recent work in speculative data forwarding places all of the processors on a single bus, allowing the data to be forwarded to all of the processors at the same cost as any subset of the processors. Modern multiprocessors however often employ more complex switching networks in which broadcast is expensive. Accurately predicting the consumers of data can be challenging, especially in the case of programs with many shared data structures. Past consumer predictors rely on simple prediction mechanisms, a single table lookup followed by a static mapping of the table values onto a prediction. We make two main contributions in this paper. First, we show how to reduce the design space of consumer predictors to a set of interesting predictors, and how previous consumer predictors can be tuned to expand the range of available performance. Second, we propose a perceptron consumer predictor that dynamically adapts its reaction to the system behavior, and uses more history information than previous consumer predictors. This predictor outperforms the previous predictors by 21% while using only 1KByte more storage than previous predictors.

We propose a subordinate threading scheme in which the main thread skips instructions that are guaranteed to be correctly executed by the subordinate thread. Speeding up the main thread increases the overall speed of the processor. Also, a faster main thread can detect the subordinate thread's mispredictions earlier, thereby cutting down the amount of time the subordinate thread spends on wrong-path instructions. Hence, the subordinate thread is now free to do more aggressive speculations. We developed a cycle-accurate simulator and evaluated our symbiotic subordinate threading scheme for the SPEC2000 integer benchmarks. Our results show an average performance improvement of 21% over a base subordinate threading scheme that does not let the main thread skip any instructions.

Recent advances in bioinformatics and the significant increase in computational power available to researchers have made it possible to make better use of the vast amounts of genetic data that has been collected over the last two decades. As the uses of genetic data expand to include drug discovery and development of gene-based therapies, bioinformatics is destined to take its place in the forefront of scientific computing application domains. Despite the clear importance of this field, common bioinformatics applications and their implication on microarchitectural design have received scant attention from the computer architecture community so far. The availability of a common set of bioinformatics benchmarks could be the first step to motivate further research in this crucial area. To this end, this paper presents BioBench, a benchmark suite that represents a diverse set of bioinformatics applications. The first version of BioBench includes applications from different application domains, with a particular emphasis on mature genomics applications. The applications in the benchmark are described briefly, and basic execution characteristics obtained on a real processor are presented. Compared to SPEC INT and SPEC FP benchmarks, applications in BioBench display a higher percentage of load/store instructions, almost negligible floating-point operation content, and higher IPC than either SPEC INT or SPEC FP applications. Our evaluation suggests that bioinformatics applications have distinctly different characteristics from the applications in both of the mentioned SPEC suites; and our findings indicate that bioinformatics workloads can benefit from architectural improvements to memory bandwidth and techniques that exploit their high levels of ILP. The entire BioBench suite and accompanying reference data will be made freely available to researchers

As feature sizes are becoming smaller, wire delays are becoming very critical. Clustering is a popular decentralization approach to reduce the impact of shrinking technologies on clock speed. In this approach, the centralized instruction window is replaced with multiple smaller windows, called clusters (PEs). The performance of these clustered processors depends on the amount of inter-PE communication and load imbalance incurred by the distribution algorithm used to distribute instructions among the PEs. In this paper, we investigate a novel approach of reducing the impact of inter-PE communication latency, while preserving good load balance. The basic idea is to selectively replicate instructions in those PEs where their results are required. The replication is done based on heuristics that weigh the potential benefits of replication. We found that, with instruction replication, the IPC of a clustered processor is significantly higher than that obtained without instruction replication and is within just 8 percent of that of a superscalar configuration with a centralized instruction scheduler.

In the evolving submicron technology, making it particularly attractive to use decentralized designs. A common form of decentralization adopted in processors is to partition the execution core into multiple clusters. Each cluster has a small instruction window, and a set of functional units. A number of algorithms have been proposed for distributing instructions among the clusters. The first part of this paper analyzes (qualitatively as well as quantitatively) the effect of various hardware parameters such as the type of cluster interconnect, the fetch size, the cluster issue width, the cluster window size, and the number of clusters on the performance of different instruction distribution algorithms. The study shows that the relative performance of the algorithms is very sensitive to these hardware parameters and that the algorithms that perform relatively better with four or fewer clusters are generally not the best ones for a larger number of clusters. This is important, given that with an imminent increase in the transistor budget, more clusters are expected to be integrated on a single chip. The second part of the paper investigates alternate interconnects that provide scalable performance as the number of clusters is increased. In particular, it investigates two hierarchical interconnects - a single ring of crossbars and multiple rings of crossbars - as well as instruction distribution algorithms to take advantage of these interconnects. Our study shows that these new interconnects with the appropriate distribution techniques achieve an IPC (instructions per cycle) that is 15-20 percent better than the most scalable existing configuration, and is within 2 percent of that achieved by a hypothetical ideal processor having a 1-cycle latency crossbar interconnect. These results confirm the utility and applicability of hierarchical interconnects and hierarchical distribution algorithms in clustered processors.

A larger dynamic scheduler (DS) exposes more instruction level parallelism (ILP), giving better performance. However, a larger DS also results in a longer scheduler latency and a slower clock speed. In this paper, we propose a new DS design that reduces the scheduler critical path latency by reducing the wakeup width (defined as the effective number of results used for instruction wakeup). The design is based on the realization that the average number of results per cycle that are immediately required to wake up the dependent instructions is considerably less than the processor issue width. Our designs are evaluated using the simulation of the SPEC 2000 benchmarks and SPICE simulations of the actual issue queue layouts in 0.18 micron process. We found that a significant reduction in scheduler latency, power consumption and area is achieved with less than 2% reduction in the instructions per cycle (IPC) count for the SPEC2K benchmarks.

Speculative multithreading (SpMT) promises to be an effective mechanism for parallelizing nonnumeric programs, which tend to have irregular and pointer-intensive data structures and complex flows of control. Proper thread formation is crucial for obtaining good speedup in an SpMT system. This paper presents a compiler framework for partitioning a sequential program into multiple threads for parallel execution in an SpMT system. This framework is very general and supports speculative threads, nonspeculative threads, loop-centric threads, and out-of-order thread spawning. It is therefore useful for compiling for a wide variety of SpMT architectures. For effective partitioning of programs, the compiler uses profiling, interprocedural pointer analysis, data dependence information, and control dependence information. The compiler is implemented on the SUIF-MachSUIF platform. A simulation-based evaluation of the generated threads shows that the use of nonspeculative threads and nonloop speculative threads provides a significant increase in speedup for nonnumeric programs.

Power consumption in the register file (RF) forms a considerable fraction of the total power consumption in a chip. With increasing instruction window sizes and issue widths, RF power consumption will suffer a significantly large growth. Using the fact that many of the register values are small and require only a small number of bits for representation, we propose a novel asymmetrically ported RF (to reduce RF power consumption), in which some of the ports can only read/write small-sized values. We experiment with both monolithic and partitioned versions of asymmetrically ported RFs. The power savings in the RF with partitioned asymmetrically ported RF reach as high as 60%. These reductions in RF power consumption come with about 40% improvement in RF access-time and a negligible impact on IPC (instructions per cycle).

There is a growing interest in the use of speculative multithreading to speed up the execution of a program. In speculative multithreading model, threads are extracted from a sequential program and are speculatively executed in parallel, without violating sequential program semantics. In order to get the best performance from this model, a highly accurate thread selection scheme is needed in order to accurately assign threads to processing elements (PEs) for parallel execution. This is done using a thread predictor that assigns threads to PEs sequentially. However, this in-order thread assignment has severe limitations. One of the limitations is when the thread predictor is unable to predict the successor of a particular thread. This may cause successor PEs to remain idle for many cycles. Another limitation has to do with control independence. When a misprediction occurs, all threads, starting from the misprediction point, get squashed, although many of them may be control independent of the misprediction. We present a hierarchical technique for building threads, as well as a nonsequential scheme of assigning them to PEs, and a selective approach to squash threads in case of misprediction, in order to take advantage of control independences. This technique uses dynamic resizing, and builds threads in two steps, statically using the compiler as well as dynamically at run-time. Based on the dynamic behavior of the program, a thread can dynamically expand or shrink in size, and can span several PEs. Detailed simulation results show that our dynamic resizing based approach results in a 11.6% average increase in speedup relative to a conventional speculative multithreaded processor.

Speculative multithreading (SpMT) promises to be very effective for parallelizing non-numeric programs. Data dependences are perhaps the most important factor in the crucial step of deciding the thread boundaries, and SpMT compilers need to estimate data dependences as precisely as possible. Interprocedural points-to and side-effects information is essential to accurately determine data dependences. Determining this information has been an Achilles' heel in SpMT compilation. Existing interprocedural analyses are unsuitable for large programs, as they have high complexity or generate imprecise (very conservative) information that is not useful for aggressive speculative parallelization.This paper presents a novel interprocedural analysis scheme that is highly effective for use in SpMT compilers. It has running time and memory requirement almost linear in the number of procedures in the input program. The information it generates is comparable in accuracy with those generated by highly accurate context-sensitive interprocedural analyses, although it does not guarantee safe information (which is not a requirement for SpMT compilers any way). We implemented this interprocedural analysis in our SpMT compiler, and parallelized large non-numeric programs from the SPEC 2000 suite. Parallel execution of these threads in an SpMT simulator demonstrate good speedups for these non-numeric programs.

Speculative multithreading (SpMT) promises to be an effective mechanism for parallelizing non-numeric programs, which tend to use irregular data structures with pointers and have complex flows of control. Proper thread selection is crucial to obtaining good speedup in an SpMT system. This paper presents a compiler framework for partitioning a sequential program into multiple threads for parallel execution in an SpMT system. This framework is very general, and support a wide variety of threads, such as speculative threads, non-speculative threads, loop-centric threads, and out-of-order thread spawning. To do efficient partitioning, the compiler uses profiling, intra-procedural pointer analysis, data dependence information and control dependence information. Our compiler framework is implemented on the SUIF-MachSUIF platform, and is able to partition large programs, such as the SPEC benchmarks. A simulation-based evaluation of the generated threads shows that an average speedup of 3 can be obtained with 6 processing elements for non-numeric programs. This speedup reduces to 2 if we use only loop-based threads.

Simultaneous Multithreading (SMT) is a technique that permits multiple threads to execute in parallel within a single processor. Usually, an SMT processor uses shared instruction queues to collect instructions from the different threads. Hence, an SMT processor's performance depends on how the instruction fetch unit fills these instruction queues. On each cycle the fetch unit must judiciously decide which threads to fetch instructions from. This paper proposes a new instruction fetch scheme that uses both fetch prioritizing and fetch gating for SMR processors. Fetch prioritizing sets up fetch priority for each thread based on the number of unresolved low-confidence branches from the thread, while fetch gating prevents fetching from a thread once it has a stipulated number of out-standing low-confidence branches. Based on the fetch priority of each thread, our fetch scheme finds threads that are most likely to be in their correct paths. This improves the overall throughput of an SMT processor by reducing the number of wrong-path instructions in the pipeline. Our experimental evaluation shows that, on the average, our fetch scheme provides 14.9% speedup over ICOUNT, which is the best fetch policy reported so far for SMT.

In the sub-micron technology era, wire delays are becoming much more important than gate delays, making it particularly attractive to go for decentralized processors. A number of algorithms have already been proposed for distributing instructions among multiple clusters. In this paper we qualitatively and quantitatively analyze the effect of various hardware parameters on the scalability of different instruction distribution algorithms. Using a set of realistic system parameters, we examine performance differences resulting from different distribution algorithms as well as from specific implementation issues such as the type of interconnect, the fetch size, the cluster issue width, and the cluster window size. Our studies have found that those distribution algorithms that perform relatively better with 4 or fewer clusters are generally not the best ones for a larger number of clusters. Also, the relative performance and scalability of the algorithms are sensitive to different hardware parameters. We also found that, among the existing algorithms, there is no single algorithm that works uniformly best across all hardware configurations. This motivates the need to develop alternate interconnects and instruction distribution algorithms.

Simultaneous Multithreading (SMT) is an execution model that executes multiple threads in parallel within a single processor pipeline. Usually, an SMT processor uses shared instruction queues to collect instructions from the different threads. Hence, an SMT processor’s performance depends on how the instruction fetch unit fills these instruction queues every cycle. In the recent past, many schemes have been proposed for fetching instructions into the SMT pipeline. These schemes focussed on increasing the throughput by using the number of instructions and the number of low confidence branch predictions currently in the pipeline, to decide which threads to fetch from. The goal of this paper is to investigate fetch policies that find a balance between fairness and throughput. We present metrics to quantify fairness. We then discuss techniques to use a set of pipeline system variables for achieving balanced throughput and fairness. Finally, we evaluate several fetch policies. Our evaluation confirms that many of our fetch policies provide a good balance between throughput and fairness.

In order to achieve high performance, wide-issue superscalar processors have to fetch a large number of instructions per cycle. Conditional branches are the primary impediment to increasing the fetch bandwidth because they can potentially alter the flow of control and are very frequent. To overcome this problem, these processors need to predict the outcome of multiple branches in a cycle. This paper investigates two control flow prediction schemes that predict the effective outcome of multiple branches with the help of a single prediction. Instead of considering branches as the basic units of prediction, these schemes consider subgraphs of the control flow graph of the executed program as the basic units of prediction and predict the target of an entire subgraph at a time, thereby allowing the superscalar fetch mechanism to go past multiple branches in a cycle. The first control flow prediction scheme investigated considers sequential block-like subgraphs and the second scheme considers tree-like subgraphs to make the control flow predictions. Both schemes do a 1-out-of-4 prediction as opposed to the 1-out-of-2 prediction done by branch-level prediction schemes. These two schemes are evaluated using a MIPS ISA-based 12-way superscalar microarchitecture. An improvement in effective fetch size of approximately 25 percent and 50 percent, respectively, is observed over identical microprocessors that use branch-level prediction. No appreciable difference in the prediction accuracy was observed, although the control flow prediction schemes predicted 1-out-of-4, outcomes.

Recent fascination for dynamic scheduling as a means for exploiting instruction-level parallelism has introduced significant interest in the scalability aspects of dynamic scheduling hardware. In order to overcome the scalability problems of centralized hardware schedulers, many decentralized execution models are being proposed and investigated recently. The crux of all these models is to split the instruction window across multiple processing elements (PEs) that do independent, scheduling of instructions. The decentralized execution models proposed so far can be grouped under 3 categories, based on the criterion used for assigning an instruction to a particular PE. They are: (i) execution unit dependence based decentralization (EDD), (ii) control dependence based decentralization (CDD), and (iii) data dependence based decentralization (DDD). This paper investigates the performance aspects of these three decentralization approaches. Using a suite of important benchmarks and realistic system parameters, we examine performance differences resulting from the type of partitioning as well as from specific implementation issues such as the type of PE interconnect.We found that with a ring-type PE interconnect, the DDD approach performs the best when the number of PEs is moderate, and that the CDD approach performs best when the number of PEs is large. The currently used approach---EDD---does not perform well for any configuration. With a realistic crossbar, performance does not increase with the number of PEs for any of the partitioning approaches. The results give insight into the best way to use the transistor budget available for implementing the instruction window.

Data dependences (data flow constraints) present a major hurdle to the amount of instruction-level parallelism that can be exploited from a program. Recent work has focused on the use of data value prediction to overcome the limits imposed by data dependences. That is, when an instruction is fetched, its result can be predicted so that subsequent instructions that depend on the result can execute earlier using the predicted value. When the correct result becomes available, it is compared against the value predicted earlier, so as to validate the prediction. Whereas significant work has been done towards developing schemes for accurately predicting data values, not much work has been done towards understanding and quantifying the performance impact of data value prediction. This paper presents a quantitative study of the impact of data value prediction on available parallelism. Our studies, done with the MIPS instruction set and a collection of SPEC95 integer benchmarks, show that data value prediction provides significant increases in available parallelism when infinite size instruction window and perfect branch prediction are used. Our studies with finite size windows shows that the impact of data value prediction is not very significant for small window sizes such as 64. When the instruction window size is increased, the benefits of data value prediction become more apparent.

In order to fetch a large number of instructions per cycle from a sequential program, wide-issue superscalar processors have to predict the outcome of multiple branches in a cycle, and fetch instructions from non-contiguous portions of code. Past research has developed schemes that predict the outcome of multiple branches by means of a single prediction. That is, instead of predicting the outcome of every conditional branch, a tree-like subgraph of the control flow graph of the executed program is considered as a single prediction unit, and a path is predicted through the tree, thereby allowing the superscalar fetch mechanism to go past multiple branches per cycle. This paper investigates the potential of dynamically modifying the tree structure by pruning the rarely seen paths and extending the frequently seen paths, so as to increase the average fetch size. It discusses the procedure used for tree modifications, and presents the path length and prediction accuracy obtainable with this approach using the SPEC '95 integer benchmarks and the MIPS instruction set.

Data dependences (data flow constraints) present a stubborn resistance to the amount of instruction-level parallelism that can be exploited from a program. Recent work has suggested that the limits imposed by data dependences can be overcome to some extent with the use of data value prediction. That is, when an instruction is fetched, its result can be predicted so that subsequent instructions that depend on the result can use this predicted value. When the correct result becomes available, all instructions that are data-dependent on that prediction can be validated. This paper investigates a variety of techniques to carry out highly accurate data value predictions. The first technique investigates the potential of using correlation in data value predictions. The second technique investigates the potential of monitoring the strides by which the results produced by different instances of an instruction change. The third technique investigates the potential of pattern-based two-level prediction schemes. The paper also presents the results from a simulation study that we conducted to verify the potential of the investigated prediction schemes. The results show that highly accurate data valve predictions are possible with two of the investigated schemes.

The multiscalar processing model extracts instruction level parallelism from ordinary programs by splitting the program into smaller, possibly dependent, tasks, and parallelly executing multiple tasks using multiple execution units. Past work had advocated pursuing multiple flows of control in the multiscalar processor. We first illustrate the problems involved in pursuing multiple flows of control. We then discuss a methodology to obtain good performance from multiple tasks extracted from a single line of control. We also present the results of simulation studies that verify the potential of this method. These results, obtained with a set of SPECS92 benchmarks, show better issue rates when a single line of control is pursued in the multiscalar processor. The primary reason for this improvement is the ability to have better load balancing among the execution units.

Data dependences (data flow constraints) present a major hurdle to the amount of instruction-level parallelism that can be exploited from a program. Recent work has suggested that the limits imposed by data dependences can be overcome to some extent with the use of data value prediction. That is, when an instruction is fetched, its result can be predicted so that subsequent instructions that depend on the result can use this predicted value. When the correct result becomes available, all instructions that are data dependent on that prediction can be validated. This paper investigates a variety of techniques to carry out highly accurate data value predictions. The first technique investigates the potential of monitoring the strides by which the results produced by different instances of an instruction change. The second technique investigates the potential of pattern-based two-level prediction schemes. Simulation results of these two schemes show improvements over the existing method of predicting the last outcome. In particular, some benchmarks show improvement with the stride-based predictor and others show improvement with the pattern-based predictor. To do uniformly well across benchmarks, we combine these two predictors to form a hybrid predictor. Simulation analysis of the hybrid predictor shows its overall prediction accuracy to be better than that of the component predictors across all benchmarks.

In this paper, we investigate techniques to incorporate fault tolerance in superscalar processors, the de facto execution model for building processors today. We first analyze the different ways in which errors can manifest when faults occur in various parts of a superscalar processor. We then describe different ways of detecting and recovering from these errors, and the merits and demerits of these schemes. Finally, we present the results of a simulation study conducted to determine the performance loss incurred due to the introduction of these fault tolerance schemes. These results suggest that fault tolerance can be incorporated in superscalar processors, with low hardware overhead, low performance overhead, and good error coverage.

The multiscalar processing model is a recently proposed model for exploiting large amounts of instruction level parallelism from programs written in ordinary, high-level languages. It splits a sequential program into smaller tasks, and exploits instruction level parallelism by executing multiple tasks in parallel using multiple execution units. The parallelly executed tasks can have both control and data dependencies between them. Because the original sequential program was not written with the multiscalar processing model in mind, it is difficult to get good performance without doing further, multiscalar-specific code scheduling. This paper compares two different ways of doing multiscalar-specific dynamic scheduling. In the first method, each execution unit has a scheduling hardware that collects decoded instructions in a buffer, and reorders them based on the run-time availability of dates. Although additional parallelism is extracted by this run-time reordering, the reordering hardware is in the critical path of program execution, and can potentially impact the cycle time. In the second approach that we investigate, called dynamic off-line scheduling, the reordering hardware is in a non-critical path of instruction execution. The off-line scheduling hardware observes the execution behavior of the instructions in a task, and reorders them with a view to speed up the task's execution the next time the task is executed. The paper presents the results of simulation studies that were conducted using the SPEC benchmarks to evaluate both of these scheduling strategies for the multiscalar processor.

To exploit instruction level parallelism, it is important not only to execute multiple memory references per cycle, but also to reorder memory references-especially to execute loads before stores that precede them in the sequential instruction stream. To guarantee correctness of execution in such situations, memory reference addresses have to be disambiguated. This paper presents a novel hardware mechanism, called an Address Resolution Buffer (ARB), for performing dynamic reordering of memory references. The ARB supports the following features: (1) dynamic memory disambiguation in a decentralized manner, (2) multiple memory references per cycle, (3) out-of-order execution of memory references, (4) unresolved loads and stores, (5) speculative loads and stores, and (6) memory renaming. The paper presents the results of a simulation study that we conducted to verify the efficacy of the ARB for a superscalar processor. The paper also shows the ARB's application in a multiscalar processor.

State-of-the-art RAM chips are designed with spare rows and columns for reconfiguration purposes. After a RAM chip is reconfigured, physically adjacent spare cells may no longer have consecutive logical addresses. Another aspect that results in distinct logical and physical neighborhoods in RAM's is the scrambling of address lines, necessitated by the need to minimize the overall silicon area and the critical path lengths. Test algorithms used to test reconfigured RAM's and scrambled address RAM's for the detection of physical neighborhood pattern sensitive faults have to consider that the physical and logical neighborhoods are different and that the address mapping of the reconfigured RAM is no longer available. In this paper, we present a test algorithm that detects static five-cell physical neighborhood pattern sensitive faults in reconfigured RAMs and RAMs with scrambled address lines. This algorithm is based on the widely used MSCAN and Marching test algorithms, and requires only O(N[log/sub 2/N]) reads and writes to test an N-bit RAM array.

Cellular automata based signature analyzers are becoming very popular for compressing test responses in built-in self-test applications. Off-line determination of signatures (both good circuit signature and faulty circuit signatures) is a compute-intensive process that involves cycle-by-cycle simulation of the signature analyzer. In this paper, we investigate a technique for speeding up the simulation of cellular automata-based multi-input signature registers (C-MISRs). First, we describe a technique for converting a C-MISR into an equivalent single input circuit. We then present an algorithm for parallelizing the simulation of these single input circuits.

In order to fetch a large number of instructions per cycle, wide-issue superscalar processors have to predict the outcome of multiple branches in a cycle, and fetch instruction blocks from multiple targets. This paper investigates a control flow prediction scheme that predicts the outcome of multiple branches by performing a single prediction. Instead of predicting the outcome of each individual conditional branch, this scheme considers a tree-like subgraph of the control flow graph of the executed program as a single prediction unit, and predicts the target of a subgraph at a time, thereby allowing the superscalar fetch mechanism to go past multiple branches per cycle. This approach is evaluated using the MIPS architecture, for a 12-way superscalar processor, and an improvement in effective fetch size of more than 50%, over an identical processor that uses branch prediction is observed for the SPEC integer benchmarks. No appreciable difference in the prediction accuracy was observed although the control flow prediction scheme predicted one out of four outcomes.

Current superscalar processors, both RISC and CISC, require substantial instruction fetch and decode bandwidth to keep multiple functional units utilized. While CISC instructions can sometimes provide reduced fetch bandwidth requirements, they are correspondingly more difficult to decode. A hardware assist, called a fill unit, can dynamically collect decoded microoperations into a decoded instruction cache. Future code fetches to those locations can be satisfied out of this cache and thus bypass the decoding logic. This approach is investigated using the Intel x86 architecture, and a speedup of approximately a factor of two over a P6-like decoding structure is seen for the three SPEC benchmarks investigated. This design is accompanied by a microengine-register allocation and renaming scheme that prevents the increased supply of microoperations from placing excessive demands on the normal register renaming hardware.

Multiple issue of instructions occurs in superscalar and VLIW machines. The paper investigates a third type of machine design, which combines the advantages of code compatibility as in superscalars and the absence of complex dependency-checking logic from the decoder as in VLIW. In this design, a stream of scalar instructions is executed by the hardware and is simultaneously compacted into VLIW-type instructions, which are then stored in a structure called a shadow cache. When a shadow cache line contains the instructions requested by the fetch unit, the scalar instruction stream is preempted and all operations in the shadow cache line are simultaneously issued and executed. The mechanism that compacts instructions is called a fill unit, and was first proposed for dynamically compacting macrooperations into large executable units by Melvin, Shebanow, and Patt in 1988. We have extended their approach to directly handle data dependencies, delayed branches, and speculative execution (using branch prediction). This approach is evaluated using the MIPS architecture, and a six-functional-unit machine is found to be 52 to 108% faster than a single-issue processor for unrecompiled SPECint92 benchmarks.

RAM decoders are designed with a view to minimize the overall silicon area and critical path lengths. This can result in designs in which-physically adjacent rows (and columns) are not logically adjacent. Even if physically adjacent rows (and columns) are logically adjacent, there are other issues that preclude the possibility of identical physical and logical addresses. State-of-the-art memory chips are designed with spare rows and spare columns for reconfiguration purposes. After a memory chip is reconfigured, physically adjacent cells may no longer have consecutive logical addresses. Test algorithms used at later stages for the detection of physical neighborhood pattern sensitive faults have to consider the fact that the address mapping of the memory chip is no longer available. We present test algorithms to detect 5-cell and 9-cell physical neighborhood pattern sensitive faults and arbitrary 3-coupling faults, even if the logical and physical addresses are different and the physical-to-logical address mapping is not available. These algorithms have test lengths of O(N[log/sub 3/N]/sup 4/) and O(N[log/sub 3/N]/sup 2/), respectively, for N-bit RAMs, and are especially suited for testing reconfigured DRAMs. They also detect other conventional faults such as stuck-at faults and decoder faults. These test algorithms are based on efficiently identifying all triplets of objects among a group of n objects. We formulated this triplet identification problem as a hypergraph coloring problem, and developed an efficient 3-coloring algorithm that colors the n vertices of a complete uniform hypergraph of rank 3 such that each edge of the hypergraph is trichromatically colored in at most [log/sub 3/n]/sup 2/ coloring steps.>

Addresses a two-fold question: whether there is enough parallelism in numeric and non-numeric workloads, such as the SPEC92 benchmark suite, under ideal conditions, disregarding any resource constraints and more importantly, whether a high ideal parallelism can be further characterized to assess its extractability with finite resources. The authors have designed and implemented an analysis tool that accepts as input a dynamic execution trace from an IBM RS/6000 environment, and outputs a parallelized instruction trace (schedule) that could be executed on an abstract machine with unlimited functional units and various constraints on the rest of its resources, namely, registers, stack and memory. They also analyze two different instruction scheduling policies: greedy and lazy. The paper further offers a characterization of ideal parallelism (obtainable on a machine with infinite resources) using a measure called slack to assess its sustainability with finite resources.>

We propose a new processing paradigm, called the Expandable Split Window (ESW) paradigm, for exploiting fine-grain parallelism. This paradigm considers a window of instructions (possibly having dependencies) as a single unit, and exploits fine-grain parallelism by overlapping the execution of multiple windows. The basic idea is to connect multiple sequential processors, in a decoupled and decentralized manner, to achieve overall multiple issue. This processing paradigm shares a number of properties of the restricted dataflow machines, but was derived from the sequential von Neumann architecture. We also present an implementation of the Expandable Split Window execution model, and preliminary performance results.

This paper considers the design of a data memory hierarchy, with a level 1 (L1) data cache at the top, to support the data bandwidth demands of a future-generation superscalar processor capable of issuing about ten instructions per clock cycle.It introduces the notion of cache bandwidfh -the bandwidth with which a cache can accept requests from the processor -and shows how the bandwidth of a standard, blocking cache, can degrade greatly because of its inability to overlap the service of misses.Non-blocking or lockup-free caches are discussed as a way of reducing the bandwidth degradation due to misses.To improve the data bandwidth to greater than 1 request per cycle, multi-port, interleaved caches are introduced.Simulation results from a cycle-by-cycle simulator, using the MIPS R2000 instruction set, suggest that memory hierarchies with blocking L 1 caches will be unable to support the bandwidth demands of futuregeneration superscalar processors.Multi-port, nonblocking (MPNB) L1 caches introduced in this paper for the top of the data memory hierarchy appear to be capable of supporting such data bandwidth demands.

State-of-the-art memory chips are designed with spare rows and columns for reconfiguration purposes. After a memory chip is reconfigured, physically adjacent cells may no longer have consecutive logical addresses. Test algorithms used at later stages for the detection of physical neighborhood pattern sensitive faults have to consider the fact that the address mapping of the memory chip is no longer available. Furthermore, RAM decoders are designed with a view to minimize the overall silicon area and critical path lengths. This can also result in designs in which physically adjacent rows (and columns) are not logically adjacent. In this paper, we present new test algorithms to detect 5-cell and 9-cell physical neighborhood pattern sensitive faults in dynamic RAMs, even if the logical and physical addresses are different and the physical-to-logical address mapping is not available. These algorithms have test lengths of O(Nr10g3M4) for N-bit RAMs, and also detect other faults such as stuck-at and coupling faults. The algorithms depend on the development of an efficient 3-coloring algorithm that michromatically colors all the triplets among a group off n objects in at most r1og34 coloring steps.

A novel fault model is developed for random-access memories for a class of pattern-sensitive faults called row/column weight-sensitive faults. A test procedure is developed to detect faults from the defined fault model. This test sequence also tests the memory array for the 5-cell-neighborhood static pattern-sensitive faults and other faults, such as stuck-at-faults and coupling faults. A built-in self-test (BIST) version of the algorithm has been implemented by completing the logic design and layout in 2- mu m CMOS technology. The silicon area overhead for a 4M RAM is as little as 0.8%. The number of extra pins can be as low as one if clock is available on-chip. The number of extra pins can be as low as one if clock is available on-chip. The delay introduced to the normal paths, as estimated by simulation tools, is small and can be reduced even further.>