Open AccessHybrid genetic‐paired‐permutation algorithm for improved VLSI placement
Author(s) -
Ignatyev Vladimir V.,
Kovalev Andrey V.,
Spiridonov Oleg B.,
Kureychik Viktor M.,
Ignatyeva Alexandra S.,
Safronenkova Irina B.
Publication year - 2021
Publication title -
etri journal
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.295
H-Index - 46
eISSN - 2233-7326
pISSN - 1225-6463
DOI - 10.4218/etrij.2019-0412
Subject(s) - very large scale integration , permutation (music) , computer science , algorithm , genetic algorithm , hybrid algorithm (constraint satisfaction) , set (abstract data type) , artificial intelligence , machine learning , constraint satisfaction , probabilistic logic , acoustics , programming language , embedded system , constraint logic programming , physics
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 ( N 2 ).