The portion of clock power in system is rapidly increasing with the continuous increasing of clock frequency and clock resources. Last two decades, a great research attention has been paid to minimizing the clock power. Recently, it is shown that the structure of resonant clock networks is very effective in saving power since it can store electric energy to the inserted inductors rather than dissipate. On the other side, it has been known that dynamic voltage-frequency scaling (DVFS) is one of the most effectively and widely used power reduction techniques. However, so far no works have addressed the design methodology problem of synthesizing resonant clock networks that are able to operate under the designs with DVFS capability even though the problem is potentially very important to maximize the synergy effect on saving power. In this context, this paper proposes a comprehensive solution to the problem. Precisely, we propose a two-phase synthesis algorithm: 1) formulating the problem of inductor allocation, placement, and adjustable-sizing to support DVFS into a weighted set cover problem with the objective of minimizing total area of inductors and 2) followed by performing the task of resizing of adjustable driving buffers to support the switch of driving strength according to the clock frequencies by DVFS. Through experiments with benchmark circuits, it is shown that for designs with DVFS using 1 and 3 GHz, our algorithm synthesizes resonant clock networks with 25.9% less power on the execution of the clock frequency, which is not supported by resonant clocking in the previous no-DVFS aware resonant clock synthesis algorithm.

The portion of clock power in system is rapidly increasing with the continuous increasing of clock frequency and clock resources. Last two decades, a great research attention has been paid to minimizing the clock power. Recently, it is shown that the structure of resonant clock networks is very effective in saving power since it can store electric energy to the inserted inductors rather than dissipate. On the other side, it has been known that dynamic voltage-frequency scaling (DVFS) is one of the most effectively and widely used power reduction techniques. However, so far no works have addressed the problem of synthesizing resonant clock networks that are able to operate under the designs with DVFS capability even though the problem is potentially very important to maximize the synergy effect on saving power. In this context, this work proposes a comprehensive solution to the problem. Precisely, we propose a two-phase synthesis algorithm: (1) formulating the problem of inductor allocation, placement, and adjustable-sizing to support DVFS into a weighted set cover problem with the objective of minimizing total area of inductors followed by (2) performing the task of resizing of adjustable driving buffers to support the switch of driving strength according to the clock frequencies by DVFS. Through experiments with benchmark circuits, it is shown that for designs with DVFS using 1GHz and 3GHz, our algorithm synthesizes resonant clock networks with 17% less power on the execution of the clock frequency, which is not supported by resonant clocking in the previous no-DVFS aware resonant clock synthesis algorithm.

CMOS scaling trends have led to an inflection point where thermal constraints (especially in mobile devices that employ only passive cooling) preclude sustained operation of all transistors on a chip --- a phenomenon called "dark silicon." Recent research proposed computational sprinting --- exceeding sustainable thermal limits for short intervals --- to improve responsiveness in light of the bursty computation demands of many media-rich interactive mobile applications. Computational sprinting improves responsiveness by activating reserve cores (parallel sprinting) and/or boosting frequency/voltage (frequency sprinting) to power levels that far exceed the system's sustainable cooling capabilities, relying on thermal capacitance to buffer heat.

Although transistor density continues to increase, voltage scaling has stalled and thus power density is increasing each technology generation. Particularly in mobile devices, which have limited cooling options, these trends lead to a utilization wall in which sustained chip performance is limited primarily by power rather than area. However, many mobile applications do not demand sustained performance; rather they comprise short bursts of computation in response to sporadic user activity. To improve responsiveness for such applications, this paper explores activating otherwise powered-down cores for sub-second bursts of intense parallel computation. The approach exploits the concept of computational sprinting, in which a chip temporarily exceeds its sustainable thermal power budget to provide instantaneous throughput, after which the chip must return to nominal operation to cool down. To demonstrate the feasibility of this approach, we analyze the thermal and electrical characteristics of a smart-phone-like system that nominally operates a single core (~1W peak), but can sprint with up to 16 cores for hundreds of milliseconds. We describe a thermal design that incorporates phase-change materials to provide thermal capacitance to enable such sprints. We analyze image recognition kernels to show that parallel sprinting has the potential to achieve the task response time of a 16W chip within the thermal constraints of a 1W mobile platform.

This paper presents a 14-tap 8-bit finite impulse response (FIR) test-chip that has been designed using a novel charge-recovery logic family, called Enhanced Boost Logic (EBL), to achieve high-speed and low-power operation. Compared to previous charge-recovery circuitry, EBL achieves increased gate overdrive, resulting in low latency overhead over static CMOS design. The EBL-based FIR has been designed with only 1.5 cycles of additional latency over its static CMOS counterpart, while consuming 21% less energy per cycle, based on post-layout simulations of the two designs. The test-chip has been fabricated in a 0.13 μ m CMOS process with a fully-integrated 3 nH inductor. Correct function has been validated in the 365-600 MHz range. At its resonant frequency of 466 MHz, the test-chip dissipates 39.1 mW with a 93.6 nW/MHz/Tap/InBit/CoeffBit figure of merit, recovering 45% of the energy supplied to it every cycle.

