Мегаобучалка Главная | О нас | Обратная связь  


Раздел 3. Размещение микросхем на коммутационных платах




 

Размещение микросхем (блоков) является следующим шагом синтеза конструкции после компоновки. На этапе размещения определяются места привязки микросхем к конструктивной основе (печатной плате), которые называются позициями, и ориентация элементов относительно сторон платы.

На данном этапе ставится задача, с помощью программы Placeing, реализующей метод ветвей и границ, найти оптимальное размещение на коммутационной плате блоков, исследуя различные стратегии решения.

Введем обозначения: Е={e1, e2,. en}-множество элементов схемы устройства, P={p1, p2,... pn}-множество установочных позиций на коммутационной плате для размещения элементов. Предполагается, что число элементов и число установочных позиций совпадают. Тогда задача размещения заключается в определении взаимно однозначного соответствия между множествами E и P.

Если все элементы однотипны, а все позиции равноправны, то общее количество возможных вариантов решений N!, где N - общее количество элементов в схеме. Поскольку N! растет очень быстро, данная задача имеет большую вычислительную сложность при проектировании реальных схем, и методы полного перебора обычно применять невозможно.



В такой постановке задача называется задачей дискретного размещения и для ее решения применяются различные комбинаторные методы. Комбинаторные методы размещения основаны на переборе вариантов решения. Из всех исследованных в процессе перебора решений выбирается тот, который имеет оптимальное значение целевой функции или критерия качества.

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

Введем функцию P (i) назначения элементов в позиции. P (i) принимает значение номера позиции, в которую алгоритм размещения назначает i-ый элемент. Суммарная длина соединения может быть рассчитана по формуле (2),

 

n n

L (P) =0,5 åå r ij d p (i) p (j) (2),

            i=1 j=1

 

где r ij - кол-во связей между i и j элементам, d p (i) p (j) - расстояние между позициями, в которых закреплены i и j элементы. æ 1, если P (i) =j, Введем функцию X ij =í. è 0, если P (i) =j. Тогда можно записать

 

n n n n

L (X) =0,5 0,5 åå å å r ij d kl X ik X jl (3)

            i=1 j=1 k=1 l=1

 

В такой постановке данная задача называется задачей квадратичного назначения.

Комбинаторный алгоритм размещения элементов

Одним из базовых методов решения комбинаторных задач перебора является метод ветвей и границ. Этот метод основан на сокращении перебора возможных решений путем отсечения заведомо неперспективных вариантов решений. Решение задачи состоит из следующей последовательности шагов:

1. Определяется последовательность выбора элементов. Для улучшения сходимости алгоритма к оптимальным решениям элементы в последовательности располагаются так, что каждый следующий элемент должен быть максимально связан с предыдущими элементами и минимально с последующими (Блок 1). Такой порядок позволяет уменьшить перебор за счет отсечения вариантов, не содержащих оптимальных решений задачи, т.к. при данной методике определения порядка выбора элементов получаются более точные нижние оценки подмножеств вариантов размещения. Будем выбирать элементы по максимальному значению фактора связности p: P=Dp-Dн. Первым элементом всегда является разъём, т.к для него выделена единственная установочная позиция.

2. Процесс оптимизации удобно представить в виде дерева решения задачи перебора. Каждая вершина соответствует одному подмножеству решения задачи перебора. На нулевом уровне находится вершина, соответствующая полному множеству всех вариантов размещения (7!), т.е. когда установлен разъём, а для остальных элементов назначение позиций не выбрано. На первом уровне располагаются 6 вершин подмножеств непересекающихся вариантов, порожденных закреплением первого элемента в различные позиции. На втором уровне располагаются (n-1) ×n вершин, соответствующих непересекающимся подмножествам всех вариантов закрепления первого и второго элементов во все установочные позиции. Продолжая деление, перейдем к n-ому уровню, на котором закреплены все элементы. Всего вершин на этом уровне N!, каждая из которых соответствует закреплению всех элементов.

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

Предположим, что выполнено директивное размещение i элементов. Остается (n-i) незакрепленных элементов. Дадим оценку F^ целевой функции F суммарной длины связей. Нижняя оценка состоит из трех слагаемых: оценка длины связи между не размещенными элементами F н^, оценка длины связи между не размещенными и размещенными элементами F нр^, значение длины связи между размещенными элементами F р.

 

F^ = F н^ + F нр^ + F р (4)

 

Значения нижних оценок записываются в вершинах дерева решений

Зная значения нижних оценок можно осуществить поиска оптимального решения. Исследование заключается в расчете нижних оценок вновь образованных подмножеств решения.

Существуют две стратегии поиска решений.

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

Следующим шагом выполняется проверка: проверяется количество вариантов во вновь образованных подмножествах. Если эти подмножества содержат по одному варианту, то делается вывод, что получены частные решения задачи размещения. Для них рассчитывается целевая функция. Среди этих значений ищется минимальное, и найденное значение называется верхней границей целевой функции (Fв^), найденной на данном шаге. Так как значения нижних оценок при детализации не уменьшается, то можно сделать вывод: подмножества решений, у которых нижние оценки хуже верхней границы могут в дальнейшем не исследоваться. Процедура повторяется до тех пор, пока не будут отсечены все подмножества вариантов кроме одного, для которого на очередном шаге была рассчитана верхняя граница. Этот вариант будет оптимальным решением.

Вторая стратегия - стратегия ныряния до дна. Алгоритм пытается получить частное решение как можно быстрее, с тем, чтобы получить расчетную Fв^ и выполнить отсечение неперспективных вершин. В этой стратегии детализация вершин выполняется по одной ветви, пока не будет по одному варианту решения. После исследования первой ветви выполняется отсечение неперспективных вариантов, выбирается вершина с минимальной оценкой Fн^ и снова выполняется процедура ветвления, пока не будет получено новое частное решение. Далее процесс повторяется, пока не будет получено оптимальное решение [3].

Последовательность действий для решения задачи размещения элементов:

Вводится множество элементов схемы Е={e1, e2,. e7}: от 1 до 7 - разъем и 6 микросхем; а также множество посадочных мест P={p1, p2,... p7}: от 1 до 7. Соответственно, исходными данными для размещения является ПЭС устройства (рис.8), чертеж ячейки, координаты посадочных мест для установки элементов (рис.9).


 

2) Ставим в соответствие множеству элементов схемы (микросхемам) множество вершин взвешенного графа (рис.7).


Рис.11.

 

В программе Placeing создаем и заполняем две матрицы: матрицу связей (по взвешенному графу на рис.11, создать файл с расширением. mxs, рис.12) и матрицу длин, расстояний (по чертежу ячейки на рис.9, создать файл с расширением. mxd, рис.13). Заполнив их, переходят к построению дерева решений. Алгоритм построения дерева описан выше.

 

Рис.12. Матрица связей.


Рис.13. Матрица длин.

 

Поставим 7 элемент в 7 позицию (е7 7p). Определим приоритетный ряд связи элементов друг с другом (последовательность выбора элементов). Начинают, как правило, с разъема, затем ищут элемент, максимально связанный с ним. После этого ищут элемент, который максимально связан с первым (который связан с разъемом). Причем, если с ним и любым другим максимально одинаково связаны несколько элементов, выбирают любой. Затем ищут элемент, наиболее связанный с разъемом и с 1-ым выбранным элементом (это определяется суммированием связей этих элементов по матрице связей) и т.д. до последнего. Получается последовательность, элементы в которой располагаются так, что каждый следующий элемент максимально связан с предыдущими элементами и минимально с последующими. Такой порядок позволяет уменьшить перебор за счет отсечения вариантов, не содержащих оптимальных решений задачи, так как при данной методике определения порядка выбора элементов получаются более точные нижние оценки подмножеств вариантов размещения. Результат данной операции:

 

   5    9      8 9       9 11

е7    е5    е6   е2 е4 е1  е3


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

Нижняя оценка состоит из трех слагаемых: оценка длины связи между не размещенными элементами F н^, оценка длины связи между не размещенными и размещенными элементами F нр^, значение длины связи между размещенными элементами Fр.

 

Fнг^ = F н^ + F р + Fнр^





 

Таким образом, построив дерево решений, была найдена ветка с минимальной оценкой (из этого следует, что найдена верхняя граница целевой функции Fв^), следовательно, найдено оптимальное решение. В соответствие с этим решением 7 элемент (разъем) устанавливается в 7 позицию, 5 элемент (5 микросхема) - в 5 позицию, 6 элемент - в 4 позицию, 2 элемент во 2 позицию, 4 элемент - в 1 позицию, 1 элемент - в 3 позицию, 3 элемент - в 6 позицию.

Рассмотрим критерий качества F (n) по шагам алгоритма n, то есть построим график увеличения нижней оценки Fн^ от 7 элемента к 3-ему в оптимальной ветке дерева (в оптимальном решении):

 

Рис.14. График зависимости значения нижней оценки по оптимальной ветви.


Таким образом, данный алгоритм удобен для нахождения оптимального варианта размещения элементов на печатной плате, так как он не подразумевает под собой перебора всех возможных N! (N! растет очень быстро) вариантов решения. Этот алгоритм основан на сокращении перебора возможных решений путем отсечения заведомо неперспективных вариантов решений, нижняя оценка которых меньше, либо равна нижней оценке (или верхней границе целевой функции) оптимального решения. Оптимальное решение находится достаточно быстро, так как используется программа Placeing. В ней есть калькулятор, быстро подсчитывающий значения нижних оценок в зависимости от варианта размещения. По ним и делается вывод о продолжении построения ветки дерева, либо об отсечении ее (их).

Программа 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 позицию.

 

Поможем в ✍️ написании учебной работы
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой



Читайте также:
Почему люди поддаются рекламе?: Только не надо искать ответы в качестве или количестве рекламы...
Модели организации как закрытой, открытой, частично открытой системы: Закрытая система имеет жесткие фиксированные границы, ее действия относительно независимы...
Личность ребенка как объект и субъект в образовательной технологии: В настоящее время в России идет становление новой системы образования, ориентированного на вхождение...
Почему человек чувствует себя несчастным?: Для начала определим, что такое несчастье. Несчастьем мы будем считать психологическое состояние...



©2015-2020 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (111)

Почему 1285321 студент выбрали МегаОбучалку...

Система поиска информации

Мобильная версия сайта

Удобная навигация

Нет шокирующей рекламы



(0.035 сек.)
Поможем в написании
> Курсовые, контрольные, дипломные и другие работы со скидкой до 25%
3 569 лучших специалисов, готовы оказать помощь 24/7