Search

Back propagation (BP) based on stochastic gradient descent is the prevailing method to train multilayer neural networks (MNNs) with hidden layers. However, the existence of the physical separation between memory arrays and arithmetic module makes it inefficient and ineffective to implement BP in conventional digital hardware. Although CMOS may alleviate some problems of the hardware implementation of MNNs, synapses based on CMOS cost too much power and areas in very large scale integrated circuits. As a novel device, memristor shows promises to overcome this shortcoming due to its ability to closely integrate processing and memory. This paper proposes a novel circuit for implementing a synapse based on a memristor and two MOSFET tansistors (p-type and n-type). Compared with a CMOS-only circuit, the proposed one reduced the area consumption by 92%–98%. In addition, we develop a fuzzy method for the adjustment of the learning rates of MNNs, which increases the learning accuracy by 2%–3% compared with a constant learning rate. Meanwhile, the fuzzy adjustment method is robust and insensitive to parameter changes due to the approximate reasoning. Furthermore, the proposed methods can be extended to memristor-based multilayer convolutional neural network for complex tasks. The novel architecture behaves in a human-liking thinking process. [ABSTRACT FROM AUTHOR]

In this paper, we propose a stratification+hybrid quasi Monte Carlo (SH-QMC) approach to improve the efficiency of Monte Carlo-based statistical static timing analysis (SSTA) using sample size reduction. Sample size reduction techniques proposed in the literature exhibit a tradeoff between accuracy of the Monte Carlo estimate with fewer samples and their ability to handle large number of variables in multidimensional space. This paper proposes to target several such techniques to different sets of process variation variables by using information about the importance of these variables to the circuit delay, and the capability of the techniques to handle multiple dimensions. Simulations on benchmark circuits up to 90 K gates show that the proposed method requires up to 224 samples for varying levels of process variation to achieve accurate timing estimates. Results also show that when SH-QMC is performed with multiple parallel threads on a quad-core processor, the approach is faster than traditional SSTA with comparable accuracy. When the proposed SH-QMC technique is supplemented with a graph pruning method the runtime is further reduced by 46–48% on average. The technique is also extended to include an incremental approach to recompute a percentile delay metric after engineering change order. [ABSTRACT FROM AUTHOR]

Compositional verification is essential to address state explosion in model checking. Traditionally, an over-approximate context is needed for each individual component in a system for sound verification. This may cause state explosion for the intermediate results as well as inefficiency for abstraction refinement. This paper presents an opposite approach, a compositional reachability method, which constructs the state space of each component from an under-approximate context gradually until a counter-example is found or a fixpoint in state space is reached. This method has an additional advantage in that counter-examples, if there are any, can be found much earlier, thus leading to faster verification. Furthermore, this modular verification framework does not require complex compositional reasoning rules. The experimental results indicate that this method is promising. [ABSTRACT FROM AUTHOR]

Diagnostic march tests are powerful tests that are capable of detecting and identifying faults in memories. Although March SS was published for detecting simple static faults, no test has been published for identifying all faults possibly present in memory cells. In this paper, we target all published simple static faults. We identify faults that cannot be distinguished due to their analog behavior. We present a new methodology for generating irredundant diagnostic march tests for any desired subset of the simple static faults using the necessary and sufficient conditions for fault detection. Using that methodology, along with a verification tool, and trial and error, we were able to build a new 46n diagnostic test for all distinguishable faults named March DSS. March DSS is the first test that is capable of identifying all distinguishable memory static faults. Compared to the latest most comprehensive published diagnostic march test, March DSS provides significant improvement in terms of fault coverage, time complexity, and power consumption. By targeting the same faults, we were able to provide a new test equivalent to the latest published test with 46% improvement in time complexity. [ABSTRACT FROM AUTHOR]

Efficient communication modeling is a critical task in system-on-chip design and exploration. In particular, fast and accurate communication is needed to predict the performance of a system. Recently, transaction level modeling is used to speed up communication simulation at the cost of accuracy. This paper proposes a novel modeling technique, called result-oriented modeling (ROM), which removes the inaccuracy drawback of transaction level models (TLMs) in many cases. Using ROM, simulation models yield nearly the same speed as their traditional TLM counterparts, yet are still 100% accurate in timing. ROM utilizes the fact that internal states in the communication channel are not observable by the caller. Hence, ROM omits the internal states entirely and optimistically predicts the end result. Retroactively, the outcome of the prediction is checked, and if necessary, corrective measures are taken to maintain the accuracy of the model. We have applied the ROM concept to two examples: the industry standard AMBA AHB and the controller area network. To validate the proposed ROM approach, we have analyzed the models in detail for performance and accuracy. Our experimental results show the clear advantages of the ROM concept. For both bus systems, ROM achieves 100% accuracy and highest speeds. In essence, ROM eliminates the TLM tradeoff for a wide range of platforms. It frees the system designer from having multiple models for different purposes and extends the TLM idea to applications that require timing accurate simulation, such as real-time communication. [ABSTRACT FROM AUTHOR]

Critical dimension (CD) variation caused by defocus is largely systematic with dense lines ‘smiling’ through focus while isolated lines ‘frown.’ In this paper, we propose a new design methodology that allows explicit compensation of focus-dependent CD variation, in particular, either within a cell (self-compensated cells) or across cells in a critical path (self-compensated design). By creating iso and dense variants for each library cell, we can achieve designs that are more robust to focus variation. Optimization with a mixture of dense and iso cell variants is possible, both for area and leakage power in timing constraints (critical delay), with the latter an interesting complement to existing leakage-reduction techniques, such as dual-Vth. We implement both a heuristic and mixed-integer linear-programming (MILP) solution methods to address this optimization and experimentally compare their results. Results indicate that designing with a self-compensated cell library incurs 12% area penalty and 6% leakage increase over a baseline library while compensating for focus-dependent CD variation (i.e., the design meets timing constraints across a large range of focus variation). We observe 27% area penalty and 7% leakage increase at the worst case defocus condition using only single-pitch cells. The area penalty of circuits after using both the heuristic and MILP optimization approaches is reduced to 3% while maintaining timing. We also apply the optimization to leakage, which traditionally shows very large variability due to its exponential relationship with gate CD. We conclude that a mixed iso/dense library that is combined with a sensitivity-based optimization approach yields much better area/timing/leakage tradeoffs than using a self-compensated cell library alone. Self-compensated designs show 25% less leakage power on average at the worst defocus condition compared to a design employing a conventional library for the benchmarks studied. [ABSTRACT FROM AUTHOR]

An automated static approach for optimizing bit widths of fixed-point feedforward designs with guaranteed accuracy, called MiniBit, is presented. Methods to minimize both the integer and fraction parts of fixed-point signals with the aim of minimizing the circuit area are described. For range analysis, the technique in this paper identifies the number of integer bits necessary to meet range requirements. For precision analysis, a semianalytical approach with analytical error models in conjunction with adaptive simulated annealing is employed to optimize the number of fraction bits. The analytical models make it possible to guarantee overflow/undertow protection and numerical accuracy for all inputs over the user-specified input intervals. Using a stream compiler for field-programmable gate arrays (FPGAs), the approach in this paper is demonstrated with polynomial approximation, RGB-to-YCbCr conversion, matrix multiplication, B-splines, and discrete cosine transform placed and routed on a Xilinx Virtex-4 FPGA. Improvements for a given design reduce the area and the latency by up to 26% and 12%, respectively, over a design using optimum uniform fraction bit widths. Studies show that MiniBit-optimized designs are within 1% of the area produced from the integer linear programming approach. [ABSTRACT FROM AUTHOR]

To reduce field-programmable gate array power, Vdd programmability has been recently proposed to select the Vdd level for interconnects and power-gate unused interconnects. However, Vdd-level converters used in the existing Vdd-programmable method consume a large amount of leakage. This paper proposes two ways to avoid using level converters in interconnects, namely; 1) tree-based level converter insertion (TLC) and 2) dual-Vdd tree-based level converter insertion (dTLC). TLC enforces that there is only one Vdd level within each routing tree, while dTLC can have different Vdd levels within a routing tree, but no VddL switch drives VddH switches. Dual-Vdd assignment algorithms were developed considering chip-level time slack allocation for maximum power reduction. The algorithms include TLC-S and dTLC-S, two power sensitivity-based algorithms with implicit time slack allocation, and dTLC-LP, a linear programming (LP)-based algorithm with explicit time slack allocation. All allocate time slack first to interconnects with higher power sensitivity and assign low Vdd to them for more power reduction. Experiments show that dTLC-LP obtains the lowest power consumption. Compared to dTLC-LP, dTLC-S obtains a slightly higher power consumption but runs three times faster. Compared to the existing segment-based level converter insertion for dual Vdd, dTLC-LP reduces interconnect power by 52.90% without performance loss for Microelectronics Center of North Carolina benchmark circuits. [ABSTRACT FROM AUTHOR]

This paper describes linear cofactor relationships (LCRs), which are defined as the exclusive sums of cofactors with respect to a pair of variables in Boolean functions. These relationships subsume classical symmetries and single-variable symmetries. The paper proposes an efficient algorithm to detect LCRs and discusses their potential applications in Boolean matching, minimization of decision diagrams, synthesis of regular layout-friendly logic circuits, and detection of support-reducing bound sets. [ABSTRACT FROM AUTHOR]

In this paper, we propose a fast algorithm to construct a performance-driven routing tree with simultaneous buffer insertion and wire sizing in the presence of wire and buffer obstacles. Recently, several algorithms have been published addressing the routing tree construction problem. However, all these algorithms are slow and not scalable. In this paper, we propose an algorithm which is fast and scalable with problem size. The main idea of our approach is to specify some important highslevel features of the whole routing tree so that it can be broken down into several components. We apply stochastic search to find the best specification. Since we need very few high-level features, the size of stochastic search space is small and can be searched in very little time. The solutions for the components are either pregenerated and stored in lookup tables, or generated by extremely fast algorithms when- ever needed. Since it is efficient to obtain solutions for components, it is also efficient to construct and evaluate the whole routing tree for each specification. Experimental results show that, for trees of moderate size, our algorithm out performs the previous algorithms in both quality and runtime. [ABSTRACT FROM AUTHOR]

This paper describes a Boolean satisfiability checking (SAT)-based unbounded symbolic model-checking algorithm. The conjunctive normal form is used to represent sets of states and transition relation. A logical operation on state sets is implemented as an operation on conjunctive normal form formulas. A satisfy-all procedure is proposed to compute the existential quantification required in obtaining the preimage and fix point. The proposed satisfy-all procedure is implemented by modifying a SAT procedure to generate all the satisfying assignments of the input formula, which is based on new efficient techniques such as line justification to make an assignment covering more search space, excluding clause management, and two-level logic minimization to compress the set of found assignments. In addition, a cache table is introduced into the satisfy-all procedure. It is a difficult problem for a satisfy-all procedure to detect the case that a previous, result can be reused. This paper shows that the case can be detected by comparing sets of undetermined variables and clauses. Experimental results show that the proposed algorithm can check more circuits than binary decision diagram-based and previous SAT-based model-checking algorithms. [ABSTRACT FROM AUTHOR]

