Метод Янова анализа процессов с обратной связью

1. История вопроса

  В 1958 г. сборник [1] АН СССР опубликовал почти целиком (!) кандидатскую диссертацию Янова Ю.И - тогда младшего научного сотрудника ИПМ (Москва): это была первая удачная попытка формального определения критерия относительно строгой эквивалентности логических схем алгоритмов (ЛСА). Для этого Янов для каждого оператора ЛСА ввел `сдвиги` - набор логических переменных в бинарной логике, которые только оператор ЛСА и может изменить. Критерий эквивалентности двух ЛСА – совпадение вычисляемых рекурсивной процедурой функций сдвигов для одних и тех же их операторов. Попытки многочисленных, конференций выяснить физическую суть функций сдвигов не увенчались успехом.
  Физический смысл введенных Яновым основополагающих для ЛСА этих понятий установлен работой [4]. Здесь вместо ЛСА использовалась более общая логическая схема вычислительного процесса (ЛСВП) с классической моделью в виде абстрактного синхронного автомата [2] без выхода с соответствующим мощным и лаконичным математическим аппаратом. Понятие `сигнал на входе такого автомата` адекватно набору всевозможных значений логических переменных (ЛП) ЛСА и, таким образом, не ограничивается двузначной логикой и перечнем ЛП, изменяемых оператором ЛСА. В модели ЛСВП понятие `сдвиги` (`распределение сдвигов`) заменено куда более широким определением `ограничения на входе автомата` (генератор в терминологии статьи [4]): для каждой из любого подмножества предысторий поведения автомата длиной не более k вводится множество допустимых сигналов, один из которых в очередной момент (синхроимпульс) времени может быть (и только!) подан на вход автомата при условии, что к этому моменту автомат прошел эту предысторию.

Отступление! При подаче на вход автомата последовательности x…y…z сигналов автомат проходит состояния a…b…c. Последовательность пар x/a,…,y/b,…,z/c определим как историю и любой конечный отрезок этой последовательности, например, y/b,…,z/c как предысторию поведения автомата. Областью определения автомата - множество всевозможных историй его поведения, начинающихся с некоторого его исходного фиксированного (начального) состояния автомата

В отсутствие такого ограничения (по умолчанию) это множество считается совпадающим со множеством всевозможных сигналов на входе автомата – их алфавитом. Такую модель ЛСВП работа [4] определяет как k/B-автомат. Основные свойства таких автоматов (одноименный раздел работы [4]) были получены повторением метода [1] Янова один к одному. Вместе с тем лаконичность языка теории абстрактных автоматов [2] позволила уточнить – усилить формулировку основных исходных положений (леммы) этого метода, не меняя схемы их доказательств. Как следствие введено понятия покрытия (см. далее п.4) области определения автомата, а затем и ее минимального покрытия, определяющего физически число шагов итерации, за которое достигается вычисление функций сдвигов ЛСА и аналогичного определения в ЛСВП. Это число шагов совпадает с максимальной длиной (количеством пар x/a) истории в минимальном покрытии.
  Известный писатель-фантаст Сергей Лукьяненко выступит на TAdviser SummIT 28 ноября. Регистрация 5.8 т В 1975 году Янову не удалась попытка объединить усилия обеих школ - московской в части исследования операторных схем алгоритмов (ак. Ершов) и киевской в анализе дискретных преобразователей.(ак. Глушков). - "Молодой человек! У вас есть 3 минуты, чтобы изложить суть дела" - предупредил заранее директор ИПМ ак. Яблонский, положив передо мной часы. Тогда я к этому не был готов и, похоже, в состояние шока пришел лишь Янов - инициатор встречи.

2. Метод Янова в анализе процессов с обратной связью

  К сожалению, авторы работы [4] (и Ваш слуга в том числе) не обратили внимание на тот факт, что введенные ими ограничения на входе автомата являются своеобразным и вместе с тем естественным способом формального определения обратной связи. Этого тем более не мог заметить Янов, поскольку ввел `сдвиги` даже не для предыстории длины 1 (k=1) поведения ЛСА, но только для выполненного последним оператора ЛСА этой предыстории – состояния автомата (ЛСВП) в терминологии работы [4]. – А это как бы `вырожденный` случай обратной связи.

  Применимость метода Янова для детерминированных процессов, использующих модель k/B-автомата, обосновывается работами [4] и [5], повторяющих этот метод [1] практически без изменений. Там же метод Янова интерпретируется для вероятностных 1/B-автоматов (k=1). Рассмотрим применимость метода к анализу вероятностных k/B-автоматов при k>=1, избегая громоздких математических выкладок работ [4] и [5] и ограничившись концепциями их реализации (сутью):

