Содержание к диссертации
Введение
ГЛАВА I . Сети петри и задачи синтеза оптимальных модульных систем обработки данных 15
1.1 . Синтез оптимальных модульных систем обработки данных (обзор) 16
1.2. Формализованное описание сетей Петри. Основные понятия и определения 24
1.3. Моделирование и анализ автоматизированных систем обработки данных с использованием сетей Петри 30
Краткие выводы 40
ГЛАВА 2. Синтез оптимальных модульных сод по критерию максимума информационной производительности . 42
2.1. Определение информационной производительности систем обработки данных 43
2.2. Анализ информационной производительности как целевой функции задач синтеза оптимальных модульных СОД 46
2.3. Постановка и решение задач синтеза оптимальных модульных СОД по критерию максимума информационной производительности 61
2.4. Синтез оптимальной модульной системы обработки данных для подсистемы '''АСУ ТП-Контроль МЧЗ" 80
Краткие выводы 86
ГЛАВА 3. Синтез оптимальных модульных сод, реализуемых на базе мультипроцессорных вычислительных систем 88
3.1 . Особенности разработки СОД, реализуемых на базе мультипроцессорных вычислительных систем . 89
3.2. Постановка и решение задач синтеза программного и информационного обеспечения СОД, реализуемых с использованием однородных вычислительных систем с жестко распределенной оперативной памятью 96
3.3. Задачи синтеза оптимальных модульных СОД, , , реализуемых на базе однородных вычислительных систем со свободно распределенной оперативной памятью 109
3.4. Задача синтеза состава программных модулей СОД, реализуемой на базе
мультипроцессорной вычислительной системы с перестраиваемой структурой 114
3.5. Использование моделей и методов синтеза оптимальных модульных СОД при проектировании задач "АСУ ТП-Контроль МЧЗ" 121
Краткие. выводы 127
ГЛАВА 4 . Синтез оптимальных модульных сод по критерию минимума общего времени обмена с внешней памятью эвм 130
4.1. Синтез оптимального состава модулей программного обеспечения систем обработки данных 131
$ 4.2. Синтез оптимальной функциональной модульной блок-схемы обработки данных и
оптимального состава информационных массивов СОД . 139
4.3. Использование методов синтеза программного и информационного обеспечения.оптимальных модульных СОД при проектировании задач АСУ "Росстройбанка" и АСУ МТС "Метро" 147
Краткие выводы 159
Заключение 161
Литература 165
Приложение 172
- . Синтез оптимальных модульных систем обработки данных (обзор)
- Анализ информационной производительности как целевой функции задач синтеза оптимальных модульных СОД
- . Особенности разработки СОД, реализуемых на базе мультипроцессорных вычислительных систем
- Синтез оптимального состава модулей программного обеспечения систем обработки данных
Введение к работе
Актуальность темы. В "Основных направлениях экономического и-социального развития СССР на I98I-I985 годы и на период до 1990 года" поставлена задача сосредоточить усилия на решение важнейших проблем в области естественных и технических наук, в том числе на "... совершенствование вычислительной техники, ее элементной базы и математического обеспечения, средств и систем передачи и обработки информации, повышение эффективности автоматизированных систем управления... " /I/.
Широкое развитие автоматизированных систем управления, и в первую очередь систем обработки данных (ООД), определяет повышенные требования к качеству и эффективности процесса проектирования их информационного и программного обеспечения. Современные системы обработки данных характеризуются большим разнообразием и сложностью взаимосвязей элементов, обработкой больших массивов информации, наличием альтернативных вариантов обработки и элементов конкурентности при использовании ресурсов ЭВМ. Повышение эффективности проектирования систем обработки данных связано с использованием методов синтеза оптимального состава модулей программного и информационного обеспечения на этапе технического проектирования ООД. Вместе с тем, имеющийся в настоящее время аппарат для формализации задач синтеза оптимальных модульных ООД, реализуемых на современных ЭВМ, не полностью описывает их технологические возможности. Полученные проектные решения (структура программных модулей, содержание информационных массивов) определяются обычно без учета наличия альтернативных вариантов обработки, возможности параллельной реализации отдельных процедур, ветвей алгоритма и программных модулей, конкурентности их по отношению к ресурсам ЭВМ. Возникает необходимость в разработке моделей и методов син- '- 5 - теза оптимальных модульных ООД, позволяющих преодолеть отмеченные недостатки. Для этих целей целесообразно использовать аппарат сетей Петри, который позволяет формировать адекватные модели (Щ, поставить задачи синтеза оптимальных модульных ООД и разработать методы их решения.
Формализация моделей и разработка эффективных алгоритмов решения задач синтеза оптимальных модульных СОД на этапе технического проектирования позволяют автоматизировать процесс проектирования систем, сократить сроки проектирования, отладки и внедрения систем в промышленную эксплуатацию на 20-30$, повысить качество проектных решений. Большие масштабы работ по созданию и внедрению СОД в различных областях народного хозяйства, а также отсутствие моделей и методов формализации и автоматизации процесса разработки оптимальных модульных СОД, учитывающих расширенные возможности современных ЭВМ и их комплексов, обуславливают актуальность выполненных научных исследований.
Цель работы. Целью данной работы является разработка с использованием аппарата сетей Петри формализованных моделей, методов, алгоритмов и программ, синтеза оптимальных модульных систем обработки данных на этапе технического проектирования, учитывающих расширенные возможности современных ЭВМ и их комплексов, наличие альтернатив в последовательности выполнения процедур обработки данных, возможность параллельного выполнения процедур, ветвей алгоритма и программных модулей, их конкурентность по отношению к ресурсам ЭВМ.
Научная новизна. На основе проведенных исследований и обобщения опыта создания и использования модульных систем обработки данных разработаны методология, модели и методы анализа и синтеза оптимальных модульных систем обработки данных, основанные на использовании для их моделирования и оптимизации аппарата сетей - б -
Петри.
Разработанные на основе предложенной методологии методы формализации, модели, алгоритмы и программы анализа и синтеза оптимальных модульных ООД обеспечивают: синтез оптимальной модульной блок-схемы обработки данных; синтез программных модулей; синтез состава информационных массивов и выбор способов их организации; определение оптимальной величины блоков информационных массивов; определение оптимальной последовательности выполнения процедур обработки данных; выбор оптимального расписания работы программных модулей в многопроцессорных ЭВМ. В качестве критериев синтеза используются: максимум информационной производительности ООД, минимум общего времени обмена между оперативной и внешней памятью ЭВМ, максимум суммарного числа независимых ветвей в программных модулях. Для решения поставленных задач разработаны эффективные точные и приближенные комбинаторные алгоритмы, основанные на учете особенностей модульных ООД и решаемых задач, отраженных в ряде доказанных утверждений, и позволяющих сократить число рассматриваемых вариантов решения.
Модели, методы и алгоритмы задач синтеза оптимальных модульных ООД разработаны и опубликованы автором впервые либо являются обобщением уже известных моделей. Их использование позволяет адекватно описывать процесс функционирования систем обработки данных, формализовать, алгоритмизировать и в значительной степени автоматизировать этап технического проектирования систем, повысить качество формируемых проектных решений.
Практическая ценность. Разработанные с использованием сетей Петри формальные модели, методы, алгоритмы и программы обеспечивают синтез оптимальных по заданным критериям эффективности и различных по своему назначению модульных систем обработки данных на этапе их технического проектирования. Кроме того, их целесооб- разно использовать при разработке программного обеспечения систем автоматизированного проектирования АСУ (САПР АСУ). Использование разработанных алгоритмов и программ проектирования модульных СОД позволяет сократить сроки разработки и внедрения систем в среднем на 20-30$ и повысить качество проектных решений.
Алгоритмы решения поставленных задач реализованы на языках программирования Фортран ІУ и PL/1, входящих в состав математического обеспечения многих отечественных вычислительных машин и могут использоваться при разработке или модернизации оптимальных модульных СОД в научно-исследовательских, проектных и конструкторских организациях, а также в вычислительных центрах, разрабатывающих, и внедряющих системы обработки данных.
Внедрение. Эффективность разработанных в диссертации моделей, методов, алгоритмов и программ синтеза с использованием аппарата сетей Петри модульных СОД подтверждена положительным опытом их использования при проектировании ряда систем. При непосредственном участии автора они внедрены при разработке первой очереди автоматизированной системы управления материально-техническим снабжением Московского метрополитена (АСУ МТС "Метро"), АСУ "РосСтройбанк1,1 систем реадьного времени "АСУ ТП-Контроль М.43% информационного и программного обеспечения АСУ группы предприятий Молдавского региона, ряда задач подсистемы "Техническая подготовка производства" Донецкого производственного объединения "Электробытмаш" и другие» Использование разработанных моделей и методов, алгоритмов и программ позволило сократить временные и стоимостные затраты на разработку, отладку и внедрение систем в среднем на 20-30$ за счет оптимизации получаемых проектных решений.
Апробация работы* Основные результаты работы докладывались автором и обсуждались на Всесоюзном семинаре по методам синтеза типовых модульных систем обработки данных (Звенигород, 1981),
Республиканском семинаре-совещании "Моделирование, идентификация, синтез систем управления процессами и производствами" (Донецк, 1982), Республиканском научно-техническом совещании "Автоматический контроль и управление в цветной металлургии1* (Ташкент, 1983) иг других совещаниях, конференциях*
Публикации. Изложенные результаты научных исследований выполнены по плану научных работ Ордена Ленина Института проблем управления № 12-79 "Синтез оптимальных модульных и типовых модульных автоматизированных информационно-управляющих систем" (ответственный исполнитель д.т.н. КульбаВ. В.), по плану госбюджетной тематики Донецкого госуниверситета "Теоретические и прикладные вопросы использования математических методов и ЭВМ в планировании и управлении промышленного производства" (номер государственной регистрации 8II03356), а также в соответствии с Целевой комплексной программой ГКНТ 0.80.06 "Создать новые и усовершенствовать действующие автоматизированные системы управления (АСУ) промышленными министерствами, производственными объединениями и предприятиями11 и опубликованы в шести научных трудах.
Объем работы. Диссертационная работа состоит из введения,, четырех глав, заключения, приложения и включает 132 страницы машинописного текста, 12 рисунков и 13 таблиц.
Содержание работы распределено по главам следующим образом.
В первой главе диссертации рассматриваются основные проблемы и задачи синтеза оптимальных модульных СОД, приводится обзор основных результатов, полученных в области формализации процесса проектирования систем обработки данных. Обоснована целесообразность использования сетей Петри для анализа и синтеза оптимальных модульных СОД.
Одним из наиболее перспективных методов проектирования еи-етем обработки данных является метод оптимального модульного проектирования, заключающийся в оптимальном (по заданному критерию) синтезе отдельных частей программного и информационного обеспечения, выполняющих заданные функции по преобразованию информационных элементов Использование этого метода при проектировании систем обработки данных сокращает сроки создания СОД и повышает их качество. Описаны и проанализированы критерии оптимальности и ограничения, используемые при синтезе программного и информационного обеспечения СОД.
Используемые традиционные модели СОД (сетевые, графовые модели, модели теории расписаний) не полностью учитывают характерные особенности современных ЭВМ и систем обработки данных: возможности параллельной реализации отдельных процедур и программных модулей на множестве процессоров, наличие альтернативных вариантов обработки данных, конкурентность программных модулей между собой, по отношению к информационным массивам и ресурсам ЭВМ и другие. Для учета этих особенностей при моделировании СЭД предлагается использовать сети Петри, позволяющие адекватно описывать дискретные процессы обработки данных на современных ЭВМ или в сетях-ЭВМ.
Разработана модель системы обработки данных с использованием сети Петри, переходы которой соответствуют процедурам обработки данных, а состояния - информационным элементам. Модель позволяет учитывать при синтезе СОД динамику функционирования программных модулей и их взаимодействие с информационными массивами. Введены необходимые теоретико-множественные операции над элементами сети Петри, позволяющие выделять множества элементов ООД с заданными свойствами.
Разработаны модели программных модулей и информационных массивов, которые являются ядрами фрагментов переходов и фрагментов состояний. Для введенных моделей определены понятия внутреннего и внешнего интерфейса, необходимые для синтеза оптимального состава программных модулей и информационных массивов СОД.
Во второй главе обосновано использование показателя максимума информационной производительности как достаточно общего критерия эффективности систем обработки данных, определяющего среднее количество информации, выдаваемое системой на один запрос пользователя в единицу времени. Показана корректность и эффективность использования введенного критерия для различных режимов функционирования СОД.
Оценка качества проектирования СОД по таким частным критериям, как минимум числа информационных связей между модулями, минимум числа обращений к внешней памяти и другим показателям, не позволяет определить количество информации, выдаваемое системой обработки данных пользователю на один запрос в течение определенного интервала времени. Предлагаемый критерий максимума информационной производительности является наиболее важным, с точки зрения пользователя, и позволяет при оценке эффективности разрабатываемой системы учесть указанную характеристику.
Исследованы зависимости информационной производительности системы от вероятностей запросов наборов информационных элементов и времени их формирования. Решена задача определения множества наборов вероятностей запросов пользователей, на котором значение информационной производительности не менее заданного. Решение данной задачи позволяет для каждой конкретной СОД определить изменение информационной производительности при заданных изменениях вероятностей запросов пользователей.
С использованием критерия максимума информационной производительности поставлены и решены следующие задачи синтеза оптимальных модульных СОД: определение оптимального состава программных модулей при'заданном информационном обеспечении СОД; опре- - II - деление оптимального состава и величины блоков системы информационных массивов при заданном программном обеспечении СОД; синтез оптимальной функциональной модульной блок-схемы обработки данных. Для решения поставленных задач разработаны комбинаторные алгоритмы, основанные на методах локальной оптимизации, последовательного построения, анализа и отбора вариантов и схеме "ветвей и границ".
Предложенные модели и методы использованы при разработке программного и информационного обеспечения задач "АСУ ТП-Контроль МЧЗ", что позволило сократить общее время на разработку, отладку и внедрение задач на 20-30$.
В третьей главе поставлены и решены задачи синтеза оптимальных модульных СОД, функционирующих на базе однородных мультипроцессорных вычислительных систем. Приведен анализ общих характеристик и свойств таких систем.
В настоящее время в различных областях использования вычислительной техники широкое применение получили однородные вычислительные системы, основные преимущества которых состоят в значительном увеличении производительности и надежности при решении задач обработки данных.
С использованием аппарата сетей Петри введен ряд понятий и определений, необходимых для описания процесса функционирования модульных СОД, реализуемых на базе мультипроцессорных вычислительных систем. Доказаны утверждения относительно условий формирования оптимального состава программных модулей и их реализации в однородной вычислительной системе, позволяющие формализовать задачи синтеза программного и информационного обеспечения модульных СОД.
Поставлены и решены задачи синтеза функциональной модульной блок-схемы СОД, реализуемой на базе однородных вычислительных систем со свободно и жестко распределенной оперативной памятью по критерию максимальной информационной производительности СОД, при ограничениях на объем оперативной памяти, занимаемый одновременно выполняющимися программными модулями и на их количество.
С использованием критерия максимума информационной производи тельности поставлены и решены частные задачи синтеза модульных СОД: определение оптимального состава программных модулей при за данном информационном обеспечении; определение оптимального со става информационных массивов при заданном программном обеспече нии; оптимальное распределение программных модулей по процессорам системы. -
Поставлена и решена задача синтеза программных модулей СОД, реализуемой на базе мультипроцессорной вычислительной системы с перестраиваемой структурой. В качестве критерия синтеза рассматривается максимум общего числа независимых линейных ветвей в программных модулях СОД, которые могут выполняться параллельно на необходимом множестве процессоров системы.
Для решения поставленных задач синтеза разработаны комбинаторные алгоритмы, основанные на методах локальной оптимизации, последовательного построения, анализа и отбора вариантов. Сокращение рассматриваемых вариантов решений достигается использованием доказанных утверждений относительно характерных особенностей и свойств модульных СОД и мультипроцессорных вычислительных систем. Разработанные алгоритмы реализованы на языке PL /і , входящем в состав математического обеспечения ЕС ЭВМ.
В четвертой главе рассмотрены задачи синтеза оптимальных модульных систем обработки данных, функционирующих в режиме пакетной обработки. В системах такого класса запрашивается, как правило, набор информационных элементов, содержащий в совокупности все выходные состояния системы. Для того, чтобы максимизировать - ІЗ - информационную производительность таких систем, необходимо минимизировать время получения всех выходных информационных элементов, которое, в основном, определяется временем обмена программных модулей с внешней памятью ЭВМ.
Формализована и решена задача синтеза блок-схемы модульной СОД, функционирующей в режиме пакетной обработки по критерию минимума общего времени обмена с внешней памятью. В процессе решения определяются не только оптимальный состав программных модулей и информационных массивов, но и последовательность выполнения процедур. Данная задача решается с использованием метода локальной оптимизации и алгоритмов решения частных задач синтеза.
Поставлены и решены задачи синтеза программных модулей при заданном информационном обеспечении СОД по критерию минимума общего времени обмена с внешней памятью и по критерию минимума общего числа обращений к внешней памяти ЭВМ.
Данные задачи решены с использованием метода последовательного построения, анализа и отбора вариантов. Сокращение числа рассматриваемых вариантов решения достигается на основе использования свойств и особенностей модульных СОД, а также обоснованных утверждений.
Поставлена и решена задача оптимального выбора состава информационных массивов по критерию минимума общего времени обмена между внешней и оперативной памятью ЭВМ при заданном, составе программных модулей. Решение данной задачи состоит в определении оптимальной последовательности выполнения процедур в программных модулях по критерию минимума числа обращений к внешней памяти и последующем выборе состава информационных массивов. Для решения данной задачи разработан комбинаторный алгоритм, основанный на методах последовательного построения, анализа и отбора вариантов решений и наименьшего разбиения.
Разработанные в диссертационной работе модели, методы, алгоритмы и программы использовались при разработке оптимальных модульных СОД для задач "АСУ МТС "Метро", "АСУ ТП-Контроль МЧЗ", АСУ "РосСтройбанк" и ряда задач АСУ группы предприятий Молдавского региона, что позволило получить значительный экономический и технико-тактический эффект. (Подтвержденный актами о внедрении экономический эффект составляет 80 тыс. руб. в год).
В приложении к диссертации приведены описания и характеристики программ для решения задач синтеза оптимальных модульных систем обработки данных, а также материалы, подтверждающие практическое использование и внедрение полученных автором результатов исследований. пава і. сети петри и задачи синтеза, оптимальных модульных систем обработки: данных
В данной главе проведен анализ существующих моделей и методов синтеза оптимальных модульных систем обработки данных.
Используемые традиционные модели СОД (сетевые, графовые модели, модели теории расписаний и другие) не полностью учитывают характерные особенности современных ЭВМ и систем обработки данных: возможности параллельной реализации.отдельных процедур и программных Модулей на множестве процессоров, наличие альтернативных вариантов обработки данных, конкурентность программных модулей между собой, по отношению к информационным массивам и ресурсам ЭВМ и другие особенности. Для учета этих особенностей при моделировании СОД. предлагается использовать сети Петри, позволяющие адекватно описывать дискретные процессы обработки данных на современных ЭВМ или в сетях ЭВМ.
С помощью аппарата сетей Петри строится формальная модель взаимодействия программных модулей и информационных массивов в сложных системах обработки данных с конкурирующими событиями и наличием ограничений на возможности технологии и технических средств обработки данных. Посредством сетей Петри моделируются основные события, происходящие в дискретных системах обработки данных, условия, определяющие их возникновение и изменение, а также соотношения между событиями и условиями. Процедурам и информационным элементам систем обработки данных ставятся в соответствие элементы сетей Петри - переходы и состояния. И в зависимости от связи процедур и информационных элементов определяются функции инцидентности.
Вводятся теоретико-множественные операции на элементах се- ти, необходимые для выделения множеств элементов сети, обладающих заданными свойствами. .
Приводятся особенности построения графа достижимости сети Петри, который используется для разработки алгоритмов синтеза оптимальных модульных СОД.
1.1. Синтез оптимальных модульных систем обработки данных Хобзор)
Оэздание и развитие ЭВМ позволило приступить к эффективному решению больших и сложных задач вычислительного характера. Однако в дальнейшем основной сферой применения электронных вычислительных машин стали невычислительные задачи, в которых над элементами обрабатываемой информации или вовсе не выполняются никакие арифметические действия, или же их доля относительно невелика/42, 18/. Основное внимание в таких задачах уделяется вводу - выводу больших информационных массивов, поиску в них нужных сведений и так далее. О размерах информационных массивов современных систем обработки данных можно судить по АСУ "Прибор" /23/, годовой объем входной информации которой составляет более 350 млн. знаков. фоки создания АСУ крупными министерствами и ведомствами составляет 8-Ю лет, стоимость разработки - от 5 до 30 млн. руб., трудоемкость - от 500 до 1500 человеко-лет /7/. Потребности в программном обеспечении растут значительно быстрее (22$ в год), чем возможности их разработки, которые увеличиваются примерно на 15% в год /54, 57/. В последние годы разработка АСУ связывается прежде всего с построением модульных систем обработки данных, поскольку при разработке модульных СОД затраты сокращаются на 20-25$ по сравнению с индивидуальным проектированием. Еще больший эффект достигается при проектировании типовых модульных
СОД: затраты и время проектирования уменьшаются в 2-3"раза /5, 32, 57/.
Необходимость развития модульного принципа проектирования определяется также интенсивными разработками в области построения САПР АСУ, так как модульный принцип проектирования программных модулей является основным при создании и- расширении банка проектных решений (БПИ) САПЕ АСУ. Основная компонента этой базы - модуль-замкнутый функционально программный элемент, имеющий развитую систему описаний /53/.
В настоящее время используются две основные стратегии мо--дульного проектирования: "сверху - вниз" и "снизу - вверх" /б, 51, 59, 61/.
Основным понятием при модульном проектировании является понятие модуля системы обработки данных. Наиболее распространенными неформальными определениями являются: "модуль есть поименованное множество программных инструкций или макрокоманд" /62/, "модуль - это целевая структуризация программного обеспечения" /63/, В определении, данном в /65/ выделены две основные характеристики модуля: мощность, то есть количество процедур обработки данных, которые он может реализовать и связность его с другими модулями системы. В /10, 26/ приведено формальное определение многофункционального"модуля СОД, основанного на понятии информационных элементов и процедур обработки данных и используемое в предлагаемой работе.
Модульный принцип проектирования систем обработки данных связан с разбиением системы на отдельные слабо связанные компоненты, допускающие относительно независимую разработку и использование. Система является модульной, если она состоит из некоторого множества частей или модулей, имеющих интерфейс, определенный таким образом, что каждый модуль не имеет информации о внутреннем содержании других модулей, кроме той, которая содержится в спецификациях интерфейса /15/.
Преимущества модульного принципа проектирования заключаются в повышений качества проектирования, облегчении программирования и отладки модулей, а также модернизации существующих систем.
Существуют различные способы разбиения информационного и программного обеспечения СОД на модули: функциональной; по числу информационных и управляющих связей между модулями; по имеющимся возможностям технического и программного обеспечения ; по использованию типовых стандартных элементов и решений; смешанные способы /24/.
Оптимальное проектирование модульных СОД - многоэтапный процесс принятия строго обоснованных и оптимальных решений в процессе анализа систем, проектирования, отладки и внедрения новой системы. Последовательность основных этапов разработки систем обработки данных приведена на рис. I.I.I.
На этапе предпроектного анализа СОД /2, 20, 24/ проводится ряд работ, наиболее важной из которой является определение необходимого набора процедур, реализующих заданные функции, а также необходимой для их решения информации.
На этапе технического проектирования осуществляется синтез оптимальной модульной СОД, под которым понимается определение оптимального состава и числа модулей системы, а также содержания и методов организации информационного обеспечения. Полученные решения уточняются и доводятся до программной реализации на стадии рабочего проектирования.
Методы синтеза модульных СОД можно разбить на два класса: методы синтеза рациональных модульных СОД /22, 64, 65/, позволяющие формально оценивать качество проектирования и методы синтеза оптимальных модульных систем по заданным критериям ка-
Отладка
Анализ существующих систем
Разработка требований к СОД
Техническое проектирование
Рабочее проектирование
Ввод в эксплуатацию опытная экс плуатация
Промышленная эксплуатация и модернизация
Предварительный анализ
Детальный анализ Подготовка данных
Анализ характеристик существующих модулей
Синтез СОД
Задачи синтеза программного обеспечения СОД I
Синтез функциональной модульной блок-схемы обработки данных I
Задачи синтеза информационного обеспечения СОД
Определение оптимального состава модулей Определение последовательности выполнения процедур Упорядочение во времени выполнения программных модулей на различных процессорах
Определение оптимального состава информационных массивов, структуры записей и способов их организации в информационных массивах
Рис. I.I.I.
Основные этапы разработки СОД чества /16, 17, 25, 26, 27, ЗО, .31/.
При решении задач синтеза оптимальных модульных СОД в качестве критерия их эффективности используются различные характеристики систем, при этом цели, преследуемые пользователем и разработчиком, в значительной степени противоречивые AV» Пользователь заинтересован в получении оптимальной, в некотором смысле, системы управления, чаще всего в качестве критерия оптимальности, в этом случае, используются показатели качества объекта проектирования A3/. Для разработчика, в большей степени чем для пользователя, важным фактором является обобщенная стоимость системы проектирования. Рассмотрим основные критерии оптимальности, используемые при синтезе модульных систем обработки данных.
Модули систем обработки данных связаны между собой входной информацией и информацией, которая является результатом выполнения одного модуля и входной для другого. Такая информация объединяется в массивы по различным признакам однотипности, особенностям получения и использования, организации структуры записей и методам организации массивов и так далее. При этом информационные массивы играют роль информационного интерфейса между модулями системы. Большое число, и сложный характер связей между модулями повышают число ошибок при проектировании систем, степень влияния ошибок в одних модулях на работу других модулей, затрудняют процесс раздельного проектирования программного и информационного обеспечения. Все это обуславливает необходимость проектирования модульных систем обработки данных, при котором минимизируется общий интерфейс между модулями системы /17, 27, 31/. Программные модули, полученные в процессе решения задач, ' связаны между собой минимальным числом информационных элементов.
Время решения задач обработки данных существенным образом зависит от времени обмена информацией между внешней и оперативной памятью ЭВМ, которое в свою очередь зависит от структуры программных модулей и информационных массивов, их связей, типа и объема используемой памяти и так далее. Различие в технических характеристиках внешних устройств современных ЭВМ и методов доступа к массивам, размещаемых на них, определяют необходимость больших затрат времени решения задач на обмен с внешней памятью ЭВМ. Поэтому одним из важнейших критериев синтеза оптимальных модульных ООД, является минимизация общего времени обмена с внешней памятью /2, 20, 26/. Упрощенным вариантом этого критерия является минимизация числа обращений к внешней памяти. Он используется в том случае, когда возникают трудности с определением временных характеристик обращения к программным модулям и информационным массивам.
Эффективность обмена между оперативной и внешней памятью может быть оценена также с помощью специального показателя технологической сложности алгоритмов обработки данных, под которым понимается отношение общего объема пересылок процедур и данных при решении задачи к объему полезных пересылок входных данных решаемой задачи. Минимизация технологической сложности алгоритмов ООД позволяет уменьшить общее число обращений к внешней памяти ЭВМ и объем промежуточных данных. Данный критерий является обобщением показателей, оценивающих число обращений к внешней памяти и "транспортного фактора" /60/, позволяющего определить степень целесообразности создания промежуточных массивов данных при решении задач. Критерий технологической сложности реализации алгоритмов позволяет оценить структуру ООД в целом, то есть эффективность системы модулей программного обеспечения и информационных массивов. Значительные потери времени на пересылку используемых данных в конкретном наборе процедур происходят при нерациональном объединении процедур обработки данных в модули и информационных элементов в массивы. В проектных решениях, получаемых при решении задач синтеза СОД по критерию минимизации ненужных пересылок, повышается качество разрабатываемой ООД и улучшаются временные характеристики функционирования СОД.
С точки зрения пользователей модульных ООД, работающих в масштабе реального времени, одним из наиболее важных критериев эффективности систем, является информационная производительность, которая определяется как среднее количество информации, выдаваемое системой на один запрос в единицу времени. Получаемые- при синтезе модульных СОД оптимальные проектные решения учитывают не только содержания, самих запросов, но и вероятности их поступления и время обработки запросов.
На синтезируемые программные модули и информационные массивы накладываются некоторые ограничения. Рассмотрим основные из них.
Объем оперативной памяти ЭВМ ограничен тем или иным числом байт (или кбайт) в зависимости от типа ЭВМ. Поэтому синтезируемые модули должны иметь объем не более заданного, включая и объем оперативной памяти для размещения блоков, необходимых информационных массивов.
В целях экономии внешней и оперативной памяти обычно запрещается дублирование процедур обработки данных в программных модулях и информационных элементов в массивах. Разработка программных модулей, как правило, осуществляется отдельными группами специалистов. В связи с этим накладываются ограничения на общее число программных модулей, разрабатываемой системы. Аналогичные ограничения накладываются и на синтезируемые информационные массивы.
Для систем обработки данных, функционирующих в масштабу ре- ального времени, характерным является использование одного и того же модуля для реализации различных запросов на выдачу содержаний информационных элементов. В связи с этим возникают большие сложности построения эффективных программных модулей, имеющих точки разрывов второго рода /2/. Поэтому при синтезе ООД реального времени предполагается, что синтезируемые программные модули имеют точки разрывов только первого рода.
Мультипроцессорные вычислительные системы содержат конечное число (в зависимости от конкретной системы) процессоров. Поэтому для них является существенным ограничение на число одновременно выполняющихся модулей.
Некоторые мультипроцессорные системы имеют общую оперативную память. В таких системах каждый процессор может обращаться к любому блоку оперативной памяти. В связи с этим общая память, занимаемая одновременно выполняющимися модулями, не должна превышать объема оперативной памяти, имеющегося в распоряжении мультипроцессорной вычислительной системы.
Для формализации моделей и методов синтеза оптимальных модульных ООД, учитывающих расширенные возможности современных ЭВМ и их комплексов, наличие альтернатив в последовательности выполнения процедур обработки данных, возможность параллельной работы процедур, ветвей алгоритма и программных модулей эффективным оказывается применение аппарата сетей Петри. В 1.2. приведены основные понятия и определения аппарата сетей Петри, используемые для анализа систем обработки данных и синтеза оптимальных модульных СОД.
1.2. "Формализованное описание сетей Петри. Основные понятия и определения.
Сети Петри /13, 58, 66,67/ нашли широкое применение во многих областях научных исследований как простой и удобный инструмент для анализа дискретных систем. Они позволяют проследить динамику функционирования, конкурентности различных элементов системы, их взаимодействие.
Сети Петри представляют собой двудольный граф. В отличие от сетей типа PERT они имеют два типа вершин, отображающих множество возможных событий или переходов систем, и множество условий или состояний. Элементы первого множества отображаются черточками (барьерами), а элементы второго - кружками. Дуги соответствуют функциям, связывающим множества состояний и переходов. Выделяются входные и выходные функции переходов. Входная функция переходов определяет для каждого перехода множество его входных состояний, а выходная - множество его выходных состояний.
Таким образом, сеть Петри определена множествами состояний и переходов, а также входными и выходными функциями переходов.
При использовании сетей Петри вводится понятие маркера, под которым понимается метка готовности запуска перехода по каждому из его входных состояний. Наличие маркера отмечается точкой в кружочке, соответствующем состоянию. Число точек соответствует числу маркеров в каждом состоянии. Переход может сработать, если в каждом его входном состоянии имеется хотя бы один маркер. Размещение маркеров по вершинам-состояниям сети Петри называется ее разметкой. Сеть имеющая разметку называется помеченной сетью Петри.
Таким образом, сеть Петри - это набор N~(P,T,F,H ,М.о) где Р - непустое конечное множество состояний, Т - не- пустое конечное множество переходов, F.-РхгЧод} функции инцидентности, #:Г*р-Ч0Д}
3(0: Р-^{0, I, 2, ...} - начальная разметка сети.
Графически сеть Петри целесообразно представить в виде ориентированного графа. Множество вершин графа образует множество PUT Вершину-со стояние Р и вершину-переход t соединяем дугой ( р , і ), если F ( Р , * ) = I и дугой ( t , Р ), если ff{ І , р ) =1. Вершины-состояния помечаются целыми неотрицательными числами, а при графическом изображении сети Петри - соответствующим числом маркерных точек.
Если все состояния сети обозначить последовательно символами рх , pz , ... , р^ , то разметку всех состояний сети удобно представить в виде П -мерного вектора 7И. » координаты которого равняются числу маркерных точек в соответствующих состояниях .. ..
Пусть, например, задана следующая сеть Петри Ж = ( Р ,
Т, F ,н ,м >'Р4&.А.А}.Г-{*іЛЛ}, М" а.0,1). , _ h к 4 ff. Pl Pz Рз />3
10 1 tl
0 10 іг
0 0 1 1Ъ
Графическое изображение данной сети представлено на рис. І.2.І.
Функционирование сети Петри заключается в переходе от одной разметки к другой. Смена разметок происходит в результате срабатывания одного из переходов. Переход / может сработать при разметке М. * если:
Рис. I.2.I. Пример сети Петри . M(p)-F(p,t)>o,VptP. CI.2.D)
Это означает, что каждое входное состояние перехода t помечено хотя бы одной маркерной точкой.
В результате срабатывания некоторого перехода t , удовлетворяющего условию (1.2.1), разметка Ж заменяется разметкой М' : vptp,M(p)-Mcp)-F(p,t)+ на ,р), то есть при срабатывании перехода из каждого его входного состояния удаляется и в каждое выходное состояние добавляется одна маркерная точка. Будем говорить, что разметка М. предшествует разметке Ж и обозначать Ж —*-М..
Функционирование сети Петри можно представить в виде графа достижимости, вершинами которого являются отдельные разметки сети. Две вершины Ж и Ж графа достижимости соединяются дугой, помеченной символом і , если Ж —-М . Фрагмент графа достижимости для сети Петри, изображенной на рис. 1.2.1,-представлен на рис. 1.2.2.
Если при некоторой разметке ни один из переходов сработать не может,-то такая разметка называется тупиковой. Так, например, для сети Петри, изображенной на рисунке І.2.І разметки (0,0,1) (0,0,2) (0,0,3) являются тупиковыми.
Разметка М. достижима в сети от разметки если существует такая последовательность переходов 1= ( ^ і » tt tk ). что м^м^м^-Лм'.
Сеть Петри с заданной начальной разметкой, в множестве достижимых разметок которой есть разметка со сколь угодно большим числом меток-В некоторой координате, называется неограниченной /36/. Так сеть Петри, представленная на рисунке I.2.I является І 2
Рис. 1.2.2. Фрагмент графа достижимости неограниченной, поскольку при срабатывании перехода L число маркерных точек в состоянии рг неограниченно растет (см. рис. 1.2.2). Если же в любой достижимой разметке сети Петри с заданной начальной разметкой число меток в каждой координате не превосходит некоторого числа С , то сеть называется
С -ограниченной. Если С - I, сеть называется 1-ограничен-ной или безопасной.
Сеть Петри называется связной, если любые ее две вершины соединены цепью в графе, полученном из исходной сети при замене каждой ее дуги неориентированным ребром.
Переход і достижим от разметки , если существует разметка }J[ , достижимая от разметки М. » при которой переход t может сработать.
Переход - живой, если он достижим от любой разметки из множества всех достижимых в сети Петри Ж разметок.
Сеть Петри Jf живая, если все ее переходы живые. Очевидно, если имеется хотя бы одна тупиковая разметка, то соответствующая сеть Петри не является живой. Такой является сеть, изображенная на рис. I.2.I.
Проблема распознавания живучести и безопасности сети решается в /66/,-но это решение связано с большими вычислительными трудностями, так как производится построение и просмотр графа достижимости. В /47/ приводится способ сокращения исходной сети за счет выделения некоторых правильных ее фрагментов и замещения их позициями-дублерами, после чего производится проверка живучести и безопасности с использованием графа достижимости. - зо -
1.3. Моделирование и анализ автоматизированных систем обработки данных с использованием сетей Петри
Автоматизированные системы обработки данных представляют собой совокупность трех основных компонент: модулей программного обеспечения, информационных массивов и вычислительных средств обработки данных.
В свою очередь, модули программного обеспечения представляют собой совокупности процедур обработки данных, а информационные массивы - совокупности информационных элементов.
Под процедурами понимаются некоторые инструкции (формулы) или их совокупность (алгоритм) преобразования одних информационных элементов в другие безотносительно к средствам, на которых они реализуются. Примерами процедур могут быть стандартные подпрограммы, операторы и команды, либо их совокупности, способные выполнить заданное преобразование информационных элементов. Под информационным элементом понимается совокупность данных, объединенных единым смысловым содержанием /26, 32/..
Таким образом, безотносительно к техническим средствам, на которых реализуются процедуры обработки данных, СОД в первую очередь определяются множеством информационных элементов D и множеством процедур их обработки А
Пусть А= {аі,#2,...Дг,.-,#} " множество процедур ООД и -0^1^1,.......} - множество информационных элементов ООД. Для каждой процедуры 0Lr 6 А определены множества входных и выходных информационных элементов, обрабатываемых данной процедурой, то есть задана матрица взаимосвязей процедур и информационных элементов.
Представим процесс реализации процедур СОД с помощью сети Петри, определенной набором Ж= {і, і ,ї ,ГІ ,М.0\ /12, 29//. - ЗІ -
Поставим в соответствие каждому элементу и D вершину-состояние pL ('элемент d-i ") сети Петри JV . Множество элементов р обозначим Р , то есть Р= ІРі, I l,L]
Каждому элементу ctr^A поставим в соответствие переход Іт ("процедура OLr ") сети. Множество переходов обозначим Т , то есть T={tr>r~Ljl) .
В соответствии с матрицей взаимосвязи процедур и информационных элементов соединяем дугами элементы множеств Р и Т , то есть устанавливаем взаимосвязи между элементами этих множеств. Элемент р, в.Р соединяется с элементом сг Т дугой ( р , 1Г ), если информационный элемент О.^ является входным элементом процедуры CLr и дугой ( с , Pi ), если он является выходным для процедуры (2Г . Поскольку информационный элемент ООД может являться входным для нескольких процедур обработки данных, то для восстановления маркерных точек состояния р. после срабатывания перехода і? необходимо также по-строить дуги ( іг , р, ) для таких і и Д , для которых существует дуга ( р , г ).
Функционирование сети Петри определяется в каждый момент времени расположением маркерных точек в вершинах-состояниях. Переход сг может сработать, если все его входные состояния р ЄР » Для которых существует дуга (А, *р )» имеют хотя бы по одному маркеру.
Определим исходную разметку построенной сети Петри. Те информационные элементы СОД, которые не являются выходными ни для одной процедуры данной СОД, называются входными информационными элементами СОД. Каждое состояние сети Петри, соответствующее входному информационному элементу СОД, пометим маркерной точкой. Полученный таким образом вектор М0 и будет исходной разметкой сети.
Таким образом, функционирование системы обработки данных может быть формализовано с помощью сети Петри, заданной набором х-(р,т^,н,Ю . їда Р-^А,А,...,А,..,Д} множество состояний сети (информационных элементов), J1 -it t ...t ...і У -множество переходов сети (процедур обработки данных) ,
I, если состояние рР связано с переходом F(p,l)-' ЬьТ- Дугой (/> , І ); [ 0, в противном случае ;
I, если переход t^T связан с состоянием реР дугой ( , р ); О, в противном случае ; исходная разметка сети. Введем следующие операции для сети N'« (Р, T,Ft Н М0) такие, что HCtJfKl-FCpf)) -1 такие, что f(jp {)= [ такие, что р(р I) =1 такие, 4?oH(t,p)(i-F(pyi))=l такие, что л 6 U f(i) r teT такие, что hCi)^h(Ж, Р) такие, что /Q?)=0 такие, что Лі)П/(ії*Р)фр. Операция I выделяет для заданного п р " переходы, имеющие направленные дуги в р и не имеющие направленных дуг из "р ". Операция 2 выделяет для заданного п " состояния, име- ющие направленные дуги в " і ". Операции 3 и 4 являются обратными по отношению к операциям I и 2. Операцией 5 выделяются все входные состояния сети Ж.
Операцией 6 выделяются все переходы, для которых входными элементами являются входные элементы сети J\f. Элементы этого множества назовем входными переходами сети Ж.
Операцией 7 выделяются выходные состояния сети Ж.
Операцией 8 выделяется множество .переходов, выходные состояния которых являются выходными состояниями сети Ж.
Рассмотрим пример использования этих операций для сети, изображенной на рис. І.З.І. fi(pL) =0, hcpj-fg, Л<й)-&}., (&>&}, Л(й)-{2,};
Таким образом, с помощью множества введенных операций выделяются входные, промежуточные и выходные состояния и множества переходов, которые преобразуют эти состояния.
Для формализации понятия модульности, анализа и синтеза оптимальных модульных СОД,, представленных в виде сетей Петри, введем понятие фрагментов переходов сети.
Пусть задана исходная сеть Петри Ж и некоторое подмно жество, переходов Тк= [ijci> ^fcj—i t-k } таких, ЧТ0 '****/' ' VJ*J'- Pi Л Ps h Ps
Рис. І.З.І. Представление системы обработки данных в виде сети Петри фрагментом переходов Вк сети Петри Jv для заданного множества переходов Тк назовем такую сеть Петри Вк=(Рк,Тк,
ГкЛкЛ^ Б К0ТРЙ
Д-и (f(i)uhcil) Fk(p,t)-F(p,i) №Тк-,\/рьРк ; Hk(p,lhH(i,p) №Tk,VptPh; Mak(p)-M0(p) VpePk.
Заданное множество. JJ. переходов, позволяющее однозначно построить некоторый фрагмент сети, назовем ядром фрагмента переходов Вк . Обозначим \(N, ід.) - операцию, позволяющую по заданному ядру Тг. построить фрагмент переходов В^ .Если, например, ядро фрагмента переходов BL содержит переходы {^ и i3 сети Петри, изображенной на рис. I.3.I, то фрагмент В± есть:
В^-ІР^Т^І^НіЛоі) О0-1-3-^- где
ЖдЛ)-*, Д<йЛ)-. ^i(A.''i)-o,
Я (ft. *.W, ^1 Сл. ii)-o, F(ps,is~)-o, Si(pJi)-i, Д^і.А)-і, #i(*i,A)-o, H^ttM-o, H&jJ-l. Щи.Рд-і,-M01CA) -1, Д* (A) = 0, 7W01C/>5) = 0.
Поскольку фрагмент переходов - это есть сеть Петри, то для нее справедливы все введенные ранее операции. Так как ядро фрагмента определено произвольным образом, то возможны случаи, когда некоторые переходы фрагмента переходов не срабатывают из-за не-
Рис. 1.3.2. Пример фрагмента переходов готовности их входных состояний, зависящих от работы других фрагментов переходов.
Множество переходов фрагмента переходов В^ , срабатывающих в последовательности переходов данного фрагмента переходов и состояния, связанные с переходами этого множества, назовем элементарным фрагментом переходов и будем обозначать ^*вк С«*-ТГ52Г).
Для моделирования состава, структуры и динамики функционирования информационных массивов введем понятие фрагментов состояний сети Петри.
Пусть в исходной сети Петри Ж выделено некоторое под множество состояний Pf=*{Pj , pf --',Р/ ] таких, что Рд+Р/і, ,Mj*jr Тогда фрагментом состояний A j. сети Петри Ж будем называть сеть Петри
Здесь % = U (k(p) и /(D)) * Функции инцидентности и начальная разметка фрагмента состояний Af определяются так же, как и для фрагментов переходов.
Фрагмент состояний Aj для заданной сети Петри Ж однозначно задается множеством А , которое назовем ядром фрагмента состояний А/
Таким образом, сеть Петри Ж= (P,T,F,H,M0)i моделирующая работу некоторой системы обработки данных, характеризуется множествами возможных фрагментов переходов, фрагментов состояний и множествами возможных последовательностей срабатывания переходов. Начальное состояние сети, как уже было сказано, задается начальной разметкой-вектором М0.
При срабатывании переходов сети начальная разметка изменяется. Пусть разметка Mj достижима от разметки Mi Тогда Mt ^Mj , то есть \/реР, M.t(p)
Чр k (ir) : F(p. ІГ) = Н (1г,р) = і.
Конечной разметкой М^ назовем такую разметку сети Петри, для которой: Mk(p) >0 Урє Р . Такая разметка соответствует окончанию функционирования сети или, на физическом уров-. не, окончанию обработки данных в системе и получению всех необходимых результатов.
Любой путь в rpaje достижимости, приводящий из исходной разметки к конечной называется возможным. Возможный путь, удовлетворяющий всем ограничениям на функционирование системы обработки данных и, -соответственно, на функционирование сети Петри, называется допустимым.
Определим тип сети Петри, построенной нами для моделирования работы систем обработки данных. При решении задач обработки данных каждая процедура выполняется один раз и поэтому переходы сети Петри срабатывают один раз. Каждый информационный элемент (состояние) является результатом работы одной процедуры (перехода). При начальном маркировании сети каждое ее входное состояние помечается только одним маркером, то есть VpP:M0(p)4,l.
Рассмотрим произвольное состояние сети р . Как было отмечено, изменение числа маркерных точек в состоянии р. , при срабатывании перехода І производится по следующему правилу: M.'(p)-M(p) + H(t,p)-F(p,i).
Если изменение разметки произошло при срабатывании перехода І}для которого состояние^ является входным (то естьГ(ру) = J.) то число маркерных точек в состоянии^? не изменится, так как в этом случае и Н(,р) = I по построению сети Петри. Если же состояниер является выходным для перехода Г , то число маркерных точек увеличится на единицу. Поскольку такой переход единственный для состояния^? и он срабатывает один раз, то
М. (р) ~ I. Если состояние р не связано с переходом t, то Щрі) = 0 и F(p,t)= О и, следовательно, Ж(у?) =М(р) Таким образом, построенная выше сеть Петри, моделирующая работу системы обработки данных, является безопасной.
Как было доказано, разметка сети, моделирующая работу СОД, при срабатывании переходов не уменьшается. Это означает, что если некоторый переход t г мог сработать при разметке Ж і , то он также сработает при разметке Mj , такой что М., ^»Ж/ Это позволяет построить упрощенный граф достижимости, с помощью которого проверяется, является ли построенная сеть Петри живой. Для этого достаточно выполнить следующую совокупность операций:
I. Определить начальную разметку сети, то есть построить вектор М0 , і =0 . -
2.-Если все координаты вектора Мі равны единице, перейти к 6, в противном случае к 3.
3. Определить множество переходов сети Т- , такое что і Ьц , если Vj>*fl(i):Mi(j>)>0.
4. Если Т[ = 0 , то перейти к 7, в противном случае к 5.
5. Ж±+1 =jM/ . Изменить разметку сети Mj+i следую щим образом:
Перейти к 2. -
Сеть Петри определяется как живая. Останов.
Сеть Петрине является живой. Останов.
Таким образом, при корректном выборе необходимых множеств процедур обработки данных и информационных элементов на этапе предпроектного анализа, сеть Петри, моделирующая данную ООД, будет правильной.
Введенные понятия фрагментов, разметки, путей на графе достижимости сетей Петри позволяют моделировать работу систем обработки данных в реальном масштабе времени, в том числе модульных СОД. Программному модулю СОД при этом соответствует ядро Тк фрагмента переходов Вк (Рк , Тк ,Fk,Hk,M.Qk) а внутренний и внешний интерфейс модуля Д, соответствует множеству _^ P=U(JG)Ufi(t)). UTkn
Внешним интерфейсом модуля Bfc будет множество состояний Pk-h(BkPk)UHBk,?h).
Информационному массиву СОД соответствует ядро фрагмента со стояний Aj- CPf ,Tf,Fj,Н/,М0/).
Таким образом, язык сетей Петри, позволяет формализовать понятия программных модулей и информационных, массивов СОД и взаимосвязи между ними, то есть построить модель СОД, используемую для постановки и решения задач анализа и синтеза оптимальных модульных систем обработки данных.
КРАТКИЕ ВЫВОДЫ
В главе I получены следующие основные результаты.
Проведен анализ моделей и методов синтеза оптимальных модульных систем обработки данных. Обоснована целесообразность использования сетей Петри для анализа и синтеза оптимальных модульных СОД.
Разработана-модель системы обработки данных с использованием сети Петри, переходы которой соответствуют процедурам обработки данных, а состояния - информационным элементам. Модель позволяет учитывать при синтезе СОД динамику функционирования программных модулей и их взаимодействия с информационными массивами. Введены необходимые теоретико-множественные операции над элементами сети Петри, позволяющие выделить множества элементов СОД с заданными свойствами.
3. Разработаны модели программных модулей и информационных массивов, которые являются ядрами фрагментов переходов и фрагментов состояний. Для введенных моделей определены понятия внутреннего и внешнего интерфейса, необходимые для синтеза оптимального состава программных модулей и информационных массивов (ЯД. [::.:1-:.7^ есер : кспіП It. Язпннз;
. Синтез оптимальных модульных систем обработки данных (обзор)
Оэздание и развитие ЭВМ позволило приступить к эффективному решению больших и сложных задач вычислительного характера. Однако в дальнейшем основной сферой применения электронных вычислительных машин стали невычислительные задачи, в которых над элементами обрабатываемой информации или вовсе не выполняются никакие арифметические действия, или же их доля относительно невелика/42, 18/. Основное внимание в таких задачах уделяется вводу - выводу больших информационных массивов, поиску в них нужных сведений и так далее. О размерах информационных массивов современных систем обработки данных можно судить по АСУ "Прибор" /23/, годовой объем входной информации которой составляет более 350 млн. знаков фоки создания АСУ крупными министерствами и ведомствами составляет 8-Ю лет, стоимость разработки - от 5 до 30 млн. руб., трудоемкость - от 500 до 1500 человеко-лет /7/. Потребности в программном обеспечении растут значительно быстрее (22$ в год), чем возможности их разработки, которые увеличиваются примерно на 15% в год /54, 57/. В последние годы разработка АСУ связывается прежде всего с построением модульных систем обработки данных, поскольку при разработке модульных СОД затраты сокращаются на 20-25$ по сравнению с индивидуальным проектированием. Еще больший эффект достигается при проектировании типовых модульных СОД: затраты и время проектирования уменьшаются в 2-3"раза /5, 32, 57/.
Необходимость развития модульного принципа проектирования определяется также интенсивными разработками в области построения САПР АСУ, так как модульный принцип проектирования программных модулей является основным при создании и- расширении банка проектных решений (БПИ) САПЕ АСУ. Основная компонента этой базы - модуль-замкнутый функционально программный элемент, имеющий развитую систему описаний /53/.
В настоящее время используются две основные стратегии мо--дульного проектирования: "сверху - вниз" и "снизу - вверх" /б, 51, 59, 61/. Основным понятием при модульном проектировании является понятие модуля системы обработки данных. Наиболее распространенными неформальными определениями являются: "модуль есть поименованное множество программных инструкций или макрокоманд" /62/, "модуль - это целевая структуризация программного обеспечения" /63/, В определении, данном в /65/ выделены две основные характеристики модуля: мощность, то есть количество процедур обработки данных, которые он может реализовать и связность его с другими модулями системы. В /10, 26/ приведено формальное определение многофункционального"модуля СОД, основанного на понятии информационных элементов и процедур обработки данных и используемое в предлагаемой работе.
Модульный принцип проектирования систем обработки данных связан с разбиением системы на отдельные слабо связанные компоненты, допускающие относительно независимую разработку и использование. Система является модульной, если она состоит из некоторого множества частей или модулей, имеющих интерфейс, определенный таким образом, что каждый модуль не имеет информации о внутреннем содержании других модулей, кроме той, которая содержится в спецификациях интерфейса /15/.
Преимущества модульного принципа проектирования заключаются в повышений качества проектирования, облегчении программирования и отладки модулей, а также модернизации существующих систем.Существуют различные способы разбиения информационного и программного обеспечения СОД на модули: функциональной; по числу информационных и управляющих связей между модулями; по имеющимся возможностям технического и программного обеспечения ; по использованию типовых стандартных элементов и решений; смешанные способы /24/.
Оптимальное проектирование модульных СОД - многоэтапный процесс принятия строго обоснованных и оптимальных решений в процессе анализа систем, проектирования, отладки и внедрения новой системы. Последовательность основных этапов разработки систем обработки данных приведена на рис. I.I.I.На этапе предпроектного анализа СОД /2, 20, 24/ проводится ряд работ, наиболее важной из которой является определение необходимого набора процедур, реализующих заданные функции, а также необходимой для их решения информации.
На этапе технического проектирования осуществляется синтез оптимальной модульной СОД, под которым понимается определение оптимального состава и числа модулей системы, а также содержания и методов организации информационного обеспечения. Полученные решения уточняются и доводятся до программной реализации на стадии рабочего проектирования.
Анализ информационной производительности как целевой функции задач синтеза оптимальных модульных СОД
Проанализируем изменение І в зависимости от изменения - 47 вероятности запросов при заданных значениях энтропии наборов состояний и времени их получения. При этом определим такие значения вероятностей запросов, при которых функция (2.1.5) принимает максимальное значение. Вероятности Чі Чг -- 9V удовлетворяют ограничениям (2.1.2) и (2.1.3). Максимизация функции (2.1.5) соответствует минимизации функции Данная функция нелинейна и дифференцируема. Найдем ее минимум при ограничении (2.1.2) методом неопределенных множителей Лаг-ранжа и покажем, что найденный минимум удовлетворяет также и ограничениям (2.1.3). Составим функцию Лагранжа: Найдем частные производные и приравняем их нулю: Для определения вероятностей, при которых минимизируется функция (2.2.1), необходимо найти Ограничение (2.1.2) с учетом (2.2.6) имеет вид: И»і (2.2.7) Данное уравнение имеет единственное положительное решение от-носительно , так как все оС„ 0 2 w 0 и поэтому oL Н &)()= s 2 W есть возрастающая функция с областью значений »-1 [О; + сто С , Единственное решение уравнения (2.2.7) можно получить любым приближенным методом. Все вероятности запросов положительны, и, следовательно, удовлетворяют ограничению (2.1.3). Таким образом, среди всех внутренних точек допустимого множества (2.1.2)-(2.1.3) области определения функции (2.2.4) имеется единственная стационарная точка, координаты которой"вычисляются по формуле (2.2.6). Обозначим эту точку через покажем, что в любой стационарной граничной точке допустимого множества значение целевой функции (2.2.1) будет больше, чем в точке С/ Значение функции (2.2.1) в точке Q равно iogz ? . Точки любой грани допустимого множества есть Ц -мерные вектора, у которых хотя бы одна координата равна нулю. Пусть решение уравнения ZJ Ч СЪ і для точки G есть С, , а для произвольной стационарной точки « грани допустимого множества - . Тогда Q , так как есть решение уравнения без некоторых положительных слагаемых. Но тогда log 5 Log q, , то есть с учетом введенного обозначения (2.2.5) получим, что значение функции (2.2.1) в стационарной точке любой грани допустимого множества больше, чем в точ-ке и . . Покажем, что значение целевой функции в любой крайней точке допустимого множества больше, чем значение целевой функции в стационарной точке грани. Рассмотрим для определенности угловую точку (?= 0,0,— 0Л В ней значение целевой функции (2.2.1) равно ( у ). Тогда нам нужно показать, что
Так как функция G)()= 4 2 w возрастающая и (С (с, ) і , то остается показать, что Последнее неравенство является истинным, поскольку левая часть есть сумма положительных величин. Таким образом, в любой стационарной точке грани и крайних точках допустимого множества области определения функции (2.2.1) значение функции больше, чем в единственной стационарной внутренней точке Q. . Это и является доказательством того, что точка Q является точкой глобального минимума для функции (2.2.1) и точкой глобального максимума для функции (2.1.5) на множестве (2.1.2)-(2.1.3). Для систем, работающих в справочном режиме без оперативного обновления хранящейся информации значения наборов состояний не изменяются, то есть.. HZo=Of V Ь) = і ,W . Для них выра жение 1\ имеет вид: s W Максимальное значение этой функции на множестве (2.1.2)-(2.1.3) достигается в точке Q ( i , 2»—» F/ Рассмотрим зависимость информационной производительности от времени получения наборов состояний. Пусть это время постоянно для всех 1,2 , » W » то есть du=dQ Уы = i}W . Такое распределение времени выборки соответствует основным способам размещения информации на магнит ных дисках. Из (2.2.9) следует что и вероятности запросов по стоянны и равны t Информационная производительность системы в этом случае равна При фиксированном W информационная производительность системы обработки данных будет обратно пропорциональна с 0 , то есть система обработки данных будет работать тем производительней, чем меньше время получения наборов состояний 0jy Зависимость информационной производительности от времени oQ при различных значениях W представлена на рис. 2.2.1. Пусть время получения набора состояний зависит от его номера следующим образом: du- ilogta + 6 . Такое распределение времени выборки соответствует некоторым способам размещения информации на магнитной ленте и номер Ь) является порядковым номером расположения набора состояний. На рис. 2.2.2 показана зависимость времени получения наборов состояний от номера набора состояний для случаев ; і На рис. 2.2.3 и 2.2.4 показана зависимость информационной производительности системы от О при заданных d и от О. при заданных Ь для 10 наборов состояний. Анализ этих графиков подтверждает общеизвестные положения теории информации об условиях достижения максимальной информационной производительности системы, а также показывает, что максимальная производительность СОД при прочих равных условиях достигается при использовании магнитных дисков. Как было показано выше, информационная производительность проектируемой системы обработки данных принимает свое максималь-ное значение вvточке U координаты которой вычисляются по формуле (2.2.6). При изменении вероятностей запросов наборов информационных элементов значение информационной производительности уменьшается. Представляет интерес определение множества наборов вероятностей запросов, на котором значение информационной производительности не менее заданного. Для трехмерного сличая эта задача может быть решена графически. Для этого достаточно построить линии уровня, то есть определить множество значений вероятностей запросов, при которых значение информационной производительности равно заданному значению. На рис. 2.2.5-2.2.7 изображены линии уровня систем обработки данных, характеристики которых приведены в таблице 2.2.1. Линии уровня для систем 1-3 построены с шагом 0,005 бит/мин.
. Особенности разработки СОД, реализуемых на базе мультипроцессорных вычислительных систем
В последние годы большое распространение получили мультипроцессорные вычислительные системы (ВС). Это объясняется многими причинами, основной из которых является необходимость значительного увеличения производительности и надежности средств обработки данных. Введение, например, второго процессора приводит к увеличению производительности вычислительной системы на 60-80$, а добавление третьего процессора дополнительно увеличивает производительность на 30-50$ /35/. Надежность двухпроцессорной вычислительной системы повышается на порядок, а при трех процессорах наработка на отказ превышает эту же характеристику однопроцессорной системы на два-три порядка /21/. Указанные преимущества мультипроцессорных систем являются весьма существенными при решении большинства задач обработки данных, так как такие задачи оперируют с большим объемом информации и предъявляют повышенные требования к быстродействию и надежности ЭВМ.
Существующие мультипроцессорные системы можно условно разделить на шесть классов: ВС с соподчинением, ВС с машиной-диспетчером, однородная ВС, дуплексная ВС, ВС с перестраиваемой структурой, высокопараллельная ВС /34/. В настоящее время наиболее широкое применение получили однородные вычислительные системы /8, 9, 34, 38, 55/. Такая система содержит несколько однотипных вычислительных модулей, модулей оперативной памяти и управления внешними устройствами. Однородная вычислительная система может иметь различную конфи -90-гурацию оборудования, минимальный комплект которого содержит по одному модулю каждого типа. Наличие однотипного оборудования позволяет использовать единое математическое обеспечение. Надежность работы такой системы высока, так как все процессоры взаимозаменяемы и при неполадках в работе одного процессора, выполнение программного модуля может продолжить другой процессор. В таких системах упрощен принцип распределения работ. Каждый свободный процессор обращается к очередному программному модулю, готовому к выполнению. Таким образом устраняются про -стой процессоров ЭВМ. Дальнейшим развитием однородных вычислительных систем является разработка многопроцессорных вычислительных систем с перестраиваемой структурой /33, 38, 39/. Такал система включает в себя однородный параллельный процессор (ОПП), ассоциативный параллельный процессор (АПП) и процессор операционной системы. Оперативная память системы имеет модульную структуру. Число и типы одновременно работающих процессоров и процессорных элементов определяются требованиями решаемых задач.
Помимо традиционных уровней управления вычислительным процессом - управление задачами и командами - в многопроцессорных вычислительных системах с перестраиваемой структурой реализуются два дополнительных уровня управления: управление ветвями задачи и управление операторами. Управление ветвями осуществляется в динамике и сводится к выполнению следующих функций: объявление ветвей; выборка их из очереди; закрепление управляющих ресурсов за ветвями; освобождение ресурсов по окончании ветви.
Распределение ресурсов между задачами выполняется процессором операционной системы. При этом число процессорных элементов, предоставляемых задаче, зависит от наличия готовых к выполнению ветвей задачи в текущий момент времени.
Разбиение задачи на ветви, которые могут выполняться параллельно при удовлетворении условий логической подчиненности ветвей, проводится на этапе проектирования программных модулей и реализуется в процессе их трансляции. Основные преимущества многопроцессорных вычислительных систем с перестраиваемой структурой состоят в значительном повышении надежности функционирования систем и увеличении быстродействия С ДО ЮО млн. опер ./сек). Мультипроцессорные вычислительные системы используют два способа разделения между процессорами оперативной памяти: жесткое и свободное /34/. При первом способе за каждым процессором закрепляется по нескольку модулей памяти. Обмен информацией в этом случае осуществляется либо через буферную память, либо через канал связи. Такое распределение памяти применяется при объединении серийных ЭВМ в мультипроцессорную вычислительную систему. К его преимуществам можно отнести простоту связи между процессорами и модулями памяти. Примерами таких систем являются модели-158 и 168 системы 370 фирмы IBM , а также вычислительный комплекс групповой обработки данных ПС 2000 /37/.
При втором способе распределения оперативной памяти все модули памяти являются общими, то есть каждый из процессоров может обратиться к любому модулю памяти. К основным преимуществам такого распределения памяти можно отнести экономное использование памяти и возможность выполнения программных модулей, требующих для своего выполнения значительного объема оперативной памяти. Примерами таких систем являются мультипроцессорные вычислительные-системы В - 825, В6700 фирмы DURROU"GHS CORPORATION , а также, отечественные: центральный вычислительный комплекс (ПС - 3000), выполненный на конструктивной базе СМ ЭВМ и ЭВМ EC-I045, EG-I055 и EC-I065. Так первые две отечественные ЭВМ имеют средства для организации двухпроцессорных систем, a EC-I065 разработана как многопроцессорная ЭВМ с общей памятью (число процессоров от двух до четырех). Как мультипроцессорные вычислительные системы проектируются будущие модели ЕС ЭВМ ЛІ/.
Эффективность использования мультипроцессорных вычислительных систем в значительной степени зависит от структуры решаемых задач и способности аппаратного и программного обеспечения систем к организации параллельного вычислительного процесса. Параллельный вычислительный процесс обработки данных заключается в одновременном выполнении нескольких независимых ветвей одного программного модуля или одновременном выполнении полностью независимых программных модулей на нескольких процессорах.
Скнтез программных модулей и информационных массивов задач обработки данных должен проводиться на этапе технического проектирования с учетом возможности- организации параллельного вычислительного процесса. Исходными данными при этом являются множество процедур обработки данных, множество информационных элементов, взаимосвязи между элементами этих множеств, структура и количество процессоров вычислительной системы. Необходимо синтезировать программные модули и информационные массивы таким образом, чтобы максимально использовались вычислительные возможности мультипроцессорной вычислительной системы заданной структуры. Целевая функция при этом должна достигать своего экстремального значения с учетом ряда технологических ограничений.
Синтез оптимального состава модулей программного обеспечения систем обработки данных
При проектировании систем обработки данных большое значение имеет задача оптимального выбора состава программных модулей и последовательности выполнения процедур обработки данных, определяющей последовательность выполнения программных модулей. Рассмотрим постановку и решение задачи синтеза состава модулей программного обеспечения и последовательности реализации процедур при заданном информационном обеспечении системы, которая является частной задачей общей задачи синтеза модульных СОД. На языке сетей Петри задача формулируется следующим образом: выбрать непересекающиеся фрагменты переходов сети Петри, удовлетворяющие всем ограничениям задачи и найти такую последо - 132 вательность срабатывания переходов, при которой минимизируется общее время обмена с внешней памятью ЭВМ, то есть необходимо минимизировать целевую функцию R-l R К R при ограничениях (2.3.4), (2.3.6) - (2.3.8), (2.3.3) и дополнительных ограничениях: - число переходов в каждом фрагменте переходов не более заданно го: R XTt Me , k-lX , (. т_. Г=1 (4.1.2) - интерфейс между отдельным Модулем и системой не более заданно К S \РкъРк \ М9 9 k-i,ic . k -l (4.1.3) - межмодульный интерфейс системы ограничен: где Тср - среднее время обращения к заданным информационным массивам, размещенным во внешней памяти ЭВМ. Данная задача относится к классу дискретных задач с булевыми переменными. Алгоритм ее решения основан на сокращенном переборе вариантов решения, иптимальное множество фрагментов переходов будем находить последовательно следующим образом: на к -м шаге определяем фрагменты переходов, каждый из которых может являться к. -м фрагментом переходов в разбиении. Сокращение числа рассматриваемых на каждом шаге фрагментов переходов осноано на.следующем утверждении:
Тогда, если существует оптимальное множество фрагментов, содержащее фрагмент переходов В то существует и оптимальное множество фрагментов, содержащих фрагмент переходов Bfc . Доказательство. В соответствии с условием "а" рассматриваются только те переходы, у которых все входные и выходные состояния входят в исходный фрагмент переходов 2. . В соответствии с условием "б" каждое входное состояние рассматриваемого перехода ір должно быть либо входным состоянием сети, либо выходным состоянием одного из переходов фрагмента переходов В Ф Согласно условию "в" среди входных состояний перехода іг найдутся состояния, являющиеся выходными состояниями фрагмента переходов Д Пусть Ki {.BijBz, ..., &К.І - оптимальное множество фрагментов переходов. Пусть для определенности переход lf G Т% Построим фрагменты переходов следующим образом: Полученное множество фрагментов переходов Rz=:lBi,Bz,...,3} допустимо. В соответствии с условием "а" для каждого фрагмента переходов Bfc (k L,K) : Pk Р % Поэтому интерфейс каждого фрагмента переходов В с остальными фрагментами множества Rz (левая часть неравенства (4.1.3)) не увеличился, а, следовательно, не увеличился и интерфейс между фрагментами переходов. Покажем теперь, что R - оптимальное множество фрагментов переходов. Для того, чтобы доказать, что Rz оптимально, необходи-мо найти последовательность СО = С1Р, сг ...)и. показать, что количество элементарных .фрагментов в ней не больше числа элементарных фрагментов в последовательности со . Для этого необхо-димо показать, что разметка в последовательности Со перед срабатыванием переходов не меньше, чем соответствующая разметка в последовательности СО, так как в противном случае переход г не мог бы сработать д -мв последовательности & Построим последовательность Перенумеруем переходы со s /v / У „ Л Покажем, что все переходы i p. могут сработать в после довательности- СО , Переходы lr г/ , - сработают, так как они являются подпоследовательностью СО, Переход гт.+і Ігп сработает по построению. Переходы Гт+г, , го сработают, так как і г 1п не меньше, чем соответствующая разметка в по следовательности со , А так как переходы в последовательности со срабатывают, то эти переходы будут срабатывать и в последовательности со , Переход /р 6 2д.- так как одно из его состояний является входным состоянием перехода іс (по условию "б" и "в" утверждения). Поэтому количество элементарных фраг-ментов в фрагменте переходов Д, и в остальных фрагментах не увеличилось, поскольку разметка состояний в СО не уменьшилась. Следовательно, множество фрагментов переходов Rz является также оптимальным.
