Александр Владимирович НЕМЧЕНКО
аспирант Харьковского национального университета
радиоэлектроники (известный как ХИРЭ)
e-mail: alexandre_n@mail.ru
www: alexandre-n.narod.ru

Параллельные цифровые автоматы - основные понятия

Введение

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

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

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

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

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

Но что же нам мешает использовать старую и добрую теорию цифровых автоматов для создания параллельных систем? Об этом я подумал перед поступлением в аспирантуру. Подумал - и решил заняться исследованием этого вопроса. Таким образом, в процессе своих исследований я займусь следующим: 1) исследованием существующей теории цифровых автоматов, 2) исследованием способов описания параллельных алгоритмов, 3) соединением 1-го и 2-го и 4) реализацией вышесказанного в рассыпном базисе и на программируемых логических устройствах.

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

Последовательный цифровой автомат - физическое поведение

То, что обычно называется "цифровым автоматом", я буду называть, естественно, "последовательным цифровым автоматом". Напрашивается аббревиатура ПЦА. Но так как я в будущем введу "параллельные цифровые автоматы" с тем же первым П, последовательные я буду сокращенно называть КЦА - "классические цифровые автоматы" (впрочем, если моя теория станет классикой, придется переобозначать :-)... ).

Итак, что же такое простейший "цифровой автомат"? Прежде всего, это цифровое устройство. Следовательно, оно базируется на двоичной логике. Если оно базируется на двоичной логике, все устройство может быть описано булевыми функциями - дизъюнкии конъюнкций. Действия выполняются над некоторыми операндами. Значит, цифровой автомат - это устройство, которое обрабатывает входные данные. Таким образом, цифровой автомат может быть описан следующим образом:

В формуле (1) X - набор входных значений, f ( X ) - их обработка, Y - результат. Графически это может быть изображено следующим образом:

Таким образом можно описать работу компараторов, мультиплексоров, элементов "И", "ИЛИ", простых преобразователей кода.

Но существует большой класс устройств, которым требуется менять свое поведение в течении времени. Фактически, это любой непростейший алгоритм. Очевидно, формулы (1) уже недостаточно, так как там отсутствует параметр времени.

"Менять поведение" в цифровой технике называется "менять свое состояние". Что такое состояние? Это те элементы устройства, которые меняются со временем. Следовательно, это элементы памяти. В простых случаях это набор триггеров. В сложном случае (компьютер, например) это набор регистров, значение всех элементов памяти и внешние запоминающие устройства. Состоянием называется комбинация всех таких элементво памяти. Для описания всех состяний компьютера нужно учесть все запоминающие устройства. Но для этого, небось, не хватит Ленинской библиотеки в Москве :-). Поэтому состояния описывают в относительно простых случаях.

Наличие памяти создает обратные связи в устройстве (см. рис. 2), которые определяют переход в новое состояние. Функция переходов определяется следующей формулой:

Состояние a зависит от времени t и текущего значения входных воздействий x ( t ).

Интерес представляет текущее время t. Строго говоря, оно измеряется в секундах (точнее, в наносекундах). Используя это время, мы можем разграничить сосдение состояния:

Как видно из рисунка 3 (что, впрочем, ясно и без рисунка), некоторое время tст цифровое устройство пребывает в состоянии at. Однако потом за время tпер изменяется значение регистра памяти. Это время зависит от времени распространения сигнала внутри схемы и от быстродействия элементов памяти и логики. В это время автомат находится в практически непредсказуемом состоянии. Естественно, в это время значение выходов будет непредсказуемо.

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

Следовательно, если мы вычеркнем промежутки времени tпер, мы получим набор вполне дискретных состояний устройства. Важно ли нам будет знать физическое значение времени? Нет. Поэтому в рассмотрение берется некое условное время 0, 1, 2, измеряемое в ежиках :-). Впрочем, при создании реального устройства эти "ежики" учитываются.

В какой момент времени происходит смена состояния устройства? Обычно это некоторый внешний сигнал. Говорят, что он "тактирует" работу устройства, "синхронизирует" смену его состояний (действительно, смена состояний происходит синхронно по всему устройству). Поэтому этот сигнал называют "тактом синхроимпульса". Для его реализации обычно делают генератор прямоугольных импульсов.

Итак, резюмируем (рис. 4). Цифровое устройство обрабатывает входные сигналы X по закону f ( X ) и выдает результат Y. При наличии элементов памяти изменяется состояние устройства a по закону

. Смена состояний инициируется внешним сигналом c.

Последовательный цифровой автомат - математическая модель

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

Цифровое устройство, оно же в нашем случае цифровой автомат описывается рядом множеств: множество входных воздействий X, множество выходных сигналов Y и множество состояний A.

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

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

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

Из всех возможных значений важно выделить то состояние, в которое попадает автомат в первый раз. Как правило, включение питания вводит автомат в некоторое непредсказуемое состояние. Поэтому вводится внешний сигнал сброса, который переводит автомат в четко определенное состояние. Это состояние называется "начальным" и обычно обозначается a0 (или a1 - так более классически).

Помимо этих множеств необходимо указать две функции - функцию переходов и функцию выходов.

Функция выходов описывает значение выходов в зависимости от текущего состояния и текущих входных параметров:

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

Как несложно догдадаться, текущее время a( t ) может быть выражено через предыдущее время a( t - 1). В связи с этим в модели применяется формула (4).

Из формулы (4) возможны 4 частных случая - 1) автомат зависит от состояния и входов, 2) зависит только от состояния, 3) зависит только от входов и 4) вообще ни от чего не зависит. 3-ий случай - это комбинационная логика. 2-ой случай получил название автомата Мура. 1-ый случай - автомат Мили. 4-ый случай - генератор константы.

Итак, математическая модель классического цифрового автомата описывается следующей системой:

В этом множестве формула (5.1) описывает множество входных слов, (5.2) - множество выходных сигналов, (5.3) - множество состояний, (5.4) - начальное состояние, (5.5) - функцию переходов, (5.6) - функцию выходов, (5.7) - дискретность работы во времени.

Параллельный цифровой автомат

А теперь попробуем добавить параллелизм в КЦА. Как это можно сделать?

Первым делом заглянем в математику. Точнее, в систему уравнений (5). Что там можно поменять? Или, если более научно, что можно изменить в системе (5) для обеспечения параллелизма и без разрушения целостности с сохранением автомата как черного ящика неизменным? Расшифруем последнюю мысль :-).

Цифровой автомат как черный ящик поменяться не должен. То есть замена КЦА на эквивалентный ему ПЦА и наоборот должна быть снаружи незаметной (под "эквивалентностью" в данном случае понимается выполнение тех же самых функций) - интерфейс меняться не должен. Следовательно, множества (5.1) и (5.2) не меняются.

Не меняется концепция ПЦА как цифрового устройства с множеством состояний. Значит, (5.3) тоже не меняется.

Не меняется концепция дискретной смены времени - (5.7) не меняется.

Если подумать, параллелизм в данном случае подразумевает наличие множества активных в данный момент состояний в отличие от одного активного у КЦА. Значит, изменяются уравнения (5.4), (5.5) и (5.6), где активно одно состояние:

Что означает (6.1)? Это означает, что в начальный момент времени могут быть активными несколько состояний одновременно. (6.2) означает зависимость множества одновременно активных состояний в данный момент времени от множества активных в предыдущий дискретный момент времени и входных сигналов. (6.3) означает зависимость выходных значений от множества одноврмененно активных состояний и входных сигналов.

Изменяет ли система (6) интерфейс цифрового автомата? Очевидно, что нет, так как интерфейс ограничен множествами (5.1) и (5.2).

Смена состояний производится одновременно (уравнение (6.2)).

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

Итак, получена модель ПЦА. Добавление системы (6) в систему (5), а также несколько необходимых переобозначений дают нам математическую модель ПЦА:

Символом

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

Упрощения

Достаточно ли системы (7) для описания ПЦА? Очевидно, что да.

Впрочем, это очевидно компьютеру, который оперирует математическими абстракциями. Если же взять какую-либо задачу (например, www.softcraft.ru/auto/ka/fil/ ), то сразу же ощущаешь некое бессилие - это ж сколько надо бумаги исписать и байтов занять, чтобы этими множествами описать работу устройства!

Если попробовать оперировать диаграммой состояний, то тоже будет нелегче - диаграмма будет абсолютно нечитабельной.

Очевидно, что нужно вводить упрощения и обобщения.

Неплохо бы ввести такие популярные у программистов процессы и потоки с нитями, буффер обмена, флаги, семафоры...

Учитывая это, данную модель я буду называть "абстрактной математической моделью". Просто "моделью" я буду называть такую, которая доступна для человека.

Все это вполне реально :-). Более того, на момент написания статьи уже существовала модель, которая работала (в рамках среды моделирования - на большее денег не хватило...).

Синтез

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

Если речь идет о рассыпной логике, то выбираются элементы памяти, кодируются состояния. Потом по полученным состояниям создается функция переходов и функция выходов. Производится упрощение на уровне булевых функций. Потом покупается целая куча элементов "И", "ИЛИ", "НЕ" и триггеров с дешифратором и все это запаивается в небольшого монстрика :-).

К счастью, есть более удобный (но не более дешевый) способ - использовать программируемые логические устройства. Берется один из языков описания аппаратуры - Verilog или VHDL (на момент написания статьи других популярных языков еще не было),- описывается поведение устройства, производится тестирование и отладка, синтезируется и, наконец, имплементируется. Весь процесс занимает куда меньше времени, чем предыдущий.

Все это применимо и для ПЦА. Производятся те же действия, разве что значительно более пузатыми получаются формулы и листинги. Но полученный код также может быть синтезирован и имплементирован.

Необходимо отметить такую деталь. Современные ПЛИС рассчитаны на синтез цифровых автоматов - у них есть несколько линий для синхроимпульса и сброса, которые короче других линий, а также напрямую подводятся к элементам памяти. В связи с этим несколько упрощается синтез таких устройств. Это также доступно для ПЦА.

Выводы

В данной статье была рассмотрена абстрактная математическая модель ПЦА, которая может быть синтезирована. Сложность процесса синтеза не выше синтеза КЦА.

Цифровой автомат - привычное понятие для разработчика цифровых устройств. Следовательно, использование ПЦА куда более понятно и просто, чем использование, например, сетей Петри.

Планируются дальнейшие статьи, где будут освещены последующие исследования.