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

8.1. Получить у преподавателя схемы соединения микросхем и монтажное пространство, условия на размещение элементов в монтажном пространстве.

8.2. Для заданных вариантов электрической схемы и монтажного пространства составить необходимые математические модели: граф электрической схемы и матрицу связности; графовую решетку и матрицу расстояний.

8.3. Запустить систему PSAPR; установить зеленый прямоугольник на окно «Размещение на плате».

8.4. На экране дисплея набрать заданную схему соединения корпусов.

8.5. На поле монтажного пространства из 40 свободных позиций оставить не более 15 позиций. Остальные ненужные перечеркнуть красным крестом. (В про-грамме за начало координат взята точка с координатами (0,0) ).

8.6. Введенную схему разместить на заданном монтажном пространстве с помощью трех алгоритмов.

8.7. Результаты размещения по всем программам оценить по критериям: минимальной суммарной длины соединений, равномерности рисунков на плате, числу слоев в платах, числу длинных соединений.

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

8.9. Оценить эффективность исследуемых алгоритмов размещения и дать рекомендации по их применению.

 

СОДЕРЖАНИЕ ОТЧЕТА

9.1.Цель работы.

9.2.Сведение из теории. Задача размещения, ее математическая формули-ровка. Методы оценки алгоритмов размещения.

9.3.Принципиальные электрические схемы и схемы монтажного про-странства.

9.4.Математичесие модели схемы и монтажного пространства.

9.5.Условия размещения элементов.

9.6.Эскизы схем размещения модулей в монтажном пространстве (копии экрана).

9.7.Ручные размещения элементов по алгоритмам.

9.7.Сравнительные результаты и характеристики алгоритмов.

9.8.Рекомендации по применению алгоритмов.

9.9.Выводы.

 

 

КОНТРОЛЬНЫЕ ВОПРОСЫ

10.1. Сформулируйте цели задачи размещения.

10.2. Математическая формулировка задачи размещения.

10.3. Назовите основные методы оценки эффективности алгоритмов размещения.

10.4. Каким образом можно оценить качество размещения элементов?

10.5. Назовите последовательность действий метода обратного размещения.

10.6. Назовите последовательность действий последовательного метода размещения.

10.7. Назовите последовательность действий предварительного метода размещения.

10.8. Поясните порядок работы с программами размещения.

 

10.9. Каким образом вводятся исходные данные для работы программ?

10.10. Назовите достоинства и недостатки изучаемых алгоритмов.

 

 

ЛАБОРАТОРНАЯ РАБОТА №4

ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ ИТЕРАЦИОННЫХ

АЛГОРИТМОВ РАЗМЕЩЕНИЯ

Цель работы– исследовать эффективность итерационных алгоритмов размещения конструктивных элементов РЭС в коммутационном пространстве; освоить особенности алгоритмизации и программирования задач улучшения размещения на ПВЭМ итерационными методами.

 

ИТЕРАЦИОННЫЕ АЛГОРИТМЫ РАЗМЕЩЕНИЯ

Алгоритмы итерационного типа относятся к группе эвристических алгоритмов [1] и основаны на парной или групповой перестановках компонентов [2]. Они требуют начального размещения и обычно используются для улучшения результатов исходного размещения. При этом результат размещения зависит от начального размещения. Применяются итерационные алгоритмы для решения задач размещения с различными критериями оптимизации и в большинстве случаев приводят к получению локальных экстремумов целевой функции F(X). Они требуют больших затрат машинного времени.

 

1.1. Алгоритм парных перестановок

Сущность алгоритма парных перестановок заключается в последователь-ном целесообразном улучшении произвольного начального размещения элемен-тов на плате по выбранному критерию путем парных перестановок [2]. С этой целью на каждой итерации алгоритма производится вычисление приращений суммарной длины всех связей для всевозможных n(n-1)/2 парных перестановок n элементов. Затем из всего множества перестановок, дающих отрицательные приращения, выбирается подмножество, которое удовлетворяет следующим требованиям:

позволяет максимально уменьшить длину всех связей;

подмножество образует лишь независимые перестановки, то есть такие парные перестановки, в которые входят элементы, не связанные с элементами других переставляемых пар.

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

 

АЛГОРИТМ

1. Вычислить матрицу расстояний D между позициями на плате по одной из формул: ________________

d_ij = Ö (x_i – x_j)² + (y_i – y_j)² или (4.1)

d_ij = ½x_i – x_j½ + ½y_i – y_j½. (4.2)

2. Составить матрицу связей R между элементами. Элементы матрицы r_ij численно равны количеству проводников, соединяющих контакты элементов. Матрицу связей составляем в каждом цикле алгоритма.

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

3. Вычислить матрицу геометрии А по формуле

A = (r _ij d _ij) _n._n . (4.3)

4. Вычислить суммарную длину соединений L по формуле

N n

L (G) = ½ å å a _ij. (4.4)

i=1 j=1

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

n

DL = 2 r _ij d _ij – å(r _ij – r _ij) (d _ij – d _ij) . (4.5)

к=1

6. Проверить наличие отрицательных элементов в матрице приращений. Если их нет, то идти к 8, иначе к 7.

7. Среди множества отрицательных элементов матрицы ΔL находим мини-мальный Δl _ij. Если их несколько, тот берем любой. Осуществляем пере-становку строк и столбцов с номерами i и j матрицы R. Переходим к 2.

Конец.

 

Достоинствами алгоритма парных перестановок являются: возможность значительного улучшения начального решения, простота и наглядность.

К недостаткам следует отнести:

а) значительные затраты машинного времени;

б) возможность получения большого количества решений, если несколько пар элементов имеют одинаковые минимальные значения Δl_ij. В этом случае переставляться могут элементы любой пары;

в) алгоритм уменьшает суммарную длину соединений, но не приводит её к минимальной. Объясняется это тем, что уменьшение длины происходит только между двумя элементами. В то же время между другими элементами длина мо-жет увеличиваться;

г) возможен случай, когда перестановка отдельных элементов не приводит к уменьшению суммарной длины, хотя ее можно сократить групповой пере-становкой элементов (парами, тройками и т.д.);

д) результат работы алгоритма зависит от первоначального размещения элементов в монтажном пространстве.

Для получения более точных результатов целесообразно сочетать быстрый обратный алгоритм с улучшающим размещение итерационным.

Среди итерационных алгоритмов наиболее эффективны методы, основан-ные на парных перестановках элементов, при этом оказывается нецелесо-образным рассматривать перестановки элементов в усеченных окрестностях, что приводит к существенным сокращениям времени при той же точности резуль-тата. Алгоритмы парных перестановок позволяют уменьшить длину межсоеди-нений от 1% до 50% в зависимости от начального размещения. Наибольшая скорость уменьшения длины соединений наблюдается на первых итерациях, монотонно уменьшаясь к значениям, близким к 1% при числе итераций К>5.

Важной характеристикой алгоритма парных перестановок является число успешных обменов среди общего числа просмотренных. Этот коэффициент минимален при использовании всех возможных n(n-1)/2 перестановок на каждой итерации и не превышает 5%. При усечении окрестности исследуемых перестановок, например, обмене лишь соседних элементов в «хорошем» начальном размещении, указанный коэффициент может достигать 50%.

 

ПРИМЕР 4.1

 

В позиции коммутационного поля с координатами l₁=(1,1), l₂=(2,1), l₃=(3,1), l₄=(4,1) размещены четыре конструктивных элемента (рис.4.1). Схема соеди-нений элементов представлена графом (рис.4.2). Требуется по критерию мини-мума суммарной длины улучшить начальное размещение.

 

Решение

Вычислим матрицу расстояний D между позициями по формуле (4.2):

 

1 2 3 4

1 0 1 2 3

D =2 1 0 1 2

3 2 1 0 1

4 3 2 1 0 .

 

По графу (рис.4.2) электрической схемы составим матрицу связей R₀ между элементами

1 2 3 4

1 0 2 0 3

R₀ = 2 2 0 1 0

3 0 1 0 1

4 3 0 1 0 .

 

Вычислим длину соединений начального размещения

 

1 2 3 4

1 0 2 0 9

A₀ = 2 2 0 1 0

3 0 1 0 1 L₁=13.

4 9 0 1 0 .

 

Определим по формуле (4.5) элементы матрицы приращения:

Δl₁₂ = 2r₁₂∙d₁₂ – [(r₁₁-r₂₁)(d₁₁-d₂₁) + (r₁₂-r₂₂)(d₁₂-d₂₂) + (r₁₃-r₂₃)(d₁₃-d₂₃) + (r₁₄-r₂₄)(d₁₄-d₂₄) = 2∙1∙2 – [(0-2)(0-1) + (2-0)(1-0) + (0-1)(2-1) + (3-0)(3-2)] =-2;

 

Δl₁₃ = 2r₁₃∙d₁₃ – [(r₁₁-r₃₁)(d₁₁-d₃₁) + (r₁₂-r₃₂)(d₁₂-d₃₂) + (r₁₃-r₃₃)(d₁₃-d₃₃) + (r₁₄-r₃₄)(d₁₄-d₃₄) = 2∙0∙2 – [(0-0)(0-2) + (2-1)(1-1) + (0-0)(2-0) + (3-1)(3-1)] = – 4; и т.д.

 

1 2 3 4

1 0 -2 -4 3

ΔL₀ = 2 -2 0 3 -2

3 -4 3 0 -2

4 3 -2 -2 0 .

Рис.4.1

 

 

t₁ t₂

t₄ t₃

 

Рис.4.2

 

Рис. 4.3

 

Поскольку минимальный элемент Δl₁₃, переставим 1-е и 3-и строки и столбцы в матрице R₀, а конструктивные элементы 1-й и 3-й поменяем местами (см. рис. 4.3). Получим матрицу

 

3 2 1 4

3 0 1 0 1

R₁ = 2 1 0 2 0

1 0 2 0 3

4 1 0 3 0 .

 

По матрице геометрии

3 2 1 4

3 0 1 0 3

А₁ =2 1 0 2 0

1 0 2 0 3

4 3 0 3 0

определим длину соединений: L₁ = 9.

Снова вычислим матрицу приращения

 

3 2 1 4

3 0 1 4 4

ΔL₁ = 2 1 0 4 0

1 4 4 0 1

4 4 0 1 0 .

 

Все элементы матрицы ΔL₁ положительные. Следовательно, процесс пере-становки окончен, и полученный результат (рис.4.3) окончательный.

 

ДОМАШНЕЕ ЗАДАНИЕ

 

2.1. Ознакомится с итерационными методами решения задачи размещения конструктивных элементов РЭС.

2.2. Изучить алгоритм парных перестановок.

2.3. Подготовить данные к эксперименту.

2.4. Провести вручную улучшение размещения одного из узлов методом парных перестановок.