ГЕНЕТИЧЕСКИЙ АЛГОРИТМ ПЛАНИРОВАНИЯ РАЗМЕЩЕНИЯ СБИС

V.I. Danilchenko; Виктор Михайлович Курейчик

V.I. Danilchenko ЮФУ, ИКТИБ
Виктор Михайлович Курейчик ЮФУ, ИКТИБ

Keywords: genetic algorithm, placement of VLSI elements, optimization, segregation operator, crossmutation operator.

Abstract

The paper deals with the problem of solving the problem of placement in the design of electronic equipment. The task belongs to the class NP-complete and for it there is no exact polynomial algorithm. The purpose of this work is to find ways to optimize the planning of the placement of VLSI using a modified genetic algorithm. The relevance of the work lies in the fact that the modified genetic algorithm used allows to improve the quality of placement planning. Scientific novelty is the development of a modified genetic algorithm. The modified genetic algorithm uses knowledge about the problem being solved, which makes it possible to quickly obtain effective local solutions. The statement of the problem in this paper is as follows: to optimize the placement of the VLSI by applying the genetic algorithm, to minimize empty space, thereby reducing the size of the site for placement. The principal difference from the known algorithms in the use of new genetic operators: segregation, cross-switching. The results of the work are confirmed by an experiment conducted on test functions for optimization algorithms. Based on the experiments performed, it should be noted that such an algorithm has the best performance when optimizing the VLSI layout. The placement area decreased from 9.14 μm2 to 7.56 μm2. The practical applicability of this algorithm is relevant in search and optimization problems.

Keywords - genetic algorithm, placement of VLSI elements, optimization, segregation operator, crossmutation operator.

References

1 Данильченко В.И., Курейчик В.М., Классификация и анализ методов решения задачи размещения СБИС // Информатика, вычислительная техника и инженерное образование. Вып. 1. Изд-во Таганрог, 2018г.
2. Гладков Л.А., Курейчик В.В., Курейчик В.М., Генетические алгоритмы. – М.: Физматлит, 2006, 2010. – 386 с.
3. Wu Y., Jiang H., Zou M., The Research on Fuzzy PID Control of the Permanent Magnet Linear Synchronous Motor // Physics Procedia. – 2012. – Vol. 24. – P. 1311-1318.
4. Лебедев Б.К., Лебедев О.Б., Методы размещения: Монография. – Таганрог: Изд-во ТРТУ, 2006.
5. Запорожец Д.Ю., Кравченко Ю.А., Лежебоков А.А., Способы интеллектуального анализа данных в слож¬ных системах // Известия Кабардино-Балкарского научного центра РАН. – 2013. – № 3. – С. 52.
6. The International Technology Roadmap for Semiconductors report, 2012. URL: http://www.itrs.net/Links/2012ITRS/2012Chapters/2012Overview.pdf (Дата обращения: 2019).
7.Рутковский Лешек. Искусственные нейронные сети. Теория и практика. – М.: Горячая линия – Телеком, 2010 – 425.
8. Pham D.T., Ghanbarzadeh A., Koç E., Otri S., Rahim S., Zaidi M., The Bees Algorithm. 2008.
9. Кулиев Э.В., Заруба Д.В., Работа гибридного поиска размещения компонентов СБИС // Труды молодых ученых Южного федерального университета и Южного научного центра РАН «Высокопроизводительные вычислительные системы». Вып. 2. Изд-во Ростов-на-Дону – Таганрог, 2012. – С. 43-46.
10. Норенков И.П., Арутюнян Н.М., Эволюционные методы в задачах выбора проектных решений // Научно-техническое издание МГТУ им. Н.Э. Баумана «Наука и образование». – 2007. – № 9.
11. Кулиев Э.В., Задача размещения элементов ЭВА с использованием генетического алгоритма и алгоритма пчелиной колонии // Труды конгресса по интеллектуальным системам и информационным технологиям «IS–IT’12». Научное издание в 4-х т. Т. 3. – М.: Физматлит, 2012. – С. 99-104.
12. Михеев М. А. Основы теплопередачи - Изд. 3-репринтное. – Москва : Бастет, 2010. – 342 с.
13. HamedBeirami, Ali ZargarShabestari, Mohammad Mahdi Zerafat., Optimal PID plus fuzzy controller design for a PEM fuel cell air feed system using the self-adaptive differential evolu-tion algorithm // International journal of hydrogen energy. – 10 August 2015. – Vol. 40, Issue 30. – P. 9422-9434.
14. Sivaranjani, P. and Senthilkumar, A., Thermal-Aware Non-Slicing VLSI Floorplanning Using a Smart Decision-Making PSO-GA Based Hybrid Algorithm. Journal of Circuits, Systems, and Signal Processing, 34 (2015), 3521-3542. http://dx.doi.org/10.1007/s00034-015-0020-x
15. Wang, L. Fast Algorithms for Thermal-Aware Floorplanning. Journal of Circuits, Systems, and Computers, 23, (2014), Article ID: 1450098. http://dx.doi.org/10.1142/s0218126614500984
16. Cadence, “Digital Implementation and Sign-off Flow,” in Rapid Adoption Kits. [Online]. URL: http://support.cadence.com/. (Дата обращения: 2019).
17. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построениеианализ– 3 изд. –М.: Вильямс, 2014 –1328с.
18. More Than Moore’s-3D-IC Economics and Design Enablement // Cadence design systems, 2013.
URL:http://www.semi.org/en/sites/semi.org/files/docs/6SiP%20Global%20Summit%203DIC%20Technology%20Forum%20_%20Brandon%20Wang.pdf(Дата обращения: 22.01.2019).
19. Иванова Е.Н. Системы проектирования. Тенденции мирового рынка САПР СБИС // Электроника: Наука, Технология, Бизнес. – 2006.
20. Ковалев А.В. Технологии энергосбережения в микроэлектронных устройствах // Монография. Таганрог: Изд-во ТТИ ЮФУ, 2009. – 100 с.