TIES: A testability increase expert system for VLSI design

JOURNALOF ELECTRONICTESTING:Theoryand Applications,6, 203-217 (1995) @ 1995KlfiwerAcademicPublishers,Boston. Manufacturedin The Netherlands.

TIES: A Testability Increase Expert System for VLSI Design G. BUONANNO, E FUMMI AND D. SCIUTO Dipartimento di Elettronica e InJormazione, Politecnico di Milano, Italy

ReceivedMarch9, 1993;RevisedAugust 15, 1994 Editor: A.R Ambler

Abstract. TIES is a knowledge based system that advises the ICs designer on the best modifications to perform on a circuit with testability problems, while satisfying design constraints defined by the user. The proposed approach differs from previous papers for three main reasons. The DfT techniques are applied only to critical areas of the circuit which are identified by means of a testability measure. A powerful description of design for testability techniques in the knowledge base is adopted. Moreover, a new decision scheme for the comparison among different implementations is proposed. Keywords: 1

design for testability techniques, testable design, DfT advisor, testability analysis

Introduction

Many design for testability techniques have been proposed during the last ten years and many companies have forced their designers to use structured Design for Testability techniques such as scan path, LSSD, Scan Set Logic or Built-In Self Test. A solution to the testability problem is to face it in the earliest phases of the design flow by orienting the VLSI design methodology to the production of testable designs. This approach offers several returns on investment in terms of diagnostics and self-testing capabilities besides an easy test pattern generation. Nevertheless design for testability techniques have two main drawbacks: the increase in device size and the need of accurately training designers on new design techniques. Integrated circuit design methodology is moving from gate level up to RTL level and module level; in other words it is moving from the current bottom-up techniques to an actual top-down design strategy. This change leads indirectly to a good opportunity of changing test approaches too. Designing with a top-down methodology the designer no longer uses logic gates as elementary modules, but behavioral descriptions of complex macro-cells (such as ROMs, RAMs, registers, counters, VHDL entities, etc.) are adopted as basic design elements. Even if the gate-level structure of these cells has been designed keeping in mind the testability problem, the designer, at the end of his work,

will obtain a circuit which is composed of several fully testable modules, but not necessarily testable itself. Design for Testability (DIT) techniques are becoming necessary to overcome such a problem. However, application of these techniques is a difficult task since the great number of different proposals appeared in literature [1] and the different causes of untestability make the choice of the most suitable technique very complex. These causes explain why such techniques are not regularly used in the industrial environment where designers try to optimize the classical performance parameters of VLSI chips (e.g. area and performances) without considering the test issue. Generally, after the design has been completed, the test engineer must solve the problem of test pattern generation on very complex and untestable structures. Even the last generation of synthesis tools [2, 3], that guarantee the application of DfT techniques to single blocks, cannot guarantee that the entire circuit will be easily testable. Furthermore, even an expert DtT designer will be doubtful on which DfT technique represents the optimal solution for a given problem due to both the great number of different techniques available and to the intrinsic complexity of their application to a given design. The effort required to correctly analyze testability and apply such techniques can take the designer off its main job of designing the circuit meeting its functional specifications. Additionally, an industrial design center should define a unique policy for design for

204

Buonanno,Fummi and Sciuto

testability, hence it becomes necessary to maintain all designers up to date on the new techniques, a difficult and costly task since this is a very active research field. Finally, every design for testability technique must be known to the automatic test pattern generator in order to make test pattern generation and therefore test application more efficient by exploiting all features provided by any DtT technique. Hence an interface is needed which provides the documentation on the testability characteristics of each design for testing purposes. These reasons have led to the requirement, derived from an industrial environment (Italtel), of a tool that could help in avoiding the bottleneck at the end of the design flow of transforming optimized but untestable devices into testable" ones, and that could also help in transfen-ing design for testability knowledge to the designers. This is why TIES has been defined and prototyped, and it is now used by a team of designers to verify its usefulness and its shortcomings. The paper presents the main features of TIES. Next section reviews the most important literature results on the subject, in order to underline the improvements implemented in TIES. Then, section three presents the strategy used by TIES to modify a circuit with testability problems and such a methodology is compared, step by step, with previous approaches. Finally section four presents part of an industrial application example, by showing how TIES works on its testability problems.

2

Background on Expert Systems for Design for Testability

Testing problems seem to match most of the criteria for a successful implementation of an expert system. Knowledge based systems technology has been applied to a large number of testing related problems, in particular to test generation, hardware diagnosis and, more recently, design for testability [4]. Two classes of approaches can be identified in literature in the design of tools that support the use of design for testability techniques: the approaches aiming at verifying the correct application of DtT techniques into a design, and the approaches whose goal is to automatically provide a testable design from an untestable or a difficult to test one. Let us briefly recall some representative contributions in both classes. In [5], a design rule checker for a subset of the LSSD design for testability technique has been presented. If any violation is detected the tool proposes the appropriate modifications to the portions of the circuit that

do not satisfy the DIT rules. Other approaches, similar to [5], are reported in [6] and [7], but, in the most recent years, this strategy has been abandoned. The second class of application of heuristic techniques to design for testability is represented by the automatic design for testability systems, to which our approach belongs. Probably the most representative approach to such a problem is TDES [8], a knowledge based automatic design for testability system that takes as input the register transfer level description of the circuit and chooses for each design the appropriate testable design methodology in order to derive a testable synthesis of the design. A heuristic approach is used to partition a circuit into a number of testable structures called kernels. Rules are introduced for applying testable design methodologies to these kernels and for evaluating the various solutions through the combination of weighted normalized measures. More recently, a testability insertion guidance expert system (TIGER) has been presented [9], which includes most of the concepts introduced in TDES. Specifically, this system identifies testability problems early in the design cycle, formulates test strategies for the design, does "what if" exploration of design for testability solutions, plans the invocation of gate-level test tools on design partitions, and develops a solution to the test problem that satisfies the design goals and constraints. Further interesting contributions may be found in other papers. EVEREST, presented in [10], uses a cost function that selects the different D f r techniques in relation to the final project cost. This idea is really interesting, but the problem of identifying and tuning all factors composing the final cost is very hard. Another important analysis has been implemented in DfFExpert [11] which partitions all blocks, composing the circuit, into process and transport elements. The latter ones transfer data without modifications and represent an easier testability problem. DftExpert tries also to connect the scan registers in an optimal way. In [ 12], a feasibility study is presented in order to develop a system that helps the user to explore different circuit modifications, enclosed between a minimal test length and a minimal area overhead. The different solutions are explored via a branch and bound algorithm. The CRETE environment [13] is used at the University of Southern California to partition circuits in order to make test generation easier and to reduce the number of test vectors. CRETE works by clustering logic gates into disjoint partitions referred to as clouds; in a following step, a specific testable design methodology such as scan-path or BIST is applied to every cloud.

TIES: A Testability Increase Expert System for VLSI Design For instance, SIESTA [ 14] implements scan-path techniques, while the work presented in [15] describes a methodology for BIST insertion. Main drawback of the already published approaches is that no testability analysis is performed on the design and therefore each part of the circuit is always considered as potentially untestable and thus subject to the application of the most appropriate DfT technique. Hence the "testability" overhead will be quite high. Finally, the last few years have shown a great interest in the testability analysis and modification at the high levels of abstraction of the design [16, 17, 18, 19]. When high-level synthesis tools will be well assessed in industrial design flows, this will probably be the most suitable approach. On the contrary, the analysis and modification for testability at the register transfer level, as described in this paper, is an immediately adopted strategy since it does not require any modifications to the adopted synthesis flow, but it can work in parallel with it.

This approach improves the circuit description used by TDES [8], and it is also better than the methodology used by TIGER [9], since TIES is able to go through the different hierarchical levels in order to find the most interesting circuit view to apply DfT techniques. The global strategy implemented in TIES is divided in the following sub-tasks: 9 Testability analysis: the circuit must be analyzed to

9

9 9

3

TIES Approach

Let us now analyze the steps of the proposed strategy for testability increment in order to underline what TIES inherits from the previous works and which are the new features introduced. The expert system requires a register transfer level description of the circuit in which the function of each module is explicitly provided (e.g. combinational cell, register, counter ..) or it is unspecified. Hence a VHDL description or any description deriving from an highlevel synthesis tool can be used. The description can be based on a library of "standard cells" which can be aggregated into more complex structures by means of objects instantiation. This library is based on an object oriented representation of the cells that allows TIES to manage technology independent descriptions which inherit particular attributes only at the time they are really needed. It is then possible to obtain a hierarchical description of the circuit, whose different levels of abstraction can be accessed by the expert system depending on the requirements. The system can work also in case one or more complex cells are not yet completely specified. In this case some of the modification choices will be delayed until the designer can provide the necessary information to take a decision. This characteristics allows the system to verify potential testability of the interconnections among cells which are still identified as black boxes (and whose functionality is unknown).

205

9 9

9

identify those parts which are not easily testable in order to localize the critical areas where de'sign for testability techniques should be applied [18]. Problems reduction: heuristic criteria must be applied to reduce the original testability problems in order to discard all related problems. This step will not be performed if the modifications are applied indifferently on the overall design, starting from the primary inputs and working towards the observable outputs, as implemented in [8, 9] and others. Choice o f Dr1" techniques: the program determines which DfI" techniques can be applied and how. Cost evaluation: it estimates the best implementation based on the project constraints and on a set of parameters given by the user to influence the final cost. The circuit is locally modified and analyzed again for testability until critical areas are no longer found. Global optimization: all local modifications may be modified by connecting together scan registers and by deleting redundant testability resources to improve the global result. Explanation: all modifications have to be exhaustively explained to the user, since he has to learn and convince himself of the goodness of the decisions.

