Перераспределение соединений между выводами возможно в том случае, если выводы являются функционально эквивалентными. Два вывода (или группы) называются функционально эквивалентными, если переключение подходящих к ним цепей не приводит к изменению логической функции схемы. Таким образом, задача перераспределения соединений между выводами сводится к задаче переключения соединений внутри функционально эквивалентных групп выводов [1].

Возможен иерархический подход к задаче перераспределения, когда осуществляется перераспределение групп соединений между эквивалентными группами выводов, не приводящих к изменению логической функции схемы. Задача распределения (или закрепление цепей за выводами) может решаться в процессе планирования СБИС, размещения блоков на кристалле, в процессе глобальной трассировки, при канальной трассировке [2]. Обычно задача решается после выполнения этапа глобальной трассировки [3].

Цель перераспределения заключается в уменьшении плотности областей трассировки, уменьшении длины соединений, уменьшении числа пересечений, повышении степени интеграции и т.п.

В последнее время для решения различных сложных задач, к которым относятся и задачи распределения (или закрепления) цепей за выводами, все чаще используются способы, основанные на применении методов искусственного интеллекта [4–7]. Особенно стремительно растет интерес к разработке алгоритмов, инспирированных природными системами. Одним из новых направлений таких методов являются мультиагентные методы интеллектуальной оптимизации, базирующиеся на моделировании коллективного интеллекта [8, 9]. В работе излагается метод решения задачи распределения соединений между выводами, основанный на моделировании адаптивного поведения муравьиной колонии [10, 11].

Постановка задачи

Изначально свойство эквивалентности присуще выводам, являющимся входами конъюнктора (или дизъюнктора). Пусть V={v_i| i= 1, 2,…, n} – входы и w – выход конструктивного элемента. Действительно, в силу коммутативного закона значение функции, являющейся конъюнкцией (или дизъюнкцией) нескольких переменных, не зависит от перестановки этих переменных. Например,y = x₁&x₂&x₃=x₂&x ₃&x₁.

Рассмотрим процесс переключения соединений между эквивалентными группами выводов.

Пусть в качестве исходных данных имеется некоторая принципиальная схема, реализуемая набором конструктивных элементов (КЭ), соединенных между собой электрическими соединениями. В качестве КЭ рассматриваются фрагменты топологии, реализующие логические функции И, ИЛИ, НЕ.

Задача закрепления соединений за выводами разбивается на два класса: общий и специальный.

Обозначим через V множество всех входов и выходов КЭ. В общем случае допускается любое, не приводящее к изменению логической функции схемы перераспределение соединений между выводами множества V.

Наибольший интерес представляет задача перераспределения соединений между выводами специального класса. К такому типу относится задача перераспределения соединений в канале или коммутационном блоке. Перераспределение соединений производится перед фазой детальной трассировки и нацелено на уменьшение длины соединений внутри канала и плотности канала, что облегчает процесс трассировки [1–3].

Канал представляет собой область, ограниченную верхними и нижними рядами выводов. Выводы имеют сквозную нумерацию слева направо. Не теряя общности, рассмотрим верхний ряд выводов. Пусть к ряду выводов V=<v_i| i=1, 2,…, n> подключена некоторая схема S, размещенная внутри ячеек. Назовем концевые точки цепей, которыми они подсоединяются к выводам, терминалами. Пусть T⁰ = <t_i| i=1, 2 ,…, n> – исходное множество подключенных к выводам терминалов, t_i – номер терминала, подключенного к i-му выводу. Назовем перестановку элементов вектора T ⁰ допустимой, если она получена путем соответствующего переназначения терминалов между эквивалентными выводами или эквивалентными группами выводов. Множество допустимых перестановок составляет пространство решений.

Задача перераспределения терминалов между выводами заключается в нахождении такой допустимой перестановки T^*, при которой критерий имеет наилучшее значение.

Каждая цепь в канале представляется в виде горизонтальных и вертикальных фрагментов, причем длина горизонтальных фрагментов в процессе трассировки не меняется.