This paper presents a circuit optimization technique called skewspreading. Given an edge-triggered sequential circuit, skew spreadingderives the required clock arrival times for all registers so that theskews are distributed evenly in a preselected time window without changing the operating frequency of the circuit. Skew spreading is ideal for peak current reduction, since it distributes clock activities and the ensuing signal activities widely in time. We have developed a skew spreading algorithm and applied it to a suite of benchmark circuits. Simulation results demonstrate that the variance of the resulting skew from the uniform distribution can be reduced to 4% on the average. In comparison to other gate-level peak current reduction techniques, our scheme achieves an average improvement of 17% with a speedup of up to 13.9 times.

This paper presents an efficient modeling scheme and a partitioning heuristic for parallelizing VLSI post-placement timing optimization. Encoding the paths with timing violations into a task graph, our novel modeling scheme provides an efficient representation of the timing and spatial relations among timing optimization tasks. Our new partitioning algorithm then assigns the task graph into multiple sessions of parallel processes, so that interprocessor communication is completely eliminated during each session. This partitioning scheme is especially useful for parallelizing processes with heavily connected tasks and, therefore, high communication requirements. For circuits with 20-130 thousand cells, the partitioning heuristic achieves speedups in excess of 5/spl times/ without degrading solution quality by dynamically utilizing 1-8 processors.

This paper investigates the problem of repeater insertion for low power under a given timing budget. A novel repeater insertion algorithm is proposed to compute the optimal repeater number and width in the discrete solution space, as defined by a given repeater library. Using the proposed algorithm, two practical and highly important questions are addressed. Given a certain tolerance to the degradation of repeater power dissipation: 1) how coarse could the repeater size granularity be? 2) What range should repeater widths be in? The experimental results provide valuable insights into repeater library design. Specifically, the investigation reveals that coarse repeater size granularities can be used to reduce the library size by more than 87% with merely a 4% power degradation. Moreover, for two-pin interconnects with various wire lengths and timing targets, the range of optimal repeater sizes for low power is limited, indicating that a low-cost small-size repeater library, if well designed, is adequate to provide high-quality repeater insertion solutions. The proposed scheme can be used in early design stages to generate a compact repeater library that is passed on to other repeater insertion algorithms.

The paper presents a novel repeater insertion algorithm for interconnect power minimization. The novelty of our approach is in the judicious integration of an analytical solver and a dynamic programming based method. Specifically, the analytical solver chooses a concise repeater library and a small set of repeater location candidates such that the dynamic programming algorithm can be performed fast with little degradation of the solution quality. In comparison with previously reported repeater insertion schemes, within comparable runtimes, our approach achieves up to 37% higher power savings. Moreover, for the same design quality, our scheme attains a speedup of two orders of magnitude.

This paper describes Boost Logic, a logic family which relies on voltage scaling, gate overdrive, and energy recovery, to achieve high energy efficiency at GHz frequencies. The key feature of our design is an energy recovering "boost" stage that provides a high gate overdrive to an aggressively voltage-scaled logic at near-threshold supply voltage. We have evaluated Boost Logic through post-layout simulation of an 8-bit carry-save multiplier in a 0.13μm CMOS process with Vth=340mV. At 1.6GHz and 1.3V supply voltage, the Boost multiplier dissipates 8.11pJ per computation, yielding 68% energy savings over its pipelined, voltage-scaled static CMOS counterpart. Using low Vth devices, the Boost Logic multiplier has been verified to operate at 2GHz with a 1.25V voltage supply and 8.50pJ energy dissipation per cycle

In this paper a new partitioning algorithm for parallelization of post-placement VLSI procedures is presented. The partitioning technique divides problem tasks into multiple sessions of parallel processes, so that interprocessor communication is entirely removed during each session. Communication is performed only in the end of each session. The algorithm is especially useful for parallelizing processes whose tasks are heavily connected to each other and may result in high communication overhead in parallel processing. Post-placement optimization of electrical violations represents such a task and was implemented in our experiments to validate the partitioning and parallelization techniques. On industry ASIC designs ranging in size from 300K to 1M gates, our partitioning scheme speeds up the execution time of this optimization by up to 2.5x over serial processing by dynamically utilizing 1-6 processors.

Three decades ago, theoretical physicists suggested that the controlled recovery of charges could result in electronic circuitry whose power dissipation approaches thermodynamic limits, growing at a significantly slower pace than the fCV/sup 2/ rate for CMOS switching power. Early engineering research in this field, which became generally known as adiabatic computing, focused on the asymptotic energetics of computation, exploring VLSI designs that use reversible logic and adiabatic switching to preserve information and achieve nearly zero power dissipation as operating frequencies approach zero. Recent advances in CMOS VLSI design have taken us to real working chips that rely on controlled charge recovery to operate at substantially lower power dissipation levels than their conventional counterparts. Although their origins can be traced back to the early adiabatic circuits, these charge-recovering systems approach energy recycling from a more practical angle, shedding reversibility to achieve operating frequencies in the hundreds of MHz with relatively low overhead. Among other charge-recovery designs, researchers have demonstrated microcontrollers, standard-cell ASICs, SRAMs, LCD panel drivers, I/O drivers, and multiGHz clock networks. In this paper, we present an overview of the field and focus on two chip designs that highlight some of the promising charge recovering techniques in practice.

