Value level parallelism (VLP) has been proposed to improve the efficiency of large-batch, low-precision general matrix multiply (GEMM) between symmetric activations and weights. In transformer based large language models (LLMs), there exist more sophisticated operations beyond activation-weight GEMM. In this paper, we explore how VLP benefits LLMs. First, we generalize VLP for nonlinear approximations, outperforming existing nonlinear approximations in end-to-end LLM accuracy, performance, and efficiency. Our VLP approximation follows a value-centric approach, where important values are assigned with greater accuracy. Second, we optimize VLP for small-batch GEMMs with asymmetric inputs efficiently, which leverages timely LLM optimizations, including weight-only quantization, key-value (KV) cache quantization, and group query attention. Finally, we design a new VLP architecture, Mugi, to encapsulate the innovations above and support full LLM workloads, while providing better performance, efficiency and sustainability. Our experimental results show that Mugi can offer significant improvements on throughput and energy efficiency, up to $45\times$ and $668\times$ for nonlinear softmax operations, and $2.07\times$ and $3.11\times$ for LLMs, and also decrease operational carbon for LLM operation by $1.45\times$ and embodied carbon by $1.48\times$.

Large Language Model (LLM) inference is widely used in interactive assistants and agentic systems. In latencysensitive deployments, inference time can become dominated by host-side overheads. Existing approaches typically expose this cost only as an aggregate residual or a launch/queue metric, which is often insufficient to identify which execution layer should be optimized. This work presents TaxBreak, a tracedriven methodology for decomposing host-visible orchestration overhead into three components: framework translation time, CUDA library translation time, and kernel launch-path time. We validate TaxBreak on NVIDIA H100 and H200 systems and use it to derive our proposed Host-Device Balance Index (HDBI), a boundedness summary index that relates device-active execution to host-visible orchestration. Across representative dense and mixture-of-experts workloads in both prefill and decode, we show that aggregate latency, GPU inactivity, or boundedness ratios alone can obscure the dominant optimization target. TaxBreak instead distinguishes cases where optimization should reduce software-stack overhead from cases where the primary win comes from reducing device-side work. We further show that MoE models dispatch $\mathbf{8 - 1 1} \times$ more kernels per output token than dense models, and that for such host-bound workloads, CPU singlethread performance is a first-order parameter: a faster host CPU reduces orchestration overhead by $\mathbf{1 0}-\mathbf{2 9} \boldsymbol{\%}$ and improves end-toend latency by up to $14 \%$, even when paired with a slowerclocked GPU. These results position TaxBreak as a diagnostic tool for assessing whether optimization effort should target the software stack or the device-side workload execution.

