JP2664750B2 - Arithmetic device and arithmetic processing method - Google Patents

Description

Description: Object of the Invention (Industrial application field) The present invention relates to an arithmetic unit and an arithmetic processing method for performing division using a subtraction shift type division algorithm, and in particular, to signed divisors and divisors. The present invention relates to an arithmetic processing device and an arithmetic processing method capable of performing calculations.

(Prior Art) Conventionally, an operation shift type algorithm has been known as an operation processing method capable of high-speed division (for example, Horikoshi “High-speed operation method of computer”, Kindai Kagakusha, 198).
0). FIG. 5 shows an example of a circuit configuration of an arithmetic unit based on this method. This arithmetic device is intended for a 32-bit dividend and a 16-bit divisor, and can calculate a 16-bit quotient and a 16-bit remainder operation result.

The dividend register 501 stores the 32-bit absolute value of the dividend as an initial value, and sequentially stores intermediate results in the course of the extension. The shifter 502 shifts the value stored in the dividend register 501 to the upper bit side by one bit and outputs it, or passes the value of the dividend register 501 as it is. On the other hand, the divisor register 503 stores the absolute value of the 16-bit divisor. The shifter 504 is stored in the divisor register 503.
The 16-bit divisor is shifted to the upper bit side by the number of bits of the difference between the number of bits of the dividend and the number of divisor bits, that is, 16 bits, and the value is fixed. The 32-bit outputs from the shifters 502 and 504 are input to the first and second ports of the subtractor 505, respectively. The subtractor 505 performs the operation of (output of shifter 502) − (output of shifter 504). At this time, a zero flag indicating that the operation result has become 0 and a signal indicating whether or not a borrow has occurred are supplied to the quotient detection circuit 506. The quotient detection circuit 506 determines a quotient bit based on these pieces of information, and stores the bit in the shift register 507 one bit at a time. The selector 508 selects one of the output of the subtracter 505 and the output of the shifter 502 based on the determined quotient bit, and stores it in the dividend register 501. In addition,
The control circuit 509 controls these units to execute repetitive operations.

Next, among the divisor procedures using the arithmetic unit configured as described above, a signed division procedure will be described in particular.

First, the dividend is read from a memory (not shown), and its absolute value is obtained and stored in the dividend register 501.

Next, the divisor is similarly read from the memory, and its absolute value is obtained and stored in the divisor register 503.

The absolute value (16 bits) of the divisor stored in the divisor register 503 is shifted to the upper 16 bits by the shifter 504, and the shifted value is subtracted from the absolute value of the dividend stored in the dividend register 501.

If the result of this operation is 0 or more, the quotient to be obtained becomes 17 bits or more, so that an overflow occurs. Therefore, when the zero flag is set from the subtractor 505 and when no borrow occurs, the operation is stopped at this point as an overflow.

The value stored in the dividend register 501 is shifted to the upper side by one bit by a shifter 502, applied to one input port of a subtractor 505, and a value obtained by shifting a 16-bit divisor output from the shifter 504 is subtracted from the value. I do. When the subtraction result of the subtracter 505 is 0 or no borrow occurs, the quotient bit is set to 1; when the subtraction of the subtractor 505 generates a borrow, the quotient bit is set to 0. The calculated quotient bit is shifted into the least significant bit of shift register 507. When the quotient bit = 1, the selector 508 uses the subtractor 505
Is selected and stored in the dividend register 501.
When the quotient bit = 0, the output of the shifter 502 is selected by the selector 508 and stored in the dividend register 501.

The above process is repeated 16 times. As a result, a 16-bit quotient is obtained in the shift register 507, and a 16-bit remainder is obtained in the upper 16 bits of the dividend register 501.

Since the quotient is obtained in the absolute value format, the sign is corrected according to the signs of the dividend and the divisor. If the codes are inconsistent as a result of the correction, it is determined that an overflow has occurred.

Similarly, since the remainder is obtained in the absolute value format, the sign is corrected according to the signs of the dividend and the divisor.

By the way, the total number of clocks required for the above division processing is
It looks like this:

The total number of clocks = the number of clocks required for the repetition processing × the number of repetitions + the number of clocks required for obtaining the absolute value × 2 + the number of clocks required for correcting the sign × 2 Here, if the shift processing in the repetition processing is ALU
If it is performed by the (arithmetic logic operation unit), the number of clocks required for repetition is 3 to 4 clocks, and most of the total number of processing clocks is occupied by the number of clocks for this repetition processing. However, in the above-described circuit, since the shift processing in the repetition is implemented by hardware,
The number of clocks required for one repetition can be reduced to one clock, and the repetition processing can be sped up.

