Распределение элементов по модулям

После определения числа модулей каждого типа  необходимо получить такое распределение элементов схемы по микросхемам, при котором число соединений между ними будет минимально. Для решения этой задачи может быть использован какой-либо последовательный алгоритм компоновки [3, 4], на каждом шаге которого выбирается один из нераспределенных элементов и приписывается к очередной ИМС. Тактика назначения элементов основана на принципе максимальной связанности назначаемого элемента с элементами, ранее помещенными в рассматриваемую ИМС. При назначении должны учитываться структура ИМС и типы элементов.

Распределение начнем с микросхем , которых имеется x₁ штук.

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

, .

Для назначения выбирается тот из элементов , который имеет наибольшее суммарное число соединений с элементами, уже помещенными с ИМС и наименьшее число соединений с остальными элементами из множества . В одинаковых ситуациях выбирается элемент с меньшим номером. Процесс компоновки ИМС продолжается до тех пор, пока или все элементы будут заняты, или на некотором шаге S < K_l среди нераспределенных элементов отсутствуют элементы, отвечающие составу микросхемы. После этого процесс продолжается для остальных T₁, а затем для T₂ , … T_m.

ПРИМЕР 1.2

В примере 1.1 получено x₁ = 3 ИМС типа , x₂ = 1 ИМС  и x₃ = 1 ИМС . Требуется распределить элементы по ИМС, используя критерий минимума числа связей между ними.

Решение

При распределении элементов по корпусам микросхем можно было учитывать только выполняемые ими функции. Тогда одним из вариантов покрытия будет схема, представленная на рис.1.4. Число связей между модулями в ней равно 12-ти.

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

1) Из схемы рис.1.1 выделим множество базовых функциональных элементов , которые могут быть помещены в микросхемы типа T_l:

.

Первым в микросхему помещаем элемент e₅, имеющий с остальными максимальное число связей – три; затем в нее назначаем связанные с e₅ элементы: трехвходовый e₂ и двухвходовый e₃. В результате 1-я ИМС 1-го типа будет включать .

Для компоновки 2-й микросхемы  этого же типа осталось множество базовых функциональных элементов . . Первым в ИМС  попадает элемент e₆, затем двухвходовые e₈ и e₉. Получим набор 2-й ИМС .

При компоновке 3-й микросхемы 1-го типа –  множество элементов будет . В соответствии с алгоритмом помещаем в нее элементы e₁ и e₇. При этом место t₁ остается незанятым, поскольку все элементы данного типа распределены.

2) Переходим к компоновке микросхем 2-го и 3-го типов –  и . Пользуясь алгоритмом, получим, что элементы множества  назначаются в ИМС , а оставшийся четырехвходовый триггер  попадает в  с одним незанятым местом . Избыточность покрытия также равна .

Получено распределение элементов по микросхемам. Теперь на основании исходной схемы (рис.1.1) можно сформировать вариант соединения корпусов ИМС, реализующий эту схему. Он представлен на рис.1.5.

В данном варианте число электрических цепей между отдельными ИМС получилось равным девяти, что на три цепи меньше, чем в результате, представленном на рис.1.4. Потому при прочих одинаковых показателях, по данному критерию результат на рис.1.5 лучше. Его и надо принять за решение поставленной задачи покрытия.

ЭКСПЕРЕМЕНТАЛЬНАЯ ЧАСТЬ

Пусть дана электрическая схема (рис.2.1), которая состоит из элементов типа t₁, t₂, t₃, t_4, t₅ и t₆ (рис.2.2). Существует библиотека ИМС  (рис.2.3), причем их условные стоимости равны соответственно: ; ;  условных единиц стоимости.

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

Рис.2.1 Электрическая схема

Рис.2.2  Элементы типа t.

Рис.2.3 Библиотека элементов

Решение

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

Для покрытия выберем микросхемы  как наиболее дешевые.

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

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

.

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

.

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

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

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

 .

Далее выполним аналогичные действия для ИМС , стоимость которой .

Вектор  поделим поэлементно на строку :

.

Значащими в результате деления будут . Минимум из них , поэтому для покрытия схемы назначаем 2 шт. ИМС . Формируем строку 2

Для этого из вектора  поэлементно вычитаем строку – 2

Определяем вектор непокрытых элементов :

.

Наличие отрицательного элемента (-2) в  указывает на избыточность по двум элементам и  , но потребность 2 элементов  и  в покрывающих ИМС.

Произведем покрытия оставшихся элементов ИМС , так как . Поделим вектор  поэлементно на строку :

.

Поскольку , получим , и для покрытия схемы назначаем 2шт. ИМС . Формируем строку 2

Для этого из вектора  поэлементно вычитаем строку – 2

Вектор непокрытых элементов  будет:

 .

Наличие отрицательного элемента (-2) в  указывает на избыточность двух элементов ,  ,   и в покрывающих ИМС.

Итак, процесс покрытия закончен. В итоге получили 2 шт. , 2 шт.  и 2 шт. . Коэффициент покрытия схемы G = 12/6 = 2.

Результаты расчетов сведены в табл.2.1. В скобках указано число элементов (по типам) в исходной схеме рис.2.1.

Таблица 2.1

Тип микросхемы	Число микросхем	Число элементов						Всего
	2	2	2	0	0	2	0	6
	2	2	0	0	2	2	0	6
	2	0	2	2	0	0	2	6
Всего	6	4(2)	4(2)	2(2)	2(2)	4(2)	2(2)	18(12)

Получено распределение элементов по микросхемам (Рис.2.4)

Рис.2.4. Распределение элементов по микросхемам

ВЫВОД

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

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

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

Суммарная стоимость модулей равна 21.

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

Общие число модулей равно 6.

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

Число типов модулей равно 2.

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

Число связей между модулями равно 20.

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

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

МАШИННЫЙ РАСЧЕТ