The proposed strategy is similar to the behavior of a human expert in the field of DIT; it is therefore characterized by the following advantages: It explains itself, so it offers more possibilities to control the results since it reasons in the same way as humans; It allows analysis and modifications only to local areas of the circuit; ==~ Only the difficult testable areas are modified by using a testability measure of the circuit; ==~ It is possible to integrate different DfT techniques. This represents a fundamental feature in the case of a circuit made of different types of modules; in this situation, very frequent indeed, an easier test can be obtained if different DtT techniques, specific for the different modules, are applied together;

206

Buonanno, Fummi and Sciuto

Testability

from Synthesis

Tools

Analyzer

modified 'STC -

_j

yes

-

_

_

: -

,_ _ _V.

_

TIES

13o

i

NTC

i

-t . . . . yes ~ , . . . . .

" - i

'->: T_PG ...... ~

circuit

circuit critical

ports ~ '

yes

modified circuit

Fig. 1. Relationships between TIES and the analyzer.

It is possible to analyze circuits with an incomplete description or at different levels of abstraction; =~ The knowledge of the system can be easily extended. On the other hand it inherits some indeterminacy which cannot lead to the development of an exact algorithm. This implies that a knowledge based system appears to be the best choice for the implementation. Beside, the feedback and many heuristic steps can make critical the speed of the system and the accuracy of the results. The next paragraphs will discuss the innovative solutions which have been devised to solve these problems in TIES.

~[~SCA~_REG 1 ;Combinat@ ional Fig. 2. D f r technique applied only to a critical port.

3.1

Testability Analysis

TIES works in conjunction with an algorithmic program [18] that checks the testability problems of the circuit. The relationships between TIES and such an analyzer are explained in [20, 18] and graphically shown in Fig. 1. The reader is referred to [ 18] for more details on the advantages and drawback of the testability analyzer; for the comprehension of this paper it is only sufficient to know that such a tool is based on sufficient (STC) and necessary (NTC) testability conditions suitably developed [ 18]. By applying such conditions, the analyzer localizes the testability problems not to the cells but to one or more input and/or output ports of

the cells themselves (such ports are so called critical). This is in fact an advantage, since the correction strategy can be applied specifically to the untestable ports identified instead of the entire cell. This represents one of the innovative aspects of the proposed system since most of the other tools presented in literature [8, 9, 4, 17] work on a cell basis without discriminating on the type of testability problem that has to be solved, if any. Our strategy allows to reach simpler and less expensive testable designs from the point of view of added hardware resources for testability purposes. An example is shown in Fig. 2, in which the possibility of distinguishing among critical

TIES: A Testability Increase Expert System for VLSI Design 3.2

_L COUNTER

--~ SHIFT_REG] I COMBINATIONAL1 CELL ) Fig. 3.

Orderingproblemexample.

and not critical ports reduces the width of the scanregister. Hence, the expert system requires as input the list of critical cells associated with a pair constituted by the port identifier and the corresponding testability problem. Moreover, TIES and the analyzer can work at different hierarchical levels, so when TIES decomposes a cell into its components (whenever possible), the analyzer evaluates testability again to exactly localize the new critical ports.

C E L L 9'

Problems Reduction

TIES has to be able to discriminate among the different testability problems and simplify those problems that can be identified as related. Hence, the testability information in input can overestimate the number of testability problems into the design without affecting the final result. When the expert system is activated with a new design, a list of critical ceils is given as input. These cells are characterized by at least one input and/or output port with respectively controllability or observability problems. Different experiments have shown that the order in which the critical ports are analyzed to insert a D f r technique is important, since often some of the controllability and observability problems are related and it is likely that, by solving the most important problems (that must first be identified) some of the other testability problems are automatically solved as well. The order in which the cells are analyzed affects the final result by bounding the number of additional components added to the circuit to achieve a testable design. For instance let us consider the circuit in Fig. 3. If the controllability problem of the combinational cell is afforded before having analyzed the counter problem, a new shift register will be added to solve this problem, without exploiting the internal register of the counter by means of the "ad-hoc technique" for the counter (see next section). Hence a superfluous register is added in this case but not in the case the critical port of the counter were analyzed first. Figure 4 shows a different aspect of the ordering -problem: the controllability problem of the second cell depends, either partially or totally, of the first cell which is difficult to control also. Hence it would be more convenient to work on the first cell and then verify if

C E L

/

L

i

i Fig. 4.

207

2

Orderingproblemexample.

208