In this paper, we present a novel power estimation scheme for programmable systems consisting of predesigned datapath and memory components. The proposed hybrid methodology yields highly accurate estimates within short runtimes by combining high-level simulation with analytical macromodeling of circuit characteristics. The kernel of our methodology is a simulation-free power estimation scheme for memoryless datapaths comprising several IP blocks connected in fixed topologies. The outer shell of our hybrid scheme is a functional simulation, which is performed only on the interfaces between memoryless components and memory blocks. This simulation accurately captures the control signals that affect the flow of data and, consequently, the utilization and power dissipation of hardware. Experimental results validate the accuracy and efficiency of our methodology. We applied our static power estimation kernel to signal processing and data encryption datapaths. For designs of up to 576 IP blocks, the average error of our power estimates is 7.3% in comparison with switch-level simulation results. We implemented our hybrid scheme into a power estimation tool, called HYPE, and used it to explore various architectural alternatives in the design of a 256-state Viterbi decoder and a Rijndael encryptor. For designs with about 1 million transistors, our estimator terminates within seconds. Compared with commercial state-of-the-art gate-level power estimators, our proposed methodology is up to 1000 times faster with 5.4% deviation on average.

In this paper, we investigate the problem of repeater insertion for low power under a given timing budget. We propose a novel repeater insertion algorithm to compute the optimal repeater number and width in the discrete solution space, as defined by a given repeater library. Using our algorithm, we show that rounding the solution under the continuity assumption to the closest discrete solution candidate may result in suboptimal designs, or it may even fail to find an existing solution. Given a certain tolerance to the degradation of repeater power dissipation, we address two practical and highly important questions: (1) How coarse could the repeater size granularity be? (2) What range should the repeater size be in?Experimental results demonstrate the high effectiveness of the proposed scheme and provide valuable insights into repeater library design. Our approach achieves up to 23 power reduction in comparison to rounding-based approaches. With a 4 power degradation tolerance, repeater size granularity as coarse as 8 can be used, reducing the library size by more than 87. For interconnects with various wire lengths and timing targets, our investigation reveals that the range of optimal repeater sizes for low-power is limited, indicating that a low-cost small-size repeater library, if well designed, is adequate to provide high quality repeater insertion solutions.

Summary form only given. We describe an algorithm for partitioning 2-weighted geometric graphs, so that each of the two weights is evenly distributed among all partitions and cutsize is minimal. This algorithm is applicable to load balancing problems in parallel computing, including scientific computation or circuit optimization, in which computational load depends on multiple factors, and geometric proximity needs to be preserved. We first show that for two continuous weight distributions, there always exists an L-shape separator that divides the two weights exactly. Based on this fact, we then give a practical and efficient heuristic for 2/sup p/-way partitioning. Our heuristic relies on recursive bipartitioning and runs in O(nlgn+m2/sup p/) time, where n is the number of vertices and m is the number of rows in the graph. In experiments with geometric graphs obtained from placed benchmark VLSI circuits, our heuristic generates balanced partitions with imbalance no greater than 2%, very short runtimes, and good cutsizes. For example, given a geometric graph with n>100,000, our heuristic computes a 32-way partitioning with 0.46% maximum imbalance within 0.5 second.

This paper proposes a constant-load SRAM design for highly efficient recovery of bit-line energy with a resonant power-clock supply. For each bit-line pair, the proposed SRAM includes a dummy bit-line of sufficient capacitance to ensure that the memory array presents a constant capacitive load to the power-clock, regardless of data or operation. Using a single-phase power-clock waveform, read and write operations are performed with single-cycle latency. The efficiency of the proposed SRAM has been assessed through simulations of 128x256 arrays with 0.25µm process parameters and a 42/58 write/non-write access pattern. Assuming lossless power-clock generation, the proposed SRAM dissipates 37% less power than its conventional counterpart at 400MHz/2.5V. When the overhead of power-clock generation is included, the proposed SRAM dissipates at least 27% less power than conventional SRAM.

In this paper, we present a novel sequence generator based on a Markov chain (MC) model. Specifically, we formulate the problem of generating a sequence of vectors with given average input probability p, average transition density d, and spatial correlation s as a transition matrix computation problem, in which the matrix elements are subject to constraints derived from the specified statistics. We also give a practical heuristic that computes such a matrix and generates a sequence of l n-bit vectors in O(nl+n/sup 2/) time. Derived from a strongly mixing MC, our generator yields binary vector sequences with accurate statistics, high uniformity, and high randomness. Experimental results show that our sequence generator can cover more than 99% of the parameter space. Sequences of 2000 48-bit vectors are generated in less than 0.05 s, with average deviations of the signal statistics p,d, and s equal to 1.6%, 1.8%, and 2.8%, respectively. Our generator enables the detailed study of power macromodeling. Using our tool and the ISCAS'85 benchmark circuits, we have assessed the sensitivity of power dissipation to the three input statistics p,d, and s. Our investigation reveals that power is most sensitive to transition density, while only occasionally exhibiting high sensitivity to signal probability and spatial correlation. Our experiments also show that input signal imbalance can cause estimation errors as high as 100% in extreme cases, although errors are usually within 25%.

