Конструкторское проектирование

Рисунок 1.3- Виды монтажных соединений:

а — цепь; б — звезда; в — д — ортогональные соединения.

 

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

        Рассмотрим математические модели  радиоэлектронных схем, используемые  в автоматизированном конструкторском  проектировании. Любую исходную схему (функционально-логическую или принципиальную электрическую)  представляют как коммутационную. Коммутационная схема — это набор элементов, связанных между собой соединениями, по которым подаются сигналы на полюсы элементов  (рис. 1.4,а).

        Элементы схемы и внешние выводы  каждого элемента нумеруются, а выводы схемы, имеющие одинаковый потенциал, группируются в комплексы соединений, также нумерованные (рис.  1.4,б).

        Перенумерованные n элементов схемы составляют множество Е={е_i, i=0, 1, 2, ..., п}. Внешние выводы элементов образуют семейство множеств {C_i= {c_ij, j= 1, 2, ..., k_i}, i=0, 1, 2,..., n}, где i —номер элемента; j—номер вывода в данном элементе; k_i — число выводов i-го элемента. Отметим, что элементы множества С₀ относятся к внешним выводам схемы, образуя специальную группу. Комплексы соединений, выделенные на рис. 1.4,б пунктирными линиями, образуют семейство множеств V={v_i, i= 1, 2,..., М}, где v_i — множество эквипотенциальных выводов схемы; М — число комплексов. Поскольку выводы, принадлежащие различным комплексам соединений, непосредственно не связаны (только через элемент), то

 

C=,          ,                              (1.2) 

 

        Приведенное формальное описание  может быть представлено в  виде графа (рис. 1.4,в), если элементы  множеств Е, С, V рассматривать как вершины, а также ввести ребра, определяющие принадлежность выводов элементам (элементные ребра F) и принадлежность выводов комплексам соединений (сигнальные ребра W). Подобная математическая модель в виде графа широко используется в задачах дискретной оптимизации.

        Граф с вершинами трех типов (Е, С, V) и ребрами двух типов (F, W) дает наиболее детальное представление схемы. Этот граф используется при задании полной информации о схеме в процессе автоматизированного проектирования. Однако в ряде задач и алгоритмов можно обойтись меньшим объемом информации о схеме, например, используя граф, полученный после втягивания вершин d в вершины Е и удаления элементных ребер F (рис. 1.4,г).

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

Рисунок 1.4 - Представление модели коммутационной схемы в задачах автоматизированного конструкторского проектирования:

а — коммутационная схема; б — комплексы соединений на схеме; в — граф схемы; г — граф элементарных комплексов соединений; д — матричное и списочное описания комплексов соединений; е — сокращенное табличное описание графа схемы (n×k — число элементов, k=max ; i=0, 1, ..., п — максимальное число выводов элементов).

 

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

 

3. Алгоритмы компоновки

 

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

 

               (1.3)

N — число групп элементов (блоков, панелей или ТЭЗов в зависимости от уровня, на котором осуществляется разбиение).

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

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

1.  Каждый  блок содержит не более Р компонентов и не более Q выводов.

2.  Каждый  блок размещается в заданном  объеме V_i и имеет длину внешних связей сне более Е_i (это модификация первого требования).

3.  Общее  число соединений между N блоками минимально.

4.  Число  блоков - N минимально.

5.  Блоки  выбираются из числа стандартных,  составляющих библиотеку эталонных  элементов (приведение задачи  компоновки к задаче покрытия  схемы совокупностью элементов  стандартного набора).

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

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

8.   Выполняются заданные ограничения  на задержки распространения сигналов.

9.  Обеспечивается  удобство тестирования, доступность  элементов в блоках и низкая стоимость ремонта.

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

        При решении задач компоновки  используются математические формулировки  задач целочисленного (дискретного)  линейного или нелинейного программирования. Комбинаторные алгоритмы, связанные с перебором всего множества элементов А, как правило, неприемлемы из-за большого размера задачи. Поэтому используются приближенные алгоритмы компоновки последовательного, последовательно-параллельного или итерационного типа.

        В конструктивных последовательных  алгоритмах оптимальное разбиение  формируется путем последовательного  удовлетворения т независимых функций Ф_i — критериев оптимальности — при включении одного элемента или группы элементов. Например, «следующий (j+1)-й» компонуемый элемент выбирается из всех оставшихся элементов, если из элементов, оптимальных по Ф_i, он оптимален также по Ф_i+1 (i= 1, 2,..., т). Формирование следующего k-го блока начинается после завершения формирования предыдущих блоков с номерами  1, 2,... ,k—1. В  конструктивных последовательно-параллельных алгоритмах формируется сразу несколько блоков.

        В итерационных алгоритмах критерий  оптимальности

 

