A device for calculating a two-dimensional convolution

 

(57) Abstract:

The invention relates to computer technology and can be used in specialized computer systems to calculate the two-dimensional convolution. The purpose of the invention is the reduction of hardware costs, increase reliability at the expense of control and redundancy and enhanced functions by solving problems of different dimensions. This objective is achieved in that contains L = I + R processing units 11, where I is the dimensionality of the problem, R is the number of redundant processing units, L - combinational adders 2, (L - I) registers 3, L - nodes comparison 4, (L - I) a group of items OR 5, L - group elements And 6 and the element OR NOT 7. 1 C.p. f-crystals, 2 tab., 3 Il.

The invention relates to the field of computer engineering and can be used in specialized computer systems to calculate the two-dimensional convolution.

A device containing a P x Q operating units, where P x Q is the window size of the two-dimensional convolution, each of which contains a register weighting factorpqwhere P = 1, ..., P, q = 1,...., Q - adder, multiplier, and shift register [1].

The closest in technical essence to the por is holding registers, the multiplier and adder [2].

Usually to ensure the accuracy obtained by the data processing results using the test periodic monitoring conducted by using external software and hardware. When the periodic test control the probability of missing failure processing unit proportional to the time between the test checks (control period), the volume of erroneous information, the issuance of which occurs between the test checks, is also proportional to the control period. Time spent on test validation are determined by the volume of the test, so the bandwidth range of the processing units of the known devices is inversely proportional to the time spent on test validation. The probability of detection of the computational process after detection of the failure processing unit (obtaining a reliable result on the output device) is proportional to the number n of processing units of the device (the length n of the line device).

The purpose of the invention is the reduction of hardware costs, increase reliability at the expense of control and redundancy and enhanced functions by solving problems of various 1, where I is the dimensionality of the problem, and the clock input device 17 is connected to the clock inputs of the processing units from the first to the I-th information inputs of the first 8 and second 9 groups of devices are connected respectively to the information inputs of the first and second groups of the first processing unit, the Iaboutthe outputs of the first and second groups of the i-th processing unit (i = 1, ..., I-1) are connected respectively to the information inputs of the first and second groups (i + 1)-th processing unit, introduced with the (I +1)-th to L-th processing units, where L = I + R, R is the number of redundant processing units, L combinational adders 2, (L - 1) register 3, L nodes comparison 4, (L - 1) group elements, OR 5, L groups of elements And 6 and the element OR NOT 7, and the first, second and third control inputs 10 and 12 are connected respectively to the first, second and third control inputs of the first processing unit, the first, second and third outputs of the i-th processing unit (where i = 1, ..., I - 1) are connected respectively to the first, second and third control inputs (I + 1)-th processing unit, a clock input device 17 is connected to the clock inputs of the processing units with (I + 1)th to L-th and the clock inputs of registers 3 from the first to the (L - 1)-th, the outputs of the first and second groups, the first, second and third outputs of the j-th bwamu, the second and third control inputs (j + 1)-th processing unit, the fourth and fifth control inputs 13 and 14 are connected respectively to the fourth and fifth inputs of the processing units from the first to the L-th control inputs of the first group of 16 devices are connected respectively to the control inputs of the first groups of processing units from the first to the L-th and respectively to the inputs of the first group of nodes in comparison with the first through L-th whose outputs are connected respectively to the inputs of the element OR NOT 7, the output of which is connected to the output 25 of the sign of failure, the control inputs of the second group, 15 of which are connected respectively to the control inputs of the second group of the first processing unit, the inputs of the third group of the K-th processing unit (where K = I,...., L) are connected respectively to the information inputs of the group of K-combinational adder 2, the outputs of the n-th combinational adder 2 (where n = I, ..., L - 1) are connected respectively to the information inputs of the n-th register 3 and respectively to the inputs of the second group of the n-th node comparison 4, the outputs of the n-th register 3 are connected respectively to the first inputs of the elements OR 5 n-th group, the outputs of the fourth group of the K-th processing unit connected respectively to the first inputs elementvalue group of the n-th processing unit connected respectively to the second inputs of the elements OR n-th group, the outputs of which are connected respectively to the control inputs of the second group (n + 1)-th processing unit and respectively to the outputs 23 (L + n)-th group of the device, the outputs of the L-th adder connected respectively to the inputs of the second group of L-th node of the comparison and respectively to the outputs 23 of the L-th group of devices, the fourth output of the K-th processing unit connected to the information input of the K-th adder, the second input elements And 6 K-th group and the K-th output 24 sign of failure, device groups, K-th input set of the first group 18, K-th input set of the second group 19, K-th input set of the third group 20 and the K-th input block 21 are connected respectively to the first, second, and third inputs of the installation and the entry lock of the K-th processing unit. Each processing unit 1 includes first and second computing nodes 26 and 27, the node comparison 28, the trigger 29, the first to the third nodes 30 to 32 elements And node elements OR 33 and the element And 34, and the control inputs of the first group 43 processing unit connected respectively to the control inputs of the groups of the first and second computing nodes, the information inputs of the first and second groups 35 and 36, with the first to fifth control inputs 37 and 41 and the control inputs of the second graphogame group to the second node 31 elements And, the outputs of the first group of the first node elements And connected respectively to the inputs of the first group of node 33 elements OR whose outputs are connected respectively to the outputs of the first 52 and second 53, 54 fourth groups, the first 55, 56 second and third 57 outputs of the processing unit, the outputs of the first group to the second node 31 elements And connected respectively to the information inputs of the first and second groups and to the control inputs from the first to the fifth of the first 26 and second 27 compute nodes, the outputs of the first, second and third groups, the first, the second and third outputs of the first computing node connected respectively to the inputs of the first node group comparison 28 and to the input groups of the third node 32 elements And whose outputs are connected respectively to the inputs of the second group of node 33 elements OR, the outputs of the first, second and third groups, the first, second and third outputs of the second computing node 27 is connected respectively to the inputs of the second node group comparison 28, the output of which is connected to the information input of the trigger 29, the output of which is connected to the input of the third node 32 elements And the inverse input of the first node, the input of the second node 31 and fourth elements And the output 50 of the processing unit outputs the second groups of the first is, the first input set 46 which is connected to the inputs of the installation to its original state of the first and second computing nodes, the second and third inputs installation 47 and 48, the clock input 45 and the input of the lock 44 processing unit connected respectively to the input set to zero trigger 29, the input set to the trigger unit 29, the first and second (inverse) input element And 34, the output of which is connected to the clock inputs of the first and second computing nodes 26 and 27 and the synchronization input of the trigger 29.

