КО-ЭВОЛЮЦИОННЫЙ АЛГОРИТМ РАЗМЕЩЕНИЯ НА ОСНОВЕ ВЗАИМОДЕЙСТВИЯ СУБПОПУЛЯЦИЙ, ОТЛИЧАЮЩИХСЯ СТРАТЕГИЯМИ ПОИСКА

  • О. Б. Лебедев Южный федеральный университет
  • А.А. Жиглатый Южный федеральный университет
Ключевые слова: СБИС, размещение, роевой интеллект, муравьиный алгоритм, адаптивное поведение, ко-эволюция, субпопуляция, оптимизация

Аннотация

Разработана новая методология и метод размещения элементов СБИС, отличающиеся
тем, что решение задачи размещения основывается на использовании фиксированного порядка
выбора позиций, ориентированного на эффективное решение задачи размещения, и эвристиче-
ской процедуры распределения элементов по позициям, позволяющие снизить общую трудоем-
кость, и повысить качество решения. Процесс формирования списка позиций на коммутацион-
ном поле осуществляется с использованием механизмов волнового алгоритма. В основу выбора
окончательного списка положен принцип построения маршрута с минимальной оценкой сум-
марной линейной длины расстояний между позициями маршрута. Для решения задачи разме-
щения разработан поисковый алгоритм на основе модифицированного метода муравьиной ко-
лонии. Для исключения преждевременной сходимости и локализации глобального экстремума
задачи разработка алгоритма производилась на основе ко-эволюционного подхода. Архитекту-
ра ко-эволюционного алгоритма размещения разработана на основе парадигмы муравьиного
алгоритма. В пространстве поиска субпопуляции параллельно реализуют четыре стратегии
оптимизации. В работе процесс ко-эволюции реализован на основе взаимодействия субпопуля-
ций, отличающихся стратегиями поиска. Отличительной особенностью используемого ко-
эволюционного подхода является то, что субпопуляции решений фактически являются вирту-
альными. Процесс ко-эволюции реализуется одной популяцией агентов Z путем последователь-
ного формирования и слияния, виртуальных субпопуляций решений в одну популяцию. В работе
решение задачи размещения направлено на повышение трассируемости посредством минимизации ресурсов, требуемых для реализации соединений. Существенный вклад в минимизацию
пространственной и временной сложности поисковой процедуры внесли: использование вирту-
альными субпопуляциями общей эволюционной памяти, общего графа поиска решений, форми-
рование единой интерпретации решения в виде маршрута на полном ориентированном графе с
бинарными ориентированными ребрами. Тестирование производилось на бенчмарках
19s, PrimGA1, PrimGA2. Результаты по сравнению с существующими алгоритмами улучшены
на 7-8%. Вероятность получения глобального оптимума составила 0.96. В среднем решения
отличаются от оптимального менее, чем на 1.5%. Временная сложность алгоритма при фик-
сированных значениях размера популяции и количества генераций составляет О(n). Общая вре-
менная сложность гибридного алгоритма составляет О(n2)–О(n3).

Литература

1. Tuchin A.V., Bormontov E.N., Ponomarev K.G. Vvedenie v sistemy avtomatizirovannogo
proektirovaniya integral'nykh mikroskhem [Introduction to computer-aided design systems for
integrated circuits]. Voronezh: Izdatel'skiy dom VGU, 2017, 110 p.
2. Kazennov G.G. Osnovy proektirovaniya integral'nykh skhem i system [Basics of designing
integrated circuits and systems]. Moscow: Binom. Laboratoriya znaniy, 2010, 295 p.
3. Lebedev B.K., Lebedev O.B., Lebedev V.B. Metody, modeli i algoritmy razmeshcheniya
[Methods, models and placement algorithms]. Rostov-on-Don: Izd-vo YuFU, 2015, 150 p.
4. Lebedev B.K., Lebedev O.B. Gibridnyy bioinspirirovannyy algoritm razmeshcheniya bazovykh
standartnykh bibliotechnykh elementov pri proektirovanii topologii poluzakaznoy SBIS [Hybrid
bioinspired algorithm for placing basic standard library elements in the design of the topology
of a semi-custom VLSI], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering
Sciences], 2019, No. 3, pp. 97-110.
5. Karpenko A.P. Sovremennye algoritmy poiskovoy optimizatsii. Algoritmy, vdokhnovlennye
prirodoy: ucheb. posobie [Modern search engine optimization algorithms. Algorithms inspired
by nature: textbook]. Moscow: Izd-vo MGTU im. N.E. Baumana, 2016, 448 p.
6. Vorob'eva E.Yu., Karpenko A.P., Seliverstov E.Yu. Ko-gibridizatsiya algoritmov roya chastits
[Co-hybridization of particle swarm algorithms], Nauka i obrazovanie [Science and Education],
2012, No. 4, pp. 28-35.
7. Lebedev O.B. Raspredelenie resursov na osnove gibridnykh modeley roevogo intellekta [Resource
distribution based on hybrid models of swarm intelligence], Nauchno-tekhnicheskiy
vestnik informatsionnykh tekhnologiy, mekhaniki i optiki [Scientific and technical bulletin of
information technologies, mechanics and optics], 2017, No. 6, pp. 1063-1073.
8. Roze K., Radchenko D. Platforma Synopsys dlya proektirovaniya tsifrovykh sistem – novyy
uroven' tekhnologiy proektirovaniya SnK [Synopsys platform for designing digital systems – a
new level of SoC design technologies], Elektronika [ELECTRONICS], 2018, No. 2, pp. 122-141.
9. Lebedev O.B. Modeli adaptivnogo povedeniya murav'inoy kolonii v zadachakh
proektirovaniya [Models of adaptive behavior of an ant colony in design problems]. Taganrog:
Izd-vo YuFU, 2013, 199 p.
10. Sur-Kolay S., Bishnu A., Das S., Nandy S.C., Bhattacharjee S. FPGA placement using spacefilling
curves: Theory meets practice, ACM Trans. Embed. Comput. Syst., 2009, Vol. 9, No. 2,
pp. 1-23.
11. Yang X., Choi B.-K., Sarrafzadeh M. Routability-driven white space allocation for fixed-die
standard-cell placement, IEEE Trans. on Computer-Aided Design of Integrated Circuits and
Systems, 2003, Vol. 22 (4), pp. 410-419.
12. Lebedev B.K., Lebedev O.B., Zhiglatyy A.A. Razmeshchenie elementov SBIS na osnove modeley
roevogo intellekta [Placement of VLSI elements based on swarm intelligence models], Problemy
razrabotki perspektivnykh mikro- i nanoelektronnykh sistem: Sb. trudov pod obshch. red.
akademika RAN A.L. Stempkovskogo [Problems of development of promising micro- and
nanoelectronic systems. Collection of works under the total. ed. Academician of the Russian Academy
of Sciences A.L. Stempkovsky]. Moscow: IPPM RAN, 2020, pp. 118-126.
13. Cong J., Romesis M., Xie M. Optimality, Scalability and Stability Study of Partitioning and
Placement Algorithms, Proc. of the International Symposium on Physical Design. Monterey,
CA, 2003, pp. 88-94.
14. Sherwani N.A. Algorithms for VLSI Physical Design Automation. 3d ed. – Kluwer Academic
Publisher. USA, 2013. – 572 p.
15. Mourelle M. Swarm intelligent systems. Berlin: Heidelberg: Springer Verlag, 2006, 217 p.
16. Norenkov I.P. Osnovy avtomatizirovannogo proektirovaniya: uchebnik [Fundamentals of
computer-aided design: textbook]. Moscow: Izd-vo MGTU imeni N.E. Baumana, 2006, 336 p.
17. Wang M., Yang X., Sarrafzadeh M. Dragon2000: Standard-cell Placement Tool for Large Industry
Circuits, ICCAD 2000, pp. 260-263.
18. Caldwell A.E., Kahng A.B., Markov I.L. Can Recursive Bisection Alone Produce Routable
Placements?, DAC 2000, pp. 477-482.
19. Cadence design systems, Inc. QPlace version 5.1.55, compiled on 10/25/1999. Envisia ultraplacer
reference.
20. IBM-PLACE 2.0 benchmark suits. Available at: http://er.cs.ucla.edu/benchmarks/-ibmplace2/
bookshelf/ibm-place2-all-bookshelf-nopad.tar.gz.
21. Adya S.N. ISPD02 IBM-MS Mixed-size Placement Benchmarks. Available at:
http://vlsicad.eecs.umich.edu/BK/ISPD02bench/.
Опубликован
2023-02-17
Выпуск
Раздел
РАЗДЕЛ I. МОДЕЛИ И МЕТОДЫ ОБРАБОТКИ ИНФОРМАЦИИ