Программисты, как правило, кушают то блюдо, которое им подают. Будь это язык программирования, библиотека, фреймворк или IDE. Однако, это еще полбеды. Удивляет нежелание выбирать. Хотя это тоже можно объяснить. Выбор‑то, может, и есть, сколько новых языков появилось за последнее время, но только разницы между ними особой нет. В результате, попробовав раз, попробовав два, мы устаем и останавливаемся на чем‑то одном, т. е. пресыщаемся...

Можно объяснить сложившуюся ситуацию также следующей аналогией. Мы не выбираем язык общения. Говорим на языке родителей и/или окружающих. Освоить другой язык — почти проблема, которая в детском возрасте решается много проще. Что‑то закладывается природой, т. е. способностями, но часто все получается само собой, когда мы погружаемся в другую языковую среду. И, вероятно, это наилучший вариант. Но кому‑то не помогает даже это.

Неужели язык программирования, который мы впитали с «детства» — со школы, института и т. п., становится нашим «родным» навсегда? Неужели наши «родители» — преподаватели, коллеги, друзья, а теперь и реклама навязывают язык, на котором мы обречены «говорить» всю оставшуюся жизнь? Можно предположить, что даже термин «язык» применительно к инструменту программирования выбран с определенным умыслом. Чтобы раз и навсегда, чтобы не было охоты менять свой «языковый мир». И, похоже, это работает?!

Или программисты попросту утеряли чувство вкуса? Немногие, наверное, помнят, но когда‑то разнообразие «параллельных блюд» было достаточно большим. Однако осталась только многопоточность, которую в последнее время приправили сопрограммами, пересыпав до этого многоядерностью. Но вкус основного блюда это ничуть не перебило. И, что интересно, ведь, такая «приправа», как сопрограммы, была известна очень давно. Тем не менее ее, было подзабыв, вытащили из дальнего угла шкафчика, обозвали иначе и стали активно продвигать.

Можно сколь угодно удивляться, но сопрограммы, прошу прощения — корутины, превратились в современный тренд развития параллельного программирования. Только что и на слуху — корутины, корутины, корутины... Правда, «помножить на ноль» основу не получилось, а потому связка корутины‑многопоточность‑многоядерность эксплуатируется по полной программе: создаются библиотеки, фреймворки, корутинами расширяются языки программирования. Но то, что сами по себе они совсем не про параллельность, ни кого не смущает. Корутины прочно обосновались в категории параллелизм.

Этапы большого пути

Рассмотрим следующую цитату из [1].

При решении проблем параллелизма не обойти следующих трех этапов:

1. Идентификация естественного параллелизма, который существует в контексте предметной области.

2. Разбиение задачи, стоящей перед программным обеспечением, на несколько подзадач, которые можно выполнять одновременно, чтобы достичь требуемого уровня параллелизма.

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

Эти три этапа достигаются при условии параллельного решения следующих проблем:

• «гонка» данных -- обнаружение взаимоблокировки

• частичный отказ -- бесконечное ожидание

• взаимоблокировка -- отказ средств коммуникации

• регистрация завершения работы -- отсутствие глобального состояния

• проблема многофазной синхронизации -- несоответствие протоколов

• локализация ошибок -- отсутствие средств централизованного распределения ресурсов

И, кажется, все правильно. Очевидное вообще сложно оспорить. Но вот по поводу решения проблем возникает множество вопросов. Например, «гонки», которые у параллельных объектов есть всегда. Просто в одном случае от них зависит результат, в другом — нет. А если влияние есть, то требуется одна модель решения задачи, а если его нет, то модель может быть попроще. Для примера: в мире дискретной математики и цифровых схем этим случаям соответствуют последовательностная и комбинационная модели (подробнее о них см. [2]).

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

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

В схему добавлены также два блока отображения данных в графической форме. И если будет какая-то гонка данных/сигналов, то вид графиков должен ее отражать. А вот, чтобы это было корректно, эти блоки должны  быть скоординированы с остальными блоками.

У перечисленных выше этапов нет чего‑то такого, что привязывало бы их к определенной модели параллельных вычислений. Все определяется неким интуитивным представлением. Тем не менее, такая модель обязательно присутствует. Так, в исходной форме используется модель блок‑схем[3], а в предлагаемом варианте решения — конечно‑автоматная (подробно о ней см. [4]). Но точно об используемой модели можно судить лишь в отношение блоков, вычисляющих НОД, для графических блоков что‑то конкретное сказать нельзя. Они в данном случае представляют так называемые «черные ящики» в отличие от остальных — «белых ящиков».

Изменения в алгоритме НОД

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

В форме модели конечного автомата измененный алгоритм НОД представлен на рис. 2.

Здесь блоку НОД добавлены два входа с именами biffast и bstart (с. рис. 1). Первый вход позволяет задать режим работы — обычный или быстрый. В быстром режиме действие y6 вычисляет значение делителя за один такт автоматного времени (но далее быстрый режим нами рассматриваться не будет, хотя и там есть о чем поговорить). Единичное значение входа bStart позволяет синхронизировать начало работы всех блоков НОД.

В автомат введено состояние S2. В нем алгоритм, выдав результат, остается пока не будет изменен хотя бы один из входов блока. С одной стороны, это позволяет фиксировать момент вычисления значения НОД, с другой, — оптимизирует работу, исключая повторные вычисления для одних и тех же входных данных. В этих целях входные значения запоминаются в буферных переменных (см. действия y1, y2).

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

