Методы формализованного описания структур вычислительных систем
1.3. Методы формализованного описания структур вычислительных систем
Целью формализованного описания структур ВС является представление имеющихся данных и параллельных процессов в виде специальных формальных объектов, удобных для проведения над ними вычислительных и имитационных экспериментов на ЭВМ. Поэтому выбор формализованного языка, в наибольшей степени учитывающего особенности параллельных ВС, является основной задачей начального этапа проектирования. Решение таких задач связано с применением специальных методов построения синхронных и асинхронных моделей дискретных систем. Среди этих методов наибольшую известность получили методы алгоритмизации систем массового обслуживания [9], автоматного и агрегативного моделирования [8,9,20], расширения известных языков программирования [4,19,63], структурные нотации [48], сетевой и алгебраический подходы [56,72,74], графовые модели [1,11,26,38,44,46,48].
Подход, предложенный в работах [8,9] для формализации анализа сложной системы и состоящий из трех шагов: структуризации объекта, формализации элементов сложной системы и взаимодействия между этими объектами, обладает существенным недостатком. Данный недостаток заключается в том, что такая формализация элементов системы и взаимодействия между ними обладает "неформульным" заданием схемы сопряжения (в виде рисунков) и операторов сопряжения (в виде таблиц). Подобная формализация не предоставляет возможности формализовать область эквивалентных структурных преобразований схемы сопряжения. Этих недостатков лишена формализация элементов сложной системы и взаимодействия между ними с помощью так называемых R-модулей [21], которые используются не только при описании детерминированных динамических систем, функционирующих в дискретном времени, но и при описании стохастических систем, представляемых вероятностными автоматами. Однако подобные автоматные модели не перекрывают все возникающие задачи.
Использование параллельных языков программирования и структурных нотаций для формализованного описания структур ВС эффективно лишь для анализа одной структуры ВС, так как данные описания громоздки и не приспособлены для поддержки процедур синтеза новых структур ВС. Если ВС рассматривать только как множество взаимодействующих функциональных блоков (объектов), а не как вычислительную сеть или многопроцессорную систему, то для исследования процессов, протекающих в ВС, может быть использован сетевой подход [72,74]. В работе [56] для описания параллельных процессов с синхронизацией были предложены OS-сети. Потребляемые ресурсы в этой модели явно не задаются, механизмы для описания повторно используемых ресурсов - самые простые. Предложенные OS-сети применяются, в основном, для анализа тупиковых ситуаций, которые могут возникнуть в параллельных ВС.
Эффективным средством анализа и синтеза параллельных ВС и процессов является алгебраический подход [56,72], который основан на формульном выражении сетевых моделей. Использование алгебраического подхода позволяет аналитическими методами путем проведения эквивалентных преобразований формул получать оптимальные структуры ВС. Недостатками данного подхода являются, во-первых, ограниченность - не все сетевые структуры могут быть описаны алгебраически; во-вторых, сложность.
В последнее время во многих работах отмечается, что графовые модели являются наиболее удобными и эффективными средствами описания и исследования параллельных структур и процессов [1,11,38]. К настоящему времени существует несколько формализмов, основанных на графовых моделях и служащих для описания параллельных процессов. Наиболее общими из них являются схемы параллельных программ Карпа-Милнера, A-программы Котова-Нариньяни, билогические графы, вычислительные модели, операторы Хоара [1].
К концу 70-х годов указанные модели были практически вытеснены сетями Петри (СП) [26,46] - формализмом, описывающим структуру и взаимодействие параллельных процессов. Широкое распространение СП обусловлено рядом преимуществ, среди которых можно выделить следующие:
1. СП позволяют моделировать асинхронность и недетерминизм параллельных независимых процессов, параллелизм конвейерного типа, конфликтные взаимодействия между процессами.
2. СП включают в себя возможности ряда других моделей, предложенных для описания и исследования параллельных ВС (семафоры Дейкстры, системы векторного сложения, вычислительные сети, сетевые структуры, модели повторно используемых ресурсов и др.).
Рекомендуемые материалы
3. СП, расширенные такими обобщениями, как ингибиторные дуги, приоритетность и время срабатывания переходов, цветные метки и др., позволяют моделировать сложные ВС с учетом таких факторов, как приоритетность процессов, временные параметры событий, совместное отображение структуры управления и потоков данных.
4. В отличие от других формализмов (таких, как А-программы, схемы Карпа-Милнера и др.) СП допускают произвольную интерпретацию элементов модели как в смысле выполняемого фрагмента (выражения, операторы, подпрограммы, аппаратные преобразования информации), так и по уровню абстракции. Это позволяет с помощью СП производить иерархическое построение аппаратных и программных модулей ВС.
5. СП позволяют эффективно представлять знания в экспертных системах (ЭС). Современные языки программирования имеют существенные ограничения, которые связаны с выполнением действий в определенном порядке. Исследования в этой области, направленные на устранение указанного ограничения путем ввода новых примитивов, привели к использованию СП. Между СП и представлением знаний в ЭС существует глубокая связь. В частности, предикатные СП являются продукционными системами, основанными на логике первого порядка. Кроме того, модульность системы правил является существенным показателем производительности ЭС. С этой точки зрения СП имеют преимущества, так как активизация правил, представленных в терминах СП, происходит ассоциативным образом, а не в порядке, строго заданном процедурой.
6. СП, обладая однородностью и аналитическими зависимостями, которые описывают функционирование переходов, удовлетворяют необходимым условиям для использования в тензорной методологии.
7. Для СП, которые являются двудольным ориентированным динамическим помеченным мультиграфом, справедливы все положения теории графов.
При исследовании параллельных ВС в качестве базовой информации используются данные о взаимосвязи событий в системе. Данные о моментах времени наступления событий, интервалах реализации, тактированных временных шкалах, как правило, не используются. Причинно-следственная связь событий в асинхронных системах, к которым относятся параллельные ВС, задается множеством отношений вида "условия-события". Построение полной структуры таких отношений для ВС - задача сложная. Однако использование структурированной информации о предметной области моделирования позволяет существенно упростить эту работу. В настоящее время выделяют два подхода к описанию семантики параллельных систем. Первый подход опирается на понятие последовательности действий (О-последовательности), второй - основывается на понятии процесса. В то время как первый подход более удовлетворяет практическим целям, во втором подходе параллельность представляется более "правильным" образом. Теория СП предоставляет аппарат, который позволяет при описании модели учесть преимущества обоих подходов.
Построение моделей ВС в терминах СП включает следующие действия.
1. Моделируемые процессы, протекающие в ВС, описываются множеством событий и условий, которыми эти события определяются, а также причинно-следственными отношениями, устанавливаемыми на множестве "события-условия".
2. Определяются события, последовательность наступления которых управляется состояниями системы. Состояние системы задается множеством условий. Условия формулируются в виде предикатов.
3. Условия (предикаты) могут выполняться и не выполняться. Только выполнение условий обеспечивает возможность наступления событий.
4. После того как событие наступило, будет обеспечено выполнение других условий, находящихся с ранее выполненными условиями в причинно-следственной связи.
В СП условие - это позиции, а события - это переходы. Последовательности событий отображаются срабатыванием переходов. Выполнение какого-либо условия связано с появлением метки в соответствующей этому условию позиции. Соглашение о правилах срабатывания переходов является способом выражения концепции причинно-следственных связей между условиями и событиями в системе. Момент фактической реализации события неизвестен, поскольку иногда бывает трудно восстановить полные цепи непосредственных причин и следствий, определяющих факт и время наступления события.
Поясним некоторые варианты применения математического аппарата СП для получения общих качественных оценок событий и процессов в параллельных ВС.
1. СП могут иметь позиции, число меток в которых растет неограниченно. Свойство ограниченности сетей связано с введением ограничений на число меток в позициях. Если, например, интерпретировать метки данными в сетях обмена информацией, а некоторые позиции буферами или регистрами, то ограниченность СП будет естественным условием, проверка выполнимости которого позволит выяснить, возможно ли в данной сети переполнение буфера, вместимость которого ограничена.
2. В СП возможны такие ситуации, когда ни при каких изменениях в сети не выполняются условия активизации некоторых переходов. Эти переходы оказываются как бы лишними и могут быть исключены из СП без всякого ущерба для ее функционирования.
Может случиться также, что после реализации в сети определенной последовательности срабатываний переходов возникает такая разметка позиций, при которой некоторые переходы никогда больше не сработают ни при каких получаемых в дальнейшем разметках. Такие ситуации соответствуют тупиковым событиям в моделируемой системе. Выявление тупиковых разметок связано с анализом живости СП.
3. СП являются эффективным аппаратом для анализа состояний в параллельных ВС. Например, при необходимости установить возможность или невозможность некоторого состояния в ВС можно использовать процедуры анализа СП на достижимость. Проверяемая ситуация в СП задается некоторой разметкой. Исследование заключается в проверке достижимости этой разметки от некоторой исходной разметки.
4. Важным направлением формального анализа СП является возможность их исследования по частям. Исходная сеть разбивается на фрагменты, каждый из которых исследуется независимо, а затем проводится анализ свойств целостной СП, в которой каждый фрагмент замещается отдельным переходом или позицией (иерархическим фрагментом).
5. Интересным расширением СП являются так называемые временные СП. Позиции или переходы во временных СП взвешиваются "временем выполнения". Метка при попадании в позицию или "захваченная" взвешенным переходом становится недоступной для возбуждения соответствующего перехода в течение "времени выполнения".
Если Вам понравилась эта лекция, то понравится и эта - Художественный комплекс первобытной культуры.
Применение временных СП связано с анализом периодических режимов функционирования систем. Используя формальный аппарат временных сетей, можно найти необходимые, а в некоторых случаях и достаточные условия выполнения в системе циклических процессов, протекающих с некоторой заданной скоростью, а также определить режимы работы ВС с максимально возможной скоростью.
На основе проведенного исследования проблем анализа и синтеза структур параллельных ВС можно сделать следующие выводы.
1. Большинство современных вычислительных структур характеризуются такими свойствами, как параллелизм, недетерминированность, многоуровневость представления, сочетание синхронных и асинхронных процессов, однородность и др. Эффективное решение задач на таких структурах должно обязательно сопровождаться согласованием структуры численных методов и архитектуры ВС.
2. При решении проблемы синтеза эффективных вычислительных структур основополагающим вопросом является выбор математического фундамента, на котором может строиться изучение таких разнородных компонент, как численные методы, алгоритмы, структуры ВС и их математические модели. В качестве подобного математического фундамента предлагается использовать тензорное исчисление.
3. Из проведенного анализа следует, что реализация современных проектов ВС должна вестись при поддержке эффективных средств автоматизации проектирования, моделирования и верификации. В силу NP-сложности задач синтеза альтернативных вариантов проектируемой ВС автоматизация структурного и параметрического синтеза является трудно реализуемой даже с использованием САПР, реализованных на высокопроизводительных ЭВМ. Поэтому большинство из существующих подходов к решению данной задачи носит эвристический характер и предусматривает включение в контур машинного проектирования человека. На основе этого можно заключить, что современные САПР параллельных ВС должны иметь интеллектуальную составляющую.
4. Анализ методов формализованного описания современных структур ВС и их особенностей позволил остановиться на аппарате СП, который в рамках единого формализма не только дает возможность описывать указанные разнообразные объекты, но, кроме того, предоставляет развитые методы анализа параллельных процессов и, обладая однородностью и аналитическими зависимостями, удовлетворяет условиям для использования в тензорной методологии.
