Материал: Laboratornaya_rabota_3i4-n

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

ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ АЛГОРИТМОВ

РАЗМЕЩЕНИЯ КОНСТРУКТИВНЫХ ЭЛЕМЕНТОВ РЭС

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

1. ОСНОВНЫЕ МЕТОДЫ ОЦЕНКИ ЭФФЕКТИВНОСТИ

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

При разработке алгоритмов и программ следует стремиться к наиболее полному удовлетворению требований, предъявляемых к ним: минимальная продолжительность решения, максимальный объем задач при заданной емкости оперативной емкости ЭВМ, максимальная точность решения, высокая надёжность, эффективность, завершённость, понятность и т.д.

Перечисленные показатели определяют качество программного обеспече-ния САПР. Причём на этапе разработки алгоритмов достаточно учесть такие показатели, как точность, временная и емкостная сложность, а при разработке программ или их сравнении следует учитывать и остальные показатели [1 – 4].

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

Для оценки качества решения рекомендуются два подхода [1]:

1. применение тест – задач;

2. статистическая обработка результатов.

Первый способ заключается в том, что каким-либо образом находят точное (глобально – оптимальное) решение F_opt некоторого варианта W задачи Z. Затем этот вариант W решают с помощью алгоритмов А₁, А₂,…, А_n и анализируют, насколько i–й (i =1, n) результат отличается от F_opt. Например, алгоритмы размещения равногабаритных элементов по критерию минимума суммарной длины соединений могут сравниваться по результатам решения тест-задачи Штейнберга. В ней предлагается на 36 заданных позиций разместить 34 элемента, матрица связности для которых также известна. Тот алгоритм, который даст размещение с меньшей суммарной длиной соединений, и будет считаться лучшим.

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

Второй – статистический способ оценки качества решения состоит в том, что формируется m вариантов задачи Z. Решив эти варианты с помощью алго-ритмов А₁, А₂, …, А_n, получают n результатов R_i (i=1, n), которые оценивается рядом показателей P = {P₁, P₂, …, P_n} и выполняют их статистическую обработку и сравнение. Такой подход позволяет получить наиболее объективные резуль-таты для оценки качества приближенных алгоритмов.

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

2. Общие сведения о задаче размещения

После распределения конструктивных элементов РЭС по коммутационным пространствам различного уровня иерархии, для каждой полученной в результате компоновки сборочной единицы производят размещение включенных в ее состав элементов предыдущего уровня, т.е. выбирают такое их взаимное расположение, при котором наилучшим образом учитываются предъявляемые к аппаратуре требования [1 – 3, 7 11].

Исходными данными для решения задачи размещения являются:

• данные о конфигурации и размерах коммутационного пространства, определяемые требованиями установки и крепления соответствующей сбороч-ной единицы в аппаратуре;

• количество и геометрические размеры конструктивных элементов, подле-жащих размещению;

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

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

В том случае, если в качестве критерия размещения используют минимум суммарной взвешенной длины соединений, необходимо сформировать матрицу расстояний размещённых элементов P = || p_ij ||_nm .

Здесь P_ij = |x_i - x_j| + |y_i - y_j|, а x_i, x_j и y_i, y_j – координаты позиций, в которые размещены соответственно i–й и j–й модули.

Т огда суммарная взвешенная длина соединений будет равна

где r_ij – элемент матрицы связности R, а p_ij – элемент матрицы размещения P.

Математически задача формулируется следующим образом [1 - 5]. Электри-ческая схема представляется в виде мультиграфа, а моделью монтажного про-странства служит графовая решётка. Требуется вершины мультиграфа размес-тить в узлы графовой решётки таким образом, чтобы суммарная длина ребер размещенного мультиграфа была минимальна.

Задача размещения является комбинаторной, т.е. может быть решена толь-ко полным перебором (для размещения n элементов на n позиций существует n! вариантов размещения). Для решения задач размещения разработано большое количество различных алгоритмов [1 – 4]. В данной работе рассмотрим эвристи-ческие алгоритмы

3. Алгоритм последовательного размещения

Алгоритм включает такую последовательность действий.

1. Сформировать матрицу расстояний D, элементы которой будем определять по формуле ортогональной метрики:

d_ij = |x_i - x_j| + |y_i - y_j| . (3.2)

2. Для каждой строки матрицы D определить суммарное значение:

3. Ввести матрицу связности R и ее размерность n.

4.Для каждой строки матрицы связности R определить сумму элементов:

5. Найти минимальное значение d_i, если B=i, то пометить столбец j=B.

6. Найти максимальное значение r_i , если Е=i, то удалить столбец j=B.

7. Разместить элемент Е в позицию В.

8. Найти минимум d_i среди оставшихся (m – 1) элементов; просмотреть строку с минимальным d_i и найти минимальный d_ij среди помеченных элементов. Здесь j=B. Определить, какой элемент расположен в позиции j; вновь присвоить B=i, j=B и пометить столбец j.

9. Рассмотреть строку Е в матрице R и найти максимальный r: присвоить E=i, j=E и пометить столбец j.

10. Найти число помеченных столбцов k; если k<n, идти к 8, иначе – к 11.

11. Подсчитать суммарную длину соединений.

ПРИМЕР 3.1

Дано монтажное пространство (печатная плата) (рис.3.1,а), в котором име-ется 7 свободных позиций с координатами центров позиций соответственно: x₁=2, y₁=1; x₂=2, y₂=2; x₃=3, y₃=2; x₄=4, y₄=2; x₅=1, y₅=3; x₆=2, y₆=3; x₇=4, y₇=4.

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

Решение

В качестве модели печатной платы возьмем решетку графа (рис. 3.2, б) и по формуле

d_ij = |x_i - x_j| + |y_i - y_j|

вычислим матрицу расстояний D:

1 2 3 4 5 6 7

1 0 1 2 3 3 2 5 16

2 1 0 1 2 2 1 4 [11]

3 2 1 0 1 3 2 3 12

D = 4 3 2 1 0 4 3 2 15

5 3 2 3 4 0 1 4 17

6 2 1 2 3 1 0 3 12

7 5 4 3 2 4 3 0 21 .

7

Определим сумму элементов  d_ij в каждой i-й строке матрицы и запи-

J=1

шем ее справа от матрицы. Сумма показывает суммарную удаленность i-й позиции от всех остальных.

Схему соединения корпусов представим в виде мультиграфа (рис. 3.2, б), для которого построим матрицу связности R:

1 2 3 4 5 6 7

1 0 3 0 2 2 0 1 8

2 3 0 3 0 5 0 0 [11]

3 0 3 0 2 0 0 0 5

R = 4 2 0 2 0 0 0 0 4

5 2 5 0 0 0 3 0 10

6 0 0 0 0 3 0 3 6

7 1 0 0 0 0 3 0 4 .

Суммирование элементов r_ij в строках матрицы дает локальную степень каждой вершины графа.

7

Среди  d_ij находим минимальное число, оно равно 11 и соответствует

J=1

позиции №2. Звездочками помечают все элементы второго столбца матрицы

7

D. Среди  r_ij находим максимальное число, оно равно 11 у вершины №2.

J=1

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

1 3 4 5 6 7

1 0 0 2 2 0 1

2 3 3 0 [5] 0 0

3 0 0 2 0 0 0

R = 4 2 2 0 0 0 0

5 2 0 0 0 3 0

6 0 0 0 3 0 3

7 1 0 0 0 3 0

1 2* 3 4 5 6 7

1 0 1 2 3 3 2 5 16

2 1 0 1 2 2 1 4

3 2 [1] 0 1 3 2 3 [12]

D = 4 3 2 1 0 4 3 2 15

5 3 2 3 4 0 1 4 17

6 2 1 2 3 1 0 3 12

7 5 4 3 2 4 3 0 21 .

7

Среди оставшихся  d_ij находим минимальное число. Оно равно 12 сразу

J=1

