Файл: Ландау И.Я. Применение ЦВМ для проектирования ЦВМ.pdf

такое их расположение, которое удовлетворяет задан­ ным условиям. Способы решения этой задачи в большой степени зависят от конструкции элемен­ тов рангов п и п— 1; мы будем рассматривать только типичную для со­ временных ЦВМ конст­ рукцию, показанную на рис.3-6. Элемент ранга п представляет собой пря­ моугольник, на одной из сторон которого располо­ жены выводы внешних

•связей (разъем). Внутри прямоугольника (на мон­ тажном поле) располо­ жены пронумерованные в некотором порядке по­ садочные места; на любое

на монтажном поле выполняются печатным монта­ жом.

Таким образом, задача размещения заключается в выборе для каждого элемента1 лучшего посадочного места. Основная трудность решения этой задачи со­ стоит в отсутствии адекватных критериев выбора. Усло­ вия, которым должно удовлетворять размещение, раз­ деляются на две группы:

1)электрические, определяющиеся характеристик

ми системы элементов (обычно они состоят в ограни-

1 В дальнейшем речь будет идти о размещении и соединении элементов ранга п— 1, поэтому ранг будем опускать.

89 •’

чениях на максимальную длину соединений между не­ которыми элементами);

2) топологические, определяющиеся необходимость реализовать все соединения без пересечений на задан­ ном числе плоскостей (монтажных слоев).

Если удовлетворить условия первой группы при -раз­ мещении не представляет труда, то с условиями второй группы дело обстоит значительно сложнее. Прежде всего в данной формулировке невозможно проверить выполнение их, не выполнив трассировку соединений; любой другой метод (определение числа пересечений между отрезками, соединяющими выводы элементов, разбиение схемы на плоские подграфы) не подходит, поскольку печатные проводники являются ломаными линиями конечной ширины, которые определяются в про­ цессе их построения. Кроме того, при размещении заданы только электрические цепи (т. е. соединяемые группы выводов элементов), но не указан порядок их соединения, который также влияет на результаты трас­ сировки. Таким образом, для выбора оптимального (по условиям второй группы) размещения необходимо совместно решать задачи размещения, выбора порядка соединений и трассировки. Это приводит к итерацион­ ному процессу «размещение — соединение — трассиров­ ка», который требует слишком большого машинного времени. Поэтому приходится решать эти задачи раз­ дельно, используя промежуточные критерии, не связан­ ные прямо с конечной цепью (оптимальной трассиров­ кой), но удобные для проверки.

Большинство алгоритмов, предложенных для реше­ ния задачи размещения, построены следующим образом.

Пусть часть элементов уже размещена. Тогда выби­ раем такой не размещенный еще элемент / и такое свободное посадочное место /, для которых значение некоторой оценочной функции qa максимально (мини­ мально). Этот процесс продолжается до тех пор, пока все элементы не будут размещены. Такие алгоритмы не дают точного решения задачи (глобального минимума или максимума qa), но это и не обязательно, поскольку qij лишь косвенно отражает конечную цель; поиск же точного решения приводит, как и в задаче компоновки, к переборным алгоритмам.

Сравнительный анализ различных алгоритмов и оце­ нок решения задачи размещения выходит за рамки дан­

90

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

1. Если данная цепь связывает небольшое количест­ во элементов («короткая» цепь), то эти элементы долж­ ны располагаться близко друг от друга; если цепь связывает много элементов («длинная» цепь), их рас­ положение менее существенно. Здесь учитывается то обстоятельство, что для коротких цепей существует сравнительно немного вариантов соединения, тогда как для длинных цепей число их очень велико1. Поскольку выбор порядка соединения элементов приходится про­ изводить после их размещения, дерево соединений ко­ роткой цепи в значительной степени уже определяется размещением элементов, а при построении дерева сое­ динений длинной цепи можно будет учесть и другие требования (например, минимум пересечений).

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

3. Если цепь связана с разъемом, то хотя бы один из подключенных к ней элементов должен располагать­ ся вблизи этого разъема. Это условие является следст­ вием условий 1 и 2.

При размещении используются две оценочные функ­

где k — число связей а,- с aj, а а; — вес связи:

и Qi, определяемая для каждого элемента ау

Q i = : 9ij>

/

1 Число различных вариантов соединений для цепи, связывающей р элементов, М — С ^ ~ г д е S = С~р . При р — '2 М = 1 , при р — 3

М — 3, при р = 10 М — 886 163 135.

91

