Abstract
Technology binding is the process of mapping a technology independent description of a circuit into a particular technology. This paper outlines a formalism of this problem and offers a solution to the problem in terms of matching patterns, describing technology specific cells and optimizations, against a technology independent circuit represented as a directed acyclic graph. This solution is implemented in DAGON. DAGON rests on a firm algorithmic foundation, and is able to guarantee locally optimal matches against a set of over three thousand patterns. DAGON is an integral part of a synthesis system that has been found to provide industrial quality solutions to real circuit design problems. 1. Introduction t We begin our treatment of the problem of technology binding with local optimizations by outlining a formalization of it. Using this formalization we will find that the problem is related to those that have been encountered in the field of programming language compilers. Indeed, we claim that compiler techniques are highly relevant to many problems in logic synthesis. This thesis was originally stated in [Jo821 and in [TJBW. In particular here we claim that technology binding for logic synthesis is a very closely related problem to code generation for programming language compilers. More specifically, matching a graphlike description of a technology independent circuit against a library of patterns in a technology, such as a standard cell library, is similar to matching a graph-like intermediate representation of a computer program against the patterns of an instruction set of a given machine. Thus twig [Tj86], a tree manipulator used for constructing code generators for programming language compilers is used to build an optimizing technology binder. The result is a technology binder, DAGON, that is capable of optimizing for time, area or a function of both. Because DAGON uses data abstraction, and a modular technology pattern description format, DAGON is easy to "port" to new Permission to copy without fee all or part of this material is granted provided that the copies are. not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission. technologies. DAGON rests on a firm algorithmic foundation, and is able to guarantee locally optimal matches against a set of over three thousand patterns.
Showing the abstract — retrieve the full paper via the Exa API.