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

Abstract

The efficiency and optimality of a divideand-conquer approach to design depends upon the associated hierarchy of implementation goals having sibling subgoals that interact only weakly or not at all. Unfortunately, in many domains the only easily acquirable design refinement knowledge leads to the formation of goal hierarchies that violate this assumption. In this paper, we describe a learning method that incrementally transforms a search-based design system that spends much of its time recovering from the implicit (and mistaken) assumption that subproblems do not interact, into a compiler-like system that decomposes the original design problem into truly noninteracting subproblems. The improved system finds locally optimal solutions to its subproblems, which are composed into globally optimal solutions. By analyzing dependencies, the learning method re-parses a poor design decomposition into one with no subproblem interactions; it then generalizes from the resulting decomposition, adding new refinement rules to the knowledge base. We have implemented a design system called CPS that solves design problems of implementing boolean expressions as gate-level circuits. We have also implemented a learning program called SCALE that incrementally transforms CPS into an optimizing compiler.