Each compute node 26 (27) contains the first through fourth groups of registers 58, 59, 61, 63, the first and second registers 60 and 62, a multiplier 64 and the adder 65, trigger group 66, first to fourth trigger 67 - 70, (2M + 2N + 5) groups of elements AND 71, ..., 78, 791, ..., 79M, 801, ..., 80N, . . . , 811. .., 81N-1, 821, ..., 82M-2(where M = (Q + 1)J + 1, N = Q + 2), eight groups of elements OR 84,...., 91, the first and second decoders 93 and 94, M elements And 83 and the element OR 92, and informational inputs of the first group 95 node connected to information inputs of the first register 581the first group and the first inputs of elements And 71 of the first group, the outputs of which are connected respectively to the first inputs of the OR element 84 PE the water and on the register of the first group 58 (where a = I, ...., M - I) is connected to information inputs (a + I)-th register 58 of the first group and the first inputs of elements AND 79a(a + 1)-th group, the outputs of the M-th register of the first group 58Mconnected to the first inputs of elements AND 79M(M + 1)-th group, the outputs of the elements And 79 groups second (M + 1)-th connected respectively to the inputs of elements OR 88 of the second group, the outputs of which are connected to the outputs of the first group of compute nodes, the outputs of the first register 59Iconnected to the first inputs of elements AND 80I(M + 2)-th group of information inputs of the second register 592the second group of information inputs of the first group of multiplier 64, the outputs of the b-th register of the second group 59b(where b = 2, ..., N - I) connected to information inputs (b + 1)-th register 59 of the second group and the first inputs of elements AND 80b(M + 1 + b)-th group, the outputs of the N-th register 59Nthe second group are connected to first inputs of elements AND 80N(M + N + 1)-th group, the outputs of the elements And groups (M + 2) th to (M + N + 1)-th connected respectively to the inputs of elements OR 89 of the third group, the outputs of which are connected respectively to the first inputs of elements And 72 (M + N + 2)-th group, the outputs of which are connected respectively to the second inputs of the elements OR the first g is that connected to the first inputs of the elements OR 85 of the fourth group, the outputs are connected to information inputs of the first group of the adder 65, the outputs of which are connected to first inputs of elements And 77 (M + N + 4)-th group and the information inputs of the first register 62, the outputs of which are connected respectively to the information inputs of the second adder, the information inputs of the second group 96 is connected to information inputs of the second register 60 and to the first inputs of elements And 74 (M + N + 5)-th group, the outputs are connected to first inputs of elements OR 86 of the fifth group, the outputs of which are connected to information inputs of the first register 61, the third group, the outputs of which are connected to information inputs of the second multiplier, the information inputs of the second register 612the third group and the first inputs of elements AND 811(M + N + 6)-th group, the outputs of the first register 61 of the third group (where b = 2, ..., N - 2) connected to information inputs (b + 1)-th register 61 of the third group and the first input element 81b(M + N + 5 + b)-th group, o (N - 1)-th register 61 of the third group are connected to first inputs of elements AND 81N-1(M + 2N + 4)-th group, the outputs of the elements And 81 groups with (M + N + 6) th to (M + 2N + 4)-th connected to respective inputs of the elements OR 90 of the sixth group, the outputs of which are under the but to the second inputs of the elements OR 86 of the fifth group, the outputs of the second register 60 is connected to the outputs of the second group of compute nodes, the outputs of the first register 631the fourth group are connected to first inputs of elements And (M + 2N + 6)-th group 76 and items, and (M + 2N + 7)-th group 78, the outputs of which are connected respectively to the second inputs of the elements OR 85 of the fourth group and the first inputs of elements OR 87 of the seventh group, the outputs of which are connected to information inputs of the second register 632the fourth group, the outputs of which are connected to the outputs of the third group 107 computing unit, the information input of the third register 633the fourth group and the first inputs of elements AND 821(M + 2N + 8)-th group, the outputs From the first register 63cthe fourth group (where C = 3, ..., M - 2) are connected respectively to the information inputs (C + 1)-th register of the fourth group and the first inputs of elements AND 82c-1(N + 2M + 6 + C)-th group, the outputs of the (M - 1)-th register 63M-1the fourth group are connected respectively to the first inputs of elements AND 82M-2(2N + 2M + 4)-th group, the outputs of the elements And 82 groups with (2N + M + 8) th to (2N + 2M + 4)-th connected to respective inputs of the elements OR 91 of the eighth group, the outputs of which are connected to information inputs of the first register 631cetm) inputs of elements And (M + N + 2)-th group and the information input of the first flip-flop 661group, the output of the d-th flip-flop 83dgroup (where d = 1, ..., M - 1) connected to the first input of the d-th element AND 83dand information log (d + 1)-th flip-flop, the output of the M-th flip-flop group connected to the first input M-th element AND 83Mthe outputs of the elements And 83 from the first to the M-th connected respectively to the inputs of the OR element 92, the output of which is connected to the first output of the computing node, the second control input 98 which is connected to the second inputs of elements And 74 (M + N + 5)-th group, the second (inverse) input element And 75 (M + 2N +5)-th group and the information input of the first flip-flop 67, the output of which is connected to the second output of the computing node, the third control input of which is connected to the first input set to zero the first case of the fourth group and the information input of the second trigger, the output of which is connected to the third output of the computing node, the fourth control input 100 which is connected to the information input of the third trigger 68, the output of which is connected to the first input set to zero the first register, the fifth control input 101 of the computing node is connected to the information input of the fourth flip-flop 69, the output of which is connected to the second inputs of elements And (M + 2N +6) is the-th group, the control inputs of the first through r-th 1021and (r + 1)-th and V-th 1022group of compute nodes (where r is log2M, V-r=log2N) are connected respectively to the inputs of the first and second decoders, f-th output of the first decoder 93 (where f = 1, ..., M) is connected to the second inputs of elements And (f + 1)-th group, the elements AND the (2N + M + 5 + h)-th group (where h = 3, ..., M) and f-element And p-th output of the second decoder 94 (where p = 1 . . ., N) is connected to the second inputs of elements And (M + 1 + q)-th group and elements And (M + N + 4 + q)-th group (where q = 2, ..., N), the clock input 104 of the computing module is connected to the inputs of a read/write register group from the first to the fourth, first and second registers, inputs synchronization trigger group and triggers from the first to the fourth input 103 of the installation to its original state computing node connected to the inputs setup to zero all of the triggers, a second register, register groups from the first to the third register from the second to the (M -1)-th of the fourth group and the second inputs of the installation in the null of the first register and the first register of the fourth group.

