🚁 🕳️ 👨🏼‍🤝‍👨🏻 并行计算模型 🏚️ 👨🏾‍⚖️ 👨🏼‍💻

1.简介。竞争性的白痴症

以前有关自动编程的文章只是“花”。自动编程的“浆果”，即对于您需要做的是基于状态机模型的并行计算模型。因此，让我们开始吧……

C ++标准包括了人们期待已久的对多线程的支持[1]。但是我们既不会赞美它，也不会批评这个事实，因为在如此多的条件，注意事项和功能的共同作用下，使用线程的工作受到很大的影响，如果没有现实生活中的例子揭示多线程问题，那么对多线程编程的讨论将不仅草率，而且也带有偏见。因此，在下文中，主要不是自动流动，而是自动机，当然首先要牢记。

C ++语言与并行语言结构相辅相成。早在上世纪60年代，N。Wirth提出了ALGOL语言的并行扩展[2]。但是，未来60年仍未弄清应将什么视为并行算法以及应将什么作为并行计算模型。显然，C ++语言的这种迟来的扩展也与此相关。

ALGOL语言的长期结构及其在C ++语言中更现代的类似物，都仅表示不引入并行算法模型的结构并行化方法。为了证明这一点，可以说，过去一段时间来创建这种正式的计算模型的尝试都失败了。可以说，同样的陪替氏网络并不能证明人们寄予厚望。

结果，并行性发展的“螺旋”似乎已经回到其源头，仅经历了“术语发展”。前琐碎的协程突然变成了高级的“协程”（英语协程的描图纸），并且在并行编程的英语部分中对并行和并发的概念的混淆有时会导致自相矛盾的事情。例如，本书[1]的第一版与第二版的不同之处在于，将“并行”替换为“竞争性”，将“多线程”替换为“并行”。因此，在“谁是谁”的情况下弄清楚这一点。

2.并行自动机计算模型

可能没有人会怀疑编程开发中的下一个定性步骤与向并行计算模型的转换有关。但是，这是否会因现有计算模型的进化发展而发生，或者是否将是根本不同的模型，仍在讨论中。而且如果理论家仍在争论，那么程序员的实际动力已经在使用结构化方法来并行化程序。

职责分离和提高生产率被认为是使用并发的唯一原因。至少，它们或它们的组合最终会减少或尝试减少所有其他[1]。但是有一个很少被谈论的原因，但是由于这个原因，通常值得进行并行编程。确实，可以通过纯粹的硬件方法来提高速度，并且通过并行执行职责分离与银行雇员的日常工作以列出其正式职责的方式相同。而且只有并行算法才能使我们克服任务的复杂性并提高程序的可靠性。所有这些都与关于多线程编程的普遍观点相反，后者将任何并行程序变成了复杂且不可靠的软件产品。

并行系统由许多具有并行功能且主动交互的组件，对象，代理等组成，它实现的算法的确定方式并非由各个组件的算法确定（尽管它们当然是），而是由组件的数量，数量和他们之间的联系。为了控制这种复杂性并理解并行系统操作算法，您不仅需要并行计算模型，还需要具有（尤其是）适当理论的模型。

轻率地说，“并行程序常常更难理解……因此错误的数量在增加”这一论点值得商bat。是的，并行程序算法可能很难理解，但是如果有一个理论，可以使用组件算法对其进行“计算”。从设计的角度来看，组件算法的实现和维护要比整个系统的算法简单得多。当设计更简单的组件时，显然，与设计一个系统相比，我们犯的错误更少。此外，调试后的组件可以成为其他系统的一部分，从而降低了复杂性，提高了可靠性并最小化了其设计成本。

3.串行并发

文章[3]描述了一个有限状态机模型的并行性。它在转换执行级别的通道指定与其关联的功能/方法（谓词和动作）的并行执行。同时，对谓词并行性没有任何限制。在工作时，它们不会相互冲突，因为不会影响内存的内容。并行操作的动作可以具有共同的输入和输出数据，也可以彼此独立地进行更改。所有这些都可能成为输出数据值不确定性的来源。

在上述情况下正确执行操作可提供影子存储。通过在其中存储新值，甚至可以在一个动作中使用相同的数据作为输入和输出。一个例子是矩形脉冲发生器的模型，描述为y =！Y，其中y是发生器的输出。清单1中显示了它在VKPa环境中的C ++代码，该程序的结果如图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()));
}

图。 1.在VKPA中模拟矩形脉冲发生器的操作

在这种情况下，电机具有一种状态，该状态具有以条件y1标记的循环形式的无条件过渡（以破折号代替输入条件的过渡），该状态实现了输出变量的反转，从而在动力学中形成了矩形脉冲。在自动机模型的框架内，可以通过设置自动机加载到其中的自动机空间的离散时间的间歇值来控制脉冲信号的频率。

1. , . . . .

控制自动机离散时间和存在许多自动机空间的能力不是VKPa环境的唯一但重要的独特属性。使用它们，您可以优化并行程序的性能。例如，应将实现数据可视化和用户对话的机器放置在缓慢的自动机空间中，并应根据优先级及其所需的速度等在自动机空间中分配应用程序进程。等等

在自动机模型的框架内，发生器输出的值很容易与模型的当前状态相关。清单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()
};

在新模型中，状态替换了输出变量，可以看出，这大大简化了生成器模型。结果，我们得到了一台“裸机”，仅由转换表表示。为了在VKPa中监视其当前状态“ s1”，为名称为SWGenState的计算机创建了fsa（状态）类型的变量，名称为SWGenState（S1）。在状态s1中，它的值为true；在机器处于其他状态时，其值为false。此外，该变量已经通过显示VKPA环境的数据使用（请参见图2中的信号趋势）。

图。2.对状态生成器建模

4.并行计算控制模型

此外，朝着建立并行过程模型的方向发展，使用许多同时起作用并相互作用的有限状态机是合乎逻辑的。自动机网络。在这种情况下，会出现选择网络时间模型的问题，该问题对于所有机器可能都是相同的，或者在限制范围内，每个机器都可能是单个的。在VKPa中，选择时倾向于一次（有关自动机同步网络的更多详细信息，请参见[5]）。

一次的选择允许您创建具有自动机的合成和分解操作的自动机代数。使用第一个，您可以找到生成的自动机，它给出了并行系统操作的准确概念。这里值得回顾一下关于并行程序的“理解的复杂性”的论文。合成操作的存在使我们能够解决并行程序的“理解问题”。

当然，由大量组件组成的网络所产生的自动机可能非常庞大。但是，幸运的是，更经常需要了解少量组件的子系统或网络的操作，为此，找到最终的自动机不会引起大问题。下面的RS触发器模型示例对此进行了演示。

RS触发模型是简单并行系统的一个示例。在存在交叉反馈的情况下，这尤其有趣。反馈或循环链，循环，代数循环等。对于并行系统的结构模型，当前是一个严重的问题。在一般情况下，可以通过引入存储元件的间隙环来实现。这是自动机理论提出的标准解决方案[4]。建议在MATLAB方面使用相同的输出。 VKPa环境的不同之处在于，它不需要引入此类其他元素即可实现循环。请注意，这非常重要，实际电路也不需要它们（请参阅RS触发器电路）。

在图。图3给出了AND-NOT元素的最简单模型，它由RS触发电路组成。它不考虑元素延迟及其类型（运输或惯性延迟）。但是，它仍然包含至少一个延迟节拍。这是从一种状态过渡到另一种状态的时间。清单3显示了模型代码

。3.元素的模型AND NOT

清单3.元素模型AND NOT

#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触发器程序的[结果]算法和单独的AND-NOT元素的运算算法。区别是惊人的。在这种情况下，组件算法是由“句柄”创建的，而并行系统算法是由网络的“人工智能”隐式创建的。这是并行程序和顺序程序之间的质的区别：仅更改通信（至少一个），我们将获得完全不同的工作算法。而且，它将绝对不再是RS触发器。顺便说一下，还有另一个自动机。

图。 4.方案的RS-FF和网络模型的

图。 5.生成的机器网络模型RS触发

图中生成的自动机的分析。图5给出了并行程序的以下“理解”（当然还有真正的触发器）。首先，当从一种状态切换到另一种状态时，触发器必然会经过输出的“禁止”状态（教科书对此有何评论？）。其次，如果将触发器驱动到单个输出状态（状态为“ s1w1”），然后将两个单元馈入输入，则它将进入生成模式，即状态“ s1w1”和“ s0w0”之间的循环切换（您是否听说过触发器的产生？）。

在真实触发中也会发生通过禁止状态的转换，但是由于真实元素的延迟差异，生成模式是不可能的。图。图6显示了触发触发模型的生成模式，只要存储输入中的单位就存在。

备注2.在绝大多数情况下，以真值表的形式给出了RS触发操作的典型描述。但是，这样做是要理解触发器是一个顺序方案，实际上，这是故意误导那些研究此主题的人。好吧，没有触发器不能有“禁止状态”！但是出于某种原因，只有少数人决定发现这个真理，尤其是讨论其产生的问题（例如，参见[7]）。

图。图7示出了触发模型在其稳定状态之间的切换。此处，触发器输入的单个状态保留了触发器输出的当前状态，并且当该输入或那个输入设置为零时，它将切换到相反的状态。同时，当触发器被切换时，它的输出等于一个离散量，此刻同时处于单个（被谁禁止？）状态。

图。 6. RS-触发生成模式

图。 7.在状态之间切换RS触发

考虑另一种由一个状态和一个动作组成的RS触发模型，即类似于清单1中的模型。清单4中显示了其代码。该模型与生成器模型一样，没有谓词，并且没有任何中间转换的信号值被输入到动作y1。这是好事还是坏事？一方面，这似乎很好，因为代码变得更简单了，但是另一方面...并非如此。我们现在将了解其原因。

清单4.一个动作的NAND元素模型

#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(); }

如果我们在“影子内存”模式下测试新模型，那么我们将不会发现它与前一个模型的操作有任何不同，即，切换后，它将进入禁止状态并定期进入发电模式。如果我们以通常的方式设置数据的工作，我们将得到如图10所示的结果。 8和图。 9.

图8. RS触发模型的生成模式失败

。 9.通过RS触发

模型跳过禁止状态为什么第一个模型，无论使用内存的工作方式如何，都会显示稳定的结果，而第二个模型会改变行为？原因是谓词。第二个模型没有谓词，这对其行为至关重要。但是谓词的存在/不存在如何以及为什么影响并行程序操作算法？

像自动机程序一样，AND-NOT元素的程序模型具有两个输入通道和一个输出通道。它们必须匹配两个谓词和一个动作。第一个程序与此完全一致。解释自动机描述的VKPa内核不仅执行特定自动机的所有谓词，还执行整个自动机空间的所有谓词，然后才执行所有操作。在这种情况下，以何种顺序执行动作，模拟并行性，以及它们在内存中使用的任何模式下，自动机当前时钟周期的谓词结果均不取决于它们（动作）。因此，第一个程序产生相同的结果。

第二个程序尽管直接与机器的输入通道一起使用，但作为操作的一部分，读取输入信号。动作在影子存储器模式下使用输入数据，将新值写入影子存储器，从而使用在离散时钟周期开始时有效的数据。在通常模式下，它们会``抓住''更改时建立的瞬时值，因此算法变得依赖于内存更改的时刻。第二个程序证明了类似的依赖性。即使将谓词方法引入第二个模型，也不会对其工作结果产生任何影响。这里重要的不是谓词方法的存在，而是它们在自动机编程模型框架中的工作特征。

5。结论

以并行RS触发程序为例，我们检查了任何并行程序固有的一些属性。我们将继续考虑并行程序功能的某些一般方面，作为逻辑（数字）电路的示例。在此处选择数字电路建模的主题并非偶然。实际上，它们以“改进的形式”表示并行过程的工作。这将分析并发，竞争，同步，死胡同等细微差别。等透明，清晰，简单。

同时，无论您如何称呼编程（“竞争”或并行），无论您使用“协程”，协程，线程还是机器进行编程，在所有实现中，[并行]程序的结果都必须相同。在CPSU框架内的并行程序自动模型追求的是这个目标，也只有这个目标。
无论对VKPa环境的自动机解释的核心实现方式做出何种假设，所有这些都是“推测”，因为自动程序的工作结果不应与计算模型的实现相关联。它可以是软件（如现在）或硬件（如我希望的那样），可以在一个内核或它们的集合上实现，可以是单线程或多线程版本等。等等所有这些都不会影响并行自动程序的结果。

而且，似乎已经实现了目标。作为并行系统可能的测试之一[8]，RS-trigger模型使我们相信了这一点...正如生活所示，所有其他并行程序，只要环境已成功通过RS-trigger测试并行性实现，就可以正确，可靠且稳定地工作。。顺便说一句，没有通过相同的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).

并行计算模型

1.简介。竞争性的白痴症

2.并行自动机计算模型

3.串行并发

4.并行计算控制模型

5。结论

More articles: