LEAP: A Learning Apprentice for VLSI Design

1. Step 1: Forming the Composed Specification from Rule RHS

The frrst step design rule from ensuring that the the original circuit m the process of inferring a ·general circuit a training example ts that of verification: function computed by the user 's circuit meets specification.

We can derive a description of the circuit's function from its structure by composing the functions of the submodules constituting the circuit, according to the configuration in which they are interconnected. For the user 's NOR-gate circuit, this composed specification is given as

(EQUALS ( ~A LVE Ou,.puL( I ) (NOT (OR (NOT (OR (VALUE lnputl(i)) (VALUE lnput2(i)))) (NOT (OR (VALUE lnput3(i)) (VALUE Input4(i)))) ) ) )

Note that , in general , the composed specification will be a syntactically roexpre48ed version of the original specification . For example, the above composed specification is not syntactically identical to the functional specifications in the training example, even though it does represent the same boolean function. This frequently occurs m VLSJ circuits in which, for example, functional specifications in terms of AND and OR boolean expressions are often implemented in terms of NAND and NOR gates.

2. Step 2: Verifying the Circuit Function

To verify the correctness of the user-suggested NOR-gate circuit, LEAP must show the equivalence between the composed specification· for this circuit and the original specification of the circuit being implemented . Thus, it seeks to verify that

(IMPLIES (composed-spec) (original-spec>) or in this case (IMPLIES (NOT (OR (NOT (OR (VALUE lnputl(i)) (VALUE lnput2(i)))) (NOT (OR (VALUE Input3(i)) (VALUE Input4(i)))))) (AND (OR (VALUE lnputl(i)) (VALUE Input2(i))) (OR (VALUE Input3(i)) (VALUE Input4(i)))))

LEAP verifies that the composed specification meets the original specification by determining a sequence of algebraic transformations which , when applied to the composed specification , will yield the original specification. Each transform has a precondition which describes the class of situations to which it can be applied , and a postcondition which specifies the result of the transformation. The two transforms that will be used for the current example in the circuit domain are given below.

De-Morgan 's ~aw Precondition: (NOT (OR ( bool - fnl ) <bool- fn2>)) Postcondition: (AND (NOT <bool-fnl>) (NOT <bool-fn2>)) Remove-Dou bie-N ega tion: Precondition: (NOT (NOT <bool-fn>)) Postcondition: (bool-fn>

Here "< bool-fn> " represents an arbitrary boolean function. Shown below is the verification as a sequence of transformations.

VERIFICATION

(NOT (OR (NOT (OR (VALUE Inputl(i)) (VALUE Input2(i)))) (NOT (OR (VALUE Input3(i)) (VALUE Input4(i)))))) De-Morgan (AND (NOT (NOT (OR (VALUE Inputl(i)) (VALUE Input2(i))))) (NOT (NOT (OR (VALUE Input3(i)) (VALUE Input4(i)))))) Remove-Double-Negation (AND (OR (VALUE Inputl(i)) (VALUE Input2(i))) (NOT (NOT (OR (VALUE Input3(i)) (VALUE Input4(i)))))) Remove-Double-Negation (AND (OR (VALUE Inputl(i)) (VALUE Input2(i))) (OR (VALUE Input3(i)) (VALUE Input4(i))))

1. Step S: Determining the Generalized Composed Specification

Given the verification tree shown above, the next step is to determine the general class of expressions for which this sequence of verification steps will correctly apply . This is essentially a problem of viewing the transformation sequence as a r rr ·· · I·I'Pd l ·l ·lit< ' 4,j ,, , I· ·· r ; . llol ; !-'. · !r · lll" "v "tl~ 1·rp. ,. ,,j,· r··n:-. f,,r lh!' ovrra1ur ~Pquenrf' LEAl' i1c,·omplishe~ rhr:-- h~ back­ I'"'J.>agat .ing the precondition of each transform 1n t.he sequence, to drtermine the necessary <"onditions on the starting expression . This process is described in great.er detail in ·l2 j. The sequence shown below illustrates this back-propagation , and indicates the resulting generalization of the composed specification.

COMPUTING THE

GENERALIZED COMPOSED SPECIFICATION

(AND (OR (VALUE Inputl(i))

(VALUE Input2(i)))

(OR (VALUE Input3(i))

(VALUE Input4(i))))

Remove-Double-Neg (AND (OR (VALUE Inputl(i)) (VALUE Input2(i))) (NOT (NOT <bool-fnl>))) Remove-Double-Neg (AND (NOT (NOT <bool-fn2>)) (NOT (NOT <bool-fnl>))) De-Morgan (NOT (OR (NOT <hool-fn2>)

(NOT <bool-fnl>)))

Notice that the final expression in the above sequence describes the generalized composed specification for which the verification will correctly apply. From it , we see that the important feature of the two submodule specifications P 1 and P 2 (the two leftmost NOR gates in figure 11-1) is that they both compute the negation of 8ome boolean funot ion, while t he specifications of t he third component cannot be generalized.

GENERALIZED SPECIFICATIONS OF SUBMODULES

.

4. Step 4: Determining the Generalized Original Specification

Having determined the generalized specifications of the circuit submodules, the RHS of t he new rule can now be formed. However, LEAP must also produce a corresponding generalization of the original functional specification in t he rule LHS. This generalized original specification can be computed in a relatively straightforward manner, either by reapplying the sequence of Ill· or by using t.he \afl~hlr· h11Hiin ~ :-- g t 'fli' P1it-'d when rornputmg th (· generalized rornposed S!J<·r iflrat ion Following either of I h<·se two approaches. the result 1s that the new original specification becomes

Comparing the generalized original specification above with the original specification of the circuit implementation in figure Il- l , it is seen that a generalization of the original specification has been achieved from a conjunction of disjunctions to a conjunction of any boolean functions.

5. Step 5: Forming the New Implementation Rule

We have shown in the last few paragraphs how the original specification of a circuit module as well as the functional specifications of each of the submodules Pi in its implementation could be generalized. The final step ts to form the new implementation rule which is based on these generalized specifications. The preconditions for this new rule are formulated to require {I) that the function to be implemented match the generalized original specification , and (2) that the input signals satisfy the constraints that are determined as shown In the previous subsection. The right-hand side of the new rule is formulated so that it produces the submodules with their corresponding submodule specifications P;'· For the present example, the new implementation rule formed In this fashion******* is shown in figure 11-3.

III Discussion

The previous section describes m some detail how LEAP captures training examples from its users , and how it forms general rules from these examples. This section discusses more broadly t he architectural issues involved in designing knowledge­ based systems that can incorporate such learning methods. In particular, we discuss the major design features of LEAP that appear important to the design of Learning Apprentice Systems more generally . Three design features that have a major impact on the capabilities of LEAP are: (1) the interactive nature of the problem solving system, (2) the use of analytic methods for generalizing from examples, and (3) the separation of knowledge about when an implementation technique can be used from knowledge about when it 8hould be used .

A. Interactive Nature of the Apprentice Consultant

A fundamental feature of LEAP is that it embeds a learning component within an interactive problem-solving consultant . This allows it to collect training examples that are closely suited to refining its rule base. In particu lar , training examples collected by a Learning Apprentice have two attractive properties:

1. Training examples focus only on knowledge that 1s missing from the system. The need for the user to intervene in problem solving occurs only when the system is missing knowledge relevant to the task at hand, and the resulting training examples therefore focus specifically on this missing knowledge.

'''''''Notice t hat in this rule, there are no final constraints that must be satisfied by the input signals. This is because the left-most circuit modules in the figure are defined so abstractly, that they pose no constrain ts on the signal formats of their inputs .

'2 . Th (' l fRIIrrll ~ t' \ i-11 1pk-.. L(Jr ~ · j ·li d -.lf!~!t· fll''·l '· '1!1 · soh·in g ~Hep~. Thi!' 1~ in rr ·trtrast t u the l)'J ..w of training examples used b~ olhrr rul e lf'arning systems such as Met.a-DE!'\DRAL :4. and INDLCE-PLANT [5j, m which training examples are complete problem solutions. By working with training examples that are single steps, LEAP circumvents many difficult issues of credit assignment that arise in cases where the training example corresponds to a chain of several rules.

While to first order, LEAP acquires training examples that correspond to single rule inferences, this is only approximately true. We expect that LEAP will encounter training examples in which its existing rules will correspond to finer-grained decisions than the user thinks of as a single step. For instance, the system may have a sequence of rules to implement a serial­ parallel converter by first selecting a shift register, then a general class of shift registers (e.g. dynamic), and only then a specific circuit , while the user may think of the whole series of decisions as a single step, implementing the converter with a specific circuit .

In such cases, LEAP could just go ahead and learn the larger­ grained rule that will follow from the user's training example, but doing so could cause a number of problems. One problem is that it will result in a rule set with rules of greatly varying grain. Such inconsistency in grain is likely to lead to redundancy and lack of generality in the rules. A second potential problem associated with large-grain trammg examples is that our analytical methods of generalization may be too expensive to use on steps of large grain. Since the methods depend on construct ing a verification of the step, there is reason to fear the cost may grow very quickly as the size of the step gets large compared to the s1ze of the transformations used in the verification process.

Thus, the question of how to handle grain size mismatch may be an important issue for future research. One possible direction would be to develop methods for examining a training example that corresponds to a large step, ihen determining which existing rules correspond to parts of this inference step, leaving only the task of acquiring the missing finer grain rules.

B. Use of Analytical Methods for Generalization

A second significant feature of the design of LEAP is that it uses analytical methods to form general rules from specific training examples, rather than more traditional empirical , data­ intensive methods. LEAP's explain-then-generalize method , based on having an initial domain theory for constructing the explanation of the example, allows LEAP to produce justifiable generalizations from single training examples. This capability is particularly important for LEAP since it is not at all clear how LEAP could tell that two different training examples involving different circuit specifications and different resulting circuits, were m fact two examples of the same rule.

One significant advantage of the analytical methods involves learning in the presence of error-prone training data. An issue that seems central to research on Learning Apprentice Systems, and one that LEAP must confront immediately , is that the users who (unwittingly) supply its training examples are likely to make mistakes. In particular, since we hope to first introduce LEAP to a user community of university students who are themselves learning about VLSI design, the issue of dealing with error-prone examples is a major one. Our initial plan for dealing with this J· l' \l tJi f' lll r ~ ,l lir ·. '" rlld Ll \ I v .. :1 ir, r n r ~I' III'I"R) nd1·, ·111!1 fro rn thosP triillllng f'Xarnpl(· i" trcrttt :-. thiit ll ra n vc·rrf~ in t.rrms of its knowl edg(:· of rirruits. Smce it :- !H'IIeraliza.Lion method requires that it explain an example circuil before it can generalize it , LEAP will be a very conservatiH learner . Since it will be unable to verify incorrect circuil examples that it encounters, there IS little danger of it learning from incorrect examples****..... This method of dealing with errorful data is attractive, but may be insufficient if we need to include empirical learning methods along with analytical methods for generalization.

While analytical generalization methods offer a number of advantages, they require that the system begin with a domain theory that it can use to explain / validate the training examples. This requirement, then, constrains the kind of domain for which our approach can be used. In the domain of digital circuit design , the required domain theory corresponds to a theory for verifying the correctness of circuits. In certain other domains, such a theory may be difficult to come by. For example, in domains such as medical diagnosis the underlying theory to explain/ verify an inference relating symptoms to diseases is often unknown even to the domain experts. In such domains , the system would lack a domain theory to guide the analytical generalization methods, and would have to rely instead on empirical generalization methods that generalize by searching for similarities among a large number of training examples. In fact , our present methods for utilizing domain theories to guide generalization are limited to cases where there is a strong enough theory to "prove" the training example is correct. One important research problem is thus to develop methods for utilizing more approximate, incomplete domain theories to guide generalization, and for combining analytical and empirical generalization methods in such cases. One new research project that is interesting in this light is an attempt to construct a Learning Apprentice for well-log interpretation Jl3J. In this domain, the underlying theory necessary to learn new rules involves geology and response of well-logging tools. Since these theories as inherently approximate and incomplete, that research project must face the issue of generating and utilizing approximate explanations of training examples to infer general rules.

C. Partitioning of Control and Basic Domain Knowledge

A third significant feature in the design of LEAP is the partitioning of its knowledge base into ( 1) implementation rules that characterize correct (though not necessarily preferred) circuit implementations, and (2) control knowledge for selecting the preferred implementation from among multiple legal options. This partitioning is important because it helps in dealing with the common problem that when one adds a new rule to a knowledge base one must often adjust existing rules as well.

The first of these two parts of the knowledge base has the convenient property that its rules are logically independent ; that is, when one adds a new implementation rule characterizing a new implementation method, it does not alter in any way the correctness of the existing implementation rules. Thus, when a new implementation rule is added, the only portion of the knowledge base that might require an update is the control knowledge for selecting among alternative implementations. This

········Even this is not quite true. Since its domain theory is only approximate (as will probably be true for Learning Apprentice Systems in general), there may be incorrect circuits that it succeeds in verifying (say, because is overlooks parasitic capacitances).

] ,,~l''f\ 1 lll<lt' l >f'UdPnrr r.f l fl oj ·l.-' 1·. ' ;l i'dJ · ·I, I , I,,, t:- ~~.. llllJH ·rfa.l l l when combining sets of rul e~ 1 hflt ma~ han· bren learrn·d from various users by different COJ.>Ies of the Learning Apprentice. While the problem of combining multiple rule sets learned from different sources is in principle simply a matter of forming the union of the rule sets, in fact the resulting set of correct rules may be overly redundant and disorganized. Thus, we anticipate that we may have to develop methods for merging and reorganizing sets of correct rules to make them more manageable.

To date, we have only considered learning the first type of knowledge. In some sense, learning these rules is easier than learning the control knowledge, because the complexity of explaining a training example is much less for implementation rules than for control rules. To explain / verify an example of an implementation rule, the system need only verify the correctness of the circuit fragment mentioned in the training example. However, to learn a control rule that characterizes when some implementation is preferred, it is necessary to compare this implementation with all the alternative possibilities. Thus, the complexity of constructing the explanations is quite different in these two cases. In the longer term, we see learning of control knowledge as an important task for LEAP, and a task for which it can easily capture useful training examples.

IV Conclusion

We have presented the notion of a Learning Apprentice System as a framework for automatically acquiring new knowledge in the context of an interactive knowledge-based consultant . The initial design of a Learning Apprentice for VLSI design has been described. In particular, we have detailed the methods that LEAP employs for learning new implementation rules, and for generalizing both the left and right hand side of these rules. Whereas previous attempts at automatic knowledge acquisition have met with little success, the proposed Learning Apprentice System differs in two important respects: it utilizes more powerful analytical learning methods, and it is restricted to interactive knowledge-based systems which can easily capture useful training examples. We are currently completing our initial implementation of LEAP, and intend to test it on a user community of students in a VLSI design course to gather data and further insights on this initial design.

V Acknowledgments

We thank several people who provided useful criticisms of earlier drafts of this paper: Rich Keller, Yves Kodratoff, John McDermott , Jack Mostow, Reid Smith, and Timothy Weinrich. We also thank the members of the Rutgers AI / VLSI project for many useful discussions regarding the design of LEAP, and for creating the VEXED system on top of which LEAP is being constructed. Schlumberger-Doll Research has made the STROBE system available as a representation framework in which VEXED and LEAP are being implemented. This research is supported by the Defense Advanced Research Projects Agency under Research Contract N00014-81-K-0394, and by the National Science Foundation under grant DCS83-51523.

• l j Da,-is. R ··Application> of meta level knowledge t,o the construct ion and use of large knowledge bases.'· in Knowledge-ba6fd Systems in Artificial Intelligence, Davis, R. and Lenat , D. , eds., McGraw-Hill, New York , 1981.
• Politakis, P. , Using Empirical Analysi· to Refine Expert System Knowledge Base<, PhD dissertation, Rutgers University , August 1982.
• Kahn , G., Nowlan , S. , and McDermott , J . "A Foundation for Knowledge Acquisition." In Proceedings of the IEEE Workshop of Principles of Knowledge-Based Systems . IEEE, December, 1984 , 89-96.
• Buchanan, B. G. and Mitchell , T. M., "Model-directed learning of production rules," in Pattern-Directed Inference Systems, Waterman, D. A. and Hayes-Roth , F ., eds. , Academic Press, New York , 1978.
• Michalski, R . S. and Chilausky R. L. "Knowledge Acquisition by Encoding Expert Rules Versus Computer Induction from Examples: A Case Study using Soybean Pathology." Inti . Jrnl. for Man-Machine Studies. 12:63 (1980) .
• [6[ Mitchell , T .M. , Steinberg, L.J., and Shulman , J .S. "A Knowledge-Based Approach to Design ." In Proceedings of the IEEE Workshop of Principles of Knowledge-Based Systems. IEEE, December, 1984, 27-34, Revised version to appear in IEEE Tran&actions on Pattern Analysis and Machine Intelligence, September, 1985.
• Mitchell , T . "Learning and Problem-Solving." In /JCAI-83. August , 1983, 1139-1151.
• DeJong G. "Automatic Language Environment ." Artificial Intelligence . 410-413. Schema Acquisition in a Natural In Second National Conference on Pittsburgh, PA, August, 1982,
• Salzberg, S. and Atkinson, D.J . "Learning by Building Causal Explanations." In ECA/-84 . September, 1984 , 497-500.
• Minton , S. "Constraint-Based Generalization ." In AAA/-84. Austin , Texas, August, 1984, 251-254 .
• Kelly , Van E. "The CRITTER System Automated Critiquing of Digital Circuit Designs." In Proceedings of the !!1st Design Automation Conference. IEEE, June, 1984, 419-425 , Also Rutgers AI/ VLSI Project Working Paper No. 13
• Mahadevan , S. "Verification-Based Learning: A Generalization Strategy for Inferring Problem-Decomposition Methods." In Proceedings of the Ninth International Joint Conference on Artificial Intelligence . August , 1985.
• Smith, R .G., Winston, H.A. , Mitchell , T.M., and Buchanan , B.G. "Representation , Use and Generation of Explicit Justifications for Knowledge Base Refinement." In Proceedings of the Ninth International Joint Conference on Artificial Intelligence. August, 1985.