This paper introduces a simple method for calculating the times at which any signal crosses a prespecified threshold voltage (e.g., 10%, 20%, 50%, etc) directly from the moments. The method can use higher order moments to asymptotically improve the accuracy of the estimated crossing limes. This technique bypasses the steps involved in calculating poles and residues to obtain time-domain information. Once q moments are calculated, only 2q multiplications and (q - 1) additions are required to determine any threshold-crossing time at a certain node. Moreover, this technique avoids other problems such as pole Instability. The final outcome of this paper is a set of empirical expressions relating the moments to different threshold-crossing times in analogy to the td = -0.693m1 formula. The presented methodology can also be used with other user defined forms of empirical expressions relating the moments to different threshold-crossing limes. Several orders of approximations are presented for different threshold-crossing times, depending on the number of moments involved. For example, the worst-case error of a first- to seventh-order (single to seven moments) approximation of 50% RC delay is 1650%, 192.26%, 1131%, 3.37%, 2.57% 2.56%, and 143%, respectively. This technique is very useful to obtain information about certain signal metrics, such as delay and rise time directly without having to compute the whole time domain waveform. In addition, if the whole waveform is required It can be easily determined by interpolation between different threshold-crossing points. The presented technique works for both step and nonstep inputs, including piecewise-linear waveforms. [ABSTRACT FROM AUTHOR]

Symmetry detection in completely specified Boolean functions is important for several applications in logic synthesis, technology mapping, binary decision diagram (BDD) minimization, and testing. This paper presents a new algorithm to detect four basic types of two-variable symmetries. The algorithm detects all pairs of symmetric variables in one pass over the shared BDD of the multioutput function. The worst case complexity of this method is cubic in the number of BDD nodes, but on typical logic synthesis benchmarks the complexity appears to be linear. The computation is particularly efficient when the functions have multiple symmetries or no symmetries. Experiments show that the algorithm is faster than other known methods, and in some cases achieves a speedup of several orders of magnitude. [ABSTRACT FROM AUTHOR]

In this paper, a new efficient and accurate analytical eye-diagram determination technique for interconnect lines is presented. The simplest input test signal model for the intersymbol interference analysis of high-speed data links is mathematically formulated. Since input test patterns for eye boundaries are determined analytically, it is considered very convenient and efficient. The proposed technique shows excellent agreement with the SPICE-based simulation in both eye height and jitter, i.e., within 5% error for nondiscontinuous data paths and 10% error for discontinuous data paths. The method is much more computation-time-efficient than the pseudorandom bit sequence-based SPICE simulation in the order of magnitude. [ABSTRACT FROM AUTHOR]

In this paper, we introduce and study the rectangle escape problem (REP), which is motivated by printed circuit board (PCB) bus escape routing. Given a rectangular region R and a set S of rectangles within R, the REP is to choose a direction for each rectangle to escape to the boundary of R, such that the resultant maximum density over R is minimized. We prove that the REP is NP-complete, and show that it can be formulated as an integer linear programming (ILP). A provably good approximation algorithm for the REP is developed by applying linear programming (LP) relaxation and a special rounding technique to the ILP. In addition, an iterative refinement procedure is proposed as a postprocessing step to further improve the results. Our approximation algorithm is also shown to work for more general versions of REP: weighted REP and simultaneous REP. Our approach is tested on a set of industrial PCB bus escape routing problems. Experimental results show that the optimal solution can be obtained within several seconds for each of the test cases. [ABSTRACT FROM AUTHOR]

Excessive supply voltage drops in a circuit may lead to significant circuit performance degradation and even malfunction. To handle this problem, existing power delivery aware placement algorithms model voltage drops as an optimization objective. We observe that directly minimizing the voltage drops in the objective function might not resolve voltage-drop violations effectively and might cause problems in power-integrity convergence. To remedy this deficiency, in this paper, we propose new techniques to incorporate device power spreading forces into a mixed-size analytical placement framework. Unlike the state-of-the-art previous work that handles the worst voltage-drop spots one by one, our approach simultaneously and globally spreads all the blocks with voltage-drop violations to desired locations directly to minimize the violations. To apply the power force, we model macro current density and power rails for our placement framework to derive desired macro/cell locations. To further improve the solution quality, we propose an efficient mathematical transformation to adjust the power force direction and magnitude. Experimental results show that our approach can substantially improve the voltage drops, wirelength, and runtime over the previous work. [ABSTRACT FROM PUBLISHER]

This paper presents an efficient technique for synthesis and optimization of the polynomials over GF(2m), where m is a nonzero positive integer. The technique is based on a graph-based decomposition and factorization of the polynomials, followed by efficient network factorization and optimization. A technique for efficiently computing the coefficients of the polynomials over GF(pm), where p is a prime number, is first presented. The coefficients are stored as polynomial graphs over GF(pm). The synthesis and optimization is initiated from this graph-based representation. The technique has been applied to minimize multipliers over the fields GF(2κ ), where k = 2,..., 8, generated with all the 51 primitive polynomials in the 0.18-/~m CMOS technology with the help of the Synopsys design compiler. It has also been applied to minimize combinational exponentiation circuits, parallel integer adders and multipliers, and other multivariate bit- as well as word-level polynomials. The experimental results suggest that the proposed technique can reduce area, delay, and power by significant amounts. We also observed that the technique is capable of producing 100% testable circuits for stuck-at faults. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new method for the synthesis of 1-D 90/1 50 linear-hybrid-group cellular automata for CA-polynomials. We obtain large-cell CA very rapidly using our algorithm. This algorithm is efficient and suitable for all practical applications. [ABSTRACT FROM AUTHOR]

Balanced truncation (BT), as applied to date in model order reduction (MOR), is known for its superior accuracy and computable error bounds. Positive-real BT (PRBT) is a particular BT procedure that pre- serves passivity and stability and imposes no structural constraints on the original state space. However, PRBT requires solving two algebraic Riccati equations (AREs), whose computational complexity limits its practical use in large-scale systems. This paper introduces a novel quadratic extension of the alternating direction implicit (ADI) iteration, which is called quadratic AD! (QAD!), that efficiently solves an ARE. A Cholesky factor version of QADI, which is called CFQADI, exploits low-rank matrices and further accelerates PRBT. [ABSTRACT FROM AUTHOR]

With growing market pressures and rising system complexities, automated system-level communication design with efficient design space exploration capabilities is becoming increasingly important. At the same time, customized network-oriented communication architectures become necessary in enabling a high-performance communication among the system components. To this end, corresponding communication design flows that are supported by efficient design automation techniques need to be developed. In this paper, we present a system-level design environment for the generation of bus-based system-on-chip architectures. Our approach supports a two-stage design flow using automated model refinement toward custom heterogeneous communication networks. Starting from an abstract specification of the desired communication channels, our environment automatically generates tailored network models at various levels of abstraction. At its core, an automatic layer-based refinement approach is utilized. We have applied our approach to a set of industrial-strength examples with a wide range of target architectures. Our experimental results show significant productivity gains over a traditional communication design, allowing early and rapid design space exploration. [ABSTRACT FROM AUTHOR]

Increasing levels of process variation in current process technologies make it extremely important that design and process decisions be made while considering their impact. This paper presents a convex-optimization-based approach to select values of supply voltages, threshold voltages, and oxide thicknesses to minimize power dissipation in a simplified abstraction of multi-Vdd/Vth/Tox CMOS designs while considering process variation. The authors use this probabilistic approach to perform optimization of different statistical parameters of power dissipation (e.g., mean or high percentile points) and quantify the impact of rising process variations on these power-minimization techniques. [ABSTRACT FROM AUTHOR]

This paper describes a cosimulation methodology for modeling the electrical behavior of integrated circuit devices in the presence of thermal interactions. The methodology consists of linking a custom finite-volume thermal simulator to a commercially available electrical simulator (Saber, Synopsys, Inc.). Specifically, this paper delineates the techniques developed to resolve the time- and length-scale issues associated with this type of cosimulation that, if left unresolved, typically lead to poor computational performance. These problems, their solutions, and their implementation into the thermal simulator are exposed in detail. [ABSTRACT FROM AUTHOR]

Full testability is a desirable property for a minimal logic network. The classical minimal two-level sum of products (SOP) networks are fully testable in some standard fault models. In this paper, the authors investigate the testability of recently introduced three-level logic forms sum of pseudoproducts (SPP), which allow the representation of Boolean functions with much shorter expressions than two-level forms. The authors study their testability under static fault models (FMs), i.e., the stuck-at-fault model (SAFM) and the cellular fault model (CFM). For SPP networks, several minimal forms can be considered. While full testability can be proven in the SAFM for some forms, SPP networks in the CFM are shown to contain redundancies. Finally, the authors propose a method for transforming nontestable networks into testable ones. In the SAFM, the resulting irredundant networks are still minimal. The experimental results are given to demonstrate the efficiency of the approach. [ABSTRACT FROM AUTHOR]

This paper shows that the worst case switching pattern that incurs the longest bus delay while considering the RLC effect is quite different from that while considering the RC effect alone. It implies that the existing encoding schemes based on the RC model may not improve or possibly worsen the delay when the inductance effects become dominant. A bus-invert method is also proposed to reduce the on-chip bus delay based on the RLC model. Simulation results show that the proposed encoding scheme significantly reduces the worst case coupling delay of the inductance-dominated buses. [ABSTRACT FROM AUTHOR]

Scan design allows a circuit to be tested using states that the circuit cannot enter during functional operation. It was observed that nonfunctional operation during testing may cause excessive currents that can cause a good chip to fail the test because of voltage droops caused by the excessive current demand. A good chip may also fail due to the propagation of signal transitions along nonfunctional long paths, especially during at-speed testing. This problem is studied in this paper in the context of tests for transition faults. A method for determining transition faults that are untestable under functional operation-conditions is described. Two procedures for generating transition-fault tests that use only functional operation conditions are also described. The first procedure accepts as input a broadside test set for transition faults. The second procedure accepts as input a test sequence for the nonscan circuit. Although such a test sequence is more complex to generate and simulate, it results in higher numbers of faults detected under functional operation conditions. [ABSTRACT FROM AUTHOR]

In this paper, the authors present compression techniques for effectively reducing the test-data-volume requirements of modern systems-on-a-chip (SOC). Their techniques are based on the following observations: 1) Conventional test compression schemes, which are designed to satisfy various constraints including low hardware overheads and decompression times, cannot fully exploit compression opportunities present in test data and 2) due to the diversity of components used in SOCs (and consequently in their test strategies and test-data characteristics), a single compression strategy may not be best suited to handle them. The authors propose the use of multilevel and heterogeneous test compression schemes to address the above issues and demonstrate that they can provide significant reductions in the test volume above currently known state-of-the-art test compression techniques. An architecture that reuses infrastructure components already present in SOCs (programmable processors, on-chip communication architecture, memory, etc.) for an efficient implementation of their techniques is proposed. Finally, the authors suggest various architectural-customization techniques, such as partitioning of the decompression functionality between the hardware and software and the addition of custom instructions, to improve decompression times and reduce hardware overheads. Experiments with several designs, including an industrial media-processing SOC, demonstrate the efficacy of the proposed techniques in achieving test-data-volume reductions with low overheads. [ABSTRACT FROM AUTHOR]