Buonanno, Fummi and Sciuto Not Comptex Cdtlcel Cell Known Function

Unknown Function

Same Problem

Different Problem

GIVE UP

SELECT

gate

gate

GIVE UP

SELECT

gate

gate

Not CompleXCell C~

SELECT Known Function

Unknown Function

gate

SELECT gate

Complex Critical Ceil

Known Function

SELECT gate or DECOMPOSE! cell

Different Problem

GIVE UP

SELECT

gate

gate

Unknown DECOMPOSE DECOMPOSE Function cell ceil i

lex

SELECT gate or DECOMPOSE ~ - U cell

Same Problem

Critical cell D e

rT

,•Not

critical cell

o

Fig. 5. Decision table.

the second cell is still characterized by controllability problems. Therefore, the choice of the core set of critical ports and the order in which they must be analyzed by the other modules represent a difficult, but of the utmost importance, problem. TIES adopts a solution based on the following concepts: 9 Transport ceils are analyzed before computing cells, since the transport cells are often used, and therefore verified, during the test of the computing cells [11]. 9 Partitioning techniques can be used to reduce the complexity of the testability problem. The circuit can be partitioned into independent sub-circuits based on the type of the cell and on its style to apply homogeneous DtT techniques on each subset of critical cells [9]. 9 There are classes of critical cells, such as the combinational cells constituted by random logic or PLAs, ROMs, whose testability problems are always primary problems, i.e. to be solved they need anyhow the application of the appropriate DfI" technique. 9 If a cell is characterized by a problem on a port, e.g. a controllability problem, and the preceding or succeeding cell in the data flow is characterized by similar problem, then it is better to afford the problem

of the other cell first. If the problems were related, then they will be solved simultaneously, otherwise at least one of them will have been solved, and the other will be solved in a following phase. 9 Complex cells can be decomposed into their constituting elements only if the function of the complex cell is unknown (the cell does not belong to the library of standard cells for which the test patterns have already been developed). This rule has been introduced to simplify the analysis: in fact, if the function of the cell is known, the cell can be treated as a black box and its analysis can be completed, without decomposing it into elements which should have been considered separately for testability purposes. In these cases, TIES is however able to apply "ad-hoc techniques" that solve the testability problem of a library cell without decomposing it. The system will decide if it has to select a critical port to apply a DfT technique, or if the testability problem of such a port can be automatically solved by solving the related problems, or if the critical cell is a complex cell and it will advise on the opportunity of decomposing the cell into its components. These decisions are summarized in the decision tables presented in Fig. 5.

TIES: A Testability Increase Expert System for VLSI Design

f

C O M B I N A T I O N A L

[4, 7, 8, 9, 11, 12]. All these methodologies are based on the Testable Design Methodology (TDM) concept explained in [8]. But all these papers take for granted that all DfT techniques can be represented by means of a topological description; for example, Fig. 6 shows the topological representation of a BIST technique. However such a description corresponds to a simplification of the model of the DfT techniques and presents two problems:

C E L L

Fig. 6. BISTtopologicaldescription. This approach, starting from the basic ideas presented in [9] and [11], improves them, since it uses a set of decision rules and it works on the critical ports instead of the entire cell; the ability to explore the different hierarchical levels of the circuit distinguishes furthermore such an approach. Moreover, TIES improves the work presented in [17], since it uses a testability measure to begin the analysis and not only a set of rules. This strategy allows TIES also to select the real critical parts of the circuit and therefore there is no need to modify the entire circuit as proposed in [9, 12, 13]. At the end of these reductions, TIES produces an ordered subset of the initial critical ports characterized by unrelated testability problems. There is a high probability that such DfT techniques will allow to solve also the testability problems of the critical ports discarded in the reduction process.

3.3

Choice of DfT Techniques

A number of methodologies for the automatic insertion of DfI" techniques have been proposed in literature

9 all possible facets of the DfT techniques cannot be represented, 9 a critical cell is considered in its entirety and it is not possible to distinguish between critical and not critical ports. In Fig. 7 different topological descriptions of a Scan Path are presented; these techniques can be applied to cells with controllability problems only (in this case the registers are connected only with the input ports), or with observability problems only (output registers), or both, or connected with fewer ports. It is evident that the number of possible combinations becomes too large to manage. For this reason the topological representation of the connections between the added registers is not possible whereas a rule based representation is needed. On the other hand the topological description is easy to use, as well as easy to describe and in some cases it allows to completely represent some DfI" techniques; for example in the case of a counter which becomes testable after the transformation of its internal register into a shift register, the topological description can completely represent all information necessary for the implementation of the technique. Another problem for the application of the DtT techniques is related to the different hierarchical levels in

COMBINATIONAL CELL

COMBINATIONAL CELL

209

COMBINATIONAL CELL

COMBINATIONAL CELL

