Материал: Лабораторная работа№ 3, 4 Исследование алгоритмов размещения конструктивных элементов и итерационных алгоритмов

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

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

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

1. ОСНОВНЫЕ МЕТОДЫ ОЦЕНКИ ЭФФЕКТИВНОСТИ АЛГОРИТМОВ РАЗМЕЩЕНИЯ

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

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

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

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

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

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

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

41

который даст размещение с меньшей суммарной длиной соединений, и будет считаться лучшим.

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

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

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

2. ОБЩИЕ СВЕДЕНИЯ О ЗАДАЧЕ РАЗМЕЩЕНИЯ

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

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

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

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

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

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

42

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

расстояний размещённых элементов P = || pij ||n m .

где rij – элемент матрицы связности R, а pij – элемент матрицы размещения P. Математически задача формулируется следующим образом [1 - 5].

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

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

3. АЛГОРИТМ ПОСЛЕДОВАТЕЛЬНОГО РАЗМЕЩЕНИЯ

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

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

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

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

43

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

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

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

8.Найти минимум di среди оставшихся (m – 1) элементов; просмотреть строку с минимальным di и найти минимальный dij среди помеченных элементов. Здесь 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 свободных позиций с координатами центров позиций соответственно:

x1=2, y1=1; x2=2, y2=2; x3=3, y3=2; x4=4, y4=2; x5=1, y5=3; x6=2, y6=3; x7=4, y7=4.

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

Решение

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

dij = |xi - xj| + |yi - yj|

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

7

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

J=1

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

44

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

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

7

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

J=1

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

7

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

J=1

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

45