This paper presents a novel power estimation scheme for programmable systems consisting of predesigned datapath and memory components. The proposed hybrid methodology yields highly accurate estimates within short runtimes by combining high-level simulation with analytical macromodeling of circuit characteristics. To assess its effectiveness in practice, we implemented our hybrid scheme into a power estimation tool, called HYPE, and applied it to explore various architectural alternatives in the design of a 256-state Viterbi decoder and a Rijndael encryptor. For designs with about 1 million transistors, our estimator terminates within seconds. Compared with industrial gate-level power estimators, our approach is up to 1,000 times faster with 5.4% deviation on average.

We have recently designed, fabricated, and successfully tested an experimental chip that validates a novel method for reducing clock dissipation through energy recovery. Our approach includes a single-phase sinusoidal clock signal, an L-C resonant sinusoidal clock generator, and an energy recovering flip-flop. Our chip comprises a dual-mode ASIC with two independent clock systems, one conventional and one energy recovering, and was fabricated in a micron bulk CMOS process. The ASIC computes a pipelined discrete wavelet transform with self-test and contains over 3500 gates. We have verified correct functionality and obtained power measurements in both modes of operation for frequencies up to 225MHz. In the energy recovering mode, our power measurements account for all of the dissipation factors, including the operation of the integrated resonant clock generator, and show a net energy savings over the conventional mode of operation. For example, at 115MHz, measured dissipation is between 60% and 75% of the conventional mode, depending on primary input activity. To our knowledge, this is the first ever published account of a direct experimentally-measured comparison between a complete energy recovering ASIC chip and its conventional implementation correctly operating in silicon at frequencies exceeding 100MHz.

Dynamic random access memorys (DRAMs) are widely used in portable applications due to their high storage density. In standby mode, the main source of DRAM power dissipation is the refresh operation that periodically restores leaking charge in each memory cell to its correct level. Conventional DRAMs use a single refresh period determined by the cell with the largest leakage. This approach is simple but dissipative, because it forces unnecessary refreshes for the majority of the cells with small leakage. In this paper, we investigate a novel scheme that relies on small refresh blocks and multiple refresh periods to reduce DRAM dissipation by decreasing the number of cells refreshed too often. In contrast to conventional row-based refresh, small refresh blocks are used to increase worst case data retention times. Long periods are used to accommodate cells with small leakage. Retention times are further extended by adding a swap cell to each refresh block. We give a novel polynomial-time algorithm for computing an optimal set of refresh periods for block-based multiperiod refresh. Specifically, given an integer K and a distribution of data-retention times, in O(KN/sup 2/) steps our algorithm computes K refresh periods that minimize DRAM dissipation, where N is the number of refresh blocks in the memory. We describe and evaluate a scalable implementation of our refresh scheme whose overhead is asymptotically linear with memory size. In simulations with a 16-Mb DRAM, block-based multiperiod refresh reduces DRAM standby dissipation by a multiplicative factor of 4 with area overhead below 6%. Moreover, our proposed scheme is robust to semiconductor process variations, with power savings degrading no more than 7% over a 20-fold increase of leaky cells.

In this paper, we present the design and experimental evaluation of an 8-bit energy-recovery multiplier with built-in self-test logic and an internal single-phase sinusoidal power-clock generator. Both the multiplier and the built-in self-test have been designed in SCAL-D, a true single-phase adiabatic logic family. Fabricated in a 0.5-/spl mu/m standard n-well CMOS process, the chip has an active area of 0.47 mm/sup 2/. Correct chip operation has been verified for clock rates up to 140 MHz. Moreover, chip dissipation measurements correlate well with HSPICE simulation results. For a selection of biasing conditions that yield correct operation at 140 MHz, total measured average dissipation for the multiplier and the power-clock generator is 250 pJ per operation.

The design of high-throughput large-state Viterbi decoders relies on the use of multiple arithmetic units. The global communication channels among these parallel processors often consist of long interconnect wires, resulting in large area and high power consumption. In this paper, we propose a data transfer oriented design methodology to implement a low-power 256-state rate-1/3 Viterbi decoder. Our architectural level scheme uses operation partitioning, packing, and scheduling to analyze and optimize interconnect effects in early design stages. In comparison with other published Viterbi decoders, our approach reduces the global data transfers by up to 75% and decreases the amount of global buses by up to 48%, while enabling the use of deeply pipelined datapaths with no data forwarding. In the register-transfer level (RTL) implementation, we apply precomputation in conjunction with saturation arithmetic to further reduce power dissipation with provably no coding performance degradation. Designed using a 0.25 /spl mu/m standard cell library, our decoder achieves a throughput of 20 Mb/s in simulation and dissipates only 0.45 W.

