Algorithmic and Knowledge-based CAD for VLSI
2: Department of Electrical Engineering, University of Newcastle upon Tyne, Newcastle, UK
This book covers algorithms and applications of techniques from the artificial intelligence community in CAD for VLSI.
Inspec keywords: analogue integrated circuits; expert systems; discrete cosine transforms; simulated annealing; application specific integrated circuits; design for testability; digital integrated circuits; high level synthesis; automatic test pattern generation; VLSI; integrated circuit testing; integrated circuit design
Other keywords: AI technique; digital circuit design; simulated annealing; digital ASIC; HIT; fault augmented function; knowledge based expert system; knowledge based-CAD; algorithmic CAD; transformational synthesis; macrotest; automatic test pattern generation; design for testability; high level synthesis technology; hierarchical integrated test methodology; knowledge based test strategy planning; VLSI testable-design technique; discrete cosine transform block
Subjects: Expert systems and other AI software and techniques; Integral transforms; Computer-aided circuit analysis and design; Optimisation techniques; Optimisation techniques; Hardware-software codesign; Integral transforms; Semiconductor integrated circuit design, layout, modelling and testing; Electronic engineering computing
- Book DOI: 10.1049/PBCS004E
- Chapter DOI: 10.1049/PBCS004E
- ISBN: 9780863412677
- e-ISBN: 9781849193580
- Page count: 288
- Format: PDF
-
Front Matter
- + Show details - Hide details
-
p.
(1)
-
1 Expert assistance in digital circuit design
- + Show details - Hide details
-
p.
1
–23
(23)
This chapter presents the details of an expert system for designing digital systems, called the design assistant (DA). The design of digital hardware is an ill-structured problem and the use of intelligent techniques helps in automating the design process of such problems. There are several advantages of using this approach such as simplicity, expandability, ease of use, explanation of reasoning. It is hoped that the design techniques used in this system can be expanded to the design of VLSI systems.
-
2 Use of a theorem prover for transformational synthesis
- + Show details - Hide details
-
p.
24
–46
(23)
The use of formal methods in VLSI design is currently a very active research area. This requires the specification of the behaviour of a hardware design in a formal, mathematically rigorous manner. Such specifications can subsequently be manipulated by proof systems (usually called 'proof assistants' or 'theorem provers') to prove the equivalence of hierarchical or temporal properties of hardware designs. We describe a prototype tool which integrates a theorem prover into the design environment in such a way as to ensure functional and trans formational correctness at all times. The system is driven from a hardware description language developed at Newcastle called STRICT, and it is interactive. Our aim in developing this tool is to make it easier for the designer to ensure correctness of the final implementation, without losing the benefit of his skill and experience.
-
3 An overview of high level synthesis technologies for digital ASICs
- + Show details - Hide details
-
p.
47
–74
(28)
In this chapter a number of techniques for dealing with high level synthesis tasks are discussed. Unfortunately, the interaction between many of these tasks means that they need to be integrated vertically and solved in a limited design-specific way. Alternatively the tasks can be organised functionally as described above and run in an iterative fashion. This leads to the toolbox concept. Tool operations can be sequenced depending on the type of design. Sequencing can be performed manually or by an expert system.
-
4 Simulated annealing based synthesis of fast discrete cosine transform blocks
- + Show details - Hide details
-
p.
75
–93
(19)
This chapter describes CAD techniques capable of synthesising Fast Discrete Cosine Transform (FDCT) Blocks from behavioural, or algorithmic, specifications. We introduce SAVAGE (a Simulated Annealing based VLSI Architecture GEnerator), a software tool developed under the auspices of the Silicon Architectures Research Initiative (S ARI(Grant, 1990)) hosted at the University of Edinburgh. SAVAGE is capable of taking a data-flow description of an input algorithm, and applying a number of synthesis steps, or transformations, to produce a hardware netlist of a datapath. The netlist description is then passed to logic synthesis and layout tools to complete the route to silicon. These application specific synthesis steps are controlled by the computational technique known as simulated annealing. This chapter reviews the design process, from the initial high-level description of the FDCT, through the various synthesis transformations, and presents a set of test results illustrating the flexibility of the SAVAGE software. Finally, some extensions to the prototype SAVAGE system are described.
-
5 Knowledge based expert systems in testing and design for testability - an overview
- + Show details - Hide details
-
p.
94
–121
(28)
The application of knowledge based systems to the design of VLSI circuits will have the greatest impact in assisting the engineer with aspects of the design which are not amenable to automation using algorithmic techniques. Test pattern generation and design for testability fall into this category. A further advantage offered by knowledge based systems is that they can 'acquire' knowledge for future use and hence improve their capabilities and the 'quality' of the solutions provided. Although expert systems offer many potential benefits a major barrier to their use is the high develop ments costs. These start-up costs can be offset to some extent by using expert system shells or by using logic programming languages e.g. Prolog, so that prototype systems can be produced relatively quickly and the required knowledge bases built up incrementally. In retrospect start-up costs were considered to be an obstacle to the development of conven tional CAD programs. These are now widely used and development costs, although still considerable, are accepted primarily because these tools have been shown to provide tangible benefits to the designer. Consequent ly, if development costs of expert systems are to be accepted these tools must demonstrate that they can also provided tangible benefits to the designer.
-
6 Knowledge based test strategy planning
- + Show details - Hide details
-
p.
122
–141
(20)
This chapter has described some current knowledge based systems to aid design for testability, and described research in this area taking place at Brunei University. It has also attempted to highlight specific problem areas in test strategy planning, and presented an economics based approach to the problem of test strategy evaluation. The system described here was constructed as a research tool, but the concepts and test strategy planning methods were used in a current ESPRIT project for gate array test strategy planning, which is now under industrial evaluation (Dislis et al, 1991). The basis of the test strategy planner is the cost modelling employed, which the authors believe is a reliable method for making realistic comparisons of design for test methodologies. The results of the economics based planning have so far agreed with test experts' approaches.
-
7 HIT: a hierarchical integrated test methodology
- + Show details - Hide details
-
p.
142
–162
(21)
The general trend in industry is to get designs right first time. This philosophy needs to be extended to testing. HIT, currently being developed at the University of Oxford, falls under a new breed of test generating systems that will ensure that this is achieved. It not only provides efficient test generation but can also guide the designer through various design for test modifications. Any extra circuitry is targetted at the correct location thereby reducing cost, hardware overhead and the effect on circuit performance. It must not be assumed that the modifications suggested by HIT are the only ones or that they are necessarily the best. The idea of designing such a system is to try and create a dialogue between the designer and the test expert. By giving the designer expert knowledge about the areas of his design where testing would be difficult he is always in a better position to suggest alternative solutions. Also conferring with the designer is more important than using arbitrary measures to improve the testability of a circuit. Finally, even though the designer is in the best position to modify the design to improve testability, having a system such as HIT to guide him/her will reduce the effort required and in most cases improve the final product.
-
8 Use of fault augmented functions for automatic test pattern generation
- + Show details - Hide details
-
p.
163
–179
(17)
Techniques for the automatic generation of test patterns for digital circuits may be classified into four main areas; 1) random pattern generation... random input sequences which may be exhaustive, pseudo-exhaustive or used in conjunction with fault simulation tools to assess fault coverage. 2) heuristics ... these include checkerboard patterns and walking ones and zeros as well as functional tests; for automatic generation of such sequences there is the implication of some kind of expert system and the need for simulation to assess fault coverage. 3) path sensitisation... this encompasses the many variations on the D-algorithm and is probably the most widely used algorithmic technique. 4) algebraic techniques. It is with the last that this chapter is concerned.
-
9 Macro-test: a VLSI testable-design technique
- + Show details - Hide details
-
p.
180
–200
(21)
Designing testable VLSI devices presents a continuous challenge to VLSI full-custom designers. Design-for-testability (DFT) has emerged as an integral part of the design process, but the integration can only be achieved if the right tools are in place. In this chapter we discuss the concepts of macro-testability and present the underlying tools to allow designers of VLSI devices to implement the testability structures required by macro-testability. These tools are now in use within Philips and the chapter concludes with comment on the practical application of such techniques.
-
10 An expert systems approach to analogue VLSI layout
- + Show details - Hide details
-
p.
201
–244
(44)
The production of computer-aided design tools and environments for analogue VLSI circuit layout has proved very much more difficult than in the digital domain. The principal reason for this is that analogue circuit design involves the accommodation of many, often conflicting, practical constraints (Allen, 1986). Typical of these constraints are the optimum placement of circuit components, layout of large transistors, routing of interconnection channels noting the importance of avoiding signal cross talk, and the minimisation of parasitics which might affect circuit performance (Haskard and May, 1988, Kimble et al, 1985 and Serhan, 1985). In addition, the design of analogue circuits requires precision modelling of individual components and extensive simulation to verify the desired performance (Rijmenants, 1988). The problems associated with analogue VLSI layout techniques are reasonably well understood by experienced analogue circuit designers and it is widely accepted that these problems cannot be solved purely algorithmically. To produce a sophisticated analogue VLSI layout design tool which will enable these demanding multiple-constraint problems to be solved effectively, requires the efficient incorporation of design expertise as an integral part of the automatic analogue VLSI layout design tool. The purpose of this work is essentially to make a contribution towards meeting these demands, and to provide a greater understanding of typical expert layout design rules and how they should be incorporated within the Expert Analogue Layout System (EALS).
-
11 Guaranteeing optimality in a gridless router using AI techniques
- + Show details - Hide details
-
p.
245
–268
(24)
CAD tools to support full-custom integrated circuit design may either provide a fully-automated 'silicon compiler' or a more interactive 'design assistant'. This approach can provide the designer with greater control whilst providing CAD tools to free him from low-level tasks such as detailed layout. The design flow within such a design assistant suite consists of three major phases: floor planning, symbolic cell design and chip assembly.
-
Back Matter
- + Show details - Hide details
-
p.
269
(1)