Модель параллельных вычислений

    1. Введение. Конкурентный корутинизм


    Предыдущие статьи на тему автоматного программирования были всего лишь «цветочками». «Ягодкой» автоматного программирования, т.е. ради чего нужно им заниматься, является модель параллельных вычислений на базе модели конечных автоматов. Итак, поехали…

    Стандарт С++ включил в свой состав долгожданную поддержку многопоточности [1]. Но не будем ни восхищаться этим, ни критиковать сей факт, т.к. работа с потоками отягощена таким множеством условий, оговорок и особенностей, что без реальных примеров, выявляющих проблемы многопоточности, обсуждение многопоточного программирования будет не только поспешным, но и достаточно предвзятым. Поэтому далее в основном не о потоках, а об автоматах, имея в виду, конечно, и первые.

    Язык С++ далеко не первый, дополненный конструкциями параллелизма. Еще в 60-х годах прошлого столетия Н.Виртом было предложено параллельное расширение языка ALGOL [2]. Тем не менее, последующие 60 лет так и не внесли ясности в что же считать параллельным алгоритмом и какова должна быть модель параллельных вычислений. Видимо, с этим связано и столь запоздалое расширение языка С++.

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

    В результате «спираль» развития параллелизма вернулась, похоже, к своему истоку, претерпев лишь «терминологическое развитие». Бывшие тривиальные сопрограммы стали внезапно продвинутыми «корутинами» (калька с английского coroutine), а путаница с понятиями parallel и concurrent англоязычного сегмента параллельного программирования приводит, порой, к парадоксальным вещам. Например, первое издание книги [1] от второго отличается заменой терминов «параллельное» на «конкурентное» и «многопоточного» на «параллельное». Вот и разберись в такой ситуации «who is who».

    2. Параллельная автоматная модель вычислений


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

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

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

    Тезис о том, что «часто параллельная программа сложнее для понимания, ..., а, стало быть, возрастает и количество ошибок», мягко говоря, спорен. Да, алгоритм параллельной программы может быть достаточно сложен для понимания, но при наличии теории его можно «вычислить» формально по алгоритмам компонент. А с точки зрения проектирования, реализации и сопровождения алгоритмы компонент много проще, чем алгоритм работы системы в целом. Проектируя более простые компоненты, мы допустим явно меньше ошибок, чем проектирование системы «одним куском». Более того, отлаженные компоненты могут быть частью других систем, уменьшая сложность, повышая надежность и минимизируя издержки их проектирования.

    3. Последовательный параллелизм


    В статье [3] был описан параллелизм отдельной модели конечного автомата. Ее каналы на уровне исполнения переходов задают параллельное исполнение сопоставленных им функций/методов — предикатов и действий. На параллелизм предикатов при этом не накладывается ограничений. Работая, они не конфликтуют друг с другом, т.к. не влияют на содержимое памяти. Действия же, работая параллельно, могут иметь общие входные и выходные данные, а также изменять их независимо друг от друга. А все это может быть источником неопределенности значения выходных данных.

    Корректность работы действий в описанных выше ситуациях обеспечивает теневая память. Сохраняя в ней новые значения, можно использовать в рамках даже одного действия одни и те же данные, как в качестве входных, так и выходных. В качестве примера можно привести модель генератора прямоугольных импульсов, описываемого как y = !y, где y — выход генератора. Его код на языке С++ в среде ВКПа представлен на листинге 1, а результаты работы программы демонстрирует рис. 1.

    Листинг 1. Генератор прямоугольных импульсов
    #include "lfsaappl.h"
    
    class FSWGenerator :
        public LFsaAppl
    {
    public:
        LFsaAppl* Create(CVarFSA *pCVF) { Q_UNUSED(pCVF)return new FSWGenerator(pTAppCore, nameFsa, pCVarFsaLibrary); }
        bool FCreationOfLinksForVariables();
        FSWGenerator(TAppCore *pInfo, string strNam, CVarFsaLibrary *pCVFL);
        virtual ~FSWGenerator(void) {};
        CVar *pVarY;				// выходная переменная
    protected:
        void y1();
    };
    
    #include "stdafx.h"
    #include "FSWGenerator.h"
    // state machine transition table
    static LArc TBL_SWGenerator[] = {
        LArc("s1",		"s1","--",	"y1"),			//
        LArc()
    };
    
    FSWGenerator::FSWGenerator(TAppCore *pInfo, string strNam, CVarFsaLibrary *pCVFL):
        LFsaAppl(TBL_SWGenerator, strNam, nullptr, pCVFL)
    {
        pTAppCore = pInfo;
    }
    // creating local variables and initialization of pointers
    bool FSWGenerator::FCreationOfLinksForVariables() {
    // creating local variables
        pVarY = CreateLocVar("y", CLocVar::vtBool, "локальный выход");
        return true;
    }
    // setting output signals
    void FSWGenerator::y1() {
        pVarY->SetDataSrc(nullptr, !bool(pVarY->GetDataSrc()));
    }
    


    image
    Рис. 1. Моделирование работы генератора прямоугольных импульсов в ВКПа

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

    Замечание 1. В среде ВКПа автоматы загружаются в так называемые автоматные пространства, объединяющие множество автоматов. На формальном уровне каждому такому автоматному пространству соответствует сеть автоматов в едином дискретном времени. Подобных автоматных пространств в среде может быть несколько. Также разными могут быть и значения их дискретного времени.


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

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

    Листинг 2. Генератор прямоугольных импульсов на состояниях
    #include "lfsaappl.h"
    
    extern LArc TBL_SWGenState[];
    class FSWGenState :
        public LFsaAppl
    {
    public:
        FSWGenState(TAppCore *pInfo, string strNam, CVarFsaLibrary *pCVFL):
        LFsaAppl(TBL_SWGenState, strNam, nullptr, pCVFL) {};
    };
    
    #include "stdafx.h"
    #include "FSWGenState.h"
    // state machine transition table
    LArc TBL_SWGenState[] = {
        LArc("s0",		"s1","--",	"--"),			//
        LArc("s1",		"s0","--",	"--"),			//
        LArc()
    };
    


    В новой модели состояния заменяют выходную переменную, а это, как можно видеть, резко упростило модель генератора. В результате мы получили «голый» автомат, представленный только таблицей переходов. Для отслеживания его текущего состояния «s1» в ВКПа для автомата с именем SWGenState создана переменная типа fsa(state) с именем SWGenState.(s1). Она принимает истинное значение в состоянии s1, и ложное, когда автомат находится в другом состоянии. Далее эта переменная используется уже средствами отображения данных среды ВКПа (см. тренд сигнала на рис. 2).

    image
    Рис. 2. Моделирование генератора на состояниях

    4. Модель управления параллельных вычислений


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

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

    Безусловно, результирующий автомат для сети из большого числа компонент может быть весьма объемным. Но, к счастью, чаще требуется понимание работы подсистем или сетей из небольшого числа компонент, для которых нахождение результирующего автомата не вызывает больших проблем. Рассмотренный далее пример модели RS-триггера это демонстрирует.

    Модель RS-триггера является примером простейшей параллельной системы. Особенно она интересна наличием перекрестных обратных связей. Обратные связи, или, по-другому, циклические цепи, петли, алгебраические петли (algebraic loop) и т.п. являются на текущий момент серьезной проблемой для структурных моделей параллельных систем. В общем случае она разрешается введением в разрыв петель элементов памяти. Это стандартное решение, предлагаемое теорией автоматов [4]. Такой же выход рекомендуется и в лице MATLAB. Среда ВКПа отличается тем, что ей для реализации петель не требует введения подобных дополнительных элементов. Заметим, а это очень важно, реальные схемы также в них не нуждаются (см. схему RS-триггера).

    На рис. 3 представлена простейшая модель элемента И-НЕ, из которых состоит схема RS-триггера. Она не учитывает задержки элемента, а также их тип (транспортные или инерционные задержки). Тем не менее, как минимум один такт задержки она все же содержит. Это время перехода из одного состояния в другое. Код модели демонстрирует листинг 3.

    image
    Рис. 3. Модель элемента И-НЕ

    Листинг 3. Модель элемента И-НЕ
    #include "lfsaappl.h"
    
    class FIne :
        public LFsaAppl
    {
    public:
        LFsaAppl* Create(CVarFSA *pCVF) { Q_UNUSED(pCVF)return new FIne(pTAppCore, nameFsa, pCVarFsaLibrary); }
        bool FCreationOfLinksForVariables();
        FIne(TAppCore *pInfo, string strNam, CVarFsaLibrary *pCVFL);
        virtual ~FIne(void) {};
        CVar *pVarX1;				// первый вход
        CVar *pVarX2;				// второй вход
        CVar *pVarY;				// выходная переменная
        CVar *pVarStrNameX1;		// имя первой входной переменной
        CVar *pVarStrNameX2;		// имя второй входной переменной
        CVar *pVarStrNameY;         // имя выходной переменной
    protected:
        int x1(); int x2(); int x12();
        void y1(); void y2(); void y12();
        bool bX1, bX2, bY;
    };
    
    
    #include "stdafx.h"
    #include "FIne.h"
    // state machine transition table
    static LArc TBL_Ine[] = {
        LArc("st",		"st","^x12","y12"), 		//
        LArc("st",		"s1","x12^x1",	"y1"),		//
        LArc("st",		"s1","x12^x2",	"y1"),		//
        LArc("st",		"s0","x12x1x2",	"y2"),		//
        LArc("s1",		"s0","x1x2",   "y2"),		//
        LArc("s0",		"s1","^x1",    "y1"),		//
        LArc("s0",		"s1","^x2",    "y1"),		//
        LArc()
    };
    
    FIne::FIne(TAppCore *pInfo, string strNam, CVarFsaLibrary *pCVFL):
        LFsaAppl(TBL_Ine, strNam, nullptr, pCVFL)
    { }
    
    // creating local variables and initialization of pointers
    bool FIne::FCreationOfLinksForVariables() {
    // creating local variables
        pVarX1 = CreateLocVar("x1", CLocVar::vtBool, "локальный 1-й вход");
        pVarX2 = CreateLocVar("x2", CLocVar::vtBool, "локальный 2-й вход");
        pVarY = CreateLocVar("y", CLocVar::vtBool, "локальный выход");
        pVarStrNameX1 = CreateLocVar("strNameX1", CLocVar::vtString, "name of external input variable(x1)");			// имя входной переменной
        pVarStrNameX2 = CreateLocVar("strNameX2", CLocVar::vtString, "name of external input variable(x2)");			// имя входной переменной
        pVarStrNameY = CreateLocVar("strNameY", CLocVar::vtString, "name of external output variable(y)");		// имя входной переменной
    // initialization of pointers
        string str;
        if (pVarStrNameX1) {
            str = pVarStrNameX1->strGetDataSrc();
            if (str != "") { pVarX1 = pTAppCore->GetAddressVar(str.c_str(), this);	}
        }
        if (pVarStrNameX2) {
            str = pVarStrNameX2->strGetDataSrc();
            if (str != "") { pVarX2 = pTAppCore->GetAddressVar(str.c_str(), this); }
        }
        if (pVarStrNameY) {
            str = pVarStrNameY->strGetDataSrc();
            if (str != ""){pVarY = pTAppCore->GetAddressVar(str.c_str(), this);}
        }
        return true;
    }
    
    int FIne::x1() { return bool(pVarX1->GetDataSrc()); }
    int FIne::x2() { return bool(pVarX2->GetDataSrc()); }
    int FIne::x12() { return pVarX1 != nullptr && pVarX2 && pVarY; }
    
    void FIne::y1() { pVarY->SetDataSrc(nullptr, 1); }
    void FIne::y2() { pVarY->SetDataSrc(nullptr, 0.0); }
    void FIne::y12() { FInit(); }
    


    На рис. 4 показана схема RS-триггера и его модель в форме конечно-автоматной сети. Стрелками на модели обозначены связи между автоматами сети. Здесь, с одной стороны, состояния моделей отражают состояния выходов элемента, а, с другой стороны, они же используются в качестве сигналов для организации информационных связей между параллельными процессами. Именно такая форма модели (с синхронизацией через состояния) позволяет достаточно просто найти результирующий автомат сети. Он показан на рис. 5 (о процедуре нахождения результирующего автомата подробнее см. [6]).

    Сравните [результирующий] алгоритм работы параллельной программы RS-триггера и алгоритм работы отдельного элемента И-НЕ. Разница разительная. При этом алгоритмы компонент созданы «ручками», а алгоритм параллельной системы создается неявным образом — «искусственным интеллектом» сети. Вот в чем качественное отличие параллельных программ от последовательных: изменив только связи (хотя бы одну), мы получим уже совершенно другой алгоритм работы. И это будет уже точно не RS-триггер. И, кстати, другой результирующий автомат.

    image
    Рис. 4. Схема RS-триггера и его сетевая модель

    image
    Рис. 5. Результирующий автомат сетевой модели RS-триггера

    Анализ результирующего автомата на рис. 5 дает следующее «понимание» работы параллельной программы (и реального триггера, конечно). Во-первых, при переходе из одного состояния в другое триггер обязательно перейдет через «запрещенное» состояние выходов (а что по этому поводу утверждают учебники?). Во-вторых, если загнать триггер в единичное состояние выходов (в состояние «s1w1»), а затем на входы подать две единицы, то он войдет в режим генерации, т.е. циклическое переключение между состояниями «s1w1» и «s0w0» и (а о генерации триггера вы слышали?).

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

    Замечание 2. Типовое описание работы RS-триггера дается в подавляющем числе случаев в форме таблицы истинности. Но поступать так, понимая, что триггер — это последовательностная схема, это, по сути дела, сознательно вводить в заблуждение изучающих эту тему. Ну, нет и не может быть у триггера «запрещенных состояний»! Но почему-то лишь единицы решаются открыть эту истину и уж, тем более, обсуждать проблему его генерации (см. например, [7]).


    Рис. 7 демонстрирует переключение модели триггера между его устойчивыми состояниями. Здесь уже единичное состояние входов триггера сохраняет текущее состояние выходов триггера, а при установке в ноль того или иного входа происходит переключение в противоположное состояние. При этом при переключении триггера его выходы на момент, равный одному дискретному такту, принимают одновременно единичное (кем запрещенное?) состояние.

    image
    Рис. 6. Режим генерации RS-триггера

    image
    Рис. 7. Переключение RS-триггера между состояниями

    Рассмотрим еще одну модель RS-триггера, состоящую из одного состояния и одного действия, т.е. аналогичную модели на листинге 1. Ее код демонстрирует листинг 4. У данной модели, как и у модели генератора, нет предикатов и значения сигналов без каких-либо промежуточных преобразований являются входными данными действия y1. Хорошо это или плохо? С одной стороны, кажется, что хорошо, т.к. код стал проще, но, с другой стороны,… не очень. А в причинах этого мы сейчас и разберемся.

    Листинг 4. Модель элемента И-НЕ из одного действия
    #include "lfsaappl.h"
    
    class FTwoOperators :
        public LFsaAppl
    {
    public:
        LFsaAppl* Create(CVarFSA *pCVF) { Q_UNUSED(pCVF)return new FTwoOperators(pTAppCore, nameFsa, pCVarFsaLibrary); }
        bool FCreationOfLinksForVariables();
        FTwoOperators(TAppCore *pInfo, string strNam, CVarFsaLibrary *pCVFL);
        virtual ~FTwoOperators(void) {};
        CVar *pVarX1;				// первый вход
        CVar *pVarX2;				// второй вход
        CVar *pVarY;				// выходная переменная
        CVar *pVarStrNameX1;		// имя первой входной переменной
        CVar *pVarStrNameX2;		// имя второй входной переменной
        CVar *pVarStrNameY;         // имя выходной переменной
    protected:
        int x12();
        void y1(); void y12();
        bool bX1, bX2, bY;
    };
    
    #include "stdafx.h"
    #include "FTwoOperators.h"
    // state machine transition table
    static LArc TBL_TwoOperators[] = {
        LArc("st",		"st","^x12","y12"), 		//
        LArc("st",		"s1","x12", "--"),		//
        LArc("s1",		"s1","--",  "y1"),		//
        LArc()
    };
    
    FTwoOperators::FTwoOperators(TAppCore *pInfo, string strNam, CVarFsaLibrary *pCVFL):
        LFsaAppl(TBL_TwoOperators, strNam, nullptr, pCVFL)
    { }
    // creating local variables and initialization of pointers
    bool FTwoOperators::FCreationOfLinksForVariables() {
    // creating local variables
        pVarX1 = CreateLocVar("x1", CLocVar::vtBool, "локальный 1-й вход");
        pVarX2 = CreateLocVar("x2", CLocVar::vtBool, "локальный 2-й вход");
        pVarY = CreateLocVar("y", CLocVar::vtBool, "локальный выход");
        pVarStrNameX1 = CreateLocVar("strNameX1", CLocVar::vtString, "name of external input variable(x1)");			// имя входной переменной
        pVarStrNameX2 = CreateLocVar("strNameX2", CLocVar::vtString, "name of external input variable(x2)");			// имя входной переменной
        pVarStrNameY = CreateLocVar("strNameY", CLocVar::vtString, "name of external output variable(y)");		// имя входной переменной
    // initialization of pointers
        string str;
        if (pVarStrNameX1) {
            str = pVarStrNameX1->strGetDataSrc();
            if (str != "") { pVarX1 = pTAppCore->GetAddressVar(str.c_str(), this);	}
        }
        if (pVarStrNameX2) {
            str = pVarStrNameX2->strGetDataSrc();
            if (str != "") { pVarX2 = pTAppCore->GetAddressVar(str.c_str(), this); }
        }
        if (pVarStrNameY) {
            str = pVarStrNameY->strGetDataSrc();
            if (str != "") { pVarY = pTAppCore->GetAddressVar(str.c_str(), this);	}
        }
        return true;
    }
    
    int FTwoOperators::x12() { return pVarX1 != nullptr && pVarX2 && pVarY; }
    
    void FTwoOperators::y1() {
    // reading input signals
        bX1 = bool(pVarX1->GetDataSrc());
        bX2 = bool(pVarX2->GetDataSrc());
    // setting output signals
        bY = !(bX1&&bX2);
        pVarY->SetDataSrc(nullptr, bY);
    }
    // initialization of pointers
    void FTwoOperators::y12() { FInit(); }
    


    Если мы протестируем новую модель в режиме «теневой памяти», то не увидим каких-либо отличий ее работы от предыдущей, т.е. и, переключаясь, она будет проходить через запрещенные состояния и исправно входить в режим генерации. Если же мы установим работу с данными в обычном режиме, то получим результаты, показанные на рис. 8 и рис. 9.

    image
    Рис. 8. Срыв режима генерации у модели RS-триггера

    image
    Рис. 9. Пропуск запрещенных состояний моделью RS-триггера

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

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

    Вторая программа, хотя работает с входными каналами автомата напрямую — считывает входные сигналы в рамках действия. Действия, работая с входными данными в режиме теневой памяти, записывают новые значения в теневую же память и тем самым работают с данными, действительными на начало дискретного такта. В обычном же режиме они «хватают» мгновенные значения, установленные в момент их изменения, и тем самым алгоритм попадает в зависимость от моментов изменения памяти. Подобную зависимость и демонстрирует вторая программа. И даже если бы ввели во вторую модель методы-предикаты это ни как не повлияло бы на результаты ее работы. Здесь важен не сам факт наличия методов-предикатов, а особенности их работы в рамках модели автоматного программирования.

    5. Выводы


    На примере параллельной программы RS-триггера мы рассмотрели некоторые свойства, присущие любым параллельных программ. Мы и далее на примере логических (цифровых) схем будем рассматривать те или иные общие аспекты функционирования параллельных программ. Выбор темы моделирования цифровых схем здесь не случаен. Они фактически в «рафинированном виде» представляют работу параллельных процессов. Это делает разбор нюансов параллелизма, гонки, синхронизация, тупики и т.д. и т.п., прозрачным, ясным и простым.

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

    И, похоже, поставленной цели удалось добиться. Модель RS-триггера, как один из возможных тестов систем на параллелизм [8], в этом убеждает… Как показала жизнь, все остальные параллельные программы, при условии успешного прохождения средой реализации параллелизма теста RS-триггера, работают столь же корректно, надежно и стабильно. Кстати, тот же MATLAB «тест RS-триггера» не прошел, а это говорит уже о многом…

    Литература
    1. Уильямс Э. Параллельное программирование на С++ в действии. Практика разработки многопоточных программ. Пер. с англ. Слинкин А.А. – М.: ДМК Пресс, 2012. – 672 с.
    2. Шоу А. Логическое проектирование операционных систем: Пер. с англ. – М.: Мир, 1981. – 360 с.
    3. Автоматная модель управления программ. [Электронный ресурс], Режим доступа: habr.com/ru/post/484588 свободный. Яз. рус. (дата обращения 07.01.2020).
    4. ГЛУШКОВ В.М. Синтез цифровых автоматов. М.: Физматгиз, 1962.
    5. Кузнецов О.П., Андельсон-Вельский Г.М. Дискретная математика для инженера. – 2-е изд., перераб. и доп. – М.: Энергоатом издат, 1988. – 480 с.
    6. Любченко В.С. Дизъюнктивная форма структурных автоматов. [Электронный ресурс], Режим доступа: cloud.mail.ru/public/HwsK/T95PMM8Ed свободный. Яз. рус. (дата обращения 01.02.2020).
    7. Фрике К. Вводный курс цифровой электроники. 2-е исправленное издание. – М.: Техносфера, 2004. – 432с.
    8. Любченко В.С. Фантазия или программирование? “Мир ПК”, №10/97, с.116-119. [Электронный ресурс], Режим доступа: www.osp.ru/pcworld/1997/10/158015 свободный. Яз. рус. (дата обращения 01.02.2020).
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 16

      0
      Event?
        0
        События? В связи с чем интерес?
          0
          Это то, чего вам не хватает.
            0
            Это то, без чего я прекрасно обхожусь. Но это не значит, что избегаю. Использую. Но не на уровне вычислений. Впрочем, подробнее в моей предыдущей статье — https://habr.com/ru/post/483610/
          0

          Мне кажется, или Вы переизобрели data drven progeamming?

            0
            Если имеется в виду потоковое программирование, то нет. Автоматное программирование — это другая модель. Работа автоматов никак не привязана к готовности данных. Хотя можно сделать и это. Т.е. автоматное программирование покрывает поточную модель программирования, но не наоборот.
              +1

              Чтобы быть уверенными о том, что говорим об одном и том же: вики. Я не буду утверждать, что полностью понимаю ваши статьи, не настолько знаю теорию автоматов, поэтому прошу объяснить разницу "на пальцах". Когда мы пишем в стиле data driven, получаются цепочки вызовов функций и движок, который задаёт "такты" для синхронизации. Точно так же перед функцией может быть буфер памяти, если функция требует несколько входов или для реализации асинхронности.

                0
                Похоже мы говорим об одном. Я просто брал за основу аналог на «русском вики»…

                Но лучше не «на пальцах», а на каком-нибудь простом примере. В моей статье приведена модель элемента И-НЕ. Даже две — с двумя и с одним состоянием. Возьмем для начала именно ее и именно с одним состоянием. Здесь мы имеем функцию — И-НЕ (y = !(x1&&x2). Функция она и в Африке функция, так? Т.е. и у Вас и у меня — это функции…
                Теперь об отличии. В потоковом программировании функция запускается только при готовности данных. Т.е. должны быть «готовы» данные — x1 и x2. Только тогда и будет запущена «функция И-НЕ». Т.е. процесс в этом случае пассивный, т.к. ждет готовности данных.
                Автомат — активный процесс. Он не ждет готовности, а берет то, что есть на текущий момент на входах. Т.е. он работает и когда готов только x1, или только x2, или готовы x1 и x2, да даже когда они оба не готовы.
                Теперь, если мы возьмем две функции И-НЕ и соединим их между собой по схеме триггера, то в терминах потокового программирования получим цепочку из двух функций, где выход первой «готовится» на один из входов второй, а выход второй «готовится» на вход первой функции. Имеем цепочку из двух функций, обменивающихся данными.
                Я правильно понял то, что Вы именно так бы реализовали «потоковый RS-триггер»?
                  0

                  Да, примерно так, хотя в дистиллированной формулировке DDP предполагает ациклический восходящий граф ценой дублирования функций. Когда заполняются оба входа, функция добавляется в очередь на выполнение. Активный автомат получается как асинхронная/самосинхронная схема без тактового генератора? Я вот честно не понимаю, как автомат должен работать, когда второй вход не готов, разве что эмитировать аналог null. А ещё не понимаю, что значит "берёт"? У него есть, условно, ссылка не только на входной буфер потребителя, но и на выходной буфер поставщика?

            0
            Вот картинка потоковой программы из книги Котов и др. Элементы параллельного программирования (можно скачать из инета, например, Z-Library)
            image
            Здесь вычисляются два выражения x = a*c- b*d; и y = a*d+b*c;
            Не знаю как Вы это реализуете, а я — по типу RS-триггера. У меня каждый «квадратик» будет автомат (по типу элемента И-НЕ только операции арифметические), ну и связи как у триггера. Все просто и логично.
            Как будет работать? Да просто. На входы подаем значения и через три такта на выходах в динамике получаем результаты. Т.е. все работает как обычная логическая (цифровая) схема.
            Будут, наверное, гонки до установившегося значения (в течение трех тактов). Но без проблем сделать автоматы, которые бы работали по готовности.
            Я вот честно не понимаю, как автомат должен работать, когда второй вход не готов

            В данной ситуации он (автомат) и не думает о готовности. Он, поскольку активный, постоянно (с дискретным временем) «лопатит» все что поступает на входы и выдает на выход. Но, еще раз, чтобы было по готовности данных, то просто автомат будет посложнее, т.к. нужно будет синхронизироваться с входными данными.
            «Тактовый генератор», конечно, есть. Нужно же как-то реализовать модель дискретного времени. Он он также «зарыт» как тактовый генератор процессора. У него-то он тоже есть, но Вы о нем просто не задумываетесь. Так и я — «рисую» автомат (см. тот же Листинг 3), а что и как тактировать решает уже среда интерпретации автоматов, т.е. ВКПа.
            По поводу «берет». См. Листинг 3. Пусть вход x1. Есть ссылка на переменную и есть предикат x1(), который с ней работает. Но вместо ссылки это могла быть и переменная типа bool. Вы, кстати, какой язык используете? Для С++ все, надеюсь, просто следует из приведенного кода.
              0

              На плюсах не пишу, но читаю. Можете сказать, что происходит в pVarX1->GetDataSrc() и как обрабатывается LArc? Ну и содержания lfsaappl.h я ни в одной из статей не нашёл. В идеале хотел бы увидеть программу, которая использует простой И-НЕ, принимая на вход два аргумента и выдавая в консоль результат.

              0
              Можете сказать, что происходит в pVarX1->GetDataSrc()

              Замечу, что сначала создается объект типа CVar — локальная переменная автомата в теневой памяти:
              pVarX1 = CreateLocVar(«x1», CLocVar::vtBool, «локальный 1-й вход»);
              Она становится доступной не только на уровне кода, но и на уровне визуальной средs исполнения автоматов ВКПа.
              GetDataSrc() — метод чтения ее значения;
              SetDataSrc(...) — метод установки ее значения.
              как обрабатывается LArc?

              Объекты типа LArc создают внутреннюю [битовую] структуру, необходимую для быстрой интерпретации автомата с необходимыми ссылками внутри этой структуры. Далее ее адрес передается базовому автоматному объекту типа LFsaAppl.
              LFsaAppl.h
              #ifndef LFSAAPPL_H
              #define LFSAAPPL_H
              
              #include <QObject>
              #include <string>
              #include <list>
              using namespace std;
              
              #include "./FSA/task.h"
              #include "./SQM/larc.h"
              #include "./FSA/LFsaHdr.h"
              //#pragma warning( disable: 4251 )	// давить warning
              #include "./VARFSA/csetlocvar.h"
              
              #include "./VARFSA/Var.h"
              typedef unsigned int UINT;
              extern string itoa(int n);
              
              class LFsaAppl;
              class TNetFsa;
              class LListState;
              class LFsaArc;
              class WSP;
              typedef int(LFsaAppl::*FncClassX)();
              typedef void(LFsaAppl::*FncClassY)();
              //+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
              //                             fs_tbl
              //+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
              class fs_tbl {
               public:
                LListState* adt; FncClassX* adx; FncClassY* ady;
              public:
                fs_tbl(LListState *pAdt, FncClassX *pAdx, FncClassY *pAdy);
                ~fs_tbl();
              };
              //+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
              //                             fs_dbg
              //+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
              class fs_dbg {
               public:
                  string nameFsa;
                  string nameFsaProcess;
                  int trace;
                  fs_dbg(string szName, int nTrace=0);
                  ~fs_dbg();
              };
              //+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
              //                             LFsaAppl
              //+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
              class CSetVarLDV35;
              class CFDelay;
              class CVarPrmProc;
              class CVarFsaLibrary;
              class CVarFSA;
              class TAppCore;
              class LFsaAppl:public fs_tbl, public fs_dbg  {
              public:
                  virtual string	CurrentState(int nNum=-1);
                  // локальные переменные
                  // реакция на левую кнопку мышки
                      virtual void VirtLButtonDown();
                      CVar *pVarIfLButtonDown;
                      bool bIfLbuttonDown;
                  //
                  // реакция на правую кнопку мышки
                      virtual void VirtRButtonDown();
                      CVar *pVarIfRButtonDown;
                      bool bIfRbuttonDown;
                  //
                  string			WhatState(int n=-1);
                  int				FGetRange();
                  LFsaAppl*		FGetPtrFsaAppl(string strNameVarFSA);
                  bool			FIsActiveParDelay();
                  void			FCreateDelay(int nDelay);
                  void			FCreateParDelay(int nDelay);
                  bool			FSavVariable(CVar* pV);
                  virtual bool	FCopyFSA(string strPatchSrc, string strPatchDst, bool bIfInfoDlg = true);
                  virtual bool	FDeleteFSA(string strPatchSrc, string strPatchDst, bool bIfInfoDlg = true);
                  bool			FDbgGetViewArc();
                  bool			FDbgGet();
                  bool			FDbgSet(bool b);
                  bool			FDbgSetViewArc(bool b);
                  virtual bool	FSetLocking(bool bSet, LFsaAppl *pOwner, string strNameVar);			//	установка/сброс блокировки определенным процессом
                  virtual void	FDbgViewCurrentArc();
                  virtual string	FDbgViewArc(UINT id = 29003);
                  virtual string	FDbgViewState(UINT id = 29003);
                  void			FUpdateVariable();                                      // обновить локальные переменные
                  void			FDrawVariable();                                        // отобразить/нарисовать локальные переменные
                  virtual bool	FCreationOfLinksForVariables();					// создание ссылок для переменных процесса
                  virtual bool	FUpdateLinks(string name, int nT);				// отредактировать связи процесса (имя процесса, тип редакции)
                  virtual bool	FInit();
                  virtual LFsaAppl* Create(CVarFSA *pCVF);
                  LFsaAppl();
                  LFsaAppl(LArc* aT, string name, CVarFSA *pCVF, CVarFsaLibrary *pCVFL, int trace=0);
                  LFsaAppl(LArc* aT, string name);
                  virtual ~LFsaAppl();
                  int virtual x1();   int virtual x2();   int virtual x3();
                  int virtual x4();   int virtual x5();   int virtual x6();
                  int virtual x7();   int virtual x8();   int virtual x9();
                  int virtual x10();  int virtual x11();  int virtual x12();
                  int virtual x13();  int virtual x14();  int virtual x15();
                  int virtual x16();
                  int virtual x17();  int virtual x18();  int virtual x19();
                  int virtual x20();  int virtual x21();  int virtual x22();
                  int virtual x23();  int virtual x24();  int virtual x25();
                  int virtual x26();  int virtual x27();  int virtual x28();
                  int virtual x29();  int virtual x30();  int virtual x31();
                  int virtual x32();
                  void virtual y1(){}   void virtual y2(){}   void virtual y3(){}
                  void virtual y4(){}   void virtual y5(){}   void virtual y6(){}
                  void virtual y7(){}   void virtual y8(){}   void virtual y9(){}
                  void virtual y10(){}  void virtual y11(){}  void virtual y12(){}
                  void virtual y13(){}  void virtual y14(){}  void virtual y15(){}
                  void virtual y16(){}
                  void virtual y17(){}  void virtual y18(){}  void virtual y19(){}
                  void virtual y20(){}  void virtual y21(){}  void virtual y22(){}
                  void virtual y23(){}  void virtual y24(){}  void virtual y25(){}
                  void virtual y26(){}  void virtual y27(){}  void virtual y28(){}
                  void virtual y29(){}  void virtual y30(){}  void virtual y31(){}
                  void virtual y32(){}
                  void virtual MooreAction(){}
                  void virtual ELSE();
                  void virtual MealyLoop();
              
                  virtual double* GetPtrDblArray(int nNum, int *nSize);
                  virtual double* SetPtrDblArray(int nNum, double *pArray, int *nSize);
                  virtual int* GetPtrIntArray(int nNum, int *nSize);
                  virtual int* SetPtrIntArray(int nNum, int *pArray, int *nSize);
                  virtual char* GetPtrCharArray(int nNum, int *nSize);
                  virtual char* SetPtrCharArray(int nNum, char *pArray, int *nSize);
                  virtual QByteArray* GetPtrByteArray(int nNum);
              
                  CVarPrmProc* GreateParameters();
                  CVarPrmProc* GetPtrParameters();
                  virtual void CleaningWindow();
                  virtual CVar* FSetPtrVarParameter(LFsaAppl *pLFsa, CVar *pVar, int  nNum);
                  virtual CVar* FGetPtrVarParameter(LFsaAppl *pLFsa, int  nNum);
                  virtual double FSetParameter(LFsaAppl *pLFsa, double d, int  nNum);
                  virtual string FSetParameter(LFsaAppl *pLFsa, string str, int  nNum);
                  virtual void FUpdateParameter(LFsaAppl *pLFsa, int  nNum);
                  virtual double FUpdateDataParameter(LFsaAppl *pLFsa, int  nNum);
                  virtual string FUpdateStringParameter(LFsaAppl *pLFsa, int  nNum);
                  virtual double FGetDataParameter(LFsaAppl *pLFsa, int  nNum);
                  virtual string FGetStringParameter(LFsaAppl *pLFsa, int  nNum);
                  virtual void ExecuteThreadStep();
                  virtual void WaitForThreadToFinish();
                  bool	IfCall();
                  void	FSetSleep(long lS);
                  long	FGetSleep();
                  void	FStart();
                  void	FStop();
                  bool	FIfStop();
                  void	FContinue();
                  TASK*	FLoad(TNetFsa *NetFsa, string strProc, int pri, bool bNot, TAppCore *pCore, CVarFSA *pVar);
                  void	FCancelTsk();
                  TASK*	FGetTask();
                  virtual string	FGetState(int nNum=-1);
                  string	FGetNextState();
                  string	FGetStateUp();
                  void	FSetNameFsa(const string nam);
                  void	FSetNameProcess(const string nam);
                  string	FGetNameFsa() const;
                  string	FGetNameProcess() const;
                  string	FGetNameVarFSA() const;
                  LFsaAppl*   FCall(LFsaAppl*);
                  int		FIsActiveTask();
                  bool 	FIfOk();
                  void 	FSetOk(int nOk=1, const char* pch=nullptr);
                  void 	FSetError(int nOk=1, const char* pch=nullptr);
                  const char*	FGetError(int* pn=nullptr);
                  const char* FGetOk(int* pn=nullptr);
                  void 	FClearOk();
                  void 	FClearError();
                  void	FPrefixErrOk(string &str);
                  void	FPrefixErrOk(char str[]);
                  CLocVar*    GetAddressVar(string nam);
                  CLocVar*    CreateLocVar(string namVar, unsigned int unType, string strComment, bool bSave=true);
                  long	GetNumberOfTasks(long *l);
                  TNetFsa*	GetPointerToNet();
                  string	strGetCurrentArc(WSP *p=nullptr);
                  string	strCurrentArc;
               private:
                  inline int X1();	inline int X2();	inline int X3();  inline int X4();
                  inline int X5();	inline int X6();	inline int X7();  inline int X8();
                  inline int X9();	inline int X10();	inline int X11(); inline int X12();
                  inline int X13();inline int X14(); inline int X15(); inline int X16();
                  inline int X17();inline int X18(); inline int X19(); inline int X20();
                  inline int X21();inline int X22(); inline int X23(); inline int X24();
                  inline int X25();inline int X26(); inline int X27(); inline int X28();
                  inline int X29();inline int X30(); inline int X31(); inline int X32();
              
              public:
                  TASK*		CALTSK(TNetFsa *NetFsa, int pri);
                  LFsaHdr		var;
                  LFsaHdr		*pLFsaHdr;
                  LFsaAppl	*pFsaApplError;
                  int			nFsaPriority;
                  string		strNameVarFsaNew;
                  TAppCore	*pTAppCore;
                  CVarFSA		*pCVarFSA;
                  CVarFsaLibrary	*pCVarFsaLibrary;
                  CVarPrmProc *pVarPrmProc;
                  CSetLocVar	*pCSetLocVar;
                  CSetVarLDV35    *pCSetVarLDV35;
                  int	nModeVar;
                  LArc		*pTBL;
                  LFsaAppl	*pNestedAutomaton;
                  LFsaAppl	*pMainAutomaton;
              
              protected:
                  LFsaArc		*ADT, *ARC_T, *ARC_B;
                  unsigned long M_X, M_XY, BAZ_XY;
                  LListState* SqmTable;
                  FncClassX	X[32];
                  FncClassY	Y[32];
                  WSP*		pWSP;
                  bool		bIfViewArc;
                  bool		bIfDebug;
                  CFDelay		*pParFDelay;
                  CFDelay		*pCFDelay;
                  bool                bIfRunThread{false};
              private:
                  unsigned long p2pck;
                  string		strOk;
                  string		strError;
                  int			nOkProcess;
                  int			nErrorProcess;
                  TNetFsa		*pTNetFsa;
                  bool		bIfCall;
                  friend class WSP;
                  friend class TNetFsa;
              };
              typedef list<LFsaAppl> CArrayLFsaAppl;
              typedef list<LFsaAppl>::iterator CIteratorLFsaAppl;
              typedef list<LFsaAppl*> CArrayILFsaAppl;
              typedef list<LFsaAppl*>::iterator CIteratorILFsaAppl;
              
              #endif // LFSAAPPL_H
              


              Код простого И-НЕ. Без теневой памяти и локальных переменных. Обращение к нему — через свойства класса, где bX1, bX2 — входы элемента, bY — выход.
              Простой И-НЕ
              
              #include "lfsaappl.h"
              
              class FIneSimple :
                  public LFsaAppl
              {
              public:
                  LFsaAppl* Create(CVarFSA *pCVF) { Q_UNUSED(pCVF)return new FIneSimple(pTAppCore, nameFsa, pCVarFsaLibrary); }
                  FIneSimple(TAppCore *pInfo, string strNam, CVarFsaLibrary *pCVFL);
                  bool bX1, bX2, bY;
              protected:
                  int x1(); int x2();
                  void y1(); void y2();
              };
              
              #include "stdafx.h"
              #include "FIneSimple.h"
              // state machine transition table
              static LArc TBL_IneSimple[] = {
              // установка в правильное начальное состояние
                  LArc("st",		"s1","^x1",	"y1"),			//
                  LArc("st",		"s1","^x2",	"y1"),			//
                  LArc("st",		"s0","x1x2","y2"),			//
              // модель И-НЕ
                  LArc("s1",		"s0","x1x2","y2"),			//
                  LArc("s0",		"s1","^x1",	"y1"),			//
                  LArc("s0",		"s1","^x2",	"y1"),			//
                  LArc()
              };
              
              FIneSimple::FIneSimple(TAppCore *pInfo, string strNam, CVarFsaLibrary *pCVFL):
                  LFsaAppl(TBL_IneSimple, strNam, nullptr, pCVFL)
              {
              }
              
              int FIneSimple::x1() { return bX1; }
              
              int FIneSimple::x2() { return bX2; }
              
              void FIneSimple::y1() { bY = true; }
              //
              void FIneSimple::y2() { bY = false; }
              



                0

                Можете подсказать, где лежит LFsaAppl.h и кто автор? Как-то не совсем понятно, как скомпилировать и использовать код из статей. Я погуглил, понял, что это не ваша самописка, похоже, это часть fsamdi, которая кочует из рук в руки, но на гитхабе не появляется. Кто, как и я, хотел бы объяснения работы на пальцах АП в качестве старта, чтобы понимать, что lws0954 привнёс нового, вот статья 2000го из журнала "Мир ПК" про задачу Майхилла.

                0
                Можете подсказать, где лежит LFsaAppl.h и кто автор?

                Разрешите представиться. Я и есть. Среда ВКПа это современное развитие того, что раньше называлось КА-технология (См. раздел КА-технология на сайте SoftCraft www.softcraft.ru/auto).

                По поводу выложить (естественный вопрос). Во-первых, как-то не дошло дело до гитхаба и, если честно, просто не знаю, не пробовал это делать. А, во-вторых, после ухода с Visual Studio и MFC на Qt Creator и, собственно, Qt нужно просто довести до полностью рабочего варианта. Я, конечно, не испытываю проблем, но нужно, чтобы это же «испытывали» и другие.
                чтобы понимать, что lws0954 привнёс нового
                Идея в основном осталась той же, но «по мелочевке» набежало достаточно много. Например, я не помню уже была ли там теневая память. А ее наличие очень и очень важно. Это по-крупному. А сама концепция автоматной модели (в лице базового класса LFsaAppl) по большому счету не изменилась. Но можно, конечно, просто сравнить заголовки lfsaappl.h, чтобы понять что добавилось нового по сравнению с 2000-м годом. Больше развитие связано со средой. Сейчас в ней можно визуально проектировать автоматы без всякого С++. Правда, не так эффективно, как на языке, но зато быстро и прямо на лету.
                PS
                В попытках вспомнить даже ностальгия «прошибла» :)
                  0

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

                  0
                  а в этой серии статей академичнее
                  Собственно такая цель и поставлена. Популярно я много написал и, видимо, пришла пора «академичности» ;)
                  Если не разберусь при отладке, не подскажете именно по реализации?
                  Конечно. Сделаю это с удовольствием ;)

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

                  Самое читаемое