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

Рассмотрим решение этой задачи при условии, что каждый элемент схемы 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. Определить количество использованных ячеек каждого типа

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

Конец.