Constrained coding plays a crucial role in high-speed communication links by restricting bit sequences to reduce the adverse effects imposed by the characteristics of the channel. This technique trades off some bit efficiency for higher transmission rates, thereby boosting overall data throughput. We show how the design of hardware-efficient translation logic to and from the restricted code space can be formulated as a Satisfiability Modulo Theories (SMT) problem. Using SMT, we can not only try to minimize the complexity of this logic and limit the effect of transmission errors on the final decoded output, but also significantly reduce development time—from weeks to just hours. Our initial results demonstrate the efficiency and effectiveness of this approach.

Sparse tensor algebra computations are often memory-bound due to irregular access patterns and low arithmetic intensity.We present D2T2 (Data-Driven Tensor Tiling), a framework that optimizes static coordinate-space tiling schemes to minimize memory traffic by identifying and leveraging relevant high-level statistics from input operands.For a given tensor algebra computation, D2T2 collects statistics from input tensors, builds a probability distribution-based model of the tensor computation, and uses it to predict traffic for various tiling configurations.It searches over tile shape and size configurations to minimize total traffic.We evaluate D2T2 against Tailors and DRT, two state of the art tiling schemes for sparse tensor algebra.We find that D2T2 achieves, on average, a 2.54× speedup over Tailors and a 1.13× lower memory bandwidth compared to DRT for sparse-sparse matrix multiplication (SpMSpM).We also achieve 1.22-48.94×lower bandwidth for SpMSpM and up to 34.31× lower bandwidth for tensor operations (TTM and MTTKRP) than conservative static tiling schemes.Unlike prior tiling techniques, D2T2 is deployable without specialized hardware support.On Opal, a 16nm sparse tensor algebra accelerator, D2T2 generated tiling configurations that achieve 1.23-3.34×speedups compared to their original hand-tuned configurations.

•Applications ranging from scientific computing to machine learning can have extremely sparse inputs

State-of-the-art deep learning models for computer vision tasks are based on the transformer architecture and often deployed in real-time applications. In this scenario, the resources available for every inference can vary, so it is useful to be able to dynamically adapt execution to trade accuracy for efficiency. To create dynamic models, we leverage the resilience of vision transformers to pruning and switch between different scaled versions of a model. Surprisingly, we find that most FLOPs are generated by convolutions, not attention. These relative FLOP counts are not a good predictor of GPU performance since GPUs have special optimizations for convolutions. Some models are fairly resilient and their model execution can be adapted without retraining, while all models achieve better accuracy with retraining alternative execution paths. These insights mean that we can leverage CNN accelerators and these alternative execution paths to enable efficient and dynamic vision transformer inference. Our analysis shows that leveraging this type of dynamic execution can lead to saving 28 % of energy with a 1.4 % accuracy drop for SegFormer (63 GFLOPs), with no additional training, and 53% of energy for ResNet-50 (4 GFLOPs) with a 3.3% accuracy drop by switching between pretrained Once-For-All models.

While coarse-grained reconfigurable arrays (CGRAs) have emerged as promising programmable accelerator architectures, they require automatic pipelining of applications during their compilation flow to achieve high performance. Current CGRA compilers either lack pipelining altogether resulting in low application performance, or perform exhaustive pipelining resulting in high power and resource consumption. We address these challenges by proposing Cascade, an end-to-end open-source application compiler for CGRAs that achieves both state-of-the-art performance and fast compilation times. The contributions of this work are: (1) a novel post place-and-route (PnR) application pipelining technique for CGRAs that accounts for interconnect hop delays during pipelining but in a unique way that avoids cyclic scheduling and place-and-route, (2) a register resource usage optimization technique that leverages the scheduling logic in CGRA memory tiles to minimize the number of register resources used during pipelining, and (3) an automated CGRA timing model generator, an application timing analysis tool, and a large set of existing and novel application pipelining techniques integrated into an end-to-end compilation flow. Cascade achieves 8 -34× lower critical path delay and 7 -190× lower energy-delay product (EDP) across a variety of dense image processing and machine learning workloads, and 3 -5.2× lower critical path delay and 2.5 -5.2× lower EDP on sparse workloads, compared to a compiler without pipelining. Cascade mitigates the performance and energy-efficiency drawbacks of existing CGRA compilers, and enables further research into CGRAs as flexible, yet competitive accelerator architectures.

We propose the Sparse Abstract Machine (SAM), an abstract machine model for targeting sparse tensor algebra to reconfigurable and fixed-function spatial dataflow accelerators. SAM defines a streaming dataflow abstraction with sparse primitives that encompass a large space of scheduled tensor algebra expressions. SAM dataflow graphs naturally separate tensor formats from algorithms and are expressive enough to incorporate arbitrary iteration orderings and many hardware-specific optimizations. We also present Custard, a compiler from a high-level language to SAM that demonstrates SAM's usefulness as an intermediate representation. We automatically bind from SAM to a streaming dataflow simulator. We evaluate the generality and extensibility of SAM, explore the performance space of sparse tensor algebra optimizations using SAM, and show SAM's ability to represent dataflow hardware.

The architecture of a coarse-grained reconfigurable array (CGRA) processing element (PE) has a significant effect on the performance and energy-efficiency of an application running on the CGRA. This paper presents APEX, an automated approach for generating specialized PE architectures for an application or an application domain. APEX first analyzes application domain benchmarks using frequent subgraph mining to extract commonly occurring computational subgraphs. APEX then generates specialized PEs by merging subgraphs using a datapath graph merging algorithm. The merged datapath graphs are translated into a PE specification from which we automatically generate the PE hardware description in Verilog along with a compiler that maps applications to the PE. The PE hardware and compiler are inserted into a flexible CGRA generation and compilation toolchain that allows for agile evaluation of CGRAs. We evaluate APEX for two domains, machine learning and image processing. For image processing applications, our automatically generated CGRAs with specialized PEs achieve from 5% to 30% less area and from 22% to 46% less energy compared to a general-purpose CGRA. For machine learning applications, our automatically generated CGRAs consume 16% to 59% less energy and 22% to 39% less area than a general-purpose CGRA. This work paves the way for creation of application domain-driven design-space exploration frameworks that automatically generate efficient programmable accelerators, with a much lower design effort for both hardware and compiler generation.

Image processing and machine learning applications benefit tremendously from hardware acceleration. Existing compilers target either FPGAs, which sacrifice power and performance for programmability, or ASICs, which become obsolete as applications change. Programmable domain-specific accelerators, such as coarse-grained reconfigurable arrays (CGRAs), have emerged as a promising middle-ground, but they have traditionally been difficult compiler targets since they use a different memory abstraction. In contrast to CPUs and GPUs, the memory hierarchies of domain-specific accelerators use push memories : memories that send input data streams to computation kernels or to higher or lower levels in the memory hierarchy and store the resulting output data streams. To address the compilation challenge caused by push memories, we propose that the representation of these memories in the compiler be altered to directly represent them by combining storage with address generation and control logic in a single structure—a unified buffer. The unified buffer abstraction enables the compiler to separate generic push memory optimizations from the mapping to specific memory implementations in the backend. This separation allows our compiler to map high-level Halide applications to different CGRA memory designs, including some with a ready-valid interface. The separation also opens the opportunity for optimizing push memory elements on reconfigurable arrays. Our optimized memory implementation, the Physical Unified Buffer, uses a wide-fetch, single-port SRAM macro with built-in address generation logic to implement a buffer with two read and two write ports. It is 18% smaller and consumes 31% less energy than a physical buffer implementation using a dual-port memory that only supports two ports. Finally, our system evaluation shows that enabling a compiler to support CGRAs leads to performance and energy benefits. Over a wide range of image processing and machine learning applications, our CGRA achieves 4.7× better runtime and 3.5× better energy-efficiency compared to an FPGA.

With the slowing of Moore’s law, computer architects have turned to domain-specific hardware specialization to continue improving the performance and efficiency of computing systems. However, specialization typically entails significant modifications to the software stack to properly leverage the updated hardware. The lack of a structured approach for updating the compiler and the accelerator in tandem has impeded many attempts to systematize this procedure. We propose a new approach to enable flexible and evolvable domain-specific hardware specialization based on coarse-grained reconfigurable arrays (CGRAs). Our agile methodology employs a combination of new programming languages and formal methods to automatically generate the accelerator hardware and its compiler from a single source of truth. This enables the creation of design-space exploration frameworks that automatically generate accelerator architectures that approach the efficiencies of hand-designed accelerators, with a significantly lower design effort for both hardware and compiler generation. Our current system accelerates dense linear algebra applications but is modular and can be extended to support other domains. Our methodology has the potential to significantly improve the productivity of hardware-software engineering teams and enable quicker customization and deployment of complex accelerator-rich computing systems.

To effectively minimize static power for a wide range of applications, power domains for coarse-grained reconfigurable array (CGRA) architectures need to be more fine-grained than those found in a typical application-specific integrated circuit. However, the special isolation logic needed to ensure electrical protection between off and on domains makes fine-grained power domains area- and timing-inefficient. We propose a novel design of the CGRA routing fabric that reduces the area overhead of power domain boundary protection from around 9% to less than 1% without incurring any extra timing delay from the isolation cells. Conventional Unified Power Format based flow for power domain boundary protection does not support this design choice. Therefore, we create our own compiler-like passes that iteratively introduce the needed design changes, and formally verify the transformations using methods based on satisfiability modulo theories. These passes also let us optimize how we handle test and debug signals through the off tiles in the CGRA. Using our framework, we add power domains to a CGRA that we designed and taped out. The CGRA has 32 × 16 processing element and memory tiles and 4-MB secondary memory. We address the implementation challenges encountered due to the introduction of fine-grained power domains, including the addressing of the CGRA tiles, the power grid design, well substrate connections, and distribution of global signals. Our CGRA achieves up to 83% reduction in leakage power and 26% reduction in total power versus an identical CGRA without multiple power domains, for a range of image processing and machine learning applications.

Achieving high code reuse in physical design flows is challenging but increasingly necessary to build complex systems. Unfortunately, existing approaches based on parameterized Tcl generators support very limited reuse as designers customize flows for specific designs and technologies, preventing their reuse in future flows. We present a vision and framework based on modular flow generators that encapsulates coarse-grained and fine-grained reusable code in modular nodes and assembles them into complete flows. The key feature is a flow consistency and instrumentation layer embedded in Python, which supports mechanisms for rapid and early feedback on inconsistent composition. We evaluate the design flows of successive generations of silicon prototypes built in TSMC16, TSMC28, TSMC40, SKY130, and IBM180 technologies, showing how our approach can enable significant code reuse in future flows.

High-level hardware generators have significantly increased the productivity of design engineers. They use software engineering constructs to reduce the repetition required to express complex designs and enable more composability. However, these benefits are undermined by a lack of debugging infrastructure, requiring hardware designers to debug generated, usually incomprehensible, RTL code. This paper describes a framework that connects modern software source-level debugging frameworks to RTL created from hardware generators. Our working prototype offers an Integrated Development Environment (IDE) experience for generators such as RocketChip (Chisel), allowing designers to set breakpoints in complex source code, relate RTL simulation state back to source-level variables, and do forward and backward debugging, with almost no simulation overhead (less than 5%).

Dedicated hardware accelerators popular for imaging, vision, and machine learning (ML) applications

This article presents an open-source framework for emulating mixed-signal chip designs on a field-programmable gate array (FPGA). It includes a Python-based synthesizable model generator for mixed-signal blocks (msdsl), a fixed-point and floating-point synthesizable SystemVerilog library for representing real numbers (svreal), and a Python-based tool that generates emulator control infrastructure and automates the FPGA build process (anasymod). The framework includes features for efficiently modeling analog dynamics, nonlinearity, and noise, often making use of compile-time caching to reduce the required computational resources of the FPGA. We demonstrate the framework’s generality by discussing three applications: 1) a high-speed link receiver (DragonPHY); 2) a firmware-controlled flyback converter; and 3) an NFC-powered chip. Our framework makes it easy to emulate these systems, while providing runtimes 2–3 orders of magnitude faster than CPU simulations with real-number functional models.

The increasing complexity of modern configurable systems makes it critical to improve the level of automation in the process of system configuration. Such automation can also improve the agility of the development cycle, allowing for rapid and automated integration of decoupled workflows. In this paper, we present a new framework for automated configuration of systems representable as state machines. The framework leverages model checking and satisfiability modulo theories (SMT) and can be applied to any application domain representable using SMT formulas. Our approach can also be applied modularly, improving its scalability. Furthermore, we show how optimization can be used to produce configurations that are best according to some metric and also more likely to be understandable to humans. We showcase this framework and its flexibility by using it to configure a CGRA memory tile for various image processing applications.

We show that DNN accelerator micro-architectures and their program mappings represent specific choices of loop order and hardware parallelism for computing the seven nested loops of DNNs, which enables us to create a formal taxonomy of all existing dense DNN accelerators. Surprisingly, the loop transformations needed to create these hardware variants can be precisely and concisely represented by Halide's scheduling language. By modifying the Halide compiler to generate hardware, we create a system that can fairly compare these prior accelerators. As long as proper loop blocking schemes are used, and the hardware can support mapping replicated loops, many different hardware dataflows yield similar energy efficiency with good performance. This is because the loop blocking can ensure that most data references stay on-chip with good locality and the processing units have high resource utilization. How resources are allocated, especially in the memory system, has a large impact on energy and performance. By optimizing hardware resource allocation while keeping throughput constant, we achieve up to 4.2X energy improvement for Convolutional Neural Networks (CNNs), 1.6X and 1.8X improvement for Long Short-Term Memories (LSTMs) and multi-layer perceptrons (MLPs), respectively.

While hardware generators have drastically improved design productivity, they have introduced new challenges for the task of verification. To effectively cover the functionality of a sophisticated generator, verification engineers require tools that provide the flexibility of metaprogramming. However, flexibility alone is not enough; components must also be portable in order to encourage the proliferation of verification libraries as well as enable new methodologies. This paper introduces fault , a Python embedded hardware verification language that aims to empower design teams to realize the full potential of generators.

Although an agile approach is standard for software design, how to properly adapt this method to hardware is still an open question. This work addresses this question while building a system on chip (SoC) with specialized accelerators. Rather than using a traditional waterfall design flow, which starts by studying the application to be accelerated, we begin by constructing a complete flow from an application expressed in a high-level domain-specific language (DSL), in our case Halide, to a generic coarse-grained reconfigurable array (CGRA). As our under-standing of the application grows, the CGRA design evolves, and we have developed a suite of tools that tune application code, the compiler, and the CGRA to increase the efficiency of the resulting implementation. To meet our continued need to update parts of the system while maintaining the end-to-end flow, we have created DSL-based hardware generators that not only provide the Verilog needed for the implementation of the CGRA, but also create the collateral that the compiler/mapper/place and route system needs to configure its operation. This work provides a systematic approach for desiging and evolving high-performance and energy-efficient hardware-software systems for any application domain.

To effectively minimize static power for a wide range of applications, power domains for a coarse-grained reconfigurable array (CGRA) need to be finer-grained than a typical ASIC. However, the special isolation logic needed to ensure electrical protection between off and on domains makes fine-grained power domains area- and timing-inefficient. We propose a novel design of the CGRA routing fabric that intrinsically provides boundary protection. This technique reduces the area overhead of boundary protection between power domains for the CGRA from around 9% to less than 1% and removes the delay from the isolation cells. However, with this design choice, we cannot leverage the conventional UPF-based flow to introduce power domain boundary protection. We create compiler-like passes that iteratively introduce the needed design transformations, and formally verify the passes with satisfiability modulo theories (SMT) methods. These passes also allow us to optimize how we handle test and debug signals through the off tiles. We use our framework to insert power domains into an SoC with an ARM Cortex M3 processor and a CGRA with 32 × 16 processing element (PE) and memory tiles and 4MB secondary memory. Depending on the size of the applications mapped, our CGRA achieves up to an 83% reduction in leakage power and 26% reduction in total power versus a CGRA without multiple power domains, for a range of image processing and machine learning applications.

Pairwise Whole Genome Alignment (WGA) is a crucial first step to understanding evolution at the DNA sequence-level. Pairwise WGA of thousands of currently available species genomes could help make biological discoveries, however, computing them for even a fraction of the millions of possible pairs is prohibitive - WGA of a single pair of vertebrate genomes (human-mouse) takes 11 hours on a 96-core Amazon Web Services (AWS) instance (c5.24xlarge). This paper presents SegAlign - a scalable, GPU-accelerated system for computing pairwise WGA. SegAlign is based on the standard seed-filter-extend heuristic, in which the filtering stage dominates the runtime (e.g. 98% for human-mouse WGA), and is accelerated using GPU(s). Using three vertebrate genome pairs, we show that SegAlign provides a speedup of up to 14× on an 8-GPU, 64-core AWS instance (p3.16xlarge) for WGA and nearly 2.3× reduction in dollar cost. SegAlign also allows parallelization over multiple GPU nodes and scales efficiently.

The use of increasingly larger and more complex neural networks (NNs) makes it critical to scale the capabilities and efficiency of NN accelerators. Tiled architectures provide an intuitive scaling solution that supports both coarse-grained parallelism in NNs: intra-layer parallelism, where all tiles process a single layer, and inter-layer pipelining, where multiple layers execute across tiles in a pipelined manner. This work proposes dataflow optimizations to address the shortcomings of existing parallel dataflow techniques for tiled NN accelerators. For intra-layer parallelism, we develop buffer sharing dataflow that turns the distributed buffers into an idealized shared buffer, eliminating excessive data duplication and the memory access overheads. For inter-layer pipelining, we develop alternate layer loop ordering that forwards the intermediate data in a more fine-grained and timely manner, reducing the buffer requirements and pipeline delays. We also make inter-layer pipelining applicable to NNs with complex DAG structures. These optimizations improve the performance of tiled NN accelerators by 2x and reduce their energy consumption by 45% across a wide range of NNs. The effectiveness of our optimizations also increases with the NN size and complexity.

Real-time CNN-based object detection models for applications like surveillance can achieve high accuracy but are computationally expensive. Recent works have shown 10 to 100× reduction in computation cost for inference by using domain-specific networks. However, prior works have focused on inference only. If the domain model requires frequent retraining, training costs can pose a significant bottleneck. To address this, we propose Dataset Culling: a pipeline to reduce the size of the dataset for training, based on the prediction difficulty. Images that are easy to classify are filtered out since they contribute little to improving the accuracy. The difficulty is measured using our proposed confidence loss metric with little computational overhead. Dataset Culling is extended to optimize the image resolution to further improve training and inference costs. We develop fixed-angle, long-duration video datasets across several domains, and we show that the dataset size can be culled by a factor of 300× to reduce the total training time by 47× with no accuracy loss or even with slight improvement.

Internet of Things (IoT) devices, once deployed, must remain secure for their entire lifetime, which can be as long as 20 years. Over this lifetime, devices must be able to update which ciphers they use to meet evolving security requirements. However, devices cannot rely on software updates for their cryptography because software implementations consume too much energy. At the same time, fixed function hardware accelerators such as an AES engine cannot support new ciphers. This paper presents Falcon, a hardware architecture for accelerating a broad range of cryptography on energy limited devices. Rather than accelerate a fixed set of current ciphers, Falcon provides a general execution engine that accelerates dominant and emerging ciphers, such as AES, Cha-Cha, SHA-256, RSA, ECC with Curve25519, as well as post-quantum ciphers such as R-LWE. For cryptography, Falcon provides the flexibility of software while reducing the energy consumption of cryptography by 5-60x compared to software. This reduction makes it feasible for IoT applications to upgrade the ciphers they use after deployment, allowing them to keep up to date with security best practices without reducing their deployment lifetime or reducing the application workload. In an application monitoring the temperature of sensitive medical supplies in hospitals, Falcon doubles the deployment lifetime (2.2x).

Real number models, which are computationally efficient analog functional models, are now indispensable in verifying complex mixed-signal systems on chip (SoCs); yet, creating and validating these models remain difficult. To remove this problem, we created a framework for building analog functional model templates. Each template covers a class of circuits (e.g., oscillators or amplifiers) and can generate functional models for any implementation of this circuit class, regardless of pin configurations, circuit topologies, and process technologies/corners. This ability to cover many implementations with one template allows one to create a “standard model template” library that covers all the basic analog building blocks used in mixed-signal SoCs. Like a digital standard cell library, this template library only contains the low-level building blocks. Models for more complex systems, such as a phase-locked loop, are constructed using a number of these models. Our template library also contains validation routines for each of the models, measuring the key performance parameters of the modeled function. These routines can also be used to drive the circuit-level implementation of this function, making it easy to update the parameters of the functional models to match their circuit implementations. We demonstrate the utility of our template library on several mixed-signal IPs integrated into an SoC. Using the proposed framework, designers can easily generate a working model of an analog functional block in a second and thus construct a complete mixed-signal IP model for the design exploration in less than a couple of hours, while it typically needs a few days when the models are manually written. The regeneration of the models to reflect the behaviors of real implementations can be seamlessly done in less half a day from the same template library. In addition to the vast improvement in model creation speed, the generated model from the template library is less error-prone by archiving designer's experience from previous mistakes to the template library.

In this paper, we propose an architecture for FPGA emulation of mixed-signal systems that achieves high accuracy at a high throughput. We represent the analog output of a block as a superposition of step responses to changes in its analog input, and the output is evaluated only when needed by the digital subsystem. Our architecture is therefore intended for digitally-driven systems; that is, those in which the inputs of analog dynamical blocks change only on digital clock edges. We implemented a high-speed link transceiver design using the proposed architecture on a Xilinx FPGA. This design demonstrates how our approach breaks the link between simulation rate and time resolution that is characteristic of prior approaches. The emulator is flexible, allowing for the real-time adjustment of analog dynamics, clock jitter, and various design parameters. We demonstrate that our architecture achieves 1% accuracy while running 3 orders of magnitude faster than a comparable high-performance CPU simulation.

The high accuracy of deep neural networks (NNs) has led to the development of NN accelerators that improve performance by two orders of magnitude. However, scaling these accelerators for higher performance with increasingly larger NNs exacerbates the cost and energy overheads of their memory systems, including the on-chip SRAM buffers and the off-chip DRAM channels.

Specialized image processing accelerators are necessary to deliver the performance and energy efficiency required by important applications in computer vision, computational photography, and augmented reality. But creating, “programming,” and integrating this hardware into a hardware/software system is difficult. We address this problem by extending the image processing language Halide so users can specify which portions of their applications should become hardware accelerators, and then we provide a compiler that uses this code to automatically create the accelerator along with the “glue” code needed for the user’s application to access this hardware. Starting with Halide not only provides a very high-level functional description of the hardware but also allows our compiler to generate a complete software application, which accesses the hardware for acceleration when appropriate. Our system also provides high-level semantics to explore different mappings of applications to a heterogeneous system, including the flexibility of being able to change the throughput rate of the generated hardware. We demonstrate our approach by mapping applications to a commercial Xilinx Zynq system. Using its FPGA with two low-power ARM cores, our design achieves up to 6× higher performance and 38× lower energy compared to the quad-core ARM CPU on an NVIDIA Tegra K1, and 3.5× higher performance with 12× lower energy compared to the K1’s 192-core GPU.

We present a method for image registration based on 3D scale- and rotation-invariant keypoints. The method extends the scale invariant feature transform (SIFT) to arbitrary dimensions by making key modifications to orientation assignment and gradient histograms. Rotation invariance is proven mathematically. Additional modifications are made to extrema detection and keypoint matching based on the demands of image registration. Our experiments suggest that the choice of neighborhood in discrete extrema detection has a strong impact on image registration accuracy. In head MR images, the brain is registered to a labeled atlas with an average Dice coefficient of 92%, outperforming registration from mutual information as well as an existing 3D SIFT implementation. In abdominal CT images, the spine is registered with an average error of 4.82 mm. Furthermore, keypoints are matched with high precision in simulated head MR images exhibiting lesions from multiple sclerosis. These results were achieved using only affine transforms, and with no change in parameters across a wide variety of medical images. This paper is freely available as a cross-platform software library.

State-of-the-art deep neural networks (DNNs) have hundreds of millions of connections and are both computationally and memory intensive, making them difficult to deploy on embedded systems with limited hardware resources and power budgets. While custom hardware helps the computation, fetching weights from DRAM is two orders of magnitude more expensive than ALU operations, and dominates the required power. Previously proposed 'Deep Compression' makes it possible to fit large DNNs (AlexNet and VGGNet) fully in on-chip SRAM. This compression is achieved by pruning the redundant connections and having multiple connections share the same weight. We propose an energy efficient inference engine (EIE) that performs inference on this compressed network model and accelerates the resulting sparse matrix-vector multiplication with weight sharing. Going from DRAM to SRAM gives EIE 120x energy saving, Exploiting sparsity saves 10x, Weight sharing gives 8x, Skipping zero activations from ReLU saves another 3x. Evaluated on nine DNN benchmarks, EIE is 189x and 13x faster when compared to CPU and GPU implementations of the same DNN without compression. EIE has a processing power of 102 GOPS working directly on a compressed network, corresponding to 3 TOPS on an uncompressed network, and processes FC layers of AlexNet at 1.88x104 frames/sec with a power dissipation of only 600mW. It is 24,000x and 3,400x more energy efficient than a CPU and GPU respectively. Compared with DaDianNao, EIE has 2.9x, 19x and 3x better throughput, energy efficiency and area efficiency.

DRAM energy is an important component to optimize in modern computing systems. One outstanding source of DRAM energy is the energy to fetch data stored on cells to the row buffer, which occurs during two DRAM operations, row activate and refresh. This work exploits previously proposed half page row access, modifying the wordline connections within a bank to halve the number of cells fetched to the row buffer, to save energy in both cases. To accomplish this, we first change the data wire connections in the sub-array to reduce the cost of row buffer overfetch in multi-core systems which yields a 12% energy savings on average and a slight performance improvement in quad-core systems. We also propose charge recycling refresh, which reuses charge left over from a prior half page refresh to refresh another half page. Our charge recycling scheme is capable of reducing both auto- and self-refresh energy, saving more than 15% of refresh energy at 85°C, and provides even shorter refresh cycle time. Finally, we propose a refresh scheduling scheme that can dynamically adjust the number of charge recycled half pages, which can save up to 30% of refresh energy at 85°C.

Algorithms for computational imaging and computer vision are rapidly evolving, and hardware must follow suit: the next generation of image signal processors (ISPs) must be “programmable” to support new algorithms created with high-level frameworks. In this work, we compare flexible ISP architectures, using applications written in the Darkroom image processing language. We target two fundamental architecture classes: programmable in time, as represented by SIMD, and programmable in space, as typified by coarse grain reconfigurable array architectures (CGRA). We consider several optimizations on these two base architectures, such as register file partitioning for SIMD, bus based routing and pipelined wires for CGRA, and line buffer variations. After these optimizations on average, CGRA provides 1.6x better energy efficiency and 1.4x better compute density versus a SIMD solution, and 1.4x the energy efficiency and 3.1x the compute density of an FPGA. However the cost of providing general programmability is still high: compared to an ASIC, CGRA has 6x worse energy and area efficiency, and this ratio would be roughly 10x if memory dominated applications were excluded.

