Method of facilitating multiplication of two numbers in modular-position presentation format with floating point on universal multi-core processors

FIELD: information technology.

SUBSTANCE: method is realised on a universal multi-core computer, having g k-bit cores, each facilitating a system of f operations which include algebraic multiplication and algebraic addition of numbers presented in position integer data formats. When facilitating multiplication operations, each number, multiplier and multiplicand, is presented in a modular-position format with a floating point in form of a (1+k+q·n)-element vector.

EFFECT: high rate of computation by replacing the operation of multiplying t-bit position mantissas of multiplicands with n concurrently executed operations of multiplying q-bit character positions of numbers in a residue number system.

 

The invention relates to computing, and is intended to perform the operation of multiplication of numbers represented in modular-point format floating-point universal multi-core processors.

Well-known iterative method for the multiplication of numbers represented in one of the positional binary formats floating point defined by IEEE-754. In this way the multiplication consists of a sequence of plies stacked mantis factors that are executed sequentially, adding order and addition modulo two signs of the cofactors. The sequence of plies stacked mantis factors as follows. When shifts the mantissa multiplier vacated bits are filled with zeros. If the first bit t bit position of the mantissa multiplier equal to one, then the rst term is the mantissa mnimogo, otherwise the rst term is equal to zero. If the second bit of the mantissa multiplier equal to one, then the second term is the mantissa mnimogo, shifted one digit to the left, otherwise the second term is zero. To the sum of the first and the second term is added to the mantissa mnimogo, shifted by two digits to the left, if the second bit of the mantissa multiplier equal to one, otherwise the added zero. Then to the resulting amount is added mantis mnimogo, shifted by three digits to the left, if the third bit of the mantissa multiplier equal to one, otherwise the added zero. And so on up to t-th digit of the mantissa multiplier, to the accrued amount is added to the mantissa mnimogo, shifted by v bits to the left, if the t-th bit of the mantissa multiplier equal to one, otherwise the added zero. In the end, the cumulative sum is the desired product of mantis factors. Next is the addition of the offset positional-order cofactors, thereby it turns out the order of the result. The sign of the result is determined by adding modulo two the signs of the cofactors.

The disadvantage of the iterative method of multiplying the positional binary floating-point numbers is that, first, by multiplying mantis is t-1 operations of summation of the t-bit operands. If we accept that the operation of summing the t-bit operands is performed for the t clock cycles, then the total execution time of the multiplication of mantis positional operands of the floating point will be t·(t-1) clock cycles. Secondly, the process of forming the sum is a serial process.

The technical result of the application of the method of managing the operation of multiplication of two numbers in modular-positional format floating-point universal multi-core processors is the appreciation is the speed of calculation by replacing the multiplication by t-bit positional mantis factors n parallel operations performed by multiplying the q-bit znakomity numbers in the number system of residual classes, and q≈t/n. If you take the time summation pair of t-bit numbers t clock cycles of the processor, and during summation pair of q-bit numbers q clock cycles of the processor, provided that the number of computational cores, universal multi-core processor is not less than n, and the multiplication operation of the q-bit numbers can be done by q-1 addition operations q-bit numbers, the maximum acceleration of computing S is:St(t-1)q(q-1)

Description how to perform the operation of multiplication of two numbers in modular-positional format floating-point universal multi-core processors: an implementation of the method is carried out by applying the set of electrical, neural or other signals to control devices, each computing core multi-core processor universal purpose, which, in accordance with these signals form the control commands for operating devices of the respective cores.

In the positional binary formats floating point IEEE-754 any material the number seems to be three-element set:

[M,e,S|M∈[0,2),e∈[eminemax],S∈{0,1}],(1)

where M is a rational mantissa, e is the order number, emin=2-2w-1and emax=2w-1-1, s is the sign of the number.

The magnitude of the numbers recorded in this format, is expressed by the formula -1s·M·2e. Machine representations of numbers of the form (1) are (w+t+1) - bit binary vectors 〈srw...r2r1dt...d2d1〉, where discharges c d1for dtdedicated to the representation of a rational binary mantis M=dt·dt-1...d2d1the bits with r1, rware allocated to the binary representation of the integer-order e written in the form of excess E=rwrw-1...r2r1=e+emaxthe category of s expresses the sign of the number.

We define the integer mantissa M'=dtdt-1...d2d1as t-bit nonnegative integer binary number, such that M=M'·21-t. Define moved the order of λ as a binary integer signed integer, such that λ=e-t+1, where e is a w-bit magnitude of the number represented in binary format (1).

Set n positive integer q-bit basis system of residual classes R1,R2,...,Rnsuch that ∀i1,i2∈{l,2,...,n},i1≠i 2:gcd(pi1,pi2)=1, q<k, where gcd(pi1,pi2) is the greatest common divisor ofpi1andpi2, k - bit size of grid processor.

Integer mantissa M'=dtdt-1...d2d1to convert to a system of residual

class with the specified reason R1,R2,...,Rnthereby modular mantissaM=〈m1,m2,...,mn〉:

M=m1,m2,...mn=|M' |p1,|M'|p2,...,|M'|pn,