The design of high-throughput large-state Viterbi decoders relies on the use of multiple arithmetic units. The global communication channels among these parallel processors often consist of long interconnect wires, resulting in large area and high power consumption. In this paper, we propose a data-transfer oriented design methodology to implement a low-power 256-state rate-1/3 IS95 Viterbi decoder. Our architectural level scheme uses operation partitioning, packing, and scheduling to analyze and optimize interconnect effects in early design stages. In comparison with other published Viterbi decoders, our approach reduces the global data transfers by up to 75% and decreases the amount of global buses by up to 48%, while enabling the use of deeply pipelined datapaths with no data forwarding. In the RTL implementation of the individual processors, we apply precomputation in conjunction with saturation arithmetic to further reduce power dissipation with provably no coding performance degradation. Designed using a 0.25 μ standard cell library, our decoder achieves a throughput of 20 Mbps in simulation and dissipates only 450 mW.

In this paper, we present a novel sequence generator based on a Markov chain model. Specifically, we formulate the problem of generating a sequence of vectors with given average input probability p, average transition density d, and spatial correlation s as a transition matrix computation problem, in which the matrix elements are subject to constraints derived from the specified statistics. We also give a practical heuristic that computes such a matrix and generates a sequence of l n-bit vectors in O(nl + n2) time. Derived from a strongly mixing Markov chain, our generator yields binary vector sequences with accurate statistics, high uniformity, and high randomness. Experimental results show that our sequence generator can cover more than 99% of the parameter space. Sequences of 2,000 48-bit vectors are generated in less than 0.05 seconds, with average deviations of the signal statistics p, d, and s equal to 1.6%, 1.8%, and 2.8%, respectively.Our generator enables the detailed study of power macromodeling. Using our tool and the ISCAS-85 benchmark circuits, we have assessed the sensitivity of power dissipation to the three input statistics p, d, and s. Our investigation reveals that power is most sensitive to transition density, while only occasionally exhibiting high sensitivity to signal probability and spatial correlation. Our experiments also show that input signal imbalance can cause estimation errors as high as 100% in extreme cases, although errors are usually within 25%.

This paper proposes an energy-recovering (a.k.a. adiabatic) static RAM with a novel driver that reduces power dissipation by efficiently recovering energy from the bit/word line capacitors. Powered by a single-phase sinusoidal power-clock, our SRAM delivers read and write operations with single-cycle latency. To that end, a precharge-low scheme is employed along with a modified sense amplifier design that achieves high efficiency at differential voltages near V/sub SS/. A simple control circuit is used to maintain driver operation in synchrony with the power-clock waveform. Feedback circuitry from the driver output to the control circuit ensures that out driver remains efficient, independent of the access pattern. Our energy recovering SRAM functions correctly while achieving substantial energy savings over a wide range of supply voltages and operating frequencies. Hspice simulations of a simple full-custom adiabatic 256/spl times/256 SRAM, that includes the energy recovering bit/word line drivers, the cell array, and the sense amplifiers, show over 2.6x energy savings at 3V, 300MHz in comparison with its conventional counterpart.

This paper investigates the application of simultaneous retiming and clock scheduling for optimizing synchronous circuits under setup and hold constraints. Two optimization problems are explored: (1) clock period minimization and (2) tolerance maximization to clock-signal delay variations. Exact mixed-integer linear programming formulations and efficient heuristics are given for both problems. When both long and short paths are considered, circuits optimized by the combined application of retiming and clock scheduling can achieve shorter clock periods or demonstrate greater tolerance to clock-signal delay variations than circuits optimized by retiming or clock scheduling. Experiments with benchmark circuits demonstrate the effectiveness of the combined optimization. In comparison with the best result obtained by either of the two optimizations, the joint application of retiming and clock scheduling increased operating speeds by more than 8% on the average. It also increased tolerance to clock delay variations by an average of 12% over a broad range of target clock frequencies. Larger relative improvements were achieved for shorter clock periods, thus suggesting that simultaneous retiming and clock scheduling can play an important role in high-speed design.

This paper presents the design and evaluation of an 8-bit adiabatic multiplier. Both the multiplier core and its built-in self-test logic have been designed using a true single-phase adiabatic logic family. Energy is supplied to the adiabatic circuitry via a sinusoidal power-clock waveform that is generated on-chip. In HSPICE simulations with post-layout extracted parasitics, our design functions correctly at clock frequencies exceeding 200 MHz. The total dissipation of the multiplier core and self-test circuitry approaches 130pJ per operation at 200MHz. Our 11,854-transistor chip has been fabricated in a 0.5&mgrm standard CMOS process with an active area of 0.470mm$^2$. Correct chip operation has been validated for operating frequencies up to 130MHz, the limit of our experimental setup. Measured dissipation correlates well with HSPICE simulations.

