Facet: A Procedure for the Automated Synthes is of Digital Sys tems 1

In the past decade significant effort has been devoted to the development of methodologies for design at the register-transfer level. However, effective and versatile procedures are still not available. This paper presents an efficient procedure for the automated synthesis of data paths at the register-transfer level. The procedure minimizes the numbers of storage elements, data operators, and interconnection units. In addition, the procedure has the capability of exploring alternatives in the design space. In some preliminary experiments the procedure produced designs nearly identical to commercially produced designs. 1 Introduct ion The Carnegie-Mellon University Design Automation (CMU-DA) system has been developed over the past six years [6]. Using the ISPS description [3] as input, the CMU-DA system proceeds through global optimization, design style selection, data-memory allocation, physical module binding, control allocation, chip partitioning, and mask generation phases. This paper describes the result of some research in the data-memory allocation phase. The problem of data-memory allocation includes five subpro~)tems. They are the specification of data flow and control flow, the allocation of storage elements, the allocation of data operators ~ the allocation of interconnection units, and the exploration of the design space. The issues of specifying the initial operation sequences are described in Section 2. Given a list of operation sequences (in some sense, this means the performance is specified), the problem of design improvement is concerned with the minimization of the numbers of storage elements, data operators, and interconnection units. These three minimization problems can be formulated into the clique.partitioning problem. The clique-partitioning pro~lem will be detailed in Section 3. Section 4, 5, and 6 describe the formulations and present algorithms for generating solutions for each of these three problems. Exploring the design space is the topic of Section 7. Section 8 contains conclusions and suggestions for future work