Matrix setprocessor

 

(57) Abstract:

The invention relates to computing and is designed to build on the basis of specialized computers. The aim of the invention is the expansion of the class of tasks. This objective is achieved in that the matrix setprocessor includes m registers, m decoders mark, 2m-1 adders-vychitala, m-1 EXCLUSIVE OR circuits, three shifter, m+3 multiplexer (m - dimensionality of the processed matrix). 4 Il.

The invention relates to computing and is designed to build on the basis of specialized computers.

Known specialized devices that perform triangulation matrix (patent RF N 1800463), solution of systems of linear algebraic equations (RF patent N 1832301), solution of systems of linear algebraic equations with a triangular matrix (patent RF N 1803921), as well as devices for the rotation vector algorithm for Valdera (ed. mon. USSR N 445042).

The main disadvantages of these devices are narrow functional composition of operations performed when significant hardware costs, as well as the need to compute the m-dimensional vector to use consistently is eusto for module definition three-dimensional vector (ed. mon. USSR N 1205139) that implements the iterative algorithm for three-dimensional movement vector using the sequence of n transformations reflection to its coincidence with the x-axis.

One of the major drawbacks of this device is a great time determination module m-dimensional vector, which is of order m/2 cycles for n iterations. In addition, with this device it is impossible for the solution of systems of linear algebraic equations with a triangular matrix (perform a "reverse" for solving systems of linear algebraic equations) and to carry out the conversion matrix according to the method of Gauss or Gauss-Jordan. Meanwhile, the above operations are the mathematical content of a significant part of practical problems.

The aim of the invention is a class extension is solved by the device of tasks by introducing the functional structure of the device of operations for solving systems of linear algebraic equations with a triangular matrix and transformation matrix according to the method of Gauss and Gauss-Jordan, and a calculation module m-dimensional vector for one cycle of operation of the device.

This goal is achieved by the fact that the device contains three register is connected to the reference input of the binary code the number of iteration the output of the first register is connected to the information input of the first shifter, added m-3 registers, m-3 decoders mark, 2m-7 adders-vychitala, m-1 XOR circuit, m+3 multiplexer, where m is the dimensionality of the processed matrix block multiplication unit changes the sign of the number, and information inputs of all the registers are the input operands setprocessor, the synchronization inputs of all the registers is connected to the synchronization input of setprocessor, the control input of block multiplication is connected to the reference input of the binary code the number of iteration of setprocessor, the output of the first shifter through the block to change the sign, a control input connected to the output of the first decoder badge, connected to the first input of the chain of adders-vychitala, in which the sign of the first term (reducing) the j-th element (j 1,2,m-1) is connected to the output of the (j-1)-th element, and the input of the second summand (wichitaeagle) output (j+1)-th register, the output of the last element of the chain is connected to the information input unit of multiplication, the output of which is connected to the information input of the second shifter, the input of the second summand (wichitaeagle) the first output of the adder-vicites connected to the output of the second DM is the l-th register, the output of the l-th output of the adder-myCitadel, except the first, is connected to the l-th output setprocessor, the input l-th decoder of the mark is the l-th input of the analysis of the sign of the operand setprocessor, the output of the first decoder of the sign is connected to the control input of the first output adder-myCitadel, the output of the first register through the third shifter connected to the first information input of the m-th multiplexer, the second information input connected to the output of block multiplication, and output with inputs of the second term (wichitaeagle) each output of the adder-myCitadel, except for the first and second, the output of the first output adder-vicites connected with the second information input of the (m+3)-th multiplexer, the first information input connected to the output of the first register, and the output from the first output setprocessor, the output of the j-th decoder sign (j 2,3,m) is connected to the second input of the (j-1) th XOR circuit, a second input connected to the output of the first decoder badge, output (j-1) th XOR circuit connected to the first information input of the (j-1)-th multiplexer, the second information input connected to the output of the j-th decoder token, the output of the j-th multiplexer (j=1,2,m-1) connected to upravlajushemu first and second, the output of the second multiplexer is connected to the second information input of (m+2)-th multiplexer, the first information input connected to the output of the first multiplexer, and the output with the control input of the second output adder-myCitadel, the first information input of the (m+1)-th multiplexer connected to the output of the m-th multiplexer, the second information input with the input binary weight of the treated discharge setprocessor, and the output to the input of the second term (wichitaeagle) of the second output adder-vicites control inputs of all of the multiplexers connected to the reference input in binary mode setprocessor.

The unit changes the sign of the number is known technical solution and, in particular, may be made in the form of adder-myCitadel, to the input of the first term (reducing) which is constantly supplied value of zero, the sign of the second term (wichitaeagle) is an information input unit changes the sign of the number, the control input of the adder-vicites managing unit changes the sign of the number, and the output of the adder-vicites output block.

