Emerging Machine Learning (ML) workloads, particularly those deployed at the edge, increasingly rely on a network of Deep Neural Networks (DNNs), where each model is tailored to a specific task. The primary challenge is efficiently utilizing all available resources simultaneously on heterogeneous multi-processor system-on-chips (MPSoCs) when executing these computationally demanding multi-DNN workloads. This becomes even more complicated because inference behavior can vary with batch size, input content, and runtime dynamics. This paper presents a novel framework to schedule the execution of multi-DNN workloads on a heterogeneous MPSoC with the goal of minimizing the latency of the workload execution. The proposed approach uses a reinforcement learning (RL) framework to handle three major sources of variability, including differences in DNN execution and batching due to hardware heterogeneity, workload fluctuations driven by input content, and runtime execution unpredictability caused by system-level constraints. The RL method integrates a graph neural network (GNN) and a pointer-based policy network to adapt to stochastic execution behavior. GNN-based embeddings enable scalable and efficient scheduling decisions across diverse workload conditions. The proposed approach achieves up to 6.2× and 2.0× performance improvement over CAMDNN and HEFT, respectively, when evaluated on a Qualcomm RB5 development kit.

Transprecision computing (TC) is a promising approach for energy-efficient machine learning (ML) computation on resource-constrained platforms. This work presents a novel ASIC design of a Transprecision Arithmetic and Logic Unit (TALU) that can support multiple number formats: Posit, Floating Point (FP), and Integer (INT) data with variable bitwidth of 8, 16, and 32 bits. Additionally, TALU can be reconfigured in runtime to support TC without overprovisioning the hardware. Posit is a new number format, gaining traction for ML computations, producing similar accuracy in lower bitwidth than FP representation. This paper thus proposes a novel algorithm for decoding Posit for energy-efficient computation. TALU implementation achieves a 54.6× reduction in power consumption and 19.8× reduction in the area as compared to a state-of-the-art unified MAC unit (UMAC) [1] for Posit and FP computation. Experimental results on an ML compute kernel executed on a Vector Processor of TALUs integrated with a RISC-V processor achieves about 2× improvement in energy efficiency and similar throughput as compared to a state-of-the-art TC-based vector processor.

This paper presents a novel approach for executing the inference of a network of pre-trained deep neural networks (DNNs) on commercial-off-the-shelf devices that are deployed at the edge. The problem is to partition the computation of the DNNs between an energy-constrained and performance-limited edge device$\boldsymbol{\mathcal{E}}$, and an energy-unconstrained, higher performance device$\boldsymbol{\mathcal{C}}$, referred to as thecloudlet, with the objective of minimizing the energy consumption of$\boldsymbol{\mathcal{E}}$subject to a deadline constraint. The proposed partitioning algorithm takes into account the performance profiles of executing DNNs on the devices, the power consumption profiles, and the variability in the delay of the wireless channel. The algorithm is demonstrated on a platform that consists of an NVIDIA Jetson Nano as the edge device$\boldsymbol{\mathcal{E}}$and a Dell workstation with a Titan Xp GPU as the cloudlet. Experimental results show significant improvements both in terms of energy consumption of$\boldsymbol{\mathcal{E}}$and processing delay of the application. Additionally, it is shown how the energy-optimal solution is changed when the deadline constraint is altered. Moreover, the overhead of decision-making for our proposed method is significantly lower than the state-of-the-art Integer Linear Programming (ILP) solutions.

Transformers-based language models have achieved remarkable accuracy in various NLP tasks, employing self-attention mechanisms primarily based on matrix multiplication. However, their significant size leads to data movement issues, causing latency and energy efficiency challenges in conventional Von-Neumann systems. To mitigate these issues, several in-memory and near-memory architectures have been proposed. This paper introduces PACT-3D, a near-memory architecture featuring novel computing units integrated with DRAM banks. PACT-3D significantly reduces latency by 1.7 × and improves energy efficiency by 18.7 × compared to state-of-the-art near-memory architectures.

Decades of progress in energy-efficient and low-power design have successfully reduced the operational carbon footprint in the semiconductor industry. However, this has led to increased embodied emissions, arising from design, manufacturing, and packaging. While existing research has developed tools to analyze embodied carbon for traditional monolithic systems, these tools do not apply to near-mainstream heterogeneous integration (HI) technologies. HI systems offer significant potential for sustainable computing by minimizing carbon emissions through two key strategies: “reducing” computation by “reusing” pre-designed chiplet IP blocks and adopting hierarchical approaches to system design. The reuse of chiplets across multiple designs, even spanning multiple generations of ICs, can substantially reduce carbon emissions throughout the lifespan. This paper introduces ECO-CHIP, a carbon analysis tool designed to assess the potential of HI systems toward sustainable computing by considering scaling, chip let, and packaging yields, design complexity, and even overheads associated with advanced packaging techniques. Experimental results from ECO-CHIP demonstrate that HI can reduce embodied carbon emissions by up to 30% compared to traditional monolithic systems. ECO-CHIP is integrated with other chiplet simulators and is applied to chiplet disaggregation considering other metrics such as power, area, and cost. ECO-CHIP suggests that HI can pave the way for sustainable computing practices.

The growing complexity of machine learning (ML) tasks drives the rapid deployment of multi-tenant ML workloads at the edge presenting unique challenges due to the variable computational demands and strict latency requirements. This paper introduces a holistic elastic scheduler, EMERALD, designed to optimize the execution of multi-tenant machine learning (ML) workloads on heterogeneous edge (Multiprocessor System on Chip) MPSoCs under strict runtime constraints. EMERALD employs input resolution scaling to dynamically adjust the computational demands of deep neural networks (DNNs), thereby enhancing the ability to meet stringent latency requirements while maintaining high accuracy. The scheduler consists of two main components: a local greedy scheduler and a global scheduler. The local scheduler actively manipulates input resolution in response to deadline violations, selecting the resolutions that minimally impact accuracy and maximally reduce response time. The global scheduler, an Integer Linear Programming (ILP)based scheduler, fine-tunes the decisions of the local scheduler by considering factors such as DNN dependencies, scene complexity, hardware heterogeneity, and the trade-offs between accuracy and makespan associated with input scaling adjustments. This hierarchical approach allows EMERALD to effectively balance computational efficiency and accuracy, significantly reducing missed deadlines—achieving 11x and 12.3x fewer missed deadlines compared to CAMDNN and HEFT, respectively, in scenarios demanding 30 frames per second. The results underscore the critical role of adaptive input scaling in managing the complexities of edge-based ML deployments.

This work consists of two main components: designing a hardware-software co-design, MT+, for adapting the Mikami-Tabuchi algorithm for on-board path planning by drones in a 3D environment; and development of a specialized custom hardware accelerator CDU, as a part of MT+, for parallel collision detection. Collision detection is a performance bottleneck in path planning. MT+reduces the delay in path planning without using any heuristic. A comparative analysis between the state-of-the-art path planning algorithm A* and Mikami-Tabuchi is performed to show that Mikami-Tabuchi is faster than A* in typical real-world environments. In custom-generated environments, path planning using Mikami-Tabuchi shows a latency improvement of 1.7× across varying average sizes of obstacles and 2.7× across varying obstacle density over state-of-the-art path planning algorithm, A*. Further, the experiments show that the co-design achieves speedups over a full software implementation on CPU, averaging between 10% to 60% across different densities and sizes of obstacles. CDU area and power overheads are negligible against a conventional single-core processor.

DRAM-based near-memory architectures are recognized for their ability to deliver substantial energy efficiency and throughput to execute data-intensive tasks. However, the inherent limitations regarding area, power, and timing within DRAM allow the integration of only primitive processing elements with limited operations and application support. This paper introduces a near-memory processing architecture based on DRAM featuring a novel computing unit termed the neuron processing element (NPE). NPEs are capable of performing multiple arithmetic, logical, and predicate operations. With a well-defined instruction set, the NPEs can be programmed to support standard data formats for floating point and fixed point precision used in different AI/ML and signal processing applications. They can be dynamically reconfigured to switch operations during run-time without increasing overall latency or power consumption. The NPEs have a small area and power footprint compared to conventional MAC units and other functionally equivalent implementations, making them suitable for integration with DRAM without compromising its organization or timing constraints. Furthermore, this paper shows a substantial improvement in latency and energy consumption compared to prior in-memory architectures and demonstrates the efficacy of the proposed architecture for the acceleration of neural network inference.

This paper presents TULIP, a new architecture for a variable precision Quantized Neural Network (QNN) inference. It is designed with the goal of maximizing energy efficiency per classification. TULIP is constructed by arranging a collection of unique processing elements (TULIP-PEs) in a single instruction multiple data (SIMD) fashion. Each TULIP-PE contains binary neurons that are interconnected using multiplexers. Each neuron also has a small dedicated local register connected to it. The binary neurons are implemented as standard cells and used for implementing threshold functions, i.e., an inner-product and thresholding operation on its binary inputs. The neurons can be reconfigured with a single change in the control signals to implement all the standard operations used in a QNN. This paper presents novel algorithms for implementing the operations of a QNN on the TULIP-PEs in the form of a schedule of threshold functions. TULIP was implemented as an ASIC in TSMC 40nm-LP technology. A QNN accelerator that employs a conventional MAC-based arithmetic processor was also implemented in the same technology to provide a fair comparison. The results show that TULIP is 30-50X more energy-efficient than an equivalent design, without any penalty in performance, area, or accuracy. Furthermore, TULIP achieves these improvements without using traditional techniques such as voltage scaling or approximate computing. Finally, the paper also demonstrates how the run-time trade-off between accuracy and energy efficiency is done on the TULIP architecture.

This paper presents a mixed-signal architecture for implementing Quantized Neural Networks (QNNs) using flash transistors, to achieve extremely high throughput with extremely low power, energy and memory requirements. Its low resource utilization makes our design especially suited for use in edge devices. The network weights are stored in-memory using flash transistors, and neurons perform operations in the analog current domain. Our design can be programmed with any QNN whose hyperparameters (the number of layers, filters, or filter size, etc) do not exceed the maximum provisioned. Once the flash devices are programmed with a trained model and our IC is given an input, our architecture performs inference with zero access to off-chip memory. We demonstrate the robustness of our design under current-mode non-linearities arising from process, voltage, and temperature (PVT) variations. We test validation accuracy on the ImageNet dataset, and show that our IC suffers only 0.71% and 0.92% reduction in classification accuracy for Top-1 and Top-5 outputs, respectively. Our implementation achieves between$2.1\times $and$125\times $better energy efficiency than previous NVM-based QNN accelerators. Our approach provides layer partitioning and neuron sharing options, which allow us to trade off latency, power, and area amongst each other.

Graph Convolutional Networks (GCNs) have successfully incorporated deep learning to graph structures for social network analysis, bio-informatics, etc. The execution pattern of GCNs is a hybrid of graph processing and neural networks which poses unique and significant challenges for hardware implementation. Graph processing involves a large amount of irregular memory access with little computation whereas processing of neural networks involves a large number of operations with regular memory access. Existing graph processing and neural network accelerators are therefore inefficient for computing GCNs. This paper presents Parag, processing in memory (PIM) architecture for GCN computation. It consists of customized logic with minuscule computing units called Neural Processing Elements (NPEs) interfaced to each bank of the DRAM to support parallel graph processing and neural network computation. It utilizes the massive internal parallelism of DRAM to accelerate the GCN execution with high energy efficiency. Simulation results for inference of GCN over standard datasets show a latency and energy reduction by three orders of magnitude over a CPU implementation. When compared to a state-of-the-art PIM architecture, PARAG achieves on an average 4x reduction in latency and 4.23x reduction in the energy-delay-product (EDP).

A new design methodology for reducing the area and power of standard cell ASICs that uses a combination of differential flipflops and a method of deliberate clock-skewing, called local clocking (LC), is described. LC introduces clock skew without the use of extra buffers in the clock network. This is done by having some flipflops, called sources, generate clock signals for other flipflops, called targets. The method involves two key features: 1) the design of a new differential flipflop, referred to as KVFF, that is functionally identical to a double-latch edge-triggered$D$flipflop, but in addition, produces a completion signal that is a skewed version of its input clock, which is used to clock other flipflops and 2) an efficient algorithm that identifies the sources and targets involved in the new clocking scheme, with the objective of reducing area and power. These are reduced because deliberate skew introduces extra slack on the logic cones that feed the target flipflops, which is exploited by synthesis tools to reduce area and power. Furthermore, the area and power overhead of conventional methods of introducing skew, e.g., buffers, is eliminated. LC is shown to result in significant improvements in area, power, and wirelength for several, publicly available, benchmark circuits for 65 nm bulk CMOS and 28 nm FDSOI technologies. For 65 nm, the average improvement in area, power and wirelength were 27.7%, 13.4%, and 21.0%, respectively. For 28 nm FDSOI the average improvement in area, power, and wirelength were 20.0%, 10.5%, and 30.5%, respectively. In addition, this article demonstrates how LC can be used to eliminate hold time violations.

This paper presents a mixed-signal architecture for implementing Quantized Neural Networks (QNNs) using flash transistors to achieve extremely high throughput with extremely low power, energy and memory requirements. Its low resource consumption makes our design especially suited for use in edge devices. The network weights are stored in-memory using flash transistors, and nodes perform operations in the analog current domain. Our design can be programmed with any QNN whose hyperparameters (the number of layers, filters, or filter size, etc) do not exceed the maximum provisioned. Once the flash devices are programmed with a trained model and the IC is given an input, our architecture performs inference with zero access to off-chip memory. We demonstrate the robustness of our design under current-mode non-linearities arising from process and voltage variations. We test validation accuracy on the ImageNet dataset, and show that our IC suffers only 0.6% and 1.0% reduction in classification accuracy for Top-1 and Top-5 outputs, respectively. Our implementation results in a$\sim \boldsymbol {50}\times$reduction in latency and energy when compared to a recently published mixed-signal ASIC implementation, with similar power characteristics. Our approach provides layer partitioning and node sharing possibilities, which allow us to trade off latency, power, and area amongst each other.

This paper presents a novel hardware-software co-design consisting of a Processing in-Memory (PiM) architecture with embedded neural processing elements (NPE) that are highly reconfigurable. The PiM platform and proposed approximation strategies are employed for various image filtering applications while providing the user with fine-grain dynamic control over energy efficiency, precision, and throughput (EPT). The proposed co-design can change the Peak Signal to Noise Ratio (PSNR, output quality metric for image filtering applications) from 25dB to 50dB (acceptable PSNR range for image filtering applications) without incurring any extra cost in terms of energy or latency. While switching from accurate to approximate mode of computation in the proposed co-design, the maximum improvement in energy efficiency and throughput is 2X. However, the gains in energy efficiency against a MAC-based PE array with the proposed memory platform are 3X-6X. The corresponding improvements in throughput are 2.26X-4.52X, respectively.

Machine Learning (ML) workloads are increasingly deployed at the edge. Enabling efficient inference execution while considering model and system heterogeneity remains challenging, especially for ML tasks built with a network of DNNs. The challenge is to maximize the utilization of all available resources on the multiprocessor system on a chip (MPSoC) at the same time. This becomes even more complicated because the optimal mapping for the network of DNNs can vary with input batch sizes and scene complexity. In this paper, a holistic hierarchical scheduling framework is presented to optimize the execution time for a network of DNN models on an edge MPSoC at runtime, considering varying input characteristics. The framework consists of a local and a global scheduler. The local scheduler maps individual DNNs in the inference pipeline to the best-performing hardware unit while the global scheduler customizes an Integer Linear Programming (ILP) solution to instantiate DNN remapping. To minimize scheduler runtime overhead, an imitation learning (IL) based scheduler is used that approximates the ILP solutions. The proposed scheduling framework (CAMDNN) was implemented on a Qualcomm Robotic RB5 platform. CAMDNN resulted in lower execution time of up to 32% than HEFT, and by factors of 6.67X, 5.6X and 2.17X than the CPU-only, GPU-only and Central Queue schedulers.