The increasing complexity of deep neural networks (DNNs) poses significant challenges for edge inference deployment due to resource and power constraints of edge devices. Recent works on unary-based matrix multiplication hardware aim to leverage data sparsity and low-precision values to enhance hardware efficiency. However, the adoption and integration of such unary hardware into commercial deep learning accelerators (DLA) remain limited due to processing element (PE) array dataflow differences. This work presents Tempus Core, a convolution core with highly scalable unary-based PE array comprising of tub (temporal-unary-binary) multipliers that seamlessly integrates with the NVDLA (NVIDIA's open-source DLA for accelerating CNNs) while maintaining dataflow compliance and boosting hardware efficiency. Analysis across various datapath granularities shows that for INT8 precision in 45nm CMOS, Tempus Core's PE cell unit (PCU) yields 59.3% and 15.3% reductions in area and power consumption, respectively, over NVDLA's CMAC unit. Considering a 16x16 PE array in Tempus Core, area and power improves by 75% and 62%, respectively, while delivering 5x and 4x iso-area throughput improvements for INT8 and INT4 precisions. Post-place and route analysis of Tempus Core's PCU shows that the 16x4 PE array for INT4 precision in 45nm CMOS requires only 0.017mm2die area and consumes only 6.2mW of total power. We demonstrate that area-power efficient unary-based hardware can be seamlessly integrated into conventional DLAs, paving the path for efficient unary hardware for edge AI inference.

Large language model (LLM)-based inference workloads increasingly dominate data center costs and resource utilization. Therefore, understanding the inference workload characteristics on evolving CPU-GPU coupled architectures is crucial for optimization. This paper presents an in-depth analysis of LLM inference behavior on loosely-coupled (PCIe A100/H100) and closely-coupled (GH200) systems. We analyze performance dynamics using fine-grained operator-to-kernel trace analysis, facilitated by our novel profiler SKIP and metrics like Total Kernel Launch and Queuing Time (TKLQT). Results show that closely-coupled (CC) GH200 significantly outperforms loosely-coupled (LC) systems at large batch sizes, achieving 1.9x-2.7x faster prefill latency for Llama-3.2-1B. However, our analysis also reveals that GH200 remains CPU-bound up to 4x larger batch sizes than LC systems. In this extended CPU-bound region, we identify the performance characteristics of the Grace CPU as a key factor contributing to higher inference latency at low batch sizes on GH200. We demonstrate that TKLQT accurately identifies this CPU/GPU-bound transition point. Based on this analysis, we further show that kernel fusion offers significant potential to mitigate GH200's low-batch latency bottleneck by reducing kernel launch overhead. This detailed kernel-level characterization provides critical insights for optimizing diverse CPU-GPU coupling strategies. This work is an initial effort, and we plan to explore other major AI/DL workloads that demand different degrees of CPU-GPU heterogeneous architectures.

General Matrix Multiply (GEMM) units, consisting of multiply-accumulate (MAC) arrays, perform bulk of the computation in deep learning (DL). Recent work has proposed a novel MAC design, Bit-Pragmatic (PRA), capable of dynamically exploiting bit sparsity. This work presents OzMAC (Omit-zero-MAC), a modified re-implementation of PRA, but extends beyond earlier works by performing rigorous post-synthesis evaluation against binary MAC design across multiple bitwidths and clock frequencies using TSMC N5 process node to assess commercial implementation potential. We demonstrate the existence of high bit sparsity in eight pretrained INT8 DL workloads and show that 8-bit OzMAC improves all three metrics of area, power, and energy significantly by 21%, 70%, and 28%, respectively. Similar improvements are achieved when scaling data precisions (4, 8, 16 bits) and clock frequencies (0.5 GHz, 1 GHz, 1.5 GHz). For the 8-bit OzMAC, scaling its frequency to normalize the throughput, it still achieves 30% improvement on both power and energy.

General matrix multiplication (GEMM) is a ubiqui-tous computing kernel/algorithm for data processing in diverse applications, including artificial intelligence (AI) and deep learning (DL). Recent shift towards edge computing has inspired GEMM architectures based on unary computing, which are predominantly stochastic and rate-coded systems. This paper proposes a novel GEMM architecture based on temporal-coding, called tuGEMM, that performs exact computation. We introduce two variants of tuGEMM, serial and parallel, with distinct area/power-latency trade-offs. Post-synthesis Power-Performance-Area (PPA) in 45 nm CMOS are reported for 2-bit, 4-bit, and 8-bit computations. The designs illustrate significant advantages in area-power efficiency over state-of-the-art stochastic unary systems especially at low precisions, e.g. incurring just 0.03 mm2and 9 mW for 4 bits, and 0.01 mm2and 4 mW for 2 bits. This makes tuGEMM ideal for power constrained mobile and edge devices performing always-on real-time sensory processing.

IoT (Internet of Things) devices, such as network-enabled wearables, are carried by increasingly more people throughout daily life. Information from multiple devices can be aggregated to gain insights into a person’s behavior or status. For example, an elderly care facility could monitor patients for falls by combining fitness bracelet data with video of the entire class. For this aggregated data to be useful to each person, we need a multi-modality association of the devices’ physical ID (i.e., location, the user holding it, visual appearance) with a virtual ID (e.g., IP address/available services). Existing approaches for multi-modality association often require intentional interaction or direct line-of-sight to the device, which is infeasible for a large number of users or when the device is obscured by clothing. We present IDIoT , a calibration-free passive sensing approach that fuses motion sensor information with camera footage of an area to estimate the body location of motion sensors carried by a user. We characterize results across three baselines to highlight how different fusing methodology results better than earlier IMU-vision fusion algorithms. From this characterization, we determine IDIoT is more robust to errors such as missing frames or miscalibration that frequently occur in IMU-vision matching systems.

Unsupervised time series clustering is a challenging problem with diverse industrial applications such as anomaly detection, bio-wearables, etc. These applications typically involve small, low-power devices on the edge that collect and process real-time sensory signals. State-of-the-art time-series clustering methods perform some form of loss minimization that is extremely computationally intensive from the perspective of edge devices. In this work, we propose a neuromorphic approach to unsupervised time series clustering based on Temporal Neural Networks that is capable of ultra low-power, continuous online learning. We demonstrate its clustering performance on a subset of UCR Time Series Archive datasets. Our results show that the proposed approach either outperforms or performs similarly to most of the existing algorithms while being far more amenable for efficient hardware implementation. Our hardware assessment analysis shows that in 7 nm CMOS the proposed architecture, on average, consumes only about 0.005 mm2die area and 22 μW power and can process each signal with about 5 ns latency.

Touch surfaces are intuitive interfaces for computing devices. Most of the traditional touch interfaces (vision, IR, capacitive, etc.) have mounting requirements, resulting in specialized touch surfaces limited by their size, cost, and mobility. More recent work has shown that vibration-based touch sensing techniques can localize taps/knocks, which provides a low-cost flexible alternative. These surfaces are envisioned as intuitive inputs for applications such as interactive meeting tables, smart kitchen appliance control, etc. However, due to dispersive and reflective properties of various vibrating mediums, it is difficult to localize taps accurately on ubiquitous surfaces. Furthermore, no work has been done on tracking continuous swipe interactions through vibration sensing.

This paper presents the Mitosis framework, which is a combined hardware-software approach to speculative multithreading, even in the presence of frequent dependences among threads. Speculative multithreading increases single-threaded application performance by exploiting thread-level parallelism speculatively - that is, executing code in parallel even when the compiler or runtime system cannot guarantee the parallelism exists. The proposed approach is based on predicting/computing thread input values via software, through a piece of code that is added at the beginning of each thread (the pre-computation slice). A pre-computation slice is expected to compute the correct thread input values most of the time, but not necessarily always. This allows aggressive optimization techniques to be applied to the slice to make it very short. This paper focuses on the microarchitecture that supports this execution model. The primary novelty of the microarchitecture is the hardware support for the execution and validation of pre-computation slices. Additionally, this paper presents new architectures for the register file and the cache memory in order to support multiple versions of each variable and allow for efficient roll-back in case of misspeculation. We show that the proposed microarchitecture, together with the compiler support, achieves an average speedup of 2.2 for applications that conventional non-speculative approaches are not able to parallelize at all.

Microprocessor design is undergoing a major paradigm shift towards multi-core designs, in anticipation that future performance gains will come from exploiting threadlevel parallelism in the software. To support this trend, we present a novel processor architecture called the Multiple Instruction Stream Processing (MISP) architecture. MISP introduces the sequencer as a new category of architectural resource, and defines a canonical set of instructions to support user-level inter-sequencer signaling and asynchronous control transfer. MISP allows an application program to directly manage user-level threads without OS intervention. By supporting the classic cache-coherent shared-memory programming model, MISP does not require a radical shift in the multithreaded programming paradigm. This paper describes the design and evaluation of the MISP architecture for the IA-32 family of microprocessors. Using a research prototype MISP processor built on an IA-32-based multiprocessor system equipped with special firmware, we demonstrate the feasibility of implementing the MISP architecture. We then examine the utility of MISP by (1) assessing the key architectural tradeoffs of the MISP architecture design and (2) showing how legacy multithreaded applications can be migrated to MISP with relative ease.

3D die stacking is an exciting new technology that increases transistor density by vertically integrating two or more die with a dense, high-speed interface. The result of 3D die stacking is a significant reduction of interconnect both within a die and across dies in a system. For instance, blocks within a microprocessor can be placed vertically on multiple die to reduce block to block wire distance, latency, and power. Disparate Si technologies can also be combined in a 3D die stack, such as DRAM stacked on a CPU, resulting in lower power higher BW and lower latency interfaces, without concern for technology integration into a single process flow. 3D has the potential to change processor design constraints by providing substantial power and performance benefits. Despite the promising advantages of 3D, there is significant concern for thermal impact. In this research, we study the performance advantages and thermal challenges of two forms of die stacking: Stacking a large DRAM or SRAM cache on a microprocessor and dividing a traditional micro architecture between two die in a stack

This paper is motivated by three recent trends in computer design. First, chip multi-processors (CMPs) with increasing numbers of CPU cores per chip are becoming common. Second, multi-threaded software that can take advantage of CMPs will soon become prevalent. Due to the nature of the algorithms, these multi-threaded programs inherently will have phases of sequential execution; Amdahl's law dictates that the speedup of such parallel programs will be limited by the sequential portion of the computation. Finally, increasing levels of on-chip integration coupled with a slowing rate of reduction in supply voltage make power consumption a first order design constraint. Given this environment, our goal is to minimize the execution times of multi-threaded programs containing nontrivial parallel and sequential phases, while keeping the CMP's total power consumption within a fixed budget. In order to mitigate the effects of Amdahl's law, in this paper we make a compelling case for varying the amount of energy expended to process instructions according to the amount of available parallelism. Using the equation, Power-Energy per instruction (EPI) * Instructions per second (IPS), we propose that during phases of limited parallelism (low IPS) the chip multi-processor will spend more EPI; similarly, during phases of higher parallelism (high IPS) the chip multi-processor will spend less EPI; in both scenarios power is fixed. We evaluate the performance benefits of an EPI throttle on an asymmetric multiprocessor (AMP) prototyped from a physical 4-way Xeon SMP server. Using a wide range of multi-threaded programs, we show a 38% wall clock speedup on an AMP compared to a standard SMP that uses the same power. We also measure the supply current on a 4-way SMP server while running the multi-threaded programs and use the measured data as input to a software simulator that implements a more flexible EPI throttle. The results from the measurement-driven simulation show performance benefits comparable to the AMP prototype. We analyze the results from both techniques, explain why and when an EPI throttle works well, and conclude with a discussion of the challenges in building practical EPI throttles.

Helper threading is a technology to accelerate a program by exploiting a processor's multithreading capability to run ``assist'' threads. Previous experiments on hyper-threaded processors have demonstrated significant speedups by using helper threads to prefetch hard-to-predict delinquent data accesses. In order to apply this technique to processors that do not have built-in hardware support for multithreading, we introduce virtual multithreading (VMT), a novel form of switch-on-event user-level multithreading, capable of fly-weight multiplexing of event-driven thread executions on a single processor without additional operating system support. The compiler plays a key role in minimizing synchronization cost by judiciously partitioning register usage among the user-level threads. The VMT approach makes it possible to launch dynamic helper thread instances in response to long-latency cache miss events, and to run helper threads in the shadow of cache misses when the main thread would be otherwise stalled.The concept of VMT is prototyped on an Itanium ® 2 processor using features provided by the Processor Abstraction Layer (PAL) firmware mechanism already present in currently shipping processors. On a 4-way MP physical system equipped with VMT-enabled Itanium 2 processors, helper threading via the VMT mechanism can achieve significant performance gains for a diverse set of real-world workloads, ranging from single-threaded workstation benchmarks to heavily multithreaded large scale decision support systems (DSS) using the IBM DB2 Universal Database. We measure a wall-clock speedup of 5.8% to 38.5% for the workstation benchmarks, and 5.0% to 12.7% on various queries in the DSS workload.

Pre-execution techniques have received much attention as an effective way of prefetching cache blocks to tolerate the ever-increasing memory latency. A number of pre-execution techniques based on hardware, compiler, or both have been proposed and studied extensively by researchers. They report promising results on simulators that model a simultaneous multithreading (SMT) processor. We apply the helper threading idea on a real multithreaded machine, i.e., Intel Pentium 4 processor with hyper-threading technology, and show that indeed it can provide wall-clock speedup on real silicon. To achieve further performance improvements via helper threads, we investigate three helper threading scenarios that are driven by automated compiler infrastructure, and identify several key challenges and opportunities for novel hardware and software optimizations. Our study shows a program behavior changes dynamically during execution. In addition, the organizations of certain critical hardware structures in the hyper-threaded processors are either shared or partitioned in the multithreading mode and thus, the tradeoffs regarding resource contention can be intricate. Therefore, it is essential to judiciously invoke helper threads by adapting to the dynamic program behavior so that we can alleviate potential performance degradation due to resource contention. Moreover, since adapting to the dynamic behavior requires frequent thread synchronization, having light-weight thread synchronization mechanisms is important.

This paper proposes and evaluates hardware mechanisms for supporting prescient instruction prefetch — an approach to improving single-threaded application performance by using helper threads to perform instruction prefetch. We demonstrate the need for enabling store-to-load communication and selective instruction execution when directly pre-executing future regions of an application that suffer I-cache misses. Two novel hardware mechanisms, safe-store and YAT-bits, are introduced that help satisfy these requirements. This paper also proposes and evaluates .nite state machine recall, a technique for limiting pre-execution to branches that are hard to predict by leveraging a counted I-prefetch mechanism. On a research Itanium®SMT processor with next line and streaming I-prefetch mechanisms that incurs latencies representative of next generation processors, prescient instruction prefetch can improve performance by an average of 10.0% to 22% on a set of SPEC 2000 benchmarks that suffer significant I-cache misses. Prescient instruction prefetch is found to be competitive against even the most aggressive research hardware instruction prefetch technique: fetch directed instruction prefetch.

This paper describes the tradeoff between latency performance and throughput performance in a power-constrained environment. We show that the key to achieving both excellent latency performance as well as excellent throughput performance is to dynamically vary the amount of energy expended to process instructions according to the amount of parallelism available in the software. We survey four techniques for achieving variable energy per instruction: voltage/frequency scaling, asymmetric cores, variable-size cores, and speculation control. We estimate the potential range of energies obtainable by each technique and conclude that a combination of asymmetric cores and voltage/frequency scaling offers the most promising approach to design a chip-level multiprocessor that can achieve both excellent latency performance and excellent throughput performance.

On-line transaction processing (OLTP) workloads are crucial benchmarks for the design and analysis of server processors. Typical cached configurations used by researchers to simulate OLTP workloads are orders of magnitude smaller than the fully scaled configurations used by OEM vendors to achieve world-record transaction processing throughput. The objective of this study is to discover the underlying relationships that characterize OLTP performance over a wide range of configurations. To this end, we have derived the "iron law" of database performance. Using our iron law, we show that both the average instructions executed per transaction (IPX) and the average cycles per instruction (CPI) are critical to the transaction-throughput performance. We use an extensive, empirical examination of an Oracle based commercial OLTP workload on an Intel Xeon multiprocessor system to characterize the scaling behaviour of both the IPX and the CPI. We demonstrate that across a wide range of configurations the IPX and CPI behaviour follows predictable trends, which can be accurately characterized by simple linear or piece-wise linear approximations. Based on our data, we propose a method for selecting a minimal, representative workload configuration from which behaviours of much larger OLTP configurations can be accurately extrapolated.

This paper describes a framework for modeling macroscopic program behavior and applies it to optimizing prescient instruction prefetch -- novel technique that uses helper threads to improve single-threaded application performance by performing judicious and timely instruction prefetch. A helper thread is initiated when the main thread encounters a spawn point, and prefetches instructions starting at a distant target point. The target identifies a code region tending to incur I-cache misses that the main thread is likely to execute soon, even though intervening control flow may be unpredictable. The optimization of spawn-target pair selections is formulated by modeling program behavior as a Markov chain based on profile statistics. Execution paths are considered stochastic outcomes, and aspects of program behavior are summarized via path expression mappings. Mappings for computing reaching, and posteriori probability; path length mean, and variance; and expected path footprint are presented. These are used with Tarjan's fast path algorithm to efficiently estimate the benefit of spawn-target pair selections. Using this framework we propose a spawn-target pair selection algorithm for prescient instruction prefetch. This algorithm has been implemented, and evaluated for the Itanium Processor Family architecture. A limit study finds 4.8%to 17% speedups on an in-order simultaneous multithreading processor with eight contexts, over nextline and streaming I-prefetch for a set of benchmarks with high I-cache miss rates. The framework in this paper is potentially applicable to other thread speculation techniques.

As the frequency gap between main memory and modern microprocessor grows, the implementation and efficiency of on-chip caches become more important. The growing latency to memory is motivating new research into load instruction behavior and selective data caching. This work investigates the classification of load instruction behavior. A new load classification method is proposed that classifies loads into those vital to performance and those not vital to performance. A limit study is presented to characterize different types of non-vital loads and to quantify the percentage of loads that are non-vital. Finally, a realistic implementation of the non-vital load classification method is presented and a new cache structure called the Vital Cache is proposed to take advantage of non-vital loads. The Vital Cache caches data for vital loads only, deferring non-vital loads to slower caches. Results: The limit study shows 75% of all loads are non-vital with only 35% of the accessed data space being vital for caching. The Vital Cache improves the efficiency of the cache hierarchy and the hit rate for vital loads. The Vital Cache increases performance by 17%.

The performance of in-order execution Itanium/sup TM/ processors can suffer significantly due to cache misses. Two memory latency tolerance approaches can be applied for the Itanium processors. One uses an out-of-order (OOO) execution core; the other assumes multithreading support and exploits cache prefetching via speculative precomputation (SP). This paper evaluates and contrasts these two approaches. In addition, this paper assesses the effectiveness of combining the two approaches. For a select set of memory-intensive programs, an in-order SMT Itanium processor using speculative precomputation can achieve performance improvement (92%) comparable to that of an out-of-order design (87%). Applying both 000 and SP yields a total performance improvement of 141% over the baseline in-order machine. OOO tends to be effective in prefetching-for L1 misses; whereas SP is primarily good at covering L2 and L3 misses. Our analysis indicates that the two approaches can be redundant or complementary depending on the type of delinquent loads that each targets. Both approaches are effective on delinquent loads in the loop body; however only SP is effective on delinquent loads found in loop control code.

This paper presents a detailed branch characterization of an Oracle based commercial on-line transaction processing workload, Oracle Database Benchmark (ODB), running on an IA32 processor. We ran a well-tuned ODB on Simics, a full system simulator, to collect the instruction traces used in this study. We compare the branch behavior of ODB with the branch behaviors of gcc, gzip and mcf from the SPECINT 2000 benchmark suite. Contrary to the popular belief that databases have unpredictable branches, we show that using larger predictors that capture enough branch history information, and using branch prediction schemes that reduce aliasing, conditional branches in ODB are more predictable than in gcc, gzip and mcf Due to frequent context switching in ODB, a hardware return address stack is ineffective in predicting return addresses for ODB. Based on further analysis, we propose and evaluate an enhanced return address predictor, which reduces return address mispredictions in ODB by 40%.

Recently, a number of thread-based prefetching techniques have been proposed. These techniques aim at improving the latency of single-threaded applications by leveraging multithreading resources to perform memory prefetching via speculative prefetch threads. Software-based speculative precomputation (SSP) is one such technique, proposed for multithreaded Itanium models. SSP does not require expensive hardware support-instead it relies on the compiler to adapt binaries to perform prefetching on otherwise idle hardware thread contexts at run time. This paper presents a post-pass compilation tool for generating SSP-enhanced binaries. The tool is able to: (1) analyze a single-threaded application to generate prefetch threads; (2) identify and embed trigger points in the original binary; and (3) produce a new binary that has the prefetch threads attached. The execution of the new binary spawns the speculative prefetch threads, which are executed concurrently with the main thread. Our results indicate that for a set of pointer-intensive benchmarks, the prefetching performed by the speculative threads achieves an average of 87% speedup on an in-order processor and 5% speedup on an out-of-order processor.

To achieve higher processor performance requires greater synergy between advanced hardware features and innovative compiler techniques. Recent advancement in compilation techniques for predicated execution has provided significant opportunity in exploiting instruction level parallelism. However, little research has been done on how to efficiently execute predicated code in a dynamic microarchitecture. In this paper, we evaluate hardware optimizations for executing predicated code on a dynamically scheduled microarchitecture. We provide two novel ideas to improve the efficiency of executing predicated code. On a generic Intel Itanium processor pipeline model, we demonstrate that, with some microarchitecture enhancements, a dynamic execution processor can achieve about 16% performance improvement over an equivalent static execution processor.

A low-latency and high-bandwidth level-1 data cache is crucial for achieving high performance in future superscalar microprocessors. The parallel cachelets (PC) proposed in this paper provide bandwidth close to that of a multi-ported cache with implementation efficiency close to that of a multi-banked cache. In the PC scheme, the traditional level-1 data cache is replaced by a set of parallel single-ported independent caches, or cachelets. Similar to the interleaved multi-banked design, the cachelets can be concurrently accessed to provide bandwidth. However, instead of mapping data elements to the banks in an interleaved fashion based on address bits, they are dynamically assigned to cachelets based on the pattern of concurrent accesses, thus many bank conflicts can be eliminated. Furthermore, the PC scheme exhibits the attribute of implicit set associativity that allows it to outperform a direct-mapped multi-ported cache for some benchmarks. The PC scheme outperforms the multi-banked scheme by an average of 6% (IPC) across a set of SPEC95 benchmarks, and comes very close to matching the performance of the multi ported scheme. When cache access latency is taken into account, the PC scheme even outperforms the multi ported scheme by 6.4%.

This paper explores Speculative Precomputation, a technique that uses idle thread context in a multithreaded architecture to improve performance of single-threaded applications. It attacks program stalls from data cache misses by pre-computing future memory accesses in available thread contexts, and prefetching these data. This technique is evaluated by simulating the performance of a research processor based on the Itanium™ ISA supporting Simultaneous Multithreading. Two primary forms of Speculative Precomputation are evaluated. If only the non-speculative thread spawns speculative threads, performance gains of up to 30% are achieved when assuming ideal hardware. However, this speedup drops considerably with more realistic hardware assumptions. Permitting speculative threads to directly spawn additional speculative threads reduces the overhead associated with spawning threads and enables significantly more aggressive speculation, overcoming this limitation. Even with realistic costs for spawning threads, speedups as high as 169% are achieved, with an average speedup of 76%.

A large number of memory accesses in memory-bound applications are irregular, such as pointer dereferences, and can be effectively targeted by thread-based prefetching techniques like Speculative Precomputation. These techniques execute instructions, for example on an available SMT thread context, that have been extracted directly from the program they are trying to accelerate. Proposed techniques typically require manual user intervention to extract and optimize instruction sequences. This paper proposes Dynamic Speculative Precomputation, which performs all necessary instruction analysis, extraction, and optimization through the use of back-end instruction analysis hardware, located off the processor's critical path. For a set of memory limited benchmarks an average speedup of 14% is achieved when constructing simple p-slices, and this gain grows to 33% when making use of aggressive optimizations.

In the past several decades, the world of computers and especially that of microprocessors has witnessed phenomenal advances. Computers have exhibited ever-increasing performance and decreasing costs, making them more affordable and in turn, accelerating additional software and hardware development that fueled this process even more. The technology that enabled this exponential growth is a combination of advancements in process technology, microarchitecture, architecture, and design and development tools. While the pace of this progress has been quite impressive over the last two decades, it has become harder and harder to keep up this pace. New process technology requires more expensive megafabs and new performance levels require larger die, higher power consumption, and enormous design and validation effort. Furthermore, as CMOS technology continues to advance, microprocessor design is exposed to a new set of challenges. In the near future, microarchitecture has to consider and explicitly manage the limits of semiconductor technology, such as wire delays, power dissipation, and soft errors. In this paper we describe the role of microarchitecture in the computer world present the challenges ahead of us, and highlight areas where microarchitecture can help address these challenges.

The need for multiple branch prediction is inherent to wide instruction fetching. This paper presents a completion time multiple branch predictor called the Tree-based Multiple Branch Predictor (TMP) that builds on previous single branch prediction techniques. It employs a tree structure of branch predictors, or tree-node predictors, and achieves accurate multiple branch prediction by leveraging the high accuracies of the individual branch predictors. A highly-efficient TMP design uses the 2-bit saturating counters for the tree-node predictors. To achieve higher prediction rate, the TMP employs two-level schemes for the tree-node predictors resulting in a three-level TMP design. Placing the TMP at completion time reduces the critical latency in the front-end of the pipeline; the resultant longer update latency does not significantly impact the overall performance. In this paper the TMP is applied to a trace cache design and shown to be very effective in increasing its performance.

The paper demonstrates how an Instruction Path Coprocessor (I-COP) can be efficiently implemented using the PipeRench reconfigurable architecture. An I-COP is a programmable on-chip coprocessor that operates on the core processor's instructions to transform them into a new format that can be more efficiently executed. The I-COP can be used to implement many sophisticated hardware code modification techniques. We show how four specific techniques can be mapped to the PipeRench pipelined computation model. The experimental results show that a PipeRench I-COP used to perform trace construction and trace optimizations for a trace cache fill unit not only achieves good performance gains but can potentially be implemented in less than 10 mm/sup 2/ (assuming 0.18 micron technology) or approximately 3% of the die area of a current high-end microprocessor. We believe these results demonstrate the usefulness and feasibility of the I-COP concept.

This paper presents the concept of dynamic control independence (DCl) and shows how it can be detected and exploited in an out-of-order superscalar processor to reduce the performance penalties of branch mispredictions.We show how DCI can be leveraged during branch misprediction recovery to reduce the number of instructions squashed on a misprediction as well as how it can be used to avoid predicting unpredictable branches by fetching instructions out-of-order A realistic implementation is described and evaluated using six SPECint95 benchmarks.We show that exploiting DCI during branch misprediction recovety improves pe$ormance by 0.9-9.9% on a I-wide processol; by I&11.2% on an b-wide processor and by 1.9-15.3%on a 12-wideprocessol: We also show that using DCI information to fetch instructions out-of-order when an unpredictable branch is encountered potentially improves performance by 0.9-15.2% on a I-wide processol: by 2.0-14.8% on an 8-wide processor and by 2.6-16.2% on a 12wide processor: Some of the largest performance gains are observed on go and gee, which have traditionally posed the most d@cult challenge to aggressive branch prediction techniques.h-mission LO make digital or hard copies ol'all or par1 of this work for personal or classroom use is granrcd without fee provided that topics are not made or distributed for profit or commercial advantage and that copies bear this notice and lhe full citation on the tirst page.To copy otherwise, to republish, IO post on servers or to redistribute lo lisls.requires prior specific permission and/or a fee.ICS ")') Rhodes Greccc

