SU1307463A1 - Device for investigating graphs - Google Patents

Abstract

The invention relates to computing and can be used for parallelization of linear program sections, taking into account informational and competitive communications of operators included in linear sections. The aim of the invention is to improve the speed of the device and enhance the functionality by distributing the vertices of the graph tio to the ranks, taking into account information and competition links. The device for examining graphs contains a matrix of 1 arc formers, a generator of 2 clock pulses, and triggers of 3 −3 / hp arc formers. (L s oo o 4 Oi CO

Description

group of elements OR group of elements AND group of registering counters, counter 7 of the number of pulses, group of comparison circuits 8y ,. New are block 15 of information and competition communications (NIC), which is designed to store information about communications operators

one

The invention relates to computing and can be used for automatic parallelization of linear program sections in parallel computing systems, i.e. for the distribution of linear sections operators by ranks taking into account informational and competitive communications between operators. This task arises when the calculations are performed on shared memory and the movement of operators during assembly into Rus can cause competition over memory, i.e. mashing some variables before using them. The necessary and sufficient condition for the competitive dependence between operators A and B is:

(InAnOutB) U (InBnOutA) U (OutAnOutB) 0,

where In A is the set used;

Oi t A is the set of variables that A can modify.

If this condition is present for a pair of statements, then a dummy link is inserted between them, i.e. they are not allowed to be executed simultaneously or in arbitrary order. Software methods for detecting and eliminating competition dependencies require considerable memory and computer time.

The purpose of the invention is to increase the speed and expansion of the functionality of the device by distributing the graph verbits by rank, taking into account the information and competition links between them.

FIG. 1 shows a block diagram of the device; in fig. 2 is a block diagram of a block of information and competition links; in FIG. 3

the linear section, the first 13 and second 14 shift registers, designed to organize the viewing of the matrix of shapers of input and output effects, the element SH-NOT 2, which is designed to generate a clock pulse stop signal. 3 or „

S

0

five

five

0

example of the graph and the corresponding matrix of input and output effects and the matrix of formers of arcs.

The device for examining graphs contains the matrix I of arc generators, a generator of 2 clock pulses, triggers of 3 arc formers, a group of elements OR 4, a group of elements AND 5, a group of counters 6, a counter 7 of the number of pulses, a group of comparison circuits 8, the first 9 and the second 10 elements AND, element OR 11, element OR-NOT 12, the first 13 and second 14 shift registers, block 15 of information and competition links and the second group of elements And 16.

Block 15 contains a matrix of 17 formers of output actions and a matrix of 18 formers of input actions, each of the formers of the matrix 17 of the input actions, except for the formers of the last row of the matrix, contains a trigger 19 and the element 20, and each of the formers of the matrix 18 of the input effects, except for the formers of the last row of the matrix, contains triggers 21 and elements Vi 22; in addition, the device contains the first 23, second 24, third 25 and sixth 26 groups of elements AND, the first group of elements OR 27, and the third group hectare input elements nts SHSh 28, groups of control inputs 29 and 30 of the block, group of information outputs 31 of the block and input 32 of the zero setting.

The operation of the device will be considered on the example of solving the problem of parallelizing a linear segment, the structure of which is shown in FIG. Behind,

31307463

where numbers denote the operators, and letters denote variables.

Initially, the matrixes 17 and 18 are entered into information about the sets of variables that are changed and used by the operators of the linear program section, respectively. In the matrix 17 of the output action drivers, the trigger 19 ij (, n; j l, ni) is set to one in that case, if the i-th operator changes) variable. In the matrix 18 shapers input effects

Sh

and i

t. ne st es e ne and / ne op va for

trigger 21 ij (, n;, m) setting f5

20

25

is cast to the unit state if the i-th operator uses the j-th variable. For the one shown in FIG. For an example of the matrix 17 and 18 formers, see FIG. Zb.

In the initial state, the first shift register 13 is in the zero bit and the first bit of the second shift register 14 is entered into the first bit. The registering counters 6 and the counter 7 of the number of pulses are reset to the zero state. The device begins to work with the launch of the generator 2 at the launch input. In this case, the first pulse from generator 2 passes through an element AND 10, the second input of which is prepared for operation by a high potential from the output of element OR 11, to the input of which a potential signal arrives from the output of the first bit of the second shift register 14. This 35th 1 element OR 28 and further the impulse goes to the shift input through the group of information outputs.

thirty

Out (i, j) nout (i.j) 0; (), i.e. trigger 3, located at the intersection of the first row and the i-th column of the matrix 1 of the arc drivers, is set to one if the i-th operator changes the same variable as the first operator and / or if the i-th operator uses the variable which is modified by the first statement. The entry of this information into the first row of the matrix 1 of arc formers occurs simultaneously for all operators i as follows.

At the first stage, competitive links are detected.

High potentials from the direct outputs of the 19 ij j triggers of the matrix of the 17 formers go to one input of the corresponding ix elements OR 27 and then from the outputs of the OR 27 elements to the first inputs of the corresponding And 25 elements, the second inputs of which are prepared for operation with high potentials the outputs of the elements 24 and from the outputs ix of the elements 25 and the j-th group, high potentials arrive at the inputs of the corresponding 3 i block (, p-1) at one of the inputs of the ix elements 16 and 16, the other inputs of which are prepared for operation by a signal from the output of the first digit shear p The register 13. The signals from the outputs of the elements And 16 set the corresponding triggers 3 in one state.

shift register 13 and shifts the unit from zero to first. The high potential from the output of this bit enters through input 29.1 in block 15 to the first inputs of elements AND 20 of the first row of the matrix 17 formers of output actions and to the inputs of elements And 1 of the first row of the matrix 1 formers of arcs.

In this case, high potentials appear at the outputs of those elements AND 20 of the first row of the matrix of 17 drivers, the second inputs of which are prepared for operation with high potential from the direct outputs of flip-flops 19. These high potentials are fed to the inputs of elements AND 24, the other inputs of which are prepared for operation - high potential from the output of the first bit of the second shift register 14 through the input 30.1 of block 15. High

five

0

five

5 current 1 elements OR 28 and further through a group of information outputs

0

Cues potential from the outputs of the elements And 24 enters the second inputs of the elements And 25. At this stage of the operation of the device, simultaneous identification of information and competitive communications of the type

Out (i, j) nout (i.j) 0; (), i.e. trigger 3, located at the intersection of the first row and the i-th column of the matrix 1 of the arc drivers, is set to one if the i-th operator changes the same variable as the first operator and / or if the i-th operator uses the variable which is modified by the first statement. The entry of this information into the first row of the matrix 1 of arc formers occurs simultaneously for all operators i as follows.

At the first stage, competitive links are detected.

High potentials from the direct outputs of the 19 ij j triggers of the matrix of the 17 formers go to one input of the corresponding ix elements OR 27 and then from the outputs of the OR 27 elements to the first inputs of the corresponding And 25 elements, the second inputs of which are prepared for operation with high potentials the outputs of the elements And 24, With the outputs ix of the elements AND 25 of the j-th group, high potentials arrive at the inputs of the corresponding 1 elements OR 28 and then through the group of information outputs

3 i blocks (, p-1) to one inputs i-x of elements AND 16, the other inputs of which are prepared for operation by a signal from the output of the first bit of the first shift register 13. The signals from the outputs of elements AND 16 set the corresponding triggers 3 to one.

At the second stage, informational communications are detected,

High potentials from the direct outputs of the 21 ij j triggered columns of the matrix of 18 operator inputs go to the first inputs of 26 And 26 ix ix elements And 26, the second inputs of which are prepared for operation with high potential from the first discharge output of the second shift register 14 via input 30.1 of block 15, High potentials from the outputs of the ix elements And 26 are fed to the inputs of the corresponding elements of IL1 27. Further

the operation of the device is carried out in the same way as when detecting competitive communications of the type

Out (l, j) nout (i, j) 5tO.

With the arrival of subsequent (n-2) pulses from generator 2 to the shift input of the first shift register 13, information is entered in the same way in all the other rows of the matrix 1 of arc drivers. When the n-th pulse arrives at the shift input of the first .shift register 13, an overflow signal occurs, which records the unit to the second bit of the first shift register 13 and shifts the unit from the first to the second bit of the second shift register 14. At the same time, the high potential c the output of the quark discharge of the first shift register 13 enters through input 29.2 in block 15 to the first inputs of elements AND 22 of the first row of the matrix 18 formers of input actions and the first inputs for elements AND 20 of the matrix formers 17 output effects vi, as well as the second inputs of the elements And 16 of the second row of the matrix 1 formers of arcs. In this case, high potentials appear at the outputs of those elements And 22 of the first row of the array of 18 drivers, some inputs of which are prepared for operation with high potential from the direct outputs of flip-flops 21. These high potentials arrive at one input of the corresponding elements And 23, the other inputs of which are prepared to work with high potential from the output of the second discharge of the second shift register 14 through the input 30.2 of the block 15. High potential from the outputs of the elements And 23 is fed to the inputs of the elements And 25. At this stage of the device operation competitive pricing

In (2, j) nOut (i, j) iO; (, n).

In this case, the trigger 3, which is the intersection of the second row and the ith column of the matrix 1 of the formers of arcs, is set to one if the ith operator changes the variable that the second statement uses. The entry of this information into the second row of the matrix 1 of arc formers occurs simultaneously for all operators as follows.

five

0

five

0

five

0

five

five

High potentials from the direct outputs of the flip-flops 19 j-ro column of the 17 formers go to the inputs of the corresponding ix elements OR 27 and then from the outputs of the OR elements 27 to one inputs of the corresponding elements AND 25, the other inputs of which are prepared for operation with high potentials from the outputs of the elements And 23. Further operation of the device is carried out in the same way as when detecting competitive communications of the type Out (I, j) nOut (i, j) tO.

With the arrival of the next (p-W) pulses from generator 2 to the input of the shift of the first shift register

13, in a similar manner, information on competing operators is entered into all the remaining rows of the matrix 1 of arc formers. As a result, the information presented in FIG. Sv,

With the arrival of the (p-2) th pulse at the input of the shift of the first shift register 13, an overflow signal arises which records the unit to the second bit of the first shift register 13 and shifts the unit from the second bit to the third bit of the second shift register 14. At the same time, low potentials from the first and second bits of the second shift register 14 are fed to the inputs of the element OR I1, the low potential from the output of which goes to the second input of the element 10, prohibiting the passage of pulses from, the generator 2 to the input of the shift of the first shift register 13. In addition, the low potentials from the outputs of the first and second bits of the second shift register, through inputs 30.1 and 30.2, arrive respectively at the first inputs of elements And 23 and 24, as a result of which the second inputs of all elements And 25 receive a low potential, which provides the prohibition of recording information in the matrix 1 formers of arcs. High potential from the output of the third bit of the second shift register

14 enters the second input of the first element 9. At this stage of the operation of the device, the operators of the linear section of the program are distributed among the ranks. Taking into account the information and competition links between them. Another impulse

71307463

from generator 2 is fed to the first input of the first element And 9 and further to the second inputs of the elements And 5 and the counter 7 of the number of pulses. At the same time, the inputs of registering counters 6 have those 5 columns, all the triggers 3 of which are in the zero state, the pulses through the elements of AND 5 do not pass. Next, the contents of the registering counters 6 receive neither the first inputs 0 of the comparison blocks 8 of the corresponding columns, the second the input of which receives information from the counter 7 of the number of pulses. If there is a mismatch

eight

of the name element AND of the first group, the output of each element AND of the first group is connected to the input of the same recording counter of the group, the output of which is connected to the first input of the same name group comparison circuit, the output of each i-th comparison circuit is connected to the input of the trigger setting of each former of the i-row arc arcing matrixes, the second inputs of all the comparison circuits of the group are combined and connected to the output of the pulse counter, characterized in that, in order to increase the speed of the counters 6 and 7, the asshireni functional

capabilities of the device by distributing the graph graphs by ranks, taking into account informational and competitive relations between them, 20 first and second elements AND, OR element, OR-NOT element, first and second shift registers, information and competitive relations forming unit were introduced , in each arc generator, except for the first arc generator of the first row of the matrix of arc generators, the element I was entered, the information and competition link formation unit contains the first group of

This produces a signal that resets to the zero state the trigger 3 of the formers of arcs of the row with the number equal to the column number, in the comparison block of which the comparison did not occur. The computational process continues as long as the comparison in the block :: 8 comparison occurs. The absence of comparison signals indicates that all the operators of the linear section of the program are distributed by rank. When a low potential occurs at the outputs of all units of comparison 8 at the output

of the element OR-NO 12, the high ° of the elements AND appears (where m is the quantity of the potential that goes to the input variables), the second stop group of the generator 2. At the same time, generator 2 stops the supply of pulses

the inputs of the elements And 9 and 10. The number of pulses recorded on the registering counters 6, corresponds to the rank number of each operator of the linear portion of the program.

Claims (1)

Claims of Invention A device for examining the graise of the m elements And; a third group of m subgroups of the elements And the (p-1) -th element N And in each subgroup, the fourth group 35 of m elements And the (n-1) -th element And each subgroup, the first group of OR elements from m subgroups of (n-1) -th element OR in each subgroup, the second group of C-1) OR elements, a matrix of 0 P Output formers, each driver of which, except for the last line the coderf containing the matrix of () is a trigger and an And element, shapers + 1, (where e p - the number of vertices of the graph) of the last row of the matrix is made in the worlds of arcs, formed as triggers, the matrix of. (n-1) t the arc former is made in the form of a trigger, input action drivers, each clock generator, the first driver of which, besides the group of (n-2) OR elements, the first tele.y of the last line, contains a trigger group elements AND, a group of register- and element AND, drivers of the last metering counter, pulse counter, matrix rows are made in the form of a trigger-group of comparison circuits, a trigger output, and the input of the installation of 1 trigger of each i-ro arc former of each arc generator matrix form () each The j-ro column, the arc drivers are connected to the output element of the first and second columns (where the artifactor of the same armature is mat-, 2, ..., n), the matrix of the formers, the first inputs of the elements And the arcs connected to the i-th input of the j-ro elementers of the arcs of each i-th row of the OR element of the first group, the output of which matrix of the formers of the arcs of the merger connected to the first input is single and connected to the output of the i-ro bit eight of the name element AND of the first group, the output of each element AND of the first group is connected to the input of the same recording counter of the group, the output of which is connected to the first input of the same name group comparison circuit, the output of each i-th comparison circuit is connected to the input of the trigger setting of each former of the i-row arc arcing driver arrays, the second inputs of all comparison circuits of the group are combined and connected to the output of a pulse counter, characterized in that, in order to increase the speed and expansion of functional Yes, the first and the shift register, the second inputs of the elements AND formers of arcs of each j-ro column of the matrix, except the first column, are combined and connected to the output of the j-ro element OR of the second group of the information and communication links forming unit, the second inputs of all comparison circuits of the group are combined and connected to the output of the pulse counter, the output of each j-th group comparison circuit is connected to the j-th input of the element ORI, the output of which is connected to the input of the stop of the clock generator, the start input of which is the start output device, the output of the clock generator is connected to the first inputs of the first and second elements I, the output of the first element I is connected to the counting input of the pulse counter and the second inputs of elements AND of the group, the second input of the first element I is connected to the output of the corresponding bit of the second shift register, the second the input of the second element AND is connected to the output of the element OR, the first and second inputs of which are connected to the outputs of the corresponding bits of the second shift register, the output of the second element AND is connected to the input of the shift the first shift register, the output of the shift register overflow is connected to the input of the same shift register and the shift input of the second shift register, the output of each i-ro bit of the first shift register is connected to the first inputs of the elements And shapers of the output actions of the i-th row of the matrix, shapers of the output the effects of the information and competition link building unit; in addition, the output of each i-ro bit, except the first bit output, the first shift register is connected to the first electrical input the inputs and shapers of input actions (iO-th row of the matrix of shapers of the input actions of the information and competition links block, the first inputs of the elements AND of the first group of the information and competitive formation block of the c - -sey are combined and connected to the output of the corresponding bit of the second shift register, the first the inputs of the elements of the second and fourth groups of the block forming information s 0 five 0 five 0 five 0 five and competitive communications are combined, and connected to the output of the corresponding bit of the second shift register, the installation inputs into 1 triggers of the formers of the matrix input and the inputs of the installation into 1 triggers of the formers of the output influences of the matrix of the information formation and competitive connections block of the device, the inputs of the installation in the triggers of the shapers of the input effects of the matrix and the inputs of the installation in o of the triggers of the shapers of the output effects of the matrix are combined are the input of the device zero setting, the direct output of the trigger of each output driver, except the output effects drivers of the last row, the matrix of the information formation and competition connections block are connected to the second input of the element And the same output effects generator, the outputs of the elements And all output effects drivers TO 1 The k-ro column of the matrix is combined and connected to the second input of the k-ro element AND the second group (where, 2, о, t) of the information and competition link formation unit, the direct output of the trigger of each j-ro driver of the output actions of each k The -ro matrix column, in addition to the output drivers that belong to the first row of the matrix, is connected to the first input (jI) -ro of the OR element of the kth subgroup of the first group of the information and competition links formation unit, the second input of each i-ro element OR k- the first subgroup of the first group en to the output of the i-ro element AND the k-th subgroup of the fourth group of the element AND block forming information and competitive communications, the output of each i-ro element OR the k-th subgroup of the first group is connected to the first input of the i-ro element AND k- second subgroups of the third group of information formation and competition links; the second inputs of all elements AND each kth subgroup of the third group are combined and connected to the output of the k-ro element; and the second group of the information and competition formation block; each output of each i-ro element And the k-th podgru ppa of the third group is connected to the k-th input of the 1st element OR the second group of the information and competition link formation unit, the direct output of the trigger of each i-ro driver input effects of each i-column of the matrix of the formers input drivers connected to the second input of the i-ro element And the k-th subgroup from the fourth group of the information generation and competitive connections, element outputs, and formers 0746312 the input X effects of each k-ro column of the input action shaper matrix are combined and connected to the second input of the k-ro element AND 5 of the first group of the information and competitive communications formation unit; the input of each k-ro element AND of the first group is connected to the second inputs of the O and k elements th subgroup of the fourth group. J 32 Da & .2 Fig.Z Compiled by T. Sapunova. Editor L. Pcholinsk. Tehred L. Oleinik Proofreader A. Ilyin Order 163A / 49 Circulation 673 Subscription VNIIGSh of the USSR State Committee for inventions and discoveries 113035, Moscow, Zh-35, Raushsk nab., 4/5 Production and printing company, Uzhgorod, st. Project, 4 and in C and 1 g 3 5 S 7 d patrix of entrances matrix SbixogoS