The flexibility of field-programmable gate arrays (FPGAs) is attributed to the reconfigurability of their basic logic elements (BLEs). Traditionally, the BLEs are comprised of one or more lookup tables (LUTs) of$n$inputs, that are designed to implement Boolean functions of$n$or fewer inputs. In an attempt to reduce the area and power consumption that comes from using LUTs, a number of complex LUT architectures have been reported. Although most of the proposed complex LUT architectures have resulted in reduced area and power, this has always been at cost of the decreased performance. This article proposes a new FPGA architecture, called threshold logic FPGA (TLFPGA), which results in significant improvement in performance, power, and area (PPA). TLFPGA is comprised of a combination of LUTs and a new type of BLE referred to as a threshold logic cell (TLC) (Muroga, 1987). Although TLCs implement a relatively small subset of Boolean functions known as threshold functions (Muroga, 1987), they require far fewer registers and multiplexers than an LUT, and are also significantly faster. This article describes the architecture of the TLFPGA and a technology mapping algorithm tailored for a TLFGA. On average, TLFPGA designs use 18% fewer registers and multiplexers, which improves the collective area of BLEs by approximately 16%, power by 14%, and performance by 5%. The improvements have been demonstrated in both 40 and 28 nm technologies for ISCAS-85 circuits as well as practical circuits, using industry-standard flows. The improvements were also demonstrated using a layout of the architecture.

In this paper, we describe a design of a mixed-signal circuit for an binary neuron (a.k.a perceptron, threshold logic gate) and a methodology for automatically embedding such cells in ASICs. The binary neuron, referred to as an FTL (flash threshold logic) uses floating gate or flash transistors whose threshold voltages serve as a proxy for the weights of the neuron. Algorithms for mapping the weights to the flash transistor threshold voltages are presented. The threshold voltages are determined to maximize both the robustness of the cell and its speed. The performance, power, and area of a single FTL cell are shown to be significantly smaller (79.4%), consume less power (61.6%), and operate faster (40.3%) compared to conventional CMOS logic equivalents. Also included are the architecture and the algorithms to program the flash devices of an FTL. The FTL cells are implemented as standard cells, and are designed to allow commercial synthesis and P&R tools to automatically use them in synthesis of ASICs. Substantial reductions in area and power without sacrificing performance are demonstrated on several ASIC benchmarks by the automatic embedding of FTL cells. The paper also demonstrates how FTL cells can be used for fixing timing errors after fabrication

This article presents a framework to enable the energy-efficient execution of convolutional neural networks (CNNs) on edge devices. The framework consists of a pair of edge devices connected via a wireless network: a performance and energy-constrained deviceDas the first recipient of data and an energy-unconstrained deviceNas an accelerator forD. DeviceDdecides on-the-fly how to distribute the workload with the objective of minimizing its energy consumption while accounting for the inherent uncertainty in network delay and the overheads involved in data transfer. These challenges are tackled by adopting the data-driven modeling framework of Markov Decision Processes, whereby an optimal policy is consulted byDinO(1) time to make layer-by-layer assignment decisions. As a special case, a linear-time dynamic programming algorithm is also presented for finding optimal layer assignment at once, under the assumption that the network delay is constant throughout the execution of the application. The proposed framework is demonstrated on a platform comprised of a Raspberry PI 3 asDand an NVIDIA Jetson TX2 asN. An average improvement of 31% and 23% in energy consumption is achieved compared to the alternatives of executing the CNNs entirely onDandN. Two state-of-the-art methods were also implemented and compared with the proposed methods.

Numerous applications such as graph processing, cryptography, databases, bioinformatics, etc., involve the repeated evaluation of Boolean functions on large bit vectors. In-memory architectures which perform processing in memory (PIM) are tailored for such applications. This paper describes a different architecture for in-memory computation called CIDAN, that achieves a 3X improvement in performance and a 2X improvement in energy for a representative set of algorithms over the state-of-the-art in-memory architectures. CIDAN uses a new basic processing element called a TLPE, which comprises a threshold logic gate (TLG) (a.k.a artificial neuron or perceptron). The implementation of a TLG within a TLPE is equivalent to a multi-input, edge-triggered flipflop that computes a subset of threshold functions of its inputs. The specific threshold function is selected on each cycle by enabling/disabling a subset of the weights associated with the threshold function, by using logic signals. In addition to the TLG, a TLPE realizes some non-threshold functions by a sequence of TLG evaluations. An equivalent CMOS implementation of a TLPE requires a substantially higher area and power. CIDAN has an array of TLPE(s) that is integrated with a DRAM, to allow fast evaluation of any one of its set of functions on large bit vectors. Results of running several common in-memory applications in graph processing and cryptography are presented.

This paper describes a novel framework for executing a network of trained deep neural network (DNN) models on commercial-off-the-shelf devices that are deployed in an IoT environment. The scenario consists of two devices connected by a wireless network: a user-end device (U), which is a low-end, energy and performance-limited processor, and a cloudlet (C), which is a substantially higher performance and energy-unconstrained processor. The goal is to distribute the computation of the DNN models between U and C to minimize the energy consumption of U while taking into account the variability in the wireless channel delay and the performance overhead of executing models in parallel. The proposed framework was implemented using an NVIDIA Jetson Nano for U and a Dell workstation with Titan Xp GPU as C. Experiments demonstrate significant improvements both in terms of energy consumption of U and processing delay.

This paper presents Tulip, a new architecture for a binary neural network (BNN) that uses an optimal schedule for executing the operations of an arbitrary BNN. It was constructed with the goal of maximizing energy efficiency per classification. At the top-level, Tulip consists of a collection of unique processing elements (TULIP-PEs) that are organized in a SIMD fashion. Each Tulip- Peconsists of a small network of binary neurons, and a small amount of local memory per neuron. The unique aspect of the binary neuron is that it is implemented as a mixed-signal circuit that natively performs the inner-product and thresholding operation of an artificial binary neuron. Moreover, the binary neuron, which is implemented as a single CMOS standard cell, is reconfigurable, and with a change in a single parameter, can implement all standard operations involved in a BNN. We present novel algorithms for mapping arbitrary nodes of a BNN onto the TULIP-PEs. Tulip was implemented as an ASIC in TSMC 40nm-LP technology. To provide a fair comparison, a recently reported BNN that employs a conventional MAC-based arithmetic processor was also implemented in the same technology. The results show that Tulip is consistently 3X more energy-efficient than the conventional design, without any penalty in performance, area, or accuracy.

A broad range of applications are increasingly benefiting from the rapid and flourishing development of convolutional neural networks (CNNs). The FPGA-based CNN inference accelerator is gaining popularity due to its high-performance and low-power as well as FPGA's conventional advantage of reconfigurability and flexibility. Without a general compiler to automate the implementation, however, significant efforts and expertise are still required to customize the design for each CNN model. In this paper, we present an register-transfer level (RTL)-level CNN compiler that automatically generates customized FPGA hardware for the inference tasks of various CNNs, in order to enable high-level fast prototyping of CNNs from software to FPGA and still keep the benefits of low-level hardware optimization. First, a general-purpose library of RTL modules is developed to model different operations at each layer. The integration and dataflow of physical modules are predefined in the top-level system template and reconfigured during compilation for a given CNN algorithm. The runtime control of layer-by-layer sequential computation is managed by the proposed execution schedule so that even highly irregular and complex network topology, e.g., GoogLeNet and ResNet, can be compiled. The proposed methodology is demonstrated with various CNN algorithms, e.g., NiN, VGG, GoogLeNet, and ResNet, on two standalone Intel FPGAs, Arria 10, and Stratix 10, achieving end-to-end inference throughputs of 969 GOPS and 1604 GOPS, respectively, with batch size of one.

The recently reported successes of convolutional neural networks (CNNs) in many areas have generated wide interest in the development of field-programmable gate array (FPGA)-based accelerators. To achieve high performance and energy efficiency, an FPGA-based accelerator must fully utilize the limited computation resources and minimize the data communication and memory access, both of which are impacted and constrained by a variety of design parameters, e.g., the degree and dimension of parallelism, the size of on-chip buffers, the bandwidth of the external memory, and many more. The large design space of the accelerator makes it impractical to search for the optimal design in the implementation phase. To address this problem, a performance model is described to estimate the performance and resource utilization of an FPGA implementation. By this means, the performance bottleneck and design bound can be identified and the optimal design option can be explored early in the design phase. The proposed performance model is validated using a variety of CNN algorithms comparing the results with on-board test results on two different FPGAs.

The next significant step in the evolution and proliferation of artificial intelligence technology will be the integration of neural network (NN) models within embedded and mobile systems. This calls for the design of compact, energy efficient NN models in silicon. In this article, we present a scalable application-specific integrated circuit (ASIC) design of an energy-efficient Long Short-Term Memory (LSTM) accelerator, named ELSA, which is suitable for energy-constrained devices. It includes several architectural innovations to achieve small area and high energy efficiency. To reduce the area and power consumption of the overall design, the compute-intensive units of ELSA employ approximate multiplications and still achieve high performance and accuracy. The performance is further improved through efficient synchronization of the elastic pipeline stages to maximize the utilization. The article also includes a performance model of ELSA, as a function of the hidden nodes and timesteps, permitting its use for the evaluation of any LSTM application. ELSA was implemented in register transfer level (RTL) and was synthesized and placed and routed in 65nm technology. Its functionality is demonstrated for language modeling—a common application of LSTM. ELSA is compared against a baseline implementation of an LSTM accelerator with standard functional units and without any of the architectural innovations of ELSA. The article demonstrates that ELSA can achieve significant improvements in power, area, and energy-efficiency when compared to the baseline design and several ASIC implementations reported in the literature, making it suitable for use in embedded systems and real-time applications.

Long Short-Term Memory (LSTM) Recurrent Neural network (RNN) is known for its capability in modeling sequence learning tasks such as language modeling. However, due to the large number of model parameters and compute-intensive operations, existing FPGA implementations of LSTMs are not sufficiently energy-efficient as they require large area and exhibit high power consumption. This work describes a substantially different hardware implementation of an LSTM which includes several architectural innovations to achieve high throughput and energy-efficiency. The architectural innovations include (1) an improved design of an approximate multiplier (AM) and its integration with the compute-intensive units of the LSTM; (2) the design of control mechanisms to handle the variable-cycle (data dependent) multiply operations; (3) incorporation of hierarchical pipelining at multiple levels of the design to maximize the overlap of the variable cycle computations. In addition, this work applies a post-training, range-based, linear quantization to the parameters of the model to further improve the performance and energy-efficiency. A python framework is also developed that allows for analysis and fine tuning of the input parameters before mapping the design to hardware. This paper extensively explores the design trade-offs and demonstrates the advantages for one common application - language modeling. Implementation of the design on a Xilinx Zynq XC7Z030 FPGA shows maximum improvement as compared to three recent published works in throughput to be 27.86X, 7.69X and 11.06X and in energy-efficiency to be 45.26X, 14.76X and 16.97X, respectively.

Long Short-Term Memory (LSTM) Recurrent Neural network (RNN) is known for its capability in modeling temporal aspects of data and has been shown to produce promising results in sequence learning tasks such as language modeling. However, due to the large number of model parameters and compute-intensive operations, existing FPGA implementations of LSTM cells are not sufficiently energy-efficient as they require large area and exhibit high power consumption. This work describes a substantially different hardware implementation of an LSTM which includes several architectural innovations to achieve high throughput and energy-efficiency. This paper includes extensive exploration of the design trade-offs and demonstrates the advantages for one common application - language modeling. Implementation of the design on a Xilinx Zynq XC7Z030 FPGA for language modeling shows significant improvements in throughput and energy-efficiency as compared to the state-of-the-art designs. It is worth mentioning that the proposed LSTM hardware architecture is also applicable to other applications that use LSTM as part of the neural network model (e.g., CNN-RNN models) or in whole (e.g., RNN models).

For the flexibility of implementing any given Boolean function(s), the FPGA uses re-configurable building blocks called LUTs. The price for this reconfigurability is a large number of registers and multiplexers required to construct the FPGA. While researchers have been working on complex LUT structures to reduce the area and power for several years, most of these implementations come at the cost of performance penalty. This paper demonstrates simultaneous improvement in area, power, and performance in an FPGA by using special logic cells called Threshold Logic Cells (TLCs) (also known as binary perceptrons). The TLCs are capable of implementing a complex threshold function, which if implemented using conventional gates would require several levels of logic gates. The TLCs only require 7 SRAM cells and are significantly faster than the conventional LUTs. The implementation of the proposed FPGA architecture has been done using 28nm FDSOI standard cells and has been evaluated using ISCAS-85, ISCAS-89, and a few large industrial designs. Experiments demonstrate that the proposed architecture can be used to get an average reduction of 18.1% in configuration registers, 18.1% reduction in multiplexer count, 12.3% in Basic Logic Element (BLE) area, 16.3% in BLE power, 5.9% improvement in operating frequency, with a slight reduction in track count, routing area and routing power. The improvements are also demonstrated on the physically designed version of the architecture.

This paper describes a novel design of a threshold logic gate (a binary perceptron) and its implementation as a standard cell. This new cell structure, referred to as flash threshold logic (FTL), uses floating gate (flash) transistors to realize the weights associated with a threshold function. The threshold voltages of the flash transistors serve as proxy for the weights. An FTL cell can be equivalently viewed as a multi-input, edge-triggered flipflop which computes a threshold function on a clock edge. Consequently it can used in automatic synthesis of ASICs. The use of flash transistors in the FTL cell allows programming of the weights after fabrication, thereby preventing discovery of its function by a foundry or by reverse engineering. This paper focuses on the design and characteristics of the FTL cell. We present a novel method for programming the weights of an FTL cell for a specified threshold function using a modified perceptron learning algorithm. The algorithm is further extended to select weights to maximize the robustness of the design in the presence of process variations. The FTL circuit was designed in 40nm technology and simulations with layout-extracted parasitics included, demonstrate significant improvements in area (79.7%), power (61.1%), and performance (42.5%) when compared to the equivalent implementations of the same function in conventional static CMOS design. Weight selection targeting robustness is demonstrated using Monte Carlo simulations. The paper also shows how FTL cells can be used for fixing timing errors after fabrication.

The success of mobile devices and applications is directly linked to a user's satisfaction of the quality of service-a metric used to denote the user's perception of the quality of an application. The first and necessary building block to manage user satisfaction is to establish accurate performance and power models which are sensitive to the mobile device's controllable features such as scalable voltage and frequency. Traditionally, performance and power models have been developed with deterministic workloads in mind - assuming long term, stable operating conditions. However, this is insufficient for mobile workloads, which are subject to many sources of variability leading to unpredictable phases of computation. This work establishes the importance and value of modeling the many sources of variations in mobile workloads. A completely data-driven approach is presented that provides accurate estimates of a workload's statistical characteristics, without any assumptions regarding its underlying statistical distribution. The method is light-weight allowing for real-time model evaluation and update. To demonstrate the usefulness of the proposed approach, the design of a dynamic voltage and frequency scaling controller is presented and implemented on an existing mobile device. The proposed controller achieves an energy efficiency improvement of 19 percent over existing Android frequency governors.

This paper proposes an alternative FPGA tile structure that consists of three traditional LUTs combined with a new reconfigurable threshold logic cell (TLC). The TLC requires only 7 SRAM cells and can be configured to implement one of several threshold functions. The proposed architecture is implemented in a 28nm FDSOI process, and is evaluated on standard benchmark circuits and several large complex function blocks. The results demonstrate an average reduction of 8.9% in register count, 15.4% in multiplexer count, 7% average reduction in Basic Logic Element (BLE) area, and 8.2% average reduction in BLE power, with a maximum decrease in register count up to 64%, BLE multiplexer count up to 68%, BLE Area up to 51.6% and BLE power up to 61.6% without loss in performance. We also show a reduction of 21% in the area of a tile.

