Application of evolutionary algorithms for partitioning in VLSI and embedded systems

Abstract

The complexity of VLSI and embedded systems is continually increasing and the analysis and design of such a complex system is an NP hard problem. Hardware/Software Co-Design (HSCD) is the discipline of automating the design of complex embedded systems with functionality in both hardware and software. The objective is to separate the cells into two or more blocks so that the number of interconnections between the blocks is minimized and the cells are evenly distributed across the layout surface. Therefore, partitioning is NP-hard and a very crucial problem. In this work two heuristics have been applied for single-objective optimization of hardware/software partitioning problem. To partition more complex systems, heuristic search methods Genetic Algorithm (GA) and Binary Particle Swarm Optimization (BPSO) are applied. In this research, three evolutionary algorithms for multi-objective optimization are applied for hardware/software partitioning in embedded system design: (i) A slightly modified version of GA in which the objective function is defined as the weighted sum of the different objectives called Weighted Sum Genetic Algorithm (WSGA). (ii) Elitist Non-dominated Genetic Algorithm (ENGA) uses non-dominated sorting and crowding tournament selection operator to select the individuals to be added to the population for next generation. (iii) Multi-Objective Particle Swarm Optimization using Crowding Distance (MOPSO-CD), which is a variant of BPSO. A typical hardware/software environment based on Altera FPGA Quartus II design environment has been developed and the real-time data for the hardware area, the software area, the hardware time and the software time are obtained. Two data-dominated applications related to DSP benchmarks namely FFT and image applications namely JPEG-FDCT (Fast Discrete Cosine Transform) are tested using the real-time data to demonstrate the practicality of the multi-objective optimization algorithms. For the two applications, ENGA is found to perform better than WSGA and MOPSO-CD.