автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.06, диссертация на тему:Многокомпонентная сетевая модель формирования алгоритмов распределенной обработки и управления в АСУ

На правах рукописи

ДЖИОЕВА Наталья Николаевна

МНОГОКОМПОНЕНТНАЯ СЕТЕВАЯ МОДЕЛЬ ФОРМИРОВАНИЯ АЛГОРИТМОВ РАСПРЕДЕЛЕННОЙ ОБРАБОТКИ И УПРАВЛЕНИЯ В АСУ

05.13.06 - Автоматизация и управление технологическими процессами и

производствами

Автореферат

диссертации на соискание ученой степени кандидата техническихнаук

Красноярск 2004

Работа выполнена на кафедре Информационных технологий Красноярской государственной академии цветных металлов и золота

Научный руководитель:

доктор технических наук, профессор

Ковалев Игорь Владимирович

Официальные оппоненты:.

доктор технических наук, Профессор

Петров Михаил Николаев

кандидат технических наук, доцент

Ступина Алена Александровна

Ведущая организация: Научно-исследовательский институт Автоматики' и электромеханики при Томском государственном университете систем управления и радиоэлектроники

Защита состоится «28» июня 2004 года в 14 часов на заседании диссертационного Совета Д212.046.01 в научно-исследовательском институте Систем управления волновых процессов и технологий Министерства образования Российской Федерации по адресу: 660028, Красноярск, ул. Баумана, 20В

С диссертацией можно ознакомиться в библиотеке института

Автореферат разослан «28» мая 2004 года.

Ученый секретарь диссертационного Совета

кандидат технических наук, доцент

Н.А. Смирнов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

Модель системного уровня автоматизированного производства как единого целого должна представлять динамику взаимодействующих информационно-алгоритмических процессов управляющей вычислительной системы (УВС) и логико-время-количественных отношений в материальных потоках производства.

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

Общность методов построения управляющих моделей автоматизированного производства и моделей проектирования распределенных УВС, вы-

3 [ РОС НАЦИОНАЛЬНАЯ I

I библиотека }

I С.Пстер4урГ/НИ ! | оэ

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

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

Поставленная цель определила следующие основные задачи исследований:

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

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

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

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

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

Методы исследования. Системный анализ и методы теории оптимизации. Методы теории вероятностей и теории потоковых графов. Методы детерминированного и стохастического анализа сетей. Теория множеств, комбинаторика и теория графов.

Научная новизна работы.

1. Разработана многокомпонентная сетевая модель с унифицированной GERT-подобной узловой логикой для формального представления и автоматизированного формирования алгоритмов распределенной обработки и управления.

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

3. Показана возможность использования метода критического пути

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

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

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

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

7. Формальный аппарат многокомпонентной сетевой модели формирования алгоритмов распределенной обработки и управления реализован в виде интерактивной системы с использованием современных программно-информационных сред и подходов.

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

Реализация результатов работы. В рамках договора между КГАЦМиЗ и ОАО «Крастяжмашэнерго» при непосредственном участии автора разработан, передан и внедрен в составе комплексной АСУ основным производством интерактивный программный модуль ERP-системы «MBS-Axapta» диалогового формирования алгоритмов распределенной обработки и управления для участка автоматизированного производства корпусных деталей и для многопроцессорной системы автоматизированной диагностики и контроля электронных устройств.

Материалы диссертационной работы введены в учебные курсы и используются при чтении лекций для студентов Красноярской государственной академии цветных металлов и золота и Сибирского государственного технологического университета.

Основные тезисы, выносимые на защиту.

1. Автоматизация решения задач формирования, анализа реализуемости и коррекции алгоритмов распределенной обработки и управления в АСУ обеспечивается формализацией оптимизационных детерминированных

и стохастических постановок на базе многокомпонентной сетевой модели с унифицированной вЕЯТ-подобной узловой логикой.

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

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

4. Предложенный формальный аппарат многокомпонентной сетевой модели формирования алгоритмов распределенной обработки и управления, реализованный в виде программного модуля ЕЯР-системы «МВ8-Ахар1а», применим для автоматизации этапа модельного анализа широкого класса автоматизированных систем управления технологическими процессами и производствами.

Апробация работы. Основные положения и результаты работы прошли всестороннюю апробацию на всероссийских и международных конференциях, научных семинарах и научно-практических конференциях. В том числе, на 7, 8 и 9-й Всероссийских научно-технических конференциях «Перспективные материалы, .технологии, конструкции, экономика» (Красноярск, 2001-2003), на международной научно-технической конференции «Информатика и проблемы телекоммуникаций» (Новосибирск, 2003), на 3-й Всероссийской научно-практической конференции «Модернизация системы профессионального образования на основе регулируемого эволюционирования» (Челябинск, 2003), на 9-й международной открытой научной конференции «Современные проблемы информатизации в технике и технологиях» (Воронеж, 2004). Докладывались на научных семинарах кафедры Информационных технологий КГАЦМиЗ.

Публикации. По теме диссертации опубликовано 12 работ общим объемом 9,4 печатных листа, список приводится в конце автореферата.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы из 88 наименований. Основное содержание изложено на 167 страницах машинописного текста.

СОДЕРЖАНИЕ РАБОТЫ

В первом разделе проведен анализ современных методологий автоматизированного управления распределенными автоматизированными производственными системами и организационно-технологическими процессами. Отмечается, что именно предпринятые сегодня расширения классических методик управления ресурсами предприятия дают толчок для новых витков развития методологий управления производственными системами и технологий системного моделирования. Однако на практике математическая под-

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

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

Каждая из перечисленных задач имеет специфические требования к функциональности алгоритмического и программного обеспечения (ПО). Например, алгоритмизация и управление «распределенными потребностями» автоматизированного производства требует более мощного аналитического1 механизма планирования и организации межскладских перемещений, не связанного непосредственно с планированием производственных потребностей (в том числе, с технологической точки зрения, - поддержки механизма репликации, автономных транзакций и\или глобальных сетей).

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

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

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