In Fig. 1 shows a block diagram of the device of Fig. 2 is a block diagram of the processing unit of Fig. 3 is a structural diagram of a computing node.

Ustroistvo, R - the number of redundant processing units, L combinational adders 2, (L - 1) register 3, L nodes comparison 4, (L - 1) group elements, OR 5, L groups of elements And 6, the element OR NOT 7, informational inputs 8 and 9, control inputs 10 - 16, clock input 17, the inputs setup 18 - 20, the input block 21, the outputs 22 of the first group of the outputs 23 of the second group of the outputs 24 of the group sign the waiver and release of 25 sign of failure. Each processing unit 1 includes compute nodes 26 and 27, the node comparison 28, the trigger 29, the element nodes And 30 - 32, the node elements OR 33, the And gate 34, the information inputs 35 and 36, the control inputs of 37 - 43, entry lock 44, the clock input 45, the inputs setup 46 - 48, the outputs 49 - 57. Each compute node 26 (27) contains the registers 58 - 63, combinational multiplier 64, the combinational adder 65, triggers, 66 - 70, member groups And 71 - 82, elements, And 83, groups of items OR 84 - 91, item, OR 92, decoders 93 and 94, information inputs 95 and 96, the control inputs 97 - 102, entry 103 initial setup, the clock input 104 and outputs 105 - 110.

The basis of operation of the device based on the algorithm for computing the two-dimensional convolution

< / BR>
which consists of two parts:

< / BR>
The first part of the algorithm is the calculation of

< / BR>
the other index (K) in parentheses indicates the number of operation cycle of the device, and the index K without parentheses is the number of recurrent step.

Compute node 26 (27) has the ability to implement the following functions:

< / BR>
where xiandivalues respectively at the inputs 95 and 96 compute nodes to the i-th step, < Reg 62 >i- the contents of register 62 at i-th step,i1,i2,i3,i4,i5values respectively to the control inputs 97 - 101 computing node at i-th step, xi,iand Yivalues respectively at the outputs 105, 106 and 107 of the computing node at the i-th clock cycle, Ti1,Ti2and Ti3/values respectively at the outputs 108, 109 and 110 of the computing node at i-th step.

Compute node 26 (27) works as follows.

For informational inputs 95 and 96 are served respectively the values of XKLandpq. The mode of operation of the computing node sets the control signals1,...,5served respectively to the inputs 97 - 101.

When1= 1 the input value of Xkerecorded in the registers 58 and 59 (elements And 71 are open and available at the output 105 delay (Q + 1)J + 1, tick.

When2= 1 input mn of the act. When2= 0 the value of pqrecorded in the register 61Q+1that is overwritten in the register 611(items And 75 are open).

When3= 1 register 631set to the zero state.

When4= 1 the register 62 is set to the zero state.

When5= 1 the contents of register 631through the open items And 76 is introduced in the information input combinational adder 65, the output of which through public members And 77 is recorded in the register 632. When5= 0 the value of the X - output combinational multiplier 64 through the open items And 73 is introduced in the information input combinational adder 65, the output of which is the resulting value of Yijthrough the elements And 77 are recorded in the register 632and issued to the output 107 of the computing node. The value of dimension M (Q+1)I+1 and N Q + 2, used to calculate the convolution of this device are fed through the input device 16, the input 43 of the processing units 1 and outputs 1021and 1022compute nodes respectively to the inputs of the decoders 93 and 94. When the decode values of M, with the corresponding output of the decoder 93, issued a single valueMthat elementov OR 88, 91 and 92. When the decode values of N, with the corresponding output of the decoder 94 is given a single valueNthat opens the corresponding elements 80 and 81, the outputs of which are reported to the inputs of the elements 89 and 90. Thus, the device implements the possibility of solving problems of two-dimensional convolution of different dimensions for different values of Z and Q).

Input and output data streams are formed according to the following expressions.

XKLserved in time

= to+ max{O, l}(Q+1)+min{0;(-1)}-K(Q+1)J,

where K =-(P-1), (I-1), l= -(Q-1),(J-1),

to=(I-1)(Q+1)j

Valuespqserved in time

tpq= to+p(Q+1)J+q,

where

The control signal 1= 1 is time , in other moments1= 0.

The control signal2= 1 is time , in other moments 2= 0

The control signal3= 1 is the time

< / BR>
where , in other moments3= 0.

The control signal4= 1 is the i-th processing unit 1iin moments

< / BR>
where in other moments4= 0.

The control signal5= 1 is the i-th processing unit in moments remake processing 1iat times

< / BR>
The last element of yIZformed in time

< / BR>
The submission period of the elements of XKLthe immediate tasks of the two-dimensional convolution is equal to

T = J(Q+1)(P+I-1)-Q+1

tick.

Each processing unit 1 produces duplication of operations performed by the computational nodes 26 and 27. The results of operations are generated at the output of the combinational adder 65 upon completion of transients in combinational circuits 64 and 65 and through the elements AND 77 OR 87 from the output of the register 632issued to the outputs of the computing nodes 107 26 (27), where these results are received, respectively, on the information input node of the comparison 28. When the coincidence of the information on the information input node 28 comparison of computational nodes 26 and 27, the processing unit 1jis considered healthy and one output node 28 comparison is recorded in the trigger 29, which is used for fixing the sign of the health of this processing unit 1j. Output trigger 29 unit is fed to the corresponding inputs of the elements 31 and 32 and the outputs 105 - 110 computing node 26 through the elements And 32 OR 33 and is fed to the outputs 52 - 57 processing unit 1j.bhod this processing unit 1j. In the result, the values of g at the input 42 of the block 1javailable at the output 49 of the block 1j. A single value is given also to the output 50 of the block 1jand, accordingly, the output 24 sign of failure. Single output 24jdevice specifies the means of external control on the health of block 1j. If this does not match the information on the information input node 28 comparison of computational nodes 26 and 27, the processing unit 1jit is considered defective and the zero signal from the output node of the comparison 28 is written in the trigger 29. Output trigger 29 zero signal is supplied to the corresponding inputs of the elements 31 and 32 and the data output from outputs of 105-110 computing node 26 is blocked. Zero, the outputs of the trigger 29 is also provided on the inverted inputs of elements And 30. As a result, the flow of information in the computing nodes 26 and 27 through the elements And 31 is blocked and offers a way of bypassing this processing unit 1j. In this case, the information coming from the previous processing unit 1j-1through elements 30 And 33, issued respectively on the outputs 52 and 57 of this processing unit 1j. The value of g at the input 42 bloodletting, at exit 24jsign of failure. Zero signal at the output 24jdevice specifies the means of external control on the detected fault block 1j.

In order in certain situations force the display unit 1jfrom the device, use the setup input device 18. In this case, the external controls on the input 18jthe device is formed of a single signal through the input 47 of the processing unit 1jis supplied to the input set to zero trigger 29. In order to force the processing unit 1jthe structure of the device, for example, after his forced withdrawal or after fixation of false rejection, using input 19jdevice. In this case, the external controls on the input 19jthe device is formed by a signal via the input 48 of the processing unit 1jis fed to the input of the installation unit of the trigger 29. Thus, the operation processing unit 1jcan be blocked by an input 20jdevice single signal. In this case, the unit via an input 44 of block 1jis supplied to an inverse input element And 34, which blocks the passage of clock pulses is slitely nodes 26 and 27 of block 1jin the initial state at the start and restarts the device using input 21jdevice. For unit 1jin the initial state at the input 21jthe device is a single signal through input 46 of block 1jrises to the inputs of the installation to its original state computing nodes 26 and 27. The input set to the initial state of the computing nodes 26 and 27 are connected to the inputs of the installation in the zero state of all registers and triggers nodes 26 and 27 (Fig. 3 not shown).