where mi∈[0,pi-1], i=1,2,...,n - q-bit numbers (modular bits) modular mantissaM, q - bit basis p1,R2,...,Rn,|M'|pi- receive operation modulo M' on the i-th basis pi.

Thus, the floating point of the form (1) can be converted to the next modular-positional format:

[m1,m2,...mn,λ,s|,mi[0,pi-1],λ[λ'min,λ'ax ],s{0,1}].(2)

where (m1,m2,...,mnis a set of znakomity (modular bits) modular mantissaMthat λ is positionally displaced procedure representing a binary integer signed integer.

The range of values of modular mantisM=〈m1,m2,...,mn〉 in the system of residual classes with the bases of p1,R2,...,Rnthe interval of[0,P=i=1npi)thus, the t-bit position of the mantissa M=d1.dt-1...d2d1can be represented in the system of residual classes a set of n mutually independent q-bit znakomity 〈m1,m2,...,mn〉, with q≈t/n (for the case if all bases R1,R2,...,Rnq-bit).

Examples of positional conversion is of floating-point numbers in modular-positional format: let the numbers presented in 10-bit binary format of the form (1), which under the offset arrangement E is given four bits (the maximum order of emax=24-1-1=7, respectively, e=e-7), under the fractional part of the mantissa is five bits (i.e. t=6, and the integer part of d6rational mantissa M is not explicitly written) and under the sign of the number - one bit. Let to represent modular mantis in modular-positional format [〈m1,m2,...,mn〉,λ,s] used three reasons: p1=3=22-1, p2=7=23-1, p3=31=25-l.

Example 1: you want to convert the number X=[1.5,-1,0]=-1°·1.5·2-1represented in binary format [M,e,s], modular-positional format [〈m1,m2,...,mn〉,λ,s].

With account taken of the characteristics of the binary format [M,e,s], X will be recorded in computer memory as a binary vector 〈0011010000〉. For his conversion to modular-positional format (2) you must perform the following steps:

1. Highlight the part of a number, X: number sign s=0, the fractional part of the rational mantissa d5...d2d1=100002shifted (redundant) order E=01102=6.

2. To recover the integer part of d6the mantissa M=d6.d5...d2d1: d6=1, because E>0, hence M=1.100002.

3. To determine the order of e: e=e-emax=6-7=-1, because F>0.

4. To determine displaced positional order λ and alocale the ing the mantissa M':λ=e-t+1=-1-6+1=-6,M'=d 6d5...d2d1=1100002=48.

5. Find modular mantissaM=〈m1,m2,m3〉:M=〈|48|3,|48|7,|48|31〉=〈0,6,17〉.

The result is a number X represented in modular-point format floating-point: X=[〈0,6,17〉,-6,0]=-10·〈0,6,17〉·2-6.

Example 2: you want to convert the number X=[0.625-6,1]=-11·0.625·2-6from binary format [M,e,s] modular-positional format [〈m1,m2,...,mn〉,λ,s].

With account taken of the characteristics of the binary format [M,e,s], X will be recorded in computer memory as a binary vector 〈1000010100〉. For his conversion to modular-positional format (2) you must perform the following steps:

1. Highlight the part of a number, X: number sign s=1, the fractional part of d5...d2d1=101002shifted the order of E=00002=0.

2. To recover the integer part of d6the mantissa M=d6·d5...d2d1: d6=0, since E=0, hence M=0.101002.

3. To determine the order of e: e=emin=2-24-1=-6, since E=0.

4. To determine the moved order λ and the integer mantissa M': λ=e-t+1=-6-6+1=-11, M'=d6d5...d2d =0101002=20.

5. Find modular mantissaM=〈m1,m2,m3〉:M=〈|20|3,|20|7,|20|31〉=(2, 6, 20). The result is a number X represented in modular-point format floating-point: X=[〈2, 6, 20〉,-11,1]=-11·〈2, 6, 20〉·2-11.

Let A=[〈m1A,m2A,...mnA〉],λA,SA], B=[〈m1B,m2B,...mnB〉],λB,SB] - the numbers presented in modular-point format floating-point, whereMA=[〈m1A,m2A,...mnA〉],λA,SA],M B=[〈m1B,m2B,...mnB〉],λB,SB] - modular mantissa of the numbers a and b, respectively. Then the method of multiplication C=A·In numbers a and b, presented in modular-point format floating point (2), on the universal k-bit processor containing g cores, is defined as follows.

1. The multiplier A=[〈m1A,m2A,...mnA〉],λA,SA] and the multiplicand B=[〈m1B,m2B,...mnB〉],λB,SB]presented in modular-point format floating-point load in the universal k-bit processor, containing g cores, as follows:

1.1. If the number g of computing cores exceeds the number n of basis p1,R2,...,Rnthe system of residual classes used to represent modular is mantis MA=〈m1A,m2A,...mnA〉 andMB=〈m1B,m2B,...mnB〉 numbers a and b, respectively, then:

in the first nucleus of the universal multi-core processor load q-bit binary representation of the first znakomitym1Aandm1Bmodular mantisMA=〈m1A,m2A,...mnA〉, andM B=〈m1B,m2B,...mnB〉 numbers a and b, respectively, and