COMBINATIONAL CELL

Fig. Z SCAN-PATHtopologicaldescription.

210

Buonanno, Fummi and Sciuto

@

9

@

Fig. 8. Differentialpulse code modulator.

which the different parts of the design are described. Consider for instance the differential pulse code modulator shown in Fig. 8. The quantizer represents a complex cell whose function is unknown to the system. Thus, the system should have the opportunity to explode this celt into its components in order to correctly apply the DfT techniques by exploiting all hardware resources already present in the circuit. Therefore the hierarchy can be considered as another D f r technique, since it allows to solve all situations in which the system does not have the appropriate knowledge for the corresponding design abstraction level. The system proposed in this paper will not loose the advantages of the descriptions identified above, by using a mixed representation based on: 9 topology; 9 rules; 9 hierarchy. A topological description of a DfT technique consists of two parts:

{premises) specification of the characteristics of the cell to which the system can apply the technique, e.g. a combinational cell rather than a complex cell. (actions} list of modifications that must be performed on the circuit in order to correctly apply the technique. The topology representation has been found useful to describe a limited family of DfT techniques named "ad-hoe techniques", that are useful to modify complex cells without exploding them into their components. Such a strategy speeds up considerably the Dfl" techniques application process, since TIES can choose the better D f r technique without exploring a lower hierarchical level and needing a further testability analysis. An application example is presented to show how

technique SHIFT-COUNTER problem C premises core

node = $CORENAME type COMPLEX function COUNT not in SI endcore endpremises actions

core mode SHIFT in SI 1 endcore father node = $SI type SI mode SI out SI 1 endfather relations $SI.SI= $CORENAME.SI endrelations endactions endtechnique

Fig. 9. "Ad-hocDfT technique" example.

such description is treated by the system and what kind of advantages can derive from the application of such techniques. Figure 9 shows the description of the SHIFTCOUNTER technique which allows to make a testable counter by modifying its internal register into a shift register. The first part of the description labeled by (problem) specifies which class of problems (controllability "C", observability "O" or both) can be solved by applying this technique. In the (premises) part of the description, the variable denoted by $CORENAME is assigned with the name of

TIES: A Testability Increase Expert System for VLSI Design the cell to which the technique is applied and the same variable is used in the (relation) part of the description to constrain the additional scan-in pin of the counter to be connected to the scan-in port. This information is then used as follows:

(premises) field is checked first against the conditions expressed in the core: if such conditions are verified then the technique is applicable to the ports of the current critical cell. (problem) field is inspected: if such a value con'esponds to the problem associated with the critical port under examination, the actions necessary (specified in the section (actions) of the description) to apply the ad-hoc design for testability technique to the critical port are selected. For example if the technique solves both the controllability and observability problem but the critical port is characterized by only one of such problems, if the problem corresponds to a controllability problem, then the set of actions that must be selected belongs to the field {fathers), while if the problem corresponds to an observability problem the set of actions to be considered belongs to the field (sons) of the section (actions) (not presented in this example). (actions) this set of actions is then executed by adding components or modifying the existing ones. (relations) the graph is modified according to the information specified in this section. The user can easily add or modify such techniques by describing them in the given format, therefore increasing the system knowledge on design for testability. The description based on rules allows to represent all exceptions to the other D f r techniques; for example a subset of rules for the activation of the BIST [1] technique is the following: (if)

TYPE (current_cell) = COMBINATIONAL (and) STYLE (current_cell) = RANDOM (and) CONTROLLABILITY (is) (in} PROBLEMS (current_cell) (and) SIZE (critic_input_port) >> SIZE (not_critic_input_port)

The knowledge base includes many such rules that allows TIES to activate and to implement any DtT technique and also they are used to jointly apply more techniques. Finally, the decomposition technique of a complex cell, which allows to traverse the hierarchy down to

211

the lower levels of the design description, is activated by the following rule:

(if)

IS_NOT_SELECTED_TECHNIQUE (and) TYPE(current_cell) = COMPLEX (and) FUNCTION(currenLcell) = UNKNOWN (and) IS_PRESENTJHE_SUBCIRCUIT (current_cell)

This rule shows that the complex cells with an unknown function may be decomposed if there are no appropriate D f f techniques, otherwise, for the complex cell with a known function (see as black-boxes), "ad-hoc techniques" are available. Hence, TIES uses a mixed mode to represent the different DfT techniques, which unifies the approaches based on topology [9, 12, 13] and the approaches based on rules [6, 7] and uses the knowledge of"ad-hoc techniques" that can be easily increased. Furthermore, such an approach is applicable to all different hierarchical levels in which a circuit is described.

3.4 Cost Evaluation The alternative implementations, that can be realized using the different DfT techniques which solve a testability problem, have to be compared. TIES uses some figures of merit to decide which is the best implementation, such as: area increase, number of added pins, test time and degradation of the circuit performances. All previous approaches, based on TDES [8], use a more or less sophisticated cost function that adds all such parameters into a global cost. This method (iliustrated in [9, 10, 11]) is characterized by an important drawback: the different parameter values, that are added weighted by their associated priority, are characterized by very different numerical ranges. Hence it is mandatory to define a normalization factor, associated with each parameter, which allows the system to correctly take into account each parameter in the sum. The normalization factors depend on the type of design and have to be tuned for any new design. Not even the approach presented in [12] solves this problem, since the analysis of the implementation alternatives is performed only at the extremity of the solution space: minimal area overhead versus minimal test time. However, TIES introduces a new decision technique by comparing only homogeneous quantities. For instance, given a set of alternative implementations Ai (1 < i < N, total number of alternatives), it is possible

212

Buonanno, Fummi and Sciuto

to compute the values vi, j (1 < j < P, number of different parameters) associated with any parameter composing the cost (cost(Ai)). Given the maximum value C of all alternatives, as computed during the analysis, the different parameters values Vi, j c a n be ordered between the maximum and the minimum value and can be scaled inside the cost range (between 0 and C) associating with each value vi,j the corresponding scaled value mi,j such that 0 _< mi,j .

ENOR_7

Fig. I0. Optimizationexample.

The possibility of adding unnecessary registers during the iterative analysis is however remote since the application of any new design for testability technique acts on the circuit modified by the application of the previous techniques and therefore exploitation of all useful structures already present into the circuit is performed. There are however cases in which the exploration of the paths between computing cells does not allow the identification of existing registers placed outside the data flow path. For instance, consider the example in Fig. t0, in which the exploration of the path starting from port DT2 of cell 13 does not find register REG5 and therefore the application of the DfI" technique introduces a new, redundant register, that will be eliminated by the optimizations. Furthermore, if the priority associated with the number of pins is high, then TIES tries to use the same pins to perform test on different cells by adding multiplexers or decoders. The benefit of such modifications can only be evaluated globally, at the end of the analysis and therefore only such a phase will be able to judge if the added structures are oversized with respect to their use. This task is performed by tracing inside the modified circuit the scan chains and by trying an optimal coupling by means of a greedy algorithm which finds an acceptable solution that is used by a branch and bound algorithm to prune the decision tree. It can therefore be concluded that this module tries to implement all those modifications that an expert would manually perform after the work of the expert system in order to minimize the overheads caused by the design for testability structures inserted.

TIES: A Testability Increase Expert System for VLSI Design

i

I

/

213

!

i

j

i

|

I'

Fig. 11. FONIAdevice.

3.6

Explanation

TIES interacts with the user in two different ways: | it builds an explanation file by connecting the data base of the performed modifications to the circuit with the reasons of such actions; 9 it provides information during the working session by putting together a limited set of sentences in natural language which describe the reasoning that has led to a particular decision. At any time during the working session, the user can ask for explanation, which is anyhow written into a file in which all information about the design for testability techniques applied and the modified cells is reported to ease the test generation process. Modification of this output information allows also TIES to produce an automatic interface to all those automatic test pattern generators which require the knowledge of the DtT structures in order to correctly exploit them during test generation [21].

4 Application Example Several Italtet benchmark circuits have been analyzed with the prototype. Here a partial example is reported: Fig. 11 shows part of the FONIA device scheme, while the file containing the critical ports, obtained from the testability analyzer, is shown graphically in Fig. 12. The expert system determines first if the critical cells provided as input constitute a set of unrelated problems. In this example the set of critical ports is already minimized and therefore the DfT techniques choice process is activated. The best DfT technique is chosen: the expert system starts considering the first port in the selected critical ports list, i.e. the CNT output port of the counter at node 11. Then, TIES computes the costs for the different D f r alternatives in order to take the optimal decision given the user constraints and priorities. The designer priorities on the circuit wj are the following: Area = 90%, Pin = 30%, Degradation = 90%, Test time = 90%. Beside, the user's constraints

214

Buonanno, Fummi and Sciuto

@

0

1~1 ]

~

00~8 I

11t

OOI11qT_8

| 6x

~

8x

-

-

? Fig. 12. FONIAcritical ports.

Table 1.

Parameter values.

Alter. Areaoverhead Pinsrequired Degradation Testtime At A2

50 50

2 2

l 0

5 5

which is therefore implemented. Then the analysis continues by considering the other critical ports. At the end of this phase, only three registers are strictly necessary, in fact cell 11: and 13: share the same register, while cell 10: and 15: share the second one.

