SU1548795A1 - Device for lu-decomposition of matirices - Google Patents

Abstract

A device for LU decomposition of matrices relates to the field of computer technology and can be used in the construction of specialized devices for matrix calculations. The purpose of the invention is to reduce hardware costs. The goal is achieved by the new organization of communications between the elements of the device. A feature of the device is the parallelization of the computation process in combination with a high utilization rate of the device elements. The dimension of decomposable matrices 4 ^. 4. 5 Il.

Description

The invention relates to automation and computing and can be used in the construction of specialized devices designed to solve systems of linear equations.

The aim of the invention is to reduce hardware costs.

Figure 1 shows the structural diagram of the device for W-decomposition of matrices; 0 2 is a block diagram of a multiplying-subtracting block; FIG. 3 is a block diagram of the synchronization block; in fig. 4 is a block diagram of one of the options for building a forming unit; in fig. 5 - timing diagram of the synchronization unit.

A device for LU decomposition of matrices (FIG. 1) contains first 1, second

2nd third 3, fourth 4, fifth 5 and sixth 6 registers, first 7, second 8, third 9, fourth 10, fifth 11 and sixth 12 switches, first 13, second 14, third 15 and fourth 16 multiplying and subtracting units , first 17 and second 18 blocks of division, seventh 19, eighth 20, ninth 21, tenth 22, eleventh 23, twelfth 24, thirteenth 25, fourteenth 26, nth 27, sixteenth 28 and seventeenth 29 registers, seventh 30, eighth 31, ninth 32, tenth 33, eleventh 34, twelfth 35, thirteenth 36 and fourteenth 37 switches, synchronization unit 38,

A multiplying / subtracting unit, for example, contains (FIG. 2) a multiplier 39, whose inputs are the inputs of the first and second factors,

cl

J

from the next

and the subtractor 40, the first input of which is connected to the output of the multiplier 39, the second input is the input of the term, and the output is the output of the entire multiplying-subtracting unit.

The multiplier-subtraction block has a term input, a first factor input and a second factor input, and performs calculations using the formula d a - bc, where a is the number at the input of the term; b and c are the numbers at the inputs of the first and second factors; d is the number at the output of the multiplying subtraction block

The synchronization unit 38, for example, contains (FI) element 41, the output of which is connected to the counting input of a three-bit address counter 42, the outputs of which are connected to the inputs of the address register 43, the information input clock of which is combined with the first input of the element 41 and is input 44.1 of the synchronization block, | The zero-setting input of the counter 42 is combined with the second input of the AND 4 element and is the 44 ' start input of the synchronization block. The outputs of the address register 43 are connected to the inputs of a permanent storage device (ROM) of 45 microcommands. The output of the AND unit 41 is the first output 46 of the synchronization unit 38. The outputs 47-57 of the micro-command storage device 45 are respectively from the second to the twelfth outputs of the synchronization unit.

The divider has a divisible input and a divider input and performs calculations using the formula 1 f / q, where f is the number at the input of the dividend; q is the number at the input of the divisor; 1 - the number at the output of the division unit,

With a single-channel source data stream, you can use a serial data stream to parallel and parallel to serial converter to create the desired source data sequence and record the results in a single-channel memory. You can build such a forming node in many different ways. The forming node shown in FIG. 4 contains six input blocks 58-63 of the registers, the inputs of which are combined and the input of the node, and the outputs are connected to the inputs of the device for W-decomposition of the matrices. Outputs

devices for LU decomposition are connected to the input of six output blocks 64-69 of registers, the outputs of which are combined and are the output of the forming unit.

The device for W-decomposition of matrices performs the calculation by the formula

U

AND

-

 but

fci

with k 4 j,

one;

ik

 a (.w - k |

/ a

fek

Where

1a (fc jafcj

i, j k, k + l,.,., n „

Since the device is intended for W-decompositions of 4x4 matrices, all the processing consists in the following calculations:

B

0

-41

- one

L4i

42 Uij

U "

aa-chz-l 41- U, s „

Let us consider in detail the operation of the device: when performing the W-decomposition of the matrix

and

eleven

1b

h

We assume that the registers are received at the falling edge of the sync pulse, i.e. at the beginning of the cycle, and the initial state of all registers is O.

At time t (the beginning of the first clock) in registers 1-6, the signal from the output 46 of the synchronization unit 38 is received a, acz ai + a21 azch, respectively ;. For the zero signals from the outputs 47, 48, 50, and 51 of the synchronization unit 38, the switches 7-12 are connected to the multiplying and subtracting blocks and the dividing blocks, the outputs of the input registers 1-6, the switch 37 by the signals 10 coming from the outputs 47 and 49 synchronization unit 38 connects to the inputs of the divider 17 and 18 dividing units the output of input register 1, the switches 30-36 can be in an arbitrary state, since zeroes will be supplied as factors in any case. Thus, at the end of the first clock cycle at ta signals coming from the output 54-57 38 block sync registers 19-24 are received in correspondingly U ,,, Un, U

,one

one

31

30 At time t 4 per register

also in register 29 - coefficient 13 ,. may respectively

At time t, the signal from the output 46 of the synchronization unit 38 is also received as

g

on., registers 1 and 6, respectively

which through the switches 7-U are fed to the inputs of the addend blocks 13-16. The output of register 22 (II1CH) through switches 30 and 33 is connected to the inputs of the first factor of blocks 13 and 16, the output of register 21 (U, 5) through switches 31 and 32 is connected to the inputs of the first factor of blono, on zero signals5 coming from outputs 47 and 48 block 38 synchronization, switches 7 and 12 are connected to the inputs of blocks 13 and 18, the outputs of registers 4Q 14 and 15, the output of register 23 (llf) lines 1 and 6, according to signals 01, after a single signal through switching from the outputs 52 and 53 of block 38, the torus 34 is applied to the input of the second somatization, accepted into registers 19 to 24, respectively.

At time t. , at the beginning of the third cycle, in registers 2-4 with

respectively

ten

33 a32

41 and the zero signal switches 8-10 serves them to the inputs of blocks 14-16, respectively. The switch 31 on the zero signal provides the input to the first factor of the block 14 U.3, i.e. the contents of register 21, switches 32 and 33 are fed to the inputs of the first factor of blocks 15 and 16 U, 2,

15 i.e. the contents of register 20, the output of register 23 (lj,) on a zero signal switch 35 connects to the input of the second factor of block 14, the output of register 29 (1E1) on a single signal 20 switch 36 connects to the input of the second factor of block 15, from the output of register 24 141 is fed to the input of the second factor of block 16,

By the end of the third bar on exit

25 of block 14 are obtained; at the output of blocks 15 and 16, the numerators are respectively 1 Ph and 147, which are taken at registers 20, 27 and 28, respectively, at time t +.

30 At time t 4, registers 1-4 are received respectively as

14

133

4h

441

35

which through the switches 7-U are fed to the inputs of the addend blocks 13-16. The output of register 22 (II1CH) through switches 30 and 33 is connected to the inputs of the first factor of blocks 13 and 16, the output of register 21 (U, 5) through switches 31 and 32 is connected to the inputs of the first factor of blocks 4Q cokes 14 and 15, the output of register 23 ( llf) through a single signal through the switch 34 is fed to the input of the second catfish

synchronization, the switch 30 connects to the input of the first factor of the block 13, the output of the register 20, m0. U For a single signal coming from the output 51 of the synchronization unit 38, the switch 34 supplies the input of the second factor of the block 13 1c, that is. register output 23. By signals. 10 coming from the outputs 47 and 49 of the synchronization unit 38, the switch 37 is connected to the input of the divider unit 18, the output register 19, i.e. i. Thus, by the end of the second clock cycle, Uj ,, appears at the output of block 13, and 41 at the output of block 18, which at time t3 is received from the output 55 of the synchronous block 38

knife 13, the output of the register 29 (131) for a single signal through

the switch 35 is connected to the input of the second factor of the block 14, from the output of the register 24 141 is fed to the input of the second factor of the block 15 via the zero signal through the switch 36, to

input block 16 - directly. The output of the register 27 (numerator 1zg) by a single signal through the switch 11 is connected to the input of the divisible block 17, the output of the register 28 (the numerator

1 ...) on signals 10 through the switch

41

12 - to the input of the divisible block 18, the output of the register 19 (U) for zero signals through the switch 37 - to the inputs of the divider blocks 17 and 18.

Thus, by the end of the fourth clock cycle, at the outputs of blocks 13-18, respectively, C are obtained.

24

the first

the difference II, the first difference of the numerator 1, the first difference 144 e 14,. At time t. U24 ,, 14g are accepted into registers 19, 23 and 24 respectively, and the first differences U33 numerator 143 and U 44 into registers 26-28, respectively.

At the beginning of the fifth cycle (tj) in region I is taken ae. and through the commutator 7 it is fed to the input of the addendum of block 130. Switches 8-10 connect the outputs of registers 26-28 to the voltages of the addendum of blocks 14-16, respectively. The output of register 22 (and 14) through switch 30 is connected via signals 10 to the input of the first doubl of block 13, the output of register 20 (Ш) through switches 31 and 32 to the inputs of the first factor of blocks 14 and 15, the output of register 19 (U44) through the switch 33 - to the input of the first factor of block 16, From the output of the register 29 through the switch 34, 131 is fed to the input of the second factor of the block I3s from the output of register 23, the switch 35 IG is fed to the input of the second factor of block 14, from the output of the register 24,142 is fed to the input the second factor of block 15 through switch 36, and at the input of the second th block factor 16 - directly,

By the end of the fifth clock cycle, the first difference UJ4, U33, the numerator 1.3, the second difference U44 are received at the outputs of blocks 13-16. At time 11, the first difference U3l, the numerator 143 and the second difference 11 are entered into registers 25, 27 and 28 , U33 is accepted into register 20.

In the sixth cycle, the switch 7 connects the output of register 25 (the first difference U34) to the input of the addendum of block 13. From the output of register 19 through switch 30, U14 is fed to the input of the first factor of block 13, from the output of register 20 through switch 37 by signals 01 U33 is fed to input the divider unit 18, from the output of the register 23 15g through the switch 34 is fed to the input of the second factor of the block 13, from the output of the register 27 thru switch 12, according to the signals 01, the numerator 143 is fed to the input of the divisible block 18,

By the end of the sixth cycle, the outputs of blocks 13 and 18 receive coefficients

U

four

14J respectively, which

at time t, registers 19 and 24 are respectively taken,

In the seventh cycle, the switch 10 supplies the input of the block 16 with the second difference U44 from the output of the register 28, from the output of the register 19 of the PCs it is fed to the input of the first factor of the block 16 through the switch 33, from the output of the register 24 to the input of the second factor of the block 16 is fed 1

43

By the end

At the seventh clock cycle, at the output of block 16, U44 is obtained, which at time tg is received in register 22,

This is where the decomposition of the original matrix A into coefficients L and TJ ends. At time t, registers 1-6 accept the raw data of the new matrix. Further, the operation of the device is similar to that described.

The synchronization unit 38 operates as follows. Sync pulses from an external device through input 44.1 are fed to the synchronous input of receiving information from address register 43 and to the first input of the element 41, to the second input of which, through input 44.2, a trigger signal is applied. With a single start-up signal, the installation signal at zero of counter 42 is removed and the clock pulses start to arrive at the counting input of address counter 42. The outputs of address counter 42 are fed to the inputs of address register 43, the outputs of which are connected to the address inputs of the ROM of 45 micro-commands, / ROM capacity of 45 micro-commands - eight nine-bit words The number of micro-instructions is equal to the number of operation cycles, the number of bits of micro-instructions is equal to the number of different control signals required for the elements of the device.

The generating node (Fig. 4) works as follows. The elements of the initial matrix are received in the corresponding input register blocks, i.e. the registers 58.1-58.4 take the elements a11s a ha, a14, a31, the registers 59.1-59 „3 - the elements a 11E a2J, aze, the registers 60.1-60.3 - a1 b, aj, a4E, into registers 61, 1-61 .3 - a 14, a42 and a44 in register 62 - ar (, in registers 63о 1-63.2 - a g and a 41. Elements of the transformed matrix W are taken into output blocks of registers as follows: in registers 64.1- 64.4 elements U (f, U22, U14, tJj4, in registers 65о 1-65.3 - elements U1Z, П2Д, Uj3 5 in register 66 - U 13 in registers 67.1 and 67.2 - U n and U44, in registers

68. 69,

1 and 68.2 - 1, 1-69.4 - 1.

.g, and Ij4, in registers

-51 41 42 4e “The elements of the transformed matrix from the device can be organized in any desired sequence. The control unit is controlled by an external control unit, which may be, for example, firmware.

Claims (1)

Formula from about, b and e A device for LU decomposition of mats, containing seventeen registers, fourteen switches, two dividing points, four multiplying-calculating blocks, a synchronization block, with the information inputs from the first to the sixth registers connected to the first, second, third, fourth, right, and The sixth inputs of the device, the first to the sixth outputs of which are connected to the outputs of the seventh, eighth, ninth, tenth, eleventh and twelfth registers, respectively, characterized in that, in order to reduce the hardware costs Yield first through sixth registers connected to the first data inputs with. first through sixth switches, the outputs of the first, second, third and fourth switches are connected to the inputs of the term of the first, second, third and fourth computational computing units, the inputs of the first factors of which are connected to the outputs of the seventh, eighth, ninth and tenth switches, information inputs of the seventh, eighth, ninth and tenth registers are connected respectively to the outputs of the first, second, third and fourth multiplying-computing blocks, the inputs of the second the multipliers of which are connected to the outputs of the eleventh, twelfth, thirteenth switches and the twelfth register, respectively, the outputs of the fifth and sixth switches are connected to the inputs of the first and second division blocks, respectively, divisible, 10 15 20 25 thirty 35 40 45 50 55 divider dyes of which are interconnected and with the output of the fourteenth commutator, the first information input of which is connected to the first information inputs of the seventh and tenth switches and the output of the seventh register, the output of the thirteenth register is connected to the second input of the first switch, the output of the first division block is connected with the information input of the eleventh register, the output of which is connected to the first inputs of the eleventh and twelfth switches, the second inputs of which are connected to each other and to the first input the fifteenth switch, the output of the fourteenth register is connected to the second information input of the second switch, the output of the fifteenth register is connected to the second information inputs of the third, fifth and sixth switches, the output of the sixteenth register is connected to the second information input of the fourth switch and the third information input of the sixth switch, the output of the second the division block is connected to the information inputs of the seventeenth and twelfth registers, the outputs of which are connected respectively to the first and watt The informational inputs of the thirteenth switch, the output of the ninth register is connected to the first information inputs of the eighth and ninth switches, the output of the eighth register is connected to the second information inputs of the seventh, eighth, ninth, tenth and fourteenth switches, the output of the tenth register is connected to the third inputs the seventh and tenth switches, the output of the first register is connected to the third input of the fourteenth switch, the first output of the synchronization unit is connected to the synchronous inputs of the first, second , third, fourth, fifth, sixth, thirteenth, fourteenth, fifteenth and sixteenth registers, the second output of the synchronization unit is connected to the configuration input of the first switch and the first configuration inputs of the sixth, tenth and fourteenth switches, the third output of the synchronization unit is connected to the second the configuration inputs of the sixth and tenth switches, the fourth output of the synchronization unit is connected to the second configuration input of the fourteenth switch; fifth output of the synchronization unit connected to the configuration inputs of the second, third, fourth and eighth switches; sixth output of the synchronization unit connected to the configuration inputs of the fifth, ninth, eleventh and twelfth switches; the seventh output of the synchronization unit is connected to the configuration input thirteenth switch and the first setup input the seventh switch, the second configuration input of which is connected to the eighth output of the synchronization unit, the ninth output of which is connected to the sync rotations of the ninth, tenth and seventeenth registers, the tenth output of the synchronization unit is connected to the sync rotations of the seventh and twelfth registers, eleven and twelfth the outputs of the synchronization unit are connected respectively with the synchronous inputs of the eighth and eleventh registers.  J S6mSI FIG. five