Обозначим через L(c_i) длину горизонтальных фрагментов цепи c_i. Величина L( c_i) определяется как расстояние по горизонтали между крайними слева и справа точками распространения c_i в канале. В качестве критерия оптимизации используется суммарная длина горизонтальных фрагментов цепей:

Очень важным показателем является плотность канала. Она определяется следующим образом: через все выводы в двух горизонтальных линейках, ограничивающих область канала, проводятся вертикальные сечения канала. Для каждого j-го сечения рассчитывается число p_j пересекаемых им горизонтальных фрагментов цепей. Средиp_j определяется максимальное p_max:p_max ® ("j)[p_j < p_max]. Величина p_max и будет плотностью канала, используемой в качестве критерия оптимизации F₂.

В качестве третьего критерия оптимизации используется число неустранимых пересечений соединений. Эти пересечения устраняются путем переключения соединений с₁ и с₂ между эквивалентными выводами v₁ и v₂. Для учета всех этих критериев может использоваться аддитивная свертка:

F = k ₁ × F₁ + k₂ × F₂ + k₃ × F_3.

Цель нашего алгоритма в минимизации критериев F₁ , F₂, F₃ и F.

Организация поисковых процедур на основе моделировании адаптивного поведения
муравьиной колонии

Пусть к ряду выводов V=<v_i|i=1, 2,…, n> подключено множество терминалов соединений T =< t_i|i=1, 2, …, n>. Предварительно на основе анализа схемы формируется множество A эквивалентных групп выводов A={A_e|e=1, 2, …, n_e}. A_e={a_ej| j=1, 2, …, n_j} – группа эквивалентных выводов. Необходимо найти допустимую перестановку терминалов T^*, при которой критерий имеет наилучшее значение. В свою очередь, допустимая перестановка терминалов T^* является совокупностью допустимых перестановок терминалов T^*_e, каждая из которых определяет подключение терминалов к соответствующей группе выводов A_e. T^*=È T^*_e, T^*_i Ç T^* _j =Æ.

Для поиска решений формируется семейство полных подграфов G={G_e|e=1, 2, …,n_e}, G_e=(X_e, U_e). Вершины множества X_e соответствуют терминалам множества T^*_e, подключаемым к группе эквивалентных выводов A_e .

Для равномерного распределения муравьев и создания равных стартовых условий формируется композитная структура среды функционирования агентов. Основу композитной структуры среды функционирования составляет интеграция полного и звездного графов. Для этого в состав каждого подграфа G_e=(X_e,U_e) вводится начальная вершина x_0e, которая связывается со всеми вершинами множества X_e. Таким образом, каждый подграфG_e=(X_e,U_e) трансформируется в подграф G_et=(X_et,U_et), где X_et = X_eÈ x_0e, а поиск решений осуществляется на семействе композитных подграфов G_t={G_et|e=1, 2, …,n_e}, G_et=(X_et, U_et).

В общем случае поиск допустимых перестановок терминалов T^*_e в количестве n_e=|A| осуществляется коллективом муравьев Z={z_k|k=1, 2, …, n_k}. На каждой итерации муравьиного алгоритма каждый муравей z_k строит свое конкретное решение. Решением является маршрут M^k=È M^k_e в семействе подграфов G, состоящий из n_e частей. Первая часть M^k₁ маршрута M^k включает все вершины, принадлежащие множеству X_1tÎG_1t, G_1t=(X_1t,U_1t), G _1tÎG_t. Построение M^k₁ начинается с вершины x₀₁. Вторая часть M^k₂ маршрута M^k включает все вершины, принадлежащие множеству X_{2 t}ÎG_2t. Построение M^k₂ начинается с вершины x₀₂ и т.д. Последовательность множества вершин X_e в маршруте M^k_e соответствует перестановке терминалов T^*_e.

Вначале каждый муравей z_k, стартующий из вершины x₀₁ÎX_1t множества X₁, строит первую часть G_t={G_et|e=1, 2, …, n_e}, маршрута M^к, затем переходит в вершину x₀₂ÎX_1t и строит вторую часть M^k₂ маршрута M^k и т.д. Число решений, формируемых муравьями на каждой итерации, равно n. Таким образом, целью муравьиного алгоритма является нахождения лучшего маршрутаM^* на семействе полных подграфов G_t={G_et|e=1, 2, …, n_e}, которому соответствует лучшая перестановка терминалов T^*.

Моделирование поведения муравьев в задаче поиска перестановки терминалов T^* связано с распределением феромона на ребрах семейства графов G. На начальном этапе на всех ребрах семейства графов G откладывается одинаковое (небольшое) количество феромона Φ/v, где v=|ÈU_e|. Параметр Φ задается априори. Процесс поиска решений итерационный. Каждая итерация l включает три этапа. На первом этапе муравей находит решение, на втором этапе откладывает феромон, на третьем осуществляется испарение феромона. В работе используется циклический (ant-cycle) метод муравьиных систем. В этом случае феромон откладывается агентом на ребрах после полного формирования решения. На первом этапе каждой итерации каждый k-й муравей формирует свой собственный маршрут M^k. Процесс построения маршрута M^k многостадийный. На каждой стадии, начиная с вершиныx_0e, строится маршрутM^k_e. Процесс построения маршрута M^k_e пошаговый. На каждом шаге s агент z_k применяет вероятностное правило выбора следующей вершины для включения ее в формируемый маршрут M^k_e(s). Для этого формируется множество вершин V^k(s)ÎX_et,таких, что каждая из вершин x_iÎV^k(t) может быть добавлена в строящийся маршрут M^k_e(s). Пусть u_k(t) – последняя вершина маршрута M^k_e(t). Агент просматривает все вершины x_iÎV^k(t). Для каждой вершины x_iÎV^k(t) рассчитывается параметр f_ik – суммарный уровень феромона на ребре графа G_et, связывающего x_i с вершиной u_k(t).

Вероятность P_ik включения вершины x_iÎV^k(t) в строящийся маршрут M^k_e(t) определяется следующим соотношением:

Агент z_k с вероятностью P_ik выбирает одну из вершин, которая включается в маршрут M^k_e(t).

На втором этапе итерации каждый муравей откладывает феромон на ребрах построенного маршрута.

Количество феромона Dτ_k(l), откладываемое муравьем z_k на каждом ребре построенного маршрута M^k_e(t), определяется следующим образом:

Dτ_k(l) = Φ / F _k(l),                         (1)

где l – номер итерации; Φ – общее количество феромона, откладываемое муравьем на ребрах маршрута M^k_e(t), F _k(l) – целевая функция для решения, полученного муравьем z_k на l-й итерации. Чем меньше F_k(l), тем больше феромона откладывается на ребрах построенного маршрута и, следовательно, тем больше вероятность выбора этих ребер при построении маршрутов на следующей итерации.

После того как каждый агент сформировал решение и отложил феромон, на третьем этапе происходит общее испарение феромона на ребрах семейства графов поиска решений G в соответствии с формулой

f_ik = f_ik(1 – ρ),                           (2)

где ρ – коэффициент обновления.

После выполнения всех действий на итерации находится агент с лучшим решением, которое запоминается. Далее осуществляется переход на следующую итерацию.

Временная сложность этого алгоритма зависит от времени жизни колонии l (число итераций), количества вершин графа n и числа муравьев m и определяется как O( l∙n²∙m).

Алгоритм перераспределения соединений между выводами на основе метода муравьиной колонии формулируется следующим образом.

1. На основе анализа схемы формируются множество эквивалентных групп выводов A={A_e|e=1, 2, …, n_e} и исходное множество подключенных к выводам терминалов цепей. Определяются исходные перестановки терминалов T^*_e, каждая из которых определяет подключение терминалов к соответствующей группе выводов A_e.

2. В соответствии с исходными данными формируется семейство полных подграфов поиска решений G={G_e|e=1, 2, …, n_e}, G преобразуется в семейство G_t={G_et|e=1, 2, …, n_e} .

3. Определяется число муравьев.

4. Задаются начальное значение параметра Φ и число итераций N_l.

5. На всех ребрах семейства полных подграфов G откладывается начальное количество феромона Φ, l=1.

6. На первом этапе l-й итерации на G_t каждым агентом z_k находится маршрут M^k( l).

7. Для каждого маршрута M^k(l) формируется допустимая перестановка терминалов T^k( l).

8. Для каждой допустимой перестановки терминалов T ^k(l) находятся соответствующее ей решение
и значение целевой функции F_k(l) .

9. На ребрах каждого найденного маршрута M^k( l) в семействе полных подграфов G откладывается феромон. Количество феромона, откладываемого каждым агентом, пропорционально F_k(l).

10. На ребрах семейства полных подграфов G выполняется процедура испарения феромона.

11. Выбор лучшего решения, полученного на протяжении всех выполненных итераций.

12. Если все итерации выполнены, конец работы алгоритма, в противном случае переход к пункту 6 для выполнения очередной итерации.

Заключение

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

Экспериментальные исследования проводились на примерах, содержащих до тысячи выводов. Тестирование производилось на бенчмарках. По сравнению с существующими алгоритмами достигнуто улучшение результатов на 6–7 %. Вероятность получения глобального оптимума составила 0,94, а у локально оптимальных решений отклонение от глобального оптимума составило в среднем 1 %. Временная сложность алгоритма, полученная экспериментальным путем, лежит в пределах О(n²)–О(n ³).

Работа выполнена при финансовой поддержке гранта РФФИ № 17-07–00997.

Литература

1. Alpert C.J., Mehta D.P., and Sapatnekar S.S. Handbook of Algorithms for Physical Design Automation. Boston, MA, Auerbach, 2009, 1044 p.

2. Лебедев Б.К. Интеллектуальные процедуры синтеза топологии СБИС. Таганрог: Изд-во ТРТУ, 2003. 107 c.

3. Деньдобренко Б.П., Малика А.С. Автоматизация проектирования радиоэлектронной аппаратуры. М.: Высш. шк., 2002. 384 с.

4. Курейчик В.М., Кажаров А.А. Использование роевого интеллекта в решении NP-трудных задач // Изв. ЮФУ: Технич. науки. 2011. № 7. С. 30–36.

5. Концепция поиска оптимальных решений при проектировании. Науч. издание; [под ред. Б.К. Лебедева]. Таганрог: Изд-во ТТИ ЮФУ, 2010.

6. Курейчик В.М. Биоинспирированный поиск с использованием сценарного подхода // Изв. ЮФУ. Изд-во ТТИ ЮФУ. 2010. № 7. C. 7–33.

7. Курейчик В.М., Лебедев Б.К., Лебедев В.Б. Адаптация в задачах проектирования топологии. Проблемы разработки перспективных микро- и наноэлектронных систем-2010. Сб. науч. тр.; [под ред. А.Л. Стемпковского]. М.: Изд-во ИППМ РАН, 2010. С. 170–177.

8. Лебедев Б.K., Лебедев В.Б. Размещение на основе метода пчелиной колонии // Изв. ЮФУ: Технич. науки. 2010. № 12. С. 12–19.

9. Лебедев В.Б. Построение кратчайших связывающих сетей на основе роевого интеллекта // Изв. ЮФУ: Технич. науки: Интеллектуальные САПР. Таганрог: Изд-во ТТИ ЮФУ. 2011. № 7. С. 37–44.

10. Dorigo M. and Stützle T. Ant Colony Optimization. Cambridge, MA, MIT Press, 2004.

11. Лебедев О.Б. Модели адаптивного поведения муравьиной колонии в задачах проектирования. Таганрог: Изд-во ЮФУ, 2013. 199 с.