Постановка задачи и критерии компоновки

Компоновка - задача определения состава конструктива каждого элемента.

Две подзадачи компоновки:
1. Покрытие - переход от логических схем к принципиальным (использующим схемно-унифицированные модули - микросхемы)
2. Разбиение - разрезание схемы на куски (конструктивная унификация)

Критерии в задаче покрытия: (меньше - лучше)
1. Суммарная стоимость микросхем
2. Общее число микросхем
3. Число типов используемых микросхем
4. Количество связей между микросхемами
5. Количество неиспользуемых элементов микросхемы

Ограничения в задаче покрытия:
1. Обеспечение теплового режима
2. Обеспечение помехозащищенности
3. Простота диагностики и эксплуатации

Постановка задачи покрытия:
Имеется:
1. Набор элементов E = {e₁,..., e_n}. t(e_i) - тип элемента, один из {t₁,..., t_l}
2. Набор микросхем M = {M₁,..., M_h}
3. Количественный состав схемы по типам K = {K₁,..., K_l}. K_i - количество элементов i-го типа, то есть Σ(1, l) K_i = n
4. Матрица состава микросхем по элементам А = ||a_rt||_hxl - элемент а_ij показывает, сколько в i-й микросхеме элементов j-го типа
5. Цена микросхемы C₁,..., C_h
Цена решения С = Σ(1, h) С_iX_i, где X_i - количество используемых микросхем i-го типа.
Необходимо набрать нужное количество элементов:

Σ(1, h) a_itX_i ≥ K_t для всех (типов) t = 1,..., l (1)
6. Y_st = 1, если элементом s можно реализовать элемент t, и 0 - в противном случае
Тогда (1) запишется в виде Σ(1, h) a_itX_i - Σ(1, l) Y_ti + Σ(1, l) Y_it ≥ K_t для t = 1,..., l (2)

Критерии в задаче разбиения:
1. Минимизация числа межблочных соединений.

2. Минимизация числа образующих блоков.
3. Задержки распространения сигналов.
4. Электромагнитная и тепловая совместимость элементов.

Ограничения в задаче разбиения:
1. Число элементов в блоке.
2. Количество внешних выводов.
3. Суммарная площадь, занимаемая элементами и соединениями.

5. Компоновка схем в схемно-унифицированные типовые конструкции.

Алгоритм покрытия (приближенный)
Пусть Y_ts = 0. Помимо минимизации стоимости (I), также минимизируем связи между микросхемами (II). Рассмотрим минимизацию стоимости (I). Общая идея - жадный алгоритм, стараемся использовать самые дешевые микросхемы.
1. Микросхемы упорядочиваются по стоимости: С_i ≤ C_i+1
2. r = 1
3. Определение локального минимального числа микросхем:
а) S_rt = ⌊K_t/a_rt⌋ (a_rt ≠ 0, K_t ≠ 0) для всех t = 1,..., l
б) S_r = min {S_rt} по всем t
4. Находим вектор непокрытых элементов: К_r = K^r-1 - S_rA_r (это векторная операция, а верхний индекс здесь отражает состояние вектора K на r-ом шаге)
5. r = r+1
6. Если есть непокрытые элементы (K^r > 0), то:
а) если r < h (еще есть типы микросхем), то переходим к пункту 3
б) если r = h, переходим к пункту 2 (второй и последующие проход)
7. X_r = сумма S_r по всем проходам

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

 Пример Þ Дано:  1. Схема из 11 элементов (e₁,..., e₁₁). Из них 5 - типа t₁, 4 - типа t₂, по одному - t₃ и t₄ => K⁰ = (5, 4, 1, 1)
2. Три типа микросхем: например, микросхема типа M₁ содержит 1 эл-т типа t₂ и 2 эл-та типа t₁ и т. д. Матрица А имеет вид ®
Выполнение алгоритма: 1. Пусть микросхемы уже отсортированы по стоимости: М₁< М₂< М₃
2. r = 1

 3. S₁₁=⌊5/2⌋=2, S₁₂=⌊4/1⌋=4. a₁₃=a₁₄=0, поэтому S₁₃ и S₁₄ не считаются. S₁=min(S₁₁, S₁₂)=2.
4. K¹=K⁰ - S₁A₁=(5, 4, 1, 1) - 2 * (2, 1, 0, 0)=(1, 2, 1, 1)
5. r = 2 ® 3. S₂₂=⌊2/1⌋=2, S₂₃=⌊1/1⌋=1 => S₂=1
4. K₂ = K¹ - (0, 1, 1, 0) = (1, 2, 1, 1) - (0, 1, 1, 0) = (1, 1, 0, 1)
5. r = 3 ® 3. S₃₁=1, S₃₄=1 => S₃=1
4. K³ = K² - (1, 0, 0, 1) = (0, 1, 0, 0)
2. r = 1 (начинается второй проход)
3. S₁₂ = 1 => S₁' = 1
4. К⁴ = К³ - (2, 1, 0, 0) = (-2, 0, 0, 0)
7. X₁=S₁+S₁'=2+1=3, X₂=S₂=1, X₃=S₃=1

Этап II: минимизация связей между микросхемами. В микросхему помещается элемент, который имеет max число связей с уже размещенными в данной микросхеме элементами и min число связей с остальными эл-тами.
E₁ = {e₃, e₆, e₂, e₅, e₁₀, e₉, e₈, e₁, e₇} // это то, что можно положить в микросхему типа M₁
M₁¹ = {e₅, e₂, e₃} // так как алгоритм приближенный, то элементы мы выбираем "на глаз". В данном случае элементы e₅, e₂ и e₃ имеют нужные типы, связаны между собой и имеют лишь одну связь с остальными элементами.
M₁² = {e₈, e₉, e₁₀} ® E₁ = {e₁, e₆, e₇} ® M₁³ = {e₁, e₇} ® M₂¹ = {e₄, e₆} ® M₃¹ = {e₁₁}