Skip to main content
main-content

Über dieses Buch

Branch-and-bound search has been known for a long time and has been widely used in solving a variety of problems in computer-aided design (CAD) and many important optimization problems.
In many applications, the classic branch-and-bound search methods perform duplications of computations, or rely on the search decision trees which keep track of the branch-and-bound search processes. In CAD and many other technical fields, the computational cost of constructing branch-and-bound search decision trees in solving large scale problems is prohibitive and duplications of computations are intolerable. Efficient branch-and-bound methods are needed to deal with today's computational challenges. Efficient branch-and-bound methods must not duplicate computations.
Efficient Branch and Bound Search with Application to Computer-Aided Design describes an efficient branch-and-bound method for logic justification, which is fundamental to automatic test pattern generation (ATPG), redundancy identification, logic synthesis, minimization, verification, and other problems in CAD. The method is called justification equivalence, based on the observation that justification processes may share identical subsequent search decision sequences. With justification equivalence, duplication of computations is avoided in the dynamic branch-and-bound search process without using search decision trees.
Efficient Branch and Bound Search with Application to Computer-Aided Design consists of two parts. The first part, containing the first three chapters, provides the theoretical work. The second part deals with applications, particularly ATPG for sequential circuits.
This book is particularly useful to readers who are interested in the design and test of digital circuits.

Inhaltsverzeichnis

Frontmatter

Theory

Frontmatter

1. Introduction

Abstract
Branch-and-bound search is a general form of enumerative schemes for solving problems for which direct solution methods either do not exist or are inefficient. It is based on the fact that, in general, only a small number of the possible solutions need actually be enumerated. The remaining possible solutions are eliminated through the applications of bounds which reflect constraints. It can also be viewed as structured search in the space containing all feasible solutions in the sense that, in the worst case, all possible solutions have to be enumerated.
Xinghao Chen, Michael L. Bushnell

2. Justification Equivalence

Abstract
Justification in logic circuits is fundamental to many areas of very large scale integrated (VLSI) circuit design, such as test generation, logic synthesis, logic verification, and redundancy identification. It can be described as a decision-making search process traversing the decision spaces, which are defined by logic circuits, to find solutions satisfying the specified objectives. In general, justification in logic circuits belongs to the class of NP-complete problems, meaning that no polynomial time solution exists.
Xinghao Chen, Michael L. Bushnell

3. Justification in Finite State Space

Abstract
In this chapter, we expand the concept of justification equivalence, as introduced in Chapter 2, to the finite state space. We present a method that dynamically gathers justification information while traversing the finite state space. The learned information is then used in subsequent justifications to avoid previously-explored state justification decisions.
Xinghao Chen, Michael L. Bushnell

Applications

Frontmatter

4. Sequential Circuit Test Generation

Abstract
In general, digital circuits with storage capability, or “memory”, are called sequential circuits, while digital circuits without storage capability are called combinational circuits. The outputs of a sequential circuit not only depend on the current inputs, but also depend on the past conditions, or “history”, of the inputs. Sequential circuits are also called finite state machines (FSM’s).
Xinghao Chen, Michael L. Bushnell

5. Fault Effects

Abstract
We presented theorems on justification equivalence in Chapters 2 and 3 for circuits assumed to have no physical defects. These circuits are called fault-free circuits. Testing of integrated circuits requires consideration of cases where we assume that the circuit-under-test has defects.
Xinghao Chen, Michael L. Bushnell

6. The Sest Algorithm

Abstract
In this chapter, we describe the SEST automatic test pattern generation (ATPG) algorithm, which applies the justification equivalence theorems discussed in Chapters 2 and 3. It is important to note that the application of the justification equivalence concept is not limited to test generation. However, applications in different areas may require separate formulations. Readers who are new to sequential circuit ATPG are advised to examine Chapter 4.
Xinghao Chen, Michael L. Bushnell

7. Experimental Results

Abstract
Consider a general search problem. The entire decision space of the search process is characterized into solution regions which direct the search process toward a solution, and non-solution regions which direct the search process away from solutions. Conceivably, it will be a recommended policy to avoid non-solution regions of the decision space during the search process.
Xinghao Chen, Michael L. Bushnell

8. Redundancy Identification

Abstract
Redundancy in a digital circuit means that the circuit can be simplified by removing at least one logic gate or gate input without affecting the function of the circuit [3, 85]. Redundancy with respect to a stuck-at fault means that the presence of the stuck-at fault does not alter the input-output behavior of the circuit.
Xinghao Chen, Michael L. Bushnell

9. Logic Verification

Abstract
Logic verification refers to verifying the correctness of a logic design before fabrication or even before any detailed physical design. It is motivated by the fact that changes and modifications in a large circuit are expensive, difficult and time-consuming. Therefore, throughout the design process, verification is done at various design levels and stages to ensure that every step in the design meets its objectives and requirements. Logic verification is usually employed at the end of the logic design phase.
Xinghao Chen, Michael L. Bushnell

10. Conclusion

Abstract
The efficient branch-and-bound search method we have described in this book has the following advantages:
  • It can guarantee absolutely no duplication of computation in a branch-and-bound search.
  • It does not depend on a specific search decision tree.
  • It can be used to augment various existing search heuristics.
Xinghao Chen, Michael L. Bushnell

Backmatter

Weitere Informationen