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

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

Введение

Было сказано, что ПЦА может быть рассмотрен на двух разных уровнях - абстрактная математическая модель и высокий уровень. Было много сказано про абстрактный математический уровень, а вот про высокий уровень будет сказано далее :-).

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

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

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

Большие извинения перед UNIXоидами всех стран - понятия для параллелизма я взял из программирования на Windows NT, в связи с чем и извиняюсь <%-(...

Пристегивайтесь покрепче - сейчас начнется полет по разным трюкам параллелизма!

Поток - основа параллелизма

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

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

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

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

В вышеприведенном промере 1-ый поток может закончиться по-разному - или породить новые потоки (e1:2) или закончиться вместе со 2-ым потоком (e1:2).

Для определения переходов между рабочими состояниями используется теория КЦА. Для начального и конечных состояний используются иные закономерности.

Вроде бы все, что касается потоков. Теперь разберемся с тем, как потоки взаимодействуют.

Порождение потоков

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

На граф-схеме алгоритма (ГСА) я порождение показываю как жирную горизонтальную полосу.

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

Но есть варианты - что считать начальным и что считать конечным состоянием? В предыдущем примере эта ситуация проявилась в потоках 1 и 3.

Варианты возникают из-за условных вершин. Следовательно, есть три варианта - 1) безусловный переход, 2) условный переход без цикла, 3) условный переход как ждущая вершина. Рассмотрим варианты для конечной вершины, так как начальная всегда будет предваряться начальным состоянием.

Если конечная вершина - просто операторная, тогда без вариантов - она и есть конечное состояние. Этого вполне достаточно для старта остальных и для перехода в начальную.

Если у нас 2-ой вариант (как было в потоке 1), то необходимо анализировать порождающиеся потоки. Если там нигде нет ждущих вершин, то можно смело не вводить конечное состояние. Но если же там есть ждущая вершина (как было в потоке 3), то необходимо отдельное состояние дабы не было коллизий.

В случае со ждущей вершиной тоже самое - если нигде далее нет ждущих вершин, то конечное состояние не нужно.

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

Синхронизация конца

Итак, ряд потоков снизу объединяется в один (или несколько) новых потоков. Очевидно, что когда все потоки, объединяемые в конце, достигнут конца, могут запускаться следующие после них. Единственный ли это вариант? Канэшно нэт! Мы с тем же успехом можем ждать первого из всех объединяющихся. Опять же - когда дождались, то ждем ли остальных... В общем, есть варианты. Посему разложим по полочкам :-).

Объединение конца по принципу И

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

Очевидно, что здесь обязательно надо вводить как конечные, так и начальные состояния, так как возможно ожидание.

Условием старта потока после конца будет конец в данном или следующем такте 1-го потока и конец в данном или следующем такте 2-го потока и конец... 3-го и ... и ... .

Условием перехода из конечной вершины в начальную будет переход потока/потоков, следующих за ними, в посленачальное состояние.

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

Объединение конца по принципу ИСКЛЮЧАЮЩЕЕ ИЛИ

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

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

Как вы видите, различные потоки имеют свои "отростки" в то место, где все они объединятся по принципу "ИСКЛЮЧАЮЩЕЕ ИЛИ" (как вы уже догадались, обозначается оно как принято в западной схемотехнике - двумя дугами).

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

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

Объединение конца по принципу ИЛИ

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

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

Тут открываются свои проблемы в реализации. Поток после объединения запускается лишь один раз или несколько? Если один, то вообще один раз за работу ПЦА или же как-то иначе? Если несколько, то как?

Я пока не смог решить однозначно эту проблему. Над этим еще стоит подумать.

Дальнейшее развитие темы объединения потоков - процедуры

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

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

Когда это нужно? Вот пример. Допустим, наш ПЦА выполняет набор каких-то параллельных действий. Время от времени ему нужно посылать информацию по какому-то каналу связи. Но этот канал связи не простой, а RS-232 :-). Там уже нельзя просто послать последовательность бит - там свой протокол, завязанный на времени и некоторых условиях. Очевидно, что можно сделать некоторый поток в виде той самой процедуры, который будет выполнять эти действия.

Как это можно сделать? Создаем некоторую переменную, куда записываем данные на посылку. Объединяем потоки по принципу "ИЛИ". Но это объединение будет порождать процедуру. Что получается? Первый из потоков достиг конца, записав при этом значение в переменную. Запускаетя процедура, которая с ней работает. В это время остальные потоки ждут конца работы этой процедуры. Обслужив первый поток, процедура начинает обслуживать следующие. А тот первый поток преспокойно идет дальше! Классно, да?!?

Флаги

Однако не все так просто, как хотелось бы. Нужно как-то защищать ту переменную, куда все будут писать данные. Иначе возможно искажение информации. Как это можно сделать?

Перед записью проводятся некоторые подготовительные действия - допустим, перевод в необходимый формат и тому подобное (см. рис. 3а). А потом что - писать надо! Но перед этим нужно проверить некоторое условие - "свободно" ли? Но не просто проверить, а зависнуть в ожидании этого "свободно". Ну а после этого уже вызывается процедура SEND.

Введем, кстати, обозначение процедуры так, как на рис. 3а). Здесь одна дуга - это западное обозначение элемента ИЛИ. Также будем обозначать, кстати, объединение по принципу ИЛИ.

Вот такое ожидание мы и назовем флагом. Он поподробней показан на рис. 3б). Флаг - это проверка некого условия f. Если оно истинно, то из состояния a18 можно сразу переходить в состояние a19. Если же нет, то необходимо "зависнуть" - остаться в некоторой ждущей вершине и ждать выполнения этого условия. Реализация такого подхода показана на рис. 3в).

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

Мультиактивные процедуры?..

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

Реализация мьютексов и семафоров

В программировании для Windows NT есть такие полезные вещи, как мьютексы и семафоры. Что это такое? Мьютекс- это некий объект, владеть которым может лишь один поток одновременно. Семафор - это тоже объект, у которого владельческие права расширены до нескольких товарищей одновременно :-). Как это можно реализовать в нашем случае?

Очевидно, что тут можно использовать процедуры. К ней будут обращаться для проверки состояния некоего объекта - мьютекса или семафора. И потом смело делать свое дело :-). А сама процедура будет решать, кому и как выделять права на объект. И тут уже можно реализовать не только семафоры и мьютексы, но и объекты посложнее.

Исключающие переходы

Еще одна полезная вещь - исключающий переход. Это такой переход из состояния в состояние, когда все остальные потоки, кроме текущего, сбрасываются в начальное. Это также можно использовать при обработке ошибок. Но если в объединении ИСКЛЮЧАЮЩЕЕ ИЛИ останавливались только "соседи", то тут можно останавливать хоть всех.

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

Процессы

Давайте рассмотрим еще одно понятие параллелизма - процессы. В среде Windows NT процесс - это набор потоков, которые между собой общаются тесно, а вот с другими потоками из других процессов - нет. То есть исключено прямое влияние процессов друг на друга. Вроде бы такое же есть и в Windows 95/98, но тогда какого черта она так зависает?!?

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

Раз процесс - это отдельный ПЦА, то у каждого процесса есть свой отдельный интерфейс - входные и выходные сигналы, сброс и синхроимпульсы. Вот давайте и будем это использовать для связи процессов. То есть, при разбиении ПЦА на процессы мы получаем набор независимых цифровых автоматов, которые могут друг друга сами тактировать и перезапускать! Фактически, в одном корпусе можно реализовать совершенно различные и асинхронные друг другу устройства!

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

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

Выводы и перспективы

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

Это статья - последняя из цикла четырех вступительных. Напомню вкратце эти статьи:

На этом работа не закончена. Собственно говоря, я пишу диссертацию на эту тему, поэтому буду еще думать и думать, писать и писать :-). Надеюсь со временем проработать формальные вопросы и все сделать красивым, точным и логичным - настолько, чтобы ВАК мне поверил :-).

Из честолюбивых планов - надеюсь создать систему автоматического проектирования (САПР), где будет векторный графический редактор. В нем вы задаете процессы и потоки, а также все связи между ними и внутри них :-). Потом вы выбираете автомат для синтеза - Мили или Мура. После этого создается синтезируемый код на языках описания аппаратуры VHDL и Verilog. Потом подключается программа для прошивки кристалла и параллельное устройство готово для применения :-) !