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

В.И. Данильченко; Виктор Михайлович Курейчик

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

Ключевые слова: генетический алгоритм, размещение элементов СБИС, оптимизация, оператор сегрегации, оператор кроссмутации.

Аннотация

В работе рассмотрена проблема решения задачи размещения при проектировании радиоэлектронной аппаратуры. Поставленная задача относится к классу NP-полных и для нее не существует точного полиномиального алгоритма. Цель данной работы заключается в нахождении путей оптимизации планирования размещения СБИС с применением модифицированного генетического алгоритма. Актуальность работы состоит в том, что используемый модифицированный генетический алгоритм позволяет повысить качество планирования размещения. Научная новизна заключается в разработке модифицированного генетического алгоритма. Модифицированный генетический алгоритм использует знания о решающейся задаче, что позволяет быстрее получать эффективные локальные решения. Постановка задачи в данной работе заключается в следующем: оптимизировать размещение СБИС путем применения генетического алгоритма, минимизировать пустое пространство, тем самым сократить габариты площадки для размещения. Принципиальное отличие от известных алгоритмов в использовании новых генетических операторов: сегрегации, кроссмутации. Результаты работы подтверждаются экспериментом, проведенном на тестовых функциях для алгоритмов оптимизации. На основе проведенных экспериментов необходимо отметить, что такой алгоритм обладает лучшими характеристиками при оптимизации размещения СБИС. Площадь размещения уменьшилась с 9,14 мкм² на 7,56 мкм². Практическая применяемость данного алгоритма актуальна в поисковых и оптимизационных задачах.

Ключевые слова – генетический алгоритм, размещение элементов СБИС, оптимизация, оператор сегрегации, оператор кроссмутации.

Литература

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 с.