1) В каждой ячейке [i,j] матрицы переходов [2] автомата множество сигналов, определяющих переход из состояния Ai в Aj, согласно [3,4] заменяем упорядоченным по алфавиту входных сигналов списком значений условной (при условии достижения состояния Ai ) вероятности перехода (из Ai в Aj,) для каждого из них, в т.ч. значением 0 для отсуствующих сигналов в ячейке [i,j]. Понятно, что сумма значений каждого из таких списков равна 1.

2) Ограничение для каждой из всевозможных предысторий поведения автомата теперь рассматривается как генератор очередного входного сигнала с вероятностью, определяемой аналогично (1). И здесь также равна 1 сумма значений списка вероятностей

3) При подаче на вход детерминированного автомата последовательности V={x1,x2,…,xN} сигналов xI (I=1,…,N) автомат проходит единственную соответствующую последовательности состояний S={a1,a2,…,aN} и этот процесс определим как отображение V->S. Теперь же (вероятностный автомат) это отображение не является одно-однозначным и речь идет о вычислении вероятности P(V->S) отображения V->S, которое выполняется на основе (1), (2) и элементарных сведений теории вероятности

4) В случае детерминированного автомата и ЛСВП [4] аналог функции сдвигов для состояния‘a’ автомата – это множество сигналов ‘x’ (набор значений ЛП в терминологии ЛСА), для которых существует (событие!) история поведения автомата, завершающаяся ‘x/a’. В случае вероятностных автоматов множество таких сигналов определяется как вероятности указанных событий для них, оформленные в список идентично (1) и (2). Вместе с тем получение таких `функций сдвигов` происходит все по той же предложенной Яновым схеме, включая исходные положения - леммы 1 и 2 работы [1]

3. Сходимость вычислений по методу Янова

  Сходимость вычислений функций сдвигов (анализа ЛСА и ЛСВП) для детерминированных процессов (ЛСА, ЛСВП и др.) фактически установил сам Янов. Сходимость аналогичных вычислений (метода) для вероятностных 1/B-автоматов (k=1) рассмотрена работами [4,5]. Здесь попробуем обосновать сходимость для процессов, моделируемых вероятностными k/B-автоматами для k>1, избегая, как и выше, громоздких математических выкладок, ограничившись концепциями их реализации. Для этого достаточно преобразовать вероятностный k/B-автомат в эквивалентный по действию простой марковский (эргодический) процесс [6]:

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

b) Формируем матрицу состояний марковского процесса [6], помечая эти состояния (строки и столбцы матрицы) предысториями (a) – в одинаковом порядке строки и столбцы

c) В ячейке матрицы (b) на переходе из состояния A (строка) марковского процесса в состояние B (столбец) вычисляем (проставляем) вероятность перехода лишь в следующих случаях:

• длина La предыстории A меньше k (La<k) и предыстория B является продолжением /предыстории A на один шаг, т.е. длина Lb=La+1, где Lb - длина предыстории B
• La=k, Lb=k и начальный отрезок длиной k-1 предыстории B совпадает с конечным отрезком предыстории A той же длины k-1

Понятно, что в обоих случаях A имеет вид ‘…,y/b’ и B - ’…,y/b,z/d’

Согласно (1) - (4) п.2 вероятность перехода из A в B определяется как произведение вероятности из списка (a) предыстории A для сигнала z последнего элемента предыстории B на вероятность из списка (1) перехода k/B-автомата из состояния b (последний элемент предыстории A) в состояние d по сигналу z на входе исходного <k/B>-автомата. Вычисленную вероятность перехода из A в B помещаем в ячейку матрицы (b) на пересечении строки A и столбца B

d) В незаполненные вычислениями (c) ячейки помещаем 0 (ноль)

Согласно (1) и (2) п.2, (c) и (d) сумма значений ячеек каждой строки полученной матрицы равна 1. Следовательно, эта матрица в общем случае с огромным количеством состояний описывает эргодический процесс

4. Практическое применение метода в анализе ЛСВП

Работа [4] формально вводит покрытие области определения k/B-автомата как компактную регулярную форму записи всевозможных историй его поведения. Внешне (граф-схема) такая структура является иерархической, удобно в своей основе (скелет) отображающая дерево простых путей – историй поведения из не повторяющихся пар x/a. Покрытие позволяет избежать необходимости выстраивать k/B-автомат, в точности отвечающий приведенному выше его определению и конкретному ЛСВП, анализируемому с применением компьютера. Достаточно разработать единый удобный (пользователю) язык описания ЛСВП, позволяющей компьютеру обработкой этого описания получить минимальное покрытие области определения k/B-автомата, соответствующего этой ЛСВП. Избегая деталей [4] отметим следующие основные моменты (суть):

1) В каждой паре 'x/a' истории поведения автомата под ‘x’ понимается упорядоченный по идентификаторам ЛП набор их текущих значений. Состояние ‘a’ автомата ассоциируется с операционным блоком (ОБ) ЛСВП, на входе в который определен набор ‘x’ значений ЛП