the basis of the system of residual classes pi, the width q of which does not exceed the size of the k bit of grid processor;

in parallel with this, the second core universal multi-core processor load q-bit binary representation of the second znakomitym2Aandm2Bmodular mantisMAandMBnumbers a and b, respectively, and the basis of the system of residual classes R2the width q of which does not exceed the size of the k bit of grid processor; etc.;

in parallel with this, in the n-th core universal multi-core processor load q-bit binary representation of the n-th znakomitym AandmnBmodular mantisMAandMBnumbers a and b, respectively, and the basis of the system of residual classes Rnthe width q of which does not exceed the size of the k bit of grid processor;

in parallel with this, in the (n+1)-th core universal multi-core processor load k-bit binary magnitude λAand λBand marks sAand sBnumbers a and b, respectively.

1.2. If the number n of basis p1p2,...,pnthe system of residual classes used to represent modular mantisMA=〈m1A,m2A,...mnA〉 andMB=〈 m1B,m2B,...mnB〉 is equal to the number g of computing cores, universal transmitter, or exceeds it, then:

q - bit binary representation of the first znakomitym1Aandm1Bmodular mantisMAandMBnumbers a and b, respectively, and q-bit basis of the system of residual classes R1load in the first nucleus of the universal multi-core processor;

in parallel with this, the q-bit binary representation of the second znakomitym2Aandm2Bmodular mantisMAmaths num="57"> MBnumbers a and b, respectively, and q-bit basis of the system of residual classes p2download the second core universal multi-core processor; etc.;

in parallel with this, the q-bit binary representation (g-1)-th znakomitymg-1Aandmg-1Bmodular mantisMAandMBnumbers a and b, respectively, and q-bit basis of the system of residual classes pg-1download (g-1)-th core universal multi-core processor;

q - bit binary representation of g's znakomitymgAandmgBmodular mantisM AandMBnumbers a and b, respectively, and q-bit basis of the system of residual classes pgload in the first nucleus of the universal multi-core processor;

q - bit binary representation of (g+1)-th znakomitymg+1Aandmg+1Bmodular mantisMAandMBnumbers a and b, respectively, and q-bit basis of the system of residual classes pg+1download the second core universal multi-core processor;

and so on until you have downloaded n s of znakomitymnAandmnBmodular mantis MA=〈m1A,m2A,...mnA〉 andMB=〈m1B,m2B,...mnB〉 numbers a and b, respectively;

in parallel with this, the k-bit binary magnitude λAndand λBand marks sAand sBnumbers a and b, respectively, are loaded into the g-oe core universal multi-core processor.

2. After the multiplier A=[〈m1A,m2A,...mnA〉,λA,SA] and the multiplicand B=[〈m1B,m2B,...mnB〉,λB,SB]presented in modular-point format floating point is th, loaded in a universal k-bit processor, containing g cores, the operation of their multiplication is as follows:

2.1. If the number g of computing cores exceeds the number n of basis p1p2,...;pnthe system of residual classes used to represent modular mantisMA=〈m1A,m2A,...mnA〉 andMB=〈m1B,m2B,...mnB〉 numbers a and b, respectively, then:

- in the first computer processor core executes the operation of integer multiplicationm1C=|m1Am1B|p1modulo p 1q-bit binary representations of znakomitym1Aandm2Bmodular mantisMA=〈m1A,m2A,...mnA〉 andMB=〈m1B,m2B,...mnB〉 numbers a and b, respectively, by finding the values of

m1C=|m1Am1B|p1=m1Am1B-m1Am1 Bp1p1wherem1Am1Bp1is the greatest integer not exceedingm1Am1Bp1; all operations are integers and are in a positional binary notation;

in parallel with this, the second computing core processor runsm2C=|m2Am2B|p2modulo p2q-bit binary representations of znakomitym2Aandm2Bmodular mantis MAandMBnumbers a and b, respectively; all operations are integers and are in a positional binary notation; etc.;

in parallel with this, the n-th computing processor core executes the multiplication operationmnC=|mnAmnB|pnmodulo pnq-bit binary representations of znakomitymnAandmnBmodular mantisMAandMBnumbers a and b, respectively; all operations are integers and are in a positional binary notation;

pair is in parallel with this, in the (n+1)-th computing core processor is the addition of binary orders of magnitude λAand λBand the addition modulo two sC=|sA+sB|2marks sAand SBnumbers a and b, respectively.

2.2. If the number n of basis p1p2,...,pnthe system of residual classes used to represent modular mantisMA=〈m1A,m2A,...mnA〉 andMB=〈m1B,m2B,...mnB〉 is equal to the number g of computing cores, universal transmitter, or exceeds it, and each j-oe computational core of the first (g-1) computational cores loaded wjznakomity

mi(g-1)+jA andmi(g-1)+jB,i=0,1,...,w1-1, then:

in the first computing core processor sequentially performs the operations of multiplicationmi(g-1)+1C=|mi(g-1)+1Ami(g-1)+1B|pi(g-1)+1the modules pi·(g-1)+1, i=0,1,...,w1-1, g-razryadnikh binary representations of all w1downloaded it znakomitymi(g-1)+1Aandmi(g-1)mo> +1B, i=0,1,...,w1-1 modular mantisMA=〈m1A,m2A,...mnA〉 andMB=〈m1B,m2B,...mnB〉 numbers a and b, respectively, by finding the values of|mi(g-1)+1Ami(g-1)+1B|pi(g-1)+1=mi(g-1)+1Awhat is mi(g-1)+1B-mi(g-1)+1Ami(g-1)+1Bpi(g-1)+1pi(g-1)+1,i=0,1,...,w1-1,gdemi(g-1)+1Ami(g-1)+1Bpi(g-1)+1

is the greatest integer not exceedingmi (g-1)+1Ami(g-1)+1Bpi(g-1)+1; all operations are integers and are in a positional binary notation;

in parallel with this, the second computing core processor consistently performsthe multiplicationmi(g-1)+2C=|mi(g-1)+2Ami(g-1)+2B|pi(g-1)+2

the modules pi·(g-1)+2, i=0,1,...,w2-1, q-bit binary representations of all w2downloaded it znakomity mi(g-1)+2Aandmi(g-1)+2B, i=0,1,...,w2-1,modular mantisMAandMBnumbers A and B, respectively; all operations are integers and are in a positional binary notation; etc.;

- in parallel, in (g-l)-M computing core processor sequentially performs the operations of multiplicationm(i+1)(g-1)C=|m(i+1)(g-1)Am(i+1)(g-1) B|p(i+1)(g-1)the modules p(i+1)·(g-1), i=0,1,..., wg-1-1, q-bit binary representations of all Wg-1downloaded it znakomitym(i+1)(g-1)Aand m(i+1)(g-1)B, i=0,1,...,Wg-1-1 modular mantisMAandMBnumbers a and b, respectively; all operations are integers and are in a positional binary notation;

in parallel with this, in g-m computing core processor is the addition of binary orders of magnitude λAand λBand the addition modulo two sC=|sA+sB|2marks sAand sB numbers a and b, respectively.

As a result of performing these operations is obtained the product

C=[m1C,m2C,...mnC,λC,sC]numbersA=[m1A,m2A,...mnA,λA,sA]andB=[m1B,m2B,...mnB,λB,sB]presented in modular-point format floating-point.

Example: it is necessary to perform a multiplication operation C=A·In modular-point format floating-point universal processor containing four 5-bit calc the positive nucleus. To represent mantis operands are specified, the following 5-bit base system of residual classes: p1=3=22-1, p2=7=23-1, R3,=31=25-1, P=p1·p2·p3=65l - piece bases (the upper limit of the allowable range view of modular mantis). The factors specified in modular-positional format as follows: A=[〈2,4,11〉,-4,1], B=[〈2,3,17〉,2,0].

1. The multiplier A=[〈2,4,11〉,-4,1] and the multiplicand B=[〈2,3,17〉,2,0] download universal 5-bit processor with four computing cores, as follows:

in the first kernel is loaded the first znakomitsyam1A=2andm1B=2modular mantisMA=(2, 4, 11) andMB=(2, 3, 17), and the Foundation of the system of residual classes p1=3;

in parallel with this, the second kernel loadable second znakomitsyam2A=4 andm2B=3modular mantisMA=(2, 4, 11) andMB=(2, 3, 17), and the Foundation of the system of residual classes R2=7;

in parallel with this, in the third nucleus downloadable third znakomitsyam3A=11andm3B=17modular mantisMA=(2, 4, 11) andMB=(2, 3, 17), and the Foundation of the system of residual classes R3=31;

in parallel with this, the fourth core universal multi-core processor loaded 5-bit binary magnitude λA=-4 and λB=2, and marks sA=1 and sB=0.

2. As the number of acyclically processor cores exceeds the number of bases of p 1,R2,...,pnthe system of residual classes used to represent modular

mantisMA=(2, 4, 11) andMB=(2, 3, 17) numbers a and b, respectively, the multiplication operation is performed in the following way:

- in the first computer processor core operation

integer multiplication modulo p1:m1C=|m1Am1B|p1=|22|3=1;

in parallel with this, the second computing processor core operation integer multiplication modulo p2:m2C=|m2Am2B|p2=|43|7= 5;

in parallel with this, the third computing processor core operation integer multiplication modulo p3:m3C=|m3Am3B|p3=|1117|31=1;

in parallel with this, the fourth computing core processor running add the binary orders of magnitude λAand λBand the addition modulo two sC=|sA+sB|2marks sAand sBnumbers a and b, respectively: λCAB=-4+2=-2, sC=|sA+sB|2=|1+0|2=1.

In the result the result C=[〈1,5,1〉, of-2.1] modular-point format floating-point corresponding to the positional number -11·187·2-2.

If taken during the addition of a pair of the q-bit residue q quanta of the universal processor containing g k-bit cores, and q≤k, then the calculation works t-bit mantics of floating point numbers a and b, at t≈q·n in the limiting case (when (miAmiB)<pi, i=1,2,...,n) no described method is q·(q -1) cycles, whereas the time multiplying the iterative method is equal to t·(t-1)≈q·n·(q·n-1) clock cycles. To calculate the magnitudes and signs of the operands will need k cycles (k-1 tact to sum orders, and 1 stroke for summation signs), and their calculation will be carried out in parallel with calculation of znakomity modular mantis, so the time to compute orders of magnitude and signs of the result of multiplying the floating-point operands is ignored. Thus, while the multiplication of floating point numbers on the basis of the described method in

t(t-1)q(q-1)=qn(qn-1)q(q-1)=n(qn-1)(q-1)once you have the e in comparison with the known performance of the iterative method of multiplying the positional floating-point numbers.

The way organizations perform the operation of multiplication of two numbers in modular-positional format floating-point universal multi-core processors, namely, that:
universal multi-core solver contains g k-bit cores, each of which provides a system of f operations, which include operations algebraic multiplication and algebraic addition on numbers represented in positional integer data formats;
when organizing the operations of multiplying each number, the multiplier and the multiplicand, is presented in modular-point format floating-point in the form (1+k+q·n) - element vector, where:
the first left digit of s is a senior rank in the format of a number, and is given by the sign of the number, and if s=0 then the number is positive, if s=1 then the number is negative;
following the first discharge s number k of bits allocated for storage of positional order of numbers representing a binary integer number of λ with the sign of sλvarying finite floating-point numbers in the range λmin≤λ≤λmaxand the resulting conversion of the number of positional floating-point format by the expression λ=e-t+1, where e defines what elicina numbers in binary positional notation a floating-point expression (-1 s·M·2e) if 0≤M<2, which is rational t-bit mantissa of a number in binary positional floating-point format, λmin=2-2k-1, λmax=2k-1-2 if sλ=0 the order of λ is positive, and if sλ=1 order λ is negative;
following the (k+1) discharge q·n bits, with q≤k, are assigned to represent the mantissa of the number ofM=m1,m2,...,mnin modular-point format, and the significand is represented in the system of residual classes with n bases p1, R2, ..., pn, n is the number of znakomity mantissa, q - bit width of each znakomitsya; moreover, each i-th znakomitsya, where 1≤i≤n, appears to be a non-negative integer number miin binary positional notation; the value of mieach i-th znakomitsya is determined by the expressionmi=|M'|piwhere M' is an integer non-negative binary number defined by the expression M'=M·2t-1M - the diet is supplemented flax t-bit mantissa of a number in binary positional floating-point format, |M'|pi- receive operation modulo M' i-oe basis of pi;
the range of modular mantissaM=m1,m2,...,mnin a positional number system is determined by the interval[0,P=i=1npi);
values of the order of λ and mantissaM=m1,m2,...,mnpositive finite numbers when s=0 in modular-positional format [λ,s,〈m1,m2,...,mn〉] are respectively in the following ranges: 2-2k-1≤λ≤2k-1-2, 〈01,02,...,0n〉≤M ≤〈(p1-1) (p2-1),...,(pn-1)〉;
values of the order of λ and mantissaM=m1,m2,...,mnnegative finite numbers when s=1 in modular-positional format are respectively in the following ranges: 2-2k-1≤λ≤2k-1-2, 〈01,02,...,0n〉≤M≤ 〈(p1-1) (p2-1),...,(pn-1)〉;
the value of positive infinity is represented in modular-positional format as follows: s=0, λ=λmax+1=2k-1-1,M=01,02,...,0n;
the value is negative infinity is represented in modular-positional format as follows: s=1, λ=λmax+1=2k-1-1,M=01,02,...,0n/math> ;
for positive non-numeric values (NaN) in modular-positional format [s,λ,〈m1,m2,...,mn〉], when s=0, the value of the positional order of λ is determined by the expression λ=λmax+1=2k-1-1, and the values of the mantissaM=m1,m2,...,mnrange 〈11,12,...,1n〉≤M≤〈(p1-1) (p2-1),...,(pn-1)〉;
for negative non-numeric values (NaN) in modular-positional format, when s=1, the value of the positional order of λ is determined by the expression λ=λmax+1=2k-1-1, and the values of the mantissaM=m1,m2,...,mnrange 〈11,12,...,1n〉≤M≤〈(p1-1) (p2-1),...,(pn-1)〉;
values in modular-positional format, there is the following positional value of the order λ=λ min-1=1-2k-1when changing the values of the modular mantissa in the range 〈11,12,...,1n〉 ≤M≤ 〈(p1-1) (p2-1),...,(pn-1)〉, are for advanced coding exceptional situations that may arise in the calculation process, namely: loss of order and full order;
the signal processor multiplierA=[m1A,m2A,...mnA,λA,sA]and the multiplicandB=[m1B,m2B,...mnB,λB,sB]presented in modular-point format floating-point load in the universal k-bit processor, containing g cores, as follows:
provided that g≥n+1, i.e. if the number of computational poison the p processor exceeds the number of bases of the system of residual classes, used to represent modular mantisMA=〈m1A,m2A,...mnA〉 andMB=〈m1B,m2B,...mnB〉 numbers a and b, respectively, then:
in the first nucleus of the universal multi-core processor load q-bit binary representation of the first znakomitym1Aandm1Bmodular mantisMA=〈m1A,m2A,...mnAand MB=〈m1B,m2B,...mnB〉 numbers a and b, respectively, and the basis of the system of residual classes p1;
in parallel, the second core universal multi-core processor load q-bit binary representation of the second znakomitym2Aandm2Bmodular mantisMAandMBnumbers a and b, respectively, and the basis of the system of residual classes p2; in parallel, in the third ÷ n-th core universal multi-core processor load q-bit binary representation of third ÷ n's znakomitym3A÷ mnAandm3B÷mnBmodular mantisMAandMBnumbers a and b, respectively, and the basis of the system of residual classes p3÷pn;
in parallel, in the (n+1)-th core universal multi-core processor load k-bit binary magnitude λAand λBand marks sAand sBnumbers a and b, respectively;
provided that g<n+1, i.e. if the number of bases of the system of residual classes used to represent modular mantisMA=〈m1A,m2A,...mnA〉 andMB =〈m1B,m2B,...mnB〉 numbers a and b, respectively, equal to the number of computational cores, universal transmitter, or exceeds it, then:
q-bit binary representation of the first znakomitym1Aandm1Bmodular mantisMAandMBnumbers a and b, respectively, and the basis of the system of residual classes R1load in the first nucleus of the universal multi-core processor;
in parallel, the q-bit binary representation of the second znakomitym2Aandm2Bmodular mantisMA andMBnumbers a and b, respectively, and the basis of the system of residual classes R2download the second core universal multi-core processor;
in parallel, similarly loaded q-bit binary representation of third ÷(q-1)-th znakomitym3A÷mg-1Aandm3B÷mg-1Bmodular mantisMAandMBnumbers a and b, respectively, and the basis of the system of residual classes p3÷pg-1in the third ÷(g-1)-th core universal multi-core processor;
q-bit binary representation of g's znakomity mgAandmgBmodular mantisMAandMBnumbers a and b, respectively, and the basis of the system of residual classes pgload in the first nucleus of the universal multi-core processor;
similarly, the q-bit binary representation of (g+1)-th znakomitymg+1Aandmg+1Bmodular mantisMAandMBnumbers a and b, respectively, and the basis of the system of residual classes pg+1download the second core universal multi-core processor;
the cyclic process the download continues until you have downloaded n s of znakomitsya mnAandmnBmodular mantisMA=〈m1A,m2A,...mnA〉 andMB=〈m1B,m2B,...mnB〉 numbers A and b, respectively;
in parallel, the k-bit binary magnitude λAand λBand marks sAand sBnumbers a and b, respectively, are loaded into the g-oe core universal multi-core processor;
after multiplierA=[m1A,m2A,...,mnA,λA,sA ]and the multiplicandB=[m1B,m2B,...,mnB,λB,sB]presented in modular-positional format
floating point loaded in a universal k-bit processor, containing g-cores, the operation of their multiplication is as follows:
provided that g≥n+1, i.e. if the number of computing cores exceeds the number of bases of the system of residual classes used to represent modular mantisMA=m1A,m2A,...,mnAandMB=m1B,m2B,...,mnBh the villages a and b, respectively, then:
in the first computer processor core executes the operation of integer multiplicationm1C=|m1Am1B|p1modulo p1q-bit binary representations of znakomitym1Aandm2Bmodular mantisMA=m1A,m2A,...,mnAandMB=m1B,m2B,...,mnBnumbers a and b, respectively, by finding the values ofm1C= |m1Am1B|p1=m1Am1B-m1Am1Bp1p1wherem1Am1Bp1is the greatest integer not exceedingm1Am1Bp1; all operations are integers and are in a positional binary notation;
in parallel, the second computing processor core in a similar way is the multiplication operationm2C=|m2Am2B|p 2modulo p2q-bit binary representations of znakomitym1Aandm2Bmodular mantisMAandMBnumbers a and b, respectively; all operations are integers and are in a positional binary notation;
in parallel with this, in the third ÷ n-th computing core processor works in a similar manner the multiplication operationm3C=|m3Am3B|p3÷mnC=|mnAmnB|pnmodulo p3÷pnq-bit binary representations of the EIT is oposici m3A÷mnAandm3B÷mnBmodular mantisMAandMBnumbers a and b, respectively; all operations are integers and are in a positional binary notation;
in parallel with this, in the (n+1)-th computing core processor is the addition of binary orders of magnitude λAand λBand the addition modulo two sC=|sA+sB|2marks sAand sBnumbers a and b, respectively;
provided that g<n+1, i.e. if the number of bases of the system of residual classes used to represent modular mantisMA=m1A,m2A,...,m nAandMB=m1B,m2B,...,mnBnumbers a and b, respectively, equal to the number of computational cores, universal transmitter, or exceeds it, and in each j-th kernel of the first (g-1) computational cores loaded wjznakomitymi(g-1)+jAandmi(g-1)+jB, i=0,1,...,wj-1, then:
in the first computer processor core for all i=0,1,...,w1-1 sequentially performs the operations of multiplicationmi(g-1)+1C=|mi(g-1)/mo> +1Ami(g-1)+1B|pi(g-1)+1the modules pi·(g-1)+1, q-bit binary representations of all w1downloaded it znakomitymi(g-1)+1Aandmi(g-1)+1B, modular mantisMA=m1A,m2A,...,mnAandMB=m1B,m2B,...,mnB/mrow> numbers A and B, respectively, by finding the values of|mi(g-1)+1Ami(g-1)+1B|pi(g-1)+1=mi(g-1)+1Ami(g-1)+1B-mi(g-1)+1Ami(g-1)+1Bpi(g-1)+1pi(g-1)+1 wheremi(g-1)+1Ami(g-1)+1Bpi(g-1)+1is the greatest integer not exceedingmi(g-1)+1Ami(g-1)+1Bpi(g-1)+1; all operations are integers and are in a positional binary notation;
in parallel, the second computing processor core in the same way for all i=0,1,...,w2-1 sequentially performs the operations of multiplicationmi(g-1)+2 C=|mi(g-1)+2Ami(g-1)+2B|pi(g-1)+2the modules pi·(g-1)+2, q-bit binary representations of all w2downloaded it znakomitymi(g-1)+2Aandmi(g-1)+2B, modular mantisMAandMBnumbers a and b, respectively; all operations are integers and are in a positional binary notation;
in parallel with this the m in the third ÷(g-1)-M computing processor core in the same way consistently for all i=0,1,...,w 3-1÷i=0,1,...,wg-1-1 performs a multiplication operationmi(g-1)+3C=|mi(g-1)+3Ami(g-1)+3B|pi(g-1)+3÷m(i+1)(g-1)C=|m(i+1)(g-1)Am(i+1)(g-1)B|p(i+1)(g-1) the modules pi·(g-1)+3÷p(i+1)·(g-1)q-bit binary representations of all w3÷wg-1downloaded znakomitymi(g-1)+3A÷m(i+1)(g-1)Aandmi(g-1)+3B÷m(i+1)(g-1)Bmodular mantisMAandMBnumbers A and b, respectively; all operations are integers and are in a positional binary notation;
in parallel, in g-m computing core processor is the addition of binary orders of magnitude λAand λBand takinogawa modulo two s C=|sA+sB|2marks sAand sBnumbers a and b, respectively;
as a result of performing these operations is obtained the product ofC=[m1C,m2C,...mnC,λC,sC]numbersA=[m1A,m2A,...mnA,λA,sA]andB=[m1B,m2B,...mnB,λB,sB]presented in modular-point format floating-point.



 

