Execution of the laboratory work

1. Study the methods of algorithmic structure description.

2. Present the results of the home-work.

3. Input the algorithmic structure description into your computer.

4. Input data defining the concrete connections between operators in the algorithm with the help of a random number generator.

5. Get a result of the algorithmic structure description.

6. Define the schedule of the operations realization in the algorithmic structure. Using the obtained data, analyze the possibilities of realization of the given algorithmic structure.

Contents of the Experimentation Paper

1. Home-work results.

2. Description of the algorithmic structure model with concrete data addresses.

3. Scheduling of the specified algorithm executed by a parallel computing system (operation cycle number, operations performed during this cycle, and data used for the given operation should be indicated in the schedule).

4. Conclusions (state whether the given structure is reasonable to be realized in a parallel system).

Home work

1. Develop, in a high-level programming language, a model of the algorithmic structure description (Fig. 2.5) based on the method described in Basic Facts.

2. Describe the operation of the random number generator that specifies a number sequence defining the connections between operator nodes of the algorithm.

3. Write a program for analysis of the algorithmic structure description, which includes the following procedures:

• searching (defining) of all the operations in the algorithm;

• defining addresses of all the operands for each operation;

• defining data-dependence between the operator nodes;

• scheduling operations according to the following priority principle: operations on the input data have the highest priority; the priority of other operations depends on the number of operations, the results of which are the operands for them – the fewer operations are needed to generate the operand, the higher is the priority of the given operation.

4. Make up a program for outputting the results.

Questions for the Self-Testing

1. What is data dependence in the algorithm?

2. What is control dependence in the algorithm?

3. How can data-flow computing be determined?

4. What is the difference between the parallel and pipeline structures?

Laboratory work 2.2

MODELING OF AN ON-BOARD COMPUTERS BY MEANS OF A PETRI NETS

Aim of the work: The aim of the work is to determine the functional states of an on-board computer with the help of Petri nets (PN).

Basic Principles

The approach based on using special network models, proposed by Carl Adam Petri for modeling of asynchronous information flows in data transformation systems, stands out among numerous methods for description and analysis of digital systems. Digital systems may be represented adequately as structures made up of two types of elements – events and conditions. Events and conditions in PN are represented by abstract symbols from two non-overlapping sets – a set of positions P = {p₁,p₂,p₃,p₄,…,p_n} and a set of transitions T = {t₁,t₂,t₃,t₄,…,t_n}. To illustrate a PN, we use graphic representation which is a bipartite oriented multigraph with two types of nodes: circles represent positions and bars represent transitions. The oriented arcs unite the positions and transitions. The functions of input I and output O, reflecting the connections between positions and transitions are also used to define a PN. A Petri net is defined by a quadruple C = (P, T, I, O).

A PN marking is introduced to describe the net operation dynamics. Marking M consists in assigning tokens to positions. A token is a primitive notion of a PN. Tokens are assigned to positions, their number and arrangement change during PN execution.

A marked PN is a net structure C and a marking M together, and it may be written as a quintuple C = (P, T, I, O, M). A token in a PN graph is depicted by a dot.

The Rules of PN Execution. The number of tokens and their distribution in the net control the execution of a PN. The PN is executed by actuating transitions. A transition is actuated by the removing the tokens from its input positions and creating new tokens in its output positions. The transition is actuated only if it is permitted, which is the case if the number of tokens in all its input positions is more or equal to the number of its input arcs. The transition is actuated by removing all the permitting tokens from its input positions with further placing in each its output position one token for each arc.

The actuation of a transition changes the PN marking M to marking M₁. If any input position of the transition does not have a sufficient number of tokens, the transition is disabled and cannot be actuated.

The state of a PN is defined by its marking. The space of PN states is a set of all markings. The matrix equation tools are used to get this space of states.

Alternative to PN definition in terms of the quadruple (P, T, I, O) there is a definition with the help of two matrices D^- and D⁺, which represent the input and output functions. Each matrix has m rows (one row for each transition) and n columns (one column for each position). Matrix D^- defines the inputs into the transitions D^-[j,i]=#(p_i,I(t_j)), and matrix D⁺ defines the outputs from the transitions D⁺[j,i]=#(p_i,O(t_j)). Then the matrix form of a PN as follows:

C = (P, T, D^-, D⁺).

The matrix theory of PNs is a tool for solving the reachability problem. If the marking M₁ is reachable from the marking M, then there is a sequence of transitions G which lead from M to M₁. This means that the vector G is a positive integer solution of the following matrix equation for X:

M₁=M+X∙D,

where D=D⁺-D^- is a compatibility matrix.

If the matrix equation has no solution, then M₁ is not reachable from M. Consider a marked net (Fig. 2.6).

The matrices look as follows:

In the initial marking M (1,0,1,0) the transition t₃ is permitted and it leads to the marking M₁, where

If the actuating sequence G=t₃t₂t₃t₂t₁ may be represented by the vector F(G)=(t₁t₂t₃)=(1,2,2), then we get the marking:

The Boolean (logic) algebra tools with some extension supply a formalism for the PN synthesis procedure: the basic logic connections – conjunction Λ, disjunction V, negation , exclusive OR , and sequence /.

The logic formula c=aΛb means that the event c will occur if both events a and b took place. The formula c=aVb means that the event c will occur if either the event a or the event b or both of them took place. The formula c=a b means that the event c will occur if the event a took place and the event b did not take place and vice versa [5, p.186, Fig. 7.1]. The formula a/b means that the event b will occur if and only if the event a took place. An illustration of the formulas in terms of graphs is depicted in Fig. 2.7.

For writing the logic formula describing processes in a system, it is necessary to investigate beforehand all possible states of its main modules and common resources, i.e. individual components. As a rule, their number is not more than two to four states for each component.

Let the given system be a two-processor system with common resources (Fig. 2.8). Each processor may be in one of the three states:

• operation with the personal memory - O;

• operation with the common memory - C;

• waiting for a common resource – W.

A common resource (common bus CB – common memory CM) may be in two states: free - state i; busy – state .

Then the logic formula for the first processor is:

F₁ = O₁/(W₁Λi)/C₁.

Having written an analogous formula for the second processor, we can write the logic formula for the entire system:

F =F₁ F₂ = [O₁/(W₁Λi)/C₁] [O₂/(W₂Λi)/C₂].

Using this formula we will build a PN (Fig. 2.9). The semantic description of the PN is given in the table.

Determination of the space of possible states in a two-processor on-board computer system by means of using matrix equations for building a space of reachable markings allows representing the system functional state and also finding possible deadlock situations when the system is not robust.

Date: 2016-03-03; view: 492