This paper proposes a novel system-level power estimation methodology for electronic designs consisting of intellectual property (IP) components. Our methodology relies on analytical output and power macromodels of the IP blocks to estimate system dissipation without performing any simulation. We derive upper bounds on the estimation error of our methodology and demonstrate the relation of this error to the sensitivities of the macromodeling functions. For circuits without feedback, we give a sufficient condition for the worst-case power estimation error to increase only linearly with the length of the IP cascades. We also give a tighter sufficient condition that ensures error boundedness in IP systems of any topology. Experiments with signal processing and data encryption systems validate the accuracy and efficiency of our approach. For designs of up to 576 IP blocks, power estimates are obtained within 0.2 seconds. In comparison with switch-level simulation results, the average error of our power estimates is 7.3%.

Recently discovered high-speed single-phase adiabatic logic families require efficient sinusoidal power-clock generators. In this paper we propose a low-power resonant clock-generator built around a zero-voltage switching push-pull power conversion topology. We describe a novel energy-efficient control circuit for this power converter, based on an asynchronous CMOS state machine. We also describe an integrated sub-micron CMOS implementation of our power converter and control circuits. Simulation results show efficiencies in excess of 90%, even under suboptimal tuning conditions, for frequencies over 200MHz. We have fabricated our clock generator in a 0.5�m standard CMOS process. Using an external surface-mount inductor as the resonant element, we have verified the correct operation of the clock generator when driving a singlephase adiabatic 8-bit multiplier.

Symbolic debuggers are system-development tools that can accelerate the validation speed of behavioral specifications by allowing a user to interact with an executing code at the source level. In response to a user query, the debugger must retrieve and display the value of a source variable in a manner consistent with user expectations with respect to the source statement where execution has halted. However, when a behavioral specification has been optimized using transformations, values of variables may either be inaccessible in the runtime state or inconsistent with user expectations. We address the problem that pertains to the retrieval of source values for the globally optimized behavioral specifications. We present a new approach for symbolic debugging. The implementation of the new debugging approach poses several optimization tasks. We formulate the optimization tasks and develop heuristics to solve them. We demonstrate the effectiveness of the proposed approach on a set of designs.

Dynamic logic families that rely on energy recovery to achieve low energy dissipation control the flow of data through gate cascades using multiphase clocks. Consequently, they typically use multiple clock generators and can exhibit increased energy consumption on their clock distribution networks. Moreover, they are not attractive for high-speed design due to their high complexity and clock skew management problems. In this paper, we present TSEL, the first energy-recovering (a.k.a. adiabatic) logic family that operates with a single-phase sinusoidal clocking scheme. We also present SCAL, a source-coupled variant of TSEL with improved supply voltage scalability and energy efficiency. Optimal performance under any operating conditions is achieved in SCAL using a tunable current source in each gate. TSEL and SCAL outperform previous adiabatic logic families in terms of energy efficiency and operating speed. In layout-based simulations with 0.5 /spl mu/m standard CMOS process parameters, 8-bit carry-lookahead adders (CLAs) in TSEL and SCAL function correctly for operating frequencies exceeding 200 MHz. In comparison with corresponding CLAs in alternative logic styles that operate at minimum supply voltages, CLAs designed in our single-phase adiabatic logic families are more energy efficient across a broad range of operating frequencies. Specifically, for clock rates ranging from 10 to 200 MHz, our andbit SCAL CLAs are 1.5 to 2.5 times more energy efficient than corresponding adders developed in PAL and 2N2P and 2.0 to 5.0 times less dissipative than their purely combinational or pipelined CMOS counterparts.

No abstract available.

Block-processing can decrease the time and power required to perform any given computation by simultaneously processing multiple samples of input data. The effectiveness of block-processing can be severely limited, however, if the delays in the dataflow graph of the computation are placed suboptimally. In this paper we investigate the application of retiming for improving the effectiveness of block-processing in computations. In particular, we consider the k-delay problem : Given a computation dataflow graph and a positive integer k , we wish to compute a retimed computation graph in which the original delays have been relocated so that k data samples can be processed simultaneously and fully regularly. We give an exact integer linear programming formulation for the k -delay problem. We also describe an algorithm that solves the k -delay problem fast in practice by relying on a set of necessary conditions to prune the search space. Experimental results with synthetic and random benchmarks demonstrate the performance improvements achievable by block-processing and the efficiency of our algorithm.

The application of retiming and clock skew scheduling for improving the operating speed of synchronous circuits under setup and hold constraints is investigated in this paper. It is shown that when both long and short paths are considered, circuits optimized by the simultaneous application of retiming and clock scheduling can achieve shorter clock periods than optimized circuits generated by applying either of the two techniques separately. A mixed-integer linear programming formulation and an efficient heuristic are given for the problem of simultaneous retiming and clock skew scheduling under setup and hold constraints. Experiments with benchmark circuits demonstrate the efficiency of this heuristic and the effectiveness of the combined optimization. All of the test circuits show improvement. For more than half of them, the maximum operating speed increases by more than 21% over the optimized circuits obtained by applying retiming or clock skew scheduling separately.