The rapid improvement in computation capability has made convolutional neural networks (CNNs) a great success in recent years on image classification tasks, which has also prospered the development of objection detection algorithms with significantly improved accuracy. However, during the deployment phase, many applications demand low latency processing of one image with strict power consumption requirement, which reduces the efficiency of GPU and other general-purpose platform, bringing opportunities for specific acceleration hardware, e.g. FPGA, by customizing the digital circuit specific for the inference algorithm. Therefore, this work proposes to customize the detection algorithm, e.g. SSD, to benefit its hardware implementation with low data precision at the cost of marginal accuracy degradation. The proposed FPGA-based deep learning inference accelerator is demonstrated on two Intel FPGAs for SSD algorithm achieving up to 2.18 TOPS throughput and up to 3.3× superior energy-efficiency compared to GPU.

This paper proposes DORA - a dynamic frequency controller that maximizes the energy efficiency of smartphones subject to user satisfaction demands in the presence of memory interference stemmed from background processes and coscheduled applications. The proposed algorithm predicts the optimal energy-efficient frequency setting at runtime using staticallytrained performance, dynamic power, and leakage power models. The parameters of the models represent web page characteristics and dynamically varying architecture and system conditions. The algorithm is designed, implemented and extensively evaluated on a Google Nexus 5 smartphone using a variety of mobile web browsing workloads. The results show high prediction accuracies for the performance and power models of 97.5% and 96%, respectively. Overall, DORA improves the smartphone's energy efficiency by an average of 16% compared to the default Android frequency governor, interactive, while maintaining the desired levels of user satisfaction (web page load time).

Systems powered by harvested energy must consume very low power and withstand frequent interruptions in power. Nonvolatile logic (NVL) addresses the latter by saving the system state in flipflops enhanced with spin-transfer torque magnetic tunnel junctions (STT-MTJs) as the nonvolatile storage devices. Manufacturing variations in the STT-MTJs and in CMOS transistors significantly reduce yield, leading to over-design and high-energy consumption. A detailed analysis of the design tradeoffs in the driver circuitry for performing backup and restore, and a novel method to design the energy optimal driver for a given yield is presented. Next, efficient designs of two nonvolatile flip-flop (NVFF) circuits are presented, in which the backup time is determined on a per-chip basis, resulting in minimizing the energy wastage and satisfying the yield constraint. To achieve a yield of 98%, the conventional approach would have to expend nearly 5× more energy than the minimum required, whereas the proposed tunable approach expends only 26% more energy than the minimum. Also included are the energy consumption of the proposed NVFF designs when used in two larger function blocks. Experimental results were based on a commercial 40-nm process design kit, and HSPICE simulations with foundry supplied statistical models and data.

A new method for reducing power and area of standard cell ASICs is described. The method is based on deliberately introducing clock skew without the use of extra buffers in the clock network. This is done by having some flipflops, called sources, generate clock signals for other flipflops, called targets. The method involves two key features: (1) the design of new differential flipflop, referred to as KVFF, that is functionally identical to a master-slave edge-triggered D flipflop, but in addition, produces an completion signal that is a skewed version of its input clock, which is used to clock other flipflops; and (2) an efficient algorithm that identifies the sources and targets involved in the new clocking scheme, with the objective of reducing area and power. These are reduced because deliberate skew introduces extra slack on the logic cones that feed the target flipflops, which is exploited by synthesis tools to reduce area and power. In addition, the overhead of conventional methods of introducing skew, e.g. buffers, is eliminated. Using commercial tools, significant improvements in power and area are shown on placed and routed netlists of several circuits.

Convolutional neural networks (CNNs) are rapidly evolving and being applied to a broad range of applications. Given a specific application, an increasing challenge is to search the appropriate CNN algorithm and efficiently map it to the target hardware. The FPGA-based accelerator has the advantage of reconfigurability and flexibility, and has achieved high-performance and low-power. Without a general compiler to automate the implementation, however, significant efforts and expertise are still required to customize the design for each CNN model. In this work, we present an RTL-level CNN compiler that automatically generates customized FPGA hardware for the inference tasks of various CNNs, in order to enable high-level fast prototyping of CNNs from software to FPGA and still keep the benefits of low-level hardware optimization. First, a general-purpose library of RTL modules is developed to model different operations at each layer. The implementation of each module is optimized at the RTL level. Given a CNN algorithm, its structure is abstracted to a directed acyclic graph (DAG) and then complied with RTL modules in the library. The integration and dataflow of physical modules are predefined in the top-level system template and reconfigured during compilation. The runtime control of layer-by-layer sequential computation is managed by the proposed execution schedule so that even highly irregular and complex network topology, e.g. ResNet, can be compiled. The proposed methodology is demonstrated with end-to-end FPGA implementations of various CNN algorithms (e.g. NiN, VGG-16, ResNet-50, and ResNet-152) on two standalone Intel FPGAs, Stratix V and Arria 10. The performance and overhead of the automated compilation are evaluated. The compiled FPGA accelerators exhibit superior performance compared to state-of-the-art automation-based works by >2× for various CNNs.

This work presents an efficient hardware accelerator design of deep residual learning algorithms, which have shown superior image recognition accuracy (>90% top-5 accuracy on ImageNet database). Two key objectives of the acceleration strategy are to (1) maximize resource utilization and minimize data movements, and (2) employ scalable and reusable computing primitives to optimize physical design under hardware constraints. Furthermore, we present techniques for efficient integration and communication of these primitives in deep residual convolutional neural networks (CNNs) that exhibit complex, non-uniform layer connections. The proposed hardware accelerator efficiently implements state-of-the-art ResNet-50/152 algorithms on Arria-10 FPGA, demonstrating 285.1/315.5 GOPS of throughput and 27.2/71.7 ms of latency, respectively.

Convolutional Neural Networks (CNNs) have gained popularity in many computer vision applications such as image classification, face detection, and video analysis, because of their ability to train and classify with high accuracy. Due to multiple convolution and fully-connected layers that are compute-/memory-intensive, it is difficult to perform real-time classification with low power consumption on today?s computing systems. FPGAs have been widely explored as hardware accelerators for CNNs because of their reconfigurability and energy efficiency, as well as fast turn-around-time, especially with high-level synthesis methodologies. Previous FPGA-based CNN accelerators, however, typically implemented generic accelerators agnostic to the CNN configuration, where the reconfigurable capabilities of FPGAs are not fully leveraged to maximize the overall system throughput. In this work, we present a systematic design space exploration methodology to maximize the throughput of an OpenCL-based FPGA accelerator for a given CNN model, considering the FPGA resource constraints such as on-chip memory, registers, computational resources and external memory bandwidth. The proposed methodology is demonstrated by optimizing two representative large-scale CNNs, AlexNet and VGG, on two Altera Stratix-V FPGA platforms, DE5-Net and P395-D8 boards, which have different hardware resources. We achieve a peak performance of 136.5 GOPS for convolution operation, and 117.8 GOPS for the entire VGG network that performs ImageNet classification on P395-D8 board.

Despite its popularity, deploying Convolutional Neural Networks (CNNs) on a portable system is still challenging due to large data volume, intensive computation and frequent memory access. Although previous FPGA acceleration schemes generated by high-level synthesis tools (i.e., HLS, OpenCL) have allowed for fast design optimization, hardware inefficiency still exists when allocating FPGA resources to maximize parallelism and throughput. A direct hardware-level design (i.e., RTL) can improve the efficiency and achieve greater acceleration. However, this requires an in-depth understanding of both the algorithm structure and the FPGA system architecture. In this work, we present a scalable solution that integrates the flexibility of high-level synthesis and the finer level optimization of an RTL implementation. The cornerstone is a compiler that analyzes the CNN structure and parameters, and automatically generates a set of modular and scalable computing primitives that can accelerate various deep learning algorithms. Integrating these modules together for end-to-end CNN implementations, this work quantitatively analyzes the complier's design strategy to optimize the throughput of a given CNN model with the FPGA resource constraints. The proposed methodology is demonstrated on Altera Stratix-V GXA7 FPGA for AlexNet and NIN CNN models, achieving 114.5 GOPS and 117.3 GOPS, respectively. This represents a 1.9× improvement in throughput when compared to the OpenCL-based design. The results illustrate the promise of the automatic compiler solution for modularized and scalable hardware acceleration of deep learning.

User satisfaction is pivotal to the success of a mobile application. A recent study has shown that 49% of users would abandon a web-based application if it failed to load within 10 seconds. At the same time, it is imperative to maximize energy efficiency to ensure maximum usage of the limited energy source available to smartphones while maintaining the necessary levels of user satisfaction. An important factor to consider, that has been previously neglected, is variability of execution times of an application, requiring them to be modeled as stochastic quantities. This changes the nature of the objective function and the constraints of the underlying optimization problem. In this paper, we present a new approach to optimal energy control of mobile applications running on modern smartphone devices, focusing on the need to ensure a specified level of user satisfaction. The proposed statistical models address both single and multi-stage applications and are used in the formulation of an optimization problem, the solution to which is a static, lightweight controller that optimizes energy efficiency of mobile applications, subject to constraints on the likelihood that the application execution time meets a given deadline. We demonstrate the proposed models and the corresponding optimization method on three common mobile applications running on a real Qualcomm Snapdragon 8074 mobile chipset. The results show that the proposed statistical estimates of application execution times are within 99.34% of the measured values. Additionally, on the actual Qualcomm Snapdragon 8074 mobile chipset, the proposed control scheme achieves a 29% power savings over commonly-used Linux governors while maintaining an average web page load time of 2 seconds with a likelihood of 90%.

Spike timing dependent plasticity (STDP) is an important neural process that enables biological neural networks to learn by strengthening or weakening synaptic connections between neurons. This work presents simulation results and post-silicon experimental data that demonstrate for the first time the possibility of tuning the on state resistance of a type of emerging resistive memory device known as conductive bridge random access memory (CBRAM) in accordance with the biological STDP rule for neuromorphic applications. STDP behavior is demonstrated for CBRAM devices integrated with CMOS spiking neuron circuitry through back end of line post-processing for different initial resistance values and spike durations.

Face detection is a critical function in many embedded applications, such as computer vision and security. Although face detection has been well studied, detecting a large number of faces with different scales and excessive variations (pose, expression, or illumination) usually involves computationally expensive classification algorithms. These algorithms may divide an image into sub-windows at different scales, evaluate a large set of features for each sub-window, and determine the presence and location of a face. Even with state-of-the-art CPUs, it is still challenging to perform real-time face detection with sufficiently high energy efficiency and accuracy. In this paper, we propose a suite of acceleration techniques to enable such a capability on the CPU-FPGA platform, based on a state-of-the-art face detection algorithm that employs a large number of simple classifiers. We first map the algorithm using the integrated OpenCL environment for FPGA. Matching the structure of the algorithm, a nested architecture is proposed to speed up both memory access and the computing iterations. This multi-layer architecture distributes parallel computing cores with the memory. The physical aspects of the nested architecture, such as the core size and the number of cores, are further optimized to achieve real-time face detection, under realistic hardware constraints.

In this paper, we describe a new approach to reduce dynamic power, leakage, and area of application-specified integrated circuits, without sacrificing performance. The approach is based on a design of threshold logic gates (TLGs) and their seamless integration with conventional standard-cell design flow. We first describe a new robust, standard-cell library of configurable circuits for implementing threshold functions. Abstractly, the threshold gate behaves as a multi-input, single-output, edge-triggered flip-flop, which computes a threshold function of the inputs on the clock edge. The library consists of a small number of cells, each of which can compute a set of complex threshold functions, which would otherwise require a multilevel network. The function realized by a given threshold gate is determined by how signals are mapped to its inputs. We present a method for the assignment of signals to the inputs of a threshold gate to realize a given threshold function. Next, we present an algorithm that replaces a subset of flip-flops and portions of their logic cones in a conventional logic netlist, with threshold gates from the library. The resulting circuits, with both conventional and TLGs (called hybrid circuits), are placed and routed using commercial tools. We demonstrate significant reductions (using postlayout simulations) in power, leakage, and area of the hybrid circuits when compared with the conventional logic circuits, when both are operated at the maximum possible frequency of the conventional design.

The cross-point array architecture with resistive synaptic devices has been proposed for on-chip implementation of weighted sum and weight update in the training process of learning algorithms. However, the non-ideal properties of the synaptic devices available today, such as the nonlinearity in weight update, limited ON/OFF range and device variations, can potentially hamper the learning accuracy. This paper focuses on the impact of these realistic properties on the learning accuracy and proposes the mitigation strategies. Unsupervised sparse coding is selected as a case study algorithm. With the calibration of the realistic synaptic behavior from the measured experimental data, our study shows that the recognition accuracy of MNIST handwriting digits degrades from ∜97 % to ∜65 %. To mitigate this accuracy loss, the proposed strategies include 1) the smart programming schemes for achieving linear weight update; 2) a dummy column to eliminate the off-state current; 3) the use of multiple cells for each weight element to alleviate the impact of device variations. With the improved synaptic behavior by these strategies, the accuracy increases back to ∜95 %, enabling the reliable integration of realistic synaptic devices in the neuromorphic systems.

Compressive sensing (CS) allows acquiring sparse signals at sub-Nyquist rate, offering an energy-efficient solution to data acquisition. This is especially important to reduce communication data for mobile medical applications. However, reconstructing the signal from CS is usually left off-line due to the complex computations. In this paper, we integrate two key technologies to enable on-line energy-efficient CS signal reconstruction. These are (1) the use of Bayesian CS Belief Propagation (CS-BP) as the algorithm basis and (2) the novel design of stochastic computing (SC) circuits to efficiently map CS-BP algorithm. The overall signal reconstruction system is implemented with digital SC circuits in 65nm CMOS and recovers compressively sensed electrocardiography (ECG) and electromyography (EMG) signals with 11X to 8X data compression factor. Compared to a conventional binary design, post-layout simulation results show that the proposed stochastic design performs reconstruction with 5X energy-delay product improvement and 2X area reduction.

This article explores the use of threshold logic for reducing the power, delay, and/or area of digital logic circuits. We first describe the architecture of a differential threshold logic gate (TLG) using conventional MOSFETs. A TLG of a given number of inputs can be configured to realize a set of threshold functions by simply connecting the appropriate signals to its inputs. One characteristic of the proposed architecture for a TLG is the increased sensitivity to process variations (device mismatch) and noise. Problems due to device mismatch can be mitigated by proper cell design and optimization. The increased sensitivity to noise makes it difficult to scale the supply voltage of a TLG. We show a simple solution which involves integrating RRAMs within the TLG circuit, to achieve robust, low voltage and energy efficient operation. The third circuit implementation referred to as a spintronic threshold logic (STL) cell uses an STT-MTJ device as a intrinsic threshold logic gate. An STL cell is an very compact structure that can realize a large number of threshold functions, many of which would require a multilevel network of conventional CMOS logic gates.

In this paper, we describe two single input threshold gate (TLG) designs, which are functionally equivalent to differential flipflops. We present a detailed comparison of TLGs with two well established D-flipflop designs. The comparisons are done in both 65nm and 28nm commercial processes. We compare total delay, which is defined as the sum of setup delay and clock to output delay. We also show a comparison of tolerance against noise and process variation between the different designs. The two proposed designs are found to be as robust as an existing D-flipflop from both commercial standard cell libraries. Meanwhile, they are 33% and 25% faster in 65nm post-layout and 25% and 22% faster in 28nm post-layout compared to a commercial D-flipflop. The energy delay product of two proposed designs is 46% and 25% smaller in the 28nm process post layout simulation. Single input threshold gates can also be extended to multi-input threshold gates. We compare the total delay, power and leakage of a three-input threshold gate as well as a seven-input threshold gate with those of the equivalent (Complementary Metal Oxide Semiconductor) CMOS counterpart, which shows 52% 48% improvement in 65nm and 35% speed improvement in the 28nm process.

