Использование сетей Петри для анализа и синтеза оптимальных модульных систем обработки данных

Актуальность темы

В «Основных направлениях экономического и-социального развития СССР на 1981;1985 годы и на период до 1990 года» поставлена задача сосредоточить усилия на решение важнейших проблем в области естественных и технических наук, в том числе на «. совершенствование вычислительной техники, ее элементной базы и математического обеспечения, средств и систем передачи и обработки информации, повышение эффективности автоматизированных систем управления. «/I/.

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

Формализация моделей и разработка эффективных алгоритмов решения задач синтеза оптимальных модульных СОД на этапе технического проектирования позволяют автоматизировать процесс проектирования систем, сократить сроки проектирования, отладки и внедрения систем в промышленную эксплуатацию на 20−30 $, повысить качество проектных решений. Большие масштабы работ по созданию и внедрению СОД в различных областях народного хозяйства, а также отсутствие моделей и методов формализации и автоматизации процесса разработки оптимальных модульных ООД, учитывающих расширенные возможности современных ЭВМ и их комплексов, обуславливают актуальность выполненных научных исследований.

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

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

— б.

Петри.

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

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

Практическая ценность. Разработанные с использованием сетей Петри формальные модели, методы, алгоритмы и программы обеспечивают синтез оптимальных по заданным критериям эффективности и различных по своему назначению модульных систем обработки данных на этапе их технического проектирования. Кроме того, их целесообразно использовать при разработке программного обеспечения систем автоматизированного проектирования АСУ (САПР АСУ). Использование разработанных алгоритмов и программ проектирования модульных СОД позволяет сократить сроки разработки и внедрения систем в среднем на 20−30% и повысить качество проектных решений.

Алгоритмы решения поставленных задач реализованы на языках программирования Фортран 1У и РЬ/1, входящих в состав математического обеспечения многих отечественных вычислительных машин и могут использоваться при разработке или модернизации оптимальных модульных ООД в научно-исследовательских, проектных и конструкторских организациях, а также в вычислительных центрах, разрабатывающих, и внедряющих системы обработки данных.

Внедрение. Эффективность разработанных в диссертации моделей, методов, алгоритмов и программ синтеза с использованием аппарата сетей Петри модульных ООД подтверждена положительным опытом их использования при проектировании ряда систем. При непосредственном участии автора они внедрены при разработке первой очереди автоматизированной системы управления материально-техническим снабжением Московского метрополитена (АСУ МТС «Метро»), АСУ «РосСтройбанк', 1 систем реального времени «АСУ ТЯ-Контроль М.43% информационного и программного обеспечения АСУ группы предприятий Молдавского региона, ряда задач подсистемы «Техническая подготовка производства» Донецкого производственного объединения «Электробытмаш» и другие» Использование разработанных моделей и методов, алгоритмов и программ позволило сократить временные и стоимостные затраты на разработку, отладку и внедрение систем в среднем на 20−30% за счет оптимизации получаемых проектных решений.

Апробация работы* Основные результаты работы докладывались автором и обсуждались на Всесоюзном семинаре по методам синтеза типовых модульных систем обработки данных (Звенигород, 1981),.

Республиканском семинаре-совещании «Моделирование, идентификация, синтез систем управления процессами и производствами» (Донецк, 1982), Республиканском научно-техническом совещании «Автоматический контроль и управление в цветной металлургии1* (Ташкент, 1983) иг других совещаниях, конференциях.

Публикации. Изложенные результаты научных исследований выполнены по плану научных работ Ордена Ленина Института проблем управления № 12−79 «Синтез оптимальных модульных и типовых модульных автоматизированных информационно-управляющих систем» (ответственный исполнитель д.т.н. КульбаВ. В.)" по плану госбюджет*-ной тематики Донецкого госуниверситета «Теоретические и прикладные вопросы использования математических методов и ЭВМ в планировании и управлении промышленного производства» (номер государственной регистрации 8X103356), а также в соответствии с Целевой комплексной программой ГКНТ 0.80.06 «Создать новые и усовершенствовать действующие автоматизированные системы управления (АСУ) промышленными министерствами, производственными объединениями и предприятиями11 и опубликованы в шести научных трудах.

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

КРАТКИЕ ВЫВОДЫ.

В главе 4 получены следующие основные результаты.

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

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

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

4. Разработанные модели и методы синтеза программного и информационного обеспечения по критерию минимума общего времени обмена между оперативной и внешней памятью ЭВМ использовались при проектировании модульных СОД для задач АСУ «Росстройбанк» и АСУ МТС «Метро», что позволило сократить общее время на разработку, отладку и внедрение задач обработки данных на 20−25 $.

ЗАКЛЮЧЕНИЕ

.

В работе-.получены следующие основные результаты:

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

Разработаны модели программных модулей и информационных массивов, которые соответствуют ядрам фрагментов переходов и фрагментов состояний. Для введенных моделей определены понятия внутреннего и внешнего интерфейса, необходимые для синтеза оптимального состава программных модулей и информационных массивов • СОД.

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

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

3. С использованием критерия максимума информационной производительности поставлены и решены следующие задачи синтеза оптимальных модульных СОД реального времени: определение оптимального состава программных модулей при заданном информационном обеспечении — определение оптимального состава информационных массивов при заданном программном обеспечении СОДсинтез оптимальной функциональной модульной блок-схемы обработки данных. В качестве ограничений в задачах оптимизации используются ограничения на объем оперативной памяти, используемой программными модулями, на последовательность реализации процедур обработки данных, размер записей информационных массивов и другие характеристики СОД.

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

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

6. Разработаны модели и методы синтеза оптимальных модульных СОД (синтез оптимальной модульной блок-схемы ооработки данных, синтез программного и информационного обеспечения), функционирующих в режиме пакетной обработки. Полученные решения учитывают альтернативы в последовательности выполнения процедур обработки данных. Задачи оптимизации рассмотрены для двух основных способов обмена с внешней памятью: обмен данными осуществляется для модуля в целом или для отдельных множеств процедур, входящих в программный модуль.

7. Для решения поставленных задач синтеза разработаны комбинаторные алгоритмы, основанные на методах локальной оптимизации, наименьшего разбиения и последовательного построения, анализа и отбора вариантов решений. Сокращение рассматриваемых вариантов решения достигается использованием доказанных утверждений, основанных на использовании характерных особенностей и свойств модульных СОД и современной вычислительной техники. Разработанные алгоритмы реализованы на языках программирования РЬ /I и Фортран 1У, входящих в состав математического обеспечения ЕС ЭВМ.

8. Разработанные в диссертационной работе модели, методы, алгоритмы и программы использовались при разработке оптимальных модульных СОД для задач АСУ МТС «Метро», «АСУ ТП-Контроль МЧЗ», АСУ «Росстройбанк» и ряда задач АСУ группы предприятий Молдавского региона, подсистемы «Техническая подготовка производства» донецкого производственного ооъединения «Злектробытмаш», что позволило получить значительный экономический и технико-тактический эффект. (Подтвержденный актами о внедрении экономический эффект составляет 80 тыс. руб. в год).