BC/NW 2012; №2 (21):2.3

 

ЗАДАЧА АНАЛИЗА РЕАЛИЗУЕМОСТИ АСИНХРОННЫХ АВТОМАТНЫХ СХЕМ С РЕГУЛЯРНЫМИ КОМПОНЕНТАМИ

 

Калинина Г.А., Мороховец Ю.Е.

 

Термин «реализуемость» широко используется в работах по computer science, статьях и книгах относящихся к IT-области. «Реализуемость формул языка», «вычислительная реализуемость алгоритмов», «реализуемость моделей обработки данных», «аппаратная реализуемость систем команд», «реализуемость IT-проектов» – все это примеры контекстов, в которых применяется рассматриваемый нами термин, причем применяется в различных смыслах. В данной работе семантика термина «реализуемость» близка к той, что используется в [1], где соответствующее понятие вводится для потоковых моделей программ, представимых формально определенными M-сетями. Для этого класса моделей наличие свойства реализуемости обеспечивает однозначность результата вычислений и их результативность. Ниже понятие реализуемости вводится для класса автоматных моделей (автоматных схем), описывающих не процессы вычислений, а потенциально бесконечные во времени процессы обработки данных, связанные с непрерывным приемом, преобразованием, накоплением и выдачей информации. В этом случае вопрос об однозначности результатов не ставится. Существенным является лишь отсутствие возможностей блокировки работы схем, приводящей к не обусловленному извне прекращению процессов обработки данных.

 В [2, 3] введено понятие асинхронной автоматной схемы непрерывного действия (далее ААС НД) и даны базовые определения, связанные с реализуемостью схем этого класса. Отмечено, что в общем случае задача анализа реализуемости ААС НД не имеет строгого решения, но что такое решение может быть получено для схем с более просто организованными компонентами – компонентами регулярного вида.

Для определения компонентов регулярного вида проведем специализацию компонентов общего вида, названных в [3] свободными компонентами. Можно выделить два уровня специализации. Первый уровень соответствует тому случаю, когда поведение компонентов ААС НД не зависит от ситуаций, возникающих на их входах – уровень детерминированных компонентов. Второй уровень предполагает, что поведение компонентов не зависит ни от ситуаций на их входах, ни от значений данных, поступающих на эти входы – уровень регулярных компонентов.

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

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

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

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

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

r  áB, P, xb, ybñ,                                                (1)

где B – множество буферов, P – множество компонентов, xb и yb – структурообразующие соответствия.

Множество буферов B – конечное множество, каждый элемент которого характеризуется размером. Размер буфера b  B обозначим через size(b).

Положим множество

                                       Q = {q | 0  q  size(b)},

где q – число блоков данных хранящихся в буфере b, в качестве множества его возможных состояний. Состояние q = 0, означающее отсутствие блоков данных в буфере, и состояние q = size(b), при котором блоки данных заполняют все секции буфера, назовем критическими состояниями буфера.

Множество компонентов P – конечное множество, элемент p которого зададим четверкой

                                              p  áS,  , , ñ,

где S – конечное множество состояний компонента (s0  S – начальное состояние),  – функция состояний,  – функция выбора входных буферов,  – функция выбора выходных буферов.

Будем различать два вида компонентов – остановочные и безостановочные компоненты. Функция состояний остановочного компонента имеет вид:

Состояние  является заключительным состоянием компонента.

Функция состояний безостановочного компонента имеет вид:

Из определения функции  для этого случая следует, что, начиная с ,
0  m  nof(S)–1, состояния компонента сменяют друг друга циклически, в диапазоне номеров от m до nof(S)–1.

Функции выбора входных и выходных буферов – функции вида

                                  : S     и   : S ,

где через  обозначено множество всех подмножеств множества входных буферов xb(p)  B компонента p, а через  – множество всех подмножеств множества его выходных буферов yb(p)  B.

Общий вид диаграмм переходов остановочного и безостановочного регулярных компонентов показан на рис. 1. Подчиненные состояниям переходы на рис. 1 обозначенны стрелками. У безостановочных компонентов, при m > 0, диаграмма переходов состоит из двух частей: ациклической части – состояния , …,  и циклической части (рабочего цикла) – состояния , …, .

Рис. 1.  Общий   вид  диаграммы   переходов   компонента   r-схемы
a) остановочный компонент,  b) безостановочный компонент

 

Соответствия xb: P  B и yb: P  B, определяющие связи компонентов с их входными и выходными буферами, – суръективные инъекции. Буфер b является входным буфером компонента p, если b  xb(p), и выходным, если b  yb(p). Буфер b является петлевым буфером компонента p, если
b  xb(p)yb(p). Будем считать, что соответствия  и yb обеспечивают информационную связность r-схемы: любые два компонента схемы информационно  связаны друг с другом либо посредством буфера, либо посредством хотя бы одной цепи, состоящей из буферов и компонентов.

Функционирование компонента определим следующим образом. Пусть s – текущее состояние компонента. Условие его перехода из s в следующее состояние s¢ связано с выполнением двух требований:

                    b   (s)  q(b)  0   и   b   (s)  q(b) size(b),

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

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

                                  q¢(b) =  q(b) –1,  если b   (s),

                                  q¢(b) =  q(b) +1,  если b   (s),

                                                   s¢ =   (s).

Как и в общем случае [2], функционирование r-схемы складывается из независимого функционирования ее компонентов.

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

Редуцированную схему назовем циклически сбалансированной (далее, для простоты, просто сбалансированной), если ее компонентам можно сопоставить вектор целых положительных чисел Z = (, …, ) такой, что для любого буфера b  B,   связывающего компоненты                 ,  P, окажется выполненным равенство:

                                      wb* = rb*,                                                   (2)

где wb – число записей в буфер b за рабочий цикл компонента , rb – число чтений из буфера b за рабочий цикл компонента ..

Минимальный вектор целых положительных чисел Z = (, …, ), обеспечивающий выполнение системы равенств (2), назовем разметкой
r-схемы.

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

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

Изложенное делает справедливой следующую простую классификацию r-схем (рис. 2).

Рис. 2. Классификация r-схем с точки зрения их реализуемости

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

Состояние r-схемы определим как элемент конечного множества состояний

                                 W = ´…´´´…´

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

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

Состояние w  W назовем тупиковым, если ready(w) пусто. Множество тупиковых состояний r-схемы обозначим через WD.

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

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

Множество достижимых состояний r-схемы обозначим через .

Схему r  R назовем реализуемой, если никакое ее тупиковое состояние не является достижимым, то есть  пусто.

Интересным является вопрос о количестве достижимых тупиковых состояний нереализуемой r-схемы. Ответ на этот вопрос может быть получен, если предположить, что r-схемы обладают свойством конфлюэнтности [1]. Это свойство, применительно к r-схемам, формулируется следующим образом: редуцированная схема конфлюэнтна, если для любых двух состояний ,    существует состояние   достижимое как из , так и из .

Следствием конфлюэнтности r-схем является следующее утверждение: всякая нереализуемая r-схема имеет единственное достижимое тупиковое состояние.

Допустим, что нереализуемая r-схема имеет два достижимых тупиковых состояния ,   , причем . Сделанное предположение сразу же вступает в противоречие с конфлюэнтностью схемы, так как в указанных условиях не может существовать   достижимое как из , так и из . Следовательно,  =  = , где    – единственное достижимое тупиковое состояние нереализуемой r-схемы.

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

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

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

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

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

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

Литература

1.     Топорков В.В. Модели распределенных вычислений. – М.: ФИЗМАТЛИТ, 2004. – 320 с.

2.     Калинина Г.А., Мороховец Ю.Е. Модель асинхронной автоматной обработки данных. // Вестник МЭИ. – 2008. – № 5. –  С. 57-61.

3.     Модели асинхронной обработки данных и их применение для организации распределенных систем. Отчет о НИР. Гос. рег. № 01200605949, науч. рук. Ладыгин И.И. – М.: МЭИ, 2009. – 147