2) Логический блок (ЛБ) имеет несколько выходов, помечаемых альтернативными условиями в виде ДНФ, а также значениями временных задержек на переключение по выходу. Эти условия ссылаются на текущие значения ЛП и только! В сущности ЛБ определяют переключения между ОБ (вместо матрицы переходов автомата)

3) ОБ содержит последов
ательность операций (отличие от [4]), каждая из которых включает:

• условие выполнения операции
• операцию спецификации (присвоения значения) одной или нескольким ЛП
• условную вероятность операции
• временную задержку - время на операцию

4) До начала анализа определяется набор исходных значений ЛП и операционный блок, запускаемый первым

5) Исходные (4) образуют уровень L=0 формируемого покрытия из единственной пары 'x/a' - начало всех историй поведения моделирующего ЛСВП автомата

6) Следующий уровень L+1 формируется поочередной генерацией всевозможных продолжений 'y/b' (в историях поведения) от каждой пары 'x/a' текущего уровня L на один шаг с отличной от 0 вероятностью. Однако пара 'y/b' включается в новый уровень L+1 только в случае, если она отсутствует в покрытии – формируемом новом L+1 или уже сформированных уровнях. В любом случае исходная пара 'x/a' связывается отдельной ссылкой с ее продолжением – новой или найденной парой 'y/b'. Ссылка помечается вероятностью и временем выполнения операции – генерации ‘y’ блоком ‘b’ . Это время (задержку) пополняют задержкой на переключение (ЛБ) от ОБ ‘a’ к ‘b’

7) В отличие от выходов ЛБ и разработок [4,5] (!) условие в ОБ ‘a’ использует не только текущие значения ЛП, но и значения ЛП на входе ОБ, предшествующим ‘a’ в предыстории длиной не более k – параметра k/B-автомата, определяемого при запуске процесса формирования покрытия. Именно с этой целью связи между парой 'x/a' и согласно (6) порождаемыми ею 'x/b' в покрытии вводятся двунаправленными. Такие ЛП предваряются (префикс) в условии именем этого предшествующего в предыстории ОБ. Более того, такое условие может содержать лишь требование наличия нужного ОБ в предыстории (без указания ЛП). Такой учет (обратными ссылками от 'y/b' к 'x/a' и далее) завершающихся парой x/a предысторий длиной не более k в уже сформированной части покрытия позволяет сократить количество ЛП и много более сократить множество всевозможных наборов их значений и, следовательно, размер покрытия

8) Процесс формирования покрытия заканчивается при пустом очередном слое формируемого покрытия. В силу (6) в формируемом покрытии пары 'x/a' не повторяются

  Результатами анализа являются:

a) удаление не активных (отсутствующих в покрытии) блоков (ОБ и ЛБ), выходов ЛБ и операций ОБ

b) упрощение условий на выходах ЛБ и в операциях ОБ исключительно учетом не используемых значений ЛП и ОБ в покрытии

c) вычисление вероятности и времени достижения различных ОБ и возврата к ним (цикл)

В точном соответствии с [4] вычисления производятся над деревом простых путей (ДПП) – историй поведения без повторяющихся пар 'x/a' в иерархической структуре покрытия. При этом используются числовые пометки ссылок (6) ДПП, выделяемого и обходимого по контуру известными классическими методами [7].

  Быстродействие вычислений фактически определяется зтратами на формирование покрытия и главным образом на этапе (6) операцией поиска сформированной очередной пары 'y/b' в уже сформированной части покрытия. Эта проблема снимается использованием ассоциативной памяти покрытия, которая может быть реализована как физически, так и программно в универсальном компьютере. Такая память (ассоциации) может эффективно использовать внутреннюю структуру ‘x’ (набор значений ЛП) пары 'x/a' покрытия, эффективные коды ‘a’ (ОБ) и, наконец, распределение пар 'x/a' по слоям покрытия

Литература

1. Янов Ю.И., О логических схемах алгоритмов, В сб. Проблемы Кибернетики, Физматгиз, Москва, 1958г., вып.1
2. Гилл А. Введение в теорию конечных автоматов: Пер. с англ.- М: Наука, 1966 г.
3. Бухараев Р.Г. Вероятностные автоматы. Казанский гос.университет, 1970 г.
4. Додонов А.Г., член-корр. АН УССР, Патрикеев В.Л., Метод машинного анализа последовательностных вычислительных процессов. – ж.: Электронное моделирование. – Киев, 1986, № 3
5. Патрикеев В.Л., Автореферат диссертации `Метод и организация вычислительной структуры для анализа вычислительных процессов и систем`, УДК 681.34:519.673, Киев, 1986
6. Дынкин Е.Б., Марковские процессы, Физматгиз, М., 1953
7. Свами М., Тхуласираман К., Графы, сети и алгортмы, М. Мир, 1984 г.
8. Байцер Б. Микроанализ производительности вычислительных систем: Пер. с англ. – М.: радио и связь, 1984 г.