Ф=а₁Ф₁+а₂Ф₂+…+а_mФ_m,                       (1.4)

 

где а₁, а₂, … , а_m, — весовые коэффициенты, которые выбираются эвристически с целью учета неравнозначимости используемых функций оптимизации.

        Набор функций {Ф₁ Ф₂, ... ,Ф_m} определяется количественными представлениями требований компоновки, рассмотренных выше. Если часть требований представлена в виде ограничений, то на каждом шаге алгоритма компоновки проверяются условия, диктуемые этими ограничениями, и в соответствии с результатами проверки изменяется ход процесса компоновки.

        Рассмотрим пример итерационного  алгоритма распределения элементов  по неограниченному числу допустимых  блоков, в каждом из которых суммарный «вес» Р элементов не должен превышать заданной величины Р* при условии, что минимизируется степень связи (число соединений) между блоками.

        Суммарная степень связи, используемая  в качестве критерия оптимальности,  выражается соотношением

 

Ф=                                                         (1.5)

 

где m_RS — коэффициент связи элементов T_R и T_s, принадлежащих разным блокам.

        Модель компонуемой схемы представим  в виде графа, вершинам которого соответствуют элементы устройства. Примем (начальное разбиение (нулевой шаг) на N=n блоков R= {А₁, А₂,... ,А_n}, когда в каждый блок входит одна вершина. Очевидно, что в этом случае значение функции Ф из (1.2) на нулевом шаге Ф₀=max. При объединении двух вершин T_R и T_s в блок A_k число блоков уменьшается (N=N—1) и уменьшается суммарная степень связи (ф₁=ф₀—m_RS). Очевидно, что на каждом i-м шаге максимальное снижение Ф_i получится при объединении блоков, имеющих максимальную степень связи. Однако при объединении блоков увеличивается вес k-ro блока: P_k=P(T_R) + P(T_S). Поэтому процесс объединения допустим до тех пор, пока P_k <Р*. Полученные блоки фиксируются, а включенные в них элементы на следующих шагах компоновки не используются. Результат разбиения схемы приведен на рис.  1.5, где цифры соответствуют весам элементов при P≤10.

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

Рисунок   1.5 -  Пример   применения   алгоритма   компоновки: результат разбиения схемы при P≤10

 

качественный показатель уменьшается. Использование упорядочения в переборе позволяет сократить число рассматриваемых вариантов. Пример применения подобного алгоритма показан на рис.  1.6.

Рисунок   1.6 -  Пример   применения   итерационного   алгоритма   назначения для компоновки:

а — начальное разбиение; б — окончательное разбиение.

       

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

Рисунок  1.7 - Пример  использования нескольких алгоритмов  компоновки:

а — результат применения итерационного  алгоритма по методу парных  перстановок (I — начальное разбиение {1, 2}, {3, 4, 5}; II — улучшенное разбиение {1, 4}, {2, 3, 5}); б — оптимизация разбиения дублированием элемента 3.

 

        В качестве примера на рис.  1.7,а для простой логической схемы показано начальное разбиение. Пунктирная линия I разделяет элементы схемы на два блока, при образовании которых потребуется введение 2×7=14 дополнительных контактных площадок. Там же показано улучшенное разбиение, полученное после применения итерационного алгоритма парных перестановок: пунктирные линии || разделяют элементы схемы на два (блока, в результате чего образуются 2×4=8 новых контактных площадок (на рисунках обозначены □)). Дублирование в этой схеме элемента 3 обеспечивает возможность разбиения ее на два блока при введении лишь 2×3=6 контактных площадок (рис. 1.6,б). Иногда при решении задач компоновки применяется дублирование не только элементов, но и сигналов в схеме. В этих случаях необходима проверка или пересмотр проектируемой схемы.

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

 

4. Алгоритмы размещения

 

        После компоновки элементов РЭУ  требуется осуществить для каждого  стандартного или уникального  блока оптимальное размещение элементов в регулярном или нерегулярном монтажном пространстве. В общем случае нужно найти на множестве позиций монтажного пространства блока А_i такое размещение компонентов {Т₁, Т₂,..., Т_п}, i, принадлежащих этому блоку, при котором достигается минимум заданного критерия качества размещения L, выраженного с использованием соотношений   (1.1).