The trace cache is a recently proposed solution to achieving high instruction fetch bandwidth by buffering and reusing dynamic instruction traces. This work presents a new block-based trace cache implementation that can achieve higher IPC performance with more efficient storage of traces. Instead of explicitly storing instructions of a trace, pointers to blocks constituting a trace are stored in a much smaller trace table. The block-based trace cache renames fetch addresses at the basic block level and stores aligned blocks in a block cache. Traces are constructed by accessing the replicated block cache using block pointers from the trace table. Performance potential of the blockbased trace cache is quantified and compared with perfect branch prediction and perfect fetch schemes. Comparing to the conventional trace cache, the block-based design can achieve higher IPC, with less impact on cycle time.

Software thread integration provides low-cost concurrency on general-purpose processors by automatically interleaving multiple threads of control into one. This simplifies hardware to software migration and can help embedded system designers meet design constraints. Previous work describes how to efficiently integrate threads. In this paper we demonstrate how to link trigger events with guest thread execution and how to analyze an application to determine which threads to integrate. The analysis involves timing measurement and prediction to identify the amount of easily accessible temporally deterministic code within each function. This information is used to predict quantitatively the impact of design decisions on system efficiency and help guide integration. To illustrate this process we evaluate an application predicted for the year 2005, when $20 buys a 2000 MIPS embedded processor-a software-based high-resolution MPEG video player.