One of the challenges that all accelerators face, is to execute loops that have if-then-else constructs. There are three ways to accelerate loops with an if-then-else construct on a Coarse-grained reconfigurable architecture (CGRA): full predication, partial predication, and dual-issue scheme. In comparison with the other schemes, dual-issue scheme may achieve the best performance, but it requires compiler support -- which does not exist. In this paper, we develop compiler techniques to map loops with conditionals on CGRA for the dual-issue scheme. Our experiments show: i) 40% of loops that can be accelerated on CGRA have conditionals, ii) The proposed dual-issue scheme enables our compiler to accelerate loops 40% faster than full predication scheme proposed in [12], and iii) Our compiler assisted dual issue scheme can exploit richer interconnects, if present.

Threshold-logic gates have long been known to result in more compact and faster circuits when compared to conventional AND/OR logic equivalents [1], However, threshold logic based design has not entered the mainstream design technology (neither custom ASIC nor FPGA) due to the lack of efficient and reliable gate implementations and the necessary infrastructure for automated synthesis and physical design. This paper is a step toward addressing this gap. We present the architecture of a novel programmable logic array, referred to as Field Programmable Threshold-Logic Array (FPTLA), in which the basic cells are differential mode threshold-logic gates (DTGs). Each individual DTG cell is a clock edge-triggered circuit that computes a threshold-logic function. A DTG can be programmed to implement different threshold logic functions by routing appropriate signals to their inputs. This reduces the number of SRAMs inside the logic blocks by about 60% compared to conventional CLBs, without adding any significant overhead in the routing infrastructure. Since a DTG is essentially a multi-input, edge-triggered flipflop that computes a threshold function, a network of DTGs forms a nano-pipelined circuit. The advantages of such a network are demonstrated on a set of deeply pipelined datapath circuits implemented on FPTLAs and conventional FPGAs using the well established FPGA design framework VTR (Verilog To Routing) and VPR (Versatile Place and Route) [2]. The results indicate that an FPTLA can achieve up to 2X improvement in delay for nearly the same energy and logic area compared to the conventional LUT based FPGA. Although differential mode circuits can potentially be more sensitive to process variations, FPTLAs can be made robust to such variations without sacrificing their improved energy efficiency and performance over FPGAs.

Spiking neural P systems (in short, SN P systems) have been introduced as computing devices inspired by the structure and functioning of neural cells. The presence of unreliable components in SN P systems can be considered in many different aspects.

Energy efficiency has taken center stage in all aspects of computing, regardless of whether it is performed on a portable battery-powered device, a desktop PC, on servers in a data center, or on a supercomputer. It is expressed as performance-per-watt (PPW), which is equal to the number of instructions that are executed per Joule of energy. The shift to multicore processors, with tens or hundreds of cores on a single die requires that the operation of the cores be dynamically controlled to maximize the processor's overall energy efficiency. This paper presents a unified formulation and an efficient solution for this problem. The solution considers dynamic frequency and voltage scaling, thread migration, and active cooling as the means to control the cores. The solution method is efficient for a real-time implementation. The formulation includes accurate power and thermal models, temperature constraints, and accounts for the dependence of leakage power and circuit delay on temperature. The PPW metric is extended to PαPW (performanceα-per-watt), which allows examining the tradeoffs between optimizing for performance versus optimizing for energy by varying . Simulation experiments assuming a four-core processor demonstrate that the derived control strategy can achieve 3.2× greater energy efficiency (i.e., executes more than three times the number of instructions per Joule) over the performance-optimal solution. The formulation and the efficiency of the solution method also allows for fast design space exploration. Specifically, it is shown how simply increasing the number of cores in a processor can significantly diminish its energy efficiency, and that there is an optimal number of cores that maximize the PPW. This number depends on the ratio of how much the power of an individual core is reduced by scaling, i.e., as the number of cores are increased. Finally, the proposed method is implemented on a quad-core Intel Sandy Bridge processor, and verified by running benchmarks. The experiments suggest that the proposed method results in an improvement of 37 percent over the current state-of-the-art energy-efficient schemes.

Recent empirical studies have shown that multicore scaling is fast becoming power limited, and consequently, an increasing fraction of a multicore processor has to be under clocked or powered off. Therefore, in addition to fundamental innovations in architecture, compilers and parallelization of application programs, there is a need to develop practical and effective dynamic energy management (DEM) techniques for multicore processors. Existing DEM techniques mainly target reducing processor power consumption and temperature, and only few of them have addressed improving energy efficiency for multicore systems. With energy efficiency taking a center stage in all aspects of computing, the focus of the DEM needs to be on finding practical methods to maximize processor efficiency. Towards this, this article presents STEAM -- an optimal closed-loop DEM controller designed for multicore processors. The objective is to maximize energy efficiency by dynamic voltage and frequency scaling (DVFS). Energy efficiency is defined as the ratio of performance to power consumption or performance-per-watt (PPW). This is the same as the number of instructions executed per Joule. The PPW metric is actually replaced by P α PW (performance α -per-Watt), which allows for controlling the importance of performance versus power consumption by varying α. The proposed controller was implemented on a Linux system and tested with the Intel Sandy Bridge processor. There are three power management schemes called governors , available with Intel platforms. They are referred to as (1) Powersave (lowest power consumption), (2) Performance (achieves highest performance), and (3) Ondemand . Our simple and lightweight controller when executing SPEC CPU2006, PARSEC, and MiBench benchmarks have achieved an average of 18% improvement in energy efficiency (MIPS/Watt) over these ACPI policies. Moreover, STEAM also demonstrated an excellent prediction of core temperatures and power consumption, and the ability to control the core temperatures within 3 ˆ C of the specified maximum. Finally, the overhead of the STEAM implementation (in terms of CPU resources) is less than 0.25%. The entire implementation is self-contained and can be installed on any processor with very little prior knowledge of the processor.

Energy harvesting is a promising solution for reducing network maintenance and the overhead of replacing chemical batteries in sensor networks. In this article, problems related to controlling an active wireless sensor network comprised of nodes powered by both rechargeable batteries and solar energy are investigated. The objective of this control is to maximize the network's Quality of Coverage (QoC), defined as the minimum number of targets that can be covered by the network over a 24-hour period. Assuming a time-varying solar profile, the underlying problem is to optimally control the sensing range of each sensor so as to maximize the QoC. The problem is further constrained by requiring all active sensors to report any sensed data to a centralized base station, making connectivity a key factor in sensor management. Implicit in the solution is the allocation of solar energy during the day to sensing tasks and recharging of the battery so that a minimum coverage is guaranteed at all times. The problem turns out to be a nonlinear optimal control problem of high complexity. By exploiting the particular structure of the problem, we present a novel method for determining near-optimal sensing radii and routing paths as a series of quasiconvex (unimodal) optimization problems. The runtime of the proposed solution is 60X less than the standard optimal control method based on dynamic programming, while the worst-case error is less than 8%. The proposed method is scalable to large networks consisting of hundreds of sensors and targets. Several insights in the design of energy-harvesting networks are provided.

Coarse-Grained Reconfigurable Architectures (CGRAs) are an extremely attractive platform when both performance and power efficiency are paramount. Although the power-efficiency of CGRAs can be very high, their performance critically hinges upon the capabilities of the compiler. This is because a CGRA compiler has to perform explicit pipelining, scheduling, placement, and routing of operations. Existing CGRA compilers struggle with two main problems: 1) effectively utilizing the local register files in the PEs, and 2) high compilation times. This paper significantly improves the state-of-the-art in CGRA compilers by first creating a precise and general formulation of the problem of loop mapping on CGRAs, considering the local registers, and from the insights gained from the problem formulation, distilling an efficient and constructive heuristic solution. We show that the mapping problem, once characterized, can be reduced to the problem of finding maximal weighted clique in the product graph of the time-extended CGRA and the data dependence graph of the kernel. The heuristic we've developed results in average of 1.89 X better performance than the state-of-the-art methods when applied to several kernels from multimedia and SPEC2006 benchmarks. A unique feature of our heuristic is that it learns from failed attempts and constructively changes the schedule to achieve better mappings at lower compilation times.

Coarse-Grained Reconfigurable Architectures (CGRAs) are an attractive platform that promise simultaneous high-performance and high power-efficiency. One of the primary challenges in using CGRAs is to develop efficient compilers that can automatically and efficiently map applications to the CGRA. To this end, this paper makes several contributions: i) Using Re-computation for Resource Limitations: For the first time in CGRA compilers, we propose the use of re-computation as a solution for resource limitation problem. This extends the solutions space, and enables better mappings, ii) General Problem Formulation: A precise and general formulation of the application mapping problem on a CGRA is presented, and its computational complexity is established. iii) Extracting an Efficient Heuristic: Using the insights from the problem formulation, we design an effective global heuristic called EPIMap. EPIMap transforms the input specification (a directed graph) to an Epimorphic equivalent graph that satisfies the necessary conditions for mapping on to a CGRA, reducing the search space. Experimental results on 14 important kernels extracted from well known benchmark programs show that using EPIMap can improve the performance of the kernels on CGRA by more than 2.8X on average, as compared to one of the best existing mapping algorithm, EMS. EPIMap was able to achieve the theoretical best performance for 9 out of 14 benchmarks, while EMS could not achieve the theoretical best performance for any of the benchmarks. EPIMap achieves better mappings at acceptable increase in the compilation time.

This paper describes the design of a standard cell library of differential mode threshold gates, referred to as a Threshold Logic Latch or TLL, and new threshold function identification and decomposition methods to map a conventional logic network consisting of logic gates and flipflops, into a hybrid network that consists of both TLLs and conventional logic gates. After logic synthesis and physical design (placement and routing) using a commercial 65nm LP (low power) library, and commercial design tools, the hybrid circuits are shown to have up to 35% less dynamic power, about 50% less leakage power and around 37% less area when compared to the corresponding conventional design operated at the same (peak) frequency.

Energy harvesting in a sensor network is essential in situations where it is either difficult or not cost effective to access the network's nodes to replace the batteries. In this paper, we investigate the problems involved in controlling an active wireless sensor network that is powered both by rechargeable batteries and solar energy. The objective of this control is to maximize the network's quality of coverage (QoC), defined as the minimum number of targets that must be covered over a 24-hour period. Assuming a time varying solar profile, the problem is to optimally control the sensing range of each sensor so as to maximize the QoC. Implicit in the solution is the dynamic allocation of solar energy during the day to sensing tasks and to recharging the battery so that minimum coverage is guaranteed even during the night, when only the batteries can supply energy to the sensors. The problem turns out to be a nonlinear optimal control problem of high complexity. Exploiting the specific structure of the problem, we present a method to solve it as a series of quasiconvex (unimodal) optimization problems. The runtime of the proposed solution is 60X less than a naive method that is based on dynamic programming, while its worst-case error is less than 8%. Unlike the dynamic programming method, the proposed method is scalable to large networks consisting of hundreds of sensors and targets. This paper also offers several insights in the design of energy-harvesting networks, which result in minimum network setup cost through the determination of the optimal configuration of the number of sensors and the sampling time.

This paper addresses the problem of determining the feasible speeds and voltages of multicore processors with hard real-time and temperature constraints. This is an important problem, which has applications in time-critical execution of programs like audio and video encoding on application-specific embedded processors. Two problems are solved. The first is the computation of the optimal time-varying voltages and speeds of each core in a heterogeneous multicore processor, that minimize the makespan-the latest completion time of all tasks, while satisfying timing and temperature constraints. The solution to the makespan minimization problem is then extended to the problem of determining the feasible speeds and voltages that satisfy task deadlines. The methods presented in this paper also provide a theoretical basis and analytical relations between speed, voltage, power and temperature, which provide greater insight into the early-phase design of processors and are also useful for online dynamic thermal management.

Advances in chip-multiprocessor processing capabilities have led to an increased power consumption and temperature hotspots. Reducing the on-die peak temperature is important from the power reduction and reliability considerations. However, the presence of task deadlines constrain the reduction of peak temperature and thus complicates the determination of optimal speeds for minimizing the peak temperature. We formulate the determination of optimal speeds for minimizing the peak temperature of execution with task deadlines as a quasiconvex optimization problem. This formulation includes accurate power and thermal models with the leakage power dependency on temperature. Experiments demonstrate that our approach is very flexible in adapting to various scenarios of workload and deadline specifications. We obtained an 8°C reduction in peak temperature for a sample execution of benchmarks.

This paper presents a new four moduli residue number system of the form {2k, 2n-1, 2n+1-1}, n d k d 2n, which is an enhancement of the popular four-moduli set {2n,2n-1,2n,2n+1-1} (for even n). Our k-mod4 moduli set achieves a higher dynamic range and a better balancing of the binary channels. Using the proposed k-mod4 moduli set helps in reducing the hardware complexity of arithmetic circuits compared with other four-moduli sets for the same performance. Additionally, we provide a reverse converter design, whose hardware complexity and performance are shown to be better than the existing reverse converters for the same dynamic range. Experimental results comparing RNS multiply and accumulate units implemented using the proposed four-moduli set with the state-of-the-art balanced four-moduli sets, show large improvements in area (46%) and power (43%) reduction for various dynamic ranges. This makes our k-mod4 moduli set ideal for digital filters implementation.

Coarse-Grained Reconfigurable Arrays or CGRAs are programmable fabrics that promise both high performance and high power efficiency. Traditionally, CGRAs were used to accelerate extremely-embedded systems, and were typically manually programmed. However, as CGRAs are conceived to be used as more general-purpose accelerators, there is a need to develop software tools and capabilities. Much work has been done on developing compiler techniques for CGRAs, making programming them easier, however, there is no support for multithreading. As an accelerator to a multithreaded processor, CGRAs now are restricted to accelerating only one kernel of one thread running on the processor at any point in time. Supporting multithreading is difficult, since the start times and end times of threads are dynamic in nature, while CGRAs are statically scheduled. In this paper, we propose a strategy to do multithreading on a CGRA. The chief capability that we develop is a scheme to quickly transform an existing application mapping using the entire CGRA to one using only a fraction of it. Our experimental results on kernels from multimedia applications demonstrate that multithreading support can improve the total throughput of a CGRA by over 30%, 75%, and 150% on 4×4, 6×6, and 8×8 CGRAs, respectively, compared to single-threaded methods.

This paper presents a new and efficient heuristic procedure for determining whether or not a given Boolean function is a threshold function, when the Boolean function is given in the form of a decision diagram. The decision diagram based method is significantly different from earlier methods that are based on solving linear inequalities in Boolean variables that derived from truth tables. This method's success depends on the ordering of the variables in the binary decision diagram (BDD). An alternative data structure, and one that is more compact than a BDD, called a max literal factor tree (MLFT) is introduced. An MLFT is a particular type of factoring tree and was found to be more efficient than a BDD for identifying threshold functions. The threshold identification procedure is applied to the MCNC benchmark circuits to synthesize threshold gate networks.

Extracting high performance from multi-core processors requires increased use of thermal management techniques. In contrast to offline thermal management techniques, online techniques are capable of sensing changes in the workload distribution and setting the processor controls accordingly. Hence, online solutions are more accurate and are able to extract higher performance than the offline techniques. This paper presents performance optimal online thermal management techniques for multicore processors. The techniques include dynamic voltage and frequency scaling and task-to-core allocation or task migration. The problem formulation includes accurate power and thermal models, as well as leakage dependence on temperature. This paper provides a theoretical basis for deriving the optimal policies and computationally efficient implementations. The effectiveness of our DVFS and task-to-core allocation techniques are demonstrated by numerical simulations. The proposed task-to-core allocation method showed a 20.2% improvement in performance over a power-based thread migration approach. The techniques have been incorporated in a thermal-aware architectural-level simulator called MAGMA that allows for design space exploration, offline, and online dynamic thermal management. The simulator is capable of handling simulations of hundreds of cores within reasonable time.