This paper investigates retiming and clock skew scheduling for improving the tolerance of synchronous circuits to delay variations. It is shown that when both long and short paths are considered, circuits optimized by the combined application of the two techniques are more tolerant to delay variations than when optimized by either of the two techniques separately. A novel mixed-integer linear programming formulation is given for simultaneous retiming and clock scheduling with a target clock period and tolerance under setup and hold constraints. Experiments with LGSynth93 and ISCAS89 benchmark circuits demonstrate the effectiveness of the combined optimization. For half of the test circuits, tolerance to delay variations increased by at least 23% over the separate application of retiming and clock scheduling. Moreover, for two thirds of the test circuits, maximum tolerance improved by at least 11%.

This paper presents a new macromodeling technique for high-level power estimation. Our technique is based on a parameterizable analytical model that relies exclusively on statistical information of the circuit's primary inputs. During estimation, the statistics of the required metrics are extracted from the input stream, and a power estimate is obtained by evaluating a model function that has been characterized in advance. Our model yields power estimates within seconds, because it does not rely on the statistics of the circuit's primary outputs and, consequently, does not perform any simulation during estimation. Moreover, it achieves better accuracy than previous macromodeling approaches by taking into account both spatial and temporal correlations in the input stream. In experiments with the ISCAS-85 combinational circuits, the average absolute relative error of our power macromodeling technique was at most 1.8%. The worst-case error was at most 12.8%. For a ripple-carry adder family, in comparison with power estimates that were obtained using Spice, the average absolute and worst-case errors of our model's estimates were at most 5.1% and 19.8%, respectively. In addition to power dissipation, our macromodeling technique can be used to estimate the statistics of a circuit's primary outputs with very low average errors. It is thus suitable for power estimation in core-based systems with pre-characterized blocks. Once the metrics of the primary inputs are known, the power dissipation of the entire system can be estimated by simply propagating this information through the blocks using their corresponding model functions.

Adiabatic circuits offer a promising alternative to conventional circuitry for low energy design.Their operation is nevertheless subject to fundamental energy-speed trade-offs, just like any other physical realization of boolean logic.Thus, adiabatic circuits with very low energy consumption at low frequencies fail to function at high operating frequencies.Conversely, high-speed adiabatic circuits tend to be dissipative at low clock rates.This paper describes SCAL, a single-phase source-coupled adiabatic logic family that operates efficiently across a wide range of operating frequencies.In layout-based simulations with O&m CMOS process parameters, pipelined carry-lookahead adders developed in our logic function correctly from 1OMHz up to 280MHz.Our SCAL adders are less dissipative than corresponding designs in alternative adiabatic families that remain functional across the same frequency range.Moreover, they are about as dissipative as other adiabatic circuits that are geared towards very efficient operation at low frequencies.In comparison with their CMOS counterparts, our SCAL adders are 3 to 10 times more energy efficient.

In this paper we present a polynomial-time algorithm for retiming synchronous circuits with edge-triggered registers under setup and hold constraints. Given a circuit G and a target clock period c, our algorithm computes in O(V³E) steps a retimed circuit that achieves c and is free of hold violations, where V is the circuit's gate count, and E is the number of wires in the circuit. This is the first polynomial-time algorithm ever reported for retiming with constraints on both long and short paths. The asymptotically efficient operation of our algorithm is based on a novel formulation of the timing constraints as an integer monotonic program with O(E²) inequalities.

In dynamic logic families that rely on energy recovery to achieve low energy dissipation, the flow of data through cascaded gates is controlled using multi-phase clocks. Consequently, these families require multiple clock generators and can exhibit increased energy consumption on their clock distribution networks. Moreover, they are not attractive for high-speed design due to clock skew management problems.

We investigate two strategies for reducing the clock period of a two-phase, level-clocked circuit: clock tuning, which adjusts the waveforms that clock the circuit, and retiming, which relocates circuit latches.These methods can be used to convert a circuit with edge-triggered latches into a faster level-clocked one.We model a two-phase circuit as a graph G ϭ (V, E) whose vertex set V is a collection of combinational logic blocks, and whose edge set E is a set of interconnections.Each interconnection passes through zero or more latches, where each latch is clocked by one of two periodic, nonoverlapping waveforms, or phases.We give efficient polynomial-time algorithms for problems involving the timing verification and optimization of two-phase circuitry.Included are algorithms for -verifying proper timing: O(VE) time.-minimizing the clock period by clock tuning: O(VE) time.-retiming to achieve a given clock period when the phases are symmetric: O(VE ϩ V 2 lg V) time.-retiming to achieve a given clock period when either the duty cycle (high time) of one phase or the ratio of the phases' duty cycles is fixed: O(V 3 ) time.We give fully polynomial-time approximation schemes for clock period minimization, within any given relative error ⑀ Ͼ 0, by -retiming and tuning when the duty cycles of the two phases are required to be equal:-retiming and tuning when either the duty cycle of one phase is fixed or the ratio of the phases' duty cycles is fixed: O(V 3 lg(V/⑀)) time.-simultaneous retiming and clock tuning with no conditions on the duty cycles of the two phases:The first two of these approximation algorithms can be used to obtain the optimum clock period in the special case where all propagation delays are integers.We generalize most of the results for two-phase clocking schemes to simple multiphase clocking disciplines, including ones with overlapping phases.Typically, the algorithms to verify and optimize

