Digital System Synthesis with Complex Functional Units


TR Number



Journal Title

Journal ISSN

Volume Title


Virginia Tech


The transistor count for todays VLSI technology reaches 40 million transistors on one chip. In order to successfully design a system with such complexity, new computer-aided design (CAD) tools are needed. This dissertation shows approaches for coping with the problem of increasing complexity of VLSI design in three aspects: 1) capturing a higher level of abstraction, 2) using a new target architecture, and 3) using a new optimization technique.

The advantage of working at a higher level of abstraction is that the number of objects that designers have to manipulate is reduced so that more complex systems can be delivered in shorter periods of time. The functions that can be used to capture higher levels of abstraction are surveyed and categorized into an is-a hierarchy. A partitioned-bus architecture that consists of complex functional units used to realize complex functions is proposed. The issues of synthesizing the complex functions to the partitioned-bus architecture are addressed. These issues are focused on the functional partitioning problem which is a known NP-complete problem. Algorithms used to optimize several metrics that affect the solution qualities of functional partitioning are presented. The metrics include communication buffer size, register file size, system delay, the number of buses, the number of links, and the number of multiplexers. These metrics are used to form a cost function, which is utilized by the Problem Space Genetic Partitioning algorithm (PSGP) to search for a good solution. Test cases with known optimal solutions are used to evaluate the solution qualities that PSGP can attain under run time and memory space constraints. The experimental results show that PSGP can reach an average about 87% of the optima for two-way partitioning. Another study also shows that PSGP outperforms the widely used Simulated Annealing algorithm.



Digital System Synthesis, Genetic Algorithm, Communication Buffer, Partitioned-Bus Architecture, Complex Functional Unit