Lower-bound estimate search device in fully connected matrix systems during one-way data transfer

FIELD: information technology.

SUBSTANCE: device has a matrix comprising m rows and n columns of a homogeneous medium, n blocks for counting units, unit for finding the maximum, adders, a memory unit, a lower-bound estimate search unit which has a pulse generator, element selection multiplexers, row selection decoder, incidental vertex decoders, fixed arc decoders, row and column counters, fixed arc counters, incidental vertex counters, mode triggers, group of m triggers, group of m inhibit circuit units, matrix (i.j) (i=1.2,…, m, j=1.2,…,n) of fixed arc counters, matrix (i.j) (i=1.2,…, m, j=1.2,…,n) of OR elements, matrices (i.j) (i=1.2,…,m, j=1.2,…,n) of AND elements, an OR element, inverters, AND elements, group of m OR elements.

EFFECT: broader functional capabilities.

2 dwg

 

The invention relates to the field of computer technology and is intended for modeling problems in the design of computing systems (SU).

Well known element of a homogeneous environment, which includes the processing unit of the input signals, the block memory characteristic of the endpoint block output logic trigger recording of tracks, the evaluation unit of the current placement, the block transmission of information, inputs, outputs, control input, data inputs, data outputs indicator output (A.S. USSR 1291957, CL G06F 7/00, publ. 23.02.87, BI No. 7).

The disadvantage of this element is the narrow scope due to the lack of means to assess the quality (degree of optimality of placement criteria total length of edges and the maximum length of the ribs.

Closest to the proposed device according to the technical nature of a device for evaluating the placement of elements containing the matrix elements of a homogeneous medium consisting of homogeneous elements of the environment, blocks counting units, the unit finding the maximum, an adder, a memory unit, the input record of the original hypergraph, the control input permutation of the columns, the control input permutation of rows, the control input is written to the memory block, the outputs of the evaluation of the current placement, information output and input setup (A.S. USSR 1410949, CL G06F 7/00, 15/20, publ. 15.10.88, BI No. 38).

p> The disadvantage of this device is the narrow scope due to lack of funds for finding lower bounds for accommodation in fully connected matrix systems (MS) with unidirectional data transfer on the criterion of minimizing the intensity of interaction between processes and data.

An object of the invention is to expand the field of application due to the introduction of tools for finding lower bounds for accommodation in fully connected matrix systems with unidirectional data transfer on the criterion of minimizing the intensity of interaction between processes and data.

The technical problem is solved in that in the device search lower bounds for accommodation in fully connected matrix systems with unidirectional data transmission containing a matrix of m rows and n columns of elements of a homogeneous environment, n blocks of counting units, the unit finding the maximum of the first adder, a memory unit, and the control inputs a permutation of the columns of the matrix elements of the homogeneous medium is connected to the control input of the permutation of the columns of the device, the control inputs by permuting the rows of the matrix elements of the homogeneous medium is connected to the control input by permuting the rows of the device, the inputs setup matrix elements of the homogeneous medium is connected to the input device setting information input the matrix elements of a homogeneous environment connected to the input of the recording device, the indicator outputs of the elements of the j-th column (j=1,2,...n) of the matrix elements of the homogeneous medium is connected to the input of the j-th block of the calculation unit, the output of which is connected to the j-th input block finding the maximum and the j-th input of the first adder, the outputs of which are connected with the output of the maximal length of the edges of the device and output the total length of the edges of the device, respectively, the control input of the write memory block is connected to the control input of the recording device, the information outputs of i-th row (i=1,2,...m) matrix elements homogeneous environment connected with i-m information input of the memory block, the output of which is connected with the information output device, inputs the search block lower bounds containing the pulse generator, the first, second and third multiplexers select, the decoder selecting line, the first, second, third and fourth decoders incident to a vertex, the first, second and third decoders fixed arc, row count, column counter, the first, second and third counters fixed arc, the first, second, third and fourth counters incident to a vertex, the first and second trigger mode, the group of m triggers a second adder, a group of m blocks of elements of the ban, the matrix (i.j) (i=1,2,..., m, j=1,2,...,n) counters fixed arcs matrix (i.j) (i=1,2,..., m, j=l,2,...,n) elements OR the first matrix (i.j) (i1,2, m, j=1,2, n), the second matrix (i.j) (i=1,2,...,m, j=1,2,...,n), the third matrix (i.j) (i=l,2,...,m, j=l,2,...,n), the fourth matrix (i.j) (i=1,2,...,m, j=1,2..., n), the fifth matrix (i.j) (i=1,2, m, j=1,2,...,n), the sixth matrix (i.j) (i=1,2,...,m, j=1,2,...,n) elements And the element OR the first and second inverters, the first, second, third, fourth, fifth, sixth, seventh, eighth, ninth and tenth elements And group m elements OR, the starting device is connected to the pulse generator, the output of which is connected to the first input of the third element And the second input is connected to the direct output of the second trigger, the output of the third element And is connected to the second input of the fourth element And to the first input of the second element And to the second input of the first element And to the first input of the fourth element And connected to the generator output and the fourth output element And is connected to the input of the second element OR the output of which is connected to the first input of the first element OR the counting input of the third counter, the output of the overflow which is connected to the counting inputs of the third and fourth counters incident to a vertex, the output of the third counter connected to the input of the third decoder fixed arc, outputs 1 through m-th of which are connected to respective first inputs of the fifth, sixth, seventh, eighth, the ninth and tenth elements And to the second input of the eighth, the ninth, and as ten what about the elements And is connected to the output of the third inverter, to the second inputs of the fifth, sixth and seventh element And connected the output of the overflow of the fourth counter is incident to a vertex, which is also connected to the input of the third inverter, the outputs of the fifth, sixth, seventh element And connected to the first inputs of the elements (i.j) and (i.j) (i=1,2,...,m, j=1,2,...m) And the outputs of the eighth, ninth and tenth elements And connected to the first inputs of the elements (i.j) and (i.j) (i=1,2,...,m, j=1,2,...,m And, the output of the overflow of the fourth counter connected to the reset input of the third counter, the inputs of the third and fourth counter connected to the output of the third multiplexer selecting element, the outputs of the third and fourth counter connected to the inputs of the third and fourth decoders, the outputs from the 1-St to m-th third decoder connected to the first input (i.j) and (i.j) element (i=1,2,...,m, j=1,2,...,m) And outputs the fourth decoder 1-th m-th connected to the second input (i.j and (i.j) element (i=1,2,...,m, j=1,2,...m) And inverted output of the second trigger connected to allows input of the third multiplexer, the S input of the second trigger connected to the output of the overflow of the third counter, the R input of the second trigger connected to the output of the overflow of the second counter is incident to a vertex, inputs 1 through m-th of the third multiplexer connected to the corresponding outputs of the group m of the trigger control input of the third multiplex the RA is connected to the output of the counter column the second input of the second element And is connected to allows the input of the second multiplexer select and to direct the output of the first trigger mode inverted output of which is connected to allow input of the first multiplexer selecting element and to the first input of the first element And whose output is connected to the counting input of the first counter fixed arc and to the first input member OR the output of the second element And is connected with the second input of the first element OR the enable input of the second counter is incident to a vertex, respectively, the S-input of the first trigger mode is connected to the output of the overflow of the first counter is incident to a vertex, the counting input of the second counter fixed arc connected to the reset input of the second counter is incident to a vertex counting input connected to the output of the second multiplexer selection control input of which is connected to the control input of the first multiplexer selecting element and to the output of the column counter, a counting input connected to the output of the first element OR the installation counter input columns connected to the output of the counter lines and to the input of the decoder, the row selection output counter overflow lines connected to the output of the overflow device, the outputs from the 1-th through n-th decoder selecting lines connected to respective control inputs g of uppy m elements of the ban, corresponding inputs of which are connected to the indicator outputs of the respective elements of the first through n-th columns of the matrix 1 elements of a homogeneous environment, the outputs of the groups of m elements prohibition connected to respective inputs of the groups of m elements OR the corresponding outputs are connected to the corresponding S-inputs of the group m RS-flip-flops corresponding to the R-inputs of which are connected to the output of the counter overflow column and to the counting input of the counter lines, the outputs of the group of m triggers connected to the corresponding inputs of the first, second and third multiplexers select, the output of the first multiplexer selection element is connected to the enable input the output of the first counter incidental peaks corresponding to the counting input of which is connected to the output of the overflow of the first counter fixed arc, the output of which is connected to the input of the first decoder fixed arc of the i-th output (i=1,2,...,m) which are connected to respective first inputs (i.j) (i=1,2,...,m, j=1,2,...,n) elements, And the output of the second counter fixed arc connected to the input of the second decoder fixed arc corresponding to j-th (j=1,2,...,n) the output of which is connected with the second inputs i.j) elements (i=1,2,...,m, j=1,2,...n) And the output of the second counter is incident to a vertex is connected to the input of the second decoder incident vertices, sootvetstvujushij-th (i=1,2,...,m) the output of which is connected to the first input (i.j) element (i=1,2, m, j=1,2,...,n) And the first counter is incident to a vertex is connected to the input of the first decoder incident to a vertex corresponding to i-th (i=1,2,...,m) the output of which is connected to the second input (i.j) element (i=1,2,...,m, j=1,2,...,n) And the outputs of the first (i.j), second (i.j), third (i.j), fourth (i.j), fifth (i.j), sixth (i.j) is connected to the corresponding inputs elements (i.j) OR corresponding outputs of which are connected to the respective counting inputs (i.j) counters fixed arcs whose outputs are connected to respective inputs of the second adder, the output of which is connected to the output values of the lower bounds of the device.

The invention is illustrated by drawings, where figure 1 shows a functional diagram of the device of finding lower bounds for accommodation in fully connected matrix systems for bidirectional data transfer; figure 2 explains the essence of the search for lower bounds.

General features of the invention are as follows.

The proposed device can be used in the design of aircraft, for example, when placing processes. The device allows you to find the so-called lower placement assessment in MS on the criterion of minimizing the intensity of interaction between processes and data.

Source (placed) task (process algorithm) is represented as undirected unweighted graph G=<X,E>,

the set of vertices of a graph G, vertices, Xqk∈X which correspond to subtasks (Podgorica), and arc relationships between them eij∈E with i,j=(q-1)·n+k weighed amounts of data mijtransfer between

tasks and summarized in a matrix of information exchange (MY)

M=||mij||N×Nwhere N=n2=|X|

MS appears homogeneous environment, which is defined in accordance topological model in the form of a graph H=<P,V>

the base unit organized in matrix |R|n×n, where

|R|=N=n2- the number of processor modules base unit; V - the set of inter-module relationships defined by the connectivity matrix ||W||N×Nn2×n2.

Hosted software package (complex tasks), described by the graph G in the parallel system (PS), can be analytically described display

where

Here s is the number of the next permutation corresponding to the s-th option. The cardinalityvarious mappings equal to the number of all possible permutations of tasks {xqk} in the matrix X: |ψ|=N!.

Functioning homogeneous environment similar to the prototype. Upon receipt of the signal from the external control device (WWW) is the modeling of permutations of pairs of rows of the matrix with which agnosti (which corresponds to the permutation of the two vertices of the graph and obtain a new variant of placement). After another permutation of the proposed device computes the value of the lower bounds and gives these values VUU. The latter analyzes the received value and either records the received placement as a more optimal (if the values of criteria improve the previously found values), or ignores it.

Unlike the prototype, where the valuation is performed by two criteria-the total length of edges and the maximum edge length, the proposed device performs additional search lower bounds for accommodation in MILLISECONDS.

The essence of the proposed lower bounds placement is illustrated figure 2. Modules on MS figa and 2B are represented by squares in the upper left corner are represented by their numbers. Inside modules circles marked vertex with corresponding numbers inside. The dotted lines indicate the communication modules of the MS, and the solid line next to the dotted hypothetical fixed arc, right diagonal is located between the modules of the MS 2 and 4, and the left between modules of the MS 1 and 2. From figa shows that communication between modules 1-2 and 1-3 are not evenly distributed, which inevitably increases the total time of the task, as modules 1 and 2 will be uploaded stronger than the modules 4 and 3. The task completion time can be reduced by reordering arcs as shown in figb. This accommodation option although the NGO is a lower placement assessment for MS.

The device search lower bounds for accommodation in fully connected matrix systems for bidirectional data transfer (figure 1) contains a matrix 1 of m rows and n columns of elements of a homogeneous environment, unit 2.1-2.n counting units, unit 3 finding the maximum, the first adder 4, block 5 memory and control inputs a permutation of the columns of the matrix 1 elements of a homogeneous medium is connected to the input 7 of the management permutation of the columns of the device, the control inputs a permutation matrix row 1 elements of a homogeneous medium is connected to the input 8 of the control by permuting the rows of the device, the inputs setup matrix 1 elements of a homogeneous medium is connected to the input 13 of the installation device, the information inputs of the matrix 1 elements of a homogeneous medium is connected to the input 6 of the recording device, the indicator outputs of the elements of the j-th column (j=1,2,...,n) matrix 1 elements of a homogeneous medium is connected to the input unit 2.j counting units, the output of which is connected to the j-th input unit 3 finding the maximum and the j-th input of the first adder 4, the outputs of which are connected to the output 10 of the maximal length of the edges of the device and the output 11 of the total length of the edges of the device, respectively, the control input of the recording unit 5 of the memory is connected to the input 9 of the control device entry, the information outputs of the elements i-th row (i=1,2,...,m) matrix 1 elements homogeneous environment is uedineny with i-m information input unit 5 memory the output of which is connected with the information output device 12, and also introduced the block 62 of finding lower bounds containing the pulse generator 14, the first 15, second 16 and third 17 multiplexers select the decoder 18 select line, the first 19, 21 second, third 23 and fourth 24 decoders incident to a vertex, the first 20, second 22 and third decoders 25 fixed arc, the counter 26 row counter 27 columns, the first 28 and second 29 and 31 third counter fixed arc, the first 30, second 32 and third 33 and 34 fourth counters incident to a vertex, the first 35 and second 36 triggers mode, a group of 37.1-37.m triggers, 38 second adder, a group of 39.1, 39.2,..., 39.m the components of the ban, the matrix 40.i.j (i=1,2,...,m, j=1,2,...,n) counters fixed arcs matrix 42.i.j (i=1,2,..., m, j=1,2,...,n) elements OR the first matrix 46.i.j (i=l,2,...,m, j=1,2,...,n), the second matrix 47.i.j (i=1,2,...,m, j=l,2,...,n), the third matrix 48.i.j (i=l,2,...,m, j=1,2,...,n), the fourth matrix 49.i.j (i=1,2,...,m,j=1,2,...,n), the fifth matrix 50.i.j (i=1,2,...,m, j=1,2,...,n), the sixth matrix 51.i.j (i=1,2,...m, j=1,2,...n) of elements And element 43 OR the first 44 and second 45 inverters, the first 58, 59 second, third 60, 61 fourth, fifth, 52, 53 sixth, seventh, 54, 55 eighth, ninth 56 and tenth 57 elements And group 41.1, 41.2-41.m elements OR, with the input 63 of the starting device is connected to the pulse generator 14, the output of which is connected to the first input of the third element 60 And W is Roy whose input is connected to the direct output 36 of the second trigger, the output of the third element 60 And is connected to the second input of the fourth element 61 And to the first input of the second 59 element And to the second input of the first element 58 And to the first input of the fourth element 61 And is connected to the output of the generator 14, and the fourth output element 61 And is connected to the input 44 of the second element OR the output of which is connected to the first input of the first element 43 OR counting input of the third counter 31, the output of the overflow which is connected to the counting inputs of the third 33 and 34 fourth counters incident to a vertex, the output of the third counter 31 is connected to the input of the third decoder 25 fixed arc, outputs 1 through m-th of which are connected to respective first inputs of the fifth 52, 53 sixth, seventh 54, 55 eighth, ninth 56 and tenth 57 elements And to the second inputs 55 eighth, ninth 56 and tenth 57 elements And connected the output of the third inverter 45 to the second input of the fifth 52, 53 sixth and seventh element 54 And is connected to the output of the overflow of the fourth counter 34 incident to a vertex, which is also connected to the input of the third inverter 45, the outputs of the fifth 52, 53 sixth, seventh element 54 And is connected to the first inputs elements 48.i.j and 49.i.j (i=1,2,...m, j=1,2,...,m) And outputs 55 eighth, ninth 56 and tenth 57 elements And connected to the first inputs of the elements 50.i.j and 51.i.j (i=1,2,...,m, j=1,2,...,m) And output overflow even artego counter 34 is connected to the reset input of the third counter 33, the inputs of the third 33 and 34 fourth counter connected to the output of the third multiplexer 17 of the select element, the outputs of the third 33 and 34 fourth counter connected to the inputs of the third 23 and fourth 24 decoders, the outputs from the 1-St to m-th third decoder 23 is connected to the first input 50.i.j and 48.i.j element (i=1, 2,...,m, j=1, 2,..., m) And outputs the fourth decoder 24 from 1-St to m-th connected to the second input 49.i.j and 51.i.j element (i=1, 2,...,m, j=1, 2,...,m) And the inverse second output 36 of the trigger is connected to allows input of the third multiplexer 17, S the second input 36 of the trigger is connected to the output of the overflow of the third counter 33, R input 36 of the second trigger connected to the output of the second overflow 29 counter incident vertices, inputs 1 through m-th 17 third multiplexer connected to the corresponding outputs of the group 37.1-37.m triggers the control input of the third multiplexer 17 is connected to the output of the counter 27 columns, the second input of the second 59 element And connected it allows the input of the second 16 multiplexer select and to direct the output of the first 35 trigger mode inverted output of which is connected to allow input of the first multiplexer 15 of the select element and to the first input of the first element 58 And the output of which is connected to the counting input of the first counter 28 fixed arc and to the first input element 43 OR the output is showing 59 element And is connected to a second input of the first element 43 OR the enable input of the second counter 32 incident vertices, respectively, S-input of the first 35 trigger mode is connected to the output of the overflow of the first 30 meter incident to a vertex, the counting input of the second 29 counter fixed arc connected to the reset input of the second counter 32 incident to a vertex counting input connected to the output of the second 16 multiplexer selection control input of which is connected to the control input of the first multiplexer 15 of the select element and to the output of the counter 27 columns, a counting input connected to the output of the first 43 item OR setting input of the counter 27 columns connected to the output of the counter 26 rows and to the input of the decoder 18 row selection, the output of the overflow of the counter 26 lines connected with the release of the overflow device 65, the outputs from the 1-th through n-th decoder 18 selection lines connected to respective control inputs of the group 39.1-39.m elements of the ban, the relevant inputs are connected to the indicator outputs of the respective elements of the first through n-th columns of the matrix 1 elements of a homogeneous environment, the outputs of the groups 39.1-39.m elements prohibition connected to respective inputs of the groups 41.1-41.m elements OR the corresponding outputs are connected to the corresponding S-inputs of the group 37.1-37.m RS - flip-flops corresponding to the R-inputs of which are connected to the output of the counter overflow columns 27 and to the counting input of the counter 26 rows, the output of the group of m triggers connected to the corresponding inputs of the first 15, the second 16 and 17 third multiplexers select, the output of the first multiplexer 15 selection element is connected to the enable input the output of the first 30 meter incident to a vertex corresponding to the counting input of which is connected to the output of the overflow of the first counter 28 fixed arc, the output of which is connected to the input of the first decoder 20 fixed arc of the i-th output (i=1,2,...,m) which are connected to respective first inputs 46.i.j (i=1,2,...,m, j=1,2,...,n) elements And the second output 29 of the counter is fixed arc connected to the input the second decoder 22 fixed arc corresponding to j-th (j=1,2,...n) the output of which is connected with the second inputs 47.i.j elements (i=1,2,...m, j=1,2,...n) And the output of the second counter 32 incident to a vertex is connected to the input of the second 21 decoder, incident to a vertex corresponding to i-th (i=1,2,...,m) the output of which is connected to the first input 47.i.j item (1=1,2,...,m, j=1,2,...,n) And the first 30 meter incident to a vertex is connected to the input of the first decoder 19 incident to a vertex corresponding to i-th (1=1,2,...,m) the output of which is connected to the second input 46.i.j item (1=1,2,...,m, j=1,2,...,n) And the outputs of the first 46.i.j, second 47.i.j, third 48.i.j, fourth 49 i.j, fifth 50.i.j, sixth 51.i.j connected to respective inputs of the elements 42.i.j OR corresponding outputs of which are connected to the respective accounts of the entrance is 40.i.j counters fixed arcs, the outputs are connected to respective inputs of the second adder 38, the output of which is connected to the output 64 of the values of the lower bounds of the device.

The purpose of the elements and units of the device search lower bounds for accommodation in matrix networks (figure 1) consists of the following.

Matrix 1 elements homogeneous environment designed to simulate the process of solving location problems.

Blocks 2.1-2.n counting units are designed to convert the code of the indicator outputs of the elements of the corresponding columns of the matrix 1 in binary codes.

Unit 3 finding the maximum intended to highlight the maximum code from the set of code at its inputs.

The first adder 4 is designed for summation of n binary codes.

Unit 5 memory is intended to store the current best hosting option.

Entrance 6 recording device used to record the matrix that represents hosted count.

Input 7 control permutation of the columns of the device is designed to receive signal from WOW about the permutation of columns.

Input 8 control by permuting the rows of the device is designed to receive signal from WOW about permutation of rows.

The input 9 of the control device entry is required for signal reception "Record" from WOW. On this signal in the memory block 5 is filled in with the current accommodation of the matrix 1.

Output 10 maximum length of an edge of a device necessary to issue the maximum length of the ribs on WWW.

The output 11 of the total length of the edges of the device necessary to return the value of the total length of the edges on WWW.

Information output device 12 is required for the issuance of options for accommodation, located in block 5 of the memory on WWW.

Entrance 13 device setup required for synchronization of recording information in the elements of the matrix 1.

The pulse generator 14 is designed to generate pulse sequences, which synchronizes the operation of block 46 of finding lower bounds for accommodation.

First 15, second 16 and third 17 multiplexers select the item intended for filing with the outputs of the triggers 41.1-41.m information about the presence of the arc incident to the two selected vertices are placed in the graph. These peaks corresponds to the currently selected row and column of the adjacency matrix.

The decoder 18 row selection buttons to select the next row of the matrix 1 (matrix adjacency hosted count).

The first 19, 21 second, third 23 and fourth 24 decoders incident to a vertex are used to select the next fixed arc incident to the current vertex of the graph. The first decoder 19 selects the arc for fixing the string MS, the second 21 decoder, incident to a vertex chosen arc to lock in the column, t is eti 23 and fourth 24 decoders incident to a vertex selects the arc for fixing the diagonals MILLISECONDS.

The first decoder 20 fixed arc is used to select the next line MS, which will fix the next arc.

The second decoder 22 fixed arc necessary to select the next column MS, which will fix the arcs.

The third decoder 25 fixed arc is used to select the next line MS, which will fix the next arc.

In the counter 26 rows contains information about the currently processed row of the matrix 1.

In the counter 27 column contains information about the current processed the column matrix 1.

In the first 28 meter fixed arc contains information about the number of arcs, fixed horizontally in MILLISECONDS. This counter may not contain values greater than m-1.

The second 29 counter fixed arc is designed to accumulate information about the number of arcs, fixed vertically in MILLISECONDS. This counter may not contain values larger n-1.

The third counter 31 fixed arc is designed to accumulate information about the number of the arc fixed diagonally.

The first 30 meter incident to a vertex is used to accumulate information about the current fixed arcs in rows MC, incident to the selected vertices of the graph of the matrix 1.

The second counter 32 incident vertices is designed to store information is current fixed arcs in columns MS, incidental to the selected vertices of the graph of the matrix 1.

The third 33 and 34 fourth counters incident to a vertex are used to store information about the current fixed arcs in the left and right diagonals MS, incidental selected vertices of the graph of the matrix 1.

The first 35 trigger mode - selects the mode of fixation of the arcs. In the zero state of the trigger will be recorded in rows MC, in single - MS columns.

The second 36 trigger mode to select the mode of fixation of the arcs. In the zero state of the trigger will be recorded in the right diagonals MS, single - left diagonals MILLISECONDS.

Group 37.1-37.m RS-triggers is used to store information about the presence of an arc between the corresponding incident vertices.

Second the adder 38 is used to accumulate the values of the lower bounds for accommodation in MILLISECONDS.

Group 39.1-39.m elements of the ban is intended to block the inflow values from elements 1 through m-th rows of the matrix 1 to the corresponding elements OR 41.1-41.m.

Matrix 40.i.j (i=1,2,...,m, j=1,2,...,n) counters fixed arcs is used to calculate load modules MILLISECONDS.

Group 41.1-41.m elements OR are used to combine signals from the outputs of the group of elements 39.1-39.m ban, respectively.

Matrix 42.i.j elements OR is intended to combine the signals from the outputs of the matrix 46.i.j, 47.i.j, 48.i.j, 49.i.j, 50.i.j, 51. i.j cell battery (included) the tov And subsequent supply to the input of counter 40. i.j fixed arcs. Here i=1,2,...,m,j=1,2,...,n.

First 46.i.j, the second 47.i.j, third 48. i.j, fourth 49.i.j, fifth 50. i.j, sixth 51. i.j matrix elements needed to ensure fixation of the incident to the current vertex of the arc in units of MILLISECONDS. Here i=1,2, m and j=1,2,...,n.

Item 43 OR is intended to combine the signals from the outputs of the first 58, second 59 and 61 third elements I.

The first 58, 59 second, third 60 and fourth 61 elements And serve for the supply of the clock pulse from the pulse generator 14 based on the value of direct output 36 of the second trigger mode, respectively, will work distribution diagonals, rows, or columns, depending on the value of the first 35 trigger mode, either the first counter 28 fixed arc and to the first input element 43 or, OR to the second input element 43 OR to sign authorizing the issuance of the second counter 32 incident to a vertex, or on the third counter 31 incident vertices, diagonals, respectively.

Group 41.1-41.m elements OR necessary to combine the signals from the outputs of the first group of m elements of the ban, respectively.

Group 52-57 elements And is designed to separate the two modes of fixation of arcs: the left diagonal and right diagonal through inverter 45.

The inverter 44 is designed to distribute fixing arcs in the diagonals.

The inverter 45 is designed to activate e is the elements 55, 56, 57 items I.

Unit 62 searches the bottom of the evaluation is to find lower bounds for accommodation in fully connected matrix systems for bidirectional data transfer.

Entrance 63 of launching devices are required to supply the start signal generator 14 pulses from WWW.

The output 64 of the values of the lower bounds is used for issuing VUU values lower estimates of current options for accommodation in MILLISECONDS.

The output 65 of the overflow device is used to supply information about the overflow of the first counter 26 line number that is simultaneously a signal on the shutdown unit 62.

Operation of units 1, 2, 3, 4 and 5 are described in detail in the prototype and therefore not considered here.

Initially in the matrix 1 elements homogeneous environment contains the original version of the host corresponding to the adjacency matrix of the original graph. All triggers in memory block 5 are in a state of logical zero. Group 37.1-37.m trigger is in a state of logical zero. The trigger 35 mode is in a state of logical zero, therefore, to direct its output is zero potential, and the inverse is unique. The trigger 36 is in the state of the logical unit and then in the counter matrix 40.i.j (i=1,2,...,m, j=1,2,...,n), there is a code of zero ("00...00"). In the counter 26 and 27, there is a code unit (00...01"). A single value output from the counter 26, under which is input to the decoder 18, therefore, the first output is a single signal, which serves to corresponding control inputs of the first block 39.1 elements of the ban, providing passage at their outputs signals from the indicator outputs of the elements in the first row of the matrix 1. These signals pass through the band 41.1-41.m elements OR, and act on relevant S-inputs of the group 37.1-37.m triggers, setting them into a single state in the presence of the respective individual signals. In the counter 30 and 34 code of two ("00...010"), the counters 29, 33 - unit code ("00...01"). In the second adder 38 and the counters 28, 31 and 32 code of zero.

The proposed device is intended to assess the placement criteria total length of edges, the maximum length of the ribs. Additionally, the proposed device allows you to search for lower bounds for accommodation in fully connected matrix systems for bidirectional data transfer, and is intended for solving the problem of tracing. The trace task is solved in the matrix 1 as in the prototype, and therefore is not considered here.

Placement assessment criteria the total length of edges and the maximum length of the edges is as follows. Information from the indicator outputs of the elements of each column of the matrix 1 enters in the appropriate blocks of counting units. Block 2.i (i=1,2,...,n) which gives a binary number (code), equal to the amount received at its input units. The resulting number then goes to the inputs of the first adder 4 and unit 3 finding the maximum corresponding to this set of counting units. In the output device 10 is formed code (estimate) maximum length of the ribs, and the output 11 of the code (estimate) total length of the edges corresponds to the current option scheme (contained in the matrix 1). The estimates obtained further act on WOW where they are compared with previous values. In case of improving estimates of WOW takes a pulse (signal "Write") to the input 9 of the control device entry and the current accommodation is rewritten in block 5 of the memory matrix 1.

The task of finding the values of the lower bounds for accommodation in fully connected matrix systems for bidirectional data transfer is solved as follows. After executing a permutation of the rows on the indicator outputs of the elements of the matrix 1 receive signals corresponding to the new option. Simultaneously starts the pulse generator 14 and starts the operation unit 62 searches the lower estimate, which is divided into four stages: the first stage is to fix the arches in rows MC, the second step is fixing the columns MS, and the third and fourth stages of fixation of arcs along the diagonals left and right is. If after all four stages of operation of the device there are still uncommitted arc, the commit process is repeated until then, until you have treated all arcs of the initial graph. This is evidenced by the complete enumeration of all values in the connectivity matrix.

As the trigger 35 mode is the state of the logical zero on its inverted output is a single signal received at the first input element 58 And to an enable input of the first multiplexer 15 selects an item. A single signal with the direct output of the trigger 36 is supplied to the second input element 60, allowing the passage of the pulse from generator 14 to the second inputs of the elements 58 and 59. The appearance of the pulse at the second input element 58 And its output is a single pulse which is fed to the counting input of the counter 28, increasing its content on the leading edge to the code unit (00...01"). The same pulse falls at the first input element 43 OR. A positive pulse is fed to the counting input of the counter 27 and increases its contents on the leading edge up to code deuces("00...010").

Code number two and the output of the counter 27 is supplied to the control inputs of the first 15, second 16 and third 17 multiplexers select the item. So as to permit input of the multiplexer 15 is a unit that received at its control the rd input code number two passes a single value from the trigger output 37.2. If it is in a single state, then the output of the multiplexer 15, you receive a single pulse. The single output of the multiplexer 15 is supplied to the enable inputs of the issuance of the counter 30, allowing the emergence of codes on their outputs. As a result, the input of the decoder 19 shows a code number two ("00...010"), so the second it comes out, you receive a single signal, which is supplied to the second input element 46.i.2 (i=1,2,...,m) AND MS.

By this time, the output of counter 28 is already present code "00...01", which is fed to the input of the decoder 20, so the first output is a single signal. This signal is applied to the first inputs of the elements 46.1.j (j=i,2,...,n) AND MC (figure 1). Thus, at the output of the element 46.1.2 And receive individual signals that pass through the corresponding element 42.1.2 OR and is supplied to the counting input of the counter 40.1.2, increasing its contents by one. Thus fixation of the arc in the first line of MILLISECONDS.

The next clock pulse supplied to the second input element 58 And to the first input element 59 And. as the first input element 58 And there is a single pulse with inverted output of the trigger 35, the output of the element 58 And you receive a positive pulse which is fed to the counting input of the counter 28 and the element 43 OR, passing to the counting input of the counter 27. As a result, the counter is 28 on the leading edge will be installed code deuces ("00...010"), and the counter 27 on the leading edge will set the code number three ("00...011"). Code C output of counter 27 will be transferred to the control inputs of multiplexers 15, 16 and 17. To permit input of the multiplexer 15 is a single signal, which allows the signals on its output. If the trigger output 37.3 present a single signal (this means the presence of arcs in the graph), then the output of multiplexer 15 will receive a single pulse, which is fed to the input authorizing the issuance of the counter 30. At the input of the decoder 19 code appears deuces output of the counter 30. Accordingly, the second output of the decoder 19 will receive a single signal. A single signal from the second output of the decoder 19 is received on the second input element 46.i.2 (i=1,2,...,m) AND MS.

Code "00...010" output of the counter 28 to the input of the decoder 20 and excites at its second output a positive pulse which in turn is supplied to the first input element 46.2.j (i=1,2,...n) I. Thus, at the output of the element 46.2.2 will get a signal that will pass through the corresponding element OR 42.2.2 and increase on the leading edge of the counter contents 40.2.2 per unit, thereby locking the next arc of the considered graph.

This happens until then, until you overflow the content of the counter 28. This situation will occur when the contents of the counters is ka > m. In this case, the output of the overflow of the counter 28 will receive a single pulse, and its contents dumped into the unit. The pulse output overflow of the counter 28 will be transferred to the counting input of the counter 30, increasing its content on the leading edge of the unit. Therefore, the counter 30 will set the code number three ("00...011"). At this time the contents of the counter 27 will be increased on the leading edge per unit up to code four ("00...0100"). After this fixation arcs is repeated as described above.

This continues until, until the overflow counter 27 or counter 30. Overflow of the counter 27 will happen if its content exceeds code number n. In this case, the output of the overflow appears a single pulse, which is supplied to the counting input of the counter 26 rows and increases its contents on the leading edge of the unit, setting the code it deuces ("00...010"). Code number two to the input of the decoder 18 and the installation of the meter inlet 27, establishing therein an initial value equal to the code deuces ("00...010"). The second output of the decoder 18, you receive a single pulse, which is supplied to control inputs of the block 39.2 elements of the ban, thus allowing passage of signals from the indicator outputs of the elements of the second row of the matrix 1, which pass through the respective input of the group 41.1-41.m items OR proceed to the appropriate S-inputs of the group 37.1-37.m triggers, putting them in the same state with the appropriate individual signals. Further work is as described above.

The overflow of the first counter 30 fixed arc means that the fixation of the arcs of the initial graph in rows completed MS (figure 2 this arc recorded in units 1-2 and 3-4) and then you need to fix the arc in the pillars MS (figure 2 are modules 1-3 and 2-4). The output signal from the overflow of the counter 33 is supplied to the S input of the trigger 35 mode, setting it in one state. Then on his direct output will be a single signal, and the inverse - zero. The zero signal from the inverted output of the trigger 35 is supplied to an enable input of the multiplexer 15 and prohibits the passage of signals at its output. In addition, the same signal arrives at the first input element 58, thereby preventing the passage of pulses from the pulse generator 14. A single signal with the direct output of the trigger 35 is supplied to the second input element 59 And permitting the passage of pulses from generator 14 of pulses at its output, and enable input of multiplexer 16, thus allowing the passage of signals from the inputs to their output. The counter 30 is set to code deuces("00...010").

The next clock pulse from the pulse generator 14 is supplied to the first input element 59 And. as its two inputs are isolated the signals, the output is a single pulse, which is supplied to the second input element 43, and then passes OR at the counting input of the counter 27, increasing its content on the leading edge of the unit. The same pulse from the output of the element 59 And reaches the entrance authorizing the issuance of the counter 32, thus allowing the emergence of the contained code in the respective output.

By that time, the control inputs of the multiplexers 15, 16 and 17 will receive the ID number contained in the counter 27. So as to permit input of the multiplexer 16 is a positive pulse, and if the trigger 41.j (j=1,2,...,n) contains a unit, then the output of multiplexer 16 will receive a positive pulse. The single output of the multiplexer 16 is supplied to the counting input of the counter 32, increasing its content on the leading edge up to code "00...01", respectively. Therefore, at the input of the decoder 21 will receive the code "00...01". With the appearance of the code at the input of the decoder 21, the first output of the decoder 21 is excited by a single pulse, which is supplied to the first inputs of the element 47.1.j (i=1,2,...,n) AND MC.

Code "00...01" output of the counter 27 to the input of the decoder 22, and at its first output is a single pulse, which is supplied to the second input element 47.i.1 (i=1,2,...,m) AND MC. Thus, the output of this item, there will be a single pulse. Thereby ensure the clicking the appearance of a positive signal at the input element 42.2.1 OR MS, which is supplied to the counting input of the corresponding counter 40.2.1 and on the leading edge increases their contents on the unit. So fixing the arc in the MS column.

The next pulse from the output of the generator 14 pulse excites the pulse at the output of the element 59 And which is fed to the counting input of the counter 32 and to the second input element 43 OR, which takes place at the counting input of the counter 27, increasing its content on the leading edge of the unit. In the counter 32 so on the leading edge will set the code number two("00...010").

As a result, the second output of the decoder 21 appears a single pulse. The corresponding pulse will be transferred to the corresponding first input element 47.2.j (j=1,2,...,n) AND MC.

The first output of the decoder 22 is still present a single value, which is supplied to the second input element 47.i.1 (i=1,2,...,m) AND MC. Thus at the output of the element 47.3.1 And will be a single value, which, after passing through the element 42.3.1 OR will arrive at the input of the corresponding counter 40.3.1 and increase its content on the leading edge of the unit. So it will get fixed next arc in the MS column.

This happens until then, until the contents of counter 32 becomes equal to m-1, indicating that the arc in the first column MS fixed and you move on to the next column. Ed is fullled pulse output overflow of counter 32 will be transferred to the counting input of the counter 29 and the leading edge increases its content per unit up to code deuces ("00...010"). After this process is repeated as described above.

So going up until at the output of the overflow of the counter 29 will not appear impulse overflows, indicating that the arc in all columns MS fixed. Pulse overflow is fed to the R-input of the trigger 36 mode, dumping its contents to zero. Thus, on its direct output appears zero, and the inverse is positive.

After the passage of pulses from the pulse generator 14 through the element 59 And is closed so as to direct the output of the trigger 36 is supplied zero pulse to the second input element 60, and opens through the element 61 And, as its second input appears zero value, then passing through the inverter 44. To permit input of the multiplexer 17 will receive a single value that allows the appearance of pulses at its output, and allows the input of the multiplexers 15 and 16 receive a value of zero, which prevents the appearance of pulses at the output of these multiplexers. A single pulse from the element 44 hits at the counting input of the element 31, setting its value per unit ("00...01") and to the first input element 43 OR, a positive pulse is fed to the counting input of the counter 27 and increases its contents on the leading edge up to code deuces("00...010").

Code number two and the output of the counter 27 postopen control inputs of the first 15, the second 16 and 17 third multiplexers select the item. So as to permit input of the multiplexer 17 is equal to one, received at its control input the code number two passes a single value from the trigger output 37.2. If it is in a single state, then the output of the multiplexer 17 appears a single pulse. The single output of the multiplexer 17 is supplied to the enable inputs of the issuance of the counters 33 and 34, allowing the emergence of codes on their outputs. As a result, the input of the decoder 23 shows a code number of units ("00...01"), so the first output is a single signal that is supplied to the second input element 48.i.1 (i=1,2,....m) AND MC. Simultaneously, the second output of the decoder 24, you receive a single signal, which is supplied to the second input element 49.i.2 (i=1,2,...,m) AND MS.

By this time, the output of the counter 31 is already present code "00...01", which is fed to the input of the decoder 25, so the first output is a single signal. This signal is applied to the first inputs of the elements 52 And 55, but since the interrupt signal from the counter 34 has not yet been, the zero signal passing through the inverter 45, becomes a single and gets on the second stroke element 52, thereby allowing the signal further. With the element 52 And the signal gets to the elements 48.1.j and 49.1.j. As a positive si is cash on the first entry is present only elements 48.1.1 and 49.2.2 through them and passes a positive signal to the corresponding elements 42.1.1 and OR 42.2.2 and arrive at the counting input of the counter 40.1.1 and 40.2.2, increasing their contents on the unit. Thus fixation of the arc in the first line of MILLISECONDS.

The next clock pulse supplied to the second input element 61 I. the Impulse comes from the output of the inverter 44 to the input of the element 43, thereby setting the counter 27 to a value of three ("00... 11"), and the counter 31 to a value of two ("00...10"). Code C output of counter 27 will be transferred to the control inputs of multiplexers 15, 16 and 17. To permit input of the multiplexer 17 is a single signal, which allows the signals on its output. If the trigger output 37.3 present a single signal (this means the presence of arcs in the graph), then the output of the multiplexer 17 will receive a single pulse, which arrives at the input authorizing the issuance of the counters 33 and 34. Code units from the output of the counter 33 is fed to the input of the decoder 23, and at the input of the decoder 24 code appears deuces output of the counter 34. Accordingly, the first output of the decoder 23 and the second output of the decoder 24 will receive a single signal. A single signal from the first output of the decoder 23 will go to the second input element 48.i.1 (i=1,2,...,m) AND MC. A single signal from the second output of the decoder 24 will go to the second input element 49.i.2 (i=1,2,...,m) AND MS.

Code "00...010" output of the counter 31 is supplied to the input of the decoder 25 and excites at its second output a positive pulse which is in turn supplied to the first inputs of the elements 48.2.j (i=1,2,...,n) and 49.2.j (i=1,2,...,n) And through the elements 52-54 I. Thus, the output elements 48.2.1 and 49.3.2 will be the common signals that pass through corresponding elements 42.2.1 and OR 42.3.2 and increase on the leading edge of the contents of the counters 40.2.1 and 40.3.2 per unit, thereby locking the next arc of the considered graph.

This happens until then, until you overflow the content of the counter 34. This situation will occur when the contents of counter >m. In this case, the output of the overflow of the counter 34 will receive a single pulse, and its contents dumped into the unit. The pulse output overflow of the counter 34 is received on the reset input of the counter 33, zeroing it and setting its content to the deuce ("00...10"), and the counter 34 will set the code number of units ("00...01"). At this time the contents of the counter 27 will be increased on the leading edge per unit up to code four("00...0100").

After this fixation of right diagonals. As a single output signal from the overflow of the counter 34 came to the input of counter 33, at the same time he gets to the second inputs of the elements 55-57, thereby allowing the fixation of right diagonals. Individual signal passing through the inverter 45 becomes zero and getting on the second inputs of the elements 52-54 And prevents the fixation of the left diagonals. The pulses from the outputs of the elements 55-57 fall on the second inputs of the elements 50.i.j and 51.i.j.

The code is Isla two outputs of the counter 27 is supplied to the control inputs of the first 15, the second 16 and 17 third multiplexers select the item. So as to permit input of the multiplexer 17 is equal to one, received at its control input the code number two passes a single value from the trigger output 37.2. If it is in a single state, then the output of the multiplexer 17 appears a single pulse. The single output of the multiplexer 17 is supplied to the enable inputs of the issuance of the counters 33 and 34, allowing the emergence of codes on their outputs. As a result, the input of the decoder 23 shows a code number twos ("00...10"), so the first output is a single signal that is supplied to the second input element 50.i.1 (i=1,2,...,m) AND MC. Simultaneously, the second output of the decoder 24, you receive a single signal, which is supplied to the second input element 51 i.2 (i=1,2,...,m) AND MS.

By this time, the output of the counter 31 is already present code "00...01", which is fed to the input of the decoder 25, so the first output is a single signal. This signal is applied to the first inputs of the elements 52 And 55, but since the interrupt signal from the counter 34 was then isolated signal passing through the inverter 45 becomes zero and gets on the second stroke element 52, thereby preventing the signal on, and to the second input element 55 And into a single signal, allowing the signal on), the. With the element 55 And the signal gets to the elements 50.1.j and 51.2.j. As a positive signal on the first input is present only elements 50.1.2 and 51.2.1 through them and pass positive signals to the corresponding elements 42.1.2 and 42.2.1 OR do on the counting input of the counter 40.1.2 and 40.2.1, increasing their contents on the unit. Thus fixation of the arc on the right diagonal MILLISECONDS.

This continues until, until the overflow counter 27, the counter 33. Overflow of the counter 27 will happen if its content exceeds code number n. In this case, the output of the overflow appears a single pulse, which is supplied to the counting input of the counter 26 rows and increases its contents on the leading edge of the unit, setting the code it deuces ("00...010"). Code number two to the input of the decoder 18 and the installation of the meter inlet 27, establishing therein an initial value equal to the code deuces ("00...010"). The second output of the decoder 18, you receive a single pulse, which is supplied to control inputs of the block 39.2 elements of the ban, thus allowing passage of signals from the indicator outputs of the elements of the second row of the matrix 1, which pass through corresponding inputs of a group 41.1-41.m items OR proceed to the appropriate S-inputs of the group 37.1-37.m triggers, setting them in dinoe state in the presence of the respective individual signals. Further work is as described above.

The overflow of the first counter 33 fixed arc means that the fixation of the arcs of the initial graph in the right diagonals MS finished. The output signal from the overflow of the counter 33 is supplied to the S input of the trigger 36, relieving the state of the logical unit. Then on his direct output will be a single signal, and the inverse - zero. The zero signal from the inverted output of the trigger 36 is supplied to an enable input of the multiplexer 17 and prevents the passage of signals at its output. With direct access to the trigger 36 single signal gets to the second input element 60 And allowing the passage of the pulse at the elements 58 and 59 I.

Then the process repeats as described above until, until you have processed all the values of the adjacency matrix of the original graph. This will happen when the output of the overflow of the counter 26 a signal overflow, which goes to the output of the overflow device 65, which indicates the end of the process of finding the values of the lower bounds for accommodation in MILLISECONDS.

By this time, the second adder 38 will contain the required total value of the lower bounds on the inputs which have already received the relevant codes from the outputs of the counters 40.i.j(i=1,2,...m, j-1,2,...,n) matrix 40.i.j (i=1,2,...,m, j-1,2,...,n) counters fixed arcs. The total value of the lower estimate is the output of the adder 38 is supplied to the output 64 of the values of the lower bounds with subsequent supply to WOW for further processing.

The device search lower bounds for accommodation in fully connected matrix systems with unidirectional data transmission containing a matrix of m rows and n columns of elements of a homogeneous environment, n blocks of counting units, the unit finding the maximum of the first adder, a memory unit, and the control inputs a permutation of the columns of the matrix elements of the homogeneous medium is connected to the control input of the permutation of the columns of the device, the control inputs by permuting the rows of the matrix elements of the homogeneous medium is connected to the control input by permuting the rows of the device, the inputs setup matrix elements of the homogeneous medium is connected to the input device setting information input matrix elements of the homogeneous medium is connected to the input of the recording device, the indicator outputs elements of the j-th column (j=1,2,...,n) the matrix elements of the homogeneous medium is connected to the input of the j-th block of the calculation unit, the output of which is connected to the j-th input block finding the maximum and the j-th input of the first adder, the outputs of which are connected with the output of the maximal length of the edges of the device and output the total length of the edges of the device, respectively, the control input of the write memory block is connected to the control input of the recording device, the information outputs of i-th row (i=1,2,...,m) matrix elements homogeneous environment connected with i-m information is authorized by the input of the memory block, the output of which is connected with the information output device, characterized in that it additionally introduced search block lower bounds containing the pulse generator, the first, second and third multiplexers select, the decoder selecting line, the first, second, third and fourth decoders incident to a vertex, the first, second and third decoders fixed arc, row count, column counter, the first, second and third counter fixed arc, the first, second, third and fourth counters incident to a vertex, the first and second trigger mode, the group of m triggers a second adder, a group of m blocks of elements of the ban, the matrix (i.j) (i=1,2,...,m, j=1,2,...,n) counters fixed arcs matrix (i.j) (i=1,2,...,m, j=1,2,...,n) elements OR the first matrix (i.j) (i=1,2,...,m, j=1,2,...,n), the second matrix (i.j) (i=1,2,...,m, j=1,2,...,n), the third matrix (i.j) (i=1,2,...m, j=1,2,...,n), the fourth matrix (i.j) (i=l,2,...,m, j=1,2,...,n), the fifth matrix (i.j) (i=1,2,...,m, j=1,2,...,n), the sixth matrix (i.j) (i=1,2,...,m, j=1,2,...,n) elements And the element OR the first and second inverters, the first, second, third, fourth, fifth, sixth, seventh, eighth, ninth and tenth elements And group m elements OR, the starting device is connected to the pulse generator, the output of which is connected to the first input of the third element And the second input is connected to the direct output of the second trigger, the output of the third is about the element And connected to the second input of the fourth element, And to the first input of the second element And to the second input of the first element And to the first input of the fourth element And connected to the generator output and the fourth output element And is connected to the input of the second element OR the output of which is connected to the first input of the first element OR the counting input of the third counter, the output of the overflow which is connected to the counting inputs of the third and fourth counters incident to a vertex, the output of the third counter connected to the input of the third decoder fixed arc, outputs 1 through m-th of which are connected to respective first inputs of the fifth, sixth, seventh, eighth, ninth and tenth elements And to the second input of the eighth, ninth and tenth elements And connected the output of the third inverter and to the second inputs of the fifth, sixth and seventh element And connected the output of the overflow of the fourth counter is incident to a vertex, which is also connected to the input of the third inverter, the outputs of the fifth, sixth, seventh element And connected to the first inputs of the elements (i.j) and (i.j) (i=1,2,...,m, j=1,2,...,m) And outputs the eighth, ninth and tenth elements And connected to the first inputs of the elements (i.j) and (i.j) (i=1,2,...,m, j=1,2,...,m) And output overflow fourth counter connected to the reset input of the third counter, the inputs of the third and fourth counter connected to the output required is LEGO multiplexer select item the outputs of the third and fourth counter connected to the inputs of the third and fourth decoders, the outputs from the 1-St to m-th third decoder connected to the first input (i.j) and (i.j) element (i=1,2,...,m, j=1,...,2,m) And outputs the fourth decoder 1-th m-th connected to the second input (i.j) and (i.j) element (i=1,2,...,m, j=1,2,...,m) And the inverse the output of the second trigger connected to allows input of the third multiplexer, the S input of the second trigger connected to the output of the overflow of the third counter, the R input of the second trigger connected to the output of the overflow of the second counter is incident to a vertex, inputs 1 through m-th of the third multiplexer connected to the corresponding outputs of the group m of the trigger control input of the third multiplexer is connected to the output of the column counter, the second input of the second element And is connected to allows the input of the second multiplexer select and to direct the output of the first trigger mode inverted output of which is connected to allow input of the first multiplexer selecting element and to the first input of the first element And whose output is connected to the counting input of the first counter fixed arc and to the first input member OR the output of the second element And is connected with the second input of the first element OR the enable input of the second counter is incident to a vertex, respectively, the S-input of the first triggerlike connected to the output of the overflow of the first counter is incident to a vertex, the counting input of the second counter fixed arc connected to the reset input of the second counter is incident to a vertex counting input connected to the output of the second multiplexer selection control input of which is connected to the control input of the first multiplexer selecting element and to the output of the column counter, a counting input connected to the output of the first element OR the installation counter input columns connected to the output of the counter lines and to the input of the decoder, the row selection output counter overflow lines connected to the output of the overflow device, the outputs from the 1-th through n-th decoder selecting lines connected to respective control inputs of the group of m elements of the ban, corresponding inputs of which are connected to the indicator outputs of the respective elements of the first through n-th columns of the matrix 1 elements of a homogeneous environment, the outputs of the groups of m elements prohibition connected to respective inputs of the groups of m elements OR the corresponding outputs are connected to the corresponding S-inputs of the group m RS-flip-flops corresponding to the R-inputs of which are connected to the output of the counter overflow column and to the counting input of the counter lines, the outputs of the group of m triggers connected to the corresponding inputs of the first, second and third multiplexers select, the output of the first multiplex the ora of the selection element is connected to the enable input the output of the first counter incident to a vertex, corresponding to the counting input of which is connected to the output of the overflow of the first counter fixed arc, the output of which is connected to the input of the first decoder fixed arc of the i-th output (i=1,2,...,m) which are connected to respective first inputs (i.j) (i=1,2,...,m, j=1,2,...,n) elements, And the output of the second counter fixed arc connected to the input of the second decoder fixed arc corresponding to j-th (Q=1,2,...,n) the output of which is connected with the second inputs (i.j) elements (i=1,2,...,m, j=1,2,...,n) And the output of the second counter is incident to a vertex is connected to the input of the second decoder incident to a vertex corresponding to i-th (i=1,2, m) the output of which is connected to the first input (i.j) element (i=1,2,...,m, j=1,2,...,n) And the first counter is incident to a vertex is connected to the input of the first decoder incident to a vertex corresponding to i-th (i=1,2,...,m) output which is connected to the second input (i.j) item (1=1,2,...,m, j=1,2,...,n) And the outputs of the first (i.j), second (i.j), third (i.j), fourth (i.j), fifth (i.j), sixth (i.j) is connected to respective inputs of the elements (i.j) OR corresponding outputs of which are connected to the respective counting inputs (i.j) counters fixed arcs whose outputs are connected to respective inputs of the second adder, the output of which is connected to the output values of the lower bounds device.



 

Same patents:

FIELD: information technology.

SUBSTANCE: invention relates to a system and a method which establish connected relationship with a graphics program such as Adobe Illustrator, and are designed for reconstructing each surface in three dimensions so as to include content of a two-dimensional design drawing, converting a two-dimensional object into a three-dimensional object. Basic shapes of boxes are presented to the user. Dimensions which correspond to the shape of the box selected by the user are taken. Coordinate values of the design drawing are altered depending on the dimensions received from the user. The design drawing with altered coordinate values is presented to the user. A specimen made by the user is divided for conformity with surfaces shown on the design drawing. Three-dimensional coordinate values are established based on the coordinate values entered. The divided specimen is put onto the three-dimensional coordinate values, generating three-dimensional data.

EFFECT: design of a system which enables easy viewing of a design drawing of the shape of each packaging box without professional knowledge on the package.

4 cl, 4 dwg

FIELD: medicine.

SUBSTANCE: according to the one version, the present invention involves an electroencephalographic system comprising sensors used to lock an electromagnetic signal from the patient; a signal processing system; and a computing system. The latter is configured to support multiple chains of related program delivery. It initiates the first chain of the related program delivery representing a measuring cell wherein data are filtered and averaged in some cases. As a rule, data are filtered over particular latency. As soon as data are filtered and averaged, the result is transferred to the second chain of the related program delivery that is a source reconstruction unit which then starts to generate reconstruction of a source to be tested. After that the measuring cell locks and processes new electromagnetic data of a new test while reconstruction of a source is carried out at the latest test. Test adjustment is carried out by results of reconstruction of a source.

EFFECT: higher reliability of reproduction of a source.

20 cl, 2 dwg

FIELD: physics, computer engineering.

SUBSTANCE: invention is related to the field of computer engineering and is designed for modeling of tasks in design of computer systems (CS). Device contains matrix from m lines and n columns of uniform medium elements, n blocks of units counting, block of maximum detection, summator, memory block, block for intensity calculation comprising pulse generator, lines decoder, decoder of selected module, multiplexor of selected element, two counters of lines, two counters of columns, group from m counters of intensity values, group from m RS-triggers, mode trigger, group of m blocks of prohibition elements, two AND elements, three OR elements, group from m OR elements.

EFFECT: expansion of device application field due to introduction of facilities for calculation of location intensity value in fully connected matrix systems in case of directive transmission of data.

5 dwg

FIELD: physics, computer engineering.

SUBSTANCE: invention is related to the field of digital computer engineering and is designed for modeling of combinatory tasks in design of computer systems (CS). Device contains matrix from m lines and n columns of uniform medium elements, n blocks of units counting, block of maximum detection, summator, memory block, block for intensity calculation comprising pulse generator, lines decoder, decoder of selected module, multiplexor of element selection, decoder of selected module, counter of lines, counter of columns, group from m counters of intensity values, group from m prohibition blocks, group of m RS-triggers, group from m OR elements.

EFFECT: expansion of device application field due to introduction of facilities for calculation of location intensity value in fully connected matrix systems.

5 dwg

FIELD: physics; image processing.

SUBSTANCE: present invention relates to a multifactorial system and method of moving virtual mannequin (10) in a virtual medium. Mannequin (10) is defined by a general position and several degrees of freedom of articulation. The method provides for: endowment of attraction factor (32), acting on several degrees of freedom of articulation of mannequin (10) for moving it to a target; endowment of a displacement factor (21), acting on the general position of mannequin (10) depending on parametres, defining its surrounding medium, for preventing mannequin (10) from colliding with elements of the medium. The method also provides for ergonomic factor (34), acting on several degrees of freedom of articulation of mannequin (10) for automatic adjustment of the position of mannequin (10) when moving to a target.

EFFECT: provision for an optimum level of comfort of positions occupied by the mannequin without need for carrying out further tests.

21 cl, 11 dwg

FIELD: physics; image processing.

SUBSTANCE: present invention relates to simulation of movements of a virtual mannequin. The proposed graphic interface system, allows for displaying two windows (10, 20) on a screen. First window (10) has the general image of mannequin (100), which allows for selecting part of the body of the mannequin directly on the screen, using a selection device (a mouse, for example). As a result, the selected part of the body appears on second window (20) in magnified form together with symbols (120), indicating all degrees of freedom, provided for that part of the body. An operator can have direct effect on symbols (120) of degrees of freedom for blocking or unblocking them, as well as for direct control of the kinematics of the model.

EFFECT: easier direct control of kinematics and control of the degrees of freedom of a virtual mannequin.

10 cl, 7 dwg

FIELD: physics; computer facilities.

SUBSTANCE: invention concerns to mapping devices. The expedient of mapping of the equipment of a bottom of a boring column (EBBC) with use of the vector drawing includes parse and interpretation of initial data EBBC for development of packages of the data corresponding to EBBC builders; EBBC assemblage with use of builders of the vector drawing of library of the vector drawing and builders of the vector drawing represent EBBC builders, and EBBC mapping in the chosen gauge. The system contains processor and storage in which the program for embodying of an expedient of mapping of the equipment of a bottom of a boring column contains.

EFFECT: representation of the bore-hole and the superficial measuring with an animated drawing.

25 cl, 23 dwg

FIELD: physics, computer facilities.

SUBSTANCE: invention concerns field of computer facilities and is intended for modelling of problems at designing of computing systems. Device contains matrix from m lines and n columns of devices of homogeneous environment, block of finding of the maximum, first adder, storage block, n blocks of calculation of unities, block of search of the inferior estimate, containing generator of impulses, counter of lines, counter of columns, second adder, multiplexer of select of device, first and second decoders of incidence vertex, decoder of select of the line, first group from m devices OR, group from m ring counters, the second group from m devices OR, group from m the triggers, the first and second counters of incidence vertex, group from m blocks of devices of an interdiction.

EFFECT: expansion of scope of the device at expense of introduction of resorts for search of inferior estimate of arrangement in ring systems by measure of minimisation of intensity of interaction of processes and data.

5 dwg

FIELD: physics, computer equipment.

SUBSTANCE: invention is related to modeling systems. Method for object manufacture that has potential {x}, generated as response to the field {f} imposed on it, includes stage of object geometric model design. Mathematical model processed with the help of computer is generated by means of object geometric model discretisation into multiple final elements and determination of units at element borders, at that in units values of field {f} and potential {x} are established. Then matrix [k] of material properties is calculated on the basis of ratio {f}=[k]{x}. Then coefficients of material properties are recovered from matrix [k] of material properties for every final element in mathematical model processed with the help of computer, and recovered coefficients of material properties are compared to coefficients of material properties for known materials, in order to coordinate recovered coefficients of material properties with coefficients of material properties for known materials. Then production parameters are determined that correspond to coordinating coefficients of material properties.

EFFECT: determination of optimised composite matrix for specific object.

14 cl, 13 dwg

FIELD: computer engineering.

SUBSTANCE: computer on user side contains data input facility for input of material name and identification number of material model, storing facility, data transmission facility, facility for receiving data about material properties, numerical analysis facility. Computer on server side contains data storage facility, data receive facility, facility for extraction types of data about material properties from mechanical properties value, thermophysical properties value and electromagnetic properties value, data transmission facility, data coding facility. Versions of methods for numerical analysis data submission to computer on user side are also disclosed.

EFFECT: raising confidentiality during data exchange between computer on server side and computer on user side.

4 cl, 11 dwg

FIELD: computer engineering, possible use for parallel computation by digit cuts of sums of paired productions of complex numbers, may be used for solving problems of digital signals processing, solving problems of spectral analysis and hydro-location, automatic control systems.

SUBSTANCE: device contains adder-subtracter, two blocks for computing sums of products, each one of which comprises multiplier registers, multiplicand registers, matrix multiplexers, transformer of equilibrium codes to positional codes, matrix adders.

EFFECT: expanded functional capabilities, increased speed of operation.

5 dwg

FIELD: computer science, possible use for engineering devices meant for processing numeric information arrays, in particular, for permutation of rows of two-dimensional array (matrix) stored in memory of computing device.

SUBSTANCE: device contains matrix of unary first memory registers and matrix of unary registers of second memory, which are identical to each other. Between them a commutator is positioned. Unary memory registers, positioned conditionally in one row, are connected between each other as shifting row registers. Commutator on basis of law given externally connects output of shifting register of first memory, corresponding to i-numbered row, to input of shifting register of second memory, corresponding to j-numbered row in second memory. After sending a packet of shifting pulses to shifting input of i-numbered shifting register of first memory, information from it moves to j-numbered shifting register of second memory. Therefore, transfer of i-numbered row to j-numbered position in new array occurs. Transfer of rows can be realized row-wise, or simultaneously for all, while structure of commutator is different for different cases.

EFFECT: realization of given permutation of rows and/or columns of two-dimensional array.

7 cl, 10 dwg, 1 tbl

FIELD: computer science.

SUBSTANCE: device has block of registers of first memory, block of registers of second memory, block for controlling reading of columns, block for controlling reading of rows, block for controlling reverse recording; according to second variant, device has same elements excluding block for controlling reverse recording. Third variant of device is different from second variant by absence of block for controlling reading of columns, and fourth variant of device is different from second one by absence of block for controlling reading of rows.

EFFECT: higher efficiency.

4 cl, 9 dwg

The invention relates to computer technology and can be used in data mining systems, including processing and analysis of geological and geophysical information and other data obtained in the study of natural or socio-economic objects or phenomena

The invention relates to the field of spectral analysis and can be used in the classification of quasi-periodic signals

The invention relates to computer technology and can be used in specialized solvers for the solution of problems, including digital processing of signals and images

The invention relates to the field of computer engineering and can be used in specialized computer systems for computing the eigenvalues of the matrix (nn)

The invention relates to computer technology and can be used in specialized computer systems to calculate the two-dimensional convolution

FIELD: physics, computer engineering.

SUBSTANCE: invention relates to methods and systems for downloading I/O processes from a first computer onto a second computer using a network interconnection through RDMA. The method and system includes a client on the first computer provided with information through a RDMA connection with a server on the second computer through a simplified input/output protocol. Overall, the protocol includes a network detection step, followed by I/O processing. At the detection step, the client and the server determine the shortest list of shared providers capable of RDMA. During I/O processing, the client gives I/O requests for downloading from the second machine through a mutually authenticated channel. The I/O model is asymmetrical with reading operations carried out through traditional sending. Requests for reading and recording can be completed in poll mode and in interruption mode. Buffers are controlled through a confidence mechanism.

EFFECT: simplified input/output protocol.

21 cl, 39 dwg

Up!