Automated synthesis of data paths in digital systems (design space)
Chia-Jeng Tseng · 1984
In the past decade significant effort has been devoted to the development of a methodology for design at the register-transfer level. However, effective and versatile procedures are still not available. This thesis presents a formalization, called Facet, for the automated synthesis of data paths at the register-transfer level. The problem of data-memory allocation includes five subtasks: 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 a design space. The formalization, based on the as early as possible strategy, first compacts a behavioral specification into the minimum number of steps. With the code sequence specified, the tasks of allocating storage elements, data operators, and interconnection units are formulated into the clique-partitioning problem. The formulation minimizes the number of storage elements, data operators, and interconnection units. Given the initial allocation, two or more storage elements, data operators, or interconnection units can be combined if the related operations are serialized. Using cost and performance measures, these alternative implementations form a design space. A design generator named Emerald, based on Facet, was developed and implemented to facilitate extensive experiments with the methodology. Emerald provides mechanisms for interactively manipulating the code sequence. When a new code sequence is specified, Emerald allocates a set of data paths for the code sequence. The capability of realizing specific functions with special hardware is also incorporated in the Emerald design generator. Data Paths for the behavioral descriptions of the AM2901, the AM2910, the MCS6502, and the IBM System/370 were produced and analyzed. Designs for the AM2901 and the AM2910 are compared with commercial designs. Overall, the total number of gates required for Emerald's designs is about 15 percent more than the commercial designs. The design space spanned by the behavioral specification of the AM2901 is extensively investigated. Limitations of automated design are also discussed.