Adders are the most fundamental arithmetic units, and often on the timing critical paths of microprocessors. Among various adder configurations, parallel prefix adders provide the best performance vs. power/area trade-off, especially for higher bit-widths. With aggressive technology scaling, the performance of a parallel prefix adder, in addition to the dependence on the logic-level, is determined by wire-length and congestion which can be mitigated by adjusting fan-out. This paper proposes a polynomial-time algorithm to synthesize n bit parallel prefix adders targeting the minimization of the size of the prefix graph with log2n logic level and any arbitrary fan-out restriction. A structure aware prefix node cloning is then applied to the resultant prefix adder solutions to further optimize the size of the prefix graphs. The design space exploration by our approach provides a set of pareto-optimal solutions for delay vs. power trade-off, and these pareto-optimal solutions can be used in high-performance designs instead of picking from a fixed library (Kogge-Stone, Sklansky, etc.). Experimental results demonstrate that our approach: 1) excels highly competitive industry standard Synopsys design compiler adder, regular adders such as Sklansky adder and Kogge-Stone adder, and a highly runtime/memory intensive recent algorithm in 32 nm technology node and 2) improves performance/area over even 64 bit custom designed adders targeting 22 nm technology library and implemented in an industrial high-performance design.

Adders are the most fundamental arithmetic units, and often on the timing critical paths of microprocessors. Among various adder configurations, parallel prefix structures provide the high performance adders for higher bit-widths. With aggressive technology scaling, the performance of a parallel prefix adder, in addition to the dependence on the logic-level, is determined by wire-length and congestion which can be mitigated by adjusting fan-out. This paper proposes a polynomial-time algorithm to synthesize n bit parallel prefix adders targeting the minimization of the size of the prefix graph with log2n logic level and any arbitrary fan-out restriction. The design space exploration by our algorithm provides a set of Pareto-optimal solutions for delay vs. power trade-off, and these Pareto-optimal solutions can be used in high-performance designs instead of picking from a fixed library (Kogge Stone, Sklansky etc.). Experimental results demonstrate that our approach (i) excels highly competitive industry standard Synopsys Design Compiler adder (128 bit) in performance (2%), area (25%) and power (13.3%) in 32nm technology node, and (ii) improves performance/area over even 64 bit custom designed adders targeting 22nm technology library and implemented in an industrial high-performance design.

The design complexity of modern high performance processors calls for innovative design techniques and methodologies for achieving time-to-market goals. New design techniques are also needed to curtail power increases that inherently arise from ever increasing performance targets. This paper describes new processor design and optimization approaches that bridge the gap between high performance and low power. These techniques are flexible as they rely on automated synthesis-centric optimizations to enable power reduction without sacrificing performance. These methodology innovations contributed to the industry leading performance of the POWER8 processor.

As dynamic variability increases with CMOS scaling, it is essential to incorporate large design-time timing margins to ensure yield and reliable operation. Online techniques for timing error resilience help recover timing margins, improving performance and/or power consumption. This paper presents TIMBER, a technique for online timing error resilience that masks timing errors by borrowing time from successive pipeline stages. TIMBER-based error masking can recover timing margins without instruction replay or roll-back support. Three sequential circuit elements are described: TIMBER flip-flop, dedicated TIMBER flip-flop, and TIMBER latch. The TIMBER flip-flop uses two master latches and one slave latch to mask timing errors by borrowing discrete units of time from successive pipeline stages. It can be simplified to a dedicated TIMBER flip-flop that uses only two latches for time-borrowing (TB) at the expense of the flexibility of configuration as a conventional master-slave flip-flop. The TIMBER latch masks timing errors through continuous time-borrowing from successive pipeline stages, and supports runtime configuration as a conventional master-slave flip-flop. The TIMBER latch's continuous time-borrowing capability provides better time-borrowing capabilities at lower hardware cost, but the TIMBER flip-flop's discrete time-borrowing capability preserves the edge triggering property of a flip-flop, thus blocking the propagation of glitches and spurious transitions. In addition to evaluating the overhead and tradeoffs of TIMBER-based error masking on an industrial processor, the three circuits were also prototyped on an FPGA and their timing error masking capability was validated using a two-stage pipeline test structure.

This paper proposes an efficient algorithm to synthesize prefix graph structures that yield adders with the best performance-area trade-off. For designing a parallel prefix adder of a given bit-width, our approach generates prefix graph structures to optimize an objective function such as size of prefix graph subject to constraints like bit-wise output logic level. Given bit-width n and level (L) restriction, our algorithm excels the existing algorithms in minimizing the size of the prefix graph. We also prove its size-optimality when n is a power of two and L= log2n. Besides prefix graph size optimization and having the best performance-area trade-off, our approach, unlike existing techniques, can 1) handle more complex constraints such as maximum node fanout or wire-length that impact the performance/area of a design and 2) generate several feasible solutions that minimize the objective function. Generating several size-optimal solutions provides the option to choose adder designs that mitigate constraints such as wire congestion or power consumption that are difficult to model as constraints during logic synthesis. Experimental results demonstrate that our approach improves performance by 3% and area by 9% over even a 64-bit full custom designed adder implemented in an industrial high-performance design.

This paper proposes an efficient algorithm to synthesize prefix graph structures that yield adders with the best performance-area trade-off. For designing a parallel prefix adder of a given bit-width, our approach generates prefix graph structures to optimize an objective function such as size of prefix graph subject to constraints like bit-wise output logic level. Besides having the best performance-area trade-off our approach, unlike existing techniques, can (i) handle more complex constraints such as maximum node fanout or wire-length that impact the performance/area of a design and (ii) generate several feasible solutions that minimize the objective function. Generating several optimal solutions provides the option to choose adder designs that mitigate constraints such as wire congestion or power consumption that are difficult to model as constraints during logic synthesis. Experimental results demonstrate that our approach improves performance by 3% and area by 9% over even a 64-bit full custom designed adder implemented in an industrial high-performance design.

With technology scaling, logical errors arising due to single-event upsets and timing errors arising due to dynamic variability effects are increasing in logic circuits. Existing techniques for online resilience to logical and timing errors are limited to detection of errors, and often result in significant performance penalty and high area/power overhead. This paper proposes approximate logic circuits as a design approach for low cost concurrent error masking. An approximate logic circuit predicts the value of the outputs of a given logic circuit for a specified portion of the input space, and can indicate uncertainty about the outputs over the rest of the input space. Using portions of the input space that are most vulnerable to errors as the specified input space, we show that approximate logic circuits can be used to provide low overhead concurrent error masking support for a given logic circuit. We describe efficient algorithms for synthesizing approximate circuits for concurrent error masking of logical and timing errors. Results indicate that concurrent error masking based on approximate logic circuits can mask 88% of targeted logical errors for 34% area overhead and 17% power overhead, 100% timing errors on all timing paths within 10% of the critical path delay for 23% area overhead and 8% power overhead, and 100% timing errors on all timing paths within 20% of the critical path delay for 42% area overhead and 26% power overhead.

This paper describes two algorithms for the selective assignment of input don't cares (DCs) for logical derating of input errors to enhance reliability. It is motivated by the observation that reliability-driven assignment of DCs can improve input error resilience by up to 49.7% in logic circuits. Two algorithms - ranking-based and complexity-factor-based - for reliability-driven DC assignment are proposed in this paper. Both algorithms use Hamming distance metrics to determine 0/1 assignments for the most critical DC terms, thereby leaving flexibility in the circuit specification for subsequent optimization. Since ranking-based DC assignment offers less control over overhead, we develop a complexity-factor-based DC assignment algorithm that can achieve up to 21.4% improvement in error rate with a simultaneous 4.3% reduction in area over conventional DC assignment. Finally, we derive analytical estimates on min-max reliability improvements to evaluate the effectiveness of the proposed algorithms.

With aggressive gate oxide scaling, latent defects in the gate oxide manifest as traps that, in time, lead to gate oxide breakdown. Progressive gate oxide breakdown, also referred to as time-dependent dielectric breakdown (TDDB), is emerging as one of the most important sources of performance degradation in nanoscale CMOS devices. This paper describes an accurate analytical model to predict the delay of combinational logic gates subject to TDDB. The analytical model can be seamlessly integrated into a static timing analysis tool to analyze TDDB effects in large combinational logic circuits across a range of supply voltages and severity of oxide breakdown. Simulation results for an early version of an industrial 32 nm library show that the model is accurate to within 3% of SPICE with orders of magnitude improvement in runtime.

Increasing dynamic variability with technology scaling has made it essential to incorporate large design-time timing margins to ensure yield and reliable operation. Online techniques for timing error resilience help recover timing margins, improving performance and/or power consumption. This paper presents TIMBER, a technique for online timing error resilience that masks timing errors by borrowing time from successive pipeline stages. TIMBER-based error masking can recover timing margins without instruction replay or roll-back support. Two sequential circuit elements-TIMBER flip-flop and TIMBER latch-that implement error masking based on time-borrowing are described. Both circuit elements are validated using corner-case circuit simulations, and the overhead and trade-offs of TIMBER-based error masking are evaluated on an industrial processor.

With increasing process variations, low-VT swapping is an effective technique that can be used to improve timing yield without having to modify a design following placement and routing. Gate criticality, defined as the probability that a gate lies on a critical path, forms the basis for existing low-VT swapping techniques. This paper presents a simulation-based study that challenges the effectiveness of low-VT swapping based on the conventional definition of gate criticality, especially as random process variations increase with technology scaling. We introduce dominant gate criticality to address the drawbacks of the conventional definition of gate criticality, and formulate dominant critical gate ranking in the presence of process variations as an optimization problem. Simulation results for 12 benchmark circuits from the ISCAS and OpenSPARC suites to achieve timing yields of 95% and 98% indicate that low-VT swapping based on dominant gate criticality reduces leakage power overhead by 61% and 42% for independent and correlated process variations, respectively, over low-VT swapping based on

Bi-decomposition techniques have been known to significantly reduce area, delay, and power during logic synthesis since they can explore multi-level and, or, and xor decompositions in a scalable technology-independent manner. The complexity of bi-decomposition techniques is in achieving a good variable partition for the given logic function. State-of-the-art techniques use heuristics and/or brute-force enumeration for variable partitioning, which results in sub-optimal results and/or poor scalability with function complexity. This paper describes a fast, scalable algorithm for obtaining provably optimum variable partitions for bi-decomposition of Boolean functions by constructing an undirected graph called the blocking edge graph (BEG). To the best of our knowledge, this is the first algorithm that demonstrates a systematic approach to derive disjoint and overlapping variable partitions for bi-decomposition. Since a BEG has only one vertex per input, our technique scales to Boolean functions with hundreds of inputs. Results indicate that on average, BEG-based bi-decomposition reduces the number of logic levels (mapped delay) of 16 benchmark circuits by 60%, 34%, 45%, and 30% (20%, 19%, 16% and 20%) over the best results of state-of-the-art tools FBDD, SIS, ABC, and an industry-standard synthesizer, respectively.

This paper describes a function-based timing-driven optimization technique for the synthesis of multi-level logic circuits. Motivated by the principles of parallel prefix computation, the proposed timingdriven optimization produces circuits with “lookahead ” properties due to the inherent parallelism among the synthesized sub-circuits. Lookahead logic circuits are synthesized by using global critical path sensitization information to reduce the Boolean functions of the nodes in the technology-independent representation of the logic circuit. Unlike prior function-based timing-driven optimization techniques, where synthesis of the decomposition functions is potentially expensive, the proposed technique has the advantage that the decomposition function is embedded in the synthesized circuit. On average, the proposed technique reduces the number of logic levels (the mapped delay) of the final circuit by 40%, 56%, and 22% (21%, 56 % and 10%) over the best results of SIS, ABC, and Synopsys DC, respectively. 1.

There is a growing concern about timing errors resulting from design marginalities and the effects of circuit aging on speed-paths in logic circuits. This paper presents a low overhead solution for masking timing errors on speed-paths in logic circuits. Error masking at the outputs of a logic circuit is achieved by synthesis of a non-intrusive error-masking circuit that has at least 20% timing slack over the original logic circuit. The error-masking circuit can also be used to collect runtime information when the speed-paths are exercised to (i) predict the onset of wearout and (ii) assist in in-system silicon debug. Simulation results for several benchmark circuits and modules from the OpenSPARC T1 processor are presented to illustrate the effectiveness of the proposed solution. 100% masking of timing errors on all speed-paths within 10% of the critical path delay is achieved for all circuits with an average area (power) overhead of 16% (18%).

Reliability of logic circuits is emerging as an important concern in scaled electronic technologies. Reliability analysis of logic circuits is computationally complex because of the exponential number of inputs, combinations, and correlations in gate failures. This paper presents three accurate and scalable algorithms for reliability analysis of logic circuits. The first algorithm, called observability-based reliability analysis, provides a closed-form expression for reliability and is accurate when single gate failures are dominant in a logic circuit. The second algorithm, called single-pass reliability analysis, computes reliability in a single topological walk through the logic circuit. It computes the exact reliability for circuits without reconvergent fan-out, even in the presence of multiple gate failures. The algorithm can also handle circuits with reconvergent fan-out with high accuracy using correlation coefficients as described in this paper. The third algorithm, called maximum-kgate failure reliability analysis, allows a constraint on the maximum number (k) of gates that can fail simultaneously in a logic circuit. Simulation results for several benchmark circuits demonstrate the accuracy, performance, and potential applications of the proposed algorithms.

Graphene nanoribbon FETs (GNRFETs) are promising devices for beyond-CMOS nanoelectronics because of their excellent carrier transport properties and potential for large scale processing and fabrication. This paper combines atomistic quantum transport modeling with circuit simulation to perform technology exploration for GNRFET circuits. A quantitative study of the effects of variations and defects on the performance and reliability of GNRFET circuits is also presented. Simulation results indicate that whereas GNRFET circuits promise higher performance, lower energy consumption, and comparable reliability at similar operating points to scaled CMOS circuits, they are more susceptible to variations and defects. The results also motivate significant engineering, modeling, and simulation challenges facing the device and CAD communities involved in graphene electronics research.

This paper describes a scalable, technology-independent algorithm for the synthesis of approximate logic circuits. A low overhead, non-intrusive solution for concurrent error detection (CED) based on such circuits is described in this paper. CED based on approximate logic circuits does not impose any performance penalty on the original design. The proposed synthesis algorithm for approximate logic circuits scales with circuit size, and provides fine-grained trade-offs between area-power overhead and CED coverage.

This paper describes a tunable transient filter (TTF) design for soft error rate reduction in combinational logic circuits. TTFs can be inserted into combinational circuits to suppress propagated single- event upsets (SEUs) before they can be captured in latches/flip- flops. TTFs are tuned by adjusting the maximum width of the propagated SEU that can be suppressed. TTFs require 6-14 transistors, making them an attractive cost-effective option to reduce the soft error rate in combinational circuits. A global optimization approach based on geometric programming that integrates TTF insertion with dual-VoD and gate sizing is described. Simulation results for the 70 nm process technology indicate that a 17-48X reduction in the soft error rate can be achieved with this approach.

This paper introduces a class of single-ended coding schemes to reduce off-chip interconnect energy consumption. State-of-the-art codes for processor-memory off-chip interfaces require the transmitter and receiver (memory controller and memory) to collaborate using current and previously transmitted values to encode and decode data. Modern embedded systems, however, cannot afford to use such double-ended codes that require specialized memories to participate in the code. In contrast, a single-ended code enables the memory controller to encode data stored in memory and subsequently decode that data when it is retrieved, allowing the use of commodity memories. In this paper, single-ended codes are presented that assign limited-weight codewords using trace-based mapping techniques. Simulation results show that such codes can reduce the energy consumption of an uncoded off-chip interconnect by up to 42.5%

An optimization algorithm for the design of combinational circuits that are robust to single-event upsets (SEUs) is described. A simple, highly accurate model for the SEU robustness of a logic gate is developed. This model -- in posynomial form -- is integrated with performance and power constraints into an optimization framework based on geometric programming for design space exploration. Simulation results for design optimization using simultaneous dual- VDD and gate sizing techniques for the 70 nm process technology demonstrate the tradeoffs that can be achieved with this approach.

An optimization algorithm for the design of combinational circuits that are robust to single-event upsets (SEUs) is described. A simple, highly accurate model for the SEU robustness of a logic gate is developed. This model is integrated with area and performance constraints into an optimization framework based on geometric programming for design space exploration. Simulation results demonstrate the design tradeoffs that can be achieved with this approach.