где суммирование ведется по всем элементам, связан­ ным с a.i. Для вычисления qij и Q, исходный список связей СВ (полученный в результате компоновки) упо­ рядочивается по номеру цепи (получаем С4) и строится список С5. В процессе построения С5 вычисляются qa и Qi, которые вписываются в строки С5 и в заголовки групп соответственно.

Размещение элементов проводится в три этапа. Вначале размещаются элементы, местоположение кото­ рых указано разработчиком. Затем выбираются все цепи, связанные с разъемом, и для каждой из них устанавливается по одному элементу вблизи разъема. После этого размещаются оставшиеся элементы. По­ скольку для некоторых связанных с разъемом цепей разработчик мог заранее определить номера контактов разъема, сначала выделяются эти цепи и входящие в них элементы устанавливаются на посадочные' места, ближайшие к заданным контактам. Для установки вы­ бираются элементы с наибольшей Q,-. После этого про­ сматриваются (в порядке возрастания длины) осталь­ ные связанные с разъемом цепи, в каждой из них выбирается элемент с наибольшей Qi и устанавливается на свободное посадочное место, ближайшее к очеред­ ному не занятому контакту разъема. Номер этого кон­ такта заносится в список цепи.

На третьем этапе размещения рассматриваются по­ садочные места, соседние с последним размещенным элементом (рис. 3-7,а). Если среди них нашлось сво­ бодное (г— 1 на рис. 3-7,а), оно заполняется. Если среди соседних посадочных мест свободного не оказалось, ищем какое-нибудь свободное посадочное место, сосед­ нее с ранее заполненными (рис. 3-7,6), и заполняем его. На выбранное таким образом посадочное место уста­ навливается элемент, наиболее связанный с соседними. Для этого поочередно просматриваются все установлен­ ные уже элементы, соседние с заполняемым посадоч­ ным местом (указаны пунктирными стрелками на рис. 3-7,а, б). Для каждого такого элемента а-; выбира­ ется из С5 входящий в его группу элемент а, с макси­ мальной qa. Эти элементы заносятся в таблицу канди­ датов на размещение (ТК). После построения ТК (она может включать от 1 до 8 элементов) повторяется про­ смотр соседних элементов, но на этот раз из каждой группы {a;}j выбираются элементы, вошедшие в ТК

92

в качестве кандидатов от других мест, соседних с за­ полняемым посадочным местом; оценочные функции qa этих элементов в ТК суммируются. Для установки выбирается из ТК элемент с максимальной суммой этих оценочных функций.

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

жа разрешают это). Ориентация определяется отдельно для каждого из элементов следующим образом. Рас­ смотрим некоторый элемент а{ и цепи {/у},-, в которые входит щ. Для каждой цепи rh из {/у}; найдем входящий в нее элемент щ, расположенный ближе всего к а,-. Выберем из допустимых ориентаций элемента а, такую, при которой расстояние между центром элемента а, п подключенным к гд выводом элемента а,- минимально; будем считать эту ориентацию желательной для цепи ot- В качестве окончательной ориентации элемента а; выби­ раем ту, которая желательна для большего числа цепей.

93

в котором указаны заранее размещенные элементы ран­ га я —1 (номер элемента и номер посадочного места). Описание конструкции элемента ранга я представляет собой список, в котором указаны порядковый номер и координаты «центра» каждого посадочного места. В ка­ честве центра посадочного места может быть выбрано

я— 1 представляет собой список координат его выводов относительно выбранного центра. Если имеются различ­ ные (по цоколевке) типы элементов ранга я— 1, их описания сводятся в библиотеку элементов. В описание конструкции элемента ранга я входят также списки координат разъемов.

Описанный алгоритм размещения элементов не при­ вязан к конкретным конструктивным особенностям эле­ ментов— характеристики конструкции задаются ему как входная информация. Это делает его пригодным для решения задач размещения элементов разных рангов. Фактически о конструкции сделаны следующие пред­ положения:

монтажное поле имеет прямоугольную форму; контакты разъемов расположены по периметру мон­

тажного поля;, геометрическая форма всех элементов ранга я— 1

одинакова; посадочные места регулярно расположены на мон­

посадочных мест, а также между любым посадочным местом и контактом разъема.

Для большинства типов конструктивных элементов современных ЦВМ эти предположения выполняются. Однако конкретная программная реализация алгоритма может оказаться непригодной для элементов некоторого ранга, поскольку объемы входной информации на раз­ ных рангах значительно отличаются. Так, например,

(с учетом разъемов), что позволяет хранить и обраба­ тывать все списки в оперативной памяти. Для шкафа

94