Polynomial expressions are frequently encountered in many application domains, particularly in signal processing and computer graphics. Conventional compiler techniques for redundancy elimination such as common subexpression elimination (CSE) are not suited for manipulating polynomial expressions, and designers often resort to hand optimizing these expressions. This paper leverages the algebraic techniques originally developed for multilevel logic synthesis to optimize polynomial expressions by factoring and eliminating common subexpressions. The proposed algorithm was tested on a set of benchmark polynomial expressions where savings of 26.7% in latency and 26.4% in energy consumption were observed for computing these expressions on the StrongARM SA1100 processor core. When these expressions were synthesized in custom hardware, average energy savings of 63.4% for minimum hardware constraints and 24.6% for medium hardware constraints over CSE were observed. [ABSTRACT FROM AUTHOR]

It is essential to formally ascertain whether the register-transfer level (RTL) validation effort effectively guarantees the correctness with respect to the design's architectural intent. The design's architectural intent can be expressed in formal properties. However, due to the capacity limitations of formal verification, these architectural properties cannot be directly verified on the RTL. As a result, a set of lower level RTL properties are developed and verified against the RTL modules. In a top-down design approach, the architect would ideally like to formally guarantee the coverage of the architectural intent at the time of creating the specifications for the component RTL modules (that is, before they are passed to the designers for implementation). In this paper, the authors present: 1) a method for checking whether the RTL properties are covering the architectural properties, that is, whether verifying the RTL properties guarantees the correctness of the design's architectural intent; 2) a method to identify which architectural properties are still uncovered, that is, not guaranteed by the RTL properties; and 3) a methodology for representing the gap between the specifications in a legible form. [ABSTRACT FROM AUTHOR]

In this paper, a time redundancy based Concurrent Error Detection (CED) technique targeting involutional functions is presented. A function F is an involution if F(F(x)) = x. The proposed CED technique exploits the involution property and checks if x = F(F(x)). Unlike traditional time redundancy based CED methods, this technique can detect both permanent and transient faults. [ABSTRACT FROM AUTHOR]

Increasingly significant variational effects present a great challenge for delivering desired clock skew reliably. Nontree clock network has been recognized as a promising approach to overcome the variation problem. Existing nontree clock routing methods are restricted to a few simple or regular structures, and often consume excessive amounts of wirelength. This paper suggests to construct a low-cost nontree dock network by inserting crosslinks in a given clock tree. The effects of the link insertion on clock skew variability are analyzed. Based on the analysis, this paper proposes two link insertion schemes that can quickly convert a clock tree to a nontree with significantly lower skew variability and very limited wirelength increase. In these schemes, the complicated nontree delay computation is circumvented. Further, they can be applied to the recently popular nonzero skew routing easily. The effectiveness of the proposed techniques has been validated through SPICE-based Monte Carlo simulations. [ABSTRACT FROM AUTHOR]

This paper presents a gate-sizing algorithm for coupling-noise reduction, which optimizes the area or power consumption (represented as a weighted sum of gate sizes) of a circuit while ensuring that its timing constraints are met. A problem for gate-size optimization under coupling-noise and timing constraints is formulated, and is broken down into two subproblems of gate-size optimization under noise and timing constraints, respectively. The subproblem of gate-size optimization under noise constraints is solved as a fixpoint computation problem on a complete lattice. The proposed algorithm to solve this problem is guaranteed to yield the optimal solution, provided it exists. The subproblem for circuit optimization under timing constraints is considered as a geometrical programming problem. The solutions to the two problems are finally combined to solve the original problem in a Lagrangian relaxation (LR) framework. Experimental results demonstrating the effectiveness of the algorithms are reported for the International Symposium on Circuits and Systems IISCAS) benchmarks and larger circuits. The obtained results are compared to the approach where successive iterations of gate sizing are performed for timing and for noise reduction independently. This alternative design approach is driven by the algorithms used to solving the mentioned subproblems, respectively. [ABSTRACT FROM AUTHOR]

With continuing scaling of CMOS process, process variations in the form of die-to-die and within-die variations become significant which cause timing uncertainty. Statistical design methods have been proposed in the past to model the impact of process variations. However, all the existing methods deal almost exclusively with modeling delay variations of logical gates or physical variations of interconnect wires. This paper proposes a method of analytically analyzing statistical behavior of multiple coupled interconnects with an uncertain signal arrival time at each interconnect input (aggressors and the victim). The method utilizes delay-change characteristics due to changes in relative arrival time between an aggressor and the victim. The results show that the proposed method is able to accurately predict delay variations through a coupled interconnect. [ABSTRACT FROM AUTHOR]

Physical unclonable function (PUF) is a technique to produce secret keys or complete authentication in integrated circuits (ICs) by exploiting the uncontrollable randomness due to manufacturing process variations. For better PUF applications, efficient analysis of different designs is important. In this article, a mathematical model to analyze the performance of typical strong PUF designs is proposed and applied to arbiter PUF, ring oscillator (RO) PUF, and duty cycle (DC) PUF. For better reliability, a new PUF design, DC multiplexer (DC MUX) PUF proposed in our previous work is analyzed. The proposed model indicates that DC MUX PUF achieves 2% higher reliability than arbiter PUF under environment influences. It also shows that DC PUF achieves 10% higher reliability than RO PUF. For verification, the aforementioned four PUF designs are testified using HSPICE. As our model analysis indicates, for reliability DC MUX PUF outperforms arbiter PUF, and DC PUF outperforms RO PUF. For randomness, DC MUX PUF and DC PUF outperform arbiter PUF and RO PUF, respectively. For security, LR attacks on DC MUX PUF and arbiter PUF are performed. The training time for DC MUX PUF is 40 000 times of arbiter PUF. [ABSTRACT FROM AUTHOR]

