Genetic Algorithms for High-Level Synthesis in VLSI Design

Abstract

VLSI design involves a number of steps such as system-level design, high-level synthesis (HLS), logic design, test generation, and physical design. All these steps involve combinatorial optimizations that are NP complete. Genetic algorithms (GA) have been used to solve many problems in VLSI design. HLS is the crucial step where the architecture of the system is decided upon. We have worked on several problems relating to high-level synthesis and developed GAs for them. In this article we describe our GAs for the following three problems and describe some general methods that we have used in these GAs to enhance their operation.

	Minimum node deletion (MND).
	Allocation and binding for data path synthesis.
	Scheduling, allocation, and binding for the synthesis of structured architectures.

All of the above problems are NP complete. We have used the following techniques to enhance the operation of the GA:

	Population control to enforce diversity within a relatively small population size.
	Solution completion using approximate algorithms to generate superior valid solutions.
	Selection control to reduce crossover between incompatible members.

These GAs have been tested on the usual benchmarks and the results have been found to be acceptably good. The enhancing techniques we describe here are of a general nature and may be used with other GAs to produce better results.

Key Words:

• VLSI design
• High-level synthesis
• Data path design
• Structured architecture
• Genetic algorithm

Acknowledgments

C. Mandal acknowledges Kingston University, UK for partial support of this work. P. P. Chakrabarti acknowledges the Department of Science and Technology, Government of India for partial support of this work.