MODELING OF ALGORITHMIC CALCULATION GRAPHS USING PETRI NETS

Aim of the work: The aim of the work is to study the application of Petri nets for building computational algorithm models.

Execution of the Calculation-Graphical Work

1. Build a computational algorithm graph according to the connections between operator nodes given in Table 2.1.

2. Turn from the graph of an algorithm to a graph of a Petri net using the rules of the operator nodes illustration.

3. Build a Petri net graph.

4. Work out rules for executing the given Petri net, i.e., operating conditions of the model in performing computations.

Variants of the task are given in Table 2.1, the variant number corresponding to the student’s number in the students’ group list.

Table 2.1

Table 2.1 (Continued)

Example. Let us build a part of the algorithm graph for variant 4. The first five operator nodes are connected with each other in the way shown in Fig. 2.1.

We build a Petri net on the basis of the algorithm in the following way. Let the computational algorithm be as shown in Fig. 2.2.

According to the rules of building Petri nets, an arc is replaced by a position and an operator node is replaced by a transition. Using these rules we get a Petri net graph shown in Fig. 2.3.

Laboratory work 2.1

A STUDY OF PARALLELISM IN ALGORITHMIC STRUCTURE

Aim of the work: The work is aimed at gaining practical experience in software development for analysis of algorithmic structures realized in parallel computing systems.

Basic Principles

The algorithmic structure is a graphic representation of any algorithm in terms of a set of operator nodes and arcs which connect these nodes (Fig. 2.4).

Each such structure represents an algorithm of any calculation which may be realized via a sequential, parallel-sequential, or parallel structure.

The following description-coding system may be used for realization of the above mentioned processing types. A binary algorithm (with binary or unary operations) may be described via a model with the following rules: the algorithm may contain binary or unary operations; the operands may be as follows: input data, output data and the result of the previous operation, output data and the result of the operation performed not less than for two previous operation cycles, result of the previous operation, two results of the previous or earlier operations. Let us introduce such a coding for model description: a is an input data; ( is an opening parenthesis; ) is a closing parenthesis; t is an operation; F is an operation result. According to the rules of model description and the chosen coding, let us define a set of variants which are possible when analyzing the algorithm:

1. (a_ia_kt_f); 2. (F_ia_kt_f); 3. (F_iF_kt_f); 4. )a_it_k); 5. )t_i); 6. )F_it_k).

Variants from 4 to 6 are so-called open blocks since the operand for performing the operation t_f is determined immediately in the previous operation cycle. Variants from 1 to 3 are closed blocks since they have direct information about the operands obtained in the appropriate operations. Variant 1 determines operands for the operation t_f, these operands are input data, so this block is performed regardless of data, i.e. without time delays.

Let us make up a description of the algorithm, presented in Fig. 2.4, using the coding F, a, t, (, and ):

R(a_ia_jt_i)(a_ka_lt_j)(a_ma_kt_k)a_vt_m)(F_iF_jt_l)a_ct_n)F_mt_c).

This description is sufficient for scheduling the execution of operations. Being data-dependent, none of the operations can be performed before all the necessary operands are determined. For example, the operation t_l may not be performed before the operations t_i and t_j are completed, and the operation t_c may not be performed before the operations t_n and t_m are completed. Thus, the algorithmic structure defines the order of execution of operations, and this order can be automatically analyzed by means of a computer.

Let the coding of description elements be chosen as follows:

a_i is 1000+i,

( is 2000,

) is 3000,

t_i is 4000+i,

F_i is 5000+i,

where i is the current number of input data, the numbers of operations, and the numbers of operations in which the result F has been determined.

The coded description of the algorithm, depicted in Fig. 2.4, is as follows:

2000 100i 100j 400i 3000 2000 100k 100l 400j 3000 2000 100m 100n 400k 3000 100v 400m 3000 2000 500i 500j 400l 3000 100c 400n 3000 500m 400c 3000.

The operation of the analysis program begins with searching the first operation in the description. This operation is 400i. Having read the two previous cells, the program finds that the operands for this operation are input data, that’s why the priority of this operation is 1 (Pr1). The same priority (Pr1) is defined for the operations 400j and 400k. While defining priority for the operation 400m the following rule is used: the highest priority of the operands is incremented by one. For the operation 400m, one of the operands is input data, and the other is the result of the operation 400k with the priority Pr1. That’s why its priority is Pr2. The next operation 400l has the same priority Pr2 since its operands are the results of the operations 400i and 400j with the priority Pr1. The operation 400n has the priority Pr3, and the operation 400c has the priority Pr4.

The schedule of operations executed by the cycles of data transformation is as follows (Table 2.2).

Table 2.2

Seven cycles of data transformation is necessary for sequential execution, and only four cycles - for sequential-parallel execution.

We shall use the described method of description-coding and analysis for a multi-level structure in which the first level transforms input data and the connections in the next levels are defined with the help of a random number generator. The structure is shown in Fig. 2.5 in which the first level transforms only input data, the second level transforms data after the first level of transformation; the third level transforms data after the first and second levels; and the fourth level transforms data after the first, second, and third levels.

The concrete connections are given with the help of the random numbers generator. With the help of these values x(i), the codes for F_i of the second level are formed as 4000+x(i). The codes for F_i of the third and fourth levels are formed analogously given the above mentioned conditions.

A fragment of the algorithmic structure description (see Fig. 2.5) may be as follows:

2000 1001 1002 4001 3000 2000 1003 1004 4002 3000 2000 1005 1006 4003 3000 2000 50** 50 ** 4004 3000 2000 50** 50** 4005 3000 …, where ** are values of the random number generator x(i); x(i) = 1 to 3 for the second level.

Date: 2016-03-03; view: 457