Модифицированный муравьиный алгоритм планирования СБИС на базе композитной модели пространства решений

Сформирован план кристалла путем рекурсивного использования "гильотинного разреза". Задать план это: задать структуру дерева разрезов, т. е. последовательность бинарных разрезов; для внутренних вершин дерева указать тип разреза H или V; пронумеровать листья дерева и указать ориентацию модулей. Структуру бинарного дерева разрезов можно задать, используя на базе алфавита A={М, TR} польское выражение, где множество букв М = {m_i|i = 1, 2, ...., n_M} соответствует листьям дерева разрезов (областям), а множество R = {H, V} соответствует разрезам. Предложен способ и методы решения задач планирования СБИС на основе модифицированной муравьиной колонии. Задача синтеза дерева разрезов плана с выбором типов разрезов, идентификацией и ориентацией модулей сведена к задаче формирования модифицированного польского выражения с идентификацией элементов на композитной модели пространства решений, включающей в себя множество альтернативных вершин. Для отражения коллективной эволюционной памяти в течение жизни популяции муравьев и для формирования решения задачи использован полный граф G = (X, U) с альтернативными состояниями вершин. Каждая вершина может находиться в одном из двух альтернативных состояний (α или β), соответствующих ориентации модуля или типу разреза. Задача синтеза польского выражения сформулирована как задача поиска минимального по стоимости маршрута на графе поиска решений G = (X, U). Отличительная особенность заключается в том, что при построении маршрута одновременно с выбором вершины x_i∈X осуществляется выбор состояния этой вершины. Временная сложность алгоритма составляет O(n²). Эксперименты показали, что при больших размерностях временные показатели разработанного алгоритма превосходят показатели сравниваемых алгоритмов при лучших значениях целевой функции

Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (грант РФФИ № 17-07-00997а)

Литература

[1] Курейчик В.М., Лебедев Б.К., Лебедев В.Б. Планирование сверхбольших интегральных схем на основе интеграции моделей адаптивного поиска. Известия РАН. Теория и системы управления, 2013, № 1, с. 84--101.

[2] Лебедев Б.К., Лебедев О.Б., Лебедев В.Б. Методы, модели и алгоритмы размещения. Ростов-на-Дону, Изд-во ЮФУ, 2015.

[3] Лебедев О.Б. Модели адаптивного поведения муравьиной колонии в задачах проектирования. Ростов-на-Дону, Изд-во ЮФУ, 2013.

[4] Qi L., Xia Y., Wang L. Simulated annealing based thermal-aware floorplanning. ICECC, 2011, pp. 463--466. DOI: 10.1109/ICECC.2011.6067654

[5] Chen J., Zhu W. A hybrid genetic algorithm for VLSI floorplanning. ICIS, 2010, pp. 128--132. DOI: 10.1109/ICICISYS.2010.5658785

[6] Карпенко А.П. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновленные природой. М., Изд-во МГТУ им. Н.Э. Баумана, 2014.

[7] Chen G., Guo W., Chen Y. A PSO-based intelligent decision algorithm for VLSI floorplanning. Soft Comput., 2010, vol. 14, iss. 12, pp. 1329--1337. DOI: https://doi.org/10.1007/s00500-009-0501-6

[8] Banerjee P., Sangtani M., Sur-Kolay S. Floorplanning for Partially Reconfigurable FPGAs. IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., 2011, vol. 30, iss. 1, pp. 8--17. DOI: 10.1109/TCAD.2010.2079390

[9] Ерошенко И.Н. Разработка генетического алгоритма кластерного планирования СБИС. Известия ЮФУ. Технические науки, 2010, № 7, с. 54--60.

[10] Лебедев Б.К., Лебедев В.Б. Планирование на основе роевого интеллекта и генетической эволюции. Известия ЮФУ. Технические науки, 2009, № 4, с. 25--33.

[11] Курейчик В.В., Курейчик В.В. Архитектура гибридного поиска при проектировании. Известия ЮФУ. Технические науки, 2012, № 7, с. 22--27.

[12] Kureichik V.M., Lebedev B.K., Lebedev O.B. Hybrid evolutionary algorithm of planning VLSI. Proc. GECCO’10. Portland, OR, 2010, рр. 821--822.

[13] Лебедев Б.К., Лебедев О.Б. Биоинспирированные методы планирования кристалла СБИС. Проблемы разработки перспективных микро- и наноэлектронных систем (МЭС), 2014, № 1, с. 171--176.

[14] Лебедев О.Б. Планирование СБИС на основе метода муравьиной колонии. Известия ЮФУ. Технические науки, 2010, № 7, с. 67--73.

[15] Potti S., Pothiraj S. GPGPU implementation of parallel memetic algorithm for VLSI floorplanning problem. In: Nagamalai D., Renault E., Dhanuskodi M. (eds). Trends in Computer Science, Engineering and Information Technology. CCSEIT 2011. Communications in Computer and Information Science, vol. 204. Berlin, Heidelberg, Springer, pp. 432--441. DOI: https://doi.org/10.1007/978-3-642-24043-0_44

[16] Shanavas I.H. et al. Evolutionary algorithmical approach for VLSI floorplanning problem. IJCTE, 2009, vol. 1, no. 4, pp. 461--464. DOI: 10.7763/IJCTE.2009.V1.75

[17] Silvaco Library Platform™. URL: http://www.nangate.com

[18] MCNC: веб-сайт компании. URL: www.mcnc.org (дата обращения: 15.04.2019).

[19] hMetis. URL: http://glaros.dtc.umn.edu/gkhome/metis/hmetis/download (дата обращения: 15.02.2019).

[20] HB Suite. cadlab.cs.ucla.edu: веб-сайт. URL: http://cadlab.cs.ucla.edu/cpmo/HBsuite.html (дата обращения: 15.02.2019).

[21] Ma Q., Young E.F.Y. Multivoltage floorplan design. IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., 2010, vol. 29, iss. 4, pp. 607--617. DOI: 10.1109/TCAD.2010.2042895

[22] Лебедев Б.К., Лебедев О.Б., Лебедева Е.М. Гибридный алгоритм ситуационного планирования траектории на плоскости в условиях частичной неопределенности. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение, 2018, № 1, с. 76--93. DOI: 10.18698/0236-3933-2018-1-76-93