Image processing algorithms implemented using custom hardware or FPGAs of can be orders-of-magnitude more energy efficient and performant than software. Unfortunately, converting an algorithm by hand to a hardware description language suitable for compilation on these platforms is frequently too time consuming to be practical. Recent work on hardware synthesis of high-level image processing languages demonstrated that a single-rate pipeline of stencil kernels can be synthesized into hardware with provably minimal buffering. Unfortunately, few advanced image processing or vision algorithms fit into this highly-restricted programming model. In this paper, we present Rigel, which takes pipelines specified in our new multi-rate architecture and lowers them to FPGA implementations. Our flexible multi-rate architecture supports pyramid image processing, sparse computations, and space-time implementation tradeoffs. We demonstrate depth from stereo, Lucas-Kanade, the SIFT descriptor, and a Gaussian pyramid running on two FPGA boards. Our system can synthesize hardware for FPGAs with up to 436 Megapixels/second throughput, and up to 297x faster runtime than a tablet-class ARM CPU.

Description of keypoints, or local image features, is widely employed in computer vision. However, the most successful techniques do not extend immediately to more than two spatial dimensions. In this paper, we describe robust methods for extracting local orientations and gradient histograms from higher-dimensional data, using these techniques to develop a three-dimensional analogue of the popular Scale-Invariant Feature Transform (SIFT). We apply our algorithm to intra-patient registration of magnetic resonance (MR) images, with promising results. Our implementation will be released as open-source software.

We describe Tethys, an energy-harvesting wireless water flow sensor that can monitor water use at a per-fixture level with the intention of associating water use with specific individuals. Tethys was motivated by recent efforts at Stanford University to reduce water use due to the California drought. Understanding how the university population uses water at per-person level can greatly influence policies and conservation approaches. Tethys uses Bluetooth Smart to both identify individuals as well as asynchronously upload data to the cloud for later analysis. We describe two challenges encountered in deploying Tethys: energy harvesting design and the mechanical considerations for high-pressure water at high temperatures.

Specialized image signal processors (ISPs) exploit the structure of image processing pipelines to minimize memory bandwidth using the architectural pattern of line-buffering , where all intermediate data between each stage is stored in small on-chip buffers. This provides high energy efficiency, allowing long pipelines with tera-op/sec. image processing in battery-powered devices, but traditionally requires painstaking manual design in hardware. Based on this pattern, we present Darkroom, a language and compiler for image processing. The semantics of the Darkroom language allow it to compile programs directly into line-buffered pipelines, with all intermediate values in local line-buffer storage, eliminating unnecessary communication with off-chip DRAM. We formulate the problem of optimally scheduling line-buffered pipelines to minimize buffering as an integer linear program. Finally, given an optimally scheduled pipeline, Darkroom synthesizes hardware descriptions for ASIC or FPGA, or fast CPU code. We evaluate Darkroom implementations of a range of applications, including a camera pipeline, low-level feature detection algorithms, and deblurring. For many applications, we demonstrate gigapixel/sec. performance in under 0.5mm 2 of ASIC silicon at 250 mW (simulated on a 45nm foundry process), real-time 1080p/60 video processing using a fraction of the resources of a modern FPGA, and tens of megapixels/sec. of throughput on a quad-core x86 processor.

All network devices must parse packet headers to decide how packets should be processed. A 64 × 10Gb/s Ethernet switch must parse one billion packets per second to extract fields used in forwarding decisions. Although a necessary part of all switch hardware, very little has been written on parser design and the trade-offs between different designs. Is it better to design one fast parser, or several slow parsers? What is the cost of making the parser reconfigurable in the field? What design decisions most impact power and area? In this paper, we describe trade-offs in parser design, identify design principles for switch and router designers, and describe a parser generator that outputs synthesizable Verilog that is available for download. We show that i) packet parsers today occupy about 1-2% of the chip, and ii) while future packet parsers will need to be programmable, this only doubles the (already small) area needed.

FPUs have been a topic of research for almost a century, leading to thousands of papers and books. Each advance focuses on the virtues of some specific new technique. This paper compares the energy efficiency of both throughput-optimized and latency-sensitive designs, each employing an array of optimization techniques, through a fair "apples to apples" methodology. This comparison required us to build many optimized FP units. We accomplished this by creating a highly parameterized FPgenerator, hierarchically encompassing lower-level generators for summation trees, Booth encoders, adders, etc. Having constructed this generator we quickly relearned a number of low-level issues that are critical and are often the most neglected by papers. By exploring cascade and fused multiply-add architectures across a variety of bit widths, summation trees, booth encoders, pipelining techniques, and pipe depths, we found that for most throughput based designs, a Booth-3 fused multiply-add architecture with a Wallace combining tree is optimal. For latency designs, we found that Booth-2 cascade multiply-add architectures are better. As we describe in the paper, Wallace is not always the optimal combining network due to wire delay and track count, and the precise way the CSA's are connected in the tree can make a larger difference than the type of tree used.

This paper focuses on the trade-off between flexibility and efficiency in specialized computing. We observe that specialized units achieve most of their efficiency gains by tuning data storage and compute structures and their connectivity to the data-flow and data-locality patterns in the kernels. Hence, by identifying key data-flow patterns used in a domain, we can create efficient engines that can be programmed and reused across a wide range of applications.

In Software Defined Networking (SDN) the control plane is physically separate from the forwarding plane. Control software programs the forwarding plane (e.g., switches and routers) using an open interface, such as OpenFlow. This paper aims to overcomes two limitations in current switching chips and the OpenFlow protocol: i) current hardware switches are quite rigid, allowing ``Match-Action'' processing on only a fixed set of fields, and ii) the OpenFlow specification only defines a limited repertoire of packet processing actions. We propose the RMT (reconfigurable match tables) model, a new RISC-inspired pipelined architecture for switching chips, and we identify the essential minimal set of action primitives to specify how headers are processed in hardware. RMT allows the forwarding plane to be changed in the field without modifying hardware. As in OpenFlow, the programmer can specify multiple match tables of arbitrary width and depth, subject only to an overall resource limit, with each table configurable for matching on arbitrary fields. However, RMT allows the programmer to modify all header fields much more comprehensively than in OpenFlow. Our paper describes the design of a 64 port by 10 Gb/s switch chip implementing the RMT model. Our concrete design demonstrates, contrary to concerns within the community, that flexible OpenFlow hardware switch implementations are feasible at almost no additional cost or power.

FFT design requires an exhaustive recoupling of data across successive stages of computation. The resulting memory access patterns have constantly-changing strides, making it hard to interleave the data for reliable conflict-free access of operand pairs. We modify an existing method of “swizzling” data locations so as to guarantee conflict-free access within any given stage and, with minimal support for buffering, we provide conflict-free access across the boundaries of adjoining stages as well. As a result, implementations that would naively require either a fully-associative, or at the very least a multiported register file, can be implemented using four single-ported banks of memory per butterfly unit, plus one bypass buffer. Because fewer ports means less area, and given that a butterfly must read two inputs and write two results for each cycle of operation, this solution should represent the least-area memory configuration for a resource-constrained FFT. Using this scheme, we show examples including a minimal one-butterfly FFT having 9% less area versus a competing equal-performance design and 20% better throughput versus a competing equal-area design.

This paper presents a design methodology forhardware synthesis of application-specific logic-in-memory(LiM) blocks. Logic-in-memory designs tightly integrate specializedcomputation logic with embedded memory, enablingmore localized computation, thus save energy consumption. Asa demonstration, we present an end-to-end design frameworkto automatically synthesize an interpolation based logic-in-memoryblock named interpolation memory, which combinesa seed table with simple arithmetic logic to efficiently evaluatefunctions. In order to support multiple consecutive seed dataaccess that is required in the interpolation operation, wesynthesize the physical memory into the novel rectangular accesssmart memory blocks. We evaluated a large designspace of interpolation memories in sub-20 nm commercialCMOS technology by using the proposed design framework.Furthermore, we implemented a logic-in-memory based computedtomography (CT) medical image reconstruction systemand our experimental results show that the logic-in-memorycomputing method achieves orders of magnitude of energysaving compared with the traditional in-processor computing.

Hardware modules would be much easier to reuse if they supported generic flexible high-level interfaces. However, these interfaces are rarely used since they lead to timing and area overheads compared to a customized design. This paper describes a reachability analysis framework that identifies over-provisioning in instances of flexible design, and offers a technique for annotating this information so that modern synthesis tools can remove most of the overhead. Results are demonstrated on a variety of flexible structures, including functional blocks, programmable state machines, and latency-insensitive interfaces.

Technology scaling has created a catch-22: technology now can do almost anything we want, but the NRE design costs are so high, that almost no one can afford to use it. Our current situation is reminiscent of the 1980's, when only a few companies could afford to produce custom silicon. Synthesis and placement and routing tools changed this, by providing modular tools with well defined interfaces that codified designer knowledge about the physical design of chips. Now we need a new set of tools that can codify designer knowledge about how to construct software, hardware, and validation to again enable application designers to produce chips. Researchers are developing methodologies that allow users to create hardware constructors, or generators. These include Genesis2, which extends SystemVerilog and enables the designer to encode hierarchical system construction procedurally. To demonstrate some of the capabilities that these languages and tools provide, we describe FPGen, a complete floating point generator written in Genesis2, that also generates the needed validation collateral and hints for the backend processes.

Sparse matrix-vector multiply (SpMV) is a critical task in the inner loop of modern iterative linear system solvers and exhibits very little data reuse. This low reuse means that its performance is bounded by main-memory bandwidth. Moreover, the random patterns of indirection make it difficult to achieve this bound. We present sparse matrix storage formats based on deduplicated memory. These formats reduce memory traffic during SpMV and thus show significantly improved performance bounds: 90x better in the best case. Additionally, we introduce a matrix format that inherently exploits any amount of matrix symmetry and is at the same time fully compatible with non-symmetric matrix code. Because of this, our method can concurrently operate on a symmetric matrix without complicated work partitioning schemes and without any thread synchronization or locking. This approach takes advantage of growing processor caches, but incurs an instruction count overhead. It is feasible to overcome this issue by using specialized hardware as shown by the recently proposed Hierarchical Immutable Content-Addressable Memory Processor, or HICAMP architecture.

To increase datacenter energy efficiency, we need memory systems that keep pace with processor efficiency gains. Currently, servers use DDR3 memory, which is designed for high bandwidth but not for energy proportionality. A system using 20% of the peak DDR3 bandwidth consumes 2.3× the energy per bit compared to the energy consumed by a system with fully utilized memory bandwidth. Nevertheless, many datacenter applications stress memory capacity and latency but not memory bandwidth. In response, we architect server memory systems using mobile DRAM devices, trading peak bandwidth for lower energy consumption per bit and more efficient idle modes. We demonstrate 3-5× lower memory power, better proportionality, and negligible performance penalties for data-center workloads.

We re-think DRAM power modes by modeling and characterizing inter-arrival times for memory requests to determine the properties an ideal power mode should have. This analysis indicates that even the most responsive of today's power modes are rarely used. Up to 88% of memory is spent idling in an active mode. This analysis indicates that power modes must have much shorter exit latencies than they have today. Wake-up latencies less than 100ns are ideal. To address these challenges, we present MemBlaze, an architecture with DRAMs and links that are capable of fast power up, which provides more opportunities to power down memories. By eliminating DRAM chip timing circuitry, a key contributor to power up latency, and by shifting timing responsibility to the controller, MemBlaze permits data transfers immediately after wake-up and reduces energy per transfer by 50% with no performance impact. Alternatively, in scenarios where DRAM timing circuitry must remain, we explore mechanisms to accommodate DRAMs that power up with less than perfect interface timing. We present MemCorrect which detects timing errors while MemDrowsy lowers transfer rates and widens sampling margins to accommodate timing uncertainty in situations where the interface circuitry must recalibrate after exit from power down state. Combined, MemCorrect and MemDrowsy still reduce energy per transfer by 50% but incur modest (e.g., 10%) performance penalties.

The implementation of merged floating-point multiply-add operations can be optimized in many ways. For latency sensitive applications, our cascade design reduces the accumulation dependent latency by 2x over a fused design, at a cost of a 13% increase in non-accumulation dependent latency. A simple in-order execution model shows this design is superior in most applications, providing 12% average reduction in FP stalls, and improves performance by up to 6%. Simulations of superscalar out-of-order machines show 4% average improvement in CPI in 2-way machines and 4.6% in 4-way machines. The cascade design has the same area and energy budget as a traditional fused multiple-add FMA.

With the growing complexity of synthetic biological circuits, robust and systematic methods are needed for design and test. Leveraging lessons learned from the semiconductor and design automation industries, synthetic biologists are starting to adopt computer-aided design and verification software with some success. However, due to the great challenges associated with designing synthetic biological circuits, this nascent approach has to address many problems not present in electronic circuits. In this session, three leading synthetic biologists will share how they have developed software tools to help design and verify their synthetic circuits, the unique challenges they face, and their insights into the next generation of tools for synthetic biology.

This paper proposes two practical approaches to address global convergence failures, commonly encountered in mixed-signal systems in which analog and digital components closely interact. That is, a nominally-working system may fail intermittently depending on its initial conditions upon start-up. The first approach uses a data clustering analysis and verifies global convergence with randomly-selected pilot simulations. The second approach adopts the practice of representing indeterminate states with X by defining its equivalent concept for analog based on entropy. With oscillator and phase-locked loop examples, it is demonstrated that the proposed approaches can effectively detect the failures and guide designers where to add more resets to prevent them.

Creating parameterized “chip generators” has been proposed as one way to decrease chip NRE costs. While many approaches are available for creating or generating flexible data path elements, the design of flexible controllers is more problematic. The most common approach is to create a microcoded engine as the controller, which offers flexibility through programmable table-based lookup functions. This paper shows that after “programming” the hardware for the desired application, or applications, these flexible controller designs can be easily converted to efficient fixed (or less programmable) solutions using partial evaluation capabilities that are already present in most synthesis tools.

Energy-efficient computation is critical if we are going to continue to scale performance in power-limited systems. For floating-point applications that have large amounts of data parallelism, one should optimize the throughput/mm2given a power density constraint. We present a method for creating a trade-off curve that can be used to estimate the maximum floating-point performance given a set of area and power constraints. Looking at FP multiply-add units and ignoring register and memory overheads, we find that in a 90 nm CMOS technology at 1 W/mm2, one can achieve a performance of 27 GFlops/mm2single precision, and 7.5 GFlops/mm double precision. Adding register file overheads reduces the throughput by less than 50 percent if the compute intensity is high. Since the energy of the basic gates is no longer scaling rapidly, to maintain constant power density with scaling requires moving the overall FP architecture to a lower energy/performance point. A 1 W/mm2design at 90 nm is a "high-energy" design, so scaling it to a lower energy design in 45 nm still yields a 7× performance gain, while a more balanced 0.1 W/mm2design only speeds up by 3.5× when scaled to 45 nm. Performance scaling below 45 nm rapidly decreases, with a projected improvement of only ~3x for both power densities when scaling to a 22 nm technology.

As analog and digital circuits have become more intertwined, we need to create a validation approach that handles both circuit types gracefully. This paper proposes a model-first approach, where one creates functional models of the analog blocks that will work in a HDL simulator, and then uses these models in the same way as HDL models are used for other standard cells: they are used in the full system validation, and the underlying implementations are validated to ensure they meet this specification. While creating functional models for the analog blocks might seem difficult, almost all analog blocks can be modeled as linear systems and we use this property to help create the required functional model.

This paper presents an approach to generate test vectors to characterize analog/mixed-signal circuits and its application to check the correspondence between a circuit and its HDL functional model. Interestingly, the abstract behavior of most analog circuits is a linear system, but sometimes only when viewed through a transformation of variables. When linearity holds, validation for the consistency between a circuit and a model can be efficiently performed with a small set of test vectors that grows linearly with the number of analog inputs. The linear abstraction for analog circuits also helps us distinguish different types of analog and digital I/O ports and verify their consistency effectively. We demonstrate the implemented tool by comparing a simple serial link receiver against its functional model.

The design of a digital system for energy efficiency often requires the analysis of circuit tradeoffs in addition to architectural tradeoffs. To assist with this analysis, we present a framework for performing joint exploration of both the architectural and circuit design spaces. In our approach, we use statistical inference techniques to create a model of a large micro-architectural design space from a small number of simulation samples. We then characterize the design tradeoffs of each of the underlying circuits and integrate these with the higher level architectural models to define the joint circuit-architecture design space. We use posynomial forms for all our models, enabling the use of convex optimization tools to efficiently search the joint design space. As an example, we apply this methodology to explore the power-performance tradeoffs in a dual-issue superscalar out-of-order processor, showing how the framework can be used to determine the optimal set of design parameters for energy efficiency. Compared to current architectural tools that use fixed circuit costs, joint optimization can reduce energy by up to 30% by considering circuit tradeoff characteristics.

Summary form only given. The IC industry is facing a huge paradox. On one hand, with the slowing of the performance and power gains provided by scaling, designers need to find new ways of delivering value to their customers. Historically this has meant creating more application specialized chips and systems. On the other hand the rising NRE costs for chip design (now over $10M/chip) has caused the number of chip design starts to fall. Everyone today seems to be talking about building programmable platforms to ensure the total available market is large enough to justify the chip design costs. To get out of this paradox, we need to change the way we think about chip design. Reducing digital NRE costs requires moving the end user designers up a level in abstraction. For many reasons I don't believe that either the current SoC, or high-level language effort will succeed. Instead, we should acknowledge that working out the interactions in a complex design is complex, and will cost a lot of money, even when we do it well. The key is to leverage this work over a broader class of chips. This approach leads to the idea of building chip-generators and not chips. That is instead of building a programmable chip to meet a broad class of application needs, you create a virtual programmable chip, that is MUCH more flexible than any real chip. The application designer (the new chip designer) will then configure this substrate to optimize for their application. The generator will take this information and then create the desired chip. While there are many very hard problems that need to be addressed to make this work, but none of them seem insurmountable. In fact I will provide some examples which indicate the promise of this approach like having the generator choose the core that is the most energy efficient for your application mix.

This paper proposes a circuit optimization approach that can ease the computational burden on the simulation-based circuit optimizers by leveraging simple design equations that reflect the designer's intent. The technique is inspired by continuation methods (a.k.a. homotopy) in numerical analysis where a hard problem is solved by constructing an easier problem first and gradually refining its solution to that of the hard problem. In a circuit optimization context, the designer's simplified equations for the circuit serve as the easier problem. These simplified design equations are easy to write as they need not be completely accurate and have intuitive, well-understood solutions. Nonetheless, in several circuit examples, it was found that the designer's equations serve as better guidance than the conventional, fixed-point equations. As a result, the proposed approach demonstrates the better convergence to the desired solution with less computational efforts.

Power consumption has become a major constraint in the design of processors today. To optimize a processor for energy-efficiency requires an examination of energy-performance trade-offs in all aspects of the processor design space, including both architectural and circuit design choices. In this paper, we apply an integrated architecture-circuit optimization framework to map out energy-performance trade-offs of several different high-level processor architectures. We show how the joint architecture-circuit space provides a trade-off range of approximately 6.5x in performance for 4x energy, and we identify the optimal architectures for different design objectives. We then show that many of the designs in this space come at very high marginal costs. Our results show that, for a large range of design objectives, voltage scaling is effective in efficiently trading off performance and energy, and that the choice of optimal architecture and circuits does not change much during voltage scaling. Finally, we show that with only two designs--a dual-issue in-order design and a dual-issue out-of-order design, both properly optimized-a large part of the energy-performance trade-off space can be covered within 3% of the optimal energy-efficiency.

Due to their high volume, general-purpose processors, and now chip multiprocessors (CMPs), are much more cost effective than ASICs, but lag significantly in terms of performance and energy efficiency. This paper explores the sources of these performance and energy overheads in general-purpose processing systems by quantifying the overheads of a 720p HD H.264 encoder running on a general-purpose CMP system. It then explores methods to eliminate these overheads by transforming the CPU into a specialized system for H.264 encoding. We evaluate the gains from customizations useful to broad classes of algorithms, such as SIMD units, as well as those specific to particular computation, such as customized storage and functional units.

Although there has been much interest in computational photography within the research and photography communities, progress has been hampered by the lack of a portable, programmable camera with sufficient image quality and computing power. To address this problem, we have designed and implemented an open architecture and API for such cameras: the Frankencamera. It consists of a base hardware specification, a software stack based on Linux, and an API for C++. Our architecture permits control and synchronization of the sensor and image processing pipeline at the microsecond time scale, as well as the ability to incorporate and synchronize external hardware like lenses and flashes. This paper specifies our architecture and API, and it describes two reference implementations we have built. Using these implementations we demonstrate six computational photography applications: HDR viewfinding and capture, low-light viewfinding and capture, automated acquisition of extended dynamic range panoramas, foveal imaging, IMU-based hand shake detection, and rephotography. Our goal is to standardize the architecture and distribute Frankencameras to researchers and students, as a step towards creating a community of photographer-programmers who develop algorithms, applications, and hardware for computational cameras.

This paper demonstrates that the steady-state and adjoint sensitivity analyses can be extended to stochastic mixed-signal systems based on Markov chain models. The examples of such systems include digital phase-locked loops and delta-sigma data converters, of which steady-state response is statistical in nature, consisting of an ensemble of waveforms with probability distribution. For efficient Markov-chain analysis, the paper describes three methods that can limit the number of states: a state discretization scheme based on Gaussian decomposition, a state exploration algorithm that discovers the recurrent states, and a state truncation algorithm that eliminates the states with negligible stationary probabilities. The stochastic AC analysis is performed by deriving a first-order ordinary differential equation governing the perturbations in the stationary probabilities and solving it via phasor analysis. In the digital PLL and first-order ΔΣ ADC examples, the number of states was reduced by a factor of 35 and the frequency-domain phase and noise transfer functions were simulated with a 57~22,000x speed-up compared to using transient, Monte-Carlo simulations.

Energy-performance tunable circuits enable the user to adjust the energy and performance of a chip after fabrication to suite the particular application, thus increase the overall power efficiency of the chip. Two tunable interconnect architectures are proposed. Pseudo-static interconnect achieves the same performance as static interconnect while consuming only 65% as much energy and provides 2X wider range for adjusting energy performance. Integration of pseudo-static interconnect in FPGA architecture does not require any system level changes. Pulse-mode interconnect provides marginal improvement at comparable power consumption but provides considerable performance boost when energy increases. Using pulses enables pulse-mode lookup tables with 2.5X higher speed at 2X higher power consumption and at the cost of significant system level changes.

As CPU cores become building blocks, we see a great expansion in the types of on-chip memory systems proposed for CMPs. Unfortunately, designing the cache and protocol controllers to support these memory systems is complex, and their concurrency and latency characteristics significantly affect the performance of any CMP. To address this problem, this paper presents a microarchitecture framework for cache and protocol controllers, which can aid in generating the RTL for new memory systems. The framework consists of three pipelined engines' request-tracking, state-manipulation, and data movement' which are programmed to implement a higher-level memory model. This approach simplifies the design and verification of CMP systems by decomposing the memory model into sequences of state and data manipulations. Moreover, implementing the framework itself produces a polymorphic memory system.

In the mid 1980's the power growth that accompanied scaling forced the industry to focus on CMOS technology, and leave nMOS and bipolars for niche applications. Twenty years later, CMOS technology is facing power issues of its own. After first reviewing the "cause" of the problem, it will become clear that there are not easy solutions this time -- no new technology or simple system/circuit change will rescue us. Power, and not number of devices is now the primary limiter of chip performance, and the need to create power efficient designs is changing how we do design. In the past, we would turn to specialized computation (ASICs) to create the needed efficiency, but the rising NRE costs for chip design (now over $10M/chip) has caused the number of ASIC design starts to fall not rise.

Building hardware prototypes for computer architecture research is challenging. Unfortunately, development of the required software tools (compilers, debuggers, runtime) is even more challenging, which means these systems rarely run real applications. To overcome this issue, when developing our prototype platform, we used the Tensilica processor generator to produce a customized processor and corresponding software tools and libraries. While this base processor was very different from the streamlined custom processor we initially imagined, it allowed us to focus on our main objective---the design of a reconfigurable CMP memory system---and to successfully tape out an 8-core CMP chip with only a small group of designers. One person was able to handle processor configuration and hardware generation, support of a complete software tool chain, as well as developing the custom runtime software to support three different programming models. Having a sophisticated software tool chain not only allowed us to run more applications on our machine, it once again pointed out the need to use optimized code to get an accurate evaluation of architectural features.

We propose a method of analytically characterizing processor performance as a function of circuit latencies. In our approach, we modify traditional simulation to use variables instead of fixed latencies for the internal functional units. The simulation engine then algebraically computes execution times, and the result is a mathematical equation which characterizes the performance space across numerous processor configurations. We discuss the computational complexity issues of this approach and show that instruction chunking and simple equation redundancy checking can make this approach feasible-we can model a large multi-dimensional design space with thousands to millions of design parameter combinations for about 10times the simulation time of a single conventional simulation run. We demonstrate our approach by exploring two different machines: a traditional MlPS-style in-order pipeline and the Intel Graphics Media Accelerator X3000.

Verification of chip multiprocessor memory systems remains challenging. While formal methods have been used to validate protocols, simulation is still the dominant method used to validate memory system implementation. Having a memory scoreboard, a high-level model of the memory, greatly aids simulation based validation, but accurate score-boards are complex to create since often they depend not only on the memory and consistency model but also on its specific implementation. This paper describes a methodology of using a relaxed scoreboard, which greatly reduces the complexity of creating these memory models. The relaxed scoreboard tracks the operations of the system to maintain a set of values that could possibly be valid for each memory location. By allowing multiple possible values, the model used in the scoreboard is only loosely coupled with the specific design, which decouples the construction of the checker from the implementation, allowing the checker to be used early in the design and to be built up incrementally, and greatly reduces the scoreboard design effort. We demonstrate the use of the relaxed scoreboard in verifying RTL implementations of two different memory models, Transactional Coherency and Consistency (TCC) and Relaxed Consistency, for up to 32 processors. The resulting checker has a performance slowdown of 19% for checking Relaxed Consistency, and less than 30% for TCC, allowing it to be used in all simulation runs.

There are two competing models for the on-chip memory in Chip Multiprocessor (CMP) systems: hardware-managed coherent caches and software-managed streaming memory . This paper performs a direct comparison of the two models under the same set of assumptions about technology, area, and computational capabilities. The goal is to quantify how and when they differ in terms of performance, energy consumption, bandwidth requirements, and latency tolerance for general-purpose CMPs. We demonstrate that for data-parallel applications on systems with up to 16 cores, the cache-based and streaming models perform and scale equally well. For certain applications with little data reuse, streaming scales better due to better bandwidth use and macroscopic software prefetching. However, the introduction of techniques such as hardware prefetching and nonallocating stores to the cache-based model eliminates the streaming advantage. Overall, our results indicate that there is not sufficient advantage in building streaming memory systems where all on-chip memory structures are explicitly managed. On the other hand, we show that streaming at the programming model level is particularly beneficial, even with the cache-based model, as it enhances locality and creates opportunities for bandwidth optimizations. Moreover, we observe that stream programming is actually easier with the cache-based model because the hardware guarantees correct, best-effort execution even when the programmer cannot fully regularize an application's code.

In this paper we explore the relationship between adder topology and energy efficiency. We compare the energy-delay tradeoff curves of selected 32- bit adder topologies, to determine how architectural features and design techniques affect energy efficiency. Optimizing different adders for the supply and threshold voltages, and transistor sizing, we show that topologies with the least number of logic stages having an average fanin of two per stage, and fewest wires are most energy efficient. While a design with fully custom sizes can be extremely tedious to layout, we show that custom sizing can be used as a guide to group different gates in the design, resulting in a manageable layout overhead without significant loss of energy efficiency.

This paper describes a noise-based method of estimating the effects of device random mismatch on circuit's transient response, such as delay and frequency. The proposed method models DC mismatch as equivalent AC pseudo-noise and exploits the fast periodic noise analysis (PNOISE) available in RF circuit simulators to compute the resulting variation in the circuit response. While the method relies on Gaussian mismatch distributions and linear perturbation model, it can model and analyze correlations as well as identify the most sensitive design parameter to mismatches with no additional simulation cost. Three benchmarks measuring the variations in the input offset voltage of a comparator, the delay of a logic path, and the frequency of an oscillator demonstrate the speed improvement of 100--1000x compared to a 1000-point Monte-Carlo method.

The drive for low-power, high performance computation coupled with the extremely high design costs for ASIC designs, has driven a number of designers to try to create a flexible, universal computing platform that will supersede the microprocessor. We argue that these flexible, general computing chips are trying to accomplish more than is commercially needed. Since design NRE costs are an order of magnitude larger than fabrication NRE costs, a two-step design system seems attractive. First, the users configure/program a flexible computing framework to run their application with the desired performance. Then, the system "compiles" the program and configuration, tailoring the original framework to create a chip that is optimized toward the desired set of applications. Thus the user gets the reduced development costs of using a flexible solution with the efficiency of a custom chip.

In this paper, a new technique for characterization of digital-to-analog converters (DAC) used in wideband applications is described. Unlike the standard narrowband approach, this technique employs least square estimation to characterize the DAC from dc to any target frequency. Characterization is performed using a random sequence with certain temporal and probabilistic characteristics suitable for intended operating conditions. The technique provides a linear estimation of the system and decomposes nonlinearity into higher-order harmonics and deterministic periodic noise. The technique can also be used to derive the impulse response of the converter, predict its operating bandwidth, and provide far more insight into its sources of distortion

Application of Discrete Multi-tone (DMT) signaling to high-speed backplane interconnects requires major modifications to the well-known analysis methods applied to wireline communication systems. Tight power budgets in backplane links impose severe constraints on DMT block size and use of channel shortening filters in the system. Consequently, maximum throughput is achieved in a DMT system that is (residual) interference limited and water-filling is not applicable in its original form. In this paper, the DMT system is cast as a Second Order Conic (SOQ problem with peak transmit power as the constraint and optimum integer bit-loading and power allocation are achieved through a novel incremental integer bit-loading algorithm. The convex framework is subsequently used to find "practical" upper bounds on the performance of multi-tone signaling over highspeed links. The results indicate that DMT has the potential to achieve 15-23 Gbps over typical backplane channels and system requirements in terms of FFT block size and prefix length are obtained.

This paper describes a method to perform linear AC analysis on mixed-signal systems which appear strongly nonlinear in the voltage domain but are linear in other variable domains. Common circuits like phase/delay-locked loops and duty-cycle correctors fall into this category, since they are designed to be linear with respect to phases, delays, and duty-cycles of the input and output clocks, respectively. The method uses variable domain translators to change the variables to which the AC perturbation is applied and from which the AC response is measured. By utilizing the efficient periodic AC (PAC) analysis available in commercial RF simulators, the circuit's linear transfer function in the desired variable domain can be characterized without relying on extensive transient simulations. Furthermore, the variable domain translators enable the circuits to be macromodeled as weakly-nonlinear systems in the chosen domain and then converted to voltage-domain models, instead of being modeled as strongly-nonlinear systems directly.

There are two basic models for the on-chip memory in CMP systems:hardware-managed coherent caches and software-managed streaming memory. This paper performs a direct comparison of the two modelsunder the same set of assumptions about technology, area, and computational capabilities. The goal is to quantify how and when they differ in terms of performance, energy consumption, bandwidth requirements, and latency tolerance for general-purpose CMPs. We demonstrate that for data-parallel applications, the cache-based and streaming models perform and scale equally well. For certain applications with little data reuse, streaming scales better due to better bandwidth use and macroscopic software prefetching. However, the introduction of techniques such as hardware prefetching and non-allocating stores to the cache-based model eliminates the streaming advantage. Overall, our results indicate that there is not sufficient advantage in building streaming memory systems where all on-chip memory structures are explicitly managed. On the other hand, we show that streaming at the programming model level is particularly beneficial, even with the cache-based model, as it enhances locality and creates opportunities for bandwidth optimizations. Moreover, we observe that stream programming is actually easier with the cache-based model because the hardware guarantees correct, best-effort execution even when the programmer cannot fully regularize an application's code.

The ability of a camera to record a high dynamic range image, whether by taking one snapshot or a sequence, is limited by the presence of veiling glare - the tendency of bright objects in the scene to reduce the contrast everywhere within the field of view. Veiling glare is a global illumination effect that arises from multiple scattering of light inside the camera's body and lens optics. By measuring separately the direct and indirect components of the intra-camera light transport, one can increase the maximum dynamic range a particular camera is capable of recording. In this paper, we quantify the presence of veiling glare and related optical artifacts for several types of digital cameras, and we describe two methods for removing them: deconvolution by a measured glare spread function, and a novel direct-indirect separation of the lens transport using a structured occlusion mask. In the second method, we selectively block the light that contributes to veiling glare, thereby attaining significantly higher signal-to-noise ratios than with deconvolution. Finally, we demonstrate our separation method for several combinations of cameras and realistic scenes.

Implementing a multi-tone (MT) architecture for high-speed backplane electrical links is difficult given the tight power and complexity constraints in this application. This paper proposes an approach that incorporates a baseband (BB) channel and a few passband (PB) channels. In this MT system inter- channel interference (ICI) and inter-symbol interference (ISI) are eliminated through fractionally spaced equalization at the transmitter and feedback equalization at the receiver. The design is modeled as a MIMO system, and optimal equalizer coefficients to minimize the transmit peak voltage are found by casting the optimization as a Second Order Conic (SOC) problem. In addition, for systems that need adaptation, we show how equalizer and power allocation coefficients can be obtained (sub optimally) using Zero Forcing (ZF) optimization. The effect of transmitter and receiver clock jitter are modeled in a way that can be included in both SOC and ZF optimizations, and the performance of this system is compared to more conventional baseband examples. It is shown that this AMT system can be built with complexity/power similar to a comparable performance baseband system, but has the ability to scale to higher bit rates.

By inserting a microlens array into the optical train of a conventional microscope, one can capture light fields of biological specimens in a single photograph. Although diffraction places a limit on the product of spatial and angular resolution in these light fields, we can nevertheless produce useful perspective views and focal stacks from them. Since microscopes are inherently orthographic devices, perspective views represent a new way to look at microscopic specimens. The ability to create focal stacks from a single photograph allows moving or light-sensitive specimens to be recorded. Applying 3D deconvolution to these focal stacks, we can produce a set of cross sections, which can be visualized using volume rendering. In this paper, we demonstrate a prototype light field microscope (LFM), analyze its optical performance, and show perspective views, focal stacks, and reconstructed volumes for a variety of biological specimens. We also show that synthetic focusing followed by 3D deconvolution is equivalent to applying limited-angle tomography directly to the 4D light field.

As integrated circuit technology continues to scale into the nanometer regime, the effect of crosstalk on circuit timing becomes significant. Static timing analysis shows that crosstalk routinely adds 10% to 20% delay to the critical path of a design. However, many aggressor/victim switching combinations are infeasible due to inherent circuit operating constraints, thereby contributing to the mismatch between timing analysis and actual silicon performance. This paper proposes a novel timing analysis technique where circuit functionality, delay, and crosstalk are simultaneously considered using time-sliced Boolean logic. The worst case timing on the critical path end point is calculated to be the minimum and maximum time slices where the timed Boolean logic on its coupled fanin cone is satisfiable. Up to 1-ns reduction in timing pessimism on 0.13-/spl mu/m industrial designs was observed. Furthermore, results on special circuit topologies such as data busses with coupled interleaved inverters match well with results from exhaustive Spice simulation sweeps with up to 50% reduction in timing pessimism over timing analysis that does not consider false coupling.

We present a novel photographic technique called dual photography, which exploits Helmholtz reciprocity to interchange the lights and cameras in a scene. With a video projector providing structured illumination, reciprocity permits us to generate pictures from the viewpoint of the projector, even though no camera was present at that location. The technique is completely image-based, requiring no knowledge of scene geometry or surface properties, and by its nature automatically includes all transport paths, including shadows, inter-reflections and caustics. In its simplest form, the technique can be used to take photographs without a camera; we demonstrate this by capturing a photograph using a projector and a photo-resistor. If the photo-resistor is replaced by a camera, we can produce a 4D dataset that allows for relighting with 2D incident illumination. Using an array of cameras we can produce a 6D slice of the 8D reflectance field that allows for relighting with arbitrary light fields. Since an array of cameras can operate in parallel without interference, whereas an array of light sources cannot, dual photography is fundamentally a more efficient way to capture such a 6D dataset than a system based on multiple projectors and one camera. As an example, we show how dual photography can be used to capture and relight scenes.

The advent of inexpensive digital image sensors and the ability to create photographs that combine information from a number of sensed images are changing the way we think about photography. In this paper, we describe a unique array of 100 custom video cameras that we have built, and we summarize our experiences using this array in a range of imaging applications. Our goal was to explore the capabilities of a system that would be inexpensive to produce in the future. With this in mind, we used simple cameras, lenses, and mountings, and we assumed that processing large numbers of images would eventually be easy and cheap. The applications we have explored include approximating a conventional single center of projection video camera with high performance along one or more axes, such as resolution, dynamic range, frame rate, and/or large aperture, and using multiple cameras to approximate a video camera with a large synthetic aperture. This permits us to capture a video light field, to which we can apply spatiotemporal view interpolation algorithms in order to digitally simulate time dilation and camera motion. It also permits us to create video sequences using custom non-uniform synthetic apertures.

Intersymbol interference (ISI) due to modal dispersion is the dominant limitation to the bit rate-distance product in multimode fiber-optic communication systems. If the light launched into the fiber excites only the desired principal modes, modal dispersion can be eliminated. We can achieve this by using spatial light modulators (SLMs) to perform adaptive spatial filtering on the electric fields of the light. In this paper, we develop an optimization framework for setting the SLMs to obtain an upper bound on the achievable performance and develop heuristics that nearly reach this upper bound Using this framework, we show that both a sophisticated semidefinite programming-based algorithm and a simple adaptive algorithm achieve performance close to the upper bound. Performance and system complexity tradeoff curves are constructed, showing that a 20/spl times/20 array of SLM pixels with binary phase control performs within 15% of more complex implementations. Finally, we extend the framework and present preliminary results showing the promise of further increases in the capabilities of multimode fiber by using the fiber as a multiple-input multiple-output (MIMO) transmission medium.

A multi-tone architecture is proposed for high-speed backplane serial links. To limit complexity, the links use analog multi-tone rather than the more modern DMT. The tradeoffs involved in the design of such a system are examined and the performance of a serial link based on this approach is compared to a baseband architecture in terms of data rate and complexity using a convex optimization framework. Slightly less than 2/spl times/ improvement in data rate at reasonable complexity is shown to be achievable with the proposed architecture.

Multi-Gb/s high-speed links face significant challenges in keeping up with the increase in desired data rates. In the evaluation of achievable data rates, it is necessary to include both link-specific noise sources and implementation driven constraints. We construct models of these noise sources and constraints in order to estimate the theoretical limits of typical high-speed link channels. In order to estimate the data rates of practical baseband architectures, we solve the power constrained optimal linear precoding problem and formulate a bit-error rate (BER) driven optimization, including all link-specific noise sources. The problem is shown to be quasiconcave, hence, a globally optimal solution is guaranteed. Using this optimization framework, we show that practical data rates are mainly limited by inter-symbol interference (ISI) due to complexity constraints on the number of precoder and equalizer taps. After these constraints are removed, we further show that slicer resolution and sampling jitter are limiting the higher bandwidth utilization provided by multi-level modulations. Better circuits are needed to improve the bandwidth utilization to more than 2bits/dimension in baseband.

Confocal microscopy is a family of imaging techniques that employ focused patterned illumination and synchronized imaging to create cross-sectional views of 3D biological specimens. In this paper, we adapt confocal imaging to large-scale scenes by replacing the optical apertures used in microscopy with arrays of real or virtual video projectors and cameras. Our prototype implementation uses a video projector, a camera, and an array of mirrors. Using this implementation, we explore confocal imaging of partially occluded environments, such as foliage, and weakly scattering environments, such as murky water. We demonstrate the ability to selectively image any plane in a partially occluded environment, and to see further through murky water than is otherwise possible. By thresholding the confocal images, we extract mattes that can be used to selectively illuminate any plane in the scene.

In this paper, a global clock network that incorporates standing waves and coupled oscillators to distribute a high-frequency clock signal with low skew and low jitter is described. The key design issues involved in generating standing waves on a chip are discussed, including minimizing wire loss within an available technology. A standing-wave oscillator, a distributed oscillator that sustains ideal standing waves on lossy wires, is introduced. A clock grid architecture comprised of coupled, standing-wave oscillators and differential, low-swing clock buffers is presented. The measured results for a prototyped standing-wave clock grid operating at 10GHz and fabricated in a 0.18μm 6M CMOS logic process are presented. A technique is proposed for on-chip skew measurements with sub-picosecond precision.

Today's rising power densities have been widely cited as the foremost challenge to continued CMOS scaling. In fact, the current power crisis is reminiscent of the final days previous technologies, such as the once popular bipolar and NMOS technologies and even vacuum tubes. How CMOS technology will respond to the current power challenge to extend CMOS scaling to sub-90nm technology is an important question for designer and CAD tool developers alike. With aggressive scaling a number of new challenges have arisen, such as leakage control, heat removal and power supply distribution, that need to be addressed using new design techniques in conjunction with new CAD solutions.This panel brings together experts in circuit design and CAD tool development to discuss the current status of low-power design and provide opinions on what new EDA capabilities are most important in the power-constrained design era. For instance, how will power be distributed in a robust fashion in sub-90nm ICs, and what are the critical EDA analysis and optimization capabilities? What are the best techniques for leakage reduction, not only in standby modes, but also in the active mode? And how far will voltage scaling take us in attacking the dynamic power consumption issue? What will a power-centric design flow look like and how will it change the way we design ICs? The objective of the panel is to explore these issues and formulate a list of critical issues that need to be addressed by the EDA community to enable successful scaling of CMOS into the sub-90nm era.

Recent analog design tools have started to allow designers to archive not only the sized schematics but also some of the objectives that the circuit is trying to achieve. This paper first describes STAR (Schematic Tool for Analog Reuse), a system that captures designer's knowledge as part of the archival circuit representation, and then describes how this system can be used to create portable design modules. Creating portable analog modules require more than just the optimization criteria for the cell. It must also include the constraints on the cell's environment (for proper operation), and how these constraints should scale with technology. Furthermore, the system must help the designer in the current task of creating the design, since it is rare that a designer thinks about creating IP for someone else. We demonstrate the capability and utility of this system by examining the reuse of a phase-locked loop.

Routers built around a single-stage crossbar and a centralized scheduler do not scale, and (in practice) do not provide the throughput guarantees that network operators need to make efficient use of their expensive long-haul links. In this paper we consider how optics can be used to scale capacity and reduce power in a router. We start with the promising load-balanced switch architecture proposed by C-S. Chang. This approach eliminates the scheduler, is scalable, and guarantees 100% throughput for a broad class of traffic. But several problems need to be solved to make this architecture practical: (1) Packets can be mis-sequenced, (2) Pathological periodic traffic patterns can make throughput arbitrarily small, (3) The architecture requires a rapidly configuring switch fabric, and (4) It does not work when linecards are missing or have failed. In this paper we solve each problem in turn, and describe new architectures that include our solutions. We motivate our work by designing a 100Tb/s packet-switched router arranged as 640 linecards, each operating at 160Gb/s. We describe two different implementations based on technology available within the next three years.

Recently, there has been considerable interest in providing "trusted computing platforms" using hardware~---~TCPA and Palladium being the most publicly visible examples. In this paper we discuss our experience with building such a platform using a traditional time-sharing operating system executing on XOM~---~a processor architecture that provides copy protection and tamper-resistance functions. In XOM, only the processor is trusted; main memory and the operating system are not trusted.Our operating system (XOMOS) manages hardware resources for applications that don't trust it. This requires a division of responsibilities between the operating system and hardware that is unlike previous systems. We describe techniques for providing traditional operating systems services in this context.Since an implementation of a XOM processor does not exist, we use SimOS to simulate the hardware. We modify IRIX 6.5, a commercially available operating system to create xomos. We are then able to analyze the performance and implementation overheads of running an untrusted operating system on trusted hardware.

We specify a hardware architecture that supports tamper-resistant software by identifying an "idealized" model, which gives the abstracted actions available to a single user program. This idealized model is compared to a concrete "actual" model that includes actions of an adversarial operating system. The architecture is verified by using a finite-state enumeration tool (a model checker) to compare executions of the idealized and actual models. In this approach, software tampering occurs if the system can enter a state where one model is inconsistent with the other in performing the verification, we detected a replay attack scenario and were able to verify the security of our solution to the problem. Our methods were also able to verify that all actions in the architecture are required, as well as come up with a set of constraints on the operating system to guarantee liveness for users.

Time division multiplexing (TDM) must be employed in multi-Gb/s transceivers in order to overcome onchip clock frequency limitations. This paper describes a transmit pre-emphasis filter for a multi-level transceiver making use of TDM. The possible applications of such a transceiver include serial links and chip-to-chip communication. The requirement of very low probability of error in the absence of coding, and the need for an adaptive solution impose a peak transmit power constraint. The TDM system is mapped to a multiple-input-multiple-output (MIMO) system, and the noise sources are analyzed. The design of the pre-emphasis filter is shown to be a non-convex optimization problem, whose optimal solution is very difficult to obtain. Still, sub-optimal solutions are derived in closed form and adaptive implementations are described. Simulation results using parameters obtained from an experimental testbed indicate that these sub-optimal solutions actually achieve very good performance.

This paper presents methods for efficient power minimization at circuit and micro-architectural levels. The potential energy savings are strongly related to the energy profile of a circuit. These savings are obtained by using gate sizing, supply voltage, and threshold voltage optimization, to minimize energy consumption subject to a delay constraint. The true power minimization is achieved when the energy reduction potentials of all tuning variables are balanced. We derive the sensitivity of energy to delay for each of the tuning variables connecting its energy saving potential to the physical properties of the circuit. This helps to develop understanding of optimization performance and identify the most efficient techniques for energy reduction. The optimizations are applied to some examples that span typical circuit topologies including inverter chains, SRAM decoders, and adders. At a delay of 20% larger than the minimum, energy savings of 40% to 70% are possible, indicating that achieving peak performance is expensive in terms of energy. Energy savings of about 50% can be achieved without delay penalty with the balancing of sizes, supplies, and thresholds.

This paper presents a method of using texture mapping with mipmapping to render a VLSI layout. Texture mapping is used to save already rasterized areas of the layout from frame to frame, and to take advantage of any hardware accelerated capabilities of the host platform. Mipmapping is used to select which textures to display so that the amount of information sent to the display is bounded, and the image rendered on the display is filtered correctly. Additionally, two caching schemes are employed. The first, used to bound memory consumption, is a general purpose cache that holds textures spatially close to the user's current viewpoint. The second, used to speed up the rendering process, is a cache of heavily used sub-designs that are precomputed so rasterization on the fly is not necessary.

This paper investigates the problem of minimizing the latency of iterative decoding of low-density parity check codes using the sum-product algorithm on a proposed low-complexity programmable pipelined parallel architecture. We present heuristic techniques for solving the NP-hard combinatorial optimization problems of mapping and scheduling the processing tasks of decoding an arbitrary LDPC code on n parallel pipelined processing units so as to minimize the total number of clock cycles required to complete a single decoding iteration. We compare the quality of result and running time of the proposed techniques to those of simple randomized techniques. We also investigate the effect of using local buffering at the pipelined processing units. In the case of zero local buffering, the proposed mapping and ordering techniques offer an improvement of 75.1% over randomized alternatives for the case of n=16. The proposed mapping technique always leads to an improvement of at least 11% over randomized mapping even if infinite local buffering is used. It is shown that a speedup factor of 1.12n-0.024n/sup 2/ can be achieved using a local buffer size of only 32 words.

Concern about the performance of wires wires in scaled technologies has led to research exploring other communication methods. This paper examines wire and gate delays as technologies migrate from 0.18-/spl mu/m to 0.035-/spl mu/m feature sizes to better understand the magnitude of the the wiring problem. Wires that shorten in length as technologies scale have delays that either track gate delays or grow slowly relative to gate delays. This result is good news since these "local" wires dominate chip wiring. Despite this scaling of local wire performance, computer-aided design (CAD) tools must still become move sophisticated in dealing with these wires. Under scaling, the total number of wires grows exponentially, so CAD tools will need to handle an ever-growing percentage of all the wires in order to keep designer workloads constant. Global wires present a more serious problem to designers. These are wires that do not scale in length since they communicate signals across the chip. The delay of these wives will remain constant if repeaters are used meaning that relative to gate delays, their delays scale upwards. These increased delays for global communication will drive architectures toward modular designs with explicit global latency mechanisms.

Although there have been attempts to develop code transformations that yield tamper-resistant software, no reliable software-only methods are know. This paper studies the hardware implementation of a form of execute-only memory (XOM) that allows instructions stored in memory to be executed but not otherwise manipulated. To support XOM code we use a machine that supports internal compartments---a process in one compartment cannot read data from another compartment. All data that leaves the machine is encrypted, since we assume external memory is not secure. The design of this machine poses some interesting trade-offs between security, efficiency, and flexibility. We explore some of the potential security issues as one pushes the machine to become more efficient and flexible. Although security carries a performance penalty, our analysis indicates that it is possible to create a normal multi-tasking machine where nearly all applications can be run in XOM mode. While a virtual XOM machine is possible, the underlying hardware needs to support a unique private key, private memory, and traps on cache misses. For efficient operation, hardware assist to provide fast symmetric ciphers is also required.

It is clear by now that scaling for CMOS will ultimately hit a roadblock, and require a radical change in fundamental device technology. And yet--we continue to make progress in making impressively small MOSFET devices, at 70nm, 50nm, 20nm.Suppose we can actually get to a 70nm or 50nm or smaller technology, where one device is only a few hundred atoms across. What might life be like down here? How (and why) do the lab versions of these devices work today? And what obstacles exist to using them in real circuits, on real chips? Can we really make wires and pins and other interconnect? Can we manufacture them reliably?And what happens out beyond this inevitable end-of-scaling barrier? What options have we for new device paradigms.Our three invited speakers will fearlessly speculate on what might lie ahead on this wild frontier from three different technical perspectives: highly scaled devices themselves, issues with highly scaled circuits and interconnect, and devices that might actually work out beyond the scaling limit.

Trends in VLSI technology scaling demand that future computing devices be narrowly focused to achieve high performance and high efficiency, yet also target the high volumes and low costs of widely applicable general purpose designs. To address these conflicting requirements, we propose a modular reconfigurable architecture called Smart Memories, targeted at computing needs in the 0.1 /spl mu/m technology generation. A Smart Memories chip is made up of many processing tiles, each containing local memory, local interconnect, and a processor core. For efficient computation under a wide class of possible applications, the memories, the wires, and the computational model can all be altered to match the applications. To show the applicability of this design, two very different machines at opposite ends of the architectural spectrum, the Imagine stream processor and the Hydra speculative multiprocessor, are mapped onto the Smart Memories computing substrate. Simulations of the mappings show that the Smart Memories architecture can successfully map these architectures with only modest performance degradation.

Article Vex—A CAD toolbox Share on Authors: Jules P. Bergmann Computer Systems Laboratory, Stanford University, Stanford, CA Computer Systems Laboratory, Stanford University, Stanford, CAView Profile , Mark A. Horowitz Computer Systems Laboratory, Stanford University, Stanford, CA Computer Systems Laboratory, Stanford University, Stanford, CAView Profile Authors Info & Claims DAC '99: Proceedings of the 36th annual ACM/IEEE Design Automation ConferenceJune 1999 Pages 523–528https://doi.org/10.1145/309847.309991Online:01 June 1999Publication History 3citation217DownloadsMetricsTotal Citations3Total Downloads217Last 12 Months1Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

This paper explores a standard-cell design methodology based on netlist partitioning as a solution for the problem of lack of convergence in the conventional methodology in deep submicron technologies.A synthesized design block is partitioned along unpredictable nets that are identified from the netlist structure.The size of each partition is restricted so that the longest possible local net in a partition can be sufficiently driven by an average library gate, hence allowing statistical wire-load modeling for the local nets.The block is resynthesized using a hybrid wire-load model that takes into a~count accurate wire-load information on the unpredictable nets derived after floorplanning the partitions, and uses custom statistical wire-load models within each partition.Final placement is restricted to respect the initial floorplan.The methodology was implemented using existing commercial tools for synthesis and layout.Experimental results show high correlation between synthesis estimates and post-placement measurements of wire-loads and gate delays with the new methodology.The trade-offs of partitioning, current limitations of the methodology and future work to overcome these limitations are also discussed.

State space techniques have proven to be useful for measuring and improving the coverage of test vectors that are used during functional validation via simulation. By comparing the state and edge coverage provided by tests with that which is possible in the design's state graph, the designer can estimate how well tested the design is and identify areas that need better testing. Unfortunately, for many interesting designs, the full state graph may be too large to fully explore, or if it is explorable, the resulting coverage may be so low as to provide limited feedback. Several techniques have been proposed that identify and work with an interesting subset of the design's state machines, but they still require computing the full state graph before projecting it. In this paper we discuss projection directed state exploration, in which a projection from the full graph is found while exploring only the relevant portion of the full graph. Even with this limited exploration, BDD size blowup is still a problem. To deal with this, we have also developed several interactive tools that provide feedback to the designer, and allow them to add hints to help with the exploration.

Interconnect scaling to deep submicron processes presents many challenges to today's CAD flows. A recent analysis by D. Sylvester and K. Keutzer (1998) examined the behavior of average length wires under scaling, and controversially concluded that current CAD tools are adequate for future module-level designs. We show that average length wire scaling is sensitive to the technology assumptions, although the change in their behavior is small under all reasonable scaling assumptions. However, examining only average length wires is optimistic, since long wires are the ones that primarily cause CAD tool exceptions. In a module of fixed complexity, under both optimistic and pessimistic scaling assumptions, the number of long wires will increase slowly with scaling. More importantly, as the overall die capacity grows exponentially, the number of modules and thus the total number of wires in a design will also increase exponentially. Thus, if the design team size and per-designer workload is to remain relatively constant, future CAD tools will need to handle long wires much better than current tools to reduce the percentage of wires that require designer intervention.

Clock skew is an increasing concern for high-speed circuit designers. Circuit designers use transparent latches and skew-tolerant domino circuits to hide clock skew from the critical path and take advantage of shared portions of the clock network to budget less skew between nearby elements than across the entire die, but current timing analysis algorithms do not handle correlated clock skews. This paper extends the Sakallah-Mudge-Olukotun (SMO) latch-based timing analysis to include different amounts of clock skew between different elements. The key change is that departure times from each latch must be defined with respect to launching clocks so that the skew between the launching and receiving clocks can be determined at each receiver. The exact analysis leads to an explosion in the number of timing constraints, but most constraints are not tight in practical situations and a modified version of the Szymanski-Shenoy relaxation algorithm gives exact results with only a small increase in runtime. The timing analysis formulation also captures the effects of skew on edge-triggered flip-flops, domino circuits, and min-delay constraints. Our exact algorithm, applied to a supercomputer node controller with over 12000 clocked elements, finds the system can run 50-90 ps faster than a single skew analysis would predict and requires searching fewer than 4% more latch departures than conventional algorithms. With the less conservative skew budgets enabled by better timing analysis, we expect clocked systems will remain viable to multi-GHz frequencies.

Approximate reachability tec hniques trade off accuracy with the capacity to deal with bigger designs. Cho et al [3] proposed approximate FSM traversal algorithms over a partition of the set of state bits. In this paper w egeneralize it by allowing projectionson to a collection of nondisjoint subsets of the state variables. We establish the adv an tageof ha ving overlapping projections and present a new multiple constr ainfunction for BDDs, to compute efficiently the approximate image during symbolic forward propagation using overlapping projections. We demonstrate the effectiveness of this new algorithm by applying it to several control modules from the I/O unit in the Stanford FLASH Multiprocessor. We also present our results on the larger ISCAS 89 benchmarks.

Memory latency is an important bottleneck in system performance that cannot be adequately solved by hardware alone. Several promising software techniques have been shown to address this problem successfully in specific situations. However, the generality of these software approaches has been limited because current architecturtes do not provide a fine-grained, low-overhead mechanism for observing and reacting to memory behavior directly. To fill this need, this article proposes a new class of memory operations called informing memory operations , which essentially consist of a memory operatin combined (either implicitly or explicitly) with a conditional branch-and-ink operation that is taken only if the reference suffers a cache miss. This article describes two different implementations of informing memory operations. One is based on a cache-outcome condition code, and the other is based on low-overhead traps. We find that modern in-order-issue and out-of-order-issue superscalar processors already contain the bulk of the necessary hardware support. We describe how a number of software-based memory optimizations can exploit informing memory operations to enhance performance, and we look at cache coherence with fine-grained access control as a case study. Our performance results demonstrate that the runtime overhead of invoking the informing mechanism on the Alpha 21164 and MIPS R10000 processors is generally small enough to provide considerable flexibility to hardware and software designers, and that the cache coherence application has improved performance compared to other current solutions. We believe that the inclusion of informing memory operations in future processors may spur even more innovative performance optimizations.

SRT [Sweeney, Robertson and Tocher (1958)] dividers are common in modern floating point units. Higher division performance is achieved by retiring more quotient bits in each cycle. Previous research has shown that realistic stages are limited to radix-2 and radix-4. Higher radix dividers are therefore formed by a combination of low-radix stages. In this paper, we present an analysis of the effects of radix-2 and radix-4 SRT divider architectures and circuit families on divider area and performance. We show the performance and area results for a wide variety of divider architectures and implementations. We conclude that divider performance is only weakly sensitive to reasonable choices of architecture but significantly improved by aggressive circuit techniques.

Current shared-memory multiprocessors are inherently vulnerable to faults: any significant hardware or system software fault causes the entire system to fail. Unless provisions are made to limit the impact of faults, users will perceive a decrease in reliability when they entrust their applications to larger machines. This paper shows that fault containment techniques can be effectively applied to scalable shared-memory multiprocessors to reduce the reliability problems created by increased machine size.The primary goal of our approach is to leave normal-mode performance unaffected. Rather than using expensive fault-tolerance techniques to mask the effects of data and resource loss, our strategy is based on limiting the damage caused by faults to only a portion of the machine. After a hardware fault, we run a distributed recovery algorithm that allows normal operation to be resumed in the functioning parts of the machine.Our approach is implemented in the Stanford FLASH multiprocessor. Using a detailed hardware simulator, we have performed a number of fault injection experiments on a FLASH system running Hive, an operating system designed to support fault containment. The results we report validate our approach and show that in conjunction with an operating system like Hive, we can improve the reliability seen by unmodified applications without substantial performance cost. Simulation results suggest that our algorithms scale well for systems up to 128 processors.

Hardware/software co-design is a methodology for solving design problems in systems with processors or embedded controllers where the design requirements mandate a functionality and performance level for the system, independent of the hardware and software boundary. In addition to the challenges of functional correctness and total system performance, design time is often a critical factor. To design MAGIC, the programmable memory and communication controller for the Stanford FLASH multiprocessor, the authors employed a hardware/software co-design methodology. This methodology allowed them to concurrently design the hardware and software thereby reducing design time while simultaneously ensuring that the design would meet ambitious performance goals. Serializing the hardware and software design would have lengthened the design time and significantly increased the amount of redesign when the tradeoffs between the hardware and software implementations became clear late in the design process. The co-design approach led them to build a series of hierarchical simulators that allowed them to begin design verification early and to reduce the level of effort required to ensure a functional design.

The functional validation of a state-of-the-art digital design is usually performed by simulation of a register-transfer-level model. The degree to which the test vector suite covers the important tests is known as the coverage of the suite. Previous coverage metrics have relied on measures such as the number of simulated cycles or number of toggles on a circuit node, which are indirect metrics at best. This paper proposes a new method of analyzing coverage based on projecting a minimized control finite-state graph onto control signals for the datapath part of the design to yield a meaningful metric and provide detailed feedback about missing tests. The largest hurdle is state-space explosion. We describe two methods of dealing with this in a practical manner and give results of applying this coverage analysis to parts of the node controller of the Stanford FLASH multiprocessor.

Memory latency is an important bottleneck in system performance that cannot be adequately solved by hardware alone. Several promising software techniques have been shown to address this problem successfully in specific situations. However, the generality of these software approaches has been limited because current architectures do not provide a fine-grained, low-overhead mechanism for observing and reacting to memory behavior directly. To fill this need, we propose a new class of memory operations called informing memory operations, which essentially consist of a memory operation combined (either implicitly or explicitly) with a conditional branch-and-link operation that is taken only if the reference suffers a cache miss. We describe two different implementations of informing memory operations---one based on a cache-outcome condition code and another based on low-overhead traps---and find that modern in-order-issue and out-of-order-issue superscalar processors already contain the bulk of the necessary hardware support. We describe how a number of software-based memory optimizations can exploit informing memory operations to enhance performance, and look at cache coherence with fine-grained access control as a case study. Our performance results demonstrate that the runtime overhead of invoking the informing mechanism on the Alpha 21164 and MIPS R10000 processors is generally small enough to provide considerable flexibility to hardware and software designers, and that the cache coherence application has improved performance compared to other current solutions. We believe that the inclusion of informing memory operations in future processors may spur even more innovative performance optimizations.

This paper presents a digital power supply controller for variable frequency and voltage circuits. By using a ring oscillator as a method of predicting circuit performance, the regulated voltage is set to the minimum required to operate at a reference frequency which maximizes energy efficiency. Our initial test silicon, implemented with a fixed frequency controller is analyzed and reveals that the controller's power consumption is a major limitation for such a design. To make the controller power dissipation scale with the CV/sup 2/f power of the load, we introduce a new architecture with variable frequency control, which allows the controller's supply and frequency to scale along with the load device.

Modern, high performance microprocessors are extremely complex machines which require substantial validation effort to ensure functional correctness prior to tapeout. Generating the corner cases to test these designs is a mostly manual process, where completion is hard to judge. Experience shows that the errors that are caught late in the design, many post-silicon, are interactions between different components in very improbable corner case situations. In this paper we present a technique that targets such error-causing interactions by automatically generating test vectors that will cause the processor to exercise all transitions of the control logic in simulation. We use techniques from formal verification to derive transition tours of a fully enumerated state graph of the control logic of the processor. Our system works from a Verilog description of the original machine and is currently being used to validate an embedded dual-issue processor in the node controller of the Stanford FLASH Multiprocessor. Modeling the processor control results in 200K states and an 8M instruction trace to check all transitions of control arcs.

A flexible communication mechanism is a desirable feature in multiprocessors because it allows support for multiple communication protocols, expands performance monitoring capabilities, and leads to a simpler design and debug process. In the Stanford FLASH multiprocessor, flexibility is obtained by requiring all transactions in a node to pass through a programmable node controller, called MAGIC. In this paper, we evaluate the performance costs of flexibility by comparing the performance of FLASH to that of an idealized hardwired machine on representative parallel applications and a multiprogramming workload. To measure the performance of FLASH, we use a detailed simulator of the FLASH and MAGIC designs, together with the code sequences that implement the cache-coherence protocol. We find that for a range of optimized parallel applications the performance differences between the idealized machine and FLASH are small. For these programs, either the miss rates are small or the latency of the programmable protocol can be hidden behind the memory access time. For applications that incur a large number of remote misses or exhibit substantial hot-spotting, performance is poor for both machines, though the increased remote access latencies or the occupancy of MAGIC lead to lower performance for the flexible design. In most cases, however, FLASH is only 2%–12% slower than the idealized machine.

There is an increasing trend to use commodity microprocessors as the compute engines in large-scale multiprocessors. However, given that the majority of the microprocessors are sold in the workstation market, not in the multiprocessor market, it is only natural that architectural features that benefit only multiprocessors are less likely to be adopted in commodity microprocessors. In this paper, we explore multiple-context processors, an architectural technique proposed to hide the large memory latency in multiprocessors. We show that while current multiple-context designs work reasonably well for multiprocessors, they are ineffective in hiding the much shorter uniprocessor latencies using the limited parallelism found in workstation environments. We propose an alternative design that combines the best features of two existing approaches, and present simulation results that show it yields better performance for both multiprogrammed workloads on a workstation and parallel applications on a multiprocessor. By addressing the needs of the workstation environment, our proposal makes multiple contexts more attractive for commodity microprocessors.

The FLASH multiprocessor efficiently integrates support for cache-coherent shared memory and high-performance message passing, while minimizing both hardware and software overhead. Each node in FLASH contains a microprocessor, a portion of the machine's global memory, a port to the interconnection network, The MAGIC chip handles all communication both within the node and among nodes, using hardwired data paths for efficient data movement and a programmable processor optimized for executing protocol operations. The use of the protocol processor makes FLASH very flexible/spl minus/it can support a variety of different communication mechanisms/spl minus/and simplifies the design and implementation. This paper presents the architecture of FLASH and MAGIC, and discusses the base cache-coherence and message-passing protocols. Latency and occupancy numbers, which are derived from our system-level simulator and our Verilog code, are given for several common protocol operations. The paper also describes our software strategy and FLASH's current status.>

The advent of high-bandwidth DRAMs poses a number of new challenges for test and characterization. This paper describes a collection of techniques that were used in the design and characterization of a new DRAM architecture with 500 MHz I/O signals. Methods of fixturing and calibration are presented for achieving system accuracies of better than 100 ps. Laboratory techniques for measuring critical circuit parameters such as path delay, clock jitter, current source strength, and pin capacitances are shown as well. These techniques, along with on-chip test logic, which allows the DRAM core to be tested using conventional low-speed memory test equipment, enable full characterization of high bandwidth memories.

Asymptotic waveform evaluation (AWE) is a waveform estimation technique which involves the computation of moments from a linear circuit followed by the generation of waveform estimates based on those moments. During moment computation a special case arises if there are capacitor cutsets or inductor loops. Methods proposed for handling these cases involve identifying the cutsets and loops and replacing one of the capacitors (inductors) with a dependent source. This note describes a different formulation of the problem. The elimination of redundant equations in order to compute moments can be viewed as the dual of the problem of reducing circuit equations to normal form. This formulation has a couple of interesting theoretical properties: (1) it formally handles all circuit topologies, including circuits with dependent sources for which the redundancies may be undetectable from an inspection of the circuit topology; and (2) it predicts that even networks without independent sources may have "hidden" particular solutions consisting of polynomials in t.>

Rsim is a switch-level simulator that can simulate large digital MOS integrated circuits up to three orders of magnitude faster than SPICE. Unfortunately, Rsim's simplified circuit models and timing analysis prevent it from simulating "difficult" CMOS circuits and circuits containing bipolar transistors. We address this shortcoming by adapting Rsim to use more general piecewise linear models. We show that these modifications can be made in a way that preserves Rsim's efficiency for the simplest cases. The result is a simulator that can approach the efficiency of dedicated switch-level simulators when switch-level models are used. Alternatively, greater accuracy and flexibility can be obtained when more sophisticated models are used.>

Rsim is a switch-level simulator which can simulate large digital MOS integrated circuits with speedups of over three orders of magnitude over SPICE. Unfortunately, Rsim's simple switched-resistor model renders it incapable of simulating certain CMOS and most BiCMOS and ECL digital circuits. We observe that the switched-resistor model is just one particular piecewise linear model and that Rsim's simulation framework can accommodate more elaborate piecewise linear models. The resulting simulator, Mom, combines the efficiency of switch-level simulation with the ability to simulate a wider variety of circuits. We demonstrate Mom's efficiency and flexibility on a variety of circuits.

The foremost goal of superscalar processor design is to increase performance through the exploitation of instruction-level parallelism (ILP). Previous studies have shown that speculative execution is required for high instruction per cycle (IPC) rates in non-numerical applications. The general trend has been toward supporting speculative execution in complicated, dynamically-scheduled processors. Performance, though, is more than just a high IPC rate; it also depends upon instruction count and cycle time. Boosting is an architectural technique that supports general speculative execution in simpler, statically-scheduled processors. Boosting labels speculative instructions with their control dependence information. This labelling eliminates control dependence constraints on instruction scheduling while still providing full dependence information to the hardware. We have incorporated boosting into a trace-based, global scheduling algorithm that exploits ILP without adversely affecting the instruction count of a program. We use this algorithm and estimates of the boosting hardware involved to evaluate how much speculative execution support is really necessary to achieve good performance. We find that a statically-scheduled superscalar processor using a minimal implementation of boosting can easily reach the performance of a much more complex dynamically-scheduled superscalar processor.

We examine two multiple-context schemes in the context of scalable shared-memory multiprocessors. The blocked scheme switches between contexts at cache misses. The proposed interleaved scheme switches between available contexts on a cycle-by-cycle basis, while providing full pipeline interlocks for good single-context performance. We show the interleaved scheme to have a performance advantage over the blocked scheme due to its ability to hide pipeline dependencies and reduce the context switch cost. We also show that, while the implementation of the interleaved scheme is more complex, this complexity is not overwhelming.

A full-custom VLSI chip demonstrates an arithmetic implementation for computing the mantissa of a 54-b (floating-point double-precision) division operation in 45 ns to 160 ns, depending on the data. The design uses self-timing to avoid the need to partition logic into clock cycles and the need for high-speed clocks. Self-timing allows the circuits to iterate with no overhead over the pure combinational logic delays. It also allows a greater-efficiency symmetric overlapped execution of the SRT stages because of dynamic path ordering. The design has several other performance enhancements, and their effects on the performance are discussed. The total effect of all the performance enhancements provides a factor of two increase in performance due to architectural improvements over a straightforward SRT approach.>

A completion-detection method is proposed for efficiently implementing Boolean functions as self-timed logic structures. Current-sensing completion detection (CSCD) allows self-timed circuits to be designed using single-rail variable encoding (one signal wire per logic variable) and implemented in about the same silicon area as an equivalent synchronous implementation. Compared to dual-rail encoding methods, CSCD can reduce the number of signal wires and transistors used by approximately 50%. CSCD implementations improved performance over equivalent dual-rail designs because of: reduced parasitic capacitance, removal of spacer tokens in the data stream, and computation state similarity of consecutive data variables. Several CSCD configurations are described and evaluated and transistor-level implementations are provided for comparison.>

Directory-based protocols have been proposed as an efficient means of implementing cache consistency in large-scale shamxlmemory multiprocessors.One class of these protocols utilizes a limited pointers directory, which stores the identities of a small number of caches containing a given block of data.However, the performance potential of these directories in large-scale machines has been speculative at best.In this paper we introduce an analytic model that not only explains the behavior seen in small-scale simulation studies, but also allows us to extrapolate forward to evaluate the efficiency of limited pointers directories in large-scale systems.Our model shows that miss rates inherent to invalidation-based consistency schemes me relatively high (typically 107o to 60Y0) for actively shared da~across a variety of workloads.We find that limited pointers schemes that resort to broadcasting invalidations when the pointers are exhausted perform very poorly in largescale machines, even if there are sufficient pointers most of the time.On the other han~no-broadcast strategies that limit the degree of caching to the number of pointers in an entry have only a modest impact on the cache miss rate and network traffic under a wide range of workloads, including those in which data blocks are actively accessed by a large number of processors.

This paper describes a superscalar processor that combines the best qualities of static and dynamic instruction scheduling to increase the performance of non-numerical applications. The architecture performs all instruction scheduling statically to take advantage of the compiler's ability to efficiently schedule operations across many basic blocks. Since the conditional branches in non-numerical code are highly data dependent, the architecture introduces the concept of boosted instructions, instructions that are committed conditionally upon the result of later branch instructions. Boosting effectively removes the dependencies caused by branches and makes the scheduling of side-effect instructions as simple as those that are side-effect free. For efficiency, boosting is supported in the hardware by shadow structures that temporarily hold the side effects of boosted instructions until the conditional branches that the boosted instructions depend upon are executed. When the branch condition is determined, the buffered side effects are either committed or squashed. The limited static scheduler in our evaluation system shows that a 1.6-times speedup over scalar code is achievable by boosting instructions above only a single conditional branch. This performance is similar to the performance of a pure dynamic scheduler.

Analysis of power distribution in VLSI circuits requires the solution of a large network of resistors and current sources. Fortunately, these resistor networks have certain characteristic properties that permit partitioning into smaller, easier to solve sections. The authors present a set of techniques that can be used to identify and quickly solve three characteristic network configurations: trees, simple loops, and series resistors with interspersed current sources. Methods for efficiently solving other sections of the network are also explored. System performance of several designs is reported.>

Several technology independent rounding algorithms for multiplying normalized numbers are presented. The first is a simple rounding algorithm suitable for software simulation or moderate performance hardware multipliers. The next two algorithms are parallel addition schemes suitable for high-performance VLSI multipliers. One of them eliminates the carry produced by the lower-order bits from the critical path. Several methods for computing the sticky bit are also presented. Included is a new fast and efficient technique for computing the sticky bit directly from the carry-save form without undergoing the expense of a carry-propagate addition.>

This paper investigates the limitations on designing a processor which can sustain an execution rate of greater than one instruction per cycle on highly-optimized, non-scientific applications. We have used trace-driven simulations to determine that these applications contain enough instruction independence to sustain an instruction rate of about two instructions per cycle. In a straightforward implementation, cost considerations argue strongly against decoding more than two instructions in one cycle. Given this constraint, the efficiency in instruction fetching rather than the complexity of the execution hardware limits the concurrency attainable at the instruction level.

This paper describes IRSIM, an incremental switch-level simulator for MOS transistor circuits. In IRSIM, the circuit under simulation can be modified and then incrementally resimulated. This allows error correction and circuit operation verification to be performed in time proportional to the size of the modifications rather than the size of the entire circuit. To accomplish this incremental simulation, IRSIM maintains a history of circuit activity during simulation and only resimulates the sections of the circuit that deviate from their history. The program was tested on several corrections to errors that actually occurred in the design of a VLSI microprocessor. These errors were corrected and the circuit was incrementally resimulated 1.6 to 3500 times faster than simulating the entire circuit.

The increasing speed of new generation processors will exacerbate the already large difference between CPU cycle times and main memory access times. As this difference grows, it will be increasingly difficult to build single-level caches that are both fast enough to match these fast cycle times and large enough to effectively hide the slow main memory access times. One solution to this problem is to use a multi-level cache hierarchy. This paper examines the relationship between cache organization and program execution time for multi-level caches. We show that a first-level cache dramatically reduces the number of references seen by a second-level cache, without having a large effect on the number of second-level cache misses. This reduction in the number of second-level cache hits changes the optimal design point by decreasing the importance of the cycle-time of the second-level cache relative to its size. The lower the first-level cache miss rate, the less important the second-level cycle time becomes. This change in relative importance of cycle time and miss rate makes associativity more attractive and increases the optimal cache size for second-level caches over what they would be for an equivalent single-level cache system.

Trace-driven simulation and hardware measurement are the techniques most often used to obtain accurate performance figures for caches. The former requires a large amount of simulation time to evaluate each cache configuration while the latter is restricted to measurements of existing caches. An analytical cache model that uses parameters extracted from address traces of programs can efficiently provide estimates of cache performance and show the effects of varying cache parameters. By representing the factors that affect cache performance, we develop an analytical model that gives miss rates for a given trace as a function of cache size, degree of associativity, block size, subblock size, multiprogramming level, task switch interval, and observation interval. The predicted values closely approximate the results of trace-driven simulations, while requiring only a small fraction of the computation cost.

Bisim is an event-driven, transistor-level, logic simulator that models both the logical and timing characteristics of custom emitter-coupled-logic/current-mode-logic circuits. Node voltages are represented by piecewise-linear waveforms, transistor currents are represented by piecewise-constant waveforms, and transistors are modeled as voltage-controlled current switches. Bisim's realistic circuit models enable it to simulate correctly a wide variety of circuit topologies while retaining much of the speed of higher level simulators.>

The problem of cache coherence in shared-memory multiprocessors is addressed using two basic approaches: directory schemes and snoopy cache systems. Directory schemes for cache coherence are potentially attractive in large multiprocessor systems that are beyond the scaling limits of the snoopy cache schemes. Slight modifications to directory schemes can make them competitive in performance with snoopy cache schemes for small multiprocessors. Trace-driven simulation, using data collected from several real multiprocessor applications, is used to compare the performance of standard directory schemes, modifications to these schemes, and snoopy cache protocols. In addition, the simulations show that most blocks that are written into are present in only a small number of other caches, which makes broadcast invalidates inefficient. This result suggests that a directory structure that stores with each block only a small number of pointers to caches containing the block is sufficient.>

A series of simulations that explore the interactions between various organizational decisions and program execution time are presented. The tradeoffs between cache size and CPU/cache cycle-time, set associativity and cycle time, and block size and main-memory speed, are investigated. The results indicate that neither cycle time nor cache size dominates the other across the entire design space. For common implementation technologies, performance is maximized when the size is increased to the size is increased to the 32-kB to 128-kB range with modest penalties to the cycle time. If set associativity impacts the cycle time by more than a few nanoseconds, it increases overall execution time. Since the block size and memory-transfer rate combine to affect the cache miss penalty, the optimum block size is substantially smaller than that which minimizes the miss rate. The interdependence between optimal cache configuration and the main memory speed necessitates multilevel cache hierarchies for high-performance uniprocessors.>

Large caches are necessary in current high-performance computer systems to provide the required high memory bandwidth. Because a small decrease in cache performance can result in significant system performance degradation, accurately characterizing the performance of large caches is important. Although measurements on actual systems have shown that operating systems and multiprogramming can affect cache performance, previous studies have not focused on these effects. We have developed a program tracing technique called ATUM (Address Tracing Using Microcode) that captures realistic traces of multitasking workloads including the operating system. Examining cache behavior using these traces from a VAX processor shows that both the operating system and multiprogramming activity significantly degrade cache performance, with an even greater proportional impact on large caches. From a careful analysis of the causes of this degradation, we explore various techniques to reduce this loss. While seemingly little can be done to mitigate the effect of system references, multitasking cache miss activity can be substantially reduced with small hardware additions.

This paper describes using adjacency lists to incrementally generate design rule spacing constraints. The algorithm generates the smallest complete set of constraints for a design, yielding fast compaction, and is as fast or faster than ordinary constraint generation methods even when the incremental features are not used. The adjacency list data structure allows one to very quickly move, insert or delete objects and generate an updated set of constraints.

This paper describes an extractor designed to produce resistance values for use in digital circuit simulation. REDS avoids resistance extraction on most nets in a design using a simple filter based on the perimeter and area values calculated by the capacitance extractor, allowing it to concentrate on areas where resistance may substantially affect circuit timing. Nets are extracted using a fast square counting algorithm, and simplified before output to remove spurious elements. REDS is designed to work on the Magic layout database.

The design of a RISC processor requires a careful analysis of the tradeoffs that can be made between hardware complexity and software. As new generations of processors are built to take advantage of more advanced technologies, new and different tradeoffs must be considered. We examine the design of a second generation VLSI RISC processor, MIPS-X.

This paper addresses various timing and glitch detection issues in switch-level simulation. Particular attention is focused on charge sharing. We categorize and analyze problems caused by charge sharing. Solutions to these problems are proposed and applied to real designs. Results are reported and compared with SPICE simulation. The computational complexity of our methods is also investigated.

Trace-driven simulation is often used in the design of computer systems, especially caches and translation lookaside buffers. Capturing address traces to drive such simulations has been problematic, often involving 1000:1 software overhead to trace a target workload, and/or mechanisms that cause significant distortions in the recorded data. A new technique for capturing address traces has been developed to use a processor's microcode to record addresses in a reserved part of main memory as a side effect of normal execution. An experimental implementation of this technique on a VAX 1 8200 processor shows a number of advantages over previous techniques, including fewer distortions of the address trace and a hundred times faster recording. With this technique, it is possible to gather full operating-system traces of multi-tasking workloads.

This paper presents a new algorithm to extract resistance values from an integrated circuit artwork description. Instead of trying to solve for the exact resistance values, heuristics are used to find an approximate solution. The algorithm first breaks the input polygons into simple pieces, and then finds the resistance through each piece. This procedure enables the extraction to be both fast and memory efficient. The heuristics used for splitting the polygons and calculating the pieces' resistance are derived from rules of electrostatics, and yield answers that are within 10 percent of the exact resistance values. The operations needed to break complex polygons into simpler pieces are very similar to other geometric operations used in artwork analysis systems.

In MOS integrated circuits, signals may propagate between stages with fanout. The exact calculation of signal delay through such networks is difficult. However, upper and lower bounds for delay that are computationally simple are presented in this paper. The results can be used 1) to bound the delay, given the signal threshold, or 2) to bound the signal voltage, given a delay time, or 3) certify that a circuit is "fast enough," given both the maximum delay and the voltage threshold.