Автоматные сети и реализация автоматных функций

 

 

 

 

 

 

 

 

Реферат

 

на тему:

 

«Автоматные сети и реализация автоматных функций»

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2010г.

СОДЕРЖАНИЕ

Введение

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

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

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

Цель работы состоит в изучении автоматных сетей и  реализации автоматных функций

Для достижения поставленной цели следует решить ряд поставленных задач:

• рассмотреть теорию автоматов;
• изучить автоматную модель;
• ознакомиться с сетями Петри;
• наглядно рассмотреть реализацию автоматных функций.

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

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

ГЛАВА 1.ТЕОРИЯ АВТОМАТОВ

1.1.Произвольный автомат.

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

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

Зададим следующие множества:

A={a1,a2,...,am} - множество входных знаков (входной алфавит),

B={b1,b2,...,bs} - множество выходных знаков (выходной алфавит),

Q={q1,q2,...,qn} - множество состояний автомата.

Особенность этих множеств состоит в том, что они содержат конечное число элементов.

Тогда автомат можно  представить в следующем виде:

Начальная установка

Особенностью автоматов  является то, что они функционируют  во времени.

Работу любого автомата можно проиллюстрировать с помощью временных диаграмм (приложение 1).

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

Существует три подхода  к изучению автоматов:

1. Макроподход. При макроподходе изучают внешнее поведение автомата, то есть то, как автомат перерабатывает входные данные  и в каких состояниях находиться, абстрагируясь от внутренней структуры автомата. Такие автоматы называются – Абстрактными автоматами.
2. Микроподход. При микроподходе учитывается структура автомата, его составные части, их функционирование и связь между собой. Такие автоматы называются – структурными автоматами.
3. Практический или практический аспект. При практическом подходе учитывается не только внешнее поведение элементарных (абстрактных) автоматов, но и особенности их реализации в виде материальных объектов (дискретных устройств).

1.2. Автоматная  модель процесса

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

Заметим, что с введением  времени модель приобретает еще  одно качество реальных процессов – инерционность. В реальных процессах нет мгновенных действий. Задержке реакции реального объекта на входное воздействие в автоматной модели соответствует один или несколько дискретных тактов.

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

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

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

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

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

1.3. Практическое  приложение автоматных моделей

В программировании применение автоматов не является экзотикой. Наиболее известная область приложения автоматных моделей – проектирование компиляторов. В области проектирования систем весьма популярна автоматная модель языка UML

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

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

ГЛАВА 2.СЕТИ ПЕТРИ

2.1. Знакомство  с сетями Петри

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

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

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

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

2.2. Функционирование  сети Петри

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

Из всего множества  разрешенных переходов сработать  может любой.

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

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

В случае, когда позиция  является входной для двух или более разрешенных переходов, срабатывание любого из них и соответствующее уменьшение количества фишек в ней может запретить другие переходы. Такой ситуацией моделируются конфликты, когда для выполнения нескольких операций требуется использование общего ресурса. Пример такой ситуации виден в приложении 2. В самом начале работы сети разрешенным является один переход – t1. После его первого срабатывания разрешенными являются все три перехода сети. Если же теперь сработает, к примеру, переход t2, он запретит переход t3, и наоборот, срабатывание t3 запретит переход t2, поскольку переходы t2 и t3 имеют общую входную позицию p3.

Срабатывание простого перехода считается мгновенным.

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

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