Автоматизация системного проектирования

В итоге образуется специальный файл электрических соединений.

Составим формальный список кругов, выделив их из принципиальной схемы:

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

В случае минимизации суммарной взвешенной длины соединений формула для расчета изменения значения целевой функции при перестановке местами элементов ri и rj, закрепленных в позициях tf и tg, имеет вид:

где p и h(p) – порядковый номер и позиция закрепления неподвижного элемента rp.

Если, то осуществляют перестановку ri и rj, что приводит к уменьшению целевой функции на, после чего делают поиск и перестановку следующего пара элементов и т.д.

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

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

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

Частичным случаем итерационного алгоритма является алгоритм Штейнберга или так называемый алгоритм парных перестановок.

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

Последовательные алгоритмы основаны на предположении, что для получения оптимального размещения необходимо в соседних позициях располагать элементы, максимально связаны друг с другом. Сущность этих алгоритмов складывается в последовательном закреплении заданного набора конструктивных элементов на коммутационной плате относительно тех, что были установлены раньше. В качестве сначала закрепленных на плате элементов обычно выбирают разнимания, которые искусственно «раздвигают» к краям платы. При этом все контакты разниманий равномерно распределяются по секциям (столбцам и строкам координатной сетки). На каждом l шаге (l=1,2.,n) для установки на коммутационнуюx0 плату выбирают элемент из числа еще не размещенных, что имеет максимальную степень связности с ранее закрепленными элементами Rl-1. В большинстве используемых в это время алгоритмов оценку степени связности делают по одной из следующих формул:

где сіj – коэффициент взвешенной связности элементов i и j;

Jl-1 – множество индексов элементов, закрепленных на предыдущих l-1 шагах;

n – общее число размещенных элементов.

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

В частности, если критерием оптимума является минимум суммарной взвешенной длины соединений, то

 Скачать реферат