ПОДХОД К КОДИРОВАНИЮ РЕШЕНИЙ В ЭВОЛЮЦИОННЫХ МЕТОДАХ ДЛЯ СОЗДАНИЯ ИНСТРУМЕНТАЛЬНОЙ ПЛАТФОРМЫ ПРОЕКТИРОВАНИЯ

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

Аннотация

Рассмотрены актуальные вопросы и проведен анализ проблемы трехмерной инте-
грации и трехмерного моделирования, возникающей на этапе конструкторского проекти-
рования в ходе решения задачи оптимального планирования компонентов больших и сверх-
больших интегральных схем и корпусных устройств электронной вычислительной аппара-
туры. Представлены и достаточно детально описаны основные преимущества примене-
ния принципов трехмерной интеграции, позволяющие эффективно организовывать произ-
водство персонифицированной электроники, оптимально планировать конфигурацию
больших и сверхбольших интегральных схем с учетом тепловых и энергетических характе-
ристик. В ходе выполнения исследований авторами разработан подход к кодированию ре-
шений на основе интеллектуального механизма, который характеризуется наличием
встроенных средств контроля допустимых решений. Одним из таких средств, экспери-
ментально доказавших свою эффективность, является встроенный механизм «смертель-
ных мутаций», учитывающий статусы генов и заранее заданные ограничения на итоговую
конфигурацию корпуса проектируемого устройства. В работе предложен ряд общих под-
ходов и конкретных алгоритмов решения задачи планирования, основывающихся на ре-
зультатах исследований авторского коллектива и современных подходах к решению
NP-полных задач. Важнейшим практически значимым результатом исследований обозна-
ченной проблемы является разработанная программно-инструментальная платформа
проектирования на современном кроссплатформенном языке программирования Java. Вы-
бранная технология разработки позволяет использовать все основные достоинства со-
временных многоядерных и многопроцессорных архитектур, по использованию программ-
ной многопоточности для реализации параллельных схем решения комбинаторных задач.
Программно-инструментальная платформа обладает дружественным интерфейсом, что
позволяет эффективно управлять процессом решения задачи планирования компонентовбольших и сверхбольших интегральных схем трехмерной интеграции, путем визуализации
ключевых показателей работы алгоритмов на графиках и в блоках текстовой статисти-
ки. Разработанное прикладное программное обеспечение позволило провести серию вычис-
лительных экспериментов, на основе наборов случайных данных также, как и наборах от-
крытых данных бенчмарков для подобного рода задач. Результаты экспериментальных
исследований позволили подтвердить теоретические оценки временной сложности и эф-
фективности предложенных подходов и алгоритмов, в том числе генетического алгорит-
ма, который использует предложенный в работе новый механизм кодирования решений.

Литература