Same patents:

FIELD: information technology.

SUBSTANCE: device includes input registers for temporary storage of bits of the initial number, memory for storing products and a parallel adder.

EFFECT: faster operation of the device for determining the sign of a number and reducing equipment.

3 dwg

FIELD: information technology.

SUBSTANCE: device includes input registers, sign determining circuits, number polarity shifting circuits, look-up tables (memory) for storing constants and an adder, an XOR element and a number sign analysis circuit.

EFFECT: faster operation of the device and cutting hardware costs.

3 dwg

FIELD: information technology.

SUBSTANCE: method comprises steps of: concurrently writing the remainder on base p1 of a multiplicand in memory elements; concurrently counting the number of units bi in each column of the i-th matrix; shifting the binary number b1 one bit to the right; summing with a number b2; shifting the obtained sum b2s one bit to the right and summing with a number b3. Similarly, the obtained sums are shifted and summed with subsequent numbers to obtain a sum b2*m1s, wherein the least significant bit of the number b1 is the first multiplication bit s1, the least significant bit of each obtained sum bis is the i-th multiplication bit. The binary number b2*m1s is shifted; the least significant bit of the obtained number is the (2*m)-th bit of the determined product s2*m. If s is greater than p1, the obtained product s is corrected by successive subtraction of the base p1 from s until s is less than p1, otherwise correction is not performed; similarly, products of m-bit residues on the rest of the bases are calculated and corrected; the powers of multipliers are simultaneously summed up and the resultant sum is the power of the determined product.

EFFECT: faster computation.

2 dwg

FIELD: information technology.

SUBSTANCE: device has an n-bit adder, an (n+1)-bit adder, a multiplexer and a register.

EFFECT: broader functional capabilities due to introduction of the modulo addition operation.

1 dwg

FIELD: information technology.

SUBSTANCE: remainder on base pi of a multiplicant is concurrently recorded in matrix memory elements of the i-th multiplier; the number of units bi in each column of the i-th matrix is concurrently counted; the binary number b1 is shifted by one bit to the right and summed with number b2; the obtained sum bs2 is shifted by one bit to the right and summed with number b3. Similarly, the obtained sums are shifted and summed with subsequent numbers to obtain a sum bs2*m-1, wherein the least significant bit of the number b1 is the first multiplication bit s1, the least significant bit of each obtained sum bsi is the i-th multiplication bit. The binary number bs2*m-1 is shifted, the least significant bit of the obtained number is the (2*m)-th bit of the determined product s2*m. If si is greater than pi, the obtained product si is corrected by successive subtraction of the base pi from si until si is less than pi, otherwise correction is not performed; powers of multipliers are simultaneously summed up and the resultant sum is the power of the determined product.

EFFECT: faster computation.

2 dwg

FIELD: information technology.

SUBSTANCE: invention can be used in digital computers as well as digital signal processing devices and cryptographic applications. The device has logic elements NOT, AND, OR.