are: max. area overhead 400 equivalent gates, max. scan length 25 and available added pins 4. The two alternatives have the parameter values shown in Table 1. Using the cost evaluation technique previously presented, all parameter values are scaled and the corresponding mi,j values are shown in Table 2 together with the final cost of every alternative (cost(Ai)). Clearly the best solution corresponds to the second alternative (Az), that represents a partial scan design,

The ports D6 and D T of the E N O R cell require also the addition of a register. All registers are then connected into a single scan chain to minimize the number of added pins to the circuit. The final solution is shown in Fig. 13. The results obtained could be improved if the "adhoc DtT technique" for counters is included into the knowledge base, since problems to cells 10: and 11: could be solved by transforming the internal register of the counter into a shift-register. Table 3 compares the cost of such "ad-hoc technique" with the previous

Table 2. Scaledvalues and total costs. Area overhead Alter. At A2

Pins r e q u k e d

Degradmion

Testtime

mi, 1

mi, 1 w 1

mi,2

mi;2 w2

mi,3

mi,3 w3

mi,4

mi, 4 W4

cost(Ai)

10 10

9 9

10 10

3 3

10 0

9 0

10 10

9 9

30 21

TIES: A Testability Increase Expert System for VLSI Design

:o o;l

215

I

i| FONIAmodifiedby scan-path.

Fig. 13.

Table 3.

"Ad-hoctechnique",scaled valuesand total costs. Area overhead Alter. A1 A2 A3

Pins required

Degradation

Test time

mi,1

mi, l ~ l

mi,2

m i,2 to2

mi,3

mi,3 to3

mi,4

mi,4 w4

cost( Ai )

10 10 2

9 9 1.8

10 10 5

3 3 1.5

10 0 0

9 0 0

10 10 to

9 9 9

30 21 12.3

analyzed alternatives applied to the CNT output port of the counter at node 11. Using "ad-hoc techniques", TIES arrives to a better global solution than the one previously described; in

fact a lower number of registers is added to the original circuit description, and the use of all available extra pins (4), produces a shorter and faster test sequence. The final circuit modifications are shown in Fig. 14.

216

Buonanno, Fummi and Sciuto

lnl

CO1J'/~_8

|

B

|

Fig, 14. FONIAmodifiedwith "ad-hocDfT technique".

5

Concluding Remarks

The aim of the prototype implementation of TIES is to prove the feasibility of the proposed methodology in an easy and fast way. Hence an expert shell has been used to develop the user interface and the inference mechanisms (backward and forward), while the rules modeling has been performed directly in Lisp. The resulting prototype is therefore an hybrid system which implements the knowledge through rules and relationships object-attribute-value, while the inference engine is based on forward and backward reasoning. The development of the prototype has been first carried out on a PC under the Personal Consulting Plus shell. Then, after proving the validity of the methodology, a software tool including testability analyzer and advisor is under development on Sun workstation into the ESB-96 expert shell environment [22]. The tool implemented

allows a test engineer to reduce the time of the definition of the best testable design which satisfies all design constraints from several hours to less than one hour. The innovative characteristics implemented in TIES can be summarized as follows: 9 A testability measure and a set of rules have been

used to localize the only parts of the circuit that are hardly testable. Furthermore, this analysis is performed through different hierarchical levels and it is focused on the critical ports instead of the entire cell. This strategy allows TIES to modify only the strictly necessary parts of the analyzed circuit. 9 DfT techniques knowledge has been represented using a mixed mode based on topology, rules, hierarchy and "ad-hoc techniques". This method allows TIES to consider all different aspects of any D f r technique. 9 Different implementations of the DfT techniques are

TIES: A Testability Increase Expert System for VLSI Design compared using a new cost function that does not need normalization factors. Such a method eliminates the problem of tuning the used comparison strategy in relation to different designs. 9 The final optimizations are performed by means of a branch and bound algorithm that finds the optimal solution according to the user's and project's constraints. 9 Learning of DfF techniques is achieved by the documentation provided by TIES for every decision taken.

Acknowledgments The authors would like to thank all designers and DfT experts working in the Italtel ICs R&D central laboratories for their contributions, in ideas and consultancy, to the development of TIES.

References 1. M. Abramovici, M.A. Breuer, and A.D. Friedman, Digital System Testing and Testable Design, Computer Science Press, 1990. 2. Mentor Graphics, Autologic Optimization Guide v.8.1, 1992. 3. Racal-Redac, Silcsyn VHDL Synthesis User's Manual, 1993, 4. M.A. Breuer, R. Gupta, R. Gupta, K.J. Lee, and J.C. Lien, "Knowledge Based Systems for Test and Diagnosis," in Knowledge Based Systems for Test and Diagnosis, G. Saucier, A. Ambler, M.A. Breuer eds., IFIP, North Holland, pp. 3-27, 1989. 5. EW. Horstmann, "A Knowledge-Based System Using Design for Testability Rules," Ptvc. 14th Fault Tolerant Computing Symposium, pp. 278-284, 1984. 6. K. Son, "Rule Based Testability Checker and Test Generator}' Proceedings International Test Conference, pp. 884-889, 1985. 7. E Camurati, R Gianoglio, R. Gianoglio, and R Prinetto, "ESTA: An Expert System for DFT Rule Verification," IEEE Transactions on ComputerAidedDesign, Vol. 7, No. 11, pp. 1172-1179, Nov. 1988. 8. M.S. Abadir and M.A. Breuer, "A Knowledge Based System for Designing Testable VLSI Chips," IEEE Design and Test of Computer, pp. 5648, Aug. 1985. 9. M.A. Abadir, "TIGER: Testability Insertion Guidance Expert System," Proceedings International Conference on Computer Aided Design, pp. 562-565, 1989, 10. I.D. Dear, C. Dislis, A.E Ambler, and J. Dick, "Economic Effects in Design and Test," IEEE Design & Test of Computer, Dec. 1991. 11. S. Bhawmik and R Palchandhuri, "An Expert System to Configure Global Design for Testability Structure in a VLSI Circuit," Microprocessors andMicrosystems, Vol. 13, No. 7, pp. 462472, Sep. 1989. 12. S. Lin, C.A. Njinda, and M.A, Breuer, "A Systematic Approach for Designing Testable VLS1 Circuits," Proceedings International Co1~ference on Computer Aided Design, pp. 496-499, 1991.

217

13. R. Gupta, R. Srinivasan, and M.A. Breuer, "Reorganizing Circuits to Aid Testability," IEEE Design & Test of Computers, Sept. 1991. 14. S. Narayanan, C. Njinda, R. Gupta, and M. Breuer, "SIESTA: a Multi-Facet Scan Design System," Proceedings International Test ConJerence, 1992. 15. D. Mukherjee, C. Njinda, and M.A. Breuer, "Synthesis of optimal 1-hot coded on-chip controllers for B1ST hardware," Pro-

ceedings International Conference on Computer Aided Design, pp. 236-239, April 1991. 16. I.C.H. Chen, C. Wu, and G. Saab, "BETA: Behavioral Testability Analysis," Proceedings International Conference on Computer Aided Design, pp. 202-205, 1991. 17. M. Kraak and R.H.J.M. Otten, "Tackling CoSt Optimization in Testable Design by Forward Inferencing," 1EEE Design & Test of Computers, pp. 252-257, Aug. 1992. 18. M. Bombana, G. Buonanno, P. Cavalloro, E Ferrandi, D. Sciuto, and G. Zaza, "ALADIN: A Multi-Level Testability Analyzer for VLSI System Design," IEEE Transaction on VLSI Systems, Vol. 2, No. 2, pp. 157-171, 1994. 19. I.C.H. Chen, T. Karnik, and G. Saab, "Structural and Behavioral Synthesis for Testability Techniques," IEEE Transactions

on Computer Aided Design of Integrated Circuits and Systems, Vol. 13, No. 6, pp. 777-785, June 1994. 20. G. Buonanno, A. Burri, E Fummi, and D.Sciuto, "An Approach to a Design for Testability Personal Consultant," Journal of Microprocessing and Microprogramming No. 30, Proceeding Euromicro'90, Amsterdam, Aug. 1990. 21. Racal-Redac, Intelligen 2.0 Reference Manual, 1992. 22. "ESB-96 User Guide," Siemens Plessey Electronic System Limited, 1990. Giacomo Buonanno received the Laura (cum laude) in Electronic Engineering in 1988 and the Ph.D. degree in Computer Science and Automation Engineering from Politecnico di Milano in 1992. He is currently a Research Assistant with the Dipartimento di Elettronica e Informazione of Politecnico di Milano. His current research interests are testability analysis and design for testability in complex VLSI circuits, formal languages for hardware specification and synthesis of multiple output CMOS gates. Franeo Fummi received the Laurea in Electronic Engineering in

1990 at the Politecnico di Milano and the Master in Hardware Engineering in 1991. Since 1992 is a Ph.D. student at the Dipartimento di Elettronica e Informazione of the Politecnico di Milano and he is currently concluding a thesis on the testable synthesis of VLSI systems. Other interests concern test generation and synthesis through different levels of abstraction. Donateila Sciuto received her Laurea in Electronic Engineering in

1984. She received her Ph.D. in Electrical and Computer Engineering in 1988 from University of Colorado, Boulder. She has been an assistant professor at the University of Brescia, Dipartimente di Elettronica per l'Automazione up to 1992. She is currently an Associate Professor at the Dipartimento di Elettronica e Informazione of the Politecnico di Milano, Italy. She is in the steering committee of the Italian section of the VHDL user group. Her research interests include VLSI synthesis and testing,VHDL system design and specification.