С целью более широкого использования математических моделей в

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

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

Во втором разделе рассмотрены алгоритмы, предлагаемые для реализации моделей детерминированного характера. Подразумевается, что вся информация, необходимая для описания характеристик комплекса информационно и по управлению взаимосвязанных распределенных алгоритмов, известна до реализации их в составе автоматизированной системы управления. Целью оптимизационного формирования исполнения последовательно -параллельных алгоритмов распределенного управления и обработки является максимизация/минимизация одного или более оценочных критериев.-

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

Формирование алгоритма распределенной обработки и управления подразумевает, что задания или алгоритмические операции (сегменты кода,. если использовать терминологию УВС в АСУ) должны быть назначены конкретному процессору для исполнения в конкретное время. Так как для выполнения может рассматриваться много заданий или операций алгоритма (задания и задачи, в данном контексте, взаимозаменяемые термины), необходимо представить набор этих задач в виде их взаимосвязи друг с другом. Реализованное в рамках многокомпонентной модели представление наборов заданий с использованием ориентированного графа или графа предшествования является наиболее популярным в литературе по планированию. Модифицированные GERT-узлы в этом графе могут представлять независимые операции или части одной программы (ярограммного модуля), которые связаны между собой во времени.

В работе предлагается модифицировать процедуру анализа и коррекции временных параметров распределенного алгоритма с корневой структурой (на базе вектора временной развертки и вектора реализации, опреде-

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

Отметим, что в общем случае неединичные операции (например, с весами больше единицы) представляются в виде потока операций с единичным весом, чья сумма равна весу изначальной операции. Такое представление позволяет определять оптимальное неприоритетное решение, используя алгоритм Хью, так как граф является деревом, а использование алгоритма наидлиннейшего пути Кауфмана (или G-алгоритма) не позволяет прерывать процессор до завершения этой составной операции, которая является членом • потока операций, представляющего алгоритмическую задачу неединичного веса.

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

1) определение минимума времени, необходимого для обработки графа задач алгоритма при фиксированном числе процессоров;

2) определение количества процессоров, необходимых для обработки графа алгоритма за заданное время.

Первым шагом в решении этой задачи является разметка узлов произвольного графа. Узлу N присваивается метка а, = X, + 1, где- А) - длина, наидлиннейшего пути от N до конечной вершины в графе. Разметка начинается с конечной вершины, которой присваивается метка а/ = 1. Узлы, на единицу отдаленные от конечного, получают метку 2 и т. д. Смысл этой схемы меток в том, что минимальное время Тт1п, необходимое для обработки графа, связано с я(тах) узлами с наивысшими индексами через соотношение

Тш1п>а(тах).

Оптимальные решения рассмотрены для корневых деревьев. Используя процедуру разметки, изложенную выше, можно получить оптимальный план для т процессоров, организуя дерево задач единичной длины в соответствии с алгоритмом генерации 2-В.

1. Включаем в план первые т начальных узлов с наивысшими индексами меток. Термин «начальный узел» применяется к узлу без предшественников. Если количество таких узлов больше т, то выбрать т узлов с наибольшими значениями а,. В случае нескольких одинаковых величин выбор производится случайным образом.

2. Удаляем т обслуженных узлов из графа.

3. Повторяем шаги 1 и 2 для оставшегося графа.

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

0123 4 56 78

(Ь)

Рис. 1. Оптимизационный алгоритм генерации 2-В: а - корневое дерево, размеченное в соответствии с процедурой Хью; Ь - оптимальный план для трех процессоров

Как было показано выше, минимальное время обработки графа, размеченного в соответствии с процедурой Хью, равно а(тах). Предположим, требуется обработать граф за предписанное время где г = д(тах) + С и С -положительное целое число.

Минимальное число т процессоров, необходимое для обработки графа за время /, вычисляется как

т -1 < [1 /(/ + С)] 1р(атм +1 -Л<т,

где р(() обозначает количество узлов в графе с меткой а„ а у* - величина константы у. которая максимизирует данное выражение.

В работе предлагается использовать процедуру Хью как основу детерминированной модели формирования: алгоритмов распределенной обработки и управления в общем случае временного анализа и коррекции (разд. 2.1.)» когда алгоритм представлен последовательно-параллельным набором единичных задач. При этом ранее в рамках процедуры анализа и коррекции ограничения на ресурсы = процессора не рассматривались. Считалось, что задачи алгоритма выполняются в срок, независимо от наличия/отсутствия • процессорного времени. Данное ограничение, однако, является алгоритмически проверяемым, т.е. процедура Хью позволяет установить взаимооднозначное соответствие между возможной длительностью реализации алгоритма и составом мультипроцессорной среды.

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

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

Итак, в работе дополнительно предполагается наличие множества ресурсов R={Ri,...,Rs}- Если задаче .Т| необходим ресурс то это требование принимается во внимание в течение всего периода выполнения задачи. Потребность задачи в ресурсе обозначается через , Пусть r/t)

обозначает общее количество ресурсов Л/, которое используется в момент времени /..Тогда r,{t) = Sumдля всех Tj, выполняемых в момент времени t и /}(/) S1. Для данной постановки в работе определено, в какой степени использование различных списков задач алгоритма влияет на время завершения w.

Предположим, что для двух произвольных списков L и L' (времена завершения списков соответственно w и w") расширенная система из п процессоров выполняет набор из г задач с результирующими временами завершения w и w' соответственно. Для такой среды исполнения алгоритмов предложен ряд решений, которые дали следующие результаты:

при/?=/Лд/ (в системе существует только один вид ресурсов, отличных от процессора) - и»/и?<п ]

• при и независимости всех задач - <Ъ-\1п\

• при Я=(Яь Я:,..., Яб}, независимости задач и»>г - и>/и/££ + 1.

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

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

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

Пусть Е-, — максимальное время выполнения одной итерации задачи /„а/¡- частота выполнения. Таким образом, каждой задаче/, соответствуют два параметра Е), I ¿¡<п , где п - количество включаемых в план задач. Период повторения равен Т|, величине, обратной /¡. Рассматривается класс задач, для которого верно следующее: если /; задач с /( по /„ распределены так, что1_/,' >//*!„ то предполагается, что / = 2/ц./ , либо допускаются задачи с любой частотой.

Рассматривая ограничения на время реакции системы управления, проанализированы периодичные задачи первого класса (с бинарным частотным распределением). Множество задач, удовлетворяющих бинарному частотному распределению, приведено в табл. 1.

Таблица - Характеристики для множества задач с бинарным частотным распределением

Задача Частота Период Время выполнения

J, У, 4 1

Л 1/8 8 2

А 1/16 16 1'Л

Л 1/32 32 5

Л 1/64 64 3

На рис.2, а, показаны задачи 1/и спланированные на разных процессорах, а на рис. 2, Ь показан план, уменьшающий количество процессоров с двух до одного. Проблемой является определение минимального количества процессоров без перебора всех возможных альтернатив. Заметим, что слияние двух задач, приведенное на рис. 2, Ь, создает новую периодичную задачу с периодом // (равным 2Т|) и временем выполнения е/ (равным Т| • + • £У). Кроме того, имеются два псомежугка с простоями: // периодичный простой с длительностью и принудительное время простоя длинной //-

Ег (обозначение А^ указывает, что принудительное время простоя получается, когда ^ объединяется с ' В процессе объединения остальных задач плана нет необходимости в рассмотрении размещения задач в интервале принудительного простоя. Вместо этого для такой среды план с минимальным числом процессоров формируется в соответствии со следующим алгоритмом:

1) Пусть J¡*, - подмножества задач, назначаемых процессорам Ри Рл,.... Сначала У/*=./?*=... а //=/7=...= . Всякий раз, когда задача ^ назначается в некоторое пустое подмножество УД 11 = Т}-Е}.

2) Чтобы назначить очередную задачу У, необходимо найти наименьшее / такое, чтобы выполнялось условие , и назначить в подмножество

Л*.

Оптимальный план для набора задач из табл. 1 показан на рис. 3. Этот результат обобщен для случая, когда = к - положительное це-

лое число больше 1.

(Ь)

Рис. 2. Планирование периодичных задач с бинарным частотным распределением: а - временная диаграмма для первых двух задач из табл. 1; Ь — ослабление ограничений на число процессоров путем слияния задач

ттт|птп тп 1п 5 им птл отпт ил ош (¡ши июни

1

Т-

-1-1-1-1-1-1-1-1-1-1-1-1

О 4 8 12 16 20 24 28 32 36 40 44 48 52 56 Рис. 3. Оптимальный план для задач из табл. I.

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

1. В порядке уменьшения частоты.

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

2. В порядке уменьшения критерия загрузки.

Критерий загрузки задачи Jht обозначаемый Ъ.„ определяется следующим образом: L, = Е/Т,.

3. Сохранение минимальной длины критического интервала.

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

При тестировании данных методов, задачи разделялись на два класса. В 1 -м классе частоты задач кратны более чем двум базовым частотам, а во 2-м - не более чем двум базовым частотам. Ни один из алгоритмов не показал значительного превосходства над другими.. Однако подход 2 исключительно хорошо показал себя на задачах первого класса. Подход 3 лучше решает некоторые задачи второго класса, а оба подхода 1 и 2 неплохо решают задачи, которые оказались трудными для подхода 3. В этом нет ничего необычного, так как число процессоров, необходимых для задач второго класса, было значительно меньше, чем для задач первого класса.

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

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

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

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

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

Очевидно, что для детерминированного случая можно рассматривать

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

Пусть N— ациклическая сетевая модель алгоритма распределенной обработки и управления с источниками и стоками (действия, соответствующие задачам управления, представляются дугами), где множество узлов обозначается V а множество дуг — Е. Сеть имееттолько один исток, который обозначается через г и соответствует началу рассматриваемой циклограммы. управления. Предполагается, что один из стоков N представляет собой успешное завершение алгоритма и обозначается 8. Оставшиеся стоки, если они есть, могут представлять собой различные виды неудачного завершения или прерывания процесса реализации.

Ациклическую сетевую модель только с одним истоком и со стоками назовем формирующей сетью распределенного алгоритма, если каждый узел / из N определен через входную характеристику СН{ е {0,1,...,|Р(1) |} и выходную характеристику CH*I е {0,1,.,.,^0) |}.Эти характеристики, формирующие узловую логику, имеют следующие значения: (а) узел активируется сразу же, как только входные действия СН~1 завершаются; (б) как только узел 1 активирован, то не более СА/4,- выходных действий начинает выполняться. Если узел 1 не активируется, то ни одно выходное действие не выполняется. Для источника г полагаем СН~Г = 0, т.е. он всегда активирован. Кроме того, СН*1 = 0 для / е 5, где 5 — множество стоков. Заметим, что если СН~Г = 1, то узел / имеет ЮЯ-вход, а если СНГ = \Р(г) |, то тогда / имеет АМБ-вход. И если "не более" заменяется на "точно" в условии (б), то С//*, = 1 соответствует вероятностному выходу, а соответствует детерминированному

выходу. Если же заданная сеть ]Ыдля формирования алгоритма имеет множество источников Л (|Л |> I) и множесА щз/й й'Мйв изируется в начале выполнения процесса реализации алгоритма, то можно формально перевести сеть N в соответствующую одно-истоковую.

Обозначим дуговые переменные через IV,у .положив = I ,еапп(У) выполняется (( ¡, }) е Е), и = 0 — в противном случае. Узловые переменные иу =1 еУ), если / активируется. Иначе — = 0, причем иг= 1, т.е. источник всегда активируется. Тогда условия базовой вЕКТ-подобной узловой логики ((а) и (б)) представляются в следующем виде:

Каждая реализация алгоритма распределенной обработки и управления (или реализация сетевой модели) может быть соотнесена с множеством выполняемых задач алгоритма (выполняемых действий сети) или с функцией w: Е —> {0,1};((/, j) € £), значения которой задаются как w((i, у)) =: Wy=l,

если (i,j) выполняется, и - 0, иначе.

Очевидно, что если некоторая w-я реализация алгоритма задана, то как узловые, так и дуговые переменные для этого случая специфицированы и можно говорить о допустимой реализации алгоритма, если w _удовлетворяет условиям GERT-подобной узловой логики. Тогда е = {w : Е —> {0, 1}| Щ-удовлетворяет (1)-(3); (/,_/) е Е }, и е — множество всех допустимых реализаций алгоритма.

Если в GERT-сети для формирования алгоритмов, обозначить вес дуги (i, j) е Е как длительность dy соответствующей задачи, то dw — длительность W-Й реализации алгоритма, т.е. время, требуемое для исполнения всех задач (i, j) при Wy = I. Каждая операция алгоритма начинается в наиболее ранний t', возможный при данной vv-й реализации рассматриваемого алгоритма, срок). В этом случае необходимо минимизировать dw при условиях: w активирует s; (w е е). Через е* :={ w е £ | w активирует s} обозначим: множество успешных реализаций алгоритма.

Для е* * О d* = min dw (4)

соответствует минимальному значению целевой функции задачи.

Рассматривая моменты как компоненты вектора временной развертки (ВВР) алгоритма, которые удовлетворяют (/,-/,- dy) wt>0, (/,_/) б£; ä 0, i eV\{r}; tr= 0, можно утверждать, что для некоторой vv-й реализации (w еБ*)> tjW отвечают этим ограничениям, а самые ранние t' удовлетворяют им для соответствующей минимальной we £*. Соответствующая оптимизационная задача при выполнении ограничений ВВР имеет вид: Минимизировать шах {(t,w+dy) w¡j}.

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

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

времени, с помощью которой для него строятся доверительные интервалы.

В заключение данного раздела отмечается, что для решения моделей GERT-анализа необходимы сложные и трудоемкие вычисления, организация которых требует использования специально разработанных программных комплексов GERT-процедур в рамках интерактивной системы модельного анализа и формирования алгоритмов распределенной обработки и управления в автоматизированных системах. Росту функциональных возможностей системы GERT способствует применение моделей. в несколько сотен или более дуг (или узлов). Однако при использовании топологического уравнения Мейсона канонического вида с увеличением размерности сети экспоненциально возрастает число петель r-х порядков, г=1,...,п. Для определения плотности распределения вероятностей GERT-сети используется модификация численного метода нахождения закона распределения выходной величины GERT-сети, для которой трудоемкость решения задачи характеризуется полиномом второй степени относительно числа дуг GERT-сети.

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

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

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

понентной модели в используемой инструментальной среде. В качестве которой выбрана современная ЕЯР-система «МВ8-Ахар1а».

Система программно-алгоритмической поддержки многокомпонентной модели формирования алгоритмов распределенной обработки и управления реализована в виде модуля «Многокомпонентная модель» ЕЯР-системы МВ8-Ахар1а. Логика системы написана на языке Х++ в виде иерархии классов и интегрирована в логику системы МВ8-Ахар1а. Конечные и промежуточные результаты сохраняются в базе данных для возможности их дальнейшей обработки и анализа.

В модуле «Многокомпонентная модель» реализованы. следующие модели, отражающие базовую концепцию структуризации и формализации графо-аналитических и аналитико-оптимизационных процедур, представленных в диссертации:

• модельный> компонент детерминированного формирования алгоритмов распределенной обработки и управления; , ,

• модельный компонент анализа стохастической структуры алгоритмов распределенной обработки и управления;

• • модельный компонент анализа и тестирования ПО реализации алгоритмов распределенной обработки и управления.

Базовую структуру моделей составляет графо-аналитическая (или структурно-стохастическая) сетевая модель с ОЕЯТ-подобной узловой логикой.-

Система программно-алгоритмической поддержки. многокомпонентной модели состоит из четырех классов моделей формирования АлгРОиУ, иеархия которых поедставлена на РИС. 4._

ВМос1е1

абстрактный класс моделей формирования АлгРОиУ

ВМоаеЦУГ класс реализации модели детерминированного формирования алгоритмов распределенной обработки и управления

ВМоае1_5Т класс реализации модели анализа стохастической структуры алгоритмов обработки и управления

ВМос)с1_АТ класс реализации модели анализа и тестирования ПО реализации алгоритмов обработки и управления

Рис. 4. Иерархия классов многокомпонентной модели

БМоёе1 является абстрактным классом моделей многокомпонентной структуры. БМоёе1_БТ, БМоёе1_8Т, БМоёе1_ЛТ - классы модели, реализующие процедуры формирования алгоритмов распределенной обработки и управления. Следует заметить, что для данных классов элементы моделей и алгоритмы их взаимодействия в рамках концепции формализации могут быть достаточно разнообразны. Предыдущие главы диссертации служат этому достаточной иллюстрацией. Пример содержания методов класса БМоёе1, БМоёе1_БТ и БМоёе1_8Т, реализованных в ЕЯР-модуле М8Б-Лхар1а, представлен в диссертации.

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

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

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

Представленная в четвертом разделе структура программы анализа и тестирования (Модуль «ПАТ», являющийся компонентом ЕЯР-модуля), реализует описанный в главе 3 подход к исследованию ПО исполнения алгоритмов распределенной обработки и управления. Исполнение модуля «ПАТ» является наиболее трудоемким этапом с точки зрения технологии системного моделирования.

Согласно требованиям МБ8-Лхар1а, программа построена в объектно-ориентированном стиле и реализует элементы модели в виде объектов. Каждой позиции модели сопоставлен объект - позиция, который имеет список объектов-переходов, которые связаны с ним в модели. Аналогично реализуются переходы, присутствующие в модели.

Функционирование программы при моделировании происходит следующим образом. Все объекты-переходы могут иметь три состояния: пассив-

ное, готовность к запуску, активное. Состояние эквивалентно числу меток в них» При изменении разметки объекта-позиции, он посылает сообщения всем объектам-переходам, для которых эта позиция является входной. Когда объект-переход получил сообщения от всех входных позиций о наличии необходимого количества меток в них, он переходит из пассивного состояния (если он в нем находился) в состояние готовности к запуску и посылает сообщение об этом диспетчеру выполнения сети. Диспетчер заносит ссылку на объект в список готовых к запуску переходов. Если изменение разметки позиций нарушило условия запуска перехода, то происходит обратный процесс и ссылка на объект-переход удаляется из списка готовых к запуску переходов.

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

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

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

• обращение к процедуре ведения протокола анализа и тестирования;

• посылка сообщений всем входным объектам-позициям, соответствующим схеме перехода, о необходимости удаления меток.

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

• обращение к диалоговым средствам;

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

Фактически, модель состоит из связанных моделей распределенных алгоритмов АСУ и модели ПО реализации этих алгоритмов.

Модуль ERP-системы многокомпонентной сетевой модели формирования алгоритмов распределенной обработки и управления использовался для моделирования процессов на участке автоматизированного производства и обработки корпусных деталей, а также при исследовании многопроцессорной системы автоматизированной диагностики и контроля электронных устройств, решение которой было реализовано в рамках ERP-системы Microsoft Business Solutions-Axapta.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

1. Разработана многокомпонентная сетевая модель с унифицированной ОЕЯТ-подобной узловой логикой для формального представления и автоматизированного формирования алгоритмов распределенной обработки и управления.

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

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

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

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

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

в) доказано существование допустимой реализации распределенного алгоритма, если сетевая модель формирования алгоритма ациклична и ее параметры удовлетворяют условиям ОЕЯТ-подобной узловой логики.

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

6. Формальный аппарат многокомпонентной сетевой модели формирования алгоритмов распределенной обработки и управления реализован в виде интерактивной системы с использованием современных программно-информационных сред и подходов.

7. Выполнена разработка структуры системы программно-алгоритмической поддержки многокомпонентной модели с учетом

собенностей компонент, включаемых в программную систему, и предложен1 метод реализации системы программно-алгоритмической поддержки путем интеграции в ERP-систему Microsoft Business Solutions - Axapta.

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

Результаты выполнения реальных проектов подтвердили эффективность и универсальность разработанной системы программно-алгоритмической поддержки многокомпонентной сетевой модели формирования алгоритмов распределенной обработки и управления в АСУ.

Основные положения и результаты диссертации опубликованы в следующих работах:

1. Джиоева, Н.Н. Алгоритмизация задач распределенной обработки информации и управления в интегрированных производственных структурах/ Н.Н. Джиоева; Вестник НИИ СУВПТ «Адаптивные системы моделирования и управления», Часть II. - Красноярск: НИИ СУВПТ, 2000. - С. 133-140.

2. Джиоева, Н.Н. Информационные технологии в экономическом образовании/ Н.Н. Джиоева, Г.И. Васина// Перспективные материалы, технологии, конструкции, экономика: Сб. научн. тр. по материалам Всероссийской научно-технической конференции. Вып. 7. - Красноярск: ГАЦМиЗ, 2001.-С. 124-126.

3. Джиоева, Н.Н. Высокоуровневые: методы информатики и программирования: Учеб. пособие/ Н.Н. Джиоева. Красноярск: ГАЦМиЗ, 2002. 94 с.

4. Джиоева, Н.Н. Управление качеством на основе новых информационных технологий/ Н.Н. Джиоева, Л.Н. Корпачева, С.Н. Ежеманская// Перспективные материалы, технологии, конструкции, экономика: Сб. научн. тр. по материалам Всероссийской научно-технической конференции. Вып. 8. -Красноярск: ГАЦМиЗ, 2002.- С. 58-61.

5. Джиоева, Н.Н. Современное состояние методологий автоматизированного управления производством/ Н.Н. Джиоева// Вестник НИИ СУВПТ.- Вып. 12.- Красноярск: НИИ СУВПТ, 2003. - С. 101-112.

6. Джиоева, Н.Н. Стохастическое представление моделей реализуемости алгоритмов обработки и управления/ Н.Н. Джиоева, Е.Н. Антамошки-на// Вестник НИИ СУВПТ.- Вып. 12.- Красноярск: НИИ СУВПТ, 2003. - С.' 216-222.

7. Джиоева, Н.Н. Использование детерминированных моделей для анализа алгоритмов обработки и управления производством/ Н.Н. Джиоева, И.В. Ковалев// Перспективные материалы, технологии, конструкции, экономика: Сб научн. тр. по материалам Всероссийской научно-технической конференции. Вып. 9, часть 2. - Красноярск: ГАЦМиЗ, 2003.- С. 154-156.

04"14554

8. Джиоева, Н.Н. Периодичные задачи при формировании алгоритмов распределенной обработки и управления/ Н.Н. Джиоева; Вестник НИИ СУВПТ.- Вып. 13.- Красноярск: НИИ СУВПТ, 2003. - С. 143-147.

9. Ковалев, И.В. Управление развитием кластерной инфраструктуры корпорации/ И.В. Ковалев, Н.Н. Джиоева, СВ. Савин// Информатика и проблемы телекоммуникаций: Сб. научн. трудов по материалам международной НТК, Новосибирск: СибГУТИ, Том 2, 2003.- С. 23-27.

10. Джиоева Н.Н., Ковалев И.В. «Анализ периодичных задач при формировании алгоритмов распределенной обработки и управления» Электронный журнал "Исследовано в России", 197, стр. 2349-2354, 2003 г.

http://zhumal.ape.relarn.ru/articles/2003/197.pdf

И. Джиоева, Н.Н. Многокомпонентная модельная среда информационно-алгоритмического взаимодействия/ Н. Н. Джиоева// Материалы 3-й Всероссийской научно-практической конференции «Модернизация системы профессионального образования на основе регулируемого эволюционирования»: В 4 ч. Ч.З/ Южно-Уральск.гос. ун-т; Ин-т доп. проф. образ, пед. раб.; Отв. ред. Д.Ф.Ильясов.- Челябинск: Изд-во «Образование», 2003.- С. 99-101.

12. Джиоева, Н.Н. Анализ вариантов развития информационных технологий в организационных системах/ Н.Н. Джиоева, СВ. Савин, М.Ю. Сло-бодин// Современные проблемы информатизации в технике и технологиях: Сб. трудов. Вып. 9/ Под ред. д.т.н., проф. О.Я. Кравца - Воронеж: Изд-во «Научная книга», 2004.- С 223-224.

Формат 60x84/16. Объем 1 п.л. Подписано в печать 21.05.04 Отпечатано на ризографе НИИ СУВПТ Красноярск, ул. Баумана, 20В Заказ № 131. Тираж 100 экз.

Введение

1. Автоматизация методологий моделирования управления производством и их математическая поддержка

1.1. Современные методологии: их математическая и вычислительная сложность

1.2. Системный анализ задач распределенной обработки и автоматизированного управления производством

1.3. Распределенное управление и состояние проблемы программирования АСУ

Выводы по разделу

2. Модельные компоненты детерминированного формирования алгоритмов распределенной обработки и управления

2.1. Модельные средства детерминированного формирования распределенных алгоритмов

2.2. Временной анализ и коррекция исполнения распределенных алгоритмов 77 Выводы по разделу

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

3.1. Стохастическое представление моделей формирования

3.2. Стохастическая модель определения нормативных времен распределенной обработки и управления в условиях неопределенности

3.3. Сетевые модели анализа и тестирования ПО алгоритмов распределенной обработки и управления 122 Выводы по разделу

4. Система программной поддержки многокомпонентной сетевой модели

4.1. Средства автоматизированного системотехнического проектирования распределенных УВС

4.2. Структура системы и средства информационной поддержки компонент 155 Выводы по разделу

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

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

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

Модель системного уровня автоматизированного производства как единого целого должна представлять динамику взаимодействующих информационно-алгоритмических процессов управляющей вычислительной системы (УВС) и логико-время-количественных отношений в материальных потоках производства.

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

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

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

Реализация результатов работы. В рамках договора между КГАЦМиЗ и ОАО «Крастяжмашэнерго» при непосредственном участии автора разработан, передан и внедрен в составе комплексной АСУ основным производством интерактивный программный модуль ERP-системы «MBS-Axapta» диалогового формирования алгоритмов распределенной обработки и управления для участка автоматизированного производства корпусных деталей и для многопроцессорной системы автоматизированной диагностики и контроля электронных устройств.

Выводы по разделу, А.

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

2.~ Разработанный модельный компонент анализа ПО реализации алгоритмов распределенной обработки и управления учитывает различные моменты, зависящие от параметров компоновки ПО УВС конкретной производственной или технологической системы, включая приоритет процессов, характеристики УВС и т.д.

Заключение

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

1. Разработана многокомпонентная сетевая модель с унифицированной GERT-подобной узловой логикой для формального представления и автоматизированного формирования алгоритмов распределенной обработки и управления.

2. Выполнен анализ задач модельного: исследования алгоритмов распределенной обработки и управления, задач их реализуемости и коррекции На базе детерминированных и стохастических компонент модели.

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

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

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

6. Формальный аппарат многокомпонентной сетевой модели формирования алгоритмов распределенной обработки и управления реализован в виде интерактивной системы с использованием современных программно-информационных сред и подходов.

7. Выполнена разработка структуры системы программно-алгоритмической поддержки многокомпонентной модели с учетом собенностей компонент, включаемых в программную систему, и предло'жен метод реализации системы программно-алгоритмической поддержки путем интеграции в ERP-систему Microsoft Business Solutions - Axapta.

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

Результаты выполнения реальных проектов подтвердили эффективность и универсальность разработанной системы программно-алгоритмической поддержки многокомпонентной сетевой модели формирования алгоритмов распределенной обработки и управления в АСУ.

1. Абдулаев, Д.А. Моделирование локальных вычислительных сетей с учетом вероятностно-временных характеристик/ Д.А. Абдулаев, У.Б. Амирсаидов// Автоматика и вычислительная техника. 1994. № 3. С. 151160.

2. Аврамчук, Е.Ф. Технология системного моделирования/ Е.Ф. Аврамчук, А.А. Вавилов, С.В. Емельянов и др.; Под общ. ред. С.В. Емельянова.- М.: Машиностроение; Берлин: Техник, 1988.- 520 с.

3. Алимханов, A.M. Обзор современных методологий автоматизированного управления производством/ A.M. Алимханов, Н.Н. Джиоева, С.В. Савин// Вестник НИИ СУВПТ.- Вып. 12.- Красноярск: НИИ СУВПТ, 2003. С. 111-120.

4. Антамошкин, А.Н. Оптимизация функционалов с булевыми переменными/ А.Н.Антамошкин. Томск: Изд-во Том. ун-та, 1987. 104 с.

5. Антамошкин, А.Н. Регулярная оптимизация псевдобулевых функций/ А.Н. Антамошкин// Красноярск: Изд-во КГУ, 1989. 160 с.

6. Боэм Б., Браун Дж., Каспар X., Липов М., Мак-Леод Г., Мерит М. Характеристики качества программного обеспечения.// М.: Мир, 1981, 208с.

7. Боэм Б.У. Инженерное проектирование программного обеспечения: Пер. с англ.- М.: Радио и связь. 1985.- 512 с.

8. Вальков В.М., Никаноров Р.А. Вопросы стандартизации математического обеспечения АСУ ТП//Электронная промышленность.-1985.- Вып. 12.- С. 27-29.

9. Веревкин, С.В. Разработка алгоритмов технологической координации сталеплавильного цеха/ http://www/synerg.nkz.ru/pub/articles/75.htm

10. Внедрение и управление проектами, www.pmforum.org, и choice.da.ru.

11. Воеводин В.В. Математические модели и методы в параллельных процессах.- М.: Наука, 1986,328 с.

12. Волик Б.Г. и др. Методы анализа и синтеза структур управляющих систем/// Под ред. Б.Г.Волика.- М.: Энергоатомиздат, 1988.- 296 с.

13. Гласс Р. Руководство по надежному программированию.- М.: Финансы и статистика, 1982.

14. Губанов, В.А. Введение в системный анализ/ В.А. Губанов// Под ред. JI. А. Петросяна.- Л.: ЛГУ, 1988,232 с.

15. Гудман, С. Введение в разработку и анализ алгоритмов/ С. Гудман, С. Хидетниеми // Пер. с англ. М.: Мир, 1981. 366 с.

16. Джиоева, Н.Н. Высокоуровневые методы информатики и программирования: Учеб. пособие/ Н.Н. Джиоева. Красноярск: ГАЦМиЗ, 2002. 94 с.

17. Джиоева, Н.Н. Стохастическое представление моделей реализуемости алгоритмов обработки и управления/ Н.Н. Джиоева, Е.Н. Антамошкина//

18. Вестник НИИ СУВПТ.- Вып. 12.- Красноярск: НИИ СУВПТ, 2003. С. 216-222.

19. Джиоева, Н:Н. Периодичные задачи при формировании алгоритмов распределенной; обработки; и; управления/ Н.Н; Джиоева; Вестник НИИ СУВПТ.- Вып. 13.- Красноярск: НИИ СУВПТ, 2003: С. 143-147.

20. Дилон Б., Сингх И; Инженерные методы обеспечения надежности систем.- М.: Мир, 1984.- 318 с.

21. Евстигнеев, В.А. Применение теории графов в программировании/ В.А. Евстигнеев/ Под ред. А.П. Ершова. М.: Наука. 1985.- 352 с.

22. Задорожный В., Малиновская И. Надежная система из ненадежных элементов. «Открытые системы». 2000, № 12.

23. Зиндер, Е.З. Проектирование баз данных: новые требования, новые подходы. СУБД, № 3,1996.- С. 10-22.

24. Зыков А.С. Роль информационных технологий на предприятии/ А.С'. Зыков// Современные проблемы информатизации в технике и технологиях: Сб. трудов. Вып. 9/ Под ред. д.т.н., проф. О.Я. Кравца -Воронеж: Изд-во «Научная книга», 2004.- С. 228-229.

25. Калянов, Г.Н. CASE-технологии: консалтинг в автоматизации бизнес-процессов/Г.Н. Калянов// М.: Горячая линия-Телеком, 2000.

26. Калянов Г.Н. Современные CASE-технологии/Т.Н. Калянов// М.: ИПУ, 2000.

27. Козленко, JI. Проектирование информационных систем/ JI. Козленко// М.: КомпьютерПресс, № 9-11, 2001.

28. Ковалев, И.В. Моделирование и оптимизация параллельных процессов в информационно-управляющих системах/ И.В. Ковалев, Р.Ю. Царев. Красноярск: ИПЦ КГТУ, 2003. 111 с.

29. Ковалев, И.В. Автоматизация создания программных средств систем управления/ И.В. Ковалев// В кн.: Микроэлектронные устройства: проектирование и технология.- Красноярск. КПИ, 1990, С.79-85.

30. Ковалев, И.В. Управление развитием: кластерной инфраструктуры корпорации/ И.В. Ковалев, Н.Н. Джиоева, С.В. Савин// Информатика и проблемы телекоммуникаций: Сб. научн. трудов по материалам международной НТК, Новосибирск: СибГУТИ, Том 2, 2003.- С. 23-27.

31. Ковалев И.В., Юнусов Р.В. Оценка надежности аппаратно-программного информационно-управляющего комплекса. САКС-2002: Тез. докл. Междунар. науч.-практ. конф. (6-7 дек. 2002, г. Красноярск)/ СибГАУ. Красноярск, 2002. С. 352-353.

32. Колесников, С. Из истории автоматизации методологий управления предприятием/ С. Колесников// Открытые системы, № 4, 1999. С. 44-56. http://www.osp.ru/os/1999/04/09.htm

33. Коржов В. Адекватные системы. «Открытые системы». 2001, № 12.

34. Корячко, В.П. Численный метод нахождения закона распределения выходной величины GERT-сети/ В.П. Корячко, А.П. Шибанов// Информационные технологии, № 7, 2001. С. 16-21.

35. Лебедев, В. А. Параллельные процессы обработки информации в управляющих системах/ В.А. Лебедев, Н.Н; Трохов, Р.Ю. Царев// Красноярск, НИИ СУВПТ, 2001 г. 142 с.

36. Липаев, В.В. Проектирование математического обеспечения АСУ/ В.В. Липаев// М.: Советское радио, 1977, 400 с.

37. Липаев, В.В. Технология проектирования комплексов программ АСУ/ В.В. Липаев, Л.А. Серебровский// М.: Радио и связь, 1983, 264 с.

38. Максимей, И.В. Имитационное моделирование на ЭВМ/ И.В. Максимей.- М.: Радио и связь, 1988.- 232 с.

39. Мамиконов, А.Г. Проектирование АСУ/А.Г. Мамиконов// М.: Высш. шк., 1987,304 с.

40. Олифер, В.Г. Сетевые операционные системы/ В.Г. Олифер, Н.А. Олифер// СПб.: Питер, 2001.- 544 с.

41. Орлов, С.А. Технологии разработки программного обеспечения/ С.А. Орлов// СПб.: Питер, 2002.

42. Основы автоматизации машиностроительного производства/ Е.Р. Ковальчук, М.Г. Косов, В.Г. Митрофанов и др.;Под ред. Ю.М. Соломенцева.- М.: Высш. шк., 1999.

43. Петров В.Н. Информационные системы/ В.Н. Петров// СПб.: Питер, 2003.- 688 с.

44. Раинкшкс К., Ушаков И.А. Оценка надежности систем с использованием графов.// М.: Радио и связь. 1988.

45. Руководство по методологии ABC. М.: Метатехнология, 1997.

46. Сапегин, А. Информационные технологии и средства анализа и проектирования корпоративных информационных систем/ А. Сапегин// 1999. http://www.citforum.ru/seminars/cis99/sap.shtml

47. Системный анализ: Проектирование, оптимизация и приложения. В 2 т., под общ. Ред. Антамошкина А.Н.// Красноярск, САА, 1996, 206 с.

48. Слепцов А.И. Автоматизация проектирования управляющих систем/ А.И. Слепцов, А.А. Юрасов.- Киев: Техника, 1986.

49. Соммервилл И. Инженерия программного обеспечения.- М.: «Вильяме», 2002, 624 с.

50. Тихонов А.Н., Цветков В.Я. Методы и системы поддержки принятия решений. М.: МАКС Пресс, 2001.

51. Толковый словарь по вычислительным системам/ Под ред. В. Иллигуорта и др.: Пер с англ.- М.: Машиностроение, 1991.- 560 с.

52. Фокс, Дж. Программное обеспечение и его разработка: Пер. с англ./ Под ред. Д.Б.Подшивалова.- М.: Мир, 1985,268 с.

53. Феллер, В. Введение в теорию вероятностей и ее приложения/ В. Феллер: Пер. с англ. В 2-х томах. Т. 2. М.: Мир. 1984- 738 с.

54. Филлипс, Д. Методы анализа сетей/ Д. Филлипс, А. Гарсиа-Диас// М.: Мир, 1984.-496 с.

55. Хетагуров Я.А., Древе Ю.Г. Проектирование информационно-вычислительных комплексов.- М.: Высш. шк., 1987,280 с.

56. Хорошевский В.Г. Инженерный анализ функционирования вычислительных машин и систем.- М.: Радио и связь, 1987, 256 с.

57. Чжу У.У., Лян Ц.К. Копирование и размещение программных модулей в системе распределенной обработки в реальном времени// ТИИЭР, 1987, Т. 75, N 5, С. 23-44.

58. Шибанов, А.П. Нахождение закона распределения выходной величины GERT-сети большой размерности/ А.П. Шибанов// Информационные технологии , № 1, 2002. С. 42-45.

59. Юдин Д.Б., Горяшко А.П., Немировский А.С. Математические методы оптимизации устройств и алгоритмов АСУ. М.: Радио и связь, 1982, 288 с.

60. Юнусов Р.В. Анализ надежности аппаратно-программного информационно-управляющего комплекса// Вестник НИИ СУВПТ: Сб. научн. трудов/ Под общей ред. профессора Н.В. Василенко; Красноярск: НИИ СУВПТ.- 2003. Выпуск 11.- С. 103-106.

61. Яппаров, Т.Г. Комплексные автоматизированные системы управления предприятием/ Т.Г. Яппаров// Средства и системы компьютерной автоматизации сервер АСУТП.ги: http://www/asutp.ru/?p=600330.

62. A solution with comfort and all the option. Manufacturing management, June 1996.

63. Boehm, B.W. Software Risk Management / IEEE СS Press Tutorial, 1989.

64. Gonzales, J.M: Deterministic Processor Scheduling / J.M. Gonzales// Computing Surveys. Vol. 9. No. 3. 1977.

65. Customer Synchronized Resource Planning: Become indispensable, Catherine de Rosa, APICS.

66. CSRP. www.symix.com. Русский перевод по адресу: csrp@socap.msk.ru.75. ISO 9000. www.osp.ru/ap/

67. Kovalev, I. Software engineering of spacecraft control technological cycles / In: "Modelling, Measurement and Control, B". Vol.56, №3. -AMSE PRESS, 1994.-P. 45-49.

68. Kovalev, I. Optimization Reliability Model for Telecommunications Software Systems /1. Kovalev , A. Privalov, Ju. Shipovalov. In: Modelling, Measurement and Control. - AMSE Periodicals, Vol.4-5, 2000 - P. 47-52.

69. MRP-ERP. plant.da.ru (http://www.geocities.com/WallStreet/2907/), erp.da.ru.

70. Neumann, K. Stochastic Project Network/ K. Neumann// Lecture Notes in Economics and Mathematical Systems, No. 34, Springer Verlag, 1990.

71. Neumann, K. An Optimality Equation for Stochastic Decision Networks/ K. Neumann//Wiss. Zeitschrift Techn. Hochschule Leipzig, No. 8, 1984. Pp. 7987.

72. Oracle University. "Enterprise DBA Part 1: Performance and Tuning", volume 1: Students Guide, Production 1.0.

73. Oracle University. "Enterprise DBA Part 2: Performance and Tuning", volume 2: Students Guide, Production 1.0.

74. Oracle Education. "Введение в Oracle: SQL и PL/SQL", Том 1: Руководство слушателя, Издание 1.1.

75. Oracle Education. "Введение в Oracle: SQL и PL/SQL", Том 2: Руководство слушателя, Издание 1.1.

76. Pritsker, А.А. GERT: Graphical Evaluation and Review Technique. Part. 1, Fundamentals/ A.A. Pritsker, W.W. Happ// The Journal of Industrial Engineering (May 1966).86; Supply Chain, www-rcf.usc.edu/~xin/supplychainbookmarks.htm

77. Shrivastava K.S. (editor). Reliable Computing Systems: Collected Papers of the Newcastle Reliability Project. Springer, Wien, New York, 1985.

78. Qatranti, T. Visual Modeling with Rational Rose and UML. Addison-Wesley, 1998.