Tuning a Knowledge Base of Refinement Rules To Create Good Circuit Designs

1 Introduction

In principle, design efficiency and solution optimality can be impacted by three factors: choice of design process model; the accuracy of the (possibly implicit) assump­ tions made by that design process about subproblem in­ teractions; and the contents of the knowledge base. We will discuss these factors in turn, finally concluding that if a learning method focuses on improving the last of these, using a fixed, search-based model of design, the second issue will disappear over time.

1.1 Some simple models of design

Much research in knowledge-based design [Kant and Barstow, 1978, Stefik, 1981, Mittal, 1986, Steinberg, 1987, Tong, 1988, Brown and Chandrasekaran, 1989] has concentrated on design involving some form of top-down refinement. In many knowledge-based design systems, top-down refinement proceeds by repeatedly applying refinement rule1 that flesh out or decompose abstract functional specifications, until the leaves of the generated hierarchy are functions that are directly implementable in the target technology (using refinement rules we will call implementation rule1). The functional component hierarchy is isomorphic to a goal hierarchy containing implementation goals and subgoals of the form, "Opti­ mally implement component x". Figure 1 illustrates such a hierarchy in the domain which we will use to illustrate our ideas: boolean expression design.

In this paper, we will consider design processes that perform not only refinement, but also patching and bad:­ traclcing; we presume a depth-first search strategy. In the boolean function domain, a patcher might use a rule base containing patching rule1 such as P1: "If the cir­ cuit is a combinational circuit, and two inverters are in sequence, they can be replaced by a wire." Patch­ ing is used to correct constraint violations, and to op­ timize the design. If patching is insufficient for resolv­ ing some problem, backtracking will retract refinement and patching choices that have been made. Models that include other design operations are also possible. For example, many of the ideas about patching apply more generally to subproblem composition processes (includ­ ing constraint-based reasoning). However, the simple elements just mentioned will suffice to demonstrate the basic intuitions behind our learning method.

1.2 The accuracy o£ assumptions about subproblem interactions

Suppose we want the design process to create an imple­ mentation of a boolean expression design problem that is optimal with respect to gate count. We will consider three different solutions to the design problem of Fig­ ure 1; one has 10 gates, another, 8 gates, and a third, 6 gates. The 6 gate solution is an optimal one for this design problem. What sort of design processes might produce the suboptimal solutions?

"Non-interacting subproblems" assumption. A 10 gate solution could be produced by a purely refinement-based process. The design process creates the subproblem decomposition in Figure 2, and selects the (locally) best solution to each subproblem ~depicted in the figure). Such a design process implicitly makes the mistaken assumption that subproblems do not interact; that is, it assumes that locally correct and optimal so­ lutions to the subproblems compose to form a globally correct and optimal solution.

"Weakly interacting subproblems" assump­ tion. An 8 gate solution could be produced by a design process that supplements top-down refinement with op­ timization. Many programming language compiler· have this sort of behavior. Repeated application of patching rule P1 in the boolean function domain is an example of a linear time optimizer, a procedure that iteratively modifies solutions until it produces an optimal solution (in linear time). "Peephole optimization" is another ex­ ample of a linear time optimizer. Both of these patching processes are applied to the flat, composed solution; hi­ erarchical patching (e.g., the merge step of mergesort) can increase the complexity by a factor of d, the depth of the hierarchy.

Top-down refinement would initially produce the same 10 gate implementation as before. Subsequent hillclimb­ ing toward a more optimal design via patching finds only a single opportunity to apply patching rule P1 (to sub­ problems 3 and 4), resulting in an 8 gate solution. This design process implicitly makes the mistaken assumption that the subproblems only weakly interact, i.e., it is pos­ sible to take any combination of subproblem solutions and patch it into a globally correct and optimal solution in linear time.

1 We only consider design processes that do not explicitly reason about such assumptions.

Strongly interacting subproblems. Subproblems ltrongly interactifsome combination of subproblem solu­ tions cannot be patched into a globally optimal solution in linear time. The subproblems in Figure 2 strongly interact (as illustrated by the particular solutions in the figure). Given the possibility of strongly interacting sub­ problems, we use a search-based model of design that permits backtracking to guarantee that an optimal solu­ tion is produced. We assume that the search is trying to optimize an evaluation function f (e.g., gate count), and that one of the problem inputs is a budget that must be met: f(de·ign) ~bu.

Because the search-based design process. still divides problems into subproblems (via refinement) it still be­ haves as though the subproblems do not interact or only weakly interact, and only backtracks when that (im­ plicit) assumption is proven wrong. Thus like the previ­ ous design processes, it selects the locally best solution to each subproblem it tries. Suppose it solves the sub­ problems of Figure 2 in the order {1,2, ... ,7}. If we set a budget of 6 gates, it will search about half the design space before it retracts the initial choice it makes for subproblem 1, and begins to converge on the optimal so­ lution (Figure 1). The optimal solution is produced by selecting the locally worlt solutions for subproblems 1 and 6, implementing each of these two ORs as a NAND gate and two inverters. This produces a design in which patch rule P1 can be applied three times, bringing the gate count down to 6. As illustrated by this example, search finally finds the optimal solution, but generally does so in exponential time. Thus no leverage in effi­ ciency was gained from the "problem decomposition".

1.3 The contents of the knowledge base

Mistaken assumptions are due to inappropriate rules. Problems of suboptimal designs or inefficient de­ sign processes occur when the goal hierarchy is inappro­ priate; the subproblems it creates interact, thus mislead­ ing a design process that presumes otherwise. Inappro­ priate goal hierarchies are evidence that the knowledge base contains inappropriate rules. For instance, pure top-down refinement would be sufficient for the boolean expression design task i/the refinement rules were guar­ anteed to produce non-interacting subproblems. Instead of changing the nature of the design process, we can try to change the rules which produce the subproblems, so that they produce subproblems whose worst-case inter­ actions are guaranteed to fall into a particular category (e.g., "weakly interacting subproblems").

Acquisition of design knowledge. The most ob­ vious response to this observation would be to acquire rules that only create non-interacting subproblems; we will call these good refinement rule1. One or more such rules might decompose our example design problem in the manner depicted in Figure 1 (instead of the decom­ position of Figure 2). Because they are non-interacting, the locally optimal solutions to these subproblems com­ pose to form a globally optimal 6 gate solution. We may arrive at these locally optimal solutions either by applying the "design as search" approach locally to solve each subproblem, or by acquiring three additional imple­ mentation rules that tell us how to optimally implement these subproblems.

In contrast, however, most prototype knowledge-based design tools or compilers that have been created for "real world" problems such as circuit or software design do not follow this strategy. Most create an initial, poor design based on an inappropriate goal hierarchy, and then optimise (e.g., [Knapp and Parker, 1986, Kowal­ ski, 1985]). Far fewer (e.g., [Kant and Barstow, 1978, Steinberg, 1987]) actually use refinement rules that en­ able a polynomial time, divide-and-conquer approach.

The reason seems clear. Acquiring implementation rules sufficient for forming (probably inappropriate) goal hierarchies is generally a relatively easy and constrained task (see, e.g., Figure 3). Acquiring patching rules suf­ ficient for limited optimisation is also relatively easy. On the other hand, acquiring good refinement rules is a rather unconstrained task. A combinatorial number of such rules may be necessary to get broad coverage. Such rules may not exist, may not be easily obtainable from domain experts, or may not be expressible in any intuitive form.

Learning good refinement rules from design ex­ perience. Let us reconsider the problem of inappropri­ ate goal hierarchies from the standpoint of human de­ signers. In a poorly understood design domain, human designers do not usually start out doing top-down design. Instead, they first do a lot of "exploratory design", using processes such as composition, hillelimbing, or analogical reasoning (see, e.g., [Kowalski, 1985]). We hypothesize that one of the primary purposes of such exploratory de­ sign is to form a more appropriate goal hierarchy out of an initially poor one, so that a reasonably efficient top-down refinement based approach to design can be pursued subsequently, and so that the process is reason­ ably likely to produce an optimal (or satisficing) solu­ tion. Human designers appear to learn appropriate goal decomposition hierarchies both while solving a particu­ lar problem, and more generally, so that later problem­ solving behavior for a similar problem seems less search­ like. We have modelled the "within-task" learning skill (given an initial budget for an evaluation function /), in a circuit design program called DONTE [Tong, 1988].

This paper focuses on modelling across-task learning of appropriate goal decomposition hierarchies that are fine­ tuned for optimizing a particular evaluation function.

Implicit vs. explicit decomposition. The prob­ lem decompositions we have been discussing can be cre­ ated directly by decompo1ition rule· that match a design problem and produce a set of subproblems to be solved. Alternatively, a decomposition can be created indirectly by applying refinement rules that only match a subex­ pression S (e.g., (AND u v)) of the design problem P (e.g., (NOT (AND u v))). Such a rule implicitly decom­ poses P into two problems: "Implement S" and "Imple­ ment everything in P but S" (e.g., (NOT expr)). H P can be "parsed" into subexpressions all of which match some refinement rule, we say that Pis implicitly decom­ poled by the set of matching rules. Ambiguity in the parse corresponds to alternative decompositions. In this paper, we will study the learning of good refinement rules that implicitly decompo1e a problem into non-interacting subproblems by matching its subexpressions.

Simplifying assumptions. Design subproblems can interact in different ways. A functional interaction oc­ curs if some combination of choices for solving the sub­ problems leads to a global design that fails to function correctly. A re1ource wage interaction occurs if some combination of choices for solving the subproblems leads to a design that is 1uboptimal with respect to a given re­ source budget. In this paper, we focus on resource usage interactions between subproblems, and presume that no functional interactions between subproblems can occur.

2 The design method

Choice of design process model. If the same de­ sign process model is to be used at any point during the course of learning, that model must be robult enough to recover from mistaken assumptions about subprob­ lem interactions. On the other hand, after its knowledge ba1e has been improved, the design process must be able to use the learned knowledge in such a way that its per­ formance is improved. In this section, we describe a simple design process model that has both of these prop­ erties. This model has been implemented in a program called CPS. CPS is a search-based design system that performs top-down refinement, patching, and chronological backtracking. We will illustrate the behavior of CPS in solving the problem in Figure 1.

Input. The input to CPS is a boolean expression (composed of binary AND and OR functions, and the NOT function), an evaluation function that defines de­ sign optimality, and a global resource budget that must be achieved. For the purpose of simplifying the learning method (so it needn't verify that the design produced by the performance system is optimal), the budget we give CPS is the cost of an optimal solution. By opti­ mal 1olution we mean the circuit in the space of circuits defined by the refinement and patching rule base (see be­ low) that costs the least (with respect to the evaluation function).

Output. The output is an optimal cost, TTL gate­ level circuit, composed of binary AND-gates, OR-gates, and NAND-gates, as well as inverters. Figure 1 gives an optimal solution to our example problem.

The knowledge base. The domain knowledge base is depicted in Figure 3.

Refinement. Design (sub)problems are solved ei­ ther directly, using a single implementation rule (e.g., for subgoal 4 in Figure 4, "Implement (AND u v)") or indirectly by (implicitly) decomposing the problem. In the latter case, the subproblems are determined recur­ sively. CPS finds all refinement rules that apply to the current expression (initialized to be the entire problem). Of these applicable refinement rules, CPS chooses one whose "left hand side" is mazimally 6pecific, i.e., one that applies to the largest possible sub-expression of the current expression. 2 Thus rules that refine expressions ofthe form (OR (AND x y)(AND w ·)) will be selected over more general rules that refine expressions of the form (OR x y). In our example, based on the refine­ ment rules in the initial knowledge base (all of whose "left hand sides" are primitive functions), the only rules that apply to the top-level OR simply have (OR x y) as their left-hand side. Subgoal 1 is created in response and added to the implementation goal hierarchy (see Figure 4). Then for each non-literal argument, the same process is repeated, creating subgoals 2 through 7.

,The ARGO circuit design system [Huhns and Acosta, 1989] uses a similar heuristic.

In general, the result of refinement can itself be de­ composable. However, in our simple boolean function domain, the subproblems of the original problem are di­ rectly implementable, because the refinement rules that implicitly construct the decomposition are all implemen­ tation rules. The implementations chosen for each sub­ problem (after some search) are illustrated in Figure 4.

Evaluation function. Faced with a choice among different refinement alternatives for the same subgoal, CPS will prefer the alternative that is locally optimal with respect to a given evaluation function. In our exam­ ples, the evaluation function is one that prefers NAND gate implementations:

5x#ANDGates+5x#ORGates+3x#INVa+#NANDGates

Selecting locally optimal refinement alternatives does not guarantee a globally optimal solution. The refine­ ment choices that do lead to the optimal cost solution are illustrated in Figure 4. Only 5 of the 7 are locally optimal.

Patching. After CPS constructs a global solution, if it detects a budget violation, it repeatedly selects and executes applicable patch rules until no more patching is possible. Figure 4 illustrates the patching process for the subproblems in our example.

Backtracking. Backtracbble choice points are cre­ ated whenever a particular implementation task has al­ ternative solutions. Chronological backtracking occurs whenever a design has been completely implemented (and patched) and the global budget has not been met; an implementation choice and all patches that depend on it are retracted. CPS stops at the first complete so­ lution that meets the budget. In the boolean function domain, given only the (easily acquired) knowledge in the initial knowledge base (Figure 3), we cannot back­ track when partial solutions violate the budget because, in many cases, further patching opportunities (leading to an optimal cost design) may become av&ilable only after additional choices have been made.

In our example (Figure 4), the partial solution after the implementation of subproblem 6 has a cost of 7, ex­ ceeding the global budget. Only when the final sub- · problem is implemented and the solution patched does the implementation meet the budget.

Termination. When all the implementation goals have been achieved, and the resulting design does not violate the budget, the design process is completed.

3 The learning method

SCALE is the learning component of our system. After CPS solves a problem, SCALE's learning method rationally reconstructs the problem decomposition by ana­ lyzing dependencies. It then generalizes from the non­ interacting subproblems in the reformulated decomposi­ tion; new refinement rules that identify and optimally implement similar non-interacting subproblems are cre­ ated. The input to SCALE is a CPS problem-solving trace. The trace includes the original problem, the se­ quence of refinement and patch operations which led to the optimal solution, and the final implementation. To illustrate SCALE's behavior, we will use the example of Section 1.

We use an explanation-based learning (EBL) approach [Mitchell et al., 1986] to ezplain the training example and jultifiably generalize from it one or more refinement rules:

• The training ezample (the input to SCALE) is a design problem and the trace of CPS solving it.
• The domain theory is the knowledge base and an evaluation function f.
• The goal concept is one or more "good" refinement rules, LHS-RHS, where LHS is a generalized clul­ ter (see below), and RHS is an implementation of LHS that is optimal with respect to f.
• The operationality criterion requires the LHS of the rule to be a boolean expression, and the RHS to be a network of gates.

Explaining subproblem interactions using clus­ ters. By analyzing dependencies in the final optimal design, SCALE identifies clu1ter1 of interacting subprob­ lems. These clusters consist of one or more of the sub­ expressions that were created when the problem was originally decomposed by refinement rules that matched its sub-expressions. A cluster consists of more than one sub-expression when the successful application of a patch depends upon the existence of several sub-expressions. The patches can be thought of as "gluing" the sub­ expressions together. H the same sub-expression is in­ volved in several patches, all the "glued" sub-expressions are clustered. The cluster is a 1ingle sub-expression in the special case when CPS has derived a better imple­ mentation for a primitive function (AND, OR, NOT) than was originally provided by the initial set of refine­ ment rules.

In our example, three clusters of interacting subprob­ lems are detected (see the circled subproblem implemen­ tations in Figure 4, which match the subproblems in Fig­ ure 1). The first cluster groups subproblems 1, 2, and 5. Patch II converts two inverters created by the im­ plementations for subproblems 1 and 2 into two NAND gates; since these two gates are in series, they are then eliminated by Patch I. These two patching rules apply in a similar way to subproblems 1 and 5. One cluster is formed for both patch applications (rather than two separate clusters) because both depend in part on sub­ problem 1. Several uncircled clusters are also formed; these clusters correspond to new, optimal implementa­ tions for OR, AND, and NOT.

The EBL goal concept requires that the RHS of a learned rule be an optimal implementation of the LHS. The global implementation is known to be optimal be­ cause CPS is required to meet an "optimal cost" bud­ get. By construction, the clusters do not interact; the optimality of the global implementation implies the op­ timality of the cluster implementations.

Cluster generalisation. The explanation process has parsed the solution tree into subproblem dusters and their optimal implementations. SCALE generalizes each of these into a refinement rule. For example, the rule learned from the first duster in Figure 4 has (OR (AND varl var2) (AND var3 var 4)) as its generalized LHS and (NAND-G (NAND-G varl var2) (NAND-G var3 var4)) as its generalized RHS. The LHS generalizes the func­ tion arguments from the original sub-expressions at the leaves of the goal hierarchy, while the RHS generalizes the implementations of those same arguments.

The long-term "goal concept" of SCALE's learning is a 6et of refinement rules that implicitly decompose any problem in the domain into non-interacting subprob­ lems (and create optimal implementations for these). SCALE's goal concept is instead expressed in terms of learning a single rule, and cluster formation. The next section discusses some of the ideas behind why SCALE's goal concept leads to achieving the long-term goal con­ cept in the boolean function domain.

4 Discussion

Closure: completely learning a knowledge base. One view of SCALE is that it compiles the optimiza­ tion knowledge of the patch rules into new refinement rules. Learning these "good" rules is attractive when us­ ing knowledge bases like that of our example, for which only a finite number (a clo6ure) of good rules exist. After a relatively small number of examples (less than twenty, on average, in fifteen experiments involving randomly generated boolean expressions), SCALE converges to the set of rules listed in Table 1. These rules have the form: IF boolean expre .. ion THEN implement as circuit. SCALE forms the closure by adding these rules to CPS's knowledge base.

Design as search: efficiency speed-up. Figure 5 illustrates the results of our experiments to measure the improvement in efficiency of a search-based design sys­ tem due to repeated application of our learning method.

The "before learning" curve illustrates the behavior of CPS using the initial knowledge base (Figure 3) on a set of randomly generated test problems. Chronolog­ ical backtracking, optimization patching, and a target optimal budget combine to control CPS's search for an optimal circuit. As discussed in Section 1, the time com­ plexity of such a problem solver is exponential.

SCALE increases the efficiency of CPS by transforming it from a search-oriented knowledge-based design system (which is relatively easy to build) into an effi­ cient (one pass) knowledge-based compiler which pro­ duces optimal designs. Because CPS uses the "maxi­ mally specific" heuristic, and draws its refinement rules from the knowledge base closure (guaranteed to pro­ duce non-interacting, locally optimal solutions), it has compiler-like behavior; because the resulting subprob­ lems do not interact, CPS simply composes subproblem solutions, producing a global solution without backtrack­ ing or patching. The "after learning" curve in Figure 5 illustrates the behavior of CPS on the same problein.s as the "before learning" curve after the closure has been learned (the "after learning" knowledge base was ex­ panded by learning from a separate, randomly generated problem set). It shows that CPS produces the target so­ lutions in linear time by generating the fewest possible nodes (one for each subproblem in the decomposition) .

Integration of knowledge. SCALE adds newly learned rules to the knowledge base, but does not remove existing rules. This raises two issues of knowledge inte­ gration: How does SCALE limit the new rules learned so as to minimize redundancy in the rule base? After new rules have been learned, how does the performance system select among competing rules, so that the overall performance after learning improves?

A common problem of rule learning is 6Wamping, learning rules that express the same knowledge redun­ dantly (see [Fikes et al., 1981]). A central contribution of our work is the selective learning of "good" refinement rules that produce non-interacting subproblems (rather than all possible rules for a knowledge base). SCALE limits redundancy because good rules express knowledge about refinement rule interactions; thus no refinement rule application can be re-expressed simply as an appli­ cation of other refinement rules. Of course, the refine­ ment rules will always be re-expressible as an application of the primitive refinement rules and patch rules.

The use of the "maximally specific" heuristic gives CPS the desirable property of non-interference: subsequently-learned rules never interfere with CPS's ability to solve previously worked problems. This is because SCALE always learns rules from the maximal clusters of a problem trace. On subsequent attempts at solving the same problem, the "maximally specific" heuristic ensures that it will choose the refinement rules for the same maximal clusters.

Solution optimality. When restricted to boolean ex­ pressions whose literals are distinct positive logic values (i.e., z, y, .z, etc.), CPS generates gate-level implemen­ tations of boolean expressions that are "optimal" with respect to the space of all designs it can generate. CPS cannot produce an optimal solution for tJll boolean ex­ pressions because it does no structure-sharing; for ex­ ample, if there are two occurrences of (N AND-G x y) in the final implementation of a circuit, the output of a sin­ gle NAND-gate could be directed to both inputs which require it.

Scope of the learning JDethod. SCALE learns about local re1ource u1age interaction· between subprob­ lems that do not interact functionally. It presumes that the patch rules improve the design with respect to the evaluation function. It does not reason about optimizing by global structure-sharing.

SCALE could be applied to any initial knowledge base of refinement and monotonic patch rules for our exam­ ple domain, including one where the results of refine­ ment rules are expressed as optimal NAND-gate configu­ rations. We chose to start with a sub-optimal knowledge base to show that we can relieve the human engineer of the requirement of providing an optimal base, and ·till produce a linear time optimizing compiler.

5 Conclusions

SUJDJDary. This paper has presented a method that in­ crementally transforms a search-based circuit design sys­ tem (CPS) that uses only primitive (and non-redundant) refinement and patch rules into a compiler-like design system with the following properties:

• Non-redundant rule-1et. No refinement rule appli­ cation can be re-expressed as an application of other refinement rules.
• No backtraclcing or patching. The system produces a design that meets an initially specified resource budget without patching or backtracking.
• Coincidence of local optimality with global optimal­ ity. Composing locally optimal solutions to sub­ problems . created by refinement rules results in a solution that is globally optimal.

When and what to learn is based on analyzing design step dependencies, and interactions of design steps with respect to optimization. This learning method has been implemented in the SCALE program, which converges on the "best possible" knowledge base (the "closure") from a simple initial knowledge base, using (on the aver­ age) less than twenty random design problems as train­ ing examples. For further details on the evolution of the CPS/SCALE system, see [Tong and Franklin, 1989].

Acknowledgements

We thank Jack Moetow, Mike Barley, Wes Braudaway, Dawn Cohen, Chun Liew, Sridhar Mahadevan, and Ar­ mand Prieditis for providing helpful comments on earlier drafts of this paper. We also thank the members of the Rutgen AI/Design Project for the stimulating environ­ ment they provide.