The FAD Project
Creators: name: Liew, C. W.
name: Steinberg, Louis
Publisher: name: Rutgers University
Year: 1992

description: Design is much easier when the design problem can be decomposed into small pieces that can be solved independently and then easily combined to form a solution. However, when the design goals include limiting overall usage of some resources, e.g. for a digital circuit limits on computation time or silicon area, interactions often arise which make it difficult to determine what effect some decision about a small piece of an artifact will have on the overall quality of the solution. Thus decomposition becomes impossible and, if the problem is too large to handle by exhaustive search, finding a good solution is very hard. We have focussed our attention primarily on the task of High-Level Synthesis (HLS) of VLSI digital circuits - the process of converting a computation specified in a language much like a programming language into a register-transfer level description of a circuit to carry out this computation. Real problems in this domain involve not just producing functionally correct circuits, but also circuits that use limited amounts of time and silicon area, and perhaps also limited power. They are often very large and complex problems, and require many decisions, and many kinds of decisions, to be made before a solution is generated. The space of possible solutions is therefore very large and it is not feasible to examine all possible solutions. Thus, this domain is a good example of problems where global interactions due to multiple resource constraints combine with a large search space to make design hard. The standard approach taken by current programs which do HLS is to none the less treat groups of decisions as if they were independent, and to use a heuristic function to estimate how good a proposed partial solution is. Unfortunately, these heuristics are not good enough (and as we will discuss below {em cannot} be good enough) to produce designs competitive with those of human designers. This paper describes a new approach we have developed for solving such problems, which we call {em Feedback Aided Design} (FAD). Since we can only really tell how good a design is when it is complete, our approach essentially does a {em search in the space of complete designs.} However, each step we make in this space is not made by directly perturbing the previous design. Rather, we design a complete circuit using standard methods, analyze it to propose a few key decisions which should have been made differently than they were, and rerun the standard design methods with the added constraints on how these specific decisions are to be made. Thus, we wrap the standard methods in an outer loop which runs them, analyzes the resulting circuit, and produces constraints which are the used as feedback to guide the next iteration of design. Our approach does not require additional software to ensure the correctness of the final solution, a requirement that would be needed if our search entailed direct modification of the design. Although our approach depends strongly on domain knowledge to do the analysis, we believe our framework gives important guidance as to what domain knowledge is needed and how a system can be structured to use it. We believe this framework should transfer to a number of important domains besides High-Level Synthesis. The approach is being implemented in the FAD System. This work is part of the CAP (Computer Aided Productivity) Project, a long term research effort in the Laboratory for Computer Science Research at Rutgers University aimed at modelling the design process and developing knowledge-based design systems for a spectrum of design domains.