Материал: laboratornaya_rabota_1-n

21

Лабораторная работа №1 исследование эффективности алгоритма покрытия схем модулями

Цель работы - исследовать эффективность алгоритма покрытия схем типовых модулей РЭС; усвоить особенности алгоритмизации и программирования задачи покрытия схем на ЭВМ; приобрести навык построения математических моделей объектов конструирования, реализации и исследования их при решении задачи покрытия в САПР.

1. Общие сведения о задаче покрытия

Задача покрытия функциональной схемы типовыми модулями из заданного набора является задачей преобразования функциональной схемы в электрическую, т.е. схему соединения конструктивных элементов (резисторов, конденсаторов, транзисторов, интегральных схем, и т.д.) [1-3]. Решается эта задача одной из первых на этапе конструкторского проектирования. Поскольку при проектировании радиоэлектронных средств (РЭС) применяется большое многообразие электрорадиоэлементов (ЭРЭ), то наряду с задачей покрытия часто возникает необходимость определения оптимального набора этих элементов для каждого конкретного класса схемы, минимизация числа типов элементов набора в проектируемом устройстве.

1. Математическая формулировка задачи

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

Допустим, схема состоит из множества элементов E = {e₁, e₂,…,e_n} и для каждого из элементов известен тип функции F(e_i) (i = 1, 2,…, l), которую он реализует (усилитель, детектор, триггер, схема «И», «ИЛИ» и т.д.).

Набор модулей определяется библиотекой T = {T₁, T₂,…, T_n}.

Количественный состав схемы по типам элементов опишем вектором , в котором b_j – число элементов типа j. Состав модулей библиотеки опишем матрицей , в которой a_kj – число элементов типа j в модуле T_k. Отметим, что элемент схемы может быть реализован с помощью элемента того же типа, находящегося в одном из модулей библиотеки, либо с помощью элементов других типов. Например, элемент ИЛИ с двумя входами может быть реализован элементом ИЛИ с большим числом входов.

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

В качестве критериев оптимальности в задаче покрытия используют:

- суммарную стоимость модулей, покрывающих схему;

- общее число модулей в покрытии;

- число типов используемых модулей;

- число связей между модулями;

- число неиспользованных элементов в модулях.

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

Для оценки качества покрытия используют дополнительный критерий – коэффициент покрытия G = N/M, где N – число элементов в схеме, а M – число модулей (микросхем), которыми покрыта схема.

Рассмотрим наиболее распространенный вариант задачи, в котором критерием качества является суммарная стоимость модулей.

Пусть известны стоимости модулей каждого типа c_1,…, c_k,…, c_m. Если ввести целочисленные переменные x_k , определяющие число модулей типа k, которые необходимы для покрытия с минимальной стоимостью, задача сведется к минимизации функции

(1.1)

при ограничениях

, (1.2)

где j = 1, 2,…,l, a_kj - число элементов типа j в T_k.

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

(1.3)

x_k – целое число для всех k, так как любой модуль используется только полностью, независимо от числа задействованных в нем компонентов.

Задача (1.1) – (1.3) является задачей целочисленного программирования.

Целевая функция для минимизации стоимости и числа модулей имеет вид:

,

где r₁ и r₂ – коэффициенты, учитывающие важность используемых критериев.

1.2. Алгоритм покрытия схем разнотипными модулями

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

1) Определение необходимого числа модулей с минимальной суммарной стоимостью.

2) Минимизация числа связей между модулями.

а) Допустим, что каждый из модулей T содержит элементы одного типа k, тогда минимальное число модулей для покрытия схемы, определяющее и минимальную стоимость покрытия, равно

, (1.4)

где а_к – число элементов в модуле T_k; b_k – число элементов типа k в схеме; { } – символ ближайшего большого целого; x_k – число использованных модулей типа k. Отметим, что для модулей с однотипными элементами получаем квадратную матрицу , причем a_k = 0 при , и .

б) Практический интерес представляют наборы модулей с разнотипными элементами.

Пусть известны:

1) Библиотека типовых элементов, содержащая m типов интегральный микросхем (ИМС). Общее число типов элементов в ИМС библиотеки l. Тогда библиотеку зададим матрицей вида .

2) Электрическая схема узла, состоящая из соединения элементов одинаковых типов. Зададим схему вектором .

Алгоритм 1

1. Составить вектор количественного состава схемы по типам элементов: .

2. Упорядочить модули (микросхемы) T_k библиотеки по возрастанию их стоимостей:

.

3. Составить матрицу описания состава библиотеки в соответствии с их стоимостью; .

4. Выполнить поэлементное деление вектора на строку матрицы A:

для , .

5. Найти и на данном шаге использовать модулей типа k.

6. Найти вектор непокрытых элементов

, где ; .

7. Если элементы , перейти к , если , перейти к .

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

( – определяет число итераций) и вычислить их суммарную стоимость: .

Конец.

ПРИМЕР 1.1

Пусть дана электрическая схема (рис.1.1), которая состоит из элементов типа t₁, t₂, t₃, и t₄ (рис.1.2). Существует библиотека ИМС (рис.1.3), причем их условные стоимости равны соответственно: ; ; ; ; условных единиц стоимости.

Требуется выполнить покрытие с минимальной стоимостью схемы на рис.1.1 набором микросхем из библиотеки рис.1.3.

Решение

Сосчитаем количество элементов каждого типа в схеме: , , , и составим вектор количественного состава: .

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

Упорядочим выбранные ИМС по возрастанию их стоимостей: T₁, T₂, T₃ .

Составим матрицу описания состава ИМС библиотеки с учетом их стоимостей:

.

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

.

В результате для ИМС имеем , .

Берем min из значащих чисел {2, 4}: . Следовательно, для покрытия схемы назначаем 2 шт. ИМС . Формируем строку .

Находим вектор непокрытых элементов . Для этого из вектора поэлементно вычитаем удвоенную строку –