ПОИСК Статьи Чертежи Таблицы Основы формализации процедур системного проектирования из "Основы теории и проектирования САПР " Формализация процедур синтеза. На системном уровне наиболее распространены следующие два подхода к структурному синтезу сведение задачи синтеза к задаче дискретного математического программирования и ее решение методами сокращенного перебора использование экспертных систем, содержащих знания об известных структурах и элементах систем и способах генерации новых структур. Рассмотрим примеры задач, решаемых в рамках этих подходов. [c.80] Пусть Х= (xi, ЛГ2. ж ), где X,- — число единиц оборудования i-ro типа в проектируемой системе. Выходные параметры у,, составляющие вектор Y среднее время решения задачи в системе, вероятность отказа в решении, производительность, коэффициенты загрузки оборудования, пропускная способность сети передачи данных (СПД) и т. п. Неравенства (4.2) — совокупность условий работоспособности, Yt — вектор заданных технических требований на выходные параметры. Целевая функция F(X) формируется по одному из способов постановки экстремальных задач (см. гл. 3). [c.80] Для снижения вычислительных затрат исходная задача большой размерности разбивается на ряд последовательно решаемых задач приемлемой размерности. [c.81] В экспертных системах знания о структурах ВС и сетей чаще всего представляются в виде И —ИЛИ — графов как разновидностей семантических сетей. [c.81] Пример 4.1. Рассмотрим часть И —ИЛИ —графа, характеризующего обобщенную структуру систем автоматизированного проектирования (рис. 4.1). Корневая вершина типа И отображает САПР. Из нее идут ветви к вершинам, отображающим составные части САПР — виды обеспечения. Это вершины типа ИЛИ, поскольку каждой из них соответствует ряд альтернатив — способов реализации. Альтернативы отображаются вершинами типа И следующего яруса. Здесь показаны только способы реализации технического обеспечения в виде вычислительной сети той или иной конфигурации. На следующем ярусе представлены уровни (составные части) вычислительной сети. Хотя на рис. 4.1 уровни центрального вычислительного комплекса (ЦВК), автоматизированных рабочих мест, рабочих мест (РМ) и сети передачи данных показаны относящимися к радиальной конфигурации, они входят и в сети других конфигураций. Поэтому обобщенная структура рис. 4.1 является не И — ИЛИ — деревом, а И —ИЛИ — графом. Далее изображены ярусы вершин, соответствующих типам и составным частям АРМ, типам реализации СПД. Полная семантическая сеть имеет гораздо больше верщин и связей. [c.81] Разработка семантической сети в виде И —ИЛИ — графа для различных автоматизированных систем не представляет принципиальных трудностей. Сложнее формализовать правила выбора маршрута в И — ИЛИ — графе, оптимальным образом соответствующего конкретному ТЗ. Разработка таких правил (продукций) составляет сущность формализации структурного синтеза на основе выделения структуры из обобщенного И —ИЛИ — графа. [c.81] Системы массового обслуживания. В системах, моделируемых в виде СМО, различают статические и динамические объекты. Статические объекты, называемые обслуживающими аппаратами (АО) или ресурсами, моделируют средства обработки информации, например, ЭВМ, отдельные устройства ЭВМ, аппаратуру передачи данных. Часто к ресурсам относят и программные средства моделируемых ВС. Динамические объекты, называемые заявками или транзактами, моделируют решаемые в ВС задачи. Если с помощью СМО моделируются производственные линии, то технологическое оборудование отображается в виде ОА, а обрабатываемые детали — в виде транзактов. [c.83] Системы массового обслуживания бывают одно- и многоканальными в зависимости от числа ОА, параллельно обрабатывающих входной поток заявок одно- и многофазными в зависимости от числа последовательно включенных ОА. Структуры из ОА, соединенных произвольным образом, называются сетями СМО. [c.83] Функционирование СМО представляется как процесс прохождения заявок через систему. При этом заявка может войти для обслуживания в некоторый ОА. Тогда переменная и, характеризующая состояние заявки, принимает значение обслуживание , а пе-земенная w, характеризующая состояние ОА, —значение занято , сли ОА не занят обслуживанием, то переменная w имеет значение свободен . Если заявка поступает на вход ОА, занятого обслуживанием другой заявки, то образуется очередь на входе ОА. Переменная и, характеризующая состояние заявки, находящейся в очереди, имеет значение ожидание . Следовательно, переменные состояния МИШ принимают одно из двух возможных значений, т, е. являются булевыми переменными. Состояние ОА характеризуется также длиной очереди г на его входе, равной числу заявок в очереди. [c.83] Правило, по которому заявки поступают из очередей на обслуживание в ОА, называется дисциплиной обслуживания. Величина, выражающая преимущественное право на обслуживание, называется приоритетом. [c.83] Любое изменение состояния системы, т. е. изменение переменных w, и или г, называется событием. Принимается допущение, что события совершаются мгновенно. [c.84] С помощью сетей Петри моделируются процессы, представляемые в виде последовательности событий. Принято считать, что события происходят мгновенно и разновременно. Каждому из возможных событий соответствует определенный переход. Событие происходит, если выполнены некоторые условия. Каждому из условий в сети Петри соответствует определенная позиция. Выполнение условий отображается с помощью маркеров, помещаемых в виде точек внутри соответствующих позиций. Число состояний сети Петри определяется числом возможных маркировок. Маркировкой называется распределение маркеров по позициям. Если упорядочить позиции Pi (см. рис. 4.2) по возрастанию индекса I, то маркировку можно представить вектором (О, О, 1,0), -й элемент которого равен числу маркеров в позиции р,-. [c.84] Пример 4,2. Сеть Петри рис. 4.2 моделирует простую вычислительную систему. Переход t 2 соответствует появлению задачи на входе ВС, /ю—началу решения задачи, и — окончанию решения, fiз — выходу решенной задачи из ВС. [c.85] Позиция р1 соответствует условию во входной очереди есть задачи , р2 — решение окончено , рз — процессор свободен , pi — в выходной очереди есть задачи . Начальная маркировка задана в виде маркера в позиции рз. Приход задачи в ВС отображается запуском перехода ц и появлением маркера в позиции р1. Это влечет за собой срабатывание перехода /ю, в результате чего изменяется маркировка удаляются маркеры из позиций р, и рз, помещается маркер в позицию Рг, т. е. имеем маркировку (О, 1, О, 0). Запускается переход ц, появляется новая маркировка (О, О, 1, 1) с маркерами в позициях рз и pi. Срабатывает переход 13, система приходит в состояние, соответствующее исходной маркировке рис. 4.2. [c.85] В общем случае в позиции может быть более одного маркера. Пусть переход связан с входной позицией п дугами, а с выходной — т дугами. Тогда его запуск возможен только при числе маркеров во входной позиции, не меньшем п, и выражается в удалении п маркеров из входной позиции и в добавлении т маркеров в выходную позицию. На рис. 4.3, а представлен фрагмент сети Петри с маркировкой (3, 3, 1). Срабатывание перехода приводит к маркировке (1,2,5) (рис. 4.3, б). [c.85] Разновидности сетей Петри. Для моделирования ВС наибольший интерес представляют временные, стохастические и функциональные сети Петри. [c.85] Временная сеть Петри характеризуется тем, что вводятся задержки при перемещениях маркеров. Задержки можно относить к переходам или позициям, они могут быть детерминированными или случайными величинами. [c.86] Пример 4.3. Стохастическая сеть Петри для моделирования процессов отказов и устранения неисправностей в технической системе показана на рис. 4.5. Исходная маркировка (3, О, 1, 0) соответствует наличию в системе трех рабочих блоков и одного запасного. Переходам соответствуют случайные временные задержки 1 — интервал времени между отказами, t2—время замены, з — время восстановления отказавшего блока. [c.86] Функциональная сеть Петри характеризуется тем, что отражает не только последовательность событий (поток управления), но и процессы обработки некоторого потока данных. Для этого в описание каждого перехода добавляется алгоритм обработки данных. С помощью функциональных сетей Петри можно моделировать разнообразные элементы ВС, производить статистическую обработку результатов моделирования, отображать различные алгоритмы функционирования. [c.86] Вернуться к основной статье