Последовательный алгоритм компоновки с равными числу вершин в каждом куске

Министерство  Образования РФ

Казанский Государственный Технический Университет  им. А.Н. Туполева

_________________________________________________________________

Кафедра ИТП ЭВС

 

 

 

«Последовательный алгоритм компоновки с равными числу вершин в каждом куске»

 

Пояснительная записка к курсовой работе по дисциплине:

“Информационные технологии проектирования ЭВС”

 

 

 

выполнил: студент 

гр.4413 Латифуллин Ф.Ф.

проверила: доцент

Воронова  В.В.

Оценка _________

         Подпись_________

 

 

Казань 2010

Содержание:

         Введение……………………………………………………………     3 

    1. Теоретическая часть

         1.1 Алгоритмы компоновки……….…………………………..…..     4

         1.2 Последовательный алгоритм компоновки …………………..     5

         1.3 Алгоритм  компоновки……………………..…………………..    6

     2. Практическая  часть

         2.1 Анализ задания…………………………………………………   8

         2.2 Инструкция пользователя…..…….…………………………..  10

    3. Заключение…………………………………………….….………     14

    4. Список используемой литературы……………………….….…    15

    5. Приложение

       5.1 Листинг программы…………………………………………....     16

       5.2 Ручной счет……………………………………………………..     31

 

 

 

 

 

 

 

 

 

 

 

 

ВВЕДЕНИЕ

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

 

 

 

 

 

 

 

 

 

 

 

1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

 

1.1 Алгоритмы компоновки

На этапе  конструкторского проектирования решаются вопросы, связанные с компоновкой  элементов логической схемы в  модули, модулей в ячейки, ячеек  в панели и т. д. Эти задачи в  общем случае тесно связаны между  собой, и их решение позволяет  значительно сократить затраты  и трудоемкость указанного этапа  в САПР. Обычно задачи компоновки рассматриваются  как процесс принятия решений  в определенных или неопределенных условиях, в результате выполнения которого части логической схемы  располагаются в конструктивных элементах i-го уровня, а эти элементы размещаются в конструктивных элементах (i+1) –го уровня и т. д., причем расположение выполняется с оптимизацией по выбранному критерию.

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

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

Известные алгоритмы компоновки можно условно  разбить на пять групп:

1. алгоритмы, использующие методы целочисленного программирования;
2. последовательные алгоритмы;
3. итерационные алгоритмы;
4. смешанные алгоритмы.

 

1.2 Последовательные алгоритмы компоновки

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

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

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

В алгоритмах, использующих принцип  раздельного выбора элемента и позиции  его установки, сначала определяют размещаемый элемент. В качестве критерия выбора используют оценку степени  связности элемента. Затем в соответствии с оценкой качества (оптимизации) – место установки элемента. Чаще всего в качестве оценки выступает  – “цена назначения”.

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

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

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

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

1.3 Последовательный алгоритм разбиения графа G = (X, E) на ℓ  кусков G₁,…,G_ℓ  равных по числу вершин в каждом куске заданному n.

Замечание. Некоторые вершины графа жестко закреплены за определенными кусками, причем в каждом куске должно находиться не более одной запрещенной вершины. Обозначим Q – множество запрещенных вершин.

Алгоритм.

1. Вычисляем матрицу смежности A=||a_ij||_nxn.
2. Выделяем первую запрещенную вершину X_v из Q и помещаем ее в первый кусок G1={ x_v }. Составляем список Г(x_v)  вершин, смежных x_v.
3. Для вершины x_i ϵ Г(x_v) определяем относительные веса

δ (x_v) = ρ(x_i)-

где ρ(x_i) – локальная степень вершины x_i , ρ(x_i) = _; – число ребер, соединяющих вершину x_i с вершинами x_j , вошедшими в G1;

m – число вершин G1 на текущем шаге работы алгоритма. Переход к п.4.

4. Выбираем вершину x_s , для которой ). Если таких вершин несколько, то выбираем вершину с большой локальной степенью ρ(x_i). Переход к п.5.
5. Полученную вершину x_s помещаем в кусок G1: G1={ x_v x_s }. Переход к п.6.
6. Подсчитываем число n₁ вершин в куске G1. Если n₁ < n, где n  - заданное число вершин в каждом куске, то переход к п.8.
7. Если n₁ = n, кусок G1 сформирован, тогда переход к п.9.
8. Добавляем в список Г(x_v) вершины, смежные вершинам, вошедшим в кусок G1. Переход к п.3.
9. Удаляем из матрицы A строки и столбцы, соответствующие номерам вершин, вошедших в кусок G1. Для формирования следующего куска G2, начиная со следующей запрещенной вершины, процедура повторяется с п.2. Если сформирован последний кусок, переход к п.10.
10. Конец работы алгоритма.

 

 

 

 

 

 

 

 

 

 

2. ПРАКТИЧЕСКАЯ ЧАСТЬ

Дано:

1) Схема соединений (см. задание).

2) Число  элементов равно m=16.

3) Кол-во  кусков разбиения схемы: ℓ = 4.

4) Число  элементов в каждом куске: n = 4.

5) Список  запрещенных вершин Q = {}

Требуется:

Провести  компоновку блоков используя последовательный  алгоритм разбиения графа G = (X, E) на ℓ кусков G₁,…,G_ℓ  равных по числу вершин в каждом куске заданному n с учетом списка запрещенных вершин. 

Решение:

1. Описываем схему G(X,E).

 

2. Составим матрицу смежности:

 

		x1	x2	x3	x4	x5	x6	x7	x8	x9	x10	x11	x12	x13	x14	x15	x16	Ρ
	x1	0	1	0	0	0	1	0	0	0	0	0	0	0	0	0	0	2
	x2	1	0	0	0	0	1	1	0	0	0	0	0	0	0	0	0	3
	x3	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0	1
	x4	0	0	0	0	1	0	0	1	1	0	0	0	0	0	0	0	3
	x5	0	0	0	1	0	0	0	1	1	0	0	0	0	0	0	0	3
	x6	1	1	0	0	0	0	1	0	0	1	1	0	0	0	0	0	5
	x7	0	1	1	0	0	1	0	0	0	0	1	0	0	0	0	0	4
A=	x8	0	0	0	1	1	0	0	0	2	0	1	1	1	0	0	0	7
	x9	0	0	0	1	1	0	0	2	0	0	0	0	1	0	0	0	5
	x10	0	0	0	0	0	1	0	0	0	0	1	1	0	1	1	0	5
	x11	0	0	0	0	0	1	1	1	0	1	0	1	1	1	0	0	7
	x12	0	0	0	0	0	0	0	1	0	1	1	0	1	0	1	0	5
	x13	0	0	0	0	0	0	0	1	1	0	1	1	0	0	0	1	5
	x14	0	0	0	0	0	0	0	0	0	1	1	0	0	0	1	1	4
	x15	0	0	0	0	0	0	0	0	0	1	0	1	0	1	0	1	4
	x16	0	0	0	0	0	0	0	0	0	0	0	0	1	1	1	0	3

 

3. Разработаем программу в соответствии с заданным алгоритмом, на языке программирования TC.

 

 

 

 

2.2. Инструкция пользователя

Программа написана на языке TC. Необходимая минимальная конфигурация компьютера для нормального функционирования программы: ОС Microsoft Windows 98/Me/2000/XP/Vista/7, процессор Pentium II 336 МГц, 64 МБ оперативной памяти, видеокарта 32 МБ.

1) Для начала работы программы необходимо запустить файл “FAN1.exe”. В появившемся окне вводим общее количество элементов графа, в нашем случае 16, нажимаем на кнопку «Enter».  Далее заполняем матрицу смежности. Рис. 1

Рис. 1

 

2) После  заполнения матрицы водим количество запрещенных вершин, у нас их 4 нажимаем на кнопку «Enter». Задаем запрещенные вершины X7, X14, X15, X5 нажимаем на кнопку «Enter».  (Рис. 2).

Рис. 2

3) Продолжаем  нажимать на кнопку «Enter»., пока не появиться новое окно со всеми сформированными (Рис. 3 - 7).

Рис. 3

Рис. 4

Рис. 5

Рис. 6

Рис. 7

4) Выход из программы осуществляется  нажатием на «красный крестик»  в правом верхнем углу окон.

 

 

3. Заключение

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

В результате была получена следующая  компоновка:

    G1 = { X7, X3, X2, X1}

    G2 = { X14, X16, X10, X6}

    G3 = { X15, X12, X11, X13}

    G4 = { X5, X4, X8, X9}

 

 

 

 

 

 

 

4. Список использованной литературы
1. Воронова В.В. Автоматизация проектирования электронных средств: Учебное пособие, Казань: Издательство КГТУ, 2000.
2. Курейчик В.М. Математическое обеспечение конструкторского и технологического проектирования с применением САПР, Москва: «Радио и связь», 1990.
3. Морзов К.К., Одиноков В.Г., Курейчик В.М. Автоматизированное проектирование конструкций радиоэлектронной аппаратуры, Москва: «Радио и связь», 1983.
4. Ильин В.Н., Фролкин В.Т., Бутко А.И. и др. Автоматизация схемотехнического проектирования: Учебное пособие для вузов, Москва: «Радио и связь», 1987.
5. Деньдобренко Б.Н. Автоматизация конструирования РЭА, Москва: «Высшая школа», 1980.