The article presents the concept of an asynchronous-streamed model, which is an extension of the functional data-flow model of parallel computing. We suppose that the model will be used to describe dynamically changing parallelism. This model is based on the concept of asynchronous lists, which allow considering their parallelism as an independent way of describing the parallelism of the program. The specifics of asynchronous lists are represented. Using the examples, we show how to use this model to get temporary estimates of parallelism at different conditions of solving the problem. These estimates depends on correlation between data speed getting and computation time those data in parallel devices. Also, we demonstrate how two connected asynchronous-streamed functions can form pipeline automatically. As a result, we show out that on this model it is possible to obtain temporary estimates of the calculations performed and estimations which demonstrate the levels of parallelism.
Parallel programming offers different approaches to create parallel programs. Most of these approaches depend on concrete parallel computer architecture. Parallel computing systems use different methods of organizing parallel processes. For example, they oriented to execute processes of various sizes, have different methods of memory access and methods of transmitting information between memory and processors. They use different ways of managing computer resources too. The most popular are imperative programming paradigms.
To estimate parallel computing, the models that describe various aspects of parallel programs are used. These models make it possible to evaluate parallel programs by different parameters. For example, we can estimate such parameters as the parallelism level of program or the relation’s of execution time between operations, or the efficiency using of computing resources. There are models, which focused on the evaluation of parallel computing. These models do not allow writing parallel programs directly, but they provide various estimations and variants of analysis. In addition, they define various paradigmatic approaches that lead to the development of parallel programming languages.
Some abstract models don’t take into account real computing resources, assuming that they are
unlimited. In this case, it's possible to analyze the maximal parallelism and evaluate a level of
parallelism by various parameters. Besides, these models provide a conceptual basis for developing of
architecture-independent parallel programming languages. Also, they can be used for creating methods
of transforming architecture-independent parallel programs to programs for real parallel computers.
These models can descript parallel processes using elementary operations. Each operation can be
evaluated in its own computing resource. It allows avoiding of resource conflicts. And it is often
unimportant which computation management strategy was used [
The following models can be distinguished:
Model of communicating sequential processes [
These models are used to solve different problems.
The model describes the communication of processes using a mechanism for transmitting
asynchronous messages [
The main feature of this model is the use of an event as an instantaneous action that fixes the
beginning or end of a process. The event is defined as some signal, which is sent from predecessor to
successor and carry additional identifying information. Therefore, events’ transmission defines parallel
system as a set of interacted processes which communicate using signals. The model describes the
synchronizing primitives, which allow resolving of resource conflicts as one of results. The solution
of various problems of communication of processes is considered in [
A key feature of the model is that the moments of occurrence of events in time are sequential. That
is, events never occur simultaneously and do not overlap. Instead of simultaneity, an interpretation
from a nondeterministic appearance is used when their order is not defined and can be arbitrary. A
similar assumption is also used in Petri nets [
In the contrast to Hoare’s model, the concept of Q-determinant [
Q-efficient implementation of the algorithm was created [
Based on this, the main purpose of the model is to evaluate parallelism. So, to make it possible, the
Software system QStudio was created [
At the same time, the lack of interaction between processes does not clearly allow determining how parallelism will be described further in solving certain problems.
The DataFlow Functional Model of Parallel Computing (DFFMPC) is oriented on an
architectureindependent representation of parallel computing using unlimited resources. The model was used in
the Pifagor language development [
The model contents asynchronous lists that allow considering parallelism not as a static
phenomenon, but as an independent way of parallelism describing [
At the same time, the lack of interaction between processes does not allow to clearly determine, how
parallelism will be described further in solving certain problems. This model is based on the data
presentation in the form of asynchronous lists, which can also be defined as streams. Stream is ready
when there is even only one data element of it [
Let the asynchronous list be denoted as AN, where N is the number of elements generated in it. Then its structure can be described by the following recursive expression:
If N = 0, then A0 = (.),
If N>0, then AN = (d, AN-1).
Where d is the head element of the generated list AN-1 is the asynchronous list of the remaining N-1
elements, A0 is an empty asynchronous list and (.) is an empty data list [
Thus, for each of the interpretation operations, a list of data consisting of formed element and asynchronous list in which other elements accumulate. This “tail” may not yet be formed by the time the first element appears.
If a stream issued all data, then it is considered as completed. If the data is absent in the stream, and then an empty data list is as result. The same empty data list terminates any stream. Denote the stream by
AN = stream(d1, d2, … dN) The result is a gradually formed data list, which consists of pairs nested in each other: AN = stream (d1, d2,d3 … dN) (d1, stream (, d2,d3 … dN)) (d1, (d2, stream (d3, … dN))) (d1, (d2, (d3, … ( dN-1, stream (dN))) (d1, (d2, d3, … (dN, stream (.))) (d1, (d2,d3 … (dN, (.))).
AN = stream (d1, d2,d3 … dN) (d1, stream (, d2,d3 … dN)) (d1, (d2, stream (d3, … dN))) (d1, (d2, (d3, … ( dN-1, stream (dN))) (d1, (d2, d3, … (dN, stream (.))) (d1, (d2,d3 … (dN, (.))).
The creation of the next pair is possible only when the previous pair will be formed. That means, there can’t be direct access to an arbitrary element of the asynchronous stream. If all data of a stream were generated in advance, then their order in the stream is determined by the placement in the original data list. For example a one-dimensional array X = (44, 55,12,42) may be transformed to asynchronous stream from the original data the following way: stream (44,55,12,42) => (44, stream (55,12,42)) => (44, (55, stream (12,42))) => => (44, (55, (12, stream (42)) => (44, (55, (12, (42, (.))))).
Thus, next data element can be used for processing in each of the operations of interpretation. And we can select the remaining elements as a new asynchronous list, for processing by next interpretation operation, if it possible. At the same time the dataflow control principle is preserved. And the processing of the tail of the list does not depend on the moment when data will be arrived.
We can see the differences between regular and asynchronous approaches using a simple example of addition vector elements. The traditional approach to addition vector elements is based on cascading convolution. The general scheme of this approach is presented in Figure 1.
But often the vector may not be known at the beginning of the calculation, and the data may arrive in random order. The time interval between the generated events in asynchronous models is not significant. That is, it can be large or close to zero. In this case, the most important role is played by the ratio of the intervals between the moments of data generation and the duration of the computational operations. These times can be comparable or correlated as very large and very small quantities. In the latter case, very small quantities can be neglected, equating them to zero.
Based on this, the following scheme for calculating the sum of the elements of a one-dimensional array based on data availability can be presented. The elements of the array, asynchronously formed during the calculations, form a queue, into which they are entered in the order of appearance. If there are two or more elements in this queue, the pairs formed are summed. Then they are sent to the same queue. The only element remaining during the summation is the final result. The scheme of such organization of calculations is presented in Figure 2.
The above extensions to DFFMPC can implement in the programming language Pifagor. This will allow writing parallel programs in a slightly different style, which takes into account asynchronous receipt data. In particular, the addition of elements of a one-dimensional array, corresponding to the scheme, presented in Figure 1, can be implemented as follows: // Function which returning the summation of asynchronous list’s elements A_VecSum<< funcdef A // format of the argument: A=stream(x1, x2, … , xn) // где x1, x2, …,xn are numbers { x1<< A:1; // input element of data tail_1<< A:2; // tail of asynchronous list // Checking if the list is empty [(tail_1:[IsEmptyDataList, IsNotEmptyDataList]:?]^ ( x1, // In the list, there is only one element that determines the amount { // Determining the second argument followed by summation block { x2<< tail_1:1; // the second argument s<< (x1,x2):+; // sum of two received elements tail_2<< tail_1:2; // tail for the tail // Recursive processing of the remaining elements [(tail_2:[IsEmptyDataList, IsNotEmptyDataList]:?]^ ( s, { stream( tail_2:[], s):A_VecSum } ):. >>break } } ):. >>return; }
It should be noted that when this function arrives at the input of a regular data list instead of an asynchronous list, it will be correctly processed. This is due to the equivalent interpretation of the operations of taking the first element and highlighting the sublist without the first element for both lists. 5.3. Interpretation of time relationships of an asynchronous streaming program Using asynchronous lists allows developing a program that, depending on the time relationships between its operations, can be interpreted as a set of alternative algorithms that describe the same task. For example, if the time interval ∆tdat between the generation of data inside the asynchronous list is longer than the execution time of the addition operation ∆tadd, then the summation will be performed sequentially. This situation is illustrated in Figure 3.
It should be noted that in this case, we are not talking about specific temporal characteristics, but about the relation of times at the level of an abstract computational model.
In the event that the time interval for the receipt of data becomes less than the time of their
addition, parallelism will begin to appear in the performance of these operations. The number of
parallel threads will be a multiple of the ratio of time ∆tadd to ∆tdat. For example, with
∆tadd / ∆tdat = 2, two addition operations flows will be dynamically generated (Figure 4).
If the rate of data receipt is much higher than the time of the addition operation, then we can assume
that they have time to arrive before the start of the summation, which will begin almost simultaneously
for all pairs of numbers [
In this work, we will also focus on time relationships when solving a problem using asynchronous lists. As an example, consider the pairwise multiplication of two vectors.
Two vectors of the same length Ai and Bi arrive at the input to the processor D, and their arrival rates are arbitrary and are determined as ∆tda and ∆tcb, respectively. As a result, a vector is formed at the output, while data race and state changes are possible.
The solution to this problem consists of two steps:
Decomposition;
Convolution [
Let us consider in more detail the decomposition step, during which subproblems of the form Ak * Bk (k = 1... n) are formed.
When it is implemented in asynchronous mode, the data arrives with a certain intensity ∆td and is processed at a speed determined by the interval ∆tc. If the data arrives faster than the operation time, then new resources can be allocated for the input data. Otherwise, one resource is enough to solve the problem. If the data arrives simultaneously, then the number of operations is determined by the number of pairs received. In general, it can be noted that the amount of resources allocated at a certain step of solving the problem is determined by time relationships.
In this case, the number of resources R that must be allocated to the system to solve this problem is determined by the formula: ∆ = , ∆ where k is the coefficient of time relations.
This formula is valid for uniform calculations.
Depending on the values that this coefficient will take, the following cases are possible: 1. If ∆td ≤ ∆tc, then 0 <k <1, then only one resource is needed to solve this stage of the problem (R = 1). 2. For example, if 2 < k < 3, then k will determine the number of simultaneously involved resources at this stage of solving the problem = R, in this situation the number of allocated resources will be two. 3. For the largest possible number of allocated resources, the coefficient k must be a large number, i.e. ∆∆ . Therefore, it is possible to determine by this coefficient how many data pairs can be processed simultaneously. This number of pairs (ns) will be determined depending on the maximum number of RSmax resources allocated at this step, i.e. ns = RSmax. 4. To achieve maximum parallelism in solving the problem, it is necessary that the number of multiplication operations at this step be approximately equal to the number of allocated resources R, i.e.
n ≈ R, where n is the number of operations.
In the general case, taking into account the time characteristics, the following conditions for the maximum parallelism of the problem can be written: a) ∆∆ b) ∆td ≥ n, where n is the number of input data pairs of the form (Am, Bm), m=1, …, n The scheme of asynchronous calculations at the step of decomposition of the solution to this problem, taking into account the time characteristics, is shown in Figure 5. In this case, we are talking about computing nodes (operating devices) that provide processing of input data.
Software implementation of the decomposition step in the Pifagor language is shown here: // call the main decomposition function // Data input format: (list), (list) decCaller << funcdef X {
return << (X: 1, X: 2,1,1, (.)): dec; } // function for finding subtasks at the decomposition step dec << funcdef X {
A << X: 1; // input vector A B << X: 2; // input vector B i << X: 3; // counter Len << A: |; // the length of the vector A (provided that the vectors A and B are the same length) c << X: 4; list << X: 5; [((i, Len): [<=,>]):?] ^ (
{(A, B, (i, 1): +, (A: i, B: i): * >> mult1, (list, mult1): concat): dec},
{list} ) :. >> return; } // helper function for generating an asynchronous list concat << funcdef X { list << X: 1; // data item tail << X: 2; // tail of the list return << stream (list, tail); // returning asynchronous list for future calculations }
With a consistent description, parallelism can be described at various levels. In addition to of
temporary estimates of parallelism, one can obtain theoretical estimates of maximum parallelism
associated with tiering. These estimates can be obtained by assuming that all data comes
simultaneously and instantly. That is, assume that [∆td] = 0. In this case, any length of data processing
time will be much longer than the time of their arrival. Assuming [∆td] = 1, we can calculate the
number of tiers of the parallel algorithm in the same way as in the model based on the Q-determinant
[
When all the data is processed at such a rate that at the output of the processor it appears simultaneously, then a tiered assessment of maximum parallelism is taken place, where 1 is the type of tier.
If, after processing at the first step, multiple simultaneous processing takes place, and the number of such operations is equal to n, then a tiered estimate can be expressed by the equation: T=log(∆tс1), where ∆tс1 is the processing time at the first step and ∆tс1=∆tс2=...=∆tсn.
The study of this approach can be considered on more complex algorithms, which show that in this case, pipelined and other estimates are possible. As an example, we can consider the algorithm of vector multiplication, which gives output 1.
In this algorithm, pairwise multiplication is first performed (the scheme is shown in Figure 5), and then further summed up using the convolution operation (scheme in Figure 6). The order of summation is arbitrary.
Based on this, it is clear that estimates are related to the parallelism of these two problems. For time-limited estimates in the addition algorithm, parallelism will change as well as in the multiplication problem, from maximum to sequential. This allows obtaining different algorithmic estimates on the same description and evaluating the algorithm from the point of view of the same description.
This task shows that in this situation, pipelining of calculations is possible. Here the input data can already undergo a summation operation during the continuation of the whole operation, and not one after another, in contrast to the case with abstract estimates that lead to simultaneity. But in real calculations it is not so.
It should be noted that all of these studies can also be applied to solving the problem of matrix multiplication, since it reduces to vector multiplication. In this case, a full time or tier assessment can be used.
The use of asynchronous lists allows implementing a new class of algorithms, the parallelism of which
depends on the time relationships between the basic and preparatory operations. This allows talking
about a specific approach to the construction of parallel functional-stream algorithms, with the help of
which we can develop and research new methods for creating portable parallel programs. Unlike
equivalent transformations of generalized functions proposed in [
The proposed mechanism for describing asynchronous computing provides the programmer with additional features. Its instrumental support at the language level ensures the use of new methods for developing functional-stream parallel programs. They are characterized by a dynamic change in parallelism depending on the time relationships between the operations performed. This increases the flexibility of the developed algorithms, and allows using the same algorithm for dynamically setting different levels of parallelism. The programs formed at the same time allow us to describe the maximum parallelism of the problem being solved and are independent of the architectures of the computing systems used. However, it should be noted that the use of asynchronous lists does not affect the organization of a virtual computer used for parallel interpretation of functional programs.
As a result of the research, the extension of the functional-stream computation model was proposed. It provides a description of parallelism formed in the form of a recursion operation on asynchronous lists, which can be deployed into dynamically generated parallelism. And at the same time, this parallelism can be performed in parallel depending on time relationships. Using this model, both temporary estimates and estimates connecting the tiers of parallelism using abstract relations in the form of abstract intervals can be obtained.
The reported study was funded by RFBR according to the research project no. 17-07-00288.