Hybrid genetic-paired-permutation algorithm for improved VLSI placement |
| |
| Authors: | Vladimir V Ignatyev Andrey V Kovalev Oleg B Spiridonov Viktor M Kureychik Alexandra S Ignatyeva Irina B Safronenkova |
| |
| Affiliation: | 1. Department of the Design Bureau of Modeling and Controlling Systems, Southern Federal University, Rostov Oblast, Russia;2. Engineering Center of Radio and Microelectronic Instrument Making, Southern Federal University, Rostov Oblast, Russia;3. Department of Computer-Aided Design Systems, Southern Federal University, Rostov Oblast, Russia;4. Federal Research Center, The Southern Scientific Center of the Russian Academy of Sciences, Rostov-on -Don, Russian Federation |
| |
| Abstract: | This paper addresses Very large-scale integration (VLSI) placement optimization, which is important because of the rapid development of VLSI design technologies. The goal of this study is to develop a hybrid algorithm for VLSI placement. The proposed algorithm includes a sequential combination of a genetic algorithm and an evolutionary algorithm. It is commonly known that local search algorithms, such as random forest, hill climbing, and variable neighborhoods, can be effectively applied to NP-hard problem-solving. They provide improved solutions, which are obtained after a global search. The scientific novelty of this research is based on the development of systems, principles, and methods for creating a hybrid (combined) placement algorithm. The principal difference in the proposed algorithm is that it obtains a set of alternative solutions in parallel and then selects the best one. Nonstandard genetic operators, based on problem knowledge, are used in the proposed algorithm. An investigational study shows an objective-function improvement of 13%. The time complexity of the hybrid placement algorithm is O(N2). |
| |
| Keywords: | evolutionary algorithm genetic algorithm multi-objective optimization VLSI design VLSI placement |
|
|