1. Norenkov I.P. Osnovy avtomatizirovannogo proektirovaniya [Fundamentals of computer-aided
design]. Moscow: Izd-vo MGTU im. N.E. Baumana, 2010, 364 p.
2. Karpenko A.P. Sovremennye algoritmy poiskovoy optimizatsii [Modern search engine optimization
algorithms], Algoritmy, vdokhnovlennye prirodoy: ucheb. posobie [Algorithms inspired
by nature: a textbook]. Moscow: Izd-vo MGTU im. N.E. Baumana, 2014, 474 p.
3. Kureychik V.V., Kureychik V.M., Rodzin S.I. Teoriya evolyutsionnykh vychisleniy [Theory of
evolutionary computation]. Moscow: Fizmatlit, 2012, 260 p.
4. Kureychik V.V., Zaporozhets D.Yu. Sovremennye problemy pri razmeshchenii elementov SBIS
[Current problems in placing VLSI elements], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya
SFedU. Engineering Sciences], 2011, No. 7 (120), pp. 68-73.
5. Lezhebokov A.A., Kravchenko Yu.A., Pashchenko S.V. Osobennosti ispol'zovaniya tekhnologii
dopolnennoy real'nosti dlya podderzhki obrazovatel'nykh protsessov [Features of using augmented
reality technology to support educational processes], Otkrytoe obrazovanie [Open education],
2014, No. 3 (104), pp. 49-54.
6. Lezhebokov A.A., Kuliev E.V. Tekhnologii vizualizatsii dlya prikladnykh zadach
intellektual'nogo analiza dannykh [Visualization technologies for data mining applications],
Izvestiya Kabardino-Balkarskogo nauchnogo tsentra RAN [Izvestiya Kabardino-Balkar scientific
center of the Russian Academy of Sciences], 2019, No. 4 (90), pp. 14-23.
7. Kureychik V.M., Kureychik V.V. Geneticheskiy algoritm razbieniya grafa [Genetic algorithm for
graph splitting], Izvestiya Rossiyskoy akademii nauk. Teoriya i sistemy upravleniya [Proceedings of
the Russian Academy of Sciences. Theory and control systems], 1999, No. 4, pp. 79-87.
8. Kuliev E.V., Kravchenko Yu.A., Loginov O.A., Zaporozhets D.Yu. Metod intellektual'nogo
prinyatiya effektivnykh resheniy na osnove bioinspirirovannogo podkhoda [Method of intelligent
decision-making based on a bioinspired approach], Izvestiya Kabardino-Balkarskogo
nauchnogo tsentra RAN [Izvestiya Kabardino-Balkar scientific center of the Russian Academy
of Sciences], 2017, No. 6-2 (80), pp. 162-169.
9. Kuliev E.V., Lezhebokov A.A., Kravchenko Yu.A. Roevoy algoritm poiskovoy optimizatsii na
osnove modelirovaniya povedeniya letuchikh myshey [Swarm algorithm search engine optimization
is based on modeling the behavior of bats], Izvestiya YuFU. Tekhnicheskie nauki
[Izvestiya SFedU. Engineering Sciences], 2016, No. 7 (180), pp. 53-62.
10. Kuliev E.V., Lezhebokov A.A. O gibridnom algoritme razmeshcheniya komponentov SBIS
[About a hybrid VLSI component placement algorithm], Izvestiya YuFU. Tekhnicheskie nauki
[Izvestiya SFedU. Engineering Sciences], 2012, No. 11 (136), pp. 188-192.
11. Bova V.V., Lezhebokov A.A., Gladkov L.A. Problem-oriented algorithms of solutions search
based on the methods of swarm intelligence, World Applied Sciences Journal, 2013, Vol. 27
(9), pp. 1201-1205.
12. Zaruba D., Zaporozhets D., Kureichik V. VLSI placement problem based on ant colony optimization
algorithm, Advances in Intelligent Systems and Computing, 2016, Vol. 464, pp. 127-133.
13. Kureichik V., Kureichik V., Bova V. Placement of VLSI fragments based on a multilayered
approach, Advances in Intelligent Systems and Computing, 2016, Vol. 464, pp. 181-190.
14. Kureichik V.V., Zaruba D.V. The bioinspired algorithm of electronic computing equipment
schemes elements placement, Advances in Intelligent Systems and Computing, 2015, Vol. 347,
pp. 51-58.
15. Gladkov L.A., Gladkova N.V., Gordienko V.N. Modifitsirovannyy geneticheskiy algoritm resheniya
zadachi komponovki blokov EVA [Modified genetic algorithm for solving the problem of EVA
block layout], Informatika, vychislitel'naya tekhnika i inzhenernoe obrazovanie [Computer science,
computer engineering and engineering education], 2015, No. 4 (24), pp. 18-27.
16. Kureychik V.V., Kureychik Vl.Vl. Bioinspirirovannyy algoritm razbieniya skhem pri proektirovanii
SBIS [Bioinspired algorithm for splitting circuits in VLSI design], Izvestiya YuFU. Tekhnicheskie
nauki [Izvestiya SFedU. Engineering Sciences], 2013, No. 7 (144), pp. 23-29.
17. Kureychik V.V., Kureychik V.M., Gladkov L.A., Sorokoletov P.V. Bioinspirirovannye metody v
optimizatsii [Bioinspired methods in optimization]. Moscow: Fizmalit, 2009, 384 p.
18. Kureychik V.V., Zaruba D.V., Zaporozhets D.Yu. Bioinspirirovannyy algoritm komponovki
blokov EVA na osnove modifitsirovannoy raskraski grafa [Bioinspired algorithm for EVA
block layout based on modified graph coloring], Izvestiya YuFU. Tekhnicheskie nauki
[Izvestiya SFedU. Engineering Sciences], 2015, No. 4 (165), pp. 6-14.
19. Kureychik V.V., Kureychik Vl.Vl., Bova V.V. Bioinspirirovannyy poisk v zadachakh
konstruktorskogo proektirovaniya i optimizatsii [Bioinspired search in the problems of design
design and optimization], Informatsionnye tekhnologii v nauke, obrazovanii i upravlenii [Information
technologies in science, education and management], ed. by prof. E.L. Gloriozova,
2015, pp. 427-432.
20. Kuliev E.V., Lezhebokov A.A., Dukkardt A.N. Podkhod k issledovaniyu okrestnostey v roevykh
algoritmakh dlya resheniya optimizatsionnykh zadach [Approach to neighborhood research in
swarm algorithms for solving optimization problems], Izvestiya YuFU. Tekhnicheskie nauki
[Izvestiya SFedU. Engineering Sciences], 2014, No. 7 (156), pp. 15-25.
21. Kuliev E.V., Lezhebokov A.A. Issledovanie kharakteristik gibridnogo algoritma razmeshcheniya
[The study of the characteristics of hybrid positioning algorithm], Izvestiya YuFU. Tekhnicheskie
nauki [Izvestiya SFedU. Engineering Sciences], 2013, No. 3 (140), pp. 255-261.
Опубликован
2020-07-20
Выпуск
Раздел
РАЗДЕЛ III. ЭВОЛЮЦИОННОЕ МОДЕЛИРОВАНИЕ