WEB-ресурс научно-практических конференций

Ганжа С.Н., Иванов Г.П., Ганжа С.А., Иванов В.Г.

Восточноукраинский национальный университет им. В. Даля, Технологический институт (г. Северодонецк )

Критерий равномерного заполнения монтажного пространства электрическими соединениями при автоматизированном размещении элементов

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

В данной работе авторами предлагается алгоритм равномерного заполнения монтажного пространства межсоединениями на этапе размещения элементов. Традиционный подход к решению поставленной задачи следующий. Монтажное пространство разбивается на «опорные» прямоугольники, либо вводятся горизонтальные и вертикальные сечения. В ходе размещения элементов минимизируется количество цепей, покрывающих эти прямоугольники либо пересекающие сечения. Это также не снимает проблему перегруженных соединениями областей, в которых задача трассировки решается достаточно сложно.

Предлагается равномерно загружать опорные прямоугольники или сечения соединениями. В случае, если монтажное пространство разбивается на опорные прямоугольники, в ходе размещения предлагается минимизировать величину S , близкую к среднеквадратическому отклонению:

где

где i – номер опорного прямоугольника;

C _i – количество цепей, попадающих в i -тый опорный прямоугольник;

N – количество опорных прямоугольников.

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

где

B , D – соответственно количество горизонтальных и вертикальных сечений;

С _x , C _y – число цепей, пересекающих сечения по оси X и Y ;

N _x , N _y – количество горизонтальных и вертикальных сечений.

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

где S ₁ – приведенный выше критерий оптимизации;

S ₂ – критерий минимизации длины электрических цепей (например, полупериметр охватывающих прямоугольников);

b ₁ , b ₂ – весовые коэффициенты.

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

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