However, in the conventional method, in addition to the above-mentioned repetition processing at the time of signed division, the necessary repetition processing is started after obtaining the absolute values of the dividend and divisor, and finally the quotient and the remainder are obtained. Even if the number of clocks required for one repetitive operation is reduced by hardware such as shift processing for speeding up division as described above, these overheads (dead time) exist. There is a problem that the total number of processing clocks cannot be reduced as expected due to the time spent on overhead. For this reason, conventionally, it was not possible to achieve a sufficient speed increase corresponding to the hardware investment.

Therefore, in order to speed up the division, it is important not only to reduce the time required for the repetitive operation but also to reduce these overheads.

(Problems to be Solved by the Invention) As described above, in the conventional operation method using the subtraction shift type algorithm, it takes time to convert the dividend and the divisor into absolute values and to perform the sign correction processing of the obtained quotient and remainder. There has been a problem that speeding up of the division process is hindered.

The present invention has been made in view of the above problems, and has an arithmetic device and an arithmetic processing method capable of reducing not only the time required for the repetitive operation but also the overhead of pre-processing and post-processing thereof and achieving a sufficient speed improvement. The aim is to provide a method.

[Means for Solving the Problems] The present invention relates to an arithmetic processing method for obtaining a quotient and a remainder between a signed dividend and a signed divisor using a subtraction shift type division algorithm. Without calculating the absolute value of, the dividend and divisor are given as they are as the input values of the arithmetic processing, and if the sign bits of the dividend and divisor are the same, the subtraction is repeated, and if they are different, the operation is repeated by repeating the addition. It is characterized by.

That is, in the present invention, a value obtained by shifting the divisor to the higher-order bits by the number of bits of the difference between the number of bits of the dividend and the number of bits of the divisor, using the dividend or an intermediate result of the operation as a first input value. Is the second input value, and when the dividend and the divisor have the same sign, subtraction is performed between the first input value and the second input value, and the dividend and the divisor have different signs. , The addition between the first input value and the second input value is performed, at least whether the subtraction or addition result is 0, whether a carry or a borrow occurs, and the dividend The step of determining the quotient bit based on the sign of is repeated a predetermined number of times. In this iterative process, the dividend is given as an initial value of the first input value, and when the determined quotient bit is the first value, the operation result is shifted to the upper bit side by one bit. Is given as the first input value, and when the determined quotient bit is the second value, the first input value is set to 1
Give the value shifted to the higher bit side of the bit.

(Operation) According to the present invention, since the absolute values of the dividend and the divisor are not determined, but are used as they are in the arithmetic processing, the operation of determining the absolute values of the dividend and the divisor as the repetitive preprocessing can be omitted. Further, according to the present invention, since the arithmetic processing is performed with a sign, the remainder is also obtained with a sign, and the procedure for this sign correction can be omitted. As described above, according to the present invention, the overhead of the pre-processing and post-processing of the repetitive operation can be significantly reduced, so that the advantages of hardware can be fully utilized,
The speed of the division process can be greatly increased.

Hereinafter, preferred embodiments of the present invention will be described with reference to the drawings.

FIG. 1 is a diagram showing a configuration of an arithmetic unit according to one embodiment of the present invention.

In addition, this arithmetic unit has a dividend
It targets 32-bit and 16-bit divisor operations.
It is assumed that a calculation result of 16 bits and a remainder of 16 bits can be calculated.

The dividend register 101 stores a 32-bit dividend as an initial value, and sequentially stores intermediate results in the course of the operation. In the case of signed division, the dividend to be stored is stored as signed. The sign bit of the dividend is stored in the sign bit register 102. Shifter 103 is dividend register
The value stored in 101 is shifted to the upper bit by one bit and output, or the value of dividend register 101 is passed as it is. On the other hand, the divisor register 104 stores a 16-bit divisor. Like the dividend, the stored divisor is stored with a sign in the case of signed division. The sign bit of the divisor is stored in the sign bit register 105. The shifter 106 shifts the 16-bit divisor stored in the divisor register 104 by the number of bits of the difference between the number of bits of the dividend and the number of bits of the divisor, that is, by 16 bits, and fixes the value. The complementer 107 converts the output of the shifter 106 into a complement when the dividend and the divisor have the same sign, and passes the output of the shifter 106 as it is when the dividend and the divisor have different signs. Shifter 103
And the 32-bit output from the complementer 107 are input to the first and second ports of the adder 108, respectively. Adder 108 performs an operation of (output of shifter 103) + (output of complementer 107). At this time, a zero flag indicating that the addition result has become 0, and a signal indicating whether or not a carry has occurred are:
The quotient determination circuit 109 is provided. Further, the quotient determination circuit 109 is also provided with each sign bit from the sign bit registers 102 and 105 and the overflow output of the shifter 103. The quotient determination circuit 109 determines a quotient bit based on the information,
It is shifted into the shift register 110 one bit at a time. Further, the quotient determination circuit 109 is provided with an ALZERO flag 120 which becomes 1 when the addition result becomes 0. The selector 111 selects the adder 1 based on the determined quotient bit.
Select either the output of 08 or the output of shifter 103,
It is stored in the dividend register 101. Further, the control circuit 112
These parts are controlled to execute the repetitive operation. In addition,
Although not shown, in an actual circuit, an internal bus, a path between registers, a general-purpose register file, and the like are additionally provided as appropriate.

Next, the processing procedure of the arithmetic unit shown in FIG. 1 configured as described above will be described with reference to the flowchart (PAD diagram) of FIG.

FIG. 2A shows the main flow. First,
The ALZERO flag 120 is initialized to 0. This arithmetic unit can perform either signed division or unsigned division. Then, it is next determined whether or not the operation is a signed operation. If the operation is a signed operation, the signs of the dividend and the divisor are stored in the sign bit registers 102 and 105, respectively. Subsequently, the operation 1 for checking the overflow is executed.

FIG. 2 (b) is a diagram showing a processing procedure of the operation 1 for the overflow check. First, the dividend register 10
The 32-bit dividend stored in 1 is added to the first
Give to the port. Next, the values of the sign bit registers 102 and 105 are referred to. If the dividend and the divisor have the same sign, the shifter 1 stores the 16-bit divisor stored in the divisor register 104.
06 shifts 16 bits to the upper bit side and complements
After being complemented by 107, it is provided to a second port of adder 108. If the dividend and the divisor have different signs, the 16-bit divisor stored in the divisor register 104 is shifted by the shifter 106 to the higher-order bit by 16 bits and passed through the complementer 107 as it is. Second
Given to the port. Then, the adder 108 performs the addition. This relationship will be described with reference to FIG. In this device, subtraction is performed when the dividend and the divisor have the same sign as shown in FIGS. A and d, and addition is repeated when the dividend and the divisor have different signs as shown in FIGS. Absolute value subtraction is performed. In this embodiment, an adder 10 is used as arithmetic means.
Since 8 is used, the divisor is complemented so that subtraction can be performed using an adder in the former case. As a result of this operation, when the quotient bit = 1, the quotient is determined to be an overflow of 17 bits or more, and the process ends. The quotient bit is determined based on the following criteria. This criterion is applied not only to Operation 1 but also to Operation 2 described later.

When the operation result is 0: quotient bit = 1 For signed division: quotient bit = sign of dividend. EXOR. Carry For unsigned division: quotient bit = overflow of shifter 103. OR. Carry In the above, the dividend is exactly the divisor It means broken octopus.
Also, with reference to FIG. 3, in order for the quotient bit = 1, it is necessary that | dividend |> | divisor |. Assuming that the sign of the dividend is positive (0), a carry occurs when the dividend> | divisor |, which should satisfy quotient bit = 1, is satisfied. For this reason, as shown in FIG.
When the sign of the dividend = 0, carry = 1 and quotient bit =
1, quotient bit of carry = 0 = 0. Assuming that the sign of the dividend is negative (1), no carry occurs when | dividend |> | divisor | where the quotient bit should be 1. Therefore, as shown in FIG. 3, when the sign of the dividend = 1, the quotient bit = 1 when carry = 0 and the quotient bit = 0 when carry = 1. In the overflow check, since the shift operation of the shifter 103 has not been performed yet, there is no overflow of the shifter. Therefore, in the case of unsigned division in operation 1, only carry is referred to.

When the operation 1 is completed, the operation 2 is repeated. This process is shown in FIG. In this operation 2,
The value of the dividend register 101 shifted to the upper bit side by one bit by the shifter 103 and the value of the divisor register 104 are
In step 06, a value which is shifted to the upper bit by 16 bits and selectively complemented is supplied to the input port of the adder 108, the addition is executed, and the quotient bit is determined based on the reference shown in the operation 1. The determined quotient bit is shifted into the least significant bit of the shift register 110. When the quotient bit = 1, the addition result of the adder 108 is selected by the selector 111 and the dividend register
Store in 101. When the quotient bit = 0, the selector 111
Select the output of the shifter 103 and store it in the dividend register 101.

The above criterion is applied only when ALZERO = 0. If the calculation result becomes 0, ALZERO = 1 is set. Thus, the quotient bit is always set to 0 in the subsequent repetitive operations. By using the ALZERO flag 120, it is possible to prevent the wrong quotient bit from being output based on the above-described criterion when the dividend is negative.

By repeating this operation 2 16 times, a 16-bit quotient is sequentially obtained in the shift register 110, and a 16-bit remainder is obtained in the upper 16 bits of the dividend register 101. At this time, the obtained quotient is represented by an absolute value, but the remainder is represented by a sign because the dividend is used for the operation with the sign. For this reason, the remainder sign correction processing can be omitted.

When the operation 2 is completed, as shown in FIG. 2 (a), in the case of signed division, reference is made to the code bits stored in the sign bit registers 102 and 105, and if the dividend and the divisor have different signs, Performs sign inversion processing of the quotient obtained by the absolute value. Finally, check whether the sign of the dividend, the sign of the divisor, and the sign of the obtained quotient are consistent.If there is a conflict, it is determined that an overflow has occurred.If there is no conflict, the correct operation result is determined. A series of processing ends.

As described above, according to the present embodiment, the signed dividend and the divisor are handled as they are, and the arithmetic unit including the complementer 107 and the adder 108 is used to perform subtraction when the dividend and the divisor have the same sign. If the signs are different, addition is performed, so that the pre-processing of the repetitive operation can be omitted. In addition, since the obtained remainder is signed, post-processing of sign correction of the remainder can be omitted. In addition, the repetitive arithmetic processing can be performed by fully utilizing the merit of speeding up by hardware as in the related art. As a result, it is possible to speed up the overall processing corresponding to the hardware.

The present invention is not limited to the embodiments described above. In the above-described embodiment, the complementer 107 and the adder 108 are used as the calculation means. However, for example, a complementer and a subtractor may be used. In this case, as shown in FIG. 4, for example, the divisor is complemented only when the dividend and the divisor have opposite signs. In the case of signed division, the quotient bit = 〜 (sign of dividend.EXOR. Borrow) However, the quotient bit may be determined based on the criterion of ~: negation.

[Effects of the Invention] As described above, according to the present invention, the absolute values of the dividend and divisor of signed division are not obtained, and if both have the same sign, subtraction is performed, and if they have different signs, addition is performed. Is performed, the overhead required before and after the repetitive operation, which was conventionally required, is reduced, and the speed can be increased in proportion to the amount of hardware.

[Brief description of the drawings]

FIG. 1 is a block diagram of an arithmetic unit based on a subtraction shift type algorithm according to one embodiment of the present invention, FIG. 2 is a flowchart of the processing of the arithmetic unit, FIG. FIG. 4 is a diagram showing a quotient bit criterion according to another embodiment of the present invention, and FIG. 5 is a block diagram of an arithmetic unit based on a conventional subtraction shift type algorithm. 101,501… Divided register, 102,105… Sign bit register, 103,106,502,504… Shifter, 104,503… Divisor register, 107… Complementer, 108… Adder, 109… Division decision circuit, 110,507… Shift register, 111,508 ... selector, 112,509 ... control circuit, 505 ... subtractor, 506 ...
... Square detection circuit.

Claims (2)

(57) [Claims] 1. A dividend storage means for sequentially storing a dividend and a numerical value of an intermediate result of an operation; a first sign bit storage means for storing a code bit of the dividend; and a value stored in the dividend storage means being 1 A first shift unit that shifts to a higher bit side, a divisor storage unit that stores a divisor, a second code bit storage unit that stores code bits of the divisor, and a divisor stored in the divisor storage unit. The second shift means for shifting to the upper bits by the number of bits of the difference between the number of bits of the divisor and the number of bits of the dividend is the same as the value stored in the first and second sign bit storage means. In this case, an operation between the output of the first shift means and the output of the second shift means is performed, and
And if the values stored in the second sign bit storage means are different, an operation means for performing an addition between the output of the first shift means and the output of the second shift means; Quotient determining means for determining whether the operation result of the means is 0, whether or not a carry or borrow has occurred, and determining the value of the quotient bit based on the value of the sign bit stored in the first sign bit storage means And if the quotient bit determined by the quotient determination means is the first value, select the operation result of the operation means and store it in the dividend storage means; Is a second value, selecting means for selecting the output of the first shift means and storing it in the dividend storage means; and controlling the respective means for causing the arithmetic means to execute a predetermined number of calculations. System Arithmetic apparatus characterized by comprising a means. 2. A method for calculating a quotient and a remainder between a signed dividend and a signed divisor using a subtraction shift type division algorithm, wherein the dividend or the intermediate result of the operation is used as a first input value, A value obtained by shifting the divisor toward the higher bits by the number of bits of the difference between the number of bits of the dividend and the number of bits of the divisor is used as a second input value, and when the dividend and the divisor have the same sign, A subtraction is performed between the first input value and the second input value, and when the dividend and the divisor have opposite signs, a difference between the first input value and the second input value is calculated. Performing the addition, and determining at least whether the subtraction or addition result is 0, whether or not a carry or a borrow has occurred, and the sign of the dividend; and setting the dividend to the first input value. Early When the determined quotient bit is the first value, a value obtained by shifting the operation result to the upper bit side by 1 bit is provided as the first input value, and the determined quotient bit is the second input value. And calculating the quotient and the remainder by repeating the predetermined number of times while giving a value obtained by shifting the first input value to the upper bit side by one bit.