у двух позиций: №3 и №6. Берем 1-ю по порядку позицию №3. Помечаем все элементы третьего столбца матрицы D. Проходим вторую строку матрицы R и находим, что в ней максимальный элемент 5, который находится в 5-м столбце. Следовательно, модуль №5 размещаем в позицию №3, а 5-й столбец матрицы R из дальнейшего рассмотрения исключается. Получили

1 3 4 6 7

1 0 0 2 0 1

2 3 [3] 0 0 0

3 0 0 2 0 0

R = 4 2 2 0 0 0

5 2 0 0 3 0

6 0 0 0 0 3

7 1 0 0 3 0

1 2* 3* 4 5 6 7

1 0 1 2 3 3 2 5 16

2 1 0 1 2 2 1 4

3 2 1 0 1 3 2 3

D = 4 3 2 1 0 4 3 2 15

5 3 2 3 4 0 1 4 17

6 2 [1] 2 3 1 0 3 [12]

7 5 4 3 2 4 3 0 21

7

На следующем шаге отыскиваем min из  d_6j =12 в строке №6.

J=1

Просматриваем шестую строку матрицы D и среди помеченных элементов 2-го и 3-го столбцов выбираем минимальный. Так определяем, к какой из уже занятых позиций, позиция №6 находится ближе всего: min[d₆₂, d₆₃] = d₆₂ = 1 – ко 2-й. Во второй позиции уже находится модуль №2. Поэтому просматриваем вторую строку матрицы R и выбираем максимальный элемент r₂₁ = 3. Он соответствует 1-му модулю, поэтому элемент №1 размещаем в позицию №6.

Исключаем из дальнейшего рассмотрения первый столбец матрицы R.

Получили матрицы

3 4 6 7

1 0 2 0 1

2 3 0 0 0

3 0 2 0 0

R = 4 2 0 0 0

5 0 0 [3] 0

6 0 0 0 3

7 0 0 3 0

1 2* 3* 4 5 6* 7

1 0 1 2 3 3 2 5 16

2 1 0 1 2 2 1 4

3 2 1 0 1 3 2 3

D = 4 3 2 [1] 0 4 3 2 [15]

5 3 2 3 4 0 1 4 17

6 2 1 2 3 1 0 3

7 5 4 3 2 4 3 0 21 .

7

Далее выбираем min из  d_ij = 15 в 4-й строке. В четвертой строке матрицы

J=1

D среди помеченных элементов d₄₂, d₄₃, d₄₆ минимальный d₄₃ = 1.Это говорит о том, что до позиции №4 ближе всех позиция №3, в которой уже размещен модуль №5. Поэтому просматриваем пятую строку матрицы R и среди оставшихся в ней элементов находим минимальный: r₅₆ = 3 в шестом столбце. Тогда модуль №6 размещаем в позицию №4 и исключаем из дальнейшего рассмотрения столбец №6 матрицы R:

3 4 7

1 0 2 1

2 [3] 0 0

3 0 2 0

R = 4 2 0 2

5 0 0 0

6 0 0 3

7 0 0 0

1 2* 3* 4* 5 6* 7

1 0 [1] 2 3 3 2 5 [16]

2 1 0 1 2 2 1 4

3 2 1 0 1 3 2 3

D = 4 3 2 1 0 4 3 2

5 3 2 3 4 0 1 4 17

6 2 1 2 3 1 0 3

7 5 4 3 2 4 3 0 21 .

7

Вновь выбираем минимальную из оставшихся сумм:  d_1j = 16 для пози-

J=1

ции №1. Просматриваем первую строку матрицы D и среди помеченных элементов {d₁₂, d₁₃, d₁₄, d₁₆} находим min: это d₁₂ = 1. Значит, от позиции №1 наименее удалена позиция №2, в которой находится модуль №2. Помечаем все элементы первого столбца матрицы D. Просматриваем вторую строку матрицы R и выбираем максимальный элемент r₂₃ = 3 для элемента №3. Его устанавливаем в 1-ю позицию, а 3-й столбец матрицы исключаем из дальнейшего рассмотрения: