Device for computing sums of productions

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

 

The invention relates to the field of computer technology, is designed for parallel computing bit slices amounts of paired pieces of complex numbers and can be used for solving problems of digital signal processing, solving problems of spectral analysis and sonar, automatic control systems and other

Known arithmetic unit calculating the sum of the works of A.S. 553613 (USSR), BI No. 13, 1977, contains two register mnimyh, two registers of multipliers, register the amount mnimyh, accumulating adder, decoder, logic gates AND, OR.

Signs of similar, coinciding with the essential features of the claimed invention are registers, adder.

The disadvantage is that the device cannot simultaneously to calculate the amount of paired pieces of complex numbers.

The reason for that is earlier than the technical result is the low degree of parallelization of the computational process.

It is also known multiplier unit complex numbers (Introduction to cybernetic technology. Edited Binalewala. - Kiev.: Naukova Dumka. 1979, p.143, RIS)containing registers, the code Converter, the switches, the decoder, the adders.

Signs of similar, coinciding with the essential features of the claimed invention, t is Auda registers, adders.

The disadvantage is that the device cannot simultaneously to calculate the amount of paired pieces of complex numbers.

The reason the technical result is the low degree of parallelization of the computational process.

The closest is the device for digital signal processing bit slices PIPE (Ethocyn. Computational imaging - HP: Energoatomizdat. 1988, p.74, RIS)containing registers, registers of conversion codes, shifter-accumulator, the multiplexer address, programmable ROM.

The characteristics of the prototype, coinciding with the essential features of the claimed invention are registers.

The disadvantage is the limitations in functionality, as in the known device signal processing parallel impossible to calculate the bit cuts the amount of paired pieces of complex numbers.

The reason that prevent obtaining the required technical result is the low degree of parallelization of the computational process.

The problem to which the present invention is directed, is to create a device parallel computing bit-slice sum M paired pieces of complex numbers.

Technical result achieved when assests the research Institute of the invention, is to increase functionality, improve performance computing the sum of M paired pieces of complex numbers.

To achieve the technical result in the computing device containing the registers, entered the adder-transmitter, two block matrix solvers amounts of works, each of which contains a matrix adder, parallel converters equilibrium codes position codes, M-matrix multipliers, each of which contains a register mnimogo and register multiplier whose inputs are connected to the inputs of the device (n+1) groups (n+1) elements And allocate the weight bit works, (n+1) elements, And selection of corrective bit works on the sign of the multiplier group of items And selection of corrective bit works in sign mnimogo. While some inputs (n+1) elements And allocate the weight bit works are connected with the outputs of the issuance of significant digits of the register of the multiplier, the second inputs of these elements And are connected to the outputs of the issuance of significant digits of the register mnimogo. Some inputs (n+1) elements, And selection of corrective bit works on the sign of the multiplier is connected through inverters with outputs of the issuance of significant digits of the register mnimogo, the second inputs of the (n+1) elements And is connected to the output of the register of issued and significant digit of the multiplier. While some inputs of the group of items And selection of corrective bit works in sign mnimogo connected to the outputs of the significant digits of the register of the multiplier, the second inputs of the group of elements And is connected to the output of issuing significant digit of the register mnimogo. Thus the outputs of the elements And allocate the weight bit works with equal weights and the outputs of the elements And highlight corrective bit works properly connected to the inputs of inverters codes. Converter output codes connected with the inputs of the matrix adder accordingly.

The matrix outputs of the adders are connected respectively to the inputs of adder-myCitadel, the outputs of which are connected with the output device.

A causal relationship between the set of features of the claimed invention and achievable technical result is the following: the introduction of M-matrix multipliers, parallel converters ravnovesnykh codes position codes connected properly, allows you to extend the functionality, improve performance, calculate the sum M of paired pieces of complex numbers.

The basis of operation of the device based on the algorithm parallel computing bit-slice sum works for complex numbers:

where C1=A1+iB1C2=A2+iB2a complex number;

Algorithm parallel computing bit slices of the real part of the sum M-paired pieces of complex numbers on the basis of parallel vertical arithmetic we write in the form:

Here a01jan2j, ..., an1ja02j; b01jbn2j, ..., bn1jb02j- weight bit of the work; a01ja3H2j; an1ja3H2j, ..., b01jb3H2j; bn1jb3H2j- correction bit works signs mnimyh a3H2jb3H2j.

- correction bit works on the signs of the multipliers a3H1jb3H1j.

Algorithm parallel computing bit slices of the imaginary part of the sum M-paired pieces of complex numbers can be written in the form:

Here a01jbn2j, ..., an1jb02j- weight bit dispensations;

a01jb3H2j, ..., an1jb3H2j; a02jb3H1j, ..., an2jb3H1j- correction bit works signs mnimyh b3H1jb3H2j

- correction bit works on the signs of the multipliers a3H1j, a3H2j.

The essence of the invention is illustrated by the device of the calculation of amounts of works is shown in figure 1.

The computing device (1) contains:

11- the first block of the calculation of amounts of works;

12the second computing unit amounts works;

21, ..., 2m - informational inputs receiving the parallel code multiplier a01, a11, ..., a3H1j; a02j, a12j, ..., a3H2j; b01jb11j, ..., b3H1j,;

31, ..., 3M - information input reception parallel codes mnimyh b01jb11i, ..., b3Hj; b02jb12j, ..., b3H2j; aj, a12j, ..., a3H2j,;

4, a control input receiving the pulse account;

51-5m - registers of the multiplier with the information outputs of the issuance of parallel codes meaningful and significant bits of the multiplier (figure 1 designated as 20, 21, ..., 3n);

61-6m - registers mnimyh information outputs issuing parallel codes meaningful and significant digits mnimyh (indicated in figure 1, as 20, 21, ..., 3n);

71-7m - matrix multiply and;

8 - converters equilibrium codes position codes;

9 - matrix (parallel - parallel) adders;

10 is the control input, receipts operating characteristic Victoria PRF=1; summation PRF=0;

11 - multi-digit adder-myCitadel;

12 - information outputs, issue the parallel code is the result of a calculation.

Matrix multiplier (Figure 2) consists of: register of the multiplier (51, ..., 5m); information input reception multipliers (21); register mnimogo (61, ..., 6m); information input reception mnimyh (31); the control input, receipt of impulse records (4);

(n+1) groups (n+1) elements And items (marked by dots) of the weight allocation bit works, (n+1) elements, And the selection bit correction bit works on the sign of the multiplier; group of items And selection of corrective bit works in sign mnimogo; (n+1) elements (elements NOT marked with circles).

Matrix (parallel-parallel) adder (Figure 3) described (Introduction to cybernetic technology. Edited Binalewala. Kyiv.: Naukova Dumka. 1979, pp.118, RIS), consists of an L-series Raman parallel adders (13), L=]log2K[, ]log2K[ - rounding to the nearest larger integer values log2K, has inputs and11... , and1n..., andk1... , andknreceiving positional codes, outputs0, ..., cnresult.

The adder-myCitadel (Figure 4) is described (Heapwalker, Cianobacteria. Digital devices. St. Petersburg: University of technology, 1996, C, risb) consists of adders modulo two 14, multibit adder 15, has inputs a0...anreceiving the first summand (umenshenya), inputs b0, ... bnreceiving the second summand (deductible), the outputs from0...cnresult, the control input (10), the receipt of the indication modes subtraction (PRF=1) or summation (PRF=0).

Parallel Converter equilibrium codes position codes (node one-bit sum) (Figure 5) described (Ed. Mon. 1557684 No. 14, 1994, or the patent SU 1679483 A1, CL G06F, 1995) consists of four vchodove element of the summation 16, the half-adder 17, the elements OR 18 has inputs 2lreceiving equilibrium discharges, the outputs of the 2l(C0), 2l+1(C1), ..., 2l+4(C4) issuance of result.

Explain the operation principle of the calculation of the amounts of compositions (Figure 1). For parallel computations bit slices of the real part of the sum M-paired pieces of complex numbers previously recorded in the registers of the multiplier 51, ..., 5Mthe first block 11 on impulse records received at the input is 4, valid a01j, a11j... , and3H1jpart j-complex numbers,and in the registers mnimyh 61, ...,6Mwritten valid a02jand12j... , and32jpart j-complex numbers.

In the registers of the multipliers 51, ..., 5Mthe second unit (12written imaginary b01jb11j, ..., b3H1jpart j-complex numbers and registers mnimyh 61, ..., 6Mwritten imaginary b02jb12j, ..., b32jpart j-complex numbers.

For parallel computations bit slices of the imaginary part of the sum M-paired pieces of complex numbers previously recorded in the registers of the multiplier 51, ..., 5Mthe first block 11on impulse records received at the input 4, valid and01jand11j... , and3H1jpart j-complex numbers and registers mnimyh 61, ..., 6Mwritten imaginary b02jb12j, ..., b3H2jpart j-complex numbers.

In the registers of the multipliers 51, ..., 5Mthe second unit 12written valid a02ja12j, ..., a3H2jpart j-complex numbers and registers mnimyh 61, ..., 6Mwritten imaginary b02jb12j, ..., b32jpart j-complex numbers.

In multiplying matrices 71, ..., 7Mfirst is the first and the second blocks are computed in parallel elements And a bit of work (figure 1).

The principle of forming elements And a multiplier matrix equilibrium bit works illustrated by example

Here b0a020b1a021b1a122, ..., b3a326- weight bit of work;

b3Hand0b3Hand1, ..., b3Hand3- corrective bit of work signs mnimogo (b3H);

- corrective bit of work on the signs of the multiplier (a3H).

Weight and correcting bit of a work formed by the elements And (tentatively identified elements in the multiplier matrix points) and issued (on the diagonal tyres) of the matrix multipliers 71...7Mthe inputs of the respective inverters codes (8) in equilibrium codes (equilibrium level) with weights 20, ..., 22n+2(figure 1).

In converters codes 8 are generated bit amount. The results of the converters codes 8 are served in parallel to the inputs of the matrix adders 9, in which the calculated amount of works.

In the multibit myCitadel 11 on the basis of HPV=1 at the input 10, parallel to the calculated real part of the sum M-paired pieces of complex numbers in the formand Popasnaya HPV=0 parallel to the calculated imaginary part of the sum M-paired pieces of complex numbers in the form:

Introduction to device new elements parallel converters codes, M-matrix multipliers connected properly, allows you to extend the functionality, improve performance by an order in comparison with the known computing devices due to the high degree of parallelization of the computational process to the level of the bit amounts.

The unit of calculation of the amounts of compositions containing the adder-myCitadel, two block matrix solvers amounts of works, each of which contains a matrix adder, parallel converters equilibrium codes position codes, M-matrix multipliers, each of which contains a register mnimogo and register multiplier whose inputs are connected to the inputs of the device (n+1) groups (n+1) elements And allocate the weight bit works, (n+1) elements, And selection of corrective bit works on the sign of the multiplier group of items And selection of corrective bit works in sign mnimogo, when this one inputs of the (n+1) elements And allocate the weight bit works are connected with the outputs of the issuance of significant digits of the register of the multiplier, the second input of these elements And are connected to the outputs of the issuance of significant digits of the register mnimogo, some inputs (n+1) elements And the allocation of ADJ is the dominant bit works on the sign of the multiplier is connected through inverters with outputs of the issuance of significant digits of the register mnimogo, the second inputs of the (n+1) elements And is connected to the output of the register issuing significant digit of the multiplier, while some inputs of the group of items And selection of corrective bit works in sign mnimogo connected to the outputs of the issuance of significant digits of the register of the multiplier, the second inputs of the group of elements And is connected to the output of issuing significant digit of the register mnimogo, while the outputs of the elements And allocate the weight bit works with equal weights and the outputs of the elements And highlight corrective bit works properly connected to the inputs of inverters codes, Converter output codes connected with the inputs of the matrix adder accordingly, the outputs of the matrix adders are connected respectively with the inputs of the adder-myCitadel, the outputs of which are connected with the output device.



 

Same patents:

FIELD: computer engineering, possible use in devices for rounding numbers in remainder class system.

SUBSTANCE: device contains input register, two groups of encryption devices, first group of n-1 adders, second group of n adders, a group of modulus adders.

EFFECT: increased speed of device operation.

1 dwg

FIELD: computer engineering, possible use during creation of active devices for local area networks.

SUBSTANCE: in accordance to invention, device includes address table, block for realization of hash function of first and second type, block for realization of orderly filling and binary search operations and control block. Address table is divided on two independent physical memory pages. Task queue is connected to block for realization of orderly filling and binary searching operations. Address table, blocks for realization of hash function of first and second types, task queue and block for realization of orderly filling and binary search operations are connected to control block.

EFFECT: possible usage of hash functions in conjunction with orderly filling and binary searching algorithms, increased speed of operation and increased reliability of commutator address processing.

1 dwg

Logical module // 2303283

FIELD: computer engineering, possible use for designing automatic devices, functional units of control systems, etc.

SUBSTANCE: in accordance to invention, logical module, containing an output, features additionally introduced first, third, fifth keys, made closing, and second, fourth, sixth keys, made opening, while input of fifth, input and output of sixth keys are connected respectively to combined outputs of first, second, combined outputs of third, fourth keys and combined outputs of firth key, to output of logical module, connected by first, second informational and first, third, second adjusting inputs respectively to control input of first-fourth, control input of fifth, sixth keys and input of first, input of fourth keys, combined inputs of second, third keys.

EFFECT: expanded functional capabilities due to realization of any one of three simple symmetric Boolean functions τ11∨х2∨х3, τ2=x1x2∨x1x3∨x2x3, τ3=x1x2x3 or of three fundamental symmetric Boolean functions

1 dwg

Logical module // 2303282

FIELD: engineering of automatic devices, functional units of control systems, etc.

SUBSTANCE: in accordance to invention, logical module contains three 2AND elements, and additionally introduced nine 2AND elements, six 2OR elements and six NOT elements, all elements being grouped in three groups in such a way that group j () contains 8-2j 2AND elements, 4-j 2OR elements and 4-j NOT elements, in group j output of i ( r=0,5(8-2j)) 2AND element and output of (r+i) 2AND element, connected by first input to output of i not element, are connected respectively to first and second inputs of i 2OR element, second input of i element 2AND of group j and input of i NOT element of group j are connected to j information input of logical module, output of which is connected to output of first 2OR element of third group, outputs of first, third and second 2OR elements of first group are connected respectively to first input of first, second input of fourth and combined first input of second, second input of third 2AND elements of second group, outputs of first and second 2OR elements of second group are connected respectively to first input of first and second input of second 2AND elements of third group, while second input of sixth, first input of first, combined first input of third, second input of fifth and combined first input of second, second input of fourth 2AND elements of first group are connected respectively to first, fourth, second and third adjustment inputs of logical module.

EFFECT: expanded functional capabilities.

1 dwg

FIELD: computer engineering, possible use for building homogeneous computer structures, executing parallel logical and arithmetical processing of data.

SUBSTANCE: device contains six FORBIDDEN elements, six AND elements, three OR elements, three triggers, adder-subtracter, controlling and informational inputs and outputs.

EFFECT: expanded functional capabilities due to realization of information storage and processing operation in non-positional numerical notation.

7 dwg, 2 tbl, 3 ex

Logical calculator // 2300138

FIELD: computer engineering, possible use for building automatic devices, functional units of control systems.

SUBSTANCE: device contains n AND elements, n OR elements, n D-triggers.

EFFECT: decreased hardware resource costs.

2 dwg, 1 tbl

Modulus multiplexer // 2299461

FIELD: computer engineering, possible use in digital computing devices, and also in devices for forming finite field elements.

SUBSTANCE: device contains multiplier, adders, inverters, constant multipliers, multiplexer.

EFFECT: expanded functional capabilities.

1 dwg

FIELD: computer engineering, possible use in digital computing devices, and also in devices for forming elements of finite fields.

SUBSTANCE: device contains adders, inverters, multipliers, multiplexer.

EFFECT: expanded functional capabilities due to expanded range of input number values.

1 dwg

FIELD: digital computer engineering, in particular, modeling of combinatorial problems during engineering of computer systems.

SUBSTANCE: device contains matrix of m rows and n columns of elements of homogeneous environment, n unit counting block, maximum finding block, first adder, memory block. Introduced into device is computing block, containing impulse generator, element selection multiplexer, row selection decoder, first and second distance counters, multiplexers, second adder, intensiveness value register, group of m OR elements, group of m triggers, row number counter, column number counter, group of m forbidding element block, mono-stable circuit, delay element.

EFFECT: expanded area of possible use of device due to introduction of means for counting minimal value of positioning intensiveness.

2 dwg

FIELD: computer engineering, in particular, modeling of tasks during engineering of computing systems.

SUBSTANCE: device contains matrix of m rows and n columns of elements of homogeneous environment, n blocks for counting units, block for finding maximum, adder, memory block, introduced is positioning block, containing impulse generator, row selection decoder, element selection decoder, element selection multiplexer, row number counter, column number counter, fixed arcs counter, value counter, distance counter, last module counter, vertex number register, mode trigger, group of m triggers, group of m counters of assigned arcs, first and second comparison elements, group of forbidding element blocks from 1-numbered to m-numbered, group of m OR elements, delay element, first and second AND elements, OR element.

EFFECT: expanded area of possible usage of device due to introduction of means for positioning tasks in circular systems on basis of criterion of minimization of interaction intensiveness of processes and data.

2 dwg

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

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

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

7 cl, 10 dwg, 1 tbl

FIELD: computer science.

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

EFFECT: higher efficiency.

4 cl, 9 dwg

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

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

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

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

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

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

Up!