Итак, задав значения на входах первых двух блоков, мы через какое‑то время должны получить результат на выходе третьего блока. При этом число затраченных блоками тактов будут выведено на соответствующий выход. Моменты получения выходных значений, как самого НОД, так и числа дискретных шагов будут отражать диаграммы графических блоков. Сам код блоков на внутреннем языке SimInTech, соответствующий автомату на рис. 2, приведен на рис. 3.

О цикличности работы процессов

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

Для любого алгоритма, представленного в текстовой форме на том или ином языке программирования, существует графический эквивалент в форме графа. Если в алгоритме есть цикл, то ему на графе алгоритма соответствует циклический путь. И, казалось бы, какая разница между циклическим путем на блок‑схеме и циклическим путем на графе автомата (а речь ведется в первую очередь именно об этих формах )? И, действительно, игнорируя отличие в формах графов, можно сказать, что ее нет. Но, однако, есть существенная разница в средствах реализации циклических путей.

В обычных языках операторы управления для реализации циклов представлены операторами типа while или for. Если в языке есть оператор безусловной передачи управления типа go to и метки, которыми можно именовать операторы программы, то цикл можно организовать с помощью их и оператора условного ветвления. Но поскольку в целом это картины не меняет, то можно ограничится рассмотрением только операторов цикла.

Возьмем оператор «задание цикла с предусловием» — оператор while <условие цикла> do <тело цикла> (см. раздел Общие сведения о языке программирования/Ключевые слова/while). В пояснении к оператору говорится, что им реализуется «выполнение операции пока выполняется условие цикла». При этом на верхнем уровне абстракции данный оператор вполне может рассматриваться как неделимый. В нашем случае цикл while завершится только тогда, когда будет найден наибольший общий делитель. В этом смысле оператор цикла столь же «мгновенен», как и любые другие операторы — арифметические, логические и т. п.

В автоматном языке нет аналога операторам управления обычных языков программирования. Их заменяет функция переходов и ее текстовая форма, соответствующая таблице переходов автомата. В данном случае каждая строка таблицы представляет отдельный переход автомата между состояниями. Программное ядро или некий «автоматный процессор» интерпретирует/исполняет каждую строку и тем самым реализует или нет переход в новое текущее состояние. Вот и все. Реализуется ли при этом циклический или какой‑то иной путь большой разницы нет.

Именно такой подход позволяет в моменты исполнения «инструкций переходов» организовать работу множества автоматов, рассматривая их текущие переходы в рамках текущего дискретного такта автоматной сети. Так реализуется «автоматный параллелизм». В рамках представленного выше кода (см. рис. 3) каждый автоматный переход представлен оператором условного ветвления if. При его выполнении реализуется <оператор при выполнения условия> (см. описание оператора if в справке SimInTech), а при невыполнении условия мы тут же просто покидаем тело блока.

Таким образом, описанный подход к реализации «автоматных блоков» исключает их зависание в принципе. Зависший автомат — нонсенс. Формально дискретный такт не может быть бесконечным, как, кстати, и равным нулю (т. е. мгновенным). Теория эти крайние случаи исключает. Но это в теории. На практике тело действия перехода может содержать бесконечный цикл, но перед подобным творчеством любая теория бессильна.

Тестируем схему

Итак, предположим, мы все сделали так, как это описано выше. Запустив схему на исполнение мы получим результаты, представленные на рис. 4, где на рис. 4а представлены значения НОД и моменты их вычисления, а на рис. 4б — число циклов, затраченных на их вычисление.

Если следовать числу циклов, то первый блок, на входах которого 10 и 2, выдаст результат через 6 шагов, что соответствует 6-й секунде (в случае дискретного шага, равного 1 сек), второй блок — на 22-й секунде, а выходной блок выдаст результат ровно через 5 секунд после второго блока (см. также рис. 4б). Таким образом, всего на получение результата будет потрачено 27 секунд. Если мы посмотрим на фронты сигналов и шкалу времени, то там картина явно другая.

Реализуем в ВКПа аналогичную схему с такими же входными данными. В результате мы получим совпадающие результаты в смысле значений НОД и числа циклов, но другую диаграмму сигналов (см. рис. 5). И на ней число дискретных тактов среды полностью соответствует числу циклов работы блоков.

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

Выводы

Проект весьма прост и его проблемы очевидны. Диагноз по результатам тестирования, если они (результаты) верны, конечно, может быть только один: существуют проблемы с координацией работы блоков в среде SimInTech. В данном случае они проявились при использовании типовых графических блоков. К остальным блокам в проекте вопросов нет.

Но не хотелось бы при этом и "наводить тень на плетень", представляя дело так, будто в SimInTech есть проблемы, а в том же МАТЛАБ-е их нет. Возможно, в этом конкретном случае и нет (все просто и желающие могут все проверить), но это не значит, что не будет проблем в других ситуациях. Просто потому, что "базовый бульон" в этих случаях один и тот же - модель блок-схем программ, пусть даже приправленная многопоточностью, корутинами и чем угодно еще. На вкус и запах это все та же модель блок-схем и перебить ее "ароматы" ни что ни в силах. Только если не взять за основу другой "бульон". Я даже не буду говорить какой. Но один из них нам всем уже достаточно хорошо знаком.

Литература

1. Камерон Х., Трейси Х. Параллельное и распределенное программирование на С++. М.: "Вильямс", 2004, – 267 с.

2. Майоров С.А., Новиков Г.И. Структура электронных вычислительных машин. – Л.: Машиностроение, 1979. – 384 с.

3. Вирт Н. Систематическое программирование. Введение: Пер с англ. – М.:Мир, 1977. – 184 с.

4. Об ошибке Вирта и вреде операторов цикла. [Электронный ресурс], Режим  доступа: https://habr.com/ru/articles/746674/ свободный. Яз. рус. (дата обращения 11.07.2023).