Get best of the week

NPS, conveyor, automatic computing and again ... coroutines

1. Again about coroutines


In my previous article, dear Habr, I only touched on the problems of knowledge of modern programming. The ensuing discussion only confirmed the spontaneous fears that arose: the notorious “theoretical foundations” immediately became a source of disagreement. The fact that they (disagreements) might not exist or they would be of a different nature does not seem to bother the bulk of "real" programmers. Moreover, perhaps it is not particularly interesting, because programmers are stimulated mainly by one interest - code, code, and only code. Well, almost "as the doctor prescribed" [1] ...

Touching on the subject of corutin in my article and comments, I did not at all dream about how much they are in the “current” trend. Amazed, however, the "backing tracks" of my comments with or without. For what, they say, programmers? However, it seems to me that everything became clear after reading the article about the newly approved C ++ 20 and the prospects for its further development [2]. To my amazement, it turned out that coroutines are in the forefront of the present and future innovations of my beloved C ++ (see also the CppCoro library ).

Well, tell me, is it possible to take seriously and / or calmly a brow who, it seems, imagines himself to be anyone? Hit what is called! :(

The background of my acquaintance with coroutines (I will call them all the same in the old way) is as follows. There was a need to parallelize, but something suitable was not. I had to invent, studying the available literature. As a result, coroutines were rejected immediately, and threads later. The reason is that both of them are structural methods of parallelizing programs, and not computational models. But I didn’t want that.

The description of what I finally came to is given in my previous articles on Habré. This conversation is far from over, but for now, how have coroutines been remembered, since they have already become the subject of such a heated discussion? The only thing is the “points” of stopping / switching processes. Unlike threads, they made it possible to predict the behavior of processes that simulate parallel operation. In theory, this also reduced system losses for the implementation of parallelism. But, nevertheless, in sum, all this fundamentally something did not change. And since the “dots” were simply imitated by the states of the automaton programming (AP) model, my acquaintance with coroutines was completed for seven.

But I could not assume that the incarnation of coroutines, now called coroutines, would so overtake me. From this, and mine, possibly unjustified “attacks” on them, for which I absolutely sincerely apologize to the apologists of Corutin. Probably hurried. Nevertheless, the newly discovered circumstances did not affect my attitude to coroutines. For the new code, for reasoning in their favor, I never saw anything fundamentally new. However, I want to note that coroutines are nevertheless closer and clearer to me than threads, because contain, as I said above, an analog of the set of internal states of finite automata (CA).

However, stop repenting. Let us return to automata that completely cover the “coroutine theme”. Next, I will present the capabilities of the AP associated with the modeling of parallel models that are quite well-known in theory and practice - tiered parallel and pipeline models of algorithms. Their automatic solution, in my opinion, looks more visual, natural and simple than it would be based on the same coroutines.

2. Tier-parallel and pipeline forms of algorithms


Suppose you need to calculate the expression:

y = (((a + b) * (c + d)) + ((e * f) + (q + h))).

Also, let the operation execution time be defined, defined in arbitrary units of discrete time — measures where addition takes 1 measure, and multiplication takes 5 measures.
Based on the logic of calculating the expression, the execution time of the operations, and the number of intermediate variables, in one embodiment, the distribution of operations by tiers and the number of tiers itself can look, for example, as follows:

t1 = a + b; t2 = c + d; t3 = e * f; t4 = q + h;
Tier0: t1; t2; t3; t4;
Tier1: t5 = t1 * t2; t6 = t3 + t4;
Tier2: t7 = t5 + t6;

Graphically this is shown in fig. 1, which shows two options for the distribution of calculations in tiers and affixed calculation time in ticks. Their comparison shows that in the general case, a decrease in the number of tiers does not automatically mean a reduction in the computation time.

image
Fig. 1. Tier-parallel form of calculating an expression.

But one more option can be considered, which is already represented by a multitude of tier-parallel forms that solve a single problem. In fig. Figure 2 shows just such a solution. The computation time has decreased. Parallelization of NPS can also be attractive taking into account their execution on multiprocessor systems.

image
Fig. 2. Parallel NPS

If you rotate the JPF graph, then you can get the scheme of pipeline computing. In it, the elements of the conveyor will be tiers, the operating time of which is reduced to the slowest tier. In fig. Figure 3 shows such a pipelining scheme of the original expression.

image
Fig. 3. Pipeline model

Since for this example the discrete conveyor time is 5 clock cycles, the calculation time will be even worse than the worst version of the NPS. Advantages of the pipeline only in the continuity of the calculations.

3. An automaton model for calculating expressions


If you remove the restrictions on the synchronization of operations, then the NPS can be turned into a circuit that will generate the result as a pipeline, but without restrictions related to the sequence and time of operations. Such a logical network diagram with a demonstration of the addition operation (the implementation of multiplication is similar) in the form of a spacecraft network model is shown in Fig. 4.

image
Fig. 4. Calculations of expressions based on a network of finite state machines

You can see that the network will constantly produce a result with a delay of 7 clock cycles, i.e. as well as the fastest NPS model (Fig. 7). Its disadvantages include output instability associated with data races. For example, a simultaneous change in the value of variables in pairs of variables g, h and e, f will lead to a change in t4 at the next clock cycle, after one clock cycle to a change in variable t6 and another clock cycle to the output variable t7 (see Fig. 1 and Fig. 4) . At the same time, after 5 clock cycles, the variable t3 will change, which will lead to a change and the output of the finally established values ​​of the variables t6, t7.

image
Fig. 5. Modeling of NPS with a network of automata

In fig. Figure 5 shows how the introduction of an additional block makes it possible to simulate the computation of NPS. Similarly, you can simulate the model of pipelined computing, as well as block the change in output associated with data races.

3. Conclusions


It would be strange to doubt that the above “pictures” cannot be realized using coroutines. That's just, to be honest, I would not want to do this. For me, it’s much easier to create automata that implement the necessary operations, and then, changing only their number and the relationships between them, implement the calculation of any expression.

I will not tire of repeating that I am attracted to the concept of visual programming implemented in the Stateflow package in MATLAB. Here you can also create the necessary automaton operations, and then, using them as standard blocks, “draw” a calculation scheme for any expression, which after compilation will turn into a working program (for example, in the same C ++). At the same time, during the design process, visualization and debugging tools will be available that are specific to the automated programming technology.

True, the question may arise - why permanent links to a certain unknown environment of the CPSU, if there is Stateflow? But we’ll talk about this separately yet ...

It is an ungrateful thing to make predictions, but nevertheless, based on my experience, I will express an seditious thought: as high-level languages ​​used to negate assembly language programming, so visual programming sooner or later and not less crowding out programming in high-level languages.

Literature

1. Programmers, let's study the sources of classical programs. [Electronic resource], Access mode: habr.com/en/post/488808 free. Yaz. Russian (date of treatment 02.22.2020).
2. C ++ 20 approved! What to expect and what to prepare for C ++ 23 developers. [Electronic resource], Access mode:habr.com/en/company/yandex/blog/488588 free. Yaz. Russian (date of treatment 02.20.2020).

More articles:


All Articles