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

ЛАБОРАТОРНАЯ РАБОТА №1

ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ АЛГОРИТМА ПОКРЫТИЯ СХЕМ МОДУЛЯМИ

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

1. ОБЩИЕ СВЕДЕНИЯ О ЗАДАЧЕ ПОКРЫТИЯ

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

1.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)