Load execution latency is dependent on memory access latency, pipeline depth, and data dependencies.Through load effective address prediction both data dependencies and deep pipeline effects can potentially he removed from the overall execution time.If a load effective address is correctly predicted, the data cache can he speculatively accessed prior to execution, thus effectively reducing the latency of load execution.A hybrid load effective address prediction technique is proposed, using three basic predictors: Last Address Predictor (LAP), Stride Predictor (SP), and Global Dynamic Predictor (GDP).In addition to improving load address prediction accuracy, this work explores the balance of data ports in the cache memory hierarchy, and the effects of load and store aliasing in wide superscalar machines.Results: Using a realistic hybrid load address predictor, load address prediction rates range from 32% to 77% averaging 51% for SPECint95 and 60% to 96% averaging 87% for SPECfp95.For a wide superscalar machine with a significant number of execution resources, this prediction rate increases IPC by 12% and 19% for SPECint95 and SPECfp95, respectively.It is also shown that load/ store aliasing decreases the average IPC by 33 % for SPECint95 and 24 % for SPECfp95.

This paper presents details of how to perform thread integration to provide low-cost concurrency for general-purpose microcontrollers and microprocessors. A post-pass compiler interleaves multiple threads of control at the machine instruction level for concurrent execution on a uniprocessor and provides very fine-grain multithreading without context switching overhead. Such efficient concurrency allows implementation of real-time functions in software rather than dedicated peripheral hardware. We investigate a set of code transformations which allow systematic integration of a real-time guest thread into a host thread, producing an integrated thread which meets all real-time requirements. The thread integration concept and the associated code transformations have been applied to example functions chosen from three application domains to evaluate the method's feasibility.

Presents a statistical approach to modeling superscalar processor performance. Standard trace-driven techniques are very accurate, but require extremely long simulation times, especially as traces reach lengths in the billions of instructions. A framework for statistical models is described which facilitates fast, accurate performance evaluation. A machine model is built up from components: buffers, pipelines, etc. Each program trace is scanned once, generating a set of program parallelism parameters which can be used across an entire family of machine models. The machine model and program parallelism parameters are combined to form a Markov chain. The Markov chain is partitioned in order to reduce the size of the state space, and the resulting linked models are solved using an iterative technique. The use of this framework is demonstrated with two simple processor microarchitectures. The IPC estimates are very close to the IPCs generated by trace-driven simulation of the same microarchitectures. Resource utilization and other performance data can also be obtained from the statistical model.

While there has been an abundance of recent papers on hardware and software approaches to improving the performance of memory accesses, few papers have addressed the problem from the program's point of view. There is a general notion that certain programs have larger working sets than others. However, there is no quantitative method for evaluating and comparing the memory requirements of programs.This paper introduces the bandwidth spectrum for characterizing the memory requirements of a program's instruction and data stream. The bandwidth spectrum measures the average bandwidth requirement of a program as a function of available local memory. These measurements are performed under the most idealized conditions of perfect knowledge and perfect memory management. As such, they represent the lower bounds on the memory requirements of programs. We present the bandwidth spectrums for a set of 22 benchmarks and show how they can be used in the comparison of memory requirements and I/O requirement. The bandwidth spectrums also offer a convenient method to weigh the trade-off amongst instruction issue rate, local memory capacity and bandwidth into local memory.Using the bandwidth spectrum, we show that at issue rates of four or less, bandwidth usually scales linearly with the issue rate. At higher issue rates, bandwidth can often scale superlinearly with respect to issue rate. Finally, we also investigate the effects of varying the input sets on the bandwidth spectrums.

Since the introduction of virtual memory demand-paging and cache memories, computer systems have been exploiting spatial and temporal locality to reduce the average latency of a memory reference. In this paper, we introduce the notion of value locality, a third facet of locality that is frequently present in real-world programs, and describe how to effectively capture and exploit it in order to perform load value prediction. Temporal and spatial locality are attributes of storage locations, and describe the future likelihood of references to those locations or their close neighbors. In a similar vein, value locality describes the likelihood of the recurrence of a previously-seen value within a storage location. Modern processors already exploit value locality in a very restricted sense through the use of control speculation (i.e. branch prediction), which seeks to predict the future value of a single condition bit based on previously-seen values. Our work extends this to predict entire 32- and 64-bit register values based on previously-seen values. We find that, just as condition bits are fairly predictable on a per-static-branch basis, full register values being loaded from memory are frequently predictable as well. Furthermore, we show that simple microarchitectural enhancements to two modern microprocessor implementations (based on the PowerPC 620 and Alpha 21164) that enable load value prediction can effectively exploit value locality to collapse true dependencies, reduce average memory latency and bandwidth requirements, and provide measurable performance gains.

There are four crucial issues associated with performance simulators: simulator retargetability, simulator validation, simulation speed and simulation accuracy. The paper documents our experiences in developing performance simulators and our recent findings in using these simulators. We are concerned with all four of the crucial issues. Our first generation tool, VMW, focused on achieving retargetability. Our second generation tool, MW, significantly improved simulation speed. Recently we validated a PowerPC 604 simulator model, generated using MW against an actual PowerPC 604 hardware system. We also present results on simulating extremely long traces on our PowerPC 620 model and highlight potential inaccuracies that can result from trace sampling. As processor complexity continues to increase at a rapid rate and microarchitectures continue to become more speculative, it is not clear whether the trace driven paradigm of performance simulation can continue to effectively predict actual machine performance.

For decades, the serialization constraints imposed by true data dependences have been regarded as an absolute limit-the dataflow limit-on the parallel execution of serial programs. This paper proposes a new technique-value prediction-for exceeding that limit that allows data dependent instructions to issue and execute in parallel without violating program semantics. This technique is built on the concept of value locality which describes the likelihood of the recurrence of a previously-seen value within a storage location inside a computer system. Value prediction consists of predicting entire 32- and 64-bit register values based on previously-seen values. We find that such register values being written by machine instructions are frequently predictable. Furthermore, we show that simple microarchitectural enhancements to a modern microprocessor implementation based on the PowerPC 620 that enable value prediction can effectively exploit value locality to collapse true dependences, reduce average result latency and provide performance gains of 4.5%-23% (depending on machine model) by exceeding the dataflow limit.

The PowerPC 620™ microprocessor is the most recent and performance leading member of the PowerPC™ family. The 64-bit PowerPC 620 microprocessor employs a two-phase branch prediction scheme, dynamic renaming for all the register files, distributed multi-entry reservation stations, true out-of-order execution by six execution units, and a completion buffer for ensuring precise exceptions. This paper presents an instruction-level performance evaluation of the 620 microarchitecture. A performance simulator is developed using the VMW (Visualization-based Microarchitecture Workbench) retargetable framework. The VMW-based simulator accurately models the microarchitecture down to the machine cycle level. Extensive trace-driven simulation is performed using the SPEC92 benchmarks. Detailed quantitative analyses of the effectiveness of all key microarchitecture features are presented.

Modern high-performance microprocessors are devoting more and more resources to the problem of the von Neuman bottleneck. In this limit study, we measure the bare minimum amount of local memories that programs require to run without delay. Our measurements are made by using the Value Reuse Profile, which contains the dynamic value reuse information of a program's execution, and by assuming the existence of efficient memory systems. The results show that the group of 16 benchmarks we use require considerably less memory than a typical superscalar microprocessor has. We also measure the amount of performance improvement that is possible in the presence of an autonomous memory system. For the DEC Alpha 21064, this figure ranges from 15% to 102%. The results provide motivation for the development of more effective memory management policies.

Ambiguous memory references have always been one of the main sources of performance bottlenecks. Many papers have addressed this problem using static disambiguation. These methods work extremely well when the memory access pattern is linear and predictable. However they are ineffective when the memory access pattern is nonlinear or when the access pattern cannot be determined statically. For these difficult problems, the authors present speculative disambiguation, a compilation technique for architectures supporting instruction level parallelism and either speculative execution or conditional execution (or both). This technique produces specialized code at compile time to disambiguate memory references at run time. It is shown that on machines with sufficient resources, the technique will always result in lower execution time. Speculative disambiguation has been implemented for a VLIW architecture with guarded execution. Preliminary results indicate that it can help bridge a significant fraction of the performance gap between a good and a perfect static disambiguator. Occasionally it can outperform the perfect static disambiguator.>