The retiming transformation can be used to optimize synchronous circuits for maximum speed of operation by relocating their storage elements. For relatively simple delay models, an optimal retiming of a given circuit can be computed in polynomial time. Under more comprehensive delay models, however, the retiming problem is solved by resorting to branch-and-bound techniques. In this paper, we investigate retiming under delay models that encompass load-dependent gate delays, register delays, interconnect delays, and clock skew. For the most general of our delay models, we express the retiming problem as a set of integer linear programming (ILP) constraints that can be solved using ILP techniques. For less general delay models, which encompass circuits with monotonic clock skews and load-dependent gate delays, we give an integer monotonic programming formulation for the retiming problem and an asymptotically efficient retiming algorithm. Our algorithm re-times any given edge-triggered circuit to achieve a specified clock period in O(V/sup 3/ F) steps, where V is the number of combinational logic gates in the circuit and F is a constant no greater than the circuit's register count. We have implemented our algorithms in DELAY, a software tool for optimizing synchronous circuits, and have evaluated their performance on benchmark circuits.

Abstract|Block-processing is a powerful and popular technique for increasing computation speed by simultaneously processing several samples of data.The eectiveness of block-processing is often reduced, however, due to suboptimal placement of delays in the data ow graph of a computation.In this paper we i n v estigate an application of the retiming transformation for improving the effectiveness of block-processing in computation structures.Speci cally, w e consider the k-delay problem in which w e wish to retime any given computation so that given an integer k the resulting computation can process k data samples simultaneously in a fully regular manner.Our main contribution is an O(V 3 E+V 4 log V )-time algorithm for the k-delay problem, where V is the number of computation blocks and E is the number of interconnections in the computation.

In this paper we introduce fixed-phase retiming, an optimization technique for reducing the power dissipation of digital circuits without sacrificing their performance. In fixed-phase retiming, we first transform any given edge-triggered circuit into a two-phase level-clocked circuit by replacing each flip-flop by two level-sensitive latches. Subsequently, while keeping the latches clocked on one of the phases fixed, we relocate the remaining latches onto interconnections with high glitching activity and capacitive load. We formulate fixed-phase retiming as a Boolean monotonic linear program and give an O(V/sup 6/ log V)-time algorithm for solving it, where V is the number of combinational blocks in the circuit.

Gang scheduling is a resource management scheme for paralder to maximize its performance on each hardware platform.1

Article DELAY: an efficient tool for retiming with realistic delay modeling Share on Authors: Kumar N. Lalgudi Department of Electrical Engineering, Yale University, New Haven, CT Department of Electrical Engineering, Yale University, New Haven, CTView Profile , Marios C. Papaefthymiou Department of Electrical Engineering, Yale University, New Haven, CT Department of Electrical Engineering, Yale University, New Haven, CTView Profile Authors Info & Claims DAC '95: Proceedings of the 32nd annual ACM/IEEE Design Automation ConferenceJanuary 1995 Pages 304–309https://doi.org/10.1145/217474.217546Online:01 January 1995Publication History 35citation265DownloadsMetricsTotal Citations35Total Downloads265Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We address the problem of optimizing logic-level sequential circuits for low power. We present a powerful sequential logic optimization method that is based on selectively precomputing the output logic values of the circuit one clock cycle before they are required, and using the precomputed values to reduce internal switching activity in the succeeding clock cycle. We present two different precomputation architectures which exploit this observation. The primary optimization step is the synthesis of the precomputation logic, which computes the output values for a subset of input conditions. If the output values can be precomputed, the original logic circuit can be "turned off" in the next clock cycle and will have substantially reduced switching activity. The size of the precomputation logic determines the power dissipation reduction, area increase and delay increase relative to the original circuit. Given a logic-level sequential circuit, we present an automatic method of synthesizing precomputation logic so as to achieve maximal reductions in power dissipation. We present experimental results on various sequential circuits. Up to 75% reductions in average switching activity and power dissipation are possible with marginal increases in circuit area and delay.>

Article TIM: a timing package for two-phase, level-clocked circuitry Share on Authors: Marios C. Papaefthymiou View Profile , Keith H. Randall View Profile Authors Info & Claims DAC '93: Proceedings of the 30th international Design Automation ConferenceJuly 1993 Pages 497–502https://doi.org/10.1145/157485.164998Online:01 July 1993Publication History 27citation162DownloadsMetricsTotal Citations27Total Downloads162Last 12 Months1Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Article Free Access Share on Understanding retiming through maximum average-weight cycles Author: Marios C. Papaefthymiou Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MAView Profile Authors Info & Claims SPAA '91: Proceedings of the third annual ACM symposium on Parallel algorithms and architecturesJune 1991 Pages 338–348https://doi.org/10.1145/113379.113410Published:01 June 1991Publication History 9citation308DownloadsMetricsTotal Citations9Total Downloads308Last 12 Months9Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF