Синтез структуры системы автоматизации

Синтез структуры системы автоматизации

и управления с оптимальным распределением

ресурсов.

Эффективность систем автоматизации и управления (сау) зависит от рационального планирования ресурсов для выполнения заданного множества взаимосвязанных работ исполнителями. Под исполнителями понимается технологическое оборудование, приборы, вычислители, при­воды, аппаратные средства и другие элементы САУ. которые осуществ­ляют контроль параметров, расчеты, управление, технологические опера­ции.

Сложность распределения ресурсов зависит от топологии связей между работами, ограничений на параметры объекта проектирования и альтернативности структуры САУ, Особые трудности возникают в случае информационно-зависимых работ и развитой архитектуры мультипроцес­сорной системы.

В общем постановке задача сводится к определению исполнителей и плана параллельно выполняемых работ [1].

Постановка задачи

Необходимо выполнить некоторое множество работ

где D. S подмножество несвязанных и связанных работ. В подмножестве S задано бинарное отношение

где круглыми скобками () обозначена последовательность элементов (работ); R -отношение информационной (технологической) связи.

Элементы и находятся в отношении R, если результаты (выходная информация) является исходными данными для .

Бинарное отношение R формально представляется матрицей следо­вания Р с элементами

Множество работ А выполняется универсальными исполнителями M1, M2,… MN и дополнительными техническими средствами - это исполнитель способный выполнять часть любой работы из А. Каждый универсальный исполнитель образует подсистему , в которую входит и дополнительные технические средства. Если участвует в решении задачи то

Поставим в соответствие каждому элементу вектор-вес , а элементу si вектор - вес ;

где - время (в условных единицах) выполнения работы с использованием универсального исполнителя .

Для одинаковых исполнителей каждый вектор - вес состоит из одно­го элемента:

=

=

Временные характеристики имеют описание в виде одномерных массивов:

План параллельной работы универсальных исполнителей назначает­ся по критерию [2]:

где - время работы, включая простои, универсального исполнителя .

Определение количества универсальных исполнителей.

Рассмотрим процедуру определения N для САУ с исполнителями одного типа. От бинарного отношения перейдем к графу где S - множество вершин, a W- множество дуг , предшествует Используя матрицу P найдем подмножество начальных работ и подмножество конечных работ , а затем построим граф G. Отметим, что , если j- й столбец матрицы Р нулевой, а если i -ая строка нулевая.

Для всех и найдем множество путей

П={П1, П2, П3 …} от до максимальный путь Пmax=max{П1, П2, П3 …} время прохождения этого пути

Количество исполнителей вычислим по формулам:

Число N является исходным для планирования работы исполните­лей и не гарантирует завершение всех работ за время .

Если это эффективность увеличения N устанавливается по приращению

Последовательное вычисление , и т.д. выявляется опти­мальное количество универсальных исполнителей.

Когда в условие задачи входит ограничение где - максимально допустимое время, и ,в расчетные форму­лы вместо подставляется .

Планирование работ и декомпозиция структуры САУ

Существует несколько подходов к распределению связанных опера­ций, результативность которых существенно зависит от топологии и раз­мерности задачи [1]. Рациональное решение достигается пошаговым пла­нированием по критерию наибольшей трудоемкости и связанности опера­ции, разрешением связей в орграфе G(S,W) путем "удаления вершин и ин­цидентных им дуг, соответствующих завершенным работам в текущий момент времени.

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

Опыт синтеза САУ подтверждает эффективность подхода с назна­чением приоритета операций. В этом случае необходимо выделить два подмножества работ (операций) и

где - объединение всех путей от до конечного элемента из

- количество путей от до

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

Пусть задано ø, а матрица Р такая

Р

При этих исходных данных . Метод распределения с учетом приоритета операций приводит к решению с вре­менем выполнения всех работ Т = 37 при N = 3 и Т - 33 при N = 4.

Использование метода распределения по критерию наибольшей трудоемкости дает решение Т= 42 при N = 3.

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

Результатом планирования операций является декомпозиция

А = DUS' в виде подмножеств :

Эти подмножества характеризуют оптимальную структур САУ.

Литература

1. Вишняков В.А.. Герман О.В, Планирование параллельной работы ин­формационно-связанных задач в неоднородной вычислительной систе­ме // Изв. АН СССР, Техническая кибернетика, 1985. № 3. С.57-61.

2. Поспелов ДА. Введение в теорию вычислительных систем. М.; Сов радио, 1972. 340с.

Дата добавления: 2015-11-04