To the input 15 of the device is zero value for g. In the presence of intact blocks 11, . .., 1I-1with outputs 241, ..., 24I-1signs of failure are given a single value, which are received at the inputs of the corresponding combinational adders 21, ..., 2I-1. The value of g at the input 42 of the block 1iwhere in the case of health blocks 11, ..., 1I-1equals (I-1). In the case of the health unit 1ithis value g outputted to the output 49 of the block 1iand is supplied to the corresponding input of the combinational adder 2ifrom the output of which is removed is g = i, which is recorded in the register 3iand is fed to the input node of the comparison 4 1iwith output combinational adder 2ireturns the value g = i. When comparing the values of g and I from the output node of the comparison 4igiven a single signal, which is supplied to the corresponding input element OR NOT 7, with which a null signal is fed to the input 25 of an indication of failure. Zero signal at the output 25 of the device indicates the preservation of the health of the device in this step. A single value from the output 50 of the serviceable processing unit 1Kalso fed to corresponding inputs of elements AND 6Kon the other inputs of which the output 54 of the block 1Kcome computed in block 1Kthe values of Yj. With the outputs of the elements OR 5Kreturns the value g, which is output 23K. Thus, in the case of health treatment unit 1Kat exit 22Kgiven the calculated value of Yjand at exit 23togiven a particular value K = g, corresponding to the first index of the element Yj. The value of K issued from the output 23Kused to indicate means of external control on the value of the first index number Yjin different situations of failure-handling blocks 1K'where K' < K. In the case of the blocks 11, ..., 1K-1at the entrance 42 of the block 1Kreceives the value of g=K-1, which is then delivered to the output 51 of the block 1Kwith outputs 43 and 49 of the block 1Kremoved zero values and, thus, the output of the combinational adder 2Kremoved zero g. As a result, the output node of the comparison 4I-1cleared to zero. If block 1IOK, to the input 42 of the block 1Ireceives the value g=I, the output 49 of the block 1Igiven a single signal and therefore, the output of the combinational adder 2Iremoved the value g= I-1. As a result, the output node of the comparison 4Iremoved individual signal which is supplied to the corresponding input element OR NOT 7, the output of which the output 25 of the device is given a zero signal indicating the preservation of the health of the device. A zero value of g generated by the combinational adder 2Kon subsequent cycles, is fed to the corresponding inputs of the elements OR 5Kand further does not affect the value of g generated at the input 42 of the block 1K+1. Thus, in this case, the outputs 220, .. . , 22K-1removed values respectively Y0,j, Y1,j, SUB>, . . ., 23K-1removed values, respectively, 0, 1,..., K-1, exit 23Kis ignored (because the output 24Kthere is zero signal), with outputs 23K+1, . .. , 23Iremoved values, respectively K, K+1,..., I-1. Thus, the processing unit 1Kderived from the computational process by bypassing, and the first of defective spare blocks, for example, 1Iintroduced in the calculation process, the length of the line of well-functioning processing units of 1 device. Upon detection of S bounce blocks 1 is bypassing the failed units 1, as described above. Let K be the number of the last failed block-1 line, then the output 51 of the block 1Kwill be given a value of g= I-S-1, which is fed to the input 42 of the block 1K+1. Because the block 1K+1is considered healthy, the output 49 of the block 1K+1given a single signal, the output of the combinational adder 2K+1will be given a value of g=I-S, which is fed to the input 42 of the block 1K+2etc. When reading the values of g at the input 42 operable unit 1iat the output of the combinational adder 2iformed a value equal to g+1. When reading the values of g at the input 42 of the defective block 1ioutput kombinatsioonidega block 1i+1the ruler. Output combinational adder 2I+S-1to the input node of the comparison 4I+S-1is is g=I-1, from the output node of the comparison 4I+S-1given a single signal, which is supplied to the corresponding input element OR NOT 7. Through the open items And 6 values of Yijgiven the outputs 22, corresponding to the proper processing units 1, while the outputs 23, corresponding to the intact blocks 1, given the values of i. In this case, one of the inputs of the element OR NOT 7 receives a single signal and, respectively, at the output 25 of the sign of failure is zero signal, which indicates the health of the device. When R < S on the output node 4 will be zero, the output of the element OR NOT 7 at exit 25 sign of failure will be given a single value, which indicates the exhaustion of the reserve and failure. Thus, the accumulation of R failures, the efficiency of the device is stored and the length of the line of well-functioning processing units 1 device remains constant. Upon detection of (R+1)-th failure device, output device 25 is given a sign of failure, which then enters the external controls.pwhere p 1, located in the tank, with the operating range of the device receives the calculated value of the iteration.

As a result of processing this value in the compute nodes 26 and 27 and the subsequent comparison of results in the node 28 backup processing units 1pupdated values of the triggers 29 these blocks. Then use this backup processing units 1pwill occur, taking into account their health.

Consider the operation of the device for the particular case I=J=P=Q=2 and R=1. Organization of input and output data streams is given by the expressions:

< / BR>
Organization of input and output data flows, control signals, the contents of the triggers and registers, the values generated at the output of the combinational adder processing units 10and 11are given in table.1.

May 10th cycle of the device detected a failure of the unit 11processing. In this case, the organization of the input and output data flow control signals, the contents of the triggers and registers the generated values at the output of the combinational adder processing units 10, 11and 12(12te t = 11 is locked block 11(further information under its nodes does not affect the remainder of the process) and zeroing block 10at stage t = 12 restarts the device (input unit 10started filing the relevant values). With tact t = 11 is the bypass block 11and inclusion in the backup block 12. The length of the ruler of the device remains the same.

The algorithm computing process after detection of the failure block 1jinvolves the following steps:

cycle i: the fixing block 1jwith the detected failure, the lock block 1jreading information from block 1j+1in block 1j+2, zeroing block 1j+1and locking block 1j+1.

cycle i+1: read data from block 1j+2in block 1j+3, lock, and reset block 1j+2zeroing blocks 11,...,1j-1.

cycle i+2: read data from block 1j+3in block 1j+4, lock, and reset block 1j+3, unlock block 1j+1.

cycle i+3: read data from block 1j+4in block 1j+5, lock, and reset block 1j+4, unlock block 1j+2.

cycle i+to: read information from the array is 1.

If tnthe time (number of cycles) required to prepare for the restart of the device by means of external control, the time reinit line is (j + tn) cycles. All timing diagrams of the filing of the values of the input matrix elements and control signals are generated by means of the external control apparatus or environment. Due to technological crystal structure of IP health or failure of its various fractions are interrelated. The degree of connection between the failures of different shares the IP is measured by the correlation coefficient, the value of which is greater than the higher level of technology and the degree of integration of IP. The presence of at least 16-bit combinational multiplier and adder determines the degree of integration and the level of technology, sufficient for the manifestation of a high degree of correlation of failures. When the control duplication of computational nodes need to bounce these nodes were independent. For this purpose, the nodes 26 and 27 of the processing unit 1 were implemented on different crystals of IP. Similarly, on the basis of the correlation of failures inside the crystal IP, it is necessary to redundant (backup) unit 1 was not located on the same Christa is the following.

In the proposed device is continuous hardware monitoring throughout time and lock the issuance of erroneous information upon detection of the faulty processing unit. The device implements the most complete hardware control, focused on the detection of all types of failures, the time control is comparable with a clock period. Reliability operation processing unit 1 systolic devices will be defined as Df(t) = PCR(t) + Po(t)

where

PCR(t) is the probability of correct operation of the processing unit 1;

Po(t) is the probability of correct operation of the processing unit 1 and issue with unit output 1 signal failure.

For the considered systolic devices

< / BR>
where

Puz(t) - probability computing node 26 (27).

Therefore, the reliability of operation of the device will be Df= (2 Puz(t)) - P2yC(t))n.

Puz= 0.99, and n = 3, Df= 0,996;

Puz= 0.99, and n = 10, Df= 0,9891;

Puz= 0,999 n = 3, Df= 0,999997;

Puz= 0,999, n = 10, Df= 0,999989;

Puz= 0,9999 and above DfPDE device) is proportional to the value of mOTCwhere mOTC- the maximum number of the failed processing unit 1 in the line device.

1. A device for calculating a two-dimensional convolution, containing the I processing units, each of which includes a first computing node, where I is the dimensionality of the problem, and the clock input devices are connected to the clock inputs of the processing units from the first to the I-th information inputs of the first and second groups of devices are connected respectively to the information inputs of the first and second groups of the first processing unit outputs the first and second groups of the i-th processing unit (i = 1, ..., I - 1) are connected respectively to the information inputs of the first and second groups (i + 1)-th processing unit, characterized in that it introduced with the (I + 1)-th to L-th processing units, where L = I + R, R is the number of redundant processing units, L combinational adders, (L - 1) registers, L nodes comparison, (L - 1) group elements, OR L groups of elements And the element OR NOT, and the first, second and third control inputs connected respectively to the first, second and third control inputs of the first processing unit, the first the second and third outputs of the i-th processing unit (where i = 1,..., I - 1) are connected respectively to the first, second and tre processing (I + 1)-th to L-th and the clock inputs of the registers from the first to the (L - 1)-th, the outputs of the first and second groups, the first, second and third outputs of the j-th processing unit (where j = 1, ..., L - 1) are connected respectively to the information inputs of the first and second groups, the first, second and third control inputs (j + 1)-th processing unit, the fourth and fifth control inputs connected respectively to the fourth and fifth inputs of the processing units from the first to the L-th, control inputs of the first group are connected respectively to the control inputs of the first groups of processing units from the first to the L-th and respectively to the inputs of the first group of nodes in comparison with the first through L-th whose outputs are connected respectively to the inputs of the element OR NOT, the output of which is connected to the output indication of failure of the device control inputs of the second group which are connected respectively to the control inputs of the second group of the first processing unit outputs the third group of the K-th processing unit (where K = 1, ..., L) connected respectively to the information inputs of the group of K-combinational adder, the outputs of the n-th combinational adder (where n = 1, . . . L - 1) are connected respectively to the information inputs of the n-th register and respectively to the inputs of the second group of the n-th node of the comparison, outputs the n-th register pocketclock respectively to the first inputs of elements And K-th group, the outputs are connected respectively to the outputs of the K-th group of the device, the outputs of the fifth group of the n-th processing unit connected respectively to the second inputs of elements OR n-th group, the outputs of which are connected respectively to the control inputs of the second group (n + 1)-th processing unit and respectively to the outputs (L + n)-th group of the device, the outputs of the L-th combinational adder connected respectively to the inputs of the second group of L-th node of the comparison and respectively to the outputs of the 2L-th group of devices, the fourth output of the K-th processing unit connected to the information input of the K-th combinational adder, to the second inputs of elements And K-th group and the K-th output indication of failure of the device groups, K-th input set of the first group, the K-th input set of the second group, the K-th input set of the third group and the K-th entry lock devices are connected respectively to the first, second, and third inputs of the installation and the entry lock of the K-th processing unit, each processing unit further comprises a second computing node, node comparison, trigger, from the first to the third element nodes And node elements OR element And, moreover, the control inputs of the first group of the processing unit podkljuchilas and second groups, from the first to the fifth control inputs and the control inputs of the second group of processing unit connected respectively to the inputs of the second group of node elements And the outputs of the first group of the first node elements And connected respectively to the inputs of the first group of node elements OR whose outputs are connected respectively to the outputs of the first, second, and fourth groups, the first, second and third inputs of the processing unit, the outputs of the first group to the second node elements And connected respectively to the information inputs of the first and second groups and the control inputs from the first to the fifth of the first and second computing nodes, the outputs of the first, second and third groups, first, second and third outputs of the first computing node connected respectively to the inputs of the first group of node comparisons and input group of the third node elements And whose outputs are connected respectively to the inputs of the second group of node elements OR, the outputs of the first, second and third groups, the first, second and third outputs of the second computing node connected respectively to the inputs of the second node group comparison, the output of which is connected to the information input trigger input of which is connected to the input of the third node elements And inverse of brogo and second nodes elements And connected respectively to the outputs of the fifth and third groups of the processing unit, the first input set which is connected to the inputs of the installation to its original state of the first and second computing nodes, the second and third inputs of the installation, the clock input and the input block processing unit connected respectively to the inputs installed in the zero trigger, the input set to the trigger unit, the first and second (inverse) input element And the output of which is connected to the clock inputs of the first and second computing nodes and the input of the synchronization trigger.