Block multiplication is known technical solution and is designed on the can, in particular, be in the form of a device consisting of a permanent storage device for storing constants and multipliers, and the address input of the storage device is a control input of the multiplication, the output of the storage device is connected to the input of the first factor, the input of the second factor of which is an information input unit of multiplication, and the output of the output unit of the multiplication.

In Fig. 1 presents a diagram of the matrix setprocessor, where 11.1mregisters operands, 21.2m- decoders mark 31.32m-1adders-myCitadel, 41, 42, 43shifters, 5-input binary code the number of iteration 61. 6m-1XOR circuit, 71.7m+3multiplexers, 8 block multiplication, 9 unit changes the sign of the number, 101.10mthe input operands, 11 synchronization input, 121. 12mthe outputs of setprocessor, 131.13mthe inputs of the analysis of the sign of the operand, 14 the reference input binary weight of the treated discharge, 15 the reference input in binary mode setprocessor.

In Fig. 2 shows the scheme for conversion of vector pipelining, where U1. UnX(j)vector processed by the device UjZ - bus the signs of the operands for n iterations, Z(j)bus signs of the operands to the j-th iteration.

In Fig. 3 presents a framework for triangulation of the matrix A(mxm), the columns of which are filed on the device U1.Um, each of which is the device shown in Fig. 2.

In Fig. 4 shows a scheme for solving systems of linear algebraic equations with a triangular matrix, where U1.U3devices, each of which is the device shown in Fig. 2, aij- the elements of the matrix system to the processing elements of the system matrix after processing, bithe elements of column free members before and after processing, respectively.

Setprocessor includes m registers 11.1m, 2m-1 adders-vychitala 31.32m-1, m decoders mark 21.2m, m-1 XOR circuit 61.6m-1m+3 multiplexer 71.7m+3three shifter 41, 42, 43unit changes the sign of the number 9, block multiplication 8 on one of the n constants, m inputs operands 101.10mm inputs of the analysis of the sign of the operand 131.13mthat outputs 121.12mthe reference input binary NGOs discharge 14, moreover, the inputs of registers 11.1minput operands 101.10mand outputs connected to the inputs of the first term (reducing) the output of adders-vychitala 3m. 32m-1accordingly, the inputs of the decoders mark 21.2mare respectively the inputs of the analysis of the sign of the operand 131.13mthe outputs of decoders mark 22.2mconnected to the second inputs of EXCLUSIVE OR circuits 61.6m-1accordingly, the first inputs of these circuits are connected to the output of the decoder, mark 21and outputs are connected with the first information inputs of the multiplexers 71.7m-1accordingly, the second information inputs of these multiplexers are connected to the outputs of decoders mark 22.2maccordingly, the reference input binary code the number of iteration 5 is connected to the control inputs of shifters 41, 42, 43and block multiplication 8, the output of register 11connected through the shifter 41and unit changes the sign of the number 9 to the input of the first term (reducing) of the adder-vicites 31the sign of the second term (wichitaeagle) which is connected to the output of the register 22the control input with the output of the multiplexer 7<31.3m-1chained together, the j-th element of which the sign of the first term (reducing) connected to the output of the (j-1)-th element, the input of the second summand (wichitaeagle) to the output (j+1)-th register, managing input to output multiplexer 7jand the entrance to the entrance of the first term (reducing) (j+1)-th element, the output of the adder-wichitas 3m-1connected with the information input unit 8 multiplication, the output of which through the shifter 42connected to the input of the second summand (wichitaeagle) adder-vicites 3mand directly to the first information input of the multiplexer 7mthe output of the adder-calculator 7mconnected to the second information input of the multiplexer 7m+3the first information input connected to the output of the first register, and the output from the first output setprocessor 121the second information input of the multiplexer 7mconnected through the shifter 43with output register 11and the output is connected to the first information input of the multiplexer 7m+1and to the inputs of the second term (wichitaeagle) adders-vychitala 3m+2.32m-1the second information input of the multiplexer 7m+1connected to the reference input of the active ingredient is of the motor 3m+1control inputs of the adders-vychitala 3m+2.32m-1connected to the outputs of the multiplexers 72.7m-1respectively, and the control input of the adder-vicites 3m+1connected to the output of the multiplexer 7m+2the first information input connected to the output of the multiplexer 71and the second with the output of the multiplexer 72control inputs of all of the multiplexers connected to the reference input in binary mode setprocessor 15, the outputs of adders-vychitala 3m+1.32m-1are the outputs of setprocessor 102.10maccordingly, the output of the decoder, mark 21connected with the control unit changes the sign of the number 9 and the controlling input of the adder-vicites 3mthe input synchronization registers 11.1mconnected to the synchronization input of setprocessor 11.

Setprocessor can operate in one of three modes.

The work of setprocessor in modes 1 and 2 can be described by the following expression:

< / BR>
where i is the iteration number.

The values of a and Cjdefines the operating mode of setprocessor.

In mode 1

< / BR>
In this mode, the algorithm (1) describes one of the n PR who is with the first of the m coordinate axes, the first element of the vector is equal to the module of the vector, and the remaining coordinates of the vector will be zero.

In mode 2

< / BR>
In this mode, the algorithm (1) describes one of the n transformation vector according to the method of Gaussian or Gauss-Jordan), in which the original source vector X0(x(10)x(20), ..., x(m0)converted to a vector Y(x(10), 0, ..., 0).

Mode 3 is auxiliary and is designed to perform a division operation on the same device, which is necessary for solving systems of linear algebraic equations with a triangular matrix.

The work of setprocessor in mode 3 can be described by the following expression:

< / BR>
where

< / BR>
In this mode, the source vector X0(x(10), 0, x(30)) is converted to a vector Y(x(10)x(30)/x(10), 0). The remaining coordinates of the input and output vector in this mode are not used and can be arbitrary.

Consider the work of setprocessor on the i-th iteration. The operands of the components of the vector Xirecorded in the registers 11.1mat the entrance the entrance 11 setprocessor. The inputs 131.13mserved operands, the signs of which decoders mark 21.2mand the XOR circuit 61.6m-1produce control signals adders-vycitalem according to the ratios(2), (3), (5).

The multiplexers 71.7m-1and 7m+2serve for switching the generated control signals by the adders-vycitalem in accordance with the mode, binary code which is specified at the input 15. Shifters 41and 42serve to shift the number by i bits, the output unit changes the sign of the number 9 will be the value of -2-ix1C1to which the adder-myCitadel 31added (deducted) the value of x2c2. Thus, at the output of the adder-vicites 3m-1it will mean -2-ix1c1+x2c2+ + xmcmthat is fed to the input of block multiplication 8. Block multiplication is to multiply the input number depending on the number of inertia to one of the n constants -2(m-1+2-i)-1. The output of block multiplication to obtain the value a, through which the shifter 42forming the value a2-i, is supplied to the adder-myCitadel 3m. Thus obtained of the engine 43. The multiplexer 7mselects one of these values depending on the mode. From the output of the multiplexer 7mthe value a is supplied to the inputs of the second term (wichitaeagle) adders-vychitala 7m+2.72m-1directly on a corresponding input of the adder-vicites 3m+1through the multiplexer 7m+1on the second information input of which is fed the value of d from the reference input binary weight of the treated discharge 14. The multiplexer 7m+1in modes 1 and 2 connects to the input of the second term (wichitaeagle) adder-vicites 3m+1the value of a, and in mode 3 value d according to (4). In modes 1 and 2 adders-vicites 3m.32m-1line-by-line implement equation (1), and in mode 3 adders-myCitadel 3m.3m+2line-by-line implement equation (4). The values of Y2. Ymobtained at the outputs of adders-solvers 3m+1.32m-1respectively, are fed directly to the outputs of setprocessor, and a value of Y1output of setprocessor through the multiplexer 7m+3that connects the corresponding output with the output of the adder-vicites 3min mode 1 and output register 11in modes 2 and 3. All multiplex the-th iteration ends. The next iteration can be performed sequentially in the same device, if you connect the outputs 12jwith inputs 10j(j=1,2,m), or in pipelined mode with n devices, as shown in Fig.2. The values applied to the inputs 131.13mthe j-th device (j=1,2,n) depend on the mode of the device, but also on whether the device column of the matrix, which is zero off-diagonal elements in the current step (main column), or the device is processed by one of the other columns of the matrix (the dependent column) to preserve the linearity of the conversion.

In modes 1 and 2 during the processing of the main column inputs 131.13mthe j-th devices are connected to the inputs 10110mthis device respectively, while processing a dependent column with inputs 101.10mdevice for machining the main column. In mode 3 inputs 131and 133the j-th devices are connected respectively to the inputs 101and 103that device. The signal applied to the inputs 131.13mthe j-th device form a bus Z(j)and a common bus Z, shown in Fig.2.

In Fig. 3 shows the circuit connection for the cast of the matrix A ({aij}) dimensions (mxm) to the upper triangular form by means of orthogonal transformations reflections (mode 1) or by decomposition of a matrix into triangular multipliers according to the method of Gauss (mode 2). The device U1handles the main column, and the device U2.Umdependent columns of the matrix. Inputs Z each device is connected as described above to form the tire Z in Fig.3. In the transformation of all the elements of the first column of the matrix, in addition , will be zero, and the element will be equal to the module of the vector (mode 1) or (a11(in mode 2). After exclusions (zero) podiagonalnee elements of the first column, the same procedure is carried out with a matrix of order (m-1) to exclude podiagonalnee elements of the second column.

After (m-1)-th similar step, the resulting matrix is an upper triangular matrix after these manipulations in mode 1 with rows of matrix - dwuhvalentnoe.

If in mode 2 at each step does not reduce the dimensionality of the space, and to use the released modules for exceptions and addiionally elements, the resulting matrix will be a diagonal initial method (Gauss-Jordan).

For triangulation matrix in raisiny column in the selected mode, for processing of column free members similar to the columns of the matrix.

In Fig. 4 presents a scheme to perform "reverse" (the solution of a triangular or diagonal matrix when solving systems of linear algebraic equations. Device U1U2U3represent the device shown in Fig.2. Device U1works in mode 3, when the input X is a vector (amm, O, bm), where ammelement of the system matrix, bmelement column free members, the output Y of the device is obtained vector, the first element of which is the value of the element of the vector solution xm=bm/amm. In the case of a diagonal matrix to obtain a vector solution it is enough to make m such operations. In the case of a triangular matrix after receiving xmyou need to go to the matrix of dimension (m-1), transforming the vector of free members. To do this, use the device U2processing the dependent column-vector (xmb1bm-1), and the device U3processing the main column vector (1, a1m, am-1m). As a result, the conclusions of the device U2the result is a vector Y (xmb1-a1mxm< is by solving m linear systems of algebraic equations with the same matrix and m different columns free members, and for finding the determinant of a matrix and solving some other problems of linear algebra.

The effectiveness of the invention consists in the extension class solved by the device of tasks, and it does so at the expense of a small increase in the cost of equipment.

Matrix setprocessor containing three cases, three decoder badge, six adders-vychitala, three shifter, and the control inputs of shifters connected to the reference input of the binary code the number of iteration of setprocessor, the output of the first register is connected to the information input of the first shifter, characterized in that it introduced m-3 registers, m-3 decoders mark, 2m-7 adders-vychitala, m-1 exclusive or circuits, m+3 multiplexers, where m is the dimensionality of the processed matrix block multiplication unit changes the sign of the number, moreover, the information inputs of all the registers are the input operands setprocessor, the synchronization inputs of all the registers is connected to the synchronization input of setprocessor, the control input of block multiplication is connected to the reference input of the binary code the number of iteration of setprocessor, the output of the first shifter through the block changes the sign of the number, the control input of which is connected to virsago term (reducing) the j-th element (j=1,2,m-1) is connected to the output of the (j-1)-th element, and the sign of the second term (wichitaeagle) output (j+1)-th register, the output of the last element of the chain is connected to the information input unit of multiplication, the output of which is connected to the information input of the second shifter, the input of the second summand (wichitaeagle) of the first output adder-vicites connected to the output of the second shifter, the input of the first term (reducing) the i-th output of the adder-vicites (j 1, 2, m) is connected to the output of the first register, the output of the i-th output of adder myCitadel, except the first, connected to the i-th output setprocessor, the input of the i-th decoder of the mark is the i-th input of the analysis of the sign of the operand setprocessor, the output of the first decoder of the sign is connected to the control input of the first output adder-myCitadel, the output of the first register through the third shifter connected to the first information input of the m-th multiplexer, the second information input connected to the output of block multiplication, and output with inputs of the second term (wichitaeagle) each output of the adder-myCitadel, except the first and the second output of the first output adder-vicites connected with the second information input of the (m + 3)th multiplexer, the first information input of which is connected to the aircraft by the second input (j 1) th XOR circuit, the second input of which is connected to the output of the first decoder badge, output (j 1) th XOR circuit connected to the first information input of the (j 1)-th multiplexer, the second information input connected to the output of the j-th decoder token, the output of the j-th multiplexer (j 1,2,m 1) is connected to the control input of the j-th adder-vicites in the chain and to the control input of the (j + 1)-th output of the adder-myCitadel, except for the first and second, the output of the second multiplexer is connected to the second information input of (m + 2)-th multiplexer, the first information input connected to the output of the first multiplexer, and the output with the control input of the second output adder-myCitadel, the first information input of the (m + 1)-th multiplexer connected to the output of the m-th multiplexer, the second information input with the input binary weight of the treated discharge setprocessor, and the output to the input of the second term (wichitaeagle) of the second output adder-vicites control inputs of all of the multiplexers connected to the reference input binary mode setprocessor.

 

Same patents:

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

The invention relates to computing and microelectronics, and can be used in specialized pre-processing of multidimensional signals

The invention relates to computer technology and can be used in specialized high-performance computing machines and devices, signal processing for handling n n-matrices

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!