JPH0833815B2 - High digit multiplier - Google Patents

Description

Description: TECHNICAL FIELD The present invention relates to a high-speed multiplication device that multiplies high-digit numerical values in various information processing devices using a computer.

[Conventional technology]

Multiplying high-digit numbers is NP (non-linear programming)
It often appears in the process of solving a problem or in the process of scientific calculation including factorial calculation. If the numerical value is 2 billion digits or less, it is calculated as 32 bits or less in one clock by a 32-bit multiplication processor or the like. For numbers with more digits, it was necessary to use floating point arithmetic. This is not a problem when a small error is allowed, but there is also a problem that accumulation of errors is not allowed and there is a problem that cannot be solved by floating-point arithmetic. As described above, with the advance of science and technology, highly accurate calculation of numerical values with higher digits is required.

There is also a way to aim for a multiplication processor of 64 bits or more, but there is always a demand for higher-digit arithmetic. In addition, since the data bus width between the memory and the processor in the computer and the number of terminals are limited, the bit width cannot be increased unnecessarily. Currently, the realization of high-digit floating-point arithmetic processors is actively demanded.
Even if the technology is used, it is quite difficult to realize a 64-bit or more multiplication circuit as an LSI chip.

Software is needed to accurately calculate the multiplication result of high-order digits instead of floating-point arithmetic.The high-order multiplication process is decomposed, partial products are sequentially obtained, and partial calculation results are combined. A program for obtaining the final calculation result was used. However, in this case, there is a problem that the calculation speed becomes slow. This is because the processing speed increases with the number of digits in proportion to about the square of the number of digits.

[Problems to be Solved by the Invention]

It is difficult to increase the number of digits in the above-mentioned conventional hardware hardware multiplication with one LSI chip, and the floating-point arithmetic processor cannot avoid the truncation error, so the high precision required for high-digit arithmetic is realized. There was a flaw that I could not do. On the other hand, since the multiplication processing by software includes sequential processing, there is a drawback that speedup cannot be realized.

The object of the invention is to overcome these drawbacks associated with multiplication of high-order numbers.

Another object of the present invention is to provide a circuit configuration technology that allows a large number of multiplication circuits to be executed by connecting a large number of multiplication circuits having a limited number of digits due to the limitation of the number of input terminals and the data bus width. At the same time, it is an object of the present invention to provide an exponential conversion type high-digit multiplication algorithm and a design technology for a small-sized high-speed high-digit multiplication circuit using the same.

[Means for solving the problem]

The present invention is a high-digit multiplication device comprising a plurality of m-digit multiplication units, wherein each m-digit multiplication unit has a register for m digits of a multiplicand of n bits for each digit and a clock signal for a multiplier of n bits for each digit. , An n-bit multiplication circuit for multiplying each digit multiplier by the multiplicand of each digit held in the register, and an i-th (i is a positive integer less than or equal to m) digit multiplier First adder for adding the contents of the carry register to the output of, the partial product register for storing the output (2n bits) of the first adder separately for upper and lower n bits, and the upper part of the i-th partial product register It is composed of a second adder for adding n bits to the lower n bits of the partial product register of the (i + 1) th digit and a carry register for temporarily storing the output of the second adder. In the first half of the input clock cycle of the bit code, A first clock signal line for setting the output of the first adder to the partial product register and a second clock signal line for setting the output of the second adder to the carry register in the latter half. Is provided.

Further, the present invention is a high-digit multiplication device comprising a plurality of m-digit multiplication units connected together and one exponential conversion circuit, wherein each m-digit multiplication unit has an n-bit digit after each exponent conversion. A register for m digits that stores the exponent code of the multiplicand, an input bus that gives the exponent code of the exponent-converted n-bit multiplier for each digit in synchronization with the clock signal, and an exponent code for each digit multiplier An adder circuit that performs addition with the exponent code of the multiplicand of each digit, an inverse exponent converter circuit connected to the adder circuit, and a digit at the output of the i-th (i is a positive integer less than or equal to m) digit First to add the contents of the raising register
N and the output of the first adder (2n bits)
A partial product register that stores the divided bit by bit, a second adder that adds the upper n bits of the i-th partial product register to the lower n bits of the partial product register of the (i + 1) th digit, A carry register for temporarily storing the output of the adder is provided.

〔Example〕

FIG. 1 is a configuration diagram of a basic circuit of an embodiment of a high digit multiplication apparatus of the present invention. Before entering a detailed description of the contents, the basic method of high-digit multiplication will be described with reference to FIG. FIG. 3 (a) is an explanatory diagram of a high-digit multiplication process, in which the multiplication is carried out in the same procedure as when performing decimal multiplication. FIG. 3 (b) shows the procedure of multiplication processing in the high-digit multiplication apparatus of the present invention.

In either case, the high-order multiplicand 310 and the multiplier 320 to be multiplied are converted into a code string in units of n bits (n is a positive integer of 2 or more). Then, the code string of the multiplicand 310 is sequentially arranged from the lower digit to the m-digit multiplication device 300 (circuit of FIG. 1).
, And holds one code in each of m (positive integers of 2 or more) n-bit registers. Next, the code string of the multiplier 320 is sequentially input to the m-digit multiplication device 300.

Each time the multiplier code is input, the multiplier device 300 simultaneously multiplies the multiplier code by the m multiplicand codes, and outputs the partial product 330 of the result in parallel for m digits. Divide them into the output code and shift code of that digit, and add them to the m partial products when the next multiplier code is input. That is, by adding the shift code obtained previously to the output code of the next partial product, the output code 340 of the partial product can be sequentially taken out from the lower digit. At this time, it is necessary to sequentially input (m + 1) or more zeros after the input of the multiplier code string (assuming d digits) to discharge the calculation result. As a result, the code string 340 covers (d + m + 1) digits.

The multiplicand converted into a code string of each digit n bits is 1
Considering the case of high digits that cannot be stored in one LSI chip, it is important to be able to connect and use the chips.
Therefore, the code strings of the multiplicand that are sequentially input first are stored in the k units 300 of m each. Then, the k units are connected as shown in FIG.

The multiplicand is stored in order from the lower digit side of the plurality of units first, then the code string of the multiplier is input to all units, and then (km + 1) 0s are additionally input. Whenever each digit of the multiplier is input, the partial product of each digit multiplier code and the multiplicand code is calculated all at once, and the output codes are sequentially output from the lower digit side.

The multiplication processing of high-digit numerical values in the connected k units is executed in parallel for each unit, and the calculation result of each unit is sequentially output from the lower digit as a code string of each digit n bits. Then, each unit sends the code string of the calculation result to the adjacent unit on the lower digit side, and sequentially receives the code string of the calculation result from the adjacent unit on the upper digit side.

The circuit of the embodiment shown in FIG. 1 is used in each unit during high-order multiplication using a plurality of units.
This is an example of a digit multiplying circuit, which only shares a part of the high digit operation, but has a circuit structure of a repetitive structure that executes as many high digit multiplications as possible by concatenation.

The specific circuit configuration of this embodiment is as follows. That is, the register 110 for m digits of the multiplicand of n bits for each digit
And an input bus 120 for inputting in synchronization with the clock signal of each digit n-bit multiplier, and an n-bit multiplication circuit 13 for multiplying each digit multiplier by the multiplicand of each digit held in the register 110.
Multiply circuit 130 for 0th and i-th (i is a positive integer less than or equal to m) digits
First adder 15 which adds the contents of the shift register to the output of
0, a partial product register 160 that stores the output (2n bits) in upper and lower n bits, and stores the upper n bits of the i-th partial product register 160 and the lower part of the (i + 1) th digit partial product register 160. Second adder 170 for adding n bits
And a shift register 140 for temporarily storing its output, a decoder 192 for controlling selective (sequential from the lower digit) setting of the multiplicand code to the register 110, and a clock signal counter 191.

The high-digit multiplication is executed every time the multiplier code is input from the terminal 125 to the bus 120. Each digit multiplier code and register
The n-bit multiplication circuit 130 simultaneously calculates the product of all the digits and the multiplicand code held in 110. The multiplication result obtained from the partial product calculation of each digit is added by the shift code held in the register 140 by the first adder 150. The result is held in the partial product register 160 by the clock signal CLK _{2 which} is a half cycle behind the clock signal CLK ₁ . The partial product register stores the 2n-bit output of the first adder 150 by dividing it into upper n bits and lower n bits. The multiplication result is the lower n bits, and is synchronized with the clock signal CLK ₂ , and is sequentially output from the lower digit as a (d + m + 1) digit code string from the partial product register 160 via the terminal 185.

Here, the multiplication algorithm will be described in more detail with reference to FIG. Now, let the multiplicand 310 be a code Xi of each digit n bits, i = 1, 2, ..., M. These are stored in the register 110. Also, the code of each digit n bits of the multiplier 320 is Yt, t = 1,2, ..., d. It is assumed that the code Y ₁ of the first digit is given at time t = 1.

When the tth code Yt of the multiplier is input, the n-bit multiplication circuit 130 simultaneously calculates the following partial products Yt * Xi i = 1,2, ..., m. The results of these calculations are the first adder
The content C of the shift register 140 is added at 150 and stored in the partial product register 160. That is, the addition result 340 obtained by adding the shift signal Ci ₋₁ to the output of the first adder 150 is Zi (t) = Yt * Xi + Ci ₋₁ (t−1 + θ) (1). Where θ is the time delay of half a clock,
(T-1 + θ) indicates a time half clock before the time t. Therefore, the lower n bits of Zi (t) become the output data, and become the upper n bits of the shift signal Ci _-1 .

Therefore, the calculation result Zi (t) obtained by the equation (1) is divided into the upper n-bit code bi (t) and the lower n-bit code ai (t) in the partial product register 160. That is, the output of the partial product register 160 is represented by Zi (t) = ai (t) * 2n + bi (t) (2). Therefore, bi (t) is output so as to be added to the lower-order partial product, while ai (t) is added to the higher-order partial product. That is, when the stored content of the shift register is Ci (t-1), it is the second adder 170.
From, it is calculated by the following formula. That is, Ci (t-1 + θ) = ai (t-1) + bi _{+ 1} (t-1)
(3) This calculation is performed by the second adder 170. The shift code of the calculation result is set in the register 140 in synchronization with the clock signal CLK ₁ . This clock signal is used to call the next multiplier code and start the partial product operation in the multiplication circuit 130. With this CLK ₁ , a shift code is always prepared before the partial product operation is completed. It will be. Such a calculation is typical of the two-stage pipeline processing, and is easily executed by using the clock signals CLK ₁ and CLK ₂ alternately input from the terminals 190 and 195.

The pipeline processing at each digit of the high digit multiplication processing will be described with reference to FIG. As a matter of course, it is assumed that the multiplicand code string is sequentially set in advance from the lower digit side to the upper digit side of the register 110. The multiplier code string is fetched from the terminal 125 at the falling edge of the input clock signal CLK ₁ and sent to the multiplication circuit 130 via the input bus 120.

When the multiplier code is input to the n-bit multiplication circuit 130,
After the operation delay time of several tens of nanoseconds, the multiplication result of the partial product Xi * Yt is output. It is sent to the first adder 150. Therefore, the contents of the shift register 140 are added. After a delay of several nsec, the addition result is output from the first adder 150. It is set in the partial product register 160 at the falling time of the clock signal CLK ₂ .

Therefore, the second adder 170 using the output of the register 160
Outputs the addition result after a delay of the delay time (several nsec) of the second adder 170 from the clock signal CLK ₂ . This is the shift register when the clock signal CLK ₁ falls.
Set to 140. The output of this register 140 has finished changing before being used by the first adder 150.

In this way, by alternately setting the addition results in the registers 140 and 160, it is possible to achieve a multiplication processing speed in a clock cycle of 10 nsec or less. That is,
The calculations of the expressions (1) and (3) are simultaneously executed by the m-digit multiplication / addition circuit and alternately with a half cycle difference.