2. The device according to p. 1, wherein each compute node contains the first through the fourth group of registers, the first and second registers, the multiplier and the adder, trigger group, first to fourth triggers (2M + 2N + 5) groups of elements And (where M = (Q+1)+1, N = Q + 2), eight groups of elements OR the first and second decoders, M items And item OR moreover, the information inputs of the first node group connected to information inputs of the first register of the first group and the first inputs of elements And the first group, the outputs of which are connected respectively to the first inputs of the elements OR of the first group, the outputs of which are connected to information inputs of the first register of the second group, the outputs of the a-th register of the first group (where a = 1, ..., p, the outputs of the M-th register of the first group are connected to first inputs of elements And (M + 1)-th group, the outputs of the elements And groups second (M + 1)-th connected respectively to the inputs of the elements OR the second group, the outputs of which are connected to the outputs of the first group of compute nodes, the outputs of the first register connected to the first inputs of elements And (M + 2)-th group of information inputs of the second register of the second group of information inputs of the first group combined multiplier, the outputs of the second register of the second group (where = 2, ..., N - 1) connected to information inputs ( + 1)-th register of the second group and the first inputs of elements And (M + 1 + )-th group, the outputs of the N-th register of the second group are connected to first inputs of elements And (M + N + 1)-th group, the outputs of the elements And groups with (M + 2) th to (M + N + 1)-th connected respectively to the inputs of the elements OR the third group, the outputs are connected respectively to the first inputs of elements And (M + N + 2)-th group, the outputs of which are connected respectively to the second inputs of the elements OR of the first group, the outputs of multipliers connected respectively to the first inputs of elements And (M + N + 3)-th group, the outputs are connected to first inputs of the elements OR the fourth group, the outputs of which are connected to enthropy and information inputs of the first register, the outputs of which are connected respectively to the information inputs of the second adder, the information inputs of the second group connected to information inputs of the second register and the first input element And (M + N + 5)-th group, the outputs are connected to first inputs of the elements OR the fifth group, the outputs of which are connected to information inputs of the first register of the third group, the outputs of which are connected to information inputs of the second multiplier, the information inputs of the second register of the third group and the first inputs of elements And (M + N + 6)-th group, the outputs of the b-th register group (where b = 2, ..., N - 2) connected to information inputs (b + 1)-th register of the third group and the first inputs of elements And (M + N + 5 + b)-th group, o (N - 1)-th register of the third group are connected to first inputs of elements AND (M + 2N + 4)-th group, the outputs of the elements And groups with (M + N + 6) th to (M + 2N + 4)th is connected to the corresponding inputs of the elements OR the sixth group, the outputs of which are connected respectively to the first inputs of elements AND (M + 2N + 5)-th group, the outputs of which are connected respectively to the second inputs of the elements OR the fifth group, the outputs of the second register connected to the outputs of the second group of compute nodes, the outputs of the first region is uhodi which are connected respectively to the second inputs of the elements OR the fourth group and the first inputs of the elements OR the seventh group, the outputs are connected to information inputs of the second register of the fourth group, the outputs of which are connected to the outputs of the third group computing unit, the information input of the third register of the fourth group and the first inputs of elements AND (M + 2N + 8)-th group, the output of the c-th register of the fourth group (where c = 3, ..., M - 2) are connected respectively to the information inputs (c + 1)-th register of the fourth group and the first inputs of elements AND (2N + M + 6 + c)-th group, the outputs of the (M - 1)-th register of the fourth group are connected respectively to the first inputs of elements AND (2N + 2M + 4)-th group, the outputs of the elements And groups with (2N + M + 8) th to (2N + 2M + 4)-th connected to respective inputs of the elements OR the eighth group, the outputs of which are connected to information inputs of the first register of the fourth group, the first control input connected to the second inputs of elements And the first group, the second (inverted) inputs of elements And (M + N + 2)-th group and the information input of the first trigger group, the output of the d-th flip-flop group (where d = 1, ..., M - 1) connected to the first input of the d-th element And the information log (d + 1)-th flip-flop, the output of the M-th flip-flop group connected to the first input element And the output element And from the first to the M-th connected respectively od which is connected to the second inputs of elements And (M + N + 5)-th group, the second (inverted) inputs of elements AND (M + 2N + 5)-th group and the information input of the first flip-flop, the output of which is connected to the second output of the computing node, the third control input of which is connected to the first input set to zero the first case of the fourth group and the information input of the second trigger, the output of which is connected to the third output of the computing node, the fourth control input of which is connected to the information input of the third flip-flop. the output of which is connected to the first input set to zero the first register, the fifth control input computing node connected to the information input of the fourth flip-flop, the output of which is connected to the second inputs of elements AND (M + 2N + 6)-th group, the elements And the (M + N + 4)-th group, the second (inverted) inputs of elements And (M + N + 3)-th group and elements AND (M + 2N + 7)-th group, the control inputs of the first through r-th and (r + 1)-th and v-th group of the computing node (where r = log2M, v - r = log2N) are connected respectively to the inputs of the first and second decoders, f-th output of the first decoder (where f = 1, ..., M) is connected to the second outputs of the elements And (f + 1)-th group, the elements AND the (2N + M + 5 + h)-th group (where h = 3, ..., M) and f-element And P-th output of the second decoder (g, the Assembly entrance computing node connected to the inputs of a read/write register group from the first to the fourth, first and second registers, inputs synchronization trigger group and triggers from the first to the fourth, the input set to the initial state of the computing node connected to the inputs setup to zero all of the triggers, a second register, registers of groups from the first to the third register from the second to the (M - 1) th fourth group and the second inputs of the installation in the null of the first register and the first register of the fourth group.

 

Same patents:

The invention relates to the field of computer engineering and can be used in specialized computer systems to calculate swerski

Matrix setprocessor // 2079879
The invention relates to computing and is designed to build on the basis of specialized computers

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

The invention relates to computer technology and can be used in specialized computing systems, in particular, in digital signal processing for multiplying two matrices
The invention relates to computer technology and can be used in the automated command and control system for managing the movement of different types of vehicles on the road network with different cross-sections

Vector accelerator // 2042980
The invention relates to computer technology and can be used in the production of vector-based devices, providing high performance vector operations

The invention relates to computer technology and can be used for performance analysis of Queuing systems

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

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 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: 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

FIELD: radio engineering.

SUBSTANCE: invention applies new sequence of interrelated actions, including procedure of vector disturbance in combination of array basis reduction and multi-alternative quantisation. Invention makes it possible to simultaneously service group of several subscriber stations in one and the same physical channel. Invention advantage is possibility of quite simple realisation in transmitter and especially simple realisation in receiver of subscriber station. Invention advantage is possibility of realisation with only one receiving antenna available in each of subscriber stations.

EFFECT: increased throughput capacity of communication channel.

6 cl, 7 dwg

FIELD: information technologies.

SUBSTANCE: system to carry out dot product operation includes the following: the first memory device designed to store instruction of a dot product of "single instruction - multiple data flows" type (SIMD); a processor connected to the first memory device to execute instruction of SIMD dot product, in which instructions of SIMD dot product include an indicator of source operand, an indicator of target operand, at least one indicator of direct value, at the same time the direct value indicator includes multiple control bits.

EFFECT: increased efficiency of processor.

28 cl, 18 dwg

FIELD: information technology.

SUBSTANCE: apparatus has an inverting unit, comprising shift code generating circuits, shift circuits, circuits for generating the code for setting the adder-subtractor operating mode and n normalising units, each having shift circuits and adder-subtractors.

EFFECT: faster operation.

1 dwg

FIELD: information technology.

SUBSTANCE: device has a matrix of homogeneous computing environment cells, having m-1 rows and m-1 columns, where m is the number of bits of the input signal, wherein a cell contains an OR element, an AND element and two flip-flops.

EFFECT: high reliability of a homogeneous computing environment owing to fewer connections between homogeneous computing environment cells and faster operation owing to use of faster homogeneous computing environment cells.

3 dwg, 1 tbl

FIELD: information technology.

SUBSTANCE: device has first registers 1ij (i=1,…,m, j=l,…,n), second multiplier units 2ij (i=1,…,m, j=1,…,n), second registers 3j (j=1,…,n), first adders 4i (i=1,…,m), second adders 5j (i=1,…,m), first multiplier units 6i (i=1,…,m), fourth adders 7i (i=1,…,m), 9j (j=1,…,n), first delay elements 10j (j=1,…,n), AND elements 11j (j=1,…,n), a fifth adder 12, a third multiplier unit 13, a maximum code selection circuit 14, a third register 15, a sixth adder 16, a second delay element 17, an input 18, outputs 19 and 20.

EFFECT: faster operation of the device for simulating the decision making process in conditions of uncertainty.

1 dwg

FIELD: information technology.

SUBSTANCE: invention is meant for use in high-performance computer systems, particularly digital signal processing systems operating in real time, fast process control systems, in personal computers as a means of enhancing performance, realised as a subcircuit in an arithmetic processor or as part of a separate device (special-purpose processor). The apparatus has n normalisation units, each having shift and adder-subtractor circuits and a radical inversion unit having shift circuits, shift code generating circuits, circuits for generating the code for setting the operating mode of adders-subtractors, double adders-subtractors.

EFFECT: high rate of normalising an n-dimensional vector.

1 dwg

Up!