EFFECT: high speed of operation of the adder due to parallel execution of the modulo addition operation.

1 dwg, 1 tbl

FIELD: information technology.

SUBSTANCE: apparatus has input registers, projection generating circuits, memory units, adders, an analysis circuit, AND logic elements, a flip-flop and a projection counter.

EFFECT: high speed of determining functional characteristics and cutting hardware costs.

1 dwg

FIELD: information technology.

SUBSTANCE: homogeneous computing environment cell has an XOR element, an AND element and two flip-flops.

EFFECT: faster operation and reliability.

3 cl, 6 dwg, 3 tbl

FIELD: information technology.

SUBSTANCE: device for generating remainder on arbitrary modulus of a number has first and second registers, a group of AND elements, a unit of half-adders and a delay element, where the device also includes (K-1) half-adders, to whose second data inputs a modulus code is transmitted, and a number code "1" is transmitted to the first data input of the first half-adder and the second data input of the group of AND elements, the output of the i-th half-adder is connected to the second data input of the group of AND elements and with shift of one bit towards the most significant bits to the first data input of the i+1 half-adder, where i=1,…,K-2, the K-1 output of the half-adder is connected to the second data input of the group of AND elements.

EFFECT: cutting the size of equipment.

2 dwg

Doubler by module // 2445681

FIELD: information technologies.

SUBSTANCE: invention may be used in digital computing devices, and also in devices to generate elements of end fields and in cryptographic applications. The device comprises summators, multipliers, inverters and multiplexors.

EFFECT: expanded range of input number values.

1 dwg

FIELD: computers.

SUBSTANCE: device has N blocks for calculating remainders, each of which has N devices for calculating remainders from bases of modular notation scale, including multiplication blocks, module adders of 3N numbers and tabular calculators.

EFFECT: higher speed of operation.

5 dwg, 1 ex

FIELD: computer science.

SUBSTANCE: device has harmonic signal generator, controlled phase changers, means for measuring phase of harmonic signal, phase changers for fixed phase values, transformers of binary number code to unary in accordance to first and second sub-modules, coder and table calculation means.

EFFECT: lower costs.

3 dwg

FIELD: computer science, possible use for engineering of signals processing microprocessors, and of digital filters.

SUBSTANCE: device uses neural-network technologies and polynomial residuals system, wherein as system base minimal polynomials pi(z), where input=1,2,...,n, are utilized, determined in expanded Galois fields GF(2V), while device has clock counter, two blocks for calculating sums of paired results of multiplication by arbitrary base, error correction block, modular adder and block for calculating sums of paired results of multiplication based on control base.

EFFECT: decreased hardware requirements, improved speed of operations.

2 dwg, 3 tbl

FIELD: automatics and computer science, possible use for engineering of computing structures functioning in modular computation system.

SUBSTANCE: device has encoder, controlled phase shifter, harmonic signal generator, phase shifters for fixed phase value, device for measuring the phase of harmonic signal, multiplexer, commutator, amplitude detector and harmonic signal amplifier.

EFFECT: simplified construction of device.

3 dwg

FIELD: computer science, in particular, modular neuron-computer means.

SUBSTANCE: network has input layer of neurons, neuron network of end ring for determining number rank, neuron network of end ring for calculating remainder at base n+1, n-neuron networks of end ring for calculating scaled number, neuron network for calculating difference in numbers between input remainders and base remainder.

EFFECT: decreased volume of equipment, increased speed of numbers rounding and expanded functional capabilities.

1 dwg

FIELD: cryptographic method and chip-card for encoding information, methods for creating electronic signatures.

SUBSTANCE: at least one calculation step is performed, providing for realization of E operation of modular exponentiation in accordance to formula E=xd(mod p·q), where d and mod p·q are components of a secret key, while parallel represent first simple multiplier, q is second simple multiplier, d is level coefficient, and x represents base, while operation E of modular exponentiation is performed in accordance to Chinese theorem about remainders.

EFFECT: decreased amount of computing operations and machine time costs during simultaneous increase of level of data protection from unsanctioned access.

4 cl

FIELD: computer science, possible use in computing devices functioning in system of remainder classes, and also communication equipment for transferring information in remainder classes system codes.

SUBSTANCE: device contains a group of constant memorizing devices, a group of registers, discharge-parallel modulus adder.

EFFECT: decreased volume of equipment and increased speed of operation when transforming a number from remainder classes system to positional code.

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

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 for forming code series, creation of which is based on finite fields theory.

SUBSTANCE: device contains block for forming partial remainders, modulus multiplexers, modulus adders.

EFFECT: expanded functional capabilities due to creation of remainders by double modulus, by calculating partial remainders from polynomial powers with their following addition in acc to coefficients of polynomial powers.

3 dwg

Up!