Разработка функциональной цифровой ячейки (стр. 4 из 8)
Программа Placeing автоматически высчитывает значения нижних оценок по заложенному в нее алгоритму. Представим расчет одной из нижних оценок целевой функции F, сделанный по этому алгоритму вручную:
Возьмем тот случай, когда 7 элемент (разъем) установлен в 7 позицию, а 5 элемент (микросхема) в 5 позицию.
1) Расчет Fр:
Fр = L (е7 - е5) *L (р7 - р5) = 5*90 = 450,
где L (е7 - е5) - количество связей между 7 элементом (разъемом) и 5 элементом, L (р7 - р5) - расстояние между 7 и 5 позициями.
2) Расчет Fн^:
Матрица незанятых позиций - это та же матрица длин, но уже без позиций, занятых размещенными элементами (то есть без 7 и 5). Матрица неразмещенных элементов - это матрица связей, но без 7 и 5 элементов. Значения матрицы незанятых позиций записываются в вектор значений в порядке возрастания сверху вниз (значения с какой-либо из половин матрицы, разделенной нулевой диагональю). Значения матрицы неразмещенных элементов так же записываются в вектор значений в порядке убывания сверху вниз (значения с какой-либо из половин матрицы, разделенной нулевой диагональю). Получаем два вектора значений. Затем эти векторы перемножаются, и получаем оценку длины связи между неразмещенными элементами:
| Матрица незанятых позиций | Матрица неразмещенных элементов | ||||||||||
| Р1 | Р2 | Р3 | Р4 | Р6 | Е1 | Е2 | Е3 | Е4 | Е6 | ||
| Р1 | 0 | 30 | 60 | 60 | 120 | Е1 | 0 | 3 | 4 | 1 | 0 |
| Р2 | 30 | 0 | 30 | 90 | 90 | Е2 | 3 | 0 | 1 | 3 | 0 |
| Р3 | 60 | 30 | 0 | 120 | 60 | Е3 | 4 | 1 | 0 | 0 | 1 |
| Р4 | 60 | 90 | 120 | 0 | 60 | Е4 | 1 | 3 | 0 | 0 | 2 |
| Р6 | 120 | 90 | 60 | 120 | 0 | Е6 | 0 | 0 | 1 | 2 | 0 |
3) Расчет Fнр^:
Матрица неразмещенных и размещенных элементов заполняется по матрице связей. В нее заносятся значения количества связей между размещенными элементами (7 и 5) и неразмещенными. Матрица незанятых и занятых позиций заполняется по матрице длин. В нее заносятся длины связей между позициями, занятыми размещенными элементами (7 и 5) и свободными позициями. Первый столбец матрицы неразмещенных и размещенных элементов записывается в вектор значений в порядке возрастания сверху вниз. Первый столбец матрицы незанятых и занятых позиций так же записывается в вектор значений в порядке убывания сверху вниз. Получаем два вектора значений. Перемножаем их. Получаем 1-ую составляющую оценки длины связи между не размещенными и размещенными элементами. Аналогично поступаем со вторыми столбцами матриц. Суммируем полученные составляющие части и получаем итоговую оценку длины связи между не размещенными и размещенными элементами:
| Матрица неразмещенных и размещенных элементов | Матрица незанятых и занятых позиций | ||||
| Е5 | Е7 | Р5 | Р7 | ||
| Е1 | 1 | 4 | Р1 | 90 | 120 |
| Е2 | 3 | 5 | Р2 | 60 | 90 |
| Е3 | 1 | 4 | Р3 | 90 | 60 |
| Е4 | 1 | 3 | Р4 | 30 | 120 |
| Е6 | 5 | 4 | Р6 | 30 | 60 |
Fнр^= Fнр1^ + Fнр2^ = 480+1740=2220
4) Расчет Fнг^. На этом этапе складываем результаты пунктов 1),
2) и 3) и получаем итоговую нижнюю оценку целевой функции F:
Fнг^ = Fн^ + Fр + Fнр^ = 720+450+2220=3390
Результат совпадает с полученным ранее в построенном дереве решений. Аналогично считаются остальные нижние оценки.
На сборочном чертеже:
Х1-Разъем (элемент 7), D1 - 1 элемент, D2 - 2 элемент, D3 - 3 элемент, D4 - 4 элемент, D5 - 5 элемент, D6 - 6 элемент, D7 - 7 элемент.
X1 - в 7 позицию, D1 - в 3 позицию, D2 - во 2 позицию, D3 - в 6 позицию, D4 - в 1 позицию, D5 - в 5 позицию, D6 - в 4 позицию.
Раздел 4. Минимизация длины связей между контактами разъема и контактами внешних цепей
Постановка задачи назначения цепей инвариантным контактам
При конструировании функциональных ячеек на печатных платах необходимо обеспечить минимизацию длины электрических связей между контактными площадками на всех этапах. Одним из действенных приёмов уменьшения длины соединений и улучшения условий трассировки проводников является рациональное назначение цепей инвариантным контактам элементов схемы. Группа контактов элемента называется инвариантными в том случае, если переназначение подключённых к ним электрических цепей не приводит к изменениям в работе ПЭС.
Примеров таких контактов являются входы логических элементов, выполняющих элементарные функции. На рисунке 10 показана микросхема К155ЛА4, в которой контакты с номерами (1,2,13), (3,4,5) и (9,10,11) образуют 3 группы инвариантных выводов.
Другим характерным примером является разъём функциональной ячейки. В том случае, если заранее не оговаривается порядок подключения внешних цепей к схеме, то конструктор может переназначить подключаемые к контактам разъёма цепи исходя из изложенных выше соображений.
В схеме на рисунке первоначально принято подключение согласно таблице 2:
Таблица 2
| Номер вывода разъема, № | Номер проводника логической схемы подключаемого к разъему, 9№ (первоначальное назначение № проводника на № вывода разъема) | Длина проводника подключаемого к разъему, d (см). |
| 1 | 18 | 9,75 |
| 2 | 2 | 10,25 |
| 3 | 5 | 12,75 |
| 4 | 7 | 3,5 |
| 5 | 19 | 11,25 |
| 6 | 20 | 11,5 |
| 7 | 21 | 11 |
| 8 | 22 | 11,5 |
| 9 | 23 | 14,5 |
| 10 | 24 | 7,5 |
| 11 | 25 | 9,5 |
| 12 | 26 | 2,75 |
| 13 | 27 | 12,25 |
| 14 | 28 | 14 |
| Функция качества составляет F | 142 | |
Анализ конструкции показывает, что такое подключение не является оптимальным с точки зрения длины связей и условий трассировки.
Для улучшения первоначального назначения цепей применяются алгоритмы линейного назначения. Задачей данного этапа является подготовка исходных данных синтеза математической модели, которая лежит в основе алгоритма оптимизации. Рассмотрим методику построения математической модели.
При проектировании печатных плат, если закрепляем часть элементов схемы
, а оставшиеся элементы не связаны между собой 
, то значение длины связи можно выразить: 
, 
, где
- количество незакрепленных элементов, 
- матрица эффективности линейного назначения элементов, 
- при назначении 
-того элемента в 
-ую позицию. 
, 
.Получаем матрицу назначений:
, 
, 
.Функция качества (надо найти для
): 
.Для получения матрицы назначений в программе оптимизации требуется заполнить таблицу 3:
Таблица 3
Венгерский алгоритм линейного назначения
| Номер цепи | Инвариантные выводы | Контакты цепей | ||||
| Х: У | Х У | Х У | Х У | Х У | Х У | |
| 18 | 118: 19 | 36 30 | 93 30 | 84 64 | ||
| 2 | 118: 24 | 99 41 | 90 76 | |||
| 5 | 118: 29 | 60 41 | 30 76 | |||
| 7 | 118: 34 | 87 76 | ||||
| 19 | 118: 39 | 30 30 | 87 30 | |||
| 20 | 118: 44 | 93 41 | 63 76 | |||
| 21 | 118: 49 | 66 41 | 36 76 | |||
| 22 | 118: 54 | 96 76 | ||||
| 23 | 118: 59 | 36 41 | 93 76 | |||
| 24 | 118: 64 | 33 76 | ||||
| 25 | 118: 69 | 96 41 | 30 65 | 66 76 | ||
| 26 | 118: 74 | 33 41 | 37 65 | |||
| 27 | 118: 79: | 60 30 | ||||
| 28 | 118: 84 | 63 41 | ||||
Назначение цепей инвариантным выводам в курсовой работе выполняется с помощью венгерского алгоритма, который реализован в виде программы, работающей в диалоговом режиме. Для управления программой необходимы знания структуры алгоритма, Структурная схема "венгерского алгоритма" показана на рисунке 15: