Личный кабинет
Подробное описание документа
Лебедев Б. К.
Модифицированный муравьиный алгоритм планирования СБИС на базе композитной модели пространства решений / Лебедев Б. К., Лебедев О. Б., Жиглатый А. А. - DOI 10.18698/0236-3933-2019-5-49-63 // Вестник МГТУ им. Н. Э. Баумана. Сер. Приборостроение. - 2019. - № 5. -
Скачать документ
Сформирован план кристалла путем рекурсивного использования "гильотинного разреза". Задать план это: задать структуру дерева разрезов, т. е. последовательность бинарных разрезов; для внутренних вершин дерева указать тип разреза H или V; пронумеровать листья дерева и указать ориентацию модулей. Структуру бинарного дерева разрезов можно задать, используя на базе алфавита A={М, TR} польское выражение, где множество букв М = {mi|i = 1, 2, ...., nM} соответствует листьям дерева разрезов (областям), а множество R = {H, V} соответствует разрезам. Предложен способ и методы решения задач планирования СБИС на основе модифицированной муравьиной колонии. Задача синтеза дерева разрезов плана с выбором типов разрезов, идентификацией и ориентацией модулей сведена к задаче формирования модифицированного польского выражения с идентификацией элементов на композитной модели пространства решений, включающей в себя множество альтернативных вершин. Для отражения коллективной эволюционной памяти в течение жизни популяции муравьев и для формирования решения задачи использован полный граф G = (X, U) с альтернативными состояниями вершин. Каждая вершина может находиться в одном из двух альтернативных состояний (α или β), соответствующих ориентации модуля или типу разреза. Задача синтеза польского выражения сформулирована как задача поиска минимального по стоимости маршрута на графе поиска решений G = (X, U). Отличительная особенность заключается в том, что при построении маршрута одновременно с выбором вершины xi∈X осуществляется выбор состояния этой вершины. Временная сложность алгоритма составляет O(n2). Эксперименты показали, что при больших размерностях временные показатели разработанного алгоритма превосходят показатели сравниваемых алгоритмов при лучших значениях целевой функции Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (грант РФФИ № 17-07-00997а)
Статья опубликована в следующих изданиях
№ 5. - 2019.
