Итерационные алгоритмы улучшения компоновки

При обмене местами элементов ех и еу изменяется число выводов лишь на узлах Ti и Tj.

Вычислим приращение в числе выводов на узле Ti:

(4.35)

где vi, - и v'i - соответственно число выводов на узле до и после обмена. Заметим, что приращение числа выводов Дvi(x, у) равно приращению числа соединений между элементами узла Ti и элементами, не входящими в узел Ti. Поэтому формула для расчета Дvi(x, у) может быть непосредственно получена из (4.35) при замене узла Tj на множество элементов :

(4.36)

где

(4.37)

. (4.38)

Аналогичная формула имеет место для приращений числа выводов на узле Tj. Для ее получения необходимо лишь заменить везде в (4.36), (4.37), (4.38) символ Ii на Ij обозначающий множество элементов, не входящих в узел Tj: I;=E\Tj, символ х на у, а символ у на х.

Заметим, что для многоконцевых соединений равенство, аналогичное (4.16), уже не выполняется.

Далее рассмотрим алгоритм минимизации числа межузловых соединений.

Пусть известен некоторый вариант разбиения схемы на г узлов. Можно считать, что в каждом узле содержится ровно k элементов, причем n=kг. В случае, когда в каком-либо узле число элементов kr меньше k, всегда можно дополнительно ввести nд=k-kr фиктивных элементов, не связанных с другими элементами схемы: rsj=0, s=n+1,…, n + nд, j=1, 2,…, n + nд.

Рассмотрим два узла Ti, и Tj, (i, j=1, 2 г). В соответствии с (4.15) приращение числа межузловых соединений при обмене местами элементов еxTi, и eyTj будет равно ДL (x, y)=Dx+Dy-2rxv, где характеристики Dx и Dv рассчитываются по матрице соединений R.

Опишем процесс выбора пары элементов ех и ev для обмена. Сначала определяются характеристики Dz, для всех элементов еz, принадлежащих Ti, или Tj. Число этих характеристик равно 2k.

Далее находится пара элементов Тi и Tj, для которой (4.15) принимает максимальное значение. Если ДL (x, y)>0, то производится обмен. В результате образуются узлы Т’i и Т’j.

Зафиксировав положение элементов и соответственно в узлах T'j и T'i, выполняем аналогичный расчет для элементов из множеств и и определяем новую пару элементов для обмена и . Процесс обменов продолжается до тех пор, пока на очередном шаге s+1 среди элементов не найдется ни одной пары, для которой ДL (x, у) > 0. Узлы Tsi и Tsj отвечают результату минимизации числа межузловых соединений между исходными узлами Ti и Tj.

Заметим, что при обмене элементов не все из рассчитанных на предыдущем шаге характеристик D изменяются. Имеют место следующие соотношения:

(4.39)

(4.40)

Справедливость (4.39) может быть легко проверена. Действительно, внутренних соединений элемента ех в результате обмена становятся внешними по отношению к узлу Ti, а внешних соединений внутренними.

Читайте также

Разработка конструкции линейного коммутатора
Радиоэлектронная аппаратура (РЭА), в основу функционирования которой положены принципы электроники, строится на базе электронных компонентов различного назначения (микросхем, резисторов, ...

Модернизация охранной сигнализации университета
Безопасность собственного имущества издревле была одной из главных забот человека. Для защиты от несанкционированного вторжения в жилище, хищения вещей и пожара человечество придумало не ...

Проектирование передатчика телевизионной системы на печатной плате
Телевизионный передатчик: совокупность специализированных технических средств, применяемых в процессе телевещания (кроме источника сигнала и его тракта, источника электропитания и энерго ...