49717 (Автоматизация системного проектирования), страница 3

Рис.1. Имитационная модель необходимого прямого управления

Сеть Петри, которая обеспечивает необходимое прямое управление показана на рисунке. Понятно, что в месте р₁ не может накопится более одной детали, при любых переходах системы. t₀, t₁, t₂ - время переходов системы. Система безопасна, т.к. операции не выполняются параллельно. Только после выхода детали на конвейер – начинается обработка следующей детали. Хотя было бы рационально использовать обработку на станке Ст1 и параллельно с ней вести обработку другой детали на станке Ст2. При этом увеличилась бы производительность выпуска деталей. Тогда последовательность операций была бы такая:

1. Перемещение детали от конвейера H1 к станку Ст1 роботом R1.

2. Перемещение детали от станка Ст1 к станку Ст2 роботом R2.

3. Получение метки на перемещение следующей детали от конвейера H1 к станку Ст1 роботом R1.

4. Перемещение детали от станка Ст2 к конвейеру Н2 роботом R1.

5. Получение метки на перемещение роботом R2 детали от станка Ст1 к станку Ст2.

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

Задание 3. Методы постановки задач и алгоритмы автоматизированного проектирования средств вычислительной техники

3.1 Выбрать схему электрическую принципиальную

Выбираем схему

Рис.2. Принципиальная электрическая схема устройства

3.2 Провести формализацию и, используя два алгоритма (последовательно-групповой и алгоритм Штейнберга), провести размещение микросхем на печатной плате.

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

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

Такими критериями могут быть:

- минимум типов конструктивно законченных частей;

- плотность компоновки, минимум соединений между устройствами;

- простота диагностики и др.

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

Список кругов формируется в виде текстового файла с обязательным перечислением всех соединений следующего вида:

...

В итоге образуется специальный файл электрических соединений.

Составим формальный список кругов, выделив их из принципиальной схемы:

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

В случае минимизации суммарной взвешенной длины соединений формула для расчета изменения значения целевой функции при перестановке местами элементов r_i и r_j, закрепленных в позициях t_f и t_g, имеет вид:

где p и h(p) – порядковый номер и позиция закрепления неподвижного элемента r_p.

Если , то осуществляют перестановку r_i и r_j, что приводит к уменьшению целевой функции на , после чего делают поиск и перестановку следующего пара элементов и т.д.

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

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

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

Частичным случаем итерационного алгоритма является алгоритм Штейнберга или так называемый алгоритм парных перестановок.

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

Последовательные алгоритмы основаны на предположении, что для получения оптимального размещения необходимо в соседних позициях располагать элементы, максимально связаны друг с другом. Сущность этих алгоритмов складывается в последовательном закреплении заданного набора конструктивных элементов на коммутационной плате относительно тех, что были установлены раньше. В качестве сначала закрепленных на плате элементов обычно выбирают разнимания, которые искусственно «раздвигают» к краям платы. При этом все контакты разниманий равномерно распределяются по секциям (столбцам и строкам координатной сетки). На каждом l шаге (l=1,2.,n) для установки на коммутационную x0 плату выбирают элемент из числа еще не размещенных, что имеет максимальную степень связности с ранее закрепленными элементами Rl-1. В большинстве используемых в это время алгоритмов оценку степени связности делают по одной из следующих формул:

где с_іj – коэффициент взвешенной связности элементов i и j;

J_l-1 – множество индексов элементов, закрепленных на предыдущих l-1 шагах;

n – общее число размещенных элементов.

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

В частности, если критерием оптимума является минимум суммарной взвешенной длины соединений, то

где d_fj – расстояние между f-ой позицией установки элемента x0 и позицией размещенного раньше элемента r_j;

Tl-1 – множество позиций, занятых элементами после (l-1)-го шага алгоритма.

Процесс размещения алгоритма заканчивается после выполнения n шагов алгоритма.

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

Для размещения разногабаритных элементов наиболее эффективным является последовательно-групповой метод. Модель монтажного пространства представляется непрерывной плоскостью в координатах X,Y. Модель схемы - гиперграфом G(P,V), где P - множество выводов элементов; V - множество электрических цепей. Каждый элемент представляется прямоугольником, с указанием координат выводов элементов.

Для решения задания размещения элементов на плате по существующему файлу связей складывается матрица инциденций, что описывает число электрических соединений между всеми элементами схемы и строится граф всех связей. Дальше определяется минимальная размерность матрицы посадочных мест m x n, где m - число мест по горизонтали n - число мест по вертикали. Эта модель расширяется к размерам (2m-1) x (2n-1).

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

Fi = Уk Уj (ЬjДxijk +вjДyijk) + Si

где: Si – неиспользованная площадь платы, связанная из разногабаритносттью элементов;

Ьj, вj =0, если и элемент не связан с j-тим;