Energy reduction of functional units (FUs) is a very important concern for high-end superscalar processors, not only because FUs consume a significant portion of processor energy, but also because they are one of the most important hotspots in the processor. In addition, the high sensitivity of leakage on temperature and process variation result in very high variation in the FU power consumption in different processor dies. Such high process variation reduces the parametric yield of processors. Consequently, reducing the FU power consumption and its variation is an important problem. However, existing FU power reduction techniques assumes all the FUs are similar, and do not consider the sensitivity of leakage on temperature. Consequently, they are not very effective in reducing the variation of FU power consumption. The advent of extremely small, yet accurate leakage sensors allow us to develop leakage-aware microarchitectural techniques to reduce both the power consumption and its variation among processor dies. Our leakage-aware operation-to-FU binding mechanism (LAOFBM) and leakage-aware power gating (LA-PG) mechanisms reduce the mean and standard deviation of the total arithmetic logic unit (ALU) power consumption of the ALPHA 21364 by 34% and 59%, respectively. At the processor level, this translates to a 13% reduction in the total processor energy consumption, with a 24°C reduction in the maximum ALU temperature.

Negative-bias-temperature instability (NBTI) has become the primary limiting factor of circuit life time. In this paper, we develop a hierarchical framework for analyzing the impact of NBTI on the performance of logic circuits under various operation conditions, such as the supply voltage, temperature, and node switching activity. Given a circuit topology and input switching activity, we propose an efficient method to predict the degradation of circuit speed over a long period of time. The effectiveness of our method is comprehensively demonstrated with the International Symposium on Circuits and Systems (ISCAS) benchmarks and a 65-nm industrial design. Furthermore, we extract the following key design insights for reliable circuit design under NBTI effect, including: 1) During dynamic operation, NBTI-induced degradation is relatively insensitive to supply voltage, but strongly dependent on temperature; 2) There is an optimum supply voltage that leads to the minimum of circuit performance degradation; circuit degradation rate actually goes up if supply voltage is lower than the optimum value; 3) Circuit performance degradation due to NBTI is highly sensitive to input vectors. The difference in delay degradation is up to 5× for various static and dynamic operations. Finally, we examine the interaction between NBTI effect, and process and design uncertainty in realistic conditions.

It is known that temperature gradients and thermal hotspots affect the reliability of microprocessors. Temperature is also an important constraint when maximizing the performance of processors. Although DVFS and DFS can be used to extract higher performance from temperature and power constrained single core processors, the full potential of multi-core performance cannot be exploited without the use of thread migration or task-to-core allocation schemes. In this paper, we formulate the problem of throughput-optimal task allocation on thermally constrained multi-core processors, and present a novel solution that includes optimal speed throttling. We show that the algorithms are implementable in real time and can be implemented in operating system's dynamic scheduling policy. The method presented here can result in a significant improvement in throughput over existing methods (5X over a naive scheme).

Advances in chip-multiprocessor processing capabilities has led to an increased power consumption and temperature hotspots. Maintaining the on-chip temperature is important from the power reduction and reliability considerations. Achieving highest performance while maintaining the temperature constraint is a challenge. We develop analytical solutions for the optimal control of frequencies for each core in a chip-multiprocessor. The objective is to reduce the makespan or the latest task completion time of all tasks. We show that the optimal frequency policy is bang-bang when the temperature constraint is not active and is exponential when the temperature constraint is active. We show that there is a significant improvement in overall throughput with our proposed solution and yet all cores operate under the thermal maximum.

In this paper a precise formulation of the problem of minimizing the maximum completion time of tasks on a multi-core processor, subject to thermal constraints is presented. The power model used in this work, accounts for the leakage dependence on temperature, while the thermal model is based on the HotSpot model. The general problem is shown to be a non-linear optimization problem that includes cyclic constraints between temperature and power. The derived policy of dynamic frequency and voltage control results in a performance improvement of 19.6% over an optimal policy which performs speed-only control.

This paper describes a fast and accurate technique to predict the steady-state throughput and the corresponding power consumption of a homogeneous multicore processor for a given benchmark workload while accounting for speed reduction due to thermal constraints. The expressions contain several parameters of interest to a system designer, like the static and dynamic-power consumptions (for hottest block and for full chip), the vertical thermal resistance of the hottest block, the leakage sensitivity to temperature, the chip threshold temperature, the ambient temperature, etc. Their computational complexity is independent of the number of cores. These are incorporated in a system-level multicore power/thermal simulator that uses the PTScalar power model and the Hotspot thermal model. The analytical throughput and power predictions were within 1.7% of that predicted by the system-level simulator. However, the analytical technique takes less than 0.2 s for a given set of design parameters, making it well suited for early design-space exploration. In contrast, the numerical technique takes anywhere from a minute (for 4 cores) up to a few hours (for 25 cores).

Fuel cell (FC) is a viable alternative power source for portable applications; it has higher energy density than traditional Li-ion battery and thus can achieve longer lifetime for the same weight or volume. However, because of its limited power density, it can hardly track fast fluctuations in the load current of digital systems. A hybrid power source, which consists of a FC and a Li-ion battery, has the advantages of long lifetime and good load following capabilities. In this paper, we consider the problem of extending the lifetime of a fuel-cell-based hybrid source that is used to provide power to an embedded system which supports dynamic voltage scaling (DVS). We propose an energy-based optimization framework that considers the characteristics of both the energy consumer (the embedded system) and the energy provider (the hybrid power source). We use this framework to develop algorithms that determine the output power level of the FC and the scaling factor of the DVS processor during task scheduling. Simulations on task traces based on a real-application (Path Finder) and a randomized version demonstrate significant superiority of our algorithms with respect to a conventional DVS algorithm which only considers energy minimization of the embedded system.

Scaling is currently the most popular technique used to improve performance metrics of CMOS circuits. This cannot go on forever because the properties that are responsible for the functioning of MOSFETs no longer hold in nano dimensions. Recent research into nano devices has shown that nano devices can be an alternative to CMOS when scaling of CMOS becomes infeasible in the near future. This is motivating the need for stable and mature design automation techniques for threshold logic since it is the design abstraction used for most nano- devices. This paper presents a new decomposition theory that is based on the properties of threshold functions. The main contributions of this paper are: (1) A new method of algebraic factorization called the min-max factorization. (2) A decomposition theory that uses this new factorization to identify and characterize threshold functions. (3) A new threshold logic synthesis methodology that uses the decomposition theory. This synthesis methodology produces circuits that are better than the previous state of art (27% better gate count and comparable circuit depth).

Increasing variability in the manufacturing process and growing complexity of the integrated circuits has given rise to many design and verification challenges. Statistical analysis of circuits and current source based gate delay models have started to replace the conventional static timing analysis which uses lookup tables for gate delays. In this paper we develop a statistical current source based gate model. We use accurate analytical models for representing the parameters of the gate model as functions of process parameters. Using the proposed statistical gate model, the gate output signal is generated and modeled as process dependent variational waveform. We present a compact model for representation of the variational signal waveform. The proposed waveform model can accurately generate the signal waveform at any process corner for accurate timing analysis. We generated the prosed model for gates of a 90 nm industry library and validated with SPICE simulations. Our model for logic gates and variational waveforms showed very good correlation with SPICE. The maximum error across all validation experiments was close to 3%.

The inductance and coupling effects in interconnects and non-linear receiver loads has resulted in complex input signals and output loads for gates in the modern deep sub- micron CMOS technologies. As a result, the conventional method of timing characterization, which is based on lookup tables with input slew and output load capacitance as indices, is no longer adequate. The focus has now shifted to current source based standard cell models which are based on the fundamental property of transconductance of MOSFETs. In this paper1we propose a systematic methodology for obtaining a current based delay model for gates, which can accommodate both single (SIS) and multi-input (MIS) switching signals of arbitrary shape and complex non-linear output loads. We use an analytical model for the gate output current expressed as a function of the node voltages. This results in an average error less than 0.5% with maximum standard deviation of 2.5% in error when compared with SPICE for a large number of standard cells. When compared with SPICE, using the proposed models gives stage delay and output slew with an average error of less than 3% and 2% respectively for arbitrary inputs and output load combinations.

We address the problem of efficient online computation of the speeds of different cores of a multi-core processor to maximize the throughput (which is expressed as a weighted sum of the speeds), subject to an upper bound on the core temperatures. We first compute the solution for steady-state thermal conditions by solving a linear program. We then present two approaches to computing the transient speed curves for each core: (i) a local solution, which involves solving a linear program every time step (of about 10 ms), and (ii) a global solution, which computes the optimal speed curve over a large time window (of about 100 s) by solving a non-linear program. We showed that the local solution is insensitive to the weights assigned in the performance objective (hence the need for the global solution). This is because a reduction in the speed of a core can only reduce the temperature of the other cores over much larger time periods (of the order of several seconds). The local solution is then completely determined by the temperature constraint equations. We show that the constraint matrix exhibits a special property - it can be expressed as the sum of a diagonal matrix and a matrix with identical rows. This allows us to solve the multi-core thermal constraint equations analytically to determine the (temporally) local optimum speeds. Further, we showed that due to this property, the steady-state speed solution selects a set of threads to operate at maximum temperature, and turns off all unused cores. Hence, to ensure that all available threads are scheduled, we impose a ldquofairnessrdquo constraint. Finally, we show how the open-loop speed control methods proposed above could be used together with a feedback controller to achieve robustness to model uncertainty.

Migrating threads away from the hot cores in a multicore processor allows them to operate at up to higher speeds. While this technique has already attracted a lot of research effort, the majority of thread migration studies are simulation-based. Although they are valuable for micro-architectural level optimization, they require prohibitively long simulation times, and hence have limited value for early design space exploration. We derive closed form expressions for the steady-state throughput of a multicore processor that employs thread migration and throttling for thermal management. These expressions can be evaluated under a millisecond (vs days for cycle-accurate simulation), and allow designers greater flexibility in evaluating the trade-offs involved in implementing thread migration on-chip. We also developed a system-level power/thermal simulator that we used to validate the analytical results.

This paper presents a novel gate-sizing methodology to minimize the leakage power in the presence of process variations. The method is based on modeling the statistics of leakage and delay as posynomials functions to formulate a geometric-programming problem. The existing statistical leakage model is extended to include the variations in gate sizes, as well as systematic variations. Using a simplified delay model, we propose an efficient method to evaluate the alpha-percentile of path delays without enumerating the paths in a circuit. The complexity of evaluating the objective function of the optimization problem is O(|N|2) and that of evaluating the delay constraints is O(|N| + |E|) for a circuit with |N| gates and |E| wires. The optimization problem is then solved using a convex optimization algorithm that gives an exact solution. The statistical optimization methodology is shown to provide as much as 15% reduction in the mean leakage power as compared to traditional worst case gate sizing with the same delay constraints.

In this paper, we present a unified approach for the statistical timing and leakage analysis of circuits in the presence of intradie variations. The intradie variations in device parameters are modeled as a spatial stochastic process with a given covariance function. The covariance function is used to construct a Karhunen-Loeve expansion of the spatial process. This leads to representing the various parameters of all components on the chip in terms of a common set of abstract random variables. The leakage and propagation delay of each gate are represented as quadratic polynomials (QPs), which are elements of a vector space whose bases are multivariate quadratic orthogonal polynomials of the device parameters. In the case of signal arrival times, we describe an efficient method to propagate the QPs through the circuit to obtain a QP representation of the signal arrival times at the primary outputs. The analysis is extended to include sequential components so that flip-flop parameters and clock arrival times can be treated as random variables. This allows efficient estimation of the timing yield of the circuit. We show how a similar representation of QP can be used to model leakage of gates and develop an efficient method to compute a QP representation of the total chip leakage. The proposed techniques and quadratic models were exercised on ISCAS89 benchmark circuits and compared with Monte Carlo (MC) simulations. The results show that the techniques are very accurate and several orders of magnitude faster than MC simulation.

This article presents our work on the development of a fuel cell (FC) and battery hybrid (FC-Bh) system for use in portable microelectronic systems. We describe the design and control of the hybrid system, as well as a dynamic power management (DPM)-based energy management policy that extends its operational lifetime. The FC is of the proton exchange membrane (PEM) type, operates at room temperature, and has an energy density which is 4--6 times that of a Li-ion battery. The FC cannot respond to sudden changes in the load, and so a system powered solely by the FC is not economical. An FC-Bh power source, on the other hand, can provide the high energy density of the FC and the high power density of a battery. In this work we first describe the prototype FC-Bh system that we have built. Such a prototype helps to characterize the performance of a hybrid power source, and also helps explore new energy management strategies for embedded systems powered by hybrid sources. Next we describe a Matlab/Simulink-based FC-Bh system simulator which serves as an alternate experimental platform and that enables quick evaluation of system-level control policies. Finally, we present an optimization framework that explicitly considers the characteristics of the FC-Bh system and is aimed at minimizing the fuel consumption. This optimization framework is applied on top of a prediction-based DPM policy and is used to derive a new fuel-efficient DPM scheme. The proposed scheme demonstrates up to 32% system lifetime extension compared to a competing scheme when run on a real trace-based MPEG encoding example.

We derive analytically, the performance optimal throttling curve for a processor under thermal constraints for a given task sequence. We found that keeping the chip temperature constant requires an exponential speed curve. Earlier works that propose constant throttling only keep the package/case temperature constant, and are hence suboptimal. We develop high-level thermal and power models that are simple enough for analysis, yet account for important effects like the power-density variation across a chip (hotspots), leakage dependence on temperature (LDT), and differing thermal characteristics of the silicon die and the thermal solution. We use a piecewise-linear approximation for the exponential leakage dependence on temperature, and devise a method to remove the circular dependency between leakage power and temperature. To solve the multi-task speed control problem, we first solve analytically, the single task problem with a constraint on the final package temperature using optimal control theory. We then find the optimum final package temperature of each task by dynamic programming. We compared the total execution time of several randomly generated task sequences using the optimal control policy against a constant speed throttling policy, and found significantly smaller total execution times. We compared the thermal profiles predicted by the proposed high-level thermal model to that of the Hotspot thermal model, and found them to be in good agreement.

Negative-bias-temperature-instability (NBTI) has become the primary limiting factor of circuit lifetime. In this work, we develop a general framework for analyzing the impact of NBTI on the performance of a circuit, based on various circuit parameters such as the supply voltage, temperature, and node switching activity of the signals etc. We propose an efficient method to predict the degradation of circuit performance based on circuit topology and the switching activity of the signals over long periods of time. We demonstrate our results on ISCAS benchmarks and a 65nm industrial design. The framework is used to provide key design insights for designing reliable circuits. The key design insights that we obtain are: (1) degradation due to NBTI is most sensitive on the input patterns and the duty cycle; the difference in the delay degradation can be up to 5X for various static and dynamic conditions, (2) during dynamic operation, NBTI-induced degradation is relatively insensitive to supply voltage, but strongly dependent on temperature; (3) NBTI has marginal impact on the clock signal.

Threshold logic is gaining prominence as an alternative to Boolean logic. The main reason for this trend is the availability of devices that implement these circuits efficiently (current mode, differential mode circuits), as well as the promise they hold for the future nanoalldevices (RTDs, SETs, QCAs and other nano devices). This has generated renewed interest in the design automation community to design efficient CAD tools for threshold logic. Recently a lot of work has been done to synthesize threshold logic circuits. So far there has been no efficient method to verify the synthesized circuits. In this work we address the problem of combinational equivalence checking for threshold circuits. We propose a new algorithm, to obtain compact functional representation of threshold elements. We give the proof of correctness, and analyze its runtime complexity. We use this polynomial time algorithm to develop a new methodology to verify threshold circuits. We report the result of our experiments, comparing the proposed methodology to the naive approach. We get up to 189X improvement in the run time (23X on average), and could verify circuits that the naive approach could not.

We analyze the effect of thermal constraints on the performance and power of multi-core processors. We propose system-level power and thermal models, and derive expressions for (a) the maximum number of cores that can be activated, with and without throttling, (b) the speedup (multi-core over single core), and the total power consumption, both as functions of the number of active cores. These expressions involve parameters like power per core, thermal resistance of hottest die block and package, and leakage dependence on temperature. We also computed the above metrics (a) and (b) numerically by solving the detailed Hotspot circuit of an multicore processor driven by a block-level exponential temperaturedependent leakage model. When compared to these numerical results, we found that the above expressions for (a) were at most 8% underpredicted, while those for (b) were accurately predicted. The proposed analytical approach is the first of its kind to relate metrics of interest in multi-core processors to high-level design parameters. Compared to numerical approaches, it provides much faster computation time, and valuable insight for processor designers.

We propose a modular approach for minimizing the total energy consumed by a pair of generic communicating devices (producer--consumer scenario) by jointly controlling their speed profiles. Each device (like a CPU, or disk drive) is assumed to have a controllable variable called its speed (e.g., a CPU's clock frequency, a disk drive's spindle motor speed) that affects its power consumption and performance (e.g., throughput, data transfer rate). The device and task models we analyzed were inspired by applications like CD recording (hard drive to CD drive data transfer) and data processing (disk drive to CPU data transfer). The proposed solution can be used for any pair of devices with convex (for continuous speed sets) or W-convex (a discrete version of a convex function for discrete speed sets) power--speed relationships. For discrete speed sets, the method operates directly on the power--speed values and does not require an analytical relationship between power and speed. The key to solving the two-device optimization problem was the observation that it could be split into two single device parametric optimization problems, where the parameters correspond to the common task that both the devices must execute. The following divide-and-conquer approach is proposed: [divide] the optimal speed policy and energy consumption of each device is derived as an analytical function of its task parameters; [conquer] the optimal values of these parameters are found by minimizing the sum of the parameterized energy functions and plugged back into the parameterized speed profiles. The main advantage of this approach is that each device can be characterized independently and this allows system designers to mix and match manufacturer-supplied device energy curves to evaluate and optimize different application scenarios. We demonstrate our approach using three device characterization examples (for a CD drive, hard drive, and a CPU) and two application scenarios (CD recording, MD5 checksum computation).

This paper proposes a novel methodology for statistical leakage minimization of digital circuits. A function of mean and variance of the circuit leakage is minimized with constraint on a-percentile of the delay using physical delay models. Since the leakage is a strong function of the threshold voltage and gate length, considering them as design variables can provide significant amount of power savings. The leakage minimization problem is formulated as a multivariable convex optimization problem. We demonstrate that statistical optimization can lead to more than 37% savings in nominal leakage compared to worst-case techniques that perform only gate sizing.

This paper proposes the use of Karhunen-Loève Expansion (KLE) for accurate and efficient modeling of intra-die correlations in the semiconductor manufacturing process. We demonstrate that the KLE provides a significantly more accurate representation of the underlying stochastic process compared to the traditional approach of dividing the layout into grids and applying Principal Component Analysis (PCA). By comparing the results of leakage analysis using both KLE and the existing approaches, we show that using KLE can provide up to 4-5x reduction in the variability space (number of random variables) while maintaining the same accuracy. We also propose an efficient leakage minimization algorithm that maximizes the leakage yield while satisfying probabilistic constraints on the delay.

Most existing dynamic voltage scaling (DVS) schemes for multiple tasks assume an energy cost function (energy consumption versus execution time) that is independent of the task characteristics. In practice the actual energy cost functions vary significantly from task to task. Different tasks running on the same hardware platform can exhibit different memory and peripheral access patterns, cache miss rates, etc. These effects results in a distinct energy cost function for each task.We present a new formulation and solution to the problem of minimizing the total (dynamic and static) system energy while executing a set of tasks under DVS. First, we demonstrate and quantify the dependence of the energy cost function on task characteristics by direct measurements on a real hardware platform (the TI OMAP processor) using real application programs. Next, we present simple analytical solutions to the problem of determining energy-optimal voltage scale factors for each task, while allowing each task to be preempted and to have its own energy cost function. Based on these solutions, we present simple and efficient algorithms for implementing DVS with multiple tasks. We consider two cases: (1) all tasks have a single deadline, and (2) each task has its own deadline. Experiments on a real hardware platform using real applications demonstrate a 10% additional saving in total system energy compared to previous leakage-aware DVS schemes.

For statistical timing and power analysis that are very importantproblems in the sub-100nm technologies, stochastic analysis of power grids that characterizes the voltage fluctuations due to process variations is inevitable. In this paper, we propose an efficient algorithm for the variational analysis of large power grids in the presence of a significant number of Gaussian intra-die process variables that are correlated. We consider variations in the power grid's electrical parameters as spatial stochastic processes and express them as linear expansions in an orthonormal series of random variables using the Karhunen-Loéve(KLE) method. The voltage response is then represented as an orthonormal polynomial series and the coefficients are obtained optimally using the Galerkin method. We propose a novel method to separate the stochastic analysis for the random variables that effect only the inputs (e.g, drain currents) and for those that effect the system parameters as well (e.g., conductance, capacitance). We show that this parallelism can result in significant speed-ups in addition to the speed-ups inherent to Galerkin-based methods. Our analysis has been applied to several industrial power grids and the results show speed-ups of up to two orders of magnitude over Monte Carlo simulations for comparable accuracy.

Fuel cells are clean power sources that have much higher energy densities and lifetimes compared to batteries. However, fuel cells have limited load following capabilities and cannot be efficiently utilized if used in isolation. In this work, we consider a hybrid system where a fuel cell based hybrid power source is used to provide power to a DVFS processor. The hybrid power source consists of a room temperature fuel cell operating as the primary power source and a Li-ion battery (that has good load following capability) operating as the secondary source. Our goal is to develop polices to extend the lifetime of the fuel cell based hybrid system. First, we develop a charge based optimization framework which minimizes the charge loss of the hybrid system (and not the energy consumption of the DVFS processor). Next, we propose a new algorithm to minimize the charge loss by judiciously scaling the load current. We compare the performance of this algorithm with one that has been optimized for energy, and demonstrate its superiority. Finally, we evaluate the performance of the hybrid system under different system configurations and show how to determine the best combination of fuel cell size and battery capacity for a given embedded application.

In this paper we propose a framework for Statistical Static Timing Analysis (SSTA) considering intra-die process variations. Given a cell library, we propose an accurate method to characterize the gate and interconnect delay as well as slew as a function of underlying parameter variations. Using these accurate delay models, we propose a method to perform SSTA based on a quadratic delay and slew model. The method is based on efficient dimensionality reduction technique used for accurate computation of the max of two delay expansions. Our results indicate less than 4% error in the variance of the delay models compared to SPICE Monte Carlo and less than 1% error in the variance of the circuit delay compared to Monte Carlo simulations.

As semiconductor manufacturing technology scales to smaller device sizes, the power consumption of clocked digital ICs begins to increase. Dynamic voltage and frequency scaling (DVFS) is a well-known technique for conserving energy. Recently, it has also been used to control the CPU temperature as part of Dynamic Thermal Management (DTM) techniques. Most works in these areas assume that the optimum speed profile (for either minimizing energy or maximizing performance) is a constant profile. However, in the presence of thermal constraints, we show that the optimal profile is in general, a time-varying function. We formulate the problem of maximizing the average throughput of a processor over a given time period, subject to thermal and speed constraints, as a problem in the calculus of variations. The variational approach provides a powerful framework for precisely specifying and solving the speed control problem, and allows us to obtain an exact analytical solution. The solution methodology is very general, and works for any convex power model, and simple lumped RC thermal models. The resulting speed profiles were found to consist of up to three segments, of which one of them is a decreasing function of time, and the others are constant. We analyze the effect of different parameters like the initial temperature, thermal capacitance and the maximum rated speed on the nature and the cost of the optimum solution. We also propose a two-speed solution that approximates the optimal speed curve. This solution was found to achieve a performance close to that of the optimum, and is also easier to implement in real processors.

Fuel cells are a viable alternative power source for portable applications. They have higher energy density than traditional Li-ion batteries and can achieve longer lifetime for the same weight or volume. However, because of their limited power density, they can not track fluctuations in the load current fast. A hybrid power source, that consists of a fuel cell and a Li-ion battery, has the advantages of long lifetime and good load following capabilities. In this work, we consider the problem of extending the lifetime of a fuel-cell based hybrid source that is used to provide power to a DVFS processor. We propose a new algorithm that is built on top of an energy based optimization framework. The algorithm simultaneously adjusts the fuel flow rate (at the producer end), and judiciously scales the load current (at the consumer end) to minimize the energy loss of the hybrid system. Simulations on randomly generated task sets demonstrate the superiority of this algorithm with respect to an algorithm that does not allow adjustment of the fuel flow rate.

Static power consumption due to subthreshold, gate, and junction leakages has become a significant component of the total power consumption. For nanoscale circuits, leakage poses one of the most important challenges to the continuation of Moore's law. The leakage of a logic gate varies by an order of magnitude over its Boolean input space. Thus, one way to minimize leakage in a circuit during standby mode is to apply an input vector for which the leakage is at its minimum. Such a set of vectors is called the minimum leakage set (MLS). In this paper, an efficient algorithm for computing the exact MLS is presented. The approach is based on implicit enumeration using integer-valued decision diagrams. Since the search space for MLS is exponential in the number of primary inputs, the enumeration is done with respect to the minimum balanced cut of the digraph representation of the circuit. Next, the problem of the increased switching power, which results from driving all inputs to a given state when entering the standby mode, is addressed. For a given upper bound B on the leakage, the MLS algorithm is extended to identify the maximal input cube with the minimum switching cost from the set of minterms whose maximum leakage is lesB. The switching cost associated with an input is taken to be proportional to the load capacitance of that input. The algorithms have been successfully tested on the ISCAS85 and MCNC91 benchmark circuits

The dynamic voltage and frequency scaling technique in CPUs is an example of adjusting a device's control variable to trade off power consumption and performance. This idea of energy optimization through speed control has been subsequently applied to other components of electronic systems such as disk drives and wireless transceivers. In this paper, the energy-optimal speed profile (a function of time) of a generic device that has to execute a given task in a given time is obtained analytically. The proposed approach is applicable to devices with either discrete or continuous-speed sets. The main novelty of the approach is that for discrete-speed sets, the nature of the underlying continuous power-speed relationship does not need to be known. The discrete power-speed data points only need to satisfy a W-convex relation: a discrete analog of a convex function. Based on the observation that most devices have W-convex power-speed relations, it is shown that the optimal speed profile uses at most one speed (for continuous speeds) or two speeds (for discrete-speed sets). Furthermore, each device has an intrinsic speed (independent of the task) ucat which it consumes the least energy per unit work done. It is shown that this speed can be calculated directly from measured values of power-speed data points (for discrete-speed sets) or by an experimental line search procedure where each step involves measuring a power-speed data point (for continuous-speed sets). In either case, no curve fit or knowledge of analytical power models is required. The optimum speed profile was shown to be either ucor the minimum feasible speed(s) for the given task, with the choice depending on the energy overheads and task parameters

Variations in the interconnect geometry of nanoscale ICs translate to variations in their performance. The resulting diminished accuracy in the estimates of performance at the design stage can lead to a significant reduction in the parametric yield. Thus, determining an accurate statistical description (e.g., moments, distribution, etc.) of the interconnect's response is critical for designers. In the presence of significant variations, device or interconnect model parameters such as wire resistance, capacitance, etc., need to modeled as random variables or as spatial random processes. The corner-based analysis is not accurate, and simulations based on sampling require long computation times due to the large number of parameters or random variables. This study proposes an efficient method of computing the stochastic response of interconnects. The technique models the stochastic response in an infinite dimensional Hilbert space in terms of orthogonal polynomial expansions. A finite representation is obtained by projecting the infinite series representation onto a finite dimensional subspace. The advantage of the proposed method is that it provides a functional representation of the response of the system in terms of the random variables that represent the process variations. The proposed algorithm has been implemented in a procedure called orthogonal polynomial expansions for response analysis (OPERA). Results from OPERA simulations on a number of design test cases match well with those from the classical Monte Carlo simulation program with integrated circuits emphasis (SPICE) and from perturbation methods. Additionally, OPERA shows good computational efficiency: speedup of up to two orders of magnitude have been observed over Monte Carlo SPICE simulations.

In this paper, we address the problem of minimizing energy consumption in a CDMA-based wireless sensor network (WSN). A comprehensive energy consumption model is proposed, which accounts for both the transmit and circuit energies. Energy consumption is minimized by jointly optimizing the transmit power and transmission time for each active node in the network. The problem is formulated as a non-convex optimization. Numerical as well as closed-form approximate solutions are provided. For the numerical solution, we show that the formulation can be transformed into a convex geometric programming (GP), for which fast algorithms, such as interior point method, can be applied. For the closed-form solution, we prove that the joint power/time optimization can be decoupled into two sequential sub-problems: optimization of transmit power with transmission time serving as a parameter, and then optimization of the transmission time. We show that the first sub-problem is a linear program while the second one can be well approximated as a convex programming problem. Taking advantage of these analytical results, we further derive the per-bit energy efficiency. Our results are verified through numerical examples and simulations

This paper presents a novel gate sizing methodology to mini-mize the leakage power in the presence of process variations. The leakage and delay are modeled as posynomials functions to formulate a geometric programming problem. The exist-ing statistical leakage model of [18] is extended to include the variations in gate sizes as well as systematic variations. We propose techniques to efficiently evaluate constraints on the α-percentile of the path delays without enumerating the paths in the circuit. The complexity of evaluating the ob-jective function is O(|N |2) and that of evaluating the delay constraints is O(|N | + |E|) for a circuit with |N | gates and |E | wires. The optimization problem is then solved using a convex optimization algorithm that gives an exact solution.

We obtain analytically, the energy optimal speed profile of a generic multi-speed device with a discrete set of speeds, to execute a given task within a given time. Current implementations of energy efficient speed control policies (including DVFS) almost exclusively use the minimum feasible speed pair, which has been shown before to be suboptimal. Unlike previous works, ours does not require an explicit functional relationship between the device's power and speed (e.g. the CMOS power model), but only assumes that the power-speed relationship is a W-convex (a discrete equivalent of a convex) function. This assumption allowed us to show that the optimal speed profile uses at most two speeds, and that all the essential characteristics of the power-speed relationship can be encapsulated within a single speed, /spl omega//sub u/. The latter speed is intrinsic to the device (i.e. task independent) and can be readily computed from its power-speed values (without any curve fit). Further, /spl omega//sub u/ is also the speed at which the device consumes the least energy per unit work done. The problem formulation reduces to a linear program in the number of supported speeds, which in general, is difficult to solve analytically. However, the optimum solution has a very simple form - it is either /spl omega//sub u/, or the minimum feasible speed pair for the given task. We verified that a number of commercial DVFS processors, and other devices like disk drives satisfied our model of the W-convex power-speed relationship.

In this paper, we investigate the impact of interconnect and device process variations on voltage fluctuations in power grids. We consider random variations in the power grid's electrical parameters as spatial stochastic processes and propose a new and efficient method to compute the stochastic voltage response of the power grid. Our approach provides an explicit analytical representation of the stochastic voltage response using orthogonal polynomials in a Hilbert space. The approach has been implemented in a prototype software called OPERA (Orthogonal Polynomial Expansions for Response Analysis). Use of OPERA on industrial power grids demonstrated speed-ups of up to two orders of magnitude. The results also show a significant variation of about /spl plusmn/35% in the nominal voltage drops at various nodes of the power grids and demonstrate the need for variation-aware power grid analysis.

In this paper, we contribute to the binary and multiple-valued applications of resonant tunneling devices (RTDs). We propose a method of systematic design of physical parameters of RTD based logic. From the abstraction of their behavior, we model the design space as a handful of systems of linear inequalities generated for a given circuit topology and an arbitrary logic function. Any valid solution reflects the physical parameters assignment that implements the function given. We solve these systems using off-the-shelf optimization tool and verify the results using SystemC based RTD circuit model. Our simulations confirm that the numerical solutions are valid parameter assignments.

Traditional single-attribute optimization problems force a designer to choose either power or delay as the objective function and minimize it with constraints on other attributes. However this approach does not provide the designer with enough freedom to incorporate tradeoffs between various attributes such as leakage and delay. In this paper we present a utility theoretic approach for the joint optimization of leakage and delay. This provides a general framework for quantifying a designer's preferences for tradeoffs between leakage and delay. We show that energy-delay product (EDP) is an element of a larger class of such utility functions. The resulting multi-attribute optimization problem is modeled as a convex gate sizing problem that is solved using Geometric Programming. The resulting solution is a design point that is optimal with respect to the designer's preferences.

Batteries are non-ideal energy sources - minimizing the energy consumption of a battery-powered system is not equivalent to maximizing its battery life. We propose an alternative interpretation of a previously proposed battery model, which indicates that the deviation from ideal behavior is due to the buildup of "unavailable charge" during the discharge process. Previously, battery-aware task scheduling algorithms and power management policies have been developed, which try to reduce the unavailable charge at the end of a given workload. However, they do not account for the occurrence of rest periods (user enforced, naturally occurring, or due to finite load horizon), which are present in a variety of workloads. We first obtain an analytical bound on the recovery time of a battery as a function of the extent of recovery. Then, we shown that the effect of the rest periods is to reduce the improvement of battery-charge optimizing techniques over traditional energy-optimizing techniques. Under certain conditions, the policy that only minimizes energy consumption can actually achieve a longer battery lifetime than a battery-aware policy. A formal criterion based on the recovery time is proposed to choose between a candidate battery-aware policy and a candidate energy-aware policy. We also model the battery discharge process as a linear time invariant system and obtain the frequency response of a battery. This is then used to study the effect of task granularity on the improvement achieved by battery-aware task scheduling. It was observed that the response time of typical batteries are of the order of seconds to several minutes. This, along with the charge recovery effect, was seen to cause battery-aware task scheduling methods to become ineffective for both very fine-grained (less than 10 ms) and very coarse-grained (greater than 30 mm) task granularities.

We consider a wireless sensor network in which sensors are grouped into clusters, each with its own cluster head (CH). Each CH collects data from sensors in its cluster and relays them to a sink node directly or through other CHs. The coverage time of the network is defined as the time until one of the CHs runs out of battery, resulting in an incomplete coverage of the sensing region. We study the maximization of coverage time by balancing the power consumption of different CHs. Using a Rayleigh fading channel model for inter-cluster communications, we provide optimal power allocation strategies that guarantee (in a probabilistic sense) an upper bound on the end-to-end (inter-CH) path reliability. Our allocation strategies account for the interaction between routing and clustering by considering the impacts of intra- and inter-cluster traffic at each CH. Two mechanisms are proposed for achieving balanced power consumption: the routing-aware optimal cluster planning and the clustering-aware optimal random relay. For both mechanisms, the problem is formulated as a signomial optimization, which can be efficiently solved using generalized geometric programming. Numerical examples and simulations are used to validate our analysis and study the performance of the proposed schemes.

This paper presents a new method based on Bayesian networks (BNs) for computing the exact probability distribution of the delay of a circuit. The method is based on BNs, which allows an efficient means to factor the joint probability distributions over variables in a circuit graph. The space complexity of the method presented here is O(m/sup |C|/), where m is the number of distinct values taken by each delay variable and |C| is the number of variables in the largest clique. The maximum clique size present in a BN is shown to be much smaller than the circuit size. For large circuits, where it is not practically feasible to compute the exact distribution, methods to reduce the problem size and get a lower bound on the exact distribution are presented. Comparison of the results with Monte Carlo simulations shows that we can reduce the size of the circuit by as much as 89% while maintaining the maximum difference between the predicted and simulated 3/spl sigma/ values to be less than 3%.

Earlier techniques for low power speed control in disk drives running audio/video applications attempted to either match the drive's speed to the data rate requirement of the host application (just-in-time speed), or run it at the maximum drive speed, neither of which are energy-optimal in general. Starting from the theory of DC motors, we obtain a high-level power model of a disk drive. We then analytically obtain the speed profile (function of time) that minimizes the energy required to transfer a given amount of data from/to the drive, in a given amount of time. Based on a power model obtained by measurement from a commercial optical drive, it is estimated that the proposed speed control technique consumes 79\%, 70\% and 50\% less energy for VCD, SVCD and DVD video playback, respectively, when compared to existing just-in-time CLV techniques. This work also provides an analytical framework to understand earlier observations that buffering multimedia data and employing CAV mode in disk drives is more energy-efficient.

In this paper we develop an approach to model interconnect delay under process variability for timing analysis and physical design optimization. The technique allows for closed-form computation of interconnect delay probability density functions (PDFs) given variations in relevant process parameters such as linewidth, metal thickness, and dielectric thickness. We express the resistance and capacitance of a line as a linear function of random variables and then use these to compute circuit moments. Finally, these variability-aware moments are used in known closed-form delay metrics to compute interconnect delay PDFs. We compare the approach to SPICE based Monte Carlo simulations and report an error in mean and standard deviation of delay of 1% and 4% on average, respectively.

In a CMOS combinational logic circuit, the subthreshold leakage current in the standby state depends on the state of the inputs. In this paper we present a new approach to identify the minimum leakage set of input vectors (MLS). Applying a vector in the MLS is known as Input Vector Control (IVC), and has proven to be very useful in reducing gate oxide leakage and sub-threshold leakage in standby mode of operation. The approach presented here is based on Implicit Enumeration of integer-valued decision diagrams. Since the search space for minimum leakage vector increases exponentially with the number of primary inputs, the enumeration is done with respect to the minimum balanced cut of the digraph representation of the circuit. To reduce the switching power dissipated when the inputs are driven to a given state (during entry into and exit from the standby state), we extend the MLS algorithm to compute a bounded leakage set (BLS). Given a bound of standby leakage, we present an algorithm for computing minimal switching cost partial input vectors such that the leakage of the circuit is always less than the upper bound.

The ability to control the variations in IC fabrication process is rapidly diminishing as feature sizes continue towards the sub-100 nm regime. As a result, there is an increasing uncertainty in the performance of CMOS circuits. Accounting for the worst case values of all parameters will result in an unacceptably low timing yield. Design for Variability, which involves designing to achieve a given level of confidence in the performance of ICs, is fast becoming an indispensable part of IC design methodology. This paper 1 describes a method to identify certain paths in the circuit that are responsible for the spread of timing performance. The method is based on defining a disutility function of the gate and path delays, which includes both the means and variances of the delay random variables. Based on the moments of this disutility function, an algorithm is presented which selects a subset of paths (called undominated paths) as being most responsible for the variation in timing performance. Next, a statistical gate sizing algorithm is presented, which is aimed at minimizing the delay variability of the nodes in the selected paths subject to constraints on the critical path delay and the area penalty. Monte-Carlo simulations with ISCAS ’85 benchmark circuits show that our statistical optimization approach results in significant improvements in timing yield over traditional deterministic sizing methods.

A distributed sensor network (DSN) designed to cover a given region R, is said to be alive if there is at least one subset of sensors that can collectively cover (sense) the region R. When no such subset exists, the network is said to be dead. A key challenge in the design of a DSN is to maximize the operational life of the network. Since sensors are typically powered by batteries, this requires maximizing the battery lifetime. One way to achieve this is to determine the optimal schedule for transitioning sets of sensors between active and inactive states while satisfying user specified performance constraints. This requires identification of feasible subsets (covers) of sensors and a scheme for switching between such subsets. We present an algorithmic solution to compute all the sensor covers in an implicit manner by formulating the problem as unate covering problem (UCP). The representation of all possible sensor sets is extremely efficient and can accommodate very large number of sensor covers. The representation and formulation makes it possible to consider the residual battery charge when switching between covers. We develop algorithms for switching between sensor covers aimed at maximizing the lifetime of the network. The algorithms take into account the transmission/reception costs of sensors, a user specified quality constraint and also utilize a novel battery model that accounts for the rate-dependent capacity effect and charge recovery during idle periods. Our simulation results show that lifetime improvement can be achieved by exploiting the charge recovery process. The work presented here constitutes a framework for battery aware sensor management in which various types of constraints can be incorporated and a range of other communication protocols can be examined.

Many applications running on today's portable devices use multiple power-consuming devices simultaneously, often in the form of a dataflow chain which involves transfer of data between devices through buffers. Some of these devices have the ability to scale their performance and power simultaneously by tuning one of their parameters (generically called the device speed). We address the problem of minimizing the energy consumed by a two-device data flow chain by choosing the speed profiles of the two devices and the "cycle time" of the intermediate buffer. Determining the speed profiles (functions of time) to minimize the energy functional, in general, requires variational techniques. However, based on certain observations about device power-speed relations and application performance constraints, we were able to solve the problem analytically in two steps - device characterization and cycle time optimization. The effectiveness of the technique was demonstrated for two practical applications of dataflow chains - CD recording and VCD playback with up to 45% and 64% energy improvements, respectively.

Deformations in interconnect due to process variations can lead to significant performance degradation in deep sub-micron circuits. Timing analyzers attempt to capture the effects of variation on delay with simplified models. The timing verification of RC or RLC networks requires the substitution of such simplified models with spatial stochastic processes that capture the random nature of process variations. The present work proposes a new and viable method to compute the stochastic response of interconnects. The technique models the stochastic response in an infinite dimensional Hilbert space in terms of orthogonal polynomial expansions. A finite representation is obtained by using the Galerkin approach of minimizing the Hilbert space norm of the residual error. The key advance of the proposed method is that it provides a functional representation of the response of the system in terms of the random variables that represent the process variations. The proposed algorithm has been implemented in a procedure called OPERA, results from OPERA simulations on commercial design test cases match well with those from the classical Monte Carlo SPICE simulations and from perturbation methods. Additionally OPERA shows good computational efficiency: speedup factor of 60 has been observed over Monte Carlo SPICE simulations.

The growing impact of within-die process variation has created the need for statistical timing analysis, where gate delays are modeled as random variables. Statistical timing analysis has traditionally suffered from exponential run time complexity with circuit size, due to arrival time dependencies created by reconverging paths in the circuit. In this paper, we propose a new approach to statistical timing analysis that is based on statistical bounds of the circuit delay. Since these bounds have linear run time complexity with circuit size, they can be computed efficiently for large circuits. Since both a lower and upper bound on the true statistical delay is available, the quality of the bounds can be determined. If the computed bounds are not sufficiently close to each other, we propose a heuristic to iteratively improve the bounds using selective enumeration of the sample space with additional run time. We demonstrate that the proposed bounds have only a small error and that by carefully selecting an small set of nodes for enumeration, this error can be further improved.

We consider the problem of scheduling multiple identical batteries for discharge in portable electronic systems. Unlike previous work reporting some experimental data to suggest which scheduling schemes are better than others, we arrive at our general conclusions formally, based on the analysis of an accurate high-level model of battery behavior. Our analytical results show that: (1) the lifetime of a parallel discharge schedule is equal to that of an equivalent monolithic battery, (2) the lifetime of a parallel discharge schedule is no less than that of a sequential discharge schedule, and (3) the lifetime of a switched discharge schedule approaches that of an equivalent monolithic battery as the switching frequency increases. We also derive bounds on the lifetime of a single battery under a constant-rate load, and then extend them to multiple battery systems. Using a low-level battery simulator, we verify our analytical findings with numerical data. For the simulated cases, the parallel discharge schedule resulted in up to 72% higher lifetimes than the sequential discharge schedule but fell short of the lifetime upper bound by up to 29%.

Noise simulators and noise avoidance tools are playing an increasingly critical role in the design of deep submicron circuits. However, noise estimates produced by these simulators are often very pessimistic. For large, high-performance industrial ICs, which can contain hundreds of thousands of nets, the worst case estimates of the noise results in thousands of reported violations, without any information about the likelihood of the possible noise violation. In this paper, we present a probabilistic approach to prioritize the violating nets based on the likelihood of occurrence of the reported noise. We derive an upper bound on the probability that the total noise injected on a given victim net by a specific set of aggressors exceeds a threshold. This is equivalent to a lower bound on the expected number of clock cycles required to realize the noise violation for the first time, i.e., mean time-to-failure. If the probability of a failure in a victim is sufficiently small, it is possible that even during the operation of the part for a number of years, the probability of failure on the net is negligible and the net can be assigned a lower priority for the application of noise avoidance strategies. We demonstrate the utility of this approach through experiments carried out on an large industrial processor design using a state-of-the-art industrial noise analysis tool.

Portable embedded computing systems require energy autonomy. This is achieved by batteries serving as a dedicated energy source. The requirement of portability places severe restrictions on size and weight, which in turn limits the amount of energy that is continuously available to maintain system operability. For these reasons, efficient energy utilization has become one of the key challenges to the designer of battery-powered embedded computing systems.In this paper, we first present a novel analytical battery model, which can be used for the battery lifetime estimation. The high quality of the proposed model is demonstrated with measurements and simulations. Using this battery model, we introduce a new "battery-aware" cost function, which will be used for optimizing the lifetime of the battery. This cost function generalizes the traditional minimization metric, namely the energy consumption of the system. We formulate the problem of battery-aware task scheduling on a single processor with multiple voltages. Then, we prove several important mathematical properties of the cost function. Based on these properties, we propose several algorithms for task ordering and voltage assignment, including optimal idle period insertion to exercise charge recovery.This paper presents the first effort toward a formal treatment of battery-aware task scheduling and voltage scaling, based on an accurate analytical model of the battery behavior.

A battery-powered portable electronic system shuts down once the battery is discharged; therefore, it is important to take the battery behavior into account. A system designer needs an adequate high-level battery model to make battery-aware decisions targeting the maximization of the system's online lifetime. We propose such a model that allows a designer to analytically predict the battery time-to-failure for a given load. Our model also allows for a tradeoff between the accuracy and the amount of computation performed. The quality of the proposed model is evaluated using typical pocket computer applications and a detailed low-level simulation of a lithium-ion electrochemical cell. In addition, we verify the proposed model against actual measurements taken on a real lithium-ion battery.

Operation of battery-powered portable systems can no longer be sustained once a battery becomes discharged. Maximization of the battery lifetime is a difficult task due to nonlinearity of battery behavior that depends on the characteristics of the system load profile. We address the problem of task sequencing without and with voltage/clock scaling that shapes the profile so that the battery lifetime is maximized. We developed an accurate analytical battery model and validated it with measurements taken on a real lithium-ion battery used in a pocket computer. We use the model as a basis for a unique battery conscious cost function and utilize its properties to develop several novel algorithms, including insertion of recovery periods and voltage/clock scaling for delay slack distribution.

The corruption of signals due to capacitive and inductive coupling of interconnects has become a significant problem in the design of deep submicron circuits (DSM). Noise simulators, based on worstcase assumptions, are overly pessimistic. As a result, when they are used on industrial ICs with hundreds of thousands of nets, thousands of nets are reported as having potential noise violations. There is a need to prioritize the problem nets based on the likelihood of the noise and possibly even eliminate them from further consideration if the likelihood is negligable. In this paper, a probabilistic approach is described which allows for a quantitative means to prioritize nets based on the likelihood of the reported noise violation. We derive upper bounds on the probability that the total noise injected on a given victim net by a specific set of aggressors exceeds a threshold. This bound is then used to determine a lower bound on the expected number of clock cycles (ENC) before the first violation occurs on a given net. Nets can be prioritized based on the ENC. We demonstrate the utility of this approach through experiments carried out on a large industrial processor design using a state-ofthe -art industrial noise analysis tool. A significant and interesting # Work done while on sabbatical with Advanced Design Tools group at Motorola, Austin TX. Also suported by NSF Center for Low Power Electronics (CLPE) (NSF Grant No. EEC-9523338, State of Arizona and Industrial consortium).

Delay due to capacitive coupling of interconnects has become an important reliability issue in the design of nanometer circuits. In this paper we present a probabilistic approach towards analyzing the impact of capacitive coupling noise on signal delay. The variation in the delay is due to the variation in the relative arrival times of the aggressors and the victim. We derive expressions for the moments of the victim voltage in the presence of noise. From these we compute estimates of the earliest and latest possible arrival times of the victim. We compare the analytical results with Monte Carlo simulations using SPICE. Even though the analytical calculations are 200 times faster than the Monte Carlo simulations, the differences in the estimates of the mean and standard deviation of the arrival time is no more than 2.8%. In addition, the width of the timing intervals using the proposed approach is reduced by as much as 48% with a confidence level of 0.984. That is 98.4% of the Monte Carlo simulations result in an arrival time that falls within the derived interval which is 48% shorter.

Predicting the time of full discharge of a finite-capacity energy source, such as a battery, is important for the design of portable electronic systems and applications. In this paper we present a novel analytical model of a battery that not only can be used to predict battery lifetime, but also can serve as a cost function for optimization of the energy usage in battery-powered systems. The model is physically justified, and involves only two parameters, which are easily estimated. The paper includes the results of extensive experimental evaluation of the model with respect to numerical simulations of the electrochemical cell, as well as measurements taken on a real battery. The model was tested using constant, interrupted, periodic and non-periodic discharge profiles, which were derived from standard applications run on a pocket computer.

Addresses the problem of delay constrained minimization of standby power of CMOS digital circuits that are implemented with dual-V/sub t/ technology. The availability of two or more threshold voltages on the same chip provides a new opportunity for circuit designers to make tradeoffs between power and delay. Three efficient algorithms that operate on a gate level netlist are described. Each algorithm assigns one of two threshold voltages (high and low V/sub t/) to each transistor so that the standby power dissipation is minimized without violating a user specified delay constraint. Experimental results on the MCNC91 benchmark circuits show that up to one order of magnitude power reduction can be achieved without any increase in delay when compared to the configuration in which all devices are at the low V/sub t/.

This article presents methods to translate a behavioral-level analog description into a Field Programmable Analog Array (FPAA) implementation. The methods consist of several steps that are referred to as function decomposition, macrocell synthesis, placement and routing, and postplacement simulation. The focus of this article is on the first three steps. The function decomposition step deals with decomposing a high-order system function into a set of lower-order functions. We present an efficient procedure for searching for an optimal solution. This procedure is based on first formally demonstrating the equivalence of two previously used optimization criteria. The objective of the macrocell synthesis step is to generate a hardware realization. A modified signal flow graph is introduced to represent FPAA circuits and graph transformations are used to identify the realizations that comply with the FPAA hardware constraints. The modified signal flow graph also allows scaling of capacitor values due to the limited set of allowable values in an FPAA. For the placement and routing step, an efficient method to estimate the circuit performance degradation due to parasitic effects is given. Using performance degradation as the cost function, an algorithm for finding an optimal FPAA placement and routing configuration is given. The efficacy of the methods developed is demonstrated by direct measurements on a set of filters.

Once the battery becomes fully discharged, a battery-powered portable electronic system goes off-line. Therefore, it is important to take the battery behavior into account. A system designer needs an adequate high-level model in order to make battery-aware decisions that target maximization of the system's lifetime on-line. We propose such a model: it allows a designer to predict the battery time-to-failure for a given load and provides a cost metric for lifetime optimization algorithms. Our model also allows for a tradeoff between the accuracy and the amount of computation performed. The quality of the proposed model is evaluated using a detailed low-level simulation of a lithium-ion electrochemical cell.

Dynamically reconfigurable computing systems built on FPGAs offer a variety of benefits; however, the reconfiguration cost in terms of power dissipation and delay in such systems is the key negative factor limiting system performance. We describe a hardware organization that allows for simple dynamic placement and routing through introduction of a virtual standard cell topology over an FPGA. We focus on the channel routing issues under the assumption that the FPGA hardware is partially (selectively) reconfigurable. Even though the channel capacity is fixed, routes that cannot fit in the channel at once can share the reconfigurable channel over time. The cost of configuring a new routing pattern can be greatly reduced if portions of the last configured routing pattern are reused. We address the problem of minimization of the configuration cost through maximization of the reuse of an already existing configuration of the channel.

Nonlinearity of the energy source behavior in portable systems needs to be modeled in order for the system software to make energy-conscious decisions. We describe an analytical battery model for predicting the battery time-to-failure under variable discharge conditions. Our model can be used to estimate the impact of various system load profiles on the energy source lifetime. The quality of our model is evaluated based on the simulation of a lithium-ion battery.

The availability of the dual V/sub t/ CMOS process provides a practical way to achieve high performance and low leakage power dissipation for current deep submicron technology. Early work on leakage power optimization of digital circuits utilizing dual V/sub t/ devices show some promising results (Kao et al., 1997). However, due to the lack of real dual V/sub t/ process models and parameters, these works are based on simple power and delay analysis of dual V/sub t/ devices. For example, the impact of dual V/sub t/ on the short circuit power dissipation is ignored in all these works. We provide extensive HSPICE simulation results on CMOS gates and circuits from a commercial dual V/sub t/ CMOS process. The experimental results show that optimization of dual V/sub t/ circuits involves complex trade-offs between leakage power, short circuit power and performance. For example, it is observed that using lower V/sub t/ devices does not always result in a faster circuit. One of the main contributions of this paper is that it reveals some new challenges and opportunities offered by the dual V/sub t/ technology to both circuit designers and CAD software developers for circuit optimization.

We present an efficient technique to reduce the switching activity in a technology-mapped CMOS combinational circuit based on local logic transformations. The transformations consist of adding redundant connections or gates so as to reduce switching activity. We describe simple and efficient procedures, based on logic implication, for identifying the sources and targets of the redundant connections. Additionally, we give procedures that permit the designer to trade-off power and delay after the transformations. Results of experiments on both the MCNC benchmark circuits and the circuits of a PowerPC microprocessor chip are given. The results indicate that significant power reduction of a CMOS combinational circuit can be achieved with very low area overhead, delay penalty, and computational cost.

In this paper we present an efficient technique to reduce the power dissipation in a technology mapped CMOS sequential circuit based on logic and structural transformations. The power reduction is achieved by adding sequential redundancies from low switching activity gates to high switching activity gates (targets) such that the switching activities at the output of the targets are significantly reduced. We show that the power reducing transformations result in a circuit that is a valid replacement of the original. The notion of validity used here is that of a delay safe replacement. The potential transformations are found by direct logic implications applied to the circuit netlist. Therefore the complexity of the proposed transformation is polynomial in the size of the circuit, allowing the processing of large designs.

h ti paper we address tbeproblem of delay constrained~ation of Ieakagepower of CMOS digiti circuits for durd VT technology.A novel and efficient hefitic rdogrithm based on circuit graph enumeration is proposed.me experimentirestits on the MCNC91 benchmark circuits show that Up to an order of magnitude powerreduction can be achieved without any increase in delay.

Traditional power optimization and estimation techniques for digital CMOS circuits have focused on the dynamic power dissipation, caused by charging and discharging the load capacitances at the gate outputs. However, as the device size and threshold voltage continue to decrease, the short circuit power dissipation is no longer a negligible factor. We show that previously published models for the short circuit power can not provide the accuracies required for current technologies. To improve the accuracy, we propose a new semi-empirical short circuit power model. Comparison of the proposed model with HSPICE simulation results on CMOS inverters using the Rockwell 0.25 /spl mu/m CMOS process parameters show that proposed model is significantly more accurate for estimating the short circuit power than the models reported in the literature.

Logic and structural transformations to reduce power havebeen considered by a number of authors.However,all the results presented so far have been based on modelsof power and estimation methods that may not be a accuratereflection of 'real world' constraitns.The performancerequirements of industrial designs often significantly restrictthe applicability of the power reducing transformations.Inthis paper we present the results of investigations on the efficacyof a recently reported logic level power optimizing algorithmon some commercial circuits, using customer suppliedinput waveforms.Based on a accurate delay model,the power consumption of the circuits is estimated using thecommercial package called 'PowerMill".The experimental resultsshow that a maximum 21% average power and 27.7%peak power power reduction can be obtained with only 3% delayincrease.Based on the experiments, we propose a generalmethodology for the practical application of the transformationsfor power optimization of CMOS logic circuits.Finally,a comparison between the experiments using randominput waveforms and customer provided input waveforms ispresented.

We present an efficient technique to reduce the switching activity in a CMOS combinational logic network based on local logic transformations. These transformations consist of adding redundant connections or gates so as to reduce the switching activity. Simple and efficient procedures, based on logic implication, for identifying the sources and targets of the redundant connections are presented. Additionally, procedures that permit the designer to trade-off power and delay after the transformations are described. Results of experiments on the MCNC benchmark circuits are given. The results indicate that significant reduction of the switching activities of a CMOS combinational circuit can be achieved with a very low area overhead and low computational cost.

We present a new data structure called edge-valued binary-decision diagrams (EVBDD). An EVBDD is a directed acyclic graph, that provides a canonical and compact representation of functions that involve both Boolean and integer quantities. In general, EVBDDs provide a more versatile and powerful representation than ordinary binary decision diagrams. We first describe the structure and properties of EVBDDs, and present a general algorithm for performing a variety of binary operations. Next, we describe an important extension of EVBDDs, called Structural EVBDDs, and show how they can be used for hierarchical verification.

Fault coverage and test length estimation in circuits under random test is the subject of this paper. Testing by a sequence of random input patterns is viewed as sequential sampling of faults from a given fault universe. Based on this model, the probability mass function (pmf) of fault coverage and expressions for all its moments are derived. This provides a means for computing estimates of fault coverage as well as determining the accuracy of the estimates. Test length, viewed as waiting time on fault coverage, is analyzed next. We derive expressions for its pmf and its probability generating function (pgf). This allows computation of all the higher order moments. In particular, expressions for mean and variance of test length for any specified fault coverage are derived. This is a considerable enhancement of the state of the art in techniques for predicting test length as a function of fault coverage. It is shown that any moment of test length requires knowledge of all the moments of fault coverage, and hence, its pmf. For this reason, expressions for approximating its expected value and variance, for user specified error bounds, are also given. A methodology based on these results is outlined. Experiments carried out on several circuits demonstrate that this technique is capable of providing excellent predictions of test length. Furthermore it is shown, as with fault coverage prediction, that estimates of variances can be used to bound average test length quite effectively.>

Folding or topological compaction of array-based VLSI layouts is an important optimization step that is carried out after logic synthesis. In this paper, a new approach to two-dimensional multiple folding of array-based VLSI layouts is presented. From the specification of the problem a pair of intersection graphs is created. We show that any pair of interval graphs that contain the intersection graphs as spanning subgraphs corresponds to a set of feasible foldings. Next, a complete and exact characterization of the folding problem is presented. In particular, it is shown that the set of all feasible foldings associated with a given pair of interval graphs corresponds to the set of independent colorings of a pair of compatibility graphs. The compatibility graphs are derived from a pair of interval graphs that contain the intersection graphs as spanning subgraphs. Thus, minimizing the area of a layout is tantamount to finding a pair of compatibility graphs such that the product of their chromatic numbers is minimum. As important as minimizing the area of a layout is, the ability to rapidly generate compact layouts over a wide range of aspect ratios is often equally, if not more, important. The interval graph-based formulation of the folding problem permits a controlled and systematic generation of compact layouts with varying aspect ratios. Efficient and provably correct algorithms to generate compact layouts that have a given number of rows or a given number of columns within their minimum and maximum possible values are given. The basic theory and methods are extended to include I/O and other types of constraints. Finally, the results of experiments that were carried out on a large number of benchmark problems are given. These results are compared with those obtained by previously reported methods.>

Edge-Valued Binary-Decision Diagrams (EVBDD's) are directed acyclic graphs that can represent and manipulate integer functions as effectively as Ordered Binary-Decision Diagrams OBDD's) do for Boolean functions. They have been used in logic verification for showing the equivalence between Boolean functions and arithmetic functions. In this paper, we present EVBDD-based algorithms for solving integer linear programs, computing spectral coefficients of Boolean functions, and performing function decomposition. These algorithms have been implemented in C under the SIS environment and experimental results are provided.>

This paper presents a theory for (disjunctive and nondisjunctive) function decomposition using the BDD representation of Boolean functions.Incompletely specified as well as multi-output Boolean functions are addressed as part of the general theory.A novel algorithm (based on an EVBDD representation) for generating the set of all bound variables that make the function decomposable is also presented.We compared our BDD-based decomposition procedure with existing implementations of the Roth-Karp procedure and obtained significant speed-ups.1

Edge-valued binary-decision diagrams (EVBDDs) are directed acyclic graphs which can represent and manipulate integer functions as effectively as ordered binary-decision diagrams (OBDDs) do for Boolean functions. They have been used to perform logic verification and compute the decomposability of Boolean functions. In this paper, we present a new EVBDD application for solving integer linear programs (ILP), which is an NP-hard problem that appears in many applications. Our approach is to combine the benefits of the EVBDD data structure (in terms of subgraph sharing and caching of computational results) with the state-of-the-art ILP solving techniques. Our program, called FGILP (Function Graph ILP) has been implemented in C under the SIS environment. The preliminary results of FGILP are comparable to those of LINDO.

Analyzes the behavior of signal probabilities in logic circuits chosen from a statistically characterized population. The statistical parameters of the population are obtained from certain aggregate structural and logical characteristics of the circuit such as fanins, fanouts, and proportions of different types of gates. A circuit is first transformed into one consisting of only nand gates, inverters, and buffers. This transformation leads to a new classification of circuits, referred to as nor-type, or-type, nand-type and and-type, the particular type being determined by computing two parameters from the circuit specification. A functional relation between gate signal probabilities, primary input signal probabilities, and aggregate structural properties of a circuit is established. This allows the study of basic characteristics of signal probability and its limiting behavior when the number of levels increases. It is shown that the limiting behavior of signal probability depends on the fixed points of a function which is determined by the two parameters estimated from the circuit and the distribution of gate fanins. A recurrence relation also allows one to define a methodology for estimating the distribution of signal probabilities in different levels. The complexity of this technique is shown to be proportional to the number of levels in the circuit. Results of extensive experiments with ISCAS '85 benchmarks as well as other circuits are given.>

A multi-input Muller C-element has frequently been used for joining signal transitions or completion time detection in self-timed circuits. An n-input Muller C-element design which uses the multilevel logic design technique and has a symmetric format for any integer n >or=2 is presented. In comparison with series-parallel MOS structure implementations and C-element tree implementations, the present design has fewer restrictions in terms of n, less path delay, less delay variance from inputs to output, and less area consumption. Experimental validation based on an industrial standard cell library is presented.>