{'fraction_non_alphanumeric': 0.043650479283846945, 'fraction_numerical': 0.008872692703794661, 'mean_word_length': 4.115072933549433, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Critical pipeline of the acyclic wave processor

This paper is devoted to studying the performance of an acyclic wave processor consisting of heterogeneous processor elements having various delays. Data channels have sufficiently large buffers. The main result is the proof of the conjecture that for an arbitrary amount of input data, an acyclic wave processor contains a pipeline whose operating time is equal to the data processing time using the entire wave processor. This pipeline is called critical. For partially testing the conjecture, a multi-threaded application simulating the work of a two-dimensional pipeline has been developed. Earlier, the author proposed an algorithm for calculating the input processing time, the complexity of which depends not only on the number of stages but also on the amount of data. The proven conjecture eliminates this drawback, it allows building algorithms for calculating data processing time, the complexity of which does not depend on the amount of data. In particular, for any class of acyclic wave processors that have some algorithm of polynomial complexity for listing maximum pipelines, it is easy to construct a polynomial algorithm for calculating the data processing time for an arbitrary volume.


Introduction
We adhere to the definitions and notation [1], except that we now call the acyclic wavefront array processor (AWAP) an acyclic wave processor (AWP). The array of processor elements under consideration is heterogeneous, and the data transfer channels have sufficiently large buffers. Let be AWP, and let ( ) be the processing time of the data volume . For calculating the time ( ), a directed graph with weighted vertices was constructed in [1] whose maximum path weight is equal to the processing time of the given amount of data by . Based on this, an algorithm was proposed for calculating ( ). The complexity of this algorithm is ( 2 ), where is the number of processor elements. The disadvantage of the algorithm is that its complexity depends on the amount of data.
Our work removes this flaw. In [1], a conjecture was put forward that every acyclic wave processor for an arbitrary amount of data contains a pipeline having a processing time of elements equal to ( ). For = 1, this is a known fact that the project execution time specified by the network is equal to the weight of the critical path. We prove this conjecture (Theorem 1). Based on this conjecture, it is possible to construct algorithms for calculating the data processing time for an acyclic wave processor, the complexity of which does not depend on the amount of data. In particular, for any class of acyclic wave processors that have some algorithm of polynomial complexity for enumerating the maximal pipelines, we obtain a polynomial algorithm for calculating the processing time for an arbitrary amount of data (Corollary 1). An acyclic wave processor consists of a set of processor elements (stages) located at the vertices of some finite acyclic directed graphs. The edges of this graph correspond to data channels. We assume that the transmission time of the data element through the channel is 0, and the channel memory buffer is large enough so that the transmission speed does not slow down. For example, an asynchronous computing pipeline is an acyclic wave processor with a sufficient channel buffer size of 1. We also do not assume that data is transmitted using the handshake method [2], [3].
Acyclic wave processors have a wide variety of applications: for the development of signal processors [4] and coprocessors [5], in cloud computing [6], and production automation [7]. For study them, Petri nets [8], [9], [10] are used. The wave processor model used by us is a particular case of the model of a weighted marked graph [10].

Preliminaries
We adhere to the definitions and notation from [1]. Let ℕ = {0, 1, 2, 3, ⋯ } be the set of all nonnegative integers. The Petri net is considered as a quadruple ( , , , ), where is a finite set of places, is a finite set of transitions, : → ℕ and : → ℕ are functions such that for all ∈ and ∈ , the number ( )( ) is equal to the number of arcs → , and ( )( ) is equal to the number of arcs → . A marked partial graph is a Petri net ( , , , ) such that for all ∈ the conditions ∑ ( )( ) ∈ ≤ 1 and ∑ ( )( ) ∈ ≤ 1 are satisfied. A place that does not have incoming arcs is called final and not having outgoing arcs is called initial. A wave processor or wave partial graph ( , ) is a marked partial graph = ( , , , ) with delays : → ℕ, each transition of which has at least one outgoing arc and at least one incoming an arc. It is called acyclic if its Petri net does not have directed cycles. The input data volume for the wave processor is an integer ≥ 0, which determines the initial marking of its Petri net according to the formula 0 ( ) = if is the initial place, and 0 ( ) = 0 otherwise. Terminal marking is defined as ( ) = if is a final place, and ( ) = 0, otherwise. The directed path between the places of the acyclic wave processor is called the pipeline connecting these places. Figure 1 (a) shows the pipeline connecting and . It is easy to see that any transition of the acyclic wave processor belongs to some pipeline connecting some initial place with some final one. Thus, an acyclic wave processor can be considered as a working process in the sense of [7]. If the transition is the first (resp. last) in any pipeline containing it connecting the places, then it is called initial (resp. final). Let = ( , , , ) be an acyclic wave processor. Denote by ( ) the set of all initial transition, ( ) the set of all final transitions, ( ) = the set of all transitions. Delays for ∈ ( ) are defined as the values ( ) of some function : ( ) → ℕ. Note that if we remove the initial place having an outgoing arc connecting it to a non-initial transition, the processing time ( ) is not change. Similarly, we can delete the final place having an incoming arc connecting it to a non-final place. Figure 1 (b) shows a wave processor with an input data volume n. Processing time is not change if you delete the place 5 or the place 6 . For an arbitrary ∈ = ( ), consider the set of all transitions and places that allow paths to and contain , as well as places ∈ allowing arcs → . Add to these transitions and places all For an arbitrary pipeline = ( , , , ) with delays ( ), using Proposition 1 and induction along the length of the pipeline, we obtain a useful well-known formula:

Results
Below everywhere, the notation ⊑ is mean that is the pipeline contained in the wave processor. The pipeline ⊑ is called critical for a given amount of data if ( ) = max ′ ⊑ ′ ( ). Denote by + the wave processor with a new transition e. Its set of transitions is equal to ( ) ∪ { }, and for each transition ′ ∈ ( ), the place ′ and two arcs are added: ′ → ′ and ′ → .
To prove this, we introduce the definition: the height of the acyclic wave processor is the maximum length of the pipelines contained in . Let the set (Λ( ) ∖ { }) consist of elements 1 , … , . Denote by the wave acyclic processor Λ( 1 ) ∪ ⋯ ∪ Λ( ), consisting of places, transitions and arcs of Petri nets Λ( ), for all 1 ≤ ≤ . If the height ( ) is 1, then ( ) has one transition, whence it follows that formula (2) is valid for all ≥ 1.
Now we prove formula (2) using induction on pairs ( , ℎ), where > 1 is the amount of data and ℎ > 1 is the height of the acyclic wave processor of the form ( ). Let this formula be true for all ( ′) of height < ℎ. And let it be true for any amount of data ′ < for the acyclic wave processor ( ) of height ℎ. We prove it for ( ) of height ℎ and data volume . According to Proposition 1, it is true ( ) = max The proof follows from ( ) = max ∈ ( ) Λ( ) ( ) (Proposition 1) and from Proposition 2. This theorem allows constructing an algorithm for calculating ( ), the complexity of which does not depend on . For this purpose, it suffices to consider any algorithm for enumerating pipelines ⊑ . For any , ( ) is equal to the maximum of the numbers ( ) = ( ) + ( − 1) ( ). The complexity of calculating each of these numbers is no more than ( ), where is the number of stages of the acyclic wave processor. It follows that if the complexity of the algorithm for enumerting the maximum pipelines of this processor is ( ( )), then there is an algorithm for finding the number ( )of complexity ( ( )).

Corollary 1.
For any class of acyclic wave processors having some algorithm of polynomial complexity for enumerating the maximum pipelines, there is a polynomial algorithm for calculating the processing time for an arbitrary amount of data.
Consider, for example, a two-dimensional pipeline. It consists of = stages , 1 ≤ ≤ , 1 ≤ ≤ . Figure 2 (a) shows the Petri net of a two-dimensional pipeline at = 2, = 3. It is easy to see that for a fixed , the complexity of enumerating its maximum pipelines is ( ), and therefore there is an algorithm for calculating the processing time, of complexity ( +1 ).

Applications
We give an example of the application of Theorem 1 for calculating the network schedule of continuing education courses in programming for teachers. We set it using Table 1, shown below in the format from [11, Example 6.5-1]. For each discipline, no more than one pair per day is conducted. The method of constructing a Petri net of a network diagram is described in [1].

Computer model
To partially test the conjecture, the author developed a computer model of the wave processor using a multi-threaded application. Each stage of a multi-threaded application is implemented as a thread containing a cycle consisting of reading an element from each input channel, performing a stage operation, and writing the results to the output channels. The exchange of data between stages through channels is based on Dijkstra's algorithm for solving the problem of producer and consumer. The operation is simulated by waiting for the time delay of the stage, set in milliseconds. This method allowed developing a program for calculating the performance of a two-dimensional pipeline.
The two-dimensional pipeline consists of × stages , 1 ≤ ≤ , 1 ≤ ≤ . Therefore, it can be set using the table of delays ( ). The example shown in Table 2 defines a two-dimensional (3 × 7)-pipeline.  1  1  40  40  40  40  40  40   2  1  1  1  1  1  1  40  3  85  1  1  1 1 1 1 Figure 3 shows a graph of the processing time versus data volume for a two-dimensional pipeline obtained as a result of the experiment. The graph is displayed in the form of black dots with coordinates ( , ), where is the data volume and Y is equal to the processing time of the X volume data. For comparison with theoretical  6 results, we plotted the lines using the lines whose values are equal to the maximum values of the processing times of X elements for pipelines contained in a two-dimensional pipeline. Running the program for various parameters showed that the theoretical results (Theorem 1) are consistent with the experiment. The graph is displayed in the form of black dots with coordinates ( , ), where is the data volume and is equal to the processing time of the volume data. For comparison with theoretical results, we plotted the lines using the lines whose values are equal to the maximum values of the processing times of elements for conveyors contained in a two-dimensional pipeline. Running the program for various parameters showed that the theoretical results (Theorem 1) are consistent with the experiment.

Conclusion
There are various problems associated with calculating the processing time of a given amount of data for a wave processor. Processing time depends on the data transfer time. It may depend on the size of the channel buffer. The results of works devoted to the performance of wave processors usually contain estimates for large [4], [8]. An exception is the results of the article [12] and subsequent works by its authors. They study homogeneous two-dimensional pipelines.
We studied the processing time for an acyclic wave processor for a given amount of data and various stage delays. We developed an application for calculating data processing time for a twodimensional pipeline. The conjecture of a critical pipeline was tested. We proved the critical pipeline conjecture and established the existence of processing time calculation algorithms for an acyclic wave processor, the complexity of which does not depend on the amount of data. The results can be used both in the development of processors and multi-threaded applications and in the construction of network schedules for mass and serial production.