As microprocessor design progresses from tens of millions of transistors on a chip using 0.18-/spl mu/m process technology to approximately a billion transistors on a chip using 0.10-/spl mu/m and finer process technologies, the microprocessor designer faces unprecedented Electronic Design Automation (EDA) challenges over the future generations of microprocessors. This paper describes the changes in the design environment that will be necessary to develop increasingly complex microprocessors. In particular, the paper describes the current status and the future challenges along three important areas in a design flow: design correctness, performance verification and power management.

Considering testability during the early stages of the design flow can have several benefits, including significantly improved fault coverage, reduced test hardware overheads, and reduced design iteration times. This paper presents an overview of high level design methodologies that consider testability during the early (behavior and architecture) stages of the design flow, and their testability benefits. The topics reviewed include behavioral and RTL test synthesis approaches that generate easily testable implementations targeting ATPG (full and partial scan) and BIST methodologies, and techniques to use high-level information for ATPG.

Concurrent error detection in digital circuits is very important in applications where error in processed data can have catastrophic effects. Typically, error detection is performed by a small amount of additional hardware called the checking circuit. In the past, researchers have developed techniques for concurrent error detection in linear digital state variable circuits. In this paper, we investigate concurrent error detection techniques for nonlinear digital circuits that compute polynomial functions of multiple variables. Such circuits have widespread use in the design of various classes of nonlinear digital filters. The proposed error detection schemes are possible due to the use of a new linearization method called time-freeze linearization. In this method, a nonlinear circuit is modeled as a linear circuit for each individual time frame corresponding to the time taken to process a given set of input data. The defining parameters of this linear model change from one time frame to another but are regarded as fixed or frozen in any given time frame. This allows the use of real number checksum codes for fault detection. As opposed to duplicating the entire nonlinear part of the circuit, our approach allows us to use the nonlinear functions to drive the check circuitry, while achieving full fault coverage at low hardware cost.

We show that existing synthesis techniques may produce asynchronous circuits that are not initializable by gate level analysis tools even when the design is functionally initializable. Due to the absence of any initialization sequence, a fault simulator or test generator that assumes an unknown starting state will be completely ineffective for these circuits. In this paper, we show that proper consideration of initializability during the asynchronous circuit synthesis procedure can guarantee initializable implementations. We show that the assignment of don't cares during the synthesis procedure affects the initializability of the final implementation. We present a novel implicit enumeration procedure that selectively assigns don't cares to obtain an initializable implementation. Initialization sequences are obtained as a by-product of our synthesis procedure.

We address the problem of transforming a behavioral specification so that synthesis of a testable implementation from the new specification requires significantly less area and partial scan cost than synthesis from the original specification. A two-stage objective function, that estimates the area and testability of the final implementation, and also captures enabling effects of the transformations, is developed. Optimization is done using a new randomized branch and bound steepest descent algorithm. Application of the transformation algorithm on several examples demonstrates significant simultaneous improvement in both area and testability of the final implementations.

There are two major reasons why high-level test synthesis (HLTS) has advantages over design for testability (DFT) at low level: (l) size complexity and (2) functional abstraction. A design grows significantly in size when it is synthesized into a low level description. For example, the behavioral description of an FIR filter in Silage language required only one page, whereas the structural VHDL of the same design at gate level required as much as forty pages. This explosion in size complexity causes a loss in the effectiveness of any automated tool. The second advantage, functional abstraction, allows one to utilize specific functional behaviors, that can be used for various activities during ATPG. For example, it is easy to identify that an adder will propagate a pattern at one of the inputs to its output provided the other input is zero, but at the gate level it requires a large amount of search to derive the same information. HLTS has access to more information than low-level DFT, hence the former is capable of achieving more than the latter. As we go higher in the description, the more functional abstraction we can get, thereby making the testing tasks easier.

We address the problem of transforming a behavioral specification so that synthesis of a testable implementation from the new specification requires significantly less area and partial scan cost than synthesis from the original specification. The proposed approach has three components: a library of relevant transformation mechanisms, an objective function, and an optimization algorithm. The most effective transformations for testability optimization are identified by analyzing the fundamental relationship between transformational mechanisms and topological and functional properties of the computations that affect testability. A dynamic, two-stage objective function that estimates the area and testability of the final implementation, and also captures enabling and disabling effects of the transformations, is developed. Optimization is done using a new randomized branch and bound steepest descent algorithm. Application of the transformation algorithm on several benchmark examples demonstrates significant simultaneous improvement in both area and testability of the final implementations.>