The current trace-driven simulation approach to determine superscalar processor performance is widely used but has some shortcomings. Modern benchmarks generate extremely long traces, resulting in problems with data storage, as well as very long simulation runtimes. More fundamentally, simulation generally does not provide significant insight into the factors that determine performance or a characterization of their interactions. This paper proposes a theoretical model of superscalar processor performance that addresses these shortcomings. Performance is viewed as an interaction of program parallelism and machine parallelism. Both program and machine parallelisms are decomposed into multiple component functions. Methods for measuring or computing these functions are described. The functions are combined to provide a model of the interaction between program and machine parallelisms and an accurate estimate of the performance. The computed performance, based on this model, is compared to simulated performance for six benchmarks from the SPEC92 suite on several configurations of the IBM RS/6000 instruction set architecture.

Computer architectures are using increased degrees of instruction-level machine parallelism to achieve higher performance, e.g., superpipelined, superscalar and very long instruction word (VLIW) processors. Full utilization of such machine parallelism is difficult to achieve and sustain, resulting in the occurrence of idle resources at run time. This work explores the use of such idle resources for concurrent error detection in processors employing instruction-level machine parallelism. The Multiflow TRACE 14/300 processor, a VLIW machine, is chosen as an experimental vehicle. Experiments indicate that significant idle resources are likely to exist across a wide range of scientific applications for the TRACE 14/300. A methodology is presented for detecting transient control-flow errors, called available resource-driven control-flow monitoring (ARC), whose resource use can be tailored to the existence of idle resources in the processor. Results of applying ARC to the Multiflow TRACE 14/300 processor show that >99% of control-flow errors are detected with negligible performance overhead. These results demonstrate that ARC is highly effective in using the idle resources of a processor to achieve concurrent error detection at a very low cost.>

Boosting, first introduced by M.D. Smith et al. (1990), is an instruction scheduling technique that increases the instruction-level parallelism by allowing the compiler to move instructions speculatively up past conditional branches and providing hardware support to delay committing the side effects of the boosted instructions until the conditional branches have been resolved. The paper proposes an enhanced compilation technique similar to boosting that provides performance improvements while maintaining instruction set architecture compatibility and eliminating the need for complex hardware support. The technique, called architecture-compatible (AC) boosting, has been implemented for the IBM RS/6000 architecture. Code scheduling and machine simulation tools have been implemented, and experiments have been performed to demonstrate the feasibility of AC boosting on the current as well as future implementations of the IBM RS/6000 architecture.>

Superscalar implementations of RISC architectures are emerging as the dominant high-performance microprocessor technology for the mid-1990's. For instruction-level parallelism to increase beyond present levels, multiple memory operations per cycle are required. The paper evaluates several alternatives for two-ported data cache memory systems. A new split data cache memory design is compared to a more conventional true dual-ported memory. Experimental simulations are used to determine the performance benefits of these cache models on superscalar processors. These experiments are reported for a contemporary processor with modest instruction-level parallelism and for a hypothetical very aggressive, highly parallel processor.>

Article Free Access Share on Instruction level profiling and evaluation of the IBM/6000 Authors: Chriss Stephens Center for Dependable Systems, Department of Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh, PA Center for Dependable Systems, Department of Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh, PAView Profile , Bryce Cogswell Center for Dependable Systems, Department of Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh, PA Center for Dependable Systems, Department of Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh, PAView Profile , John Heinlein Center for Dependable Systems, Department of Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh, PA Center for Dependable Systems, Department of Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh, PAView Profile , Gregory Palmer Center for Dependable Systems, Department of Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh, PA Center for Dependable Systems, Department of Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh, PAView Profile , John P. Shen Center for Dependable Systems, Department of Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh, PA Center for Dependable Systems, Department of Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh, PAView Profile Authors Info & Claims ISCA '91: Proceedings of the 18th annual international symposium on Computer architectureApril 1991Pages 180–189https://doi.org/10.1145/115952.115971Published:01 April 1991Publication History 30citation385DownloadsMetricsTotal Citations30Total Downloads385Last 12 Months38Last 6 weeks4 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

Article Free Access Share on Implementation optimization techniques for architecture synthesis of application-specific processors Authors: Mauricio Breternitz Advanced Workstations Division, IBM-Austin, TX Advanced Workstations Division, IBM-Austin, TXView Profile , John Paul Shen ECE Department, Carnegie-Mellon University ECE Department, Carnegie-Mellon UniversityView Profile Authors Info & Claims MICRO 24: Proceedings of the 24th annual international symposium on MicroarchitectureSeptember 1991 Pages 114–123https://doi.org/10.1145/123465.123488Published:01 September 1991Publication History 0citation252DownloadsMetricsTotal Citations0Total Downloads252Last 12 Months11Last 6 weeks2 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 key principles of the Application-Specific Processor Design (ASPD) methodology include: a semi-custom compilation-driven design/implementation approach, the exploitation of fine-grained parallelism for high performance, and the adaptation of datapath topology to the data transfers required by the application. The powerful microcode compilation techniques of Percolation Scheduling and Pipeline Scheduling extract and enhance the parallelism in the application object code to generate an optimized specification of the target processor. Implementation optimization is performed to allocate functional units and register files. Graph-coloring algorithms minimize the amount of hardware needed to exploit available parallelism. Data memory employs an organization with multiple banks. Compilation techniques are used to allocate data over the memory banks to enhance parallel access.

Signature monitoring has proven to be an effective method for concurrent detection of control-flow errors in processors. A recent proposal adapts signature monitoring to the concurrent checking of dedicated controllers or state machines. The authors extend this approach and present theoretical results, including existence-of-solution guarantees, as well as new, efficient synthesis algorithms. The algorithms have been implemented and successfully applied to a variety of machines including all of the machines in the MCNC benchmark set. For most examples, the evaluation and synthesis algorithms exhibit negligible running times and the resulting optimized machines exhibit reasonable overheads. There is strong indication that the efficient synthesis of self-monitoring, and possibly self-testing, state machines is feasible using this approach.>

A low-cost approach to concurrent detection of processor control errors is presented that uses a simple hardware monitor and signatures embedded into the executing program. Existing signature-monitoring techniques detect a large portion of processor control errors at a fraction of the cost of duplication. Analytical methods developed in this study show that the new approach, continuous signature monitoring (CSM), makes major advances beyond existing techniques. CSM reduces the fraction of undetected control-flow errors by orders of magnitude, to less than 10/sup -6/, while the number of signatures reaches a theoretical minimum, being lowered by as much as three times to a range of 4-11%. Signature cost is reduced by placing CSM signatures at locations that minimize performance loss and (for some architectures) memory overhead. CSM exploits the program memory's SEC/DED code to decrease error-detection latency by as much as 1000 times, to 0.016 program memory cycles, without increasing memory overhead. This short latency allows transient faults to be tolerated.>

The design and implementation of a high-performance special-purpose processor, called the White Dwarf, or accelerating finite-element analysis algorithms is presented. The White Dwarf CPU contains two Am2935 32-bit floating-point processors and one Am29332 32-bit arithmetic logic unit (ALU), and uses a wide-instruction-word architecture in which the application algorithm is directly implemented in microcode. The entire system is VME-bus compatible and interfaces with a Sun 3/160 host. The system's potential peak performance is 20 MFLOPS (million floating-point operations per second) a sustained computation rate in excess of 15 MFLOPS is expected. A potential speedup of between one and two orders of magnitude is possible. With a fully populated memory subsystem, the White Dwarf can accommodate finite-element problems involving up to half a million nodes. The system is designed using an approach called application-specific processor design (ASPD). A retargetable compiler has been developed which is capable of generating highly parallel and efficient code for the White Dwarf and other processors with similar architecture. System debug/integration is in progress; a highly useful system is expected.>

FXT is a software tool which implements inductive fault analysis for CMOS circuits. It extracts a comprehensive list of circuit-level faults for any given CMOS circuit and ranks them according to their relative likelihood of occurrence. Five commercial CMOS circuits are analyzed using FXT. Of the extracted faults, approximately 50% can be modeled by single-line stuck-at 0/1 fault model. Faults extracted from two circuits are simulated with the switch-level fault simulator FMOSSIM. The test set provided by the circuits' manufacturer, which detects 100% of the single-line stuck-at 0/1 faults, detected between 73% and 89% of the simulated faults.>

Concurrent detection of processor control errors using signatured programs is discussed. The approach, called continuous signature monitoring (CSM), makes significant advances beyond the existing signature-monitoring techniques. For typical programs, CSM decreased average error-detection latency by as much as eight times, down to 1.2 to 1.6 program memory cycles. Memory overhead for storing signatures reaches a theoretical minimum, lowered as much as four times, dozen to 3-7%. The CSM monitor is less complex by more than half, and processor-performance loss is reduced as much as 10 times down to 0.6-1.5%. CSM increases coverage of control-flow errors and detects certain types of errors not detected by the existing techniques, including a stuck program counter.>

The inductive fault analysis (IFA) method is presented and a description is given of the CMOS fault extraction program FXT. The IFA philosophy is to consider the causes of faults (manufacturing defects) and then simulate these causes to find the faults that are likely to occur in a circuit. FXT automates IFA for a CMOS technology by generating a list of faults that are likely to occur in a CMOS circuit. The realistic faults generated by FXT are used to evaluate fault models, find the realistic fault coverage of test sets, and guide future testing research. How well various fault models characterize the realistic faults can be quantitatively measured because FXT's fault list includes the relative likelihood of occurrence (weight) of each extracted fault. The value of IFA and FXT is demonstrated by the analysis of five commercial CMOS circuits. This analysis shows that the traditional SSA fault model characterizes fewer than half of the faults extracted by FXT; graph-theoretic techniques provide little improvement in the percentage of realistic faults modeled.>

Recent research on parallel systems has shown that the most difficult problem for system designers and users is interprocessor connection and communication. A methodology for the automated design and implementation of interprocessor communication for certain multiple-processor systems has been developed and is presented in this paper. For many application- specific and mission-oriented systems, the interprocessor communication is deterministic and can be specified at system inception. This specification can then be automatically mapped or complied onto a physical multiple-processor system using a network traffic scheduler. An algorithm for such a scheduler, which is capable of obtaining optimal network traffic patterns, has been developed. It is shown that the order of complexity of network scheduler components is polynomial, rather than expopential as in classical solutions.

This paper presents an innovative approach, called signatured instruction streams (SIS), to the on-line detection of control flow errors caused by transient and intermittent faults. At compile time an application program is appropriately partitioned into smaller subprograms, and cyclic codes, or signatures, characterizing the control flow of each subprogram are generated and embedded in the object code. At runtime, special built-in hardware regenerates these signatures using runtime information and compares them to the precomputed signatures. A mismatch indicates the detection of an error. A demonstration system, based on the MC68000 processor, has been designed and built. Fault insertion experiments have been performed using the demonstration system. The demonstration system, using 17 percent hardware overhead, is able to detect 98 percent of faults affecting the control flow and 82 percent of all randomly inserted faults.

Array multipliers are well suited for VLSI implementation because of the regularity in their iterative structure. However, most VLSI circuits are difficult to test. This correspondence shows that, with appropriate cell design, array multipliers can be designed to be very easily testable. An array multiplier is called C-testable if all its adder cells can be exhaustively tested while requiring only a constant number of test patterns. The testability of two well-known array multiplier structures is studied in detail. The conventional design of the carry–save array multiplier is modified. The modified design is shown to be C-testable and requires only 16 test patterns. Similar results are obtained for the Baugh–Wooley two's complement array multiplier. A modified design of the Baugh–Wooley array multiplier is shown to be C-testable and requires 55 test patterns. The C-testability of two other array multipliers, namely the carry–propagate and the TRW designs, is also presented.

A β-network is an interconnection network composed of 2 ×2 crossbar switches called β-elements. This paper presents an analysis of the fault-tolerance of β-networks. A fault model is specified which allows β-elements to be stuck in either of their two normal states. A new connectivity property called dynamic full access (DFA) is introduced which serves as the criterion for fault tolerance. A fault is called critical if it destroys the DFA property; otherwise, it is noncritical. A minimal critical fault (MCF) is a critical fault none of whose proper subsets constitutes a critical fault. Two graph-theoretical characterizations of the minimal critical faults and the noncritical faults of a β-network are presented. Some applications of the theory developed here are discussed.

Array multipliers are well-suited for VLSI implementation because of the regularity in their iterative structure. However, most VLSI circuits are very difficult to test. This paper shows that, with appropriate cell design, array multipliers can be designed to be very easily-testable. An array multiplier is called C-testable if all its adder cells can be exhaustively tested while requiring only a constant number of test patterns. The testability of two well-known array multiplier structures are studied. The conventional design of the carry-save array multiplier is shown to be not C-testable. However, a modified design, using a modified adder cell, is generated and shown lo be C-testable and requires only 76 test patterns. Similar results are obtained for the Baugh-Wooley two's complement array multiplier. A modified design of the Baugh-Wooley array multiplier is shown to be C-testable and requires 55 test patterns. The implementation of a practical C-testable 16 × 16 array multiplier is also presented.

Several proposals have been made for using a class of connecting networks called β-networks in multicomputer systems, such as systems containing large numbers of microprocessors. A β-network is a network of 2 × 2 crossbar switches called β-elements. This paper presents an analysis of the fault tolerance of β-networks intended for multicomputer applications. A fault model is used which allows β-elements to be stuck in either of their two normal states. A new connectivity property called dynamic full access (DFA) is introduced which serves as the criterion for fault tolerance. A β-network is said to have the DFA property if each of its inputs can be connected to any of its outputs in a finite number of passes through the network. A fault is called critical if it destroys the DFA property. Two graph-theoretical characterizations of the critical faults of a β-network are presented. It is shown that there is a one-to-one correspondence between minimal critical faults and the cutsets of the circuit adjacency graphs derived from the β-network. It is further shown that a fault is critical if and only if it is incompatible with all Eulerian circuits associated with the β-network. Some applications of the theory are discussed.