HYBRID BIOINSPIRED ALGORITHM FOR PLACING BASIC STANDARD LIBRARY ELEMENTS WHEN DESIGNING A TOPOLOGY VLSI

  • О.B. Lebedev Southern Federal University
  • B.K. Lebedev Southern Federal University
  • A.E. Lebedinsky Southern Federal University
Keywords: VLSI, placement of standard cells, one-dimensional packaging, genetic search, particle swarm, affine search space, hybridization, optimization

Abstract

A hybrid algorithm is proposed for locating basic standard library elements in the design of topology of a semi-custom VLSI using the one-dimensional packaging method based on the integration of swarm and genetic algorithms. In the work, as a solution interpretation - a data structure that carries information about packaging (placement), a sequence of elements (priority list) is used, which determines the order of their packaging. As a decoder, the standard packaging procedure (SPP) is used. The interpretation of the placement problem, which is generated by the swarm and genetic algorithms, is an ordered list that includes all cells, with its division into parts. Each part includes vertices corresponding to elements placed in a ruler (block). The number of parts serves as an estimate of the solution. The interpretation of the solution generated by the algorithms is the chromosome, whose structure is identical to the list structure. The list is divided into parts as a result of decoding. We describe the search procedures in the decision space, the mechanisms of behavior of the modernized swarm of particles and genetic search. In contrast to the canonical paradigm of the swarm algorithm, an approach to constructing a modified particle swarm paradigm is proposed, which makes it possible to simultaneously use chromosomes with discrete integer parameter values in a genetic algorithm and in a particle swarm algorithm. The operator of a directed mutation (ОDМ), the essence of which consists in changing the integer values of genes in the chromosome, acts as an analogue of speed when moving. In contrast to the canonical paradigm of the swarm algorithm, an approach to constructing a modified particle swarm paradigm is proposed, which makes it possible to simultaneously use chromosomes with discrete integer parameter values in a genetic algorithm and in a particle swarm algorithm. As an analogue of speed when moving particles, there is a directed mutation operator (ОDМ), the essence of which is to change the integer values of genes in the chromosome. This reduced the combinatorial complexity of the problem. This reduced the combinatorial complexity of the problem. For the experiments were used well-known test problems presented in the library of OR-objects - (OR-Library Beasley). The temporal complexity of the algorithm, obtained experimentally, coincides with theoretical studies and for the considered test problems it is O (n2)-O (n3). The developed algorithm allowed us to obtain optimal solutions for all tasks of the set.

References

1. Месягутов М.А., Мухачева Э.А., Белов Г.Н., Шайтхауэр Г. Упаковка одномерных контейнеров с продолженным выбором идентичных предметов: точный метод поиска оптимального решения. – М.: Наука. Автоматика и телемеханика, – № 1, – 2011. – С. 154-173.
2. Потарусов Р.В., Курейчик В.М. Проблема одномерной упаковки элементов // Известия ТРТУ. Изд-во ТРТУ, – №8, – 2006. – C. 88 – 93.
3. Ross P., Marin-Blazquez J.G., Schulenburg, S., and Hart E. Learning a Procedure That Can Solve Hard Bin-Packing Problems: A New GA-Based Approach to Hyper-heurstics // Proceeding of the Genetic and Evolutionary Computation Conference, GECCO 2003, Chicargo, Illinois, USA, – 2003. – рр. 1295-1306.
4. Gupta J.N. and Ho J.C. A New Heuristic Algorithm for the One-dimensional Bin-packing Problem, Production Planning & Control, – №10, – 1999. – рр. 598-603.
5. Levine J. and Ducatelle F. Ant Colony Optimization and Local Search for Bin Packing and Cutting Stock Problems. Centre for Intelligent Systems and their Applications, School of Informatics, University of Edinburgh, – 2003. – рр. 389-401.
6. Fleszar, K. and Hindi, K.S. New Heuristics for One-dimensional Bin-packing, Computers & Operations Research. – № 29, – 2002. – рр. 821-839.
7. Alvim Adriana C.F., Glover Fred S., Ribeiro Celso C. and Aloise Dario J. Local search for the bin packing problem // Journal of Heuristics. – № 10, – 2004. – рр. 205–229.
8. Курейчик В.М., Лебедев Б.К., Лебедев О.Б. Поисковая адаптация: теория и практика. – М.: Физматлит, – 2006. – 288 с.
9. Engelbrecht A.P. Fundamentals of Computational Swarm Intelligence. John Wiley & Sons, Chichester, UK, – 2005. – 235 р.
10. Карпенко А.П. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновленные природой: Учебное пособие – М: Издательство МГТУ им. Н.Э. Баумана, –2014. – 448 с.
11. Курейчик В.М., Лебедев Б.К., Лебедев О.Б. Решение задачи размещения на основе эволюционного моделирования. // Известия РАН. Теория и системы управления. – №4, – 2007. – С. 78-90.
12. M. Clerc. Particle Swarm Optimization. ISTE, London, UK, – 2006. – 248 р.
13. Лебедев О.Б. Модели адаптивного поведения муравьиной колонии в задачах проектирования. - Таганрог: Изд-во ЮФУ, 2013. – 199 с.
14. Lebedev B.K., Lebedev O.B., Lebedeva E.O. One-Dimensional swarm algorithm packaging // International Conference Information Technologies in Business and Industry 2018. Journal of Physics: Conference Series, Volume 1015, Enterprise Information systems. 2018.
15. Лебедев Б.К., Лебедев О.Б., Лебедев В.Б. Гибридизация роевого интеллекта и генетической эволюции на примере размещения. ЭЛЕКТРОННЫЙ НАУЧНЫЙ ЖУРНАЛ: ПРОГРАММНЫЕ ПРОДУКТЫ, СИСТЕМЫ И АЛГОРИТМЫ. DOI: 10.15827/2311-6749.25.280. http://swsys-web.ru/hybridization-of-swarm-intelligence-and-genetic-evolution.html.
16. Valerio de Carvalho J.M. Exact Solution of Bin-packing Problems Using Column Generation and Branch-and-bound //Annals of Operations Research. – № 86, – 1999. – рр. 629-659.
Published
2019-09-24
Issue
No 3 (2019)
Section
SECTION I. INFORMATION PROCESSING ALGORITHMS.