We introduce BETS, a behavioral test synthesis system, for the synthesis of high-throughput, area-efficient testable designs. While hardware sharing is a powerful technique to achieve area efficiency, it may adversely affect the testability of the synthesized design by introducing new loops. Besides CDFG loops, hardware sharing introduces three other types of loops: assignment loops, sequential false loops, and register files cliques. We provide a comprehensive analysis and a formal grammar characterization of the sources of loops in the data path during behavioral synthesis. Partial scan is a cost-effective technique for sequential circuit testing. Hardware sharing of scan registers can be used to minimize the number of scan registers required to synthesize data paths with minimal number of loops. The scan registers can be shared amongst several variables of the CDFG, to break not only the loops in the CDFG, but also the very loops introduced in the data path by hardware sharing. A new random walk based algorithm is proposed to break all CDFG loops using a minimal number of scan registers. The subsequent scheduling and assignment phase avoids formation of loops in the data path by reusing the scan registers, while ensuring high resource utilization. The experimental results demonstrate the effectiveness of the new technique to synthesize easily testable data paths, with nominal hardware overhead, while maintaining the performance of the designs. The partial scan overhead incurred by the technique is significantly less than that of a gate-level partial scan approach.>

Partial scan is a popular design for testability technique for cost-effective sequential automatic test pattern generation (ATPG). An efficient partial scan approach selects flip-flops (FFs) in the minimum feedback vertex set (MFVS) of the FF dependency graph, so that loops are broken. Through an analysis of the sources of loops in the data path, this paper proposes a new high-level synthesis methodology to synthesize DSP designs which have low-cardinality MFVS, thereby reducing the cost of partial scan significantly. A test efficiency of 100% could be achieved for all designs synthesized by the proposed approach, requiring a significantly less number of FFs to be scanned compared to the original implementations.>

We present a procedure for synthesizing initializable asynchronous circuits from functionally uninitializable Signal Transition Graphs (STG). After characterizing the necessary conditions for functional uninitializability, we propose a technique that transforms the original STG into an equivalent, functionally initializable STG. It is shown that initializability can be achieved by sacrificing minimal concurrency without violating the syntactic properties of the STG required for a hazard-free implementation. The synthesis of a trigger module illustrates this procedure.>

Fault diagnosis in digital signal processing (DSP) circuits is very important for debugging circuit prototypes and chips and for identifying manufacturing process related problems. In this paper, we address the problem of diagnosing failures in digital filters. It is assumed that the circuit response obtained during off-line testing of digital filters is to be used for fault diagnosis. The tests applied to the filter consist of input data patterns generated by a standard test pattern generation algorithm. We propose a design for diagnosability procedure, based on time space expansion of a digital filter, which allows one circuit node in addition to the normal filter output to be externally observable for diagnosability purposes. The diagnosis is performed by measuring the error magnitudes at the observable circuit nodes at different times during application of the test sequence.>

An efficient partial scan approach for cost-effective sequential ATPG is to select flip-flops (FFs) in the minimum feedback vertex set (MFVS) of the FF dependency graph, so that loops are broken. Through a comprehensive analysis of the sources of loops in the data path, this paper proposes a new high-level synthesis methodology to synthesize data paths which have low-cardinality MFVS, thereby reducing the cost of partial scan significantly. A test efficiency of 100% could be achieved for all designs synthesized by the proposed approach, requiring a significantly less number of FFs to be scanned compared to the original implementations.>

Most behavioral synthesis tools perform limited architectural transformations to optimize hardware.In this paper, we present a new architectural transformation scheme that changes the circuit interconnections and the descriptions of constant multipliers.The scheme is based on numerical matrix transformation algorithms that allow a given matrix to be expressed as the product of severrd matrices and achieves significant hardware savings over conventional methods.

A new approach to high level synthesis, which simultaneously addresses testability and resource utilization, is presented. We explore the relationship between hardware sharing, loops in the synthesized data-path, and partial scan overhead. Since loops make a circuit hard to test, a comprehensive analysis of the sources of loops in the data path, created during high level synthesis, is provided. The paper introduces the problem of breaking CDFG loops with a minimal number of scan registers. Subsequent scheduling and assignment avoid formation of loops in the data path by sharing the scan registers, while ensuring high resource utilization. Experimental results demonstrate the effectiveness of the technique to synthesize easily testable data paths, with significantly less partial scan cost than a gate-level partial scan approach.

Concurrent error detection in digital state variable circuits is very important, because they are often used in critical digital signal processing (DSP) and control applications where error in processed data can have catastrophic effects. Typically, error detection is performed by a small amount of additional hardware called the checking circuit. In this paper, we investigate concurrent error detection techniques for nonlinear digital circuits that compute polynomial functions of multiple variables. The novelty of our approach allows us to use the nonlinear functions to drive the check circuitry without duplicating the entire nonlinear part, while achieving high fault coverage.>

A greedy optimization technique for minimizing the area of linear digital systems using a combination of common subexpression elimination and modification of multiplier coefficients is proposed. Since the amount of logic required by a coefficient multiplier is dependent on the value of the coefficient, the given system is transformed, using splitting of coefficients, in such a way that the overall circuit requires a smaller area. The approach explores a much larger design space as compared to previously known techniques. The approach is the first to optimize numerically intensive digital circuits by additive decomposition of multiplier coefficients. The new synthesis scheme generates functionally equivalent but structurally different circuits with a 15 to 40% reduction in area over conventional methods, for practical circuits with DSP applications.>

A hierarchial testing approach for linear state variable digital systems based on matrix manipulation and constrained low-level test generation is reported. FEAST (functional extractor and sequential test generator) operates at the high level, where the circuit is described as an interconnection of arithmetic modules. CREST (constrained sequential test generator) operates at the low level description of the individual modules, and generates test sets satisfying constraints imposed by the high-level modules and their interconnection structure. The approach was found to perform better than automatic test generation at the gate level using existing algorithms for several large circuits.>

Delay fault testing of iterative arithmetic arrays (IAAs) is important because IAAs contain long critical paths and often determine the clock speed. A new approach, based on a weighted graph model has been developed that exploits the regularity of IAAs to select paths to be tested, and generates delay fault tests for those paths. The number of longest paths in an IAA grows exponentially with the dimension of the IAA, but the technique tests only a selected subset of longest paths, whose size is linear in the dimension of the IAA. A Monte-Carlo simulation was performed to ascertain the detection of delay faults in paths that were not explicitly tested. Promising results were obtained.>

Test generation for combinational circuits, an NP-complete problem, shows its worst-case behavior while trying to generate tests for redundant faults and failing after an exhaustive search. The performance of an automatic test generator can be significantly improved by identifying redundancy via simple techniques which do not involve a search. The authors present a technique to identify redundant faults. This technique works dynamically during test generation, but is not based on a search process. It relies on test-covering relations among faults, which allow identification of addition redundant faults after the test generator fails to generate a test for a target fault. This technique has been implemented in AT&T's Testpilot test generation system and has shown a reduction of up to 32% in the number of backtracks in test generation runs.>

The authors describe a number of heuristic algorithms to compact a set of test sequences generated by a sequential circuit automatic test pattern generator (ATPG). A model has been developed and analyzed which shows that finding the optimal solution has an exponential worst-case complexity. To achieve an acceptable run time, some heuristics have been developed that yield good suboptimal solutions in a very short time. Three heuristic algorithms were developed. These algorithms were implemented in C and lex and applied to several of the ISCAS-89 benchmark sequential circuits. They reduce the test length by 17%-63% with a very small time overhead, while having little effect on the original fault overage.>

The full-scan and the nonscan versions of a circuit This paper presents a new algorithm for selecting the best flip-flops to scan for achieving maximum fault coverage in a partial-scan circuit. The algorithm, called PASCAL (PArtial Scan AnaLysis), ranks the flip-flops based on their contribution to the fault coverage. The results of PASCAL provide a global view of the entire partial-scan design spectrum (from no scan to full scan), and allow the designer to estimate the fault coverage achievable with any number of scanned flip-flops and to select the minimal subset of flip-flops to scan for obtaining a desired fault coverage. The number of scanned flip-flops can be reduced by taking into account faults detected by functional tests.

The performance of an automatic test generator can be significantly improved by identifying redundancy by simple techniques which do not involve search. The authors present a technique for identifying redundant faults. This technique works dynamically during test generation but is not based on a search process. It exploits dominance and test-covering relations among faults, which allow identification of additional redundant faults after the test generator fails to generate a test for a target fault. This technique has been implemented in AT&T's LTG (LAMP2 test generation) system and has shown up to 32% reduction in the number of backtracks in test generation runs.>

Currently available automatic test pattern generators (ATPGs) generate test sets that are nonoptimal in length. The authors describe novel heuristic techniques to reduce the length of the test set for a sequential circuit by compaction of the automatically generated patterns. Based on these techniques, a program has been written in C that achieved a 56%-73% reduction in the test length of a highly sequential circuit obtained from industry.>