Это первая статья цикла, предусматривающего рассмотрение логических схем или, более общо, логических процессов. Будет создан базис из логических элементов, позволяющих собрать любую схему. Специалистам, погруженным в бизнес-процессы, такая тема может показаться не стоящей внимания. Но мне тоже не понятно, почему бизнес-процессы выделяют в отдельную категорию. С формальной точки зрения они ни чем не отличаются от любых других процессов.
Таким образом, если вас интересуют общие проблемы параллельных процессов, то в этой и в последующих статьях на примере логических процессов мы их и рассмотрим. Терминологически мы будем придерживаться словаря по вычислительной технике под редакцией В.Иллингоута[1]. Но это может быть учебная литература, подобная [2], научная литература, как монография [3], или научно-популярные книги типа [4, 5].
Литературы по автоматам много. Бум пришелся на 80-е годы прошлого века, а сейчас лишь отголоски прошлого. Поэтому, с одной стороны, такой информационный массив позволяет выбрать наиболее подходящую литературу, но, с другой стороны, орождает множество толкований модели автомата, среди которых разобраться не так уж просто.
У меня сформировался свой вариант модели конечного автомата (КА), который далее будет основным. Данная модель, во-первых, очень близка к классической форме. А это важно, т.к. позволяет использовать теорию почти без исключений. А, во-вторых, она удобна для практики программирования, допуская эффективную ее реализацию. Более детально все эти вопросы освещены в статье [6].
Я, надеюсь, не похож на «мазохиста», терпящего «пот, боль и кровь» многопоточности (см. обсуждение статьи [7]). Тем не менее, в планы входит создание элементов на базе потоков. Все ли получится еще не ясно, но есть надежда на вполне благополучный исход, исходя из опыта использования потоков в контексте автоматного программирования.
Модель элемента задержки
Начнем, пожалуй, с не самого простого - модели задержки. Она базовый элемент всех логических элементов, где прямо или косвенно присутствует везде. Это подтверждается также тем, что ни чего мгновенно в природе нет. Например, среди взаимодействующих процессов нет таких, которые не требовали бы ее учета. Кроме того, у задержки есть определенный «характер», которым наделяются и включающие ее процессы.
Приведем определение задержки из словаря В.Иллингоута. Оно следующее:
P.296 propagation delay
Время, необходимое для того чтобы изменение сигнала на входе логического вентиля (L.123 Logic gate) или логической схемы (L.116 logic circuit) вызвало изменение на их выходе. Обычно это очень короткий промежуток времени. Он различен для разных схем и вентилей и вызван неизбежными задержками на переключение транзисторов.
Автоматная модель логического элемента «задержки на распространение» (далее просто задержки) в форме модели конечного автомата показана на рис. 1.
![Рис.2. Примеры из книги Кудрявцев В.Б и др.[2]](https://habrastorage.org/r/w1560/getpro/habr/upload_files/da7/e2c/ea0/da7e2cea049531705bc6383c14dd227f.png "Рис.2. Примеры из книги Кудрявцев В.Б и др.[2]")
На рис. 2 приведены автоматы в классической форме, которая, судя по учебнику [2], является базовой в МГУ. Здесь задержка представлена таблицей на рис. 1.12 и графом на рис. 1.13 (рис. 1.3 пример параллельной системы). Эти модели автоматов достаточно легко конвертируются друг в друга, но автомат на рис. 1 включает то, что не учитывает модель на рис. 2. Например, вложение автоматов, как аналог понятия подпрограммы. Они в «классике» фактически не рассматриваются. Не отражается и тип задержки. Относительно абстрактной модели классического автомата можно сказать, что ее использование достаточно специфично, а потому более удобна модель структурного типа.
Но вернемся к задержке. Автомат на рис.1 из начального состояния «st» перейдет в состояние «s0» или «s1». Только произойдет это после того, как в рамках действия y12 будут инициированы ссылки на переменные модели и значение задержек. Выходная переменная устанавливаются действиями y1 и y2. В модели это действия автомата Мура, которые выполняются только один раз при входе в соответствующее состояние. Действия y3 и y4 (это уже автомат Мили) устанавливают текущее значение задержки, создавая вложенные автоматы, которые отсчитывают заданное число дискретных тактов.
Таким образом, модель на рис. 1 отслеживает текущее состояние входа и при его изменении переходит в то или иное состояние, устанавливая с задержкой выходной сигнал. Напомним, что сигналам автомата в этом случае соответствуют переменные программной модели задержки.
Транспортные и инерционные задержки
Задержки делятся на транспортные и инерционные. Транспортные всегда передают на выход изменения сигналов на входе, а инерционные лишь в случае, если длительность входного сигнала превышает значение задержки. Выше была рассмотрена задержка транспортного типа. Модель задержки, которая может быть как транспортной, так и инерционной представлена на рис. 3. На графе автомата все, что относится к инерционной задержке, выделено красным цветом.
Инерционная задержка при изменении входного сигнала переходит в состояние «0» или «1». Если при этом входной сигнал в течение времени задержки не возвращается к исходному, то его значение передается на выход. В противном случае задержка возвращается в состояние, предшествующее изменению входного сигнала, а выход остается в текущем состоянии.
При переходе в состояния «0» или «1» создается циклический параллельный процесс с циклом, равным значению задержки. Затем одновременно контролируется входной сигнал, и активность параллельного процесса (предикат x3). Задержка перейдет в противоположное состояние, если за время активности параллельного процесса значение входа не изменится. В противном случае она вернется к предыдущему состоянию. При этом запускается действие y5, уничтожающее параллельный процесс.
На рис. 4 приведены результаты тестирования задержек, одна из которых транспортная - средний график, а другая инерционная - верхний график. Видно, что инерционная задержка фильтрует короткие импульсы, а транспортная задержка реагирует на изменение сигнала, транслируя его на выход. Но, что важно, во время работы вложенного автомата транспортной задержки любое изменение входного сигнала ею игнорируется.
Однако транспортная задержка реагирует даже на очень короткий входной сигнал, который инерционная задержка отфильтрует. В определенном смысле она тоже фильтрует входной сигнал, но делает это лишь тогда, когда находится в режиме реализации задержки.
Итог
Окончательный итог подводить пока рано, т.к. еще есть о чем поговорить. Например, если все делать на автоматах, то при большом их числе ядро среды ВКПа будет перегружено. Это, кроме влияния на скорость процессов, снижает и качество управления.
Использование медленных автоматных пространств среды ВКПа снижает нагрузку на ядро, но, порой, не спасает и это. Может помочь использование таймеров и потоков. Подобные задержки (уж поскольку мы их рассматриваем) фактически уже созданы. Вот обо всем этом мы и поговорим в продолжение начатого разговора.
PS
Не удержался, чтобы не откликнуться на статью, которая неверно и крайне безграмотно трактует роль параллелизма [8]. Подобные воззрения служат питательной почвой для формирования мифов о параллелизме вообще и параллельном программировании в частности.
Во-первых, параллельное программирование – это далеко не про скорость. Скорость – лишь ее побочный эффект. Главное предназначение параллелизма – решение проблем сложности. Это когда сложная проблема разбивается на множество параллельных простых частей. Возьмем тех же философов Дейкстры: один философ – несравненно более мелкая проблема, чем задача в целом. В любой нейронной сетке множество нейронов нужны отнюдь не для увеличения скорости, а для решения сложных задач.
Во-вторых, распараллеливанию поддается любая задача, кроме элементарных. К последним относятся те, которые формально могут быть представлены автоматом без памяти (автомат с одним состоянием). А таких задач по сравнению с общим их числом ничтожно мало. А потому распараллеливанию поддается буквально все, что «движется», т.е. имеет мало-мальски сложный алгоритм.
Литература
1. Толковый словарь по вычислительным системам/Под ред. В. Иллингоута и др.: Пер. с англ. А.К. Белоцкого и др.; Под ред. Масловского. – М.: Машиностроение, 1991. – 560 с. https://libcats.org/book/764533
2. Кудрявцев В.Б., Алешин С.В., Подколзин А.С. Введение в теорию автоматов – М.: Наука. Гл. ред. физ.-мат. лит., 1985. – 320 с.
3. Мелихов А.Н. Ориентированные графы и конечные автоматы. – М.: Наука, 1971. – 416 с.
4. Поспелов Д.А. Фантазия или наука: на пути к искусственному интеллекту - М.: Наука, 1982. – 224с.,15 ил.
5. Варшавский В.И., Поспелов Д.А. Оркестр играет без дирижера: размышления об эволюции некоторых технических систем и управления ими. - М.: Наука. Главная редакция физико-математической литературы, 1984, - 208с.
6. Автоматное программирование: определение, модель, реализация. https://habr.com/ru/articles/682422/
7. Инь и ян программирования или alter ego многопоточности. https://habr.com/ru/articles/978350/
8. Больше ядер, а не более быстрые ядра. https://habr.com/ru/companies/spring_aio/articles/980220/