The circuit configuration for such pipeline processing in FIG. 1 has a completely repetitive structure and is suitable for LSI. When n is 4, the 4-bit multiplier has about 350 gates, the adder has about 60 gates, and the 4-bit register has 16 gates. Therefore, the circuit scale per digit is 80 + 120 + 350 = 550
Become a gate.

If the gate accommodating capacity per LSI chip is about 40,000, the number of multiplication processing digits in one chip will be 64 or more. This corresponds to 256-bit multiplication. The present invention relates to such an LSI
Chips can be connected and used for higher digit multiplication processing.

FIG. 4 is an explanatory diagram of an inter-unit connection method when performing high-digit multiplication using a plurality of multiplication units (LSI chips). Even if only 64 digits are accepted per unit, if 8 units are connected (units 401, 402, ..., 408),
512 digit multiplication is expected. For that purpose, first, the multiplicand code 440 is divided into 64 digits, and sequentially stored from the lower digit unit 401 to the upper digit unit 402 and further toward the upper digit unit 408. To do this, each unit 401-408
To the multiplicand load mode and set the clock signal generator 430
Is used to selectively apply 64 clock signals CLK ₁ in order from the lower digit unit to the upper digit unit.

Next, between the units, the lower n-bit output terminal 185 of the least significant digit partial product register 160 of the upper digit unit is connected to the upper n bit input terminal 180 of the most significant digit partial product register 160 of the lower digit unit. Connecting. Therefore, the bottom digit unit 401
The output terminal 185 of the lower n bits of the least significant digit partial product of is connected to the overall multiplication result extraction terminal 420. In addition, the upper n of the most significant digit partial product register 160 of the most significant digit unit 408
Since the bit does not have a shift signal from the upper digit, a value of 0 may be given to the terminal 180 of the unit 408.

After that, the multiplier 450 is supplied to the data input terminals 125 of all the units sequentially from the lower digit. From the clock signal generator 430, clock signals CLK ₁ and CLK ₂ are simultaneously supplied to all units. Accordingly, the product (partial product) of the multiplier code on the input bus 120 and the multiplicand code held in the register 110 is calculated all at once in all the digits of all units.

The calculation result of the partial product in each unit is 40
From the partial product register 8 of 8 to the partial product register 160 of the lower digit unit 401 through the partial product register 160 of the units 407, 406, ...
The partial calculation results are integrated one after another, and the comprehensive high-digit multiplication result 460 is sequentially output from the lower digit through the terminal 420.

In such a serial combination of multiple multiplication units, binary code multiplication of 64 digits per unit can be performed, and multiplication of 512 digits can be performed by concatenation of 8 units. However, the calculation time increases as the number of digits increases. Even if the calculation time at each digit is 10 nsec, the time to output the 64-digit multiplication result is 0.64
It becomes μsec. When 8 chips are connected, the multiplication time of 512 digits is 5.12 μsec. Quite long, but much shorter than software handles.

FIG. 5 is a block diagram of an embodiment of a high digit multiplication apparatus using exponential conversion. Before entering the detailed description of this figure, the multiplication method by the exponential conversion method will be described. The exponential conversion method of multiplication is similar to the rule of thumb rule.

Before calculating the product C of A and B, A mod (p) = ra (4) B mod (p) = rb (5) By this calculation, a table for converting A and B into a and b is created in advance. At the same time, create an inverse conversion table. At this time, since A × B mod (p) = ra ⁺ b (6), the result of addition of a + b is A in the inverse conversion table.
The product of × B can be obtained. Here, the inverse conversion table can be easily created when p = 257 and r = 10.

Therefore, when the n-bit code of the multiplicand and the n-bit code of the multiplier for creating the partial product of each digit in FIG. 3 are converted into n-bit exponent codes by the exponent conversion table and input, the multiplication circuit is not used. High-order multiplication can be executed only with the adder. Of course, conversion table memory must be used for exponential conversion and inverse conversion.

Returning to FIG. 5, the high digit multiplication device will be described. The difference from FIG. 1 is that an exponent conversion table memory 505 is added in the preceding stage of the input bus 120 and that the exponent code register 510 of the multiplicand is used instead of the n-bit multiplicand register 110.
Is used, the addition circuit 530 is used instead of the multiplication circuit 130, and the inverse exponent conversion table memory 520 is inserted after that.

If exponential conversion is performed, the adder circuit can be used instead of the multiplying circuit, so the delay time in the multiplying circuit is shortened, but the total calculation time cannot be shortened unless the inverse exponential conversion table memory 520 is high speed. Therefore, the fixed memory matrix of the gate array is used as the conversion table memory. Since the addition circuit is sufficiently smaller than the multiplication circuit, the hardware size is expected to be smaller than that shown in FIG.

The exponential conversion is n considering the size of the conversion table memory.
= 4 is appropriate. In the case of 4 bits, 16 code conversions are enough, so the conversion table is realized by a memory of 16 × 4 = 64 bits. Since it is fixed, it can be realized with 128 gates or less. The inverse conversion table can also be made small.

The hardware amounts of the high digit multiplication devices shown in FIGS. 1 and 5 are compared. In the embodiment shown in FIG. 1, the 4-bit multiplication circuit has about 35
Compared with 0 gates and about 60 adders, the embodiment of FIG. 5 uses an adder of 60 gates and an inverse conversion table of 128 gates, so that 410 gates are reduced to 188 gates. . Since there is only one exponential conversion table memory for the multiplier and the multiplicand, it can be ignored in the multiplication unit of 40,000 gates. Therefore, the circuit size per digit is 328 gates, which is 222 gates less than 550 gates.
Assuming that the same number of gates are used, the LSI in FIG.
64 digits per chip will increase to 108 digits. This corresponds to an increase in integration of about 1.7 times.

Next, the processing times are compared. The conversion time in the exponential conversion table can be 2nsec or less when using fixed memory. The addition of 4 bits is also about 2nsec. Since there are two conversions and two sequential additions, 8 nsec is required for calculation. Considering the set time in the partial product register,
After all, it does not fall below 10 nsec. This value is not much different from that in Fig. 1, but if the multiplier circuit in Fig. 1 uses the Booth method for 64-digit 4-bit code multiplication, the total calculation time per digit in Fig. 1 is 15 nsec. Because it will be close,
It can be said that FIG. 5 is faster.

It was explained that the high-order multiplication of the exponential conversion method is somewhat improved in terms of hardware size and processing speed compared to the case where exponential conversion is not used, but this is not the result of detailed circuit design and improvements. And I can't say which one is better. However, in the era of VLSI, where the scale of the gate array becomes large, it has been shown that the LSI chip can sufficiently multiply 128 digits or more.

〔The invention's effect〕

As described above, according to the present invention, the number of digits when sequentially performing multiplication of high-order numeric values without using floating-point arithmetic using a 16-bit or 32-bit multiplication processor and software is increased. It can be seen that the problem that the calculation time increases in proportion to the square of the number of digits can be easily solved as it increases.

When the bit width of the multiplication processor is set to 32 bits or more, it is difficult to design the wareware due to the limitation of the number of terminals and the bus width and the limitation of the circuit scale. Expected to have merit.

The first advantage is that even if the number of digits in the multiplier increases, the calculation result is only output sequentially from the lower digit over the period of serial input, which increases the execution time.
High-order multiplication can be performed simply by inputting it to the hardware that can be converted.

The second merit is that the circuit structure of the repeating structure of the 4-bit or 8-bit partial product arithmetic circuit can be realized in a small size even if there are about 100 partial product circuits and the LSI can be easily realized. is there.

A third advantage is achieved by simply connecting the multiplication units serially when increasing the digit of the multiplicand.

The fourth merit is that the multiplication per digit is processed by the clock of 100 MHz because the circuit configuration is simple.

Here, the multiplication time of 512 digits is
It was estimated to be 5.12 μsec, but it was assumed that the memory for storing the multiplier could supply the multiplier code (4 bit unit) with a cycle time of 10 nsec. In a 32-bit multiplication processor, if 512-bit multiplications and multiplicands are supplied in 16-bit divisions of 32 bits each, about 256 partial product calculations are required.

It is necessary to store and read the intermediate calculation results in the memory each time a partial product is calculated. The calculation time for each partial product is 10 nsec.
It is necessary to estimate twice. Therefore, 256 × 30nsec = 7.6μse
c time is used in the partial product operation. About 5 more 16 additions
It also needs to be repeated 12 times. 32-bit addition 5nsec
Then, 80 × 512nsec = 40μsec is added. 47.6 in total
It becomes μsec. Comparing this, the calculation time of 5.12 μsec in the high-order multiplication apparatus of the 8-unit connection according to the present invention is quite good. From this, it is expected that the present invention can bring about high-speed multiplication of about one digit for high-digit multiplication.

[Brief description of drawings]

FIG. 1 is an explanatory diagram of a circuit configuration of an embodiment of a high digit multiplication apparatus of the present invention, FIG. 2 is an operation waveform diagram of each part in the circuit of FIG. 1, FIG. 3 is an explanatory diagram of a high digit multiplication system, FIG. 4 is an explanatory diagram of a method of connecting high-digit multiplication units, and FIG. 5 is a diagram showing an embodiment of a high-digit multiplication device using an exponential conversion method. 110 ... n-bit multiplicand register 120 ... input bus 125 ... data input terminal 130 ... n-bit multiplication circuit 140 ... shift register 150 ... first adder 160 ... partial product register 170 ... second Adder 180 …… Partial product input terminal 185 …… Partial product output terminal 190 …… Clock signal CLK ₁ input terminal 195 …… Clock signal CLK ₂ input terminal 300,401 to 408 …… Multiplying unit 310 …… Multiplicand 320… … Multiplier 330 …… Partial product 340 …… Sum of partial products 410 …… Input terminal 420 …… Output terminal 430 …… Clock signal generator 440 …… High digit multiplicand 450 …… High digit multiplier 460 …… Multiply result 505… … Exponential conversion table memory 510 …… Multiplicand exponent code register 520 …… Inverse exponential conversion table memory 530 …… Exponent adder

Claims (3)

[Claims] 1. A high-digit multiplication device comprising a plurality of m-digit multiplication units, wherein each m-digit multiplication unit has a register for m digits of a multiplicand of n bits of each digit and a clock of a multiplier of n bits of each digit. An input bus for inputting in synchronization with a signal, an n-bit multiplication circuit for multiplying each digit multiplier by a multiplicand of each digit held in a register, and multiplication of an i-th (i is a positive integer less than or equal to m) digit A first adder that adds the contents of the carry register to the output of the circuit, a partial product register that stores the output (2n bits) of the first adder in upper and lower n bits, and an i-th partial product register A second adder for adding the upper n bits of the lower n bits of the partial product register of the (i + 1) th digit and a carry register for temporarily storing the output of the second adder. First half of input clock cycle of digit n-bit code , To all digits simultaneously, a first clock signal line for setting the output of the first adder to the partial product register,
A high-digit multiplication device, characterized in that a second clock signal line for setting the output of the second adder to the carry register is provided in the latter half. 2. A plurality of m-digit multiplication units connected to each other,
A high-digit multiplication device including one exponential conversion circuit,
Each m-digit multiplication unit stores an m-digit register for storing the exponent code of the multiplicand of each digit n bits after exponential conversion, and an input that gives the exponent code of the multiplier of each digit n bits after exponent conversion in synchronization with the clock signal. A bus, an adder circuit for adding the exponent code of each digit multiplier and the exponent code of the multiplicand of each digit held in the register, an inverse exponential conversion circuit connected to the adder circuit, and the i-th (i is m or less) Positive adder) to add the contents of the carry register to the output of the inverse exponent converter circuit and the output of the first adder (2n bits) divided into upper and lower n bits and stored. A product register and a second adder that adds the upper n bits of the i-th partial product register to the lower n bits of the (i + 1) th digit partial product register;
A high-digit multiplication device comprising: a carry register for temporarily storing the output of the second adder. 3. A first clock signal line for setting the output of the first adder to the partial product register all at once in the first half of the input clock cycle of each digit n-bit code of multiplication, and in the second half. And a second clock signal line for setting the output of the second adder to the carry register.