Single isolated fault (SIF) stands for about 60%–70% of the total number of defects and is rather redundancy hungry since a spare row or a column is required for repairing each SIF. Therefore, manufacturing yield will decrease if we do not allocate sufficient spare resources. In this paper, instead of the traditional fault replacement techniques, synergistic techniques that integrate both fault replacement and fault masking techniques are proposed. With our approaches, SIFs are masked instead of the traditional replacement for repairing. For other minor fault types (e.g., faulty rows and faulty columns), the fault replacement technique is used as usual. According to simulation results, repair rates can be improved significantly. The proposed techniques can be integrated with the conventional built-in self-repair with nearly negligible hardware overhead. [ABSTRACT FROM PUBLISHER]

This paper presents a completely new approach to the problem of hypergraph clustering for wirelength-driven placement. The novel algorithm we propose is called SafeChoice (SC). Different from all previous approaches, SC is proposed based on a fundamental theorem, safe condition which guarantees that clustering would not degrade the placement wirelength. To mathematically derive such a theorem, we first introduce the concept of safe clustering, i.e., do clustering without degrading the placement quality. To efficiently check the safe condition for pair-wise clustering, we propose a technique called selective enumeration. SafeChoice maintains a global priority queue based on the safeness and area of potential clusters. Using a simple heuristic, it automatically stops clustering when generating more clusters would degrade the placement wirelength. Moreover, we extend SafeChoice to do clustering while considering the object physical locations, i.e., physical clustering. Finally, we apply SafeChoice into a two-phase placement framework and propose a high-quality analytical placement algorithm called SCPlace. Comprehensive experimental results show that the clusters produced by SC consistently help the placer to achieve the best wirelength among all other clustering algorithms, and SCPlace generates the best half-perimeter wirelength compared with all other state-of-the-art placers. [ABSTRACT FROM AUTHOR]

This paper proposes a methodology for performance evaluation of schedules for job-shops modeled using tag machines. The most general tag structure for capturing dependences is shown to be inadequate for the task. A new tag structure is proposed. Comparison of the method with existing ones reveals that the proposed method has no dependence on schedule length in terms of modeling efficiency and it shares the same order of complexity with existing approaches. The proposed method, however, is shown to bear promise of applicability to other models of computation and hence to heterogeneous system models having such constituent models. [ABSTRACT FROM AUTHOR]

A novel algorithm for automatic behavioral model topology formulation (MTF) is described in this paper. Several new terms are defined to support this formulation approach. The algorithms for determining the controllability and equivalence of branches are developed. The identification of differential pairs and current mirror structures is implemented automatically. Some other algorithms identify a subset of nodes in circuits that are extracted and modeled, while the other nodes will be collapsed. The MTF algorithm then is applied to construct a new signal-path graph, i.e., forming an equivalent circuit that has the ability to represent the behavior of the original circuit in a much-simplified form. This algorithm is implemented in a fully automated modeling tool, ASCEND, which starts from the netlist description of a circuit and generates a differential-algebraic-equation-based model. These models are able to represent static and dynamic behaviors with excellent accuracy and significant simulation speedup. The details of the MTF algorithm are described. Examples of applying the MTF algorithm for behavioral modeling are given. [ABSTRACT FROM AUTHOR]

A key challenge in using timing-robust asynchronous circuit styles is the lack of automated optimization techniques. In this paper, technology mapping and cell merger algorithms for asynchronous threshold networks are introduced. The cell merger problem is a restricted form of technology mapping where only adjacent cells are merged. The two algorithms can each target either delay or area, or a combined delay-area cost function. Experiments were performed on substantial industrial design examples (DES and GCD circuits) that had already been optimized by an existing commercial asynchronous synthesis tool flow. Average delay improvements of 31.6% for basic technology mapping and 29.6% for basic cell merger were obtained. Average area improvements of 9.5 % for basic technology mapping and 8.5 % for basic cell merger were also obtained. Additional experiments were performed on the largest MCNC combinational benchmarks with similar results. Finally, targeting a hybrid cost function, area minimization under specified hard timing constraints, a further area reduction of up to 10.7% on average in technology mapping was recovered without compromising the overall system performance. The new algorithms are the first systematic and general mapping approach for asynchronous threshold networks, targeting delay or area, which preserve the timing-robustness properties of the initial unoptimized circuits. [ABSTRACT FROM AUTHOR]

Diagnostic fault simulation is used to determine the pairs of faults distinguished by a given test set or test sequence. Diagnostic test generation is used to generate tests that distinguish pairs of faults. Typically, the test sets or test sequences contain tests that detect all the detectable target faults. In this paper, a framework for diagnostic fault simulation and test generation is described, based on structural circuit characteristics called z-sets. These characteristics are used to show that certain fault pairs are guaranteed to be distinguished by a fault detection test set. Such fault pairs do not need to be considered during diagnostic fault simulation or test generation that starts from a fault detection test set. Experimental results for single stuck-at faults in full-scan benchmark circuits demonstrate that only small percentages of fault pairs need to be considered during diagnostic fault simulation or test generation once a fault detection test set is available. The concept of z-sets is extended to define z-detections. This concept uses the results of conventional fault simulation to determine additional fault pairs that are guaranteed to be distinguished by a fault detection test set. The concept of z-sets is also extended to define difference-sets (or d-sets) that provide even fewer targets for diagnostic test generation. [ABSTRACT FROM AUTHOR]

Due to technology scaling trends, the accurate and efficient calculations of the temperature distribution corresponding to a specific circuit layout and power density distribution will become indispensable in the design of high-performance very large scale integrated circuits. In this paper, we present three highly efficient thermal simulation algorithms for calculating the on-chip temperature distribution in a multilayered substrate structure. All three algorithms are based on the concept of the Green function and utilize the technique of discrete cosine transform. However, the application areas of the algorithms are different. The first algorithm is suitable for localized analysis in thermal problems, whereas the second algorithm targets full-chip temperature profiling. The third algorithm, which combines the advantages of the first two algorithms, can be used to perform thermal simulations where the accuracy requirement differs from place to place over the same chip. Experimental results show that all three algorithms can achieve relative errors of around 1% compared with that of a commercial computational fluid dynamic software package for thermal analysis, whereas their efficiencies are orders of magnitude higher than that of the direct application of the Green function method. [ABSTRACT FROM AUTHOR]

In this paper, we study the retiming problem of sequential circuits with net topology optimization. Both interconnect and gate delay are considered in retiming. Most previous retiming algorithms have assumed ideal conditions for the nonlogical portions of data paths, which are not sufficiently accurate to be used in high-performance circuits today. In our modeling, we assume that the delay of a wire is directly proportional to its length. This assumption is reasonable since the quadratic component of a wire delay is significantly smaller than its linear component when the more accurate Elmore delay model is used. A simple experiment was conducted to illustrate the validity of this assumption. We present two approaches to solve the retiming problem, both of which have polynomial time complexity. The first one can compute the optimal clock period, while the second one is an improvement over the first one in terms of practical applicability. The second approach gives solutions that are very close to the optimal (0.06% more than the optimal on average) but in a much shorter runtime. The optimally retimed circuit will then be realized physically by placing the registers and finding the net topologies. In contrast to many previous works [Proc. IEEE mt. Conf. Comput.-Aided Des., p. 136, 1998], [IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., 22(7) Jul. 2003] that performed simple calculations to determine the register positions, our approach can preserve the optimal clock period that is obtained by the retiming step and utilize as few registers as possible. Minimization of register number saves both area and power in register and clock loading. Our topology optimization step is shown to be optimal for nets with four or fewer pins, and this type of nets constitutes over 90% of the nets in a sequential circuit on average. Using the ISCAS89 benchmark, we tested our algorithm with a 0.35-μsm complementary metal-oxide-semiconductor standard cell library. Silicon Ensemble was used to layout the design with a row utilization of 50%. Experimental results showed that our algorithm could find the best sharing of registers for a net in most of the cases, i.e., using the minimum number of registers while preserving the target clock period that is obtained by the retiming step, within a minute run on an Intel Pentium IV 1.5 GHz PC with 512 MB RAM. [ABSTRACT FROM AUTHOR]

Convex-optimization techniques are very popular in the very large-scale-integration design society due to guaranteed convergence to a global optimal point. The table data need to be fitted into convex forms to be used in the convex optimization problems. Fitting the tables into posynomials, which are analytically convex under logarithmic transformation, may suffer from the excessive fitting errors as the fitting problem is nonconvex. In this paper, we propose to directly adjust the lookup-table values into a numerically convex lookup table without any explicit analytical form. We show that numerically ‘convexifying’ the lookup-table data with minimum perturbation can be formulated as a convex semidefinite optimization problem, and hence, optimality can be reached in polynomial time. We also propose three algorithms to make the table data smooth to enable faster convergence of the convex optimizer. Results from extensive experiments on industrial cell libraries demonstrate 9.6x improvement in fitting error over a well- developed posynomial-fitting procedure. We illustrate the effectiveness of this model in a convex optimization problem by providing results for using our model in the optimal gate sizing of standard cells. We observe a 5.07% improvement in the delay of International Symposium on Circuits and Systems (ISCAS) benchmark circuits over the posynomial-fitting procedure. [ABSTRACT FROM AUTHOR]

Conventional high-level synthesis (HLS) algorithms are very conservative when dealing with read-after-write (RAW) dependences, the execution of one operation is allowed once all its predecessors have been calculated. However, in the execution of arithmetic operations, some bits are required later than others, and some bits are produced earlier than others. This paper proposes a presynthesis optimization algorithm that relaxes RAW dependences, taking advantage of this feature for a more efficient HLS of data flow graphs formed by additions, multiplications, and logic operations. The presented preprocessor analyzes the critical path at bit granularity and splits the arithmetic operations into subword fragments. These fragments become the input to any regular HLS tool to speed up circuit execution times through scheduling in different cycles of the fragments obtained from the same original operation. This way, the execution of one operation may begin before the calculus of its predecessors has been completed. This becomes feasible when the execution of the predecessor has begun in the selected cycle or in a previous one, and even if it will finish in a posterior cycle. The experimental results that were carried out show that implementations obtained from the optimized specification are, on the average, 70% faster, with only slight variations in the data path area. [ABSTRACT FROM AUTHOR]

This paper describes a new discretization scheme for quantum confinement transport simulations using a quantum drift-diffusion model. A high-resolution scheme is constructed by developing an exponential-fitting method with the slope limiter in a class of conservative schemes to simulate the flow of electrons with quantum confinement effects in MOSFETs. This method is reinterpreted as a flux-limiter method that hybridizes a low-order flux and a high-order flux into a single numerical flux. The discretization method provides good approximations to the density profile in the smooth regions and boundary layers of the electron flow and allows high-resolution simulations of quantum confinement transport in ultrasmall MOSFETs. [ABSTRACT FROM AUTHOR]

This paper describes the implementation of a wire length-driven force-directed placer named FDP for generic placement. Specifically, it describes efficient force computation for cell spreading, numerical instabilities during force-directed placement, a means to avoid instabilities, and metrics for proper assessment of cell distribution throughout the placement region. It demonstrates that one of the greatest impediments to achieving high-quality placements using a force-directed placer lies in the large amount of cell overlap present in initial placements. This overlap makes the determination of cell ordering difficult and can lead to the inadvertent separation of highly connected cells. It is shown that median improvement and multilevel clustering improve cell ordering and aid in wire length minimization. Numerical results are presented for both standard cell and mixed-size placement problems. For standard cell problems, the tool generates placements that are, on average, 3% better than Capo 9.0, but 5% worse than FengShui 2.6. For mixed-size problems, FDP generated placements that are, on average, 2%–5% better than Capo 9.0 and -5%–-2% better than Fengshui 2.6, depending on the presence (or absence) of pin offsets. Run times for FDP are higher than both Capo 9.0 and FengShu 2.6, although reasonable. [ABSTRACT FROM AUTHOR]

Most methods for hardware power estimation operate at the register-transfer level (RTL) or lower levels of design abstraction. Since cycle-accurate functional descriptions (CAFDs) are being widely adopted in integrated circuit (IC) design flows, power estimation can potentially benefit from the inherent increase in the efficiency of a cycle-based functional simulation. However, attempts at power estimation for functional descriptions have suffered from a poor accuracy because the design decisions performed during their synthesis lead to an unavoidable large uncertainty in any power estimate that is based solely on the functional description. The authors propose a methodology for a CAFD power estimation that combines the accuracy achieved by structural RTL power estimation with the efficiency of cycle-accurate functional simulation. This goal is achieved by viewing a CAFD as an abstraction of a specific known RTL implementation that is synthesized from it. The authors identify correlations between a CAFD and its RTL implementation and ‘back-annotate’ information into the CAFD solely for power estimation. The resulting RTL-aware CAFD contains a layer of code that instantiates virtual placeholders for RTL components and maps values of CAFD variables into the RTL components' inputs/outputs, thus enabling efficient and accurate power estimation. Power estimation is performed in the proposed methodology by simply cosimulating the RTL-aware CAFD with a simulatable power-model library that contains power macromodels for each RTL component. Techniques to further improve the speed of CAFD power estimation through the use of control-state-based adaptive power sampling are presented. The authors have implemented and evaluated the proposed techniques in the context of a commercial C-based hardware design flow. Experiments with a number of large industrial designs (up to 1 000 000 gates) demonstrate that the proposed methodology achieves an accuracy very close to RTL power estimation with two-three orders of magnitude speedup in estimation times. [ABSTRACT FROM AUTHOR]

Three-dimensional (3-D) packaging via system-on-a-package (SOP) has been recently proposed as an alternative solution to overcome the limitation of system-on-a-chip (SOC) and meet the rigorous requirements of today's mixed signal system integration. The true potential of SOP technology lies in its capability to integrate both active and passive components into a single high speed/density 3-D packaging substrate. The routing environment for 3-D SOP is more advanced than that of the conventional printed circuit board (PCB) or multichip module (MCM) technology—pins are located at all layers of the SOP packaging substrate rather than the topmost layer only, and various types of vias are available for layer-to-layer connections. The contribution of this work is to provide: 1) the formulation of the new block-level 3-D global routing problem under wire length, layer, crosstalk, and congestion minimization and 2) the first global router for 3-D SOP named 3PGR. This paper reviews various approaches for MCM routing algorithms and investigates their applicability to the SOP model. The related experimental results demonstrate the effectiveness of the algorithms. [ABSTRACT FROM AUTHOR]

This paper presents two recently developed algorithms for efficient model order reduction. Both algorithms enable the fast solution of continuous-time algebraic Riccati equations (CAREs) that constitute the bottleneck in the passivity-preserving balanced stochastic truncation (BST). The first algorithm is a Smith-method-based Newton algorithm, called Newton/Smith CARE, that exploits low-rank matrices commonly found in physical system modeling. The second algorithm is a project- and-balance scheme that utilizes dominant eigenspace projection, followed by a simultaneous solution of a pair of dual CAREs through completely separating the stable and unstable invariant subspaces of a Hamiltonian matrix. The algorithms can be applied individually or together. Numerical examples show the proposed algorithms offer significant computational savings and better accuracy in reduced-order models over those from conventional schemes. [ABSTRACT FROM AUTHOR]

This paper describes a design for testability (DFT) approach for synchronous sequential circuits that combines scan with nonscan DFT in a transparent way. DFT control inputs and scan chain inputs are used as primary inputs of the circuit, and scan chain outputs are used as primary outputs of the circuit during test generation to eliminate the distinction between functional clock cycles and the various types of nonfunctional clock cycles. The result is 1) short test application times due to the nonscan DFT modes and the ability to use limited scan operations and 2) the ability to detect all the combinationally irredundant faults due to the scan mode. [ABSTRACT FROM AUTHOR]

This paper presents two low-cost fault-independent techniques that can be used to identify significantly more untestable faults than could be identified by earlier fault-independent techniques. A new theorem and an efficient implementation of the theorem for the purpose of identifying sequentially untestable faults are presented first. Unlike the single-fault theorem where the stuck-at fault is injected exclusively in the last time frame of the k-frame unrolled circuit, this theorem enables a fault injection in any time frame within the unrolled sequential circuit. To efficiently apply the authors' concept to untestable fault identification, sequential implications are used to extend the unobservability propagation of gates to multiple time frames during single-line conflict analysis. Then, a new technique called ‘maximizing local impossibilities’ is proposed. This technique efficiently identifies multiple-node conflicting assignments by analyzing logical relationships local to Boolean gates in the circuit. Using this new concept in conjunction with a powerful implication engine enables identification of many more untestable faults that were missed by the single-line conflict-based approach. Since this approach concentrates on identifying conflicting combinations locally around each Boolean gate in the circuit, its complexity is linear in the size of the circuit. The application of these two proposed techniques to the International Symposium on Circuits and Systems (ISCAS) 1985 and ISCAS 1989 Sequential Benchmark Circuits showed a significant increase in the number of faults identified as untestable, at practically no overhead in both the memory and the execution time. [ABSTRACT FROM AUTHOR]