JPH08123667A - High speed division circuit - Google Patents

Abstract

(57) [Abstract] [Purpose] A high-speed division circuit in a vector processor that inputs valid data in consecutive cycles reduces the processing time and raises the operating frequency. [Structure] Two sets of dividend and divisor are input in consecutive cycles, division is performed by two-cycle processing, one group of data is divided in the first cycle, and the other cycle is divided in the second cycle. Processing other than the addition / subtraction processing of the set is performed.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a high speed division circuit, and more particularly to a high speed division circuit of a vector processor for inputting valid data in consecutive cycles.

In order to perform division (division), which is one of the four arithmetic operations, by a computer, it is impossible to perform division as it is, and it is usual to obtain it by repeatedly subtracting the divisor from the dividend.

This will be explained with reference to FIG. 11. First, in the example shown in FIG. 1A, when the decimal number "30" is divided by "4", the two's complement value "1100" of the divisor "4" is calculated. Seeking,
This is the top 4 of the binary number "011110" of the dividend "30"
Bit "0111" (this is the same number of bits as the divisor)
By adding to, "10011" is obtained.

Of these, the most significant bit "1" is set as a partial quotient, and the four bits "0011" and the next least significant bit "1" of the dividend are added as the least significant bits of the addition value. In addition to the divisor “0100”, the two's complement value “1100”
Is added.

In this way, subtraction is performed until all the bits of the dividend are added (addition by the complement of 2), and the partial quotient at each stage is the final quotient "111" = 1.
The decimal residue is “7”, and the final partial remainder is the final residue “0010” = decimal number “2”. That is, as a result of this division, the quotient is 7 and the remainder is 2.

Further, in the case of the example shown in FIG. 2B, there is a step in which the partial quotient is not always “1” as in the example of FIG. Is 0, the divisor is added without subtraction (addition by 2's complement) in the next stage.

In this way, in this example, the quotient is "1001".
And the final partial remainder becomes “0000”, so 10
In radix, the quotient is "9" and the remainder is "0".

In this way, although the division takes a long processing time, it is necessary to perform the above subtraction processing as quickly as possible in the vector processor in which the dividend and the divisor are input in a continuous cycle.

[0009]

2. Description of the Related Art FIG. 12 shows a conventional division circuit in a vector processor. The divisor and dividend are shown in FIG.
Operand OP as shown in the time chart in
1 is held by the enable signal from the enable signal generating circuit (g) in the divisor register (a) and the dividend register (d), respectively.

In the control circuit (i), the two's complement is first generated and given to the adder (k) as shown in FIG. 11, and in the control circuit (j), the dividend register (d) is first generated. The dividend data held in () (however, the data having the same number of bits as the divisor) is sent to the adder (k) as it is.

In the adder (k), the output data of the control circuits (i) and (j) are added, the result is once post-processed by the arithmetic processing circuit (l), and then as shown in FIG. The partial quotient data is sent to the commercial shift register (o), and the partial remainder data is sent to the partial remainder register (t).

The adder (k) also supplies the partial quotient data as control data to the control register (n) through the arithmetic processing circuit (l).

In this way, the data 1-1 is simultaneously stored in the control register (n), the commercial shift register (o) and the partial remainder register (t) at the clock cycle "2" as shown in FIG. The Rukoto.

In the next clock cycle, the control circuit (i) performs subtraction when the control data is positive as shown in FIG. 11 based on the control data from the control register (n). A two's complement of the divisor data from the divisor register (a) is generated and given to the adder (k). Further, when the control data is negative, the divisor data from the divisor register (a) is given to the adder (k) as it is for addition.

In the control circuit (j), the partial remainder from the partial remainder register (t) has the same number of bits of data as the divisor data extracted in the previous clock cycle of the dividend data from the dividend register (d). The next lower 1-bit data is fetched, and one dividend data combined with the partial remainder data from the partial remainder register (d) is sent to the adder (k).

The adder (k) sends the partial quotient and the partial remainder data to the registers (o) and (t) via the register (l), respectively, and gives control data to the control register (n). Data 1-2 as shown in FIG. 13 is sent to each register in the clock cycle “3”.
Will be stored at the same time.

Thus, in the example shown in FIG. 13, for example, in the example shown in FIG. 13, the final quotient and remainder for one operand OP1 are output through the operation steps shown in FIG.

[0018]

In such a conventional division circuit, when a plurality of operands for division are input, as shown in FIG. 15, one operand OP1 is input. After 5 clock cycles, the final quotient and the remainder for it are output, and starting from that, the final quotient and the remainder for the next operand OP2 are the next 5
It will be required after a clock cycle.

Therefore, in the case where data is continuously input like a vector processor, each input operand must be made to wait, resulting in a long processing time and a problem in increasing the operating frequency. It was.

Therefore, an object of the present invention is to shorten the processing time and increase the operating frequency in a high speed division circuit in a vector processor which inputs valid data in consecutive cycles.

[0021]

[Means and Actions for Solving the Problems]

[1] In order to achieve the above object, the high-speed division circuit according to the present invention, as shown in principle in FIG. 1, stores a divisor register ( a), a divisor temporary register (b) for storing data of the second set of divisors, and data of the divisor register (a) or the divisor temporary register (b) output from the first data selection circuit (h) A divisor selector (c) that selects and outputs the signals alternately, a dividend register (d) that stores the first set of data of the dividend input in consecutive cycles, and a data of the second set of dividends. A dividend temporary register (e) and a first register for generating an enable signal for storing data in each register (a to e)
Of the enable signal generation circuit (g) and the dividend register (d) or the dividend temporary register (e) are alternately selected by the output signal of the first data selection circuit (h) and output. (F) and a first control circuit (i) that outputs the data of the divisor selector (c) as a two's complement value or a value as it is according to the control data indicating whether the addition result is positive or negative, and only for the first time The data of the dividend selector (f) is selected, and thereafter, the most significant bit of the remaining data of the dividend selector (f) is used as the least significant bit, and the partial remainder data of the addition result is shifted by one bit to the upper bit. The second control circuit (j) which outputs one data and the output data of both control circuits (i, j) are input and the addition processing of the first set and the second set is alternately performed to perform the control. Day And the partial quotient data and the partial remainder data are output, an arithmetic processing result register (l) that holds the output data of the adder (k), and the register (l) are output. To store data in the first and second commercial shift registers (o, p) that store partial quotient data for the first and second sets of dividend and divisor, respectively, and both commercial shift registers (o, p) Second enable signal generation circuit (q) for generating the enable signal of the second data selection circuit, and when the final quotient is stored in both commercial shift registers (o, p), it is output to the outside by the output signal of the second data selection circuit. Quotient selector (r) for selecting data
A control register (n) for storing the control data and giving it to the first control circuit (i), and a partial remainder register (n) for storing the partial remainder data and giving it to the second control circuit (j). t) and.

That is, according to the present invention, since two sets of dividend and divisor are input in consecutive cycles, the divisor temporary register (b) and dividend temporary are provided in addition to the divisor register (a) and the dividend register (d). A register (e) is provided.

The divisor data and dividend data of the first set are first stored in the divisor register (a) and the dividend register (d), respectively, as shown in the time chart of FIG.
Is held by the enable signal from the enable signal generation circuit (g), and the second set of divisor data and dividend data are held in the divisor temporary register (b) and the dividend temporary register (e), respectively, as shown in FIG. It

The divisor data and dividend data of the first set and the second set are sent to the divisor selector (c) and the dividend selector (f), respectively. As shown in FIGS. The data selection circuit (h) controls so that the divisor data and the dividend data are output from the selectors (c) and (f), respectively.

The divisor data and the dividend data output from the divisor selector (c) and the dividend selector (f) are the first control circuit (i) and the second control circuit (j), respectively.
Then, the same arithmetic processing as that described with reference to FIG. 14 is performed, and the partial quotient data, the partial remainder data, and the control data are separately output from the arithmetic processing result register (l).

However, in this case, the partial quotient causes the commercial shift registers (o) and (p) to hold the data of the first set and the second set, respectively, and the data of these shift registers (o) and (p) are held. The quotient data is extracted from the quotient selector (r) controlled by the data selection circuit (s).

In this way, the first set of operands OP
The processed data 1-1 for 1 is output from the registers (t), (o), and (n), respectively, as shown in the second stage of FIG. It can be seen that the arithmetic processing is not performed as shown in the first stage.

That is, since the arithmetic processing is not performed in the cycle shown by the vertical line in FIG. 2, the processing for the second set of operand OP2 is performed using this period.

As a result, as shown in FIG. 3, the operation result for the operand OP2 is held in the portion shown by the vertical line in FIG.

Therefore, when two sets of dividend data and divisor data are input and two-cycle processing is performed as in this example, the number of cycles until the final quotient and the remainder for the operand OP1 are output is one cycle. Although it takes a lot of time, when data is continuously input like vector data, the operation performance is improved.

[2] In the above high-speed division circuit, when the dividend and the data of the divisor have the same number of bits and the partial quotient data is obtained bit by bit, the first control circuit outputs the data from the divisor selector. A used two's complement generation circuit, a subtraction selector for inputting the data from the complement generation circuit and the data from the divisor selector, and a third data selection circuit for generating a selection control signal of the subtraction selector from the control data. The second control circuit inputs a shift circuit for left-shifting the partial remainder data of the partial remainder register by 1 bit and outputting it, and output data of the dividend selector and output data of the shift circuit. And a fourth data selection circuit for generating a selection control signal of the minuend selector.

When the divisor selector subtracts the divisor from the dividend as division processing, the output data of the complement generation circuit is selected based on the output signal of the third data selection circuit, and when the divisor is added to the dividend, the output data of the complement generation circuit is selected. Select the output data of the divisor selector.

[3] In the above high-speed division circuit, when the number of bits of the data of the dividend is larger than the number of bits of the data of the divisor, the partial quotient data is obtained bit by bit,
Control circuit using the data from the divisor selector.
Complementary generation circuit, a subtraction selector for inputting the data from the complement generation circuit and the data from the divisor selector, and a third data selection circuit for generating a selection control signal for the subtraction selector from the control data. The second control circuit outputs a carry-down data selector for selecting data having the same number of bits as the divisor data from the upper side of the dividend selector, and outputting the lower 1-bit data from the data selector. The fourth data selection circuit for generating a selection control signal and the partial remainder data of the partial remainder register are set to 1
A shift circuit that shifts the output to the left by a bit, and a subdivided value selector that selects one of the output data of the dividend selector or the output data of the data selector as the least significant bit and the output data of the shift circuit as the upper bit,
Fifth for generating a selection control signal for the minuend selector
It may be configured with the data selection circuit.

Then, only when the divisor is first subtracted from the dividend as the division processing, the output data of the dividend selector is selected by the dividend selector.

[4] In the above high-speed division circuit, the first control circuit uses an inverter circuit that performs bit inversion of output data of the divisor selector instead of the complement generation circuit, and the adder performs division processing. When subtracting the divisor from the dividend, "1" is input as the carry data for the output signal of the third data selection circuit, and when adding the divisor to the dividend, the carry data may not be input.

[5] One of the above high-speed division circuits is
It can also be applied to the case where the number of bits of the data of the dividend is the same as the number of bits of the data of the divisor and the partial quotient is obtained by 4 bits using the quotient prediction method.

That is, a quotient prediction circuit which has a table and outputs a prediction quotient obtained from the relationship with the upper 5 bits of the partial remainder for each of the numbers indicated by the upper 9 bits of the data from the divisor selector from the table. A timing register for holding the output data of the quotient prediction circuit and adjusting the timing with the register, and a control register for adjusting the timing of the data of the timing register with the timing of the partial remainder from the adder, A prediction quotient detection circuit that detects the matching prediction quotient by comparing the prediction quotient from the table and the partial remainder via the control register, a prediction quotient register that stores the prediction quotient data twice, and the prediction quotient A quotient correction circuit that corrects the predicted quotient based on the sign relationship between the quotient register data and the partial remainder data, and a control signal that indicates the predicted quotient data Further comprising a control unit of the order, first
Instead of the control circuit, the shift circuit shifts the value of the divisor selector based on the predicted quotient from the control unit, the complement generation circuit that generates the two's complement of the output data of the shift circuit, and the shift circuit. A third control circuit composed of a circuit and a divisor selector that inputs output data of the complement generation circuit and selects data based on the predicted quotient may be used.

Then, as a division process, a 4-bit quotient is predicted in advance, the quotient is corrected using the predicted quotient and the partial remainder generated next, and the final quotient can be obtained by repeating this.

[0039]

FIG. 4 shows an embodiment (1) of a high-speed division circuit according to the present invention. In this embodiment, in the high-speed division circuit shown in FIG. ) Are the same and the data of the partial quotient are obtained bit by bit.

Therefore, the first control circuit (i) uses the data from the divisor selector (c) to generate a two's complement generating circuit (A), the data from the complement generating circuit (A) and the divisor selector. A subtraction selector (B) for inputting data from (c) and a third data selection circuit (C) for generating a selection control signal of the subtraction selector (B) from control data from a control register (n). I am configuring.

The second control circuit (j) shifts the partial remainder data from the partial remainder register (t) to the left by one bit and outputs it, and the output of the dividend selector (f). It is composed of a minuend selector (E) for inputting data and output data of the shift circuit (D) and a fourth data selection circuit (F) for generating a selection control signal of the minuend selector (E).

Next, referring to the time chart of FIG. 3, which shows the operation for obtaining the final quotient and the remainder in the flow of four times in this embodiment, two data sets of the dividend and the divisor are input in consecutive cycles. And will be described below.

(1) Operation in clock cycle "0": Processing of first set data = divisor and dividend (OP
1) is input. Processing of the second set of data = None.

(2) Operation in clock cycle "1": processing of first group of data (processing in first stage circuit) = divisor of first group of data at rising edge of clock cycle "1", dividend register (a, Store in d). The enable signal for storing is generated by the enable signal generation circuit (g).

The data input from the dividend register (d) to the dividend selector (f) and the data input from the divisor register (a) to the divisor selector (c) are selected by the selection signal generated by the data selection circuit (h). To be selected.

The data inputted from the dividend selector (f) to the dividend selector (E) is selected as it is by using the selection signal generated by the data selection circuit (C), and the data output from the divisor selector (c) is The 2's complement generation circuit (A) generates a 2's complement value of the divisor and the data input to the subtraction selector (B) is selected by the selection signal generated by the data selection circuit (C).

In this way, the data selected by the minuend selector (E) and the subtrahend selector (B) are input to the adder (k) and operated.

Processing of second set data = divisor and dividend (OP2) are input from the outside.

(3) Operation in clock cycle "2": processing of the first set of data (processing in the second stage circuit) = calculation result register of the processing result of the adder (k) at the rising edge of clock cycle "2" Store in (l). The sign, quotient, and partial remainder are separated from the operation result.

Processing of the second set of data (processing in the first stage circuit) = The data of the second set is divided by the rising edge of the clock cycle "2", and the divisor and dividend temporary registers (b,
Store in e). The enable signal for storing is generated by the enable signal generation circuit (g).

The data input from the dividend temporary register (e) to the dividend selector (f) and the data input from the divisor temporary register (b) to the divisor selector (c) are selected by the data selection circuit (h). Selected by signal.

The data input from the dividend selector (f) to the dividend selector (E) is selected as it is by using the selection signal generated by the data selection circuit (F), and the data output from the divisor selector (c) is The 2's complement generation circuit (A) generates a 2's complement value of the divisor and the data input to the subtraction selector (B) is selected by the selection signal generated by the data selection circuit (C).

In this way, the data selected by the minuend selector (E) and the subtrahend selector (B) are input to the adder (k) to be calculated.

(4) Operation in clock cycle "3": Processing of first set of data (processing in first stage circuit) = sign, quotient obtained in clock cycle "2" at the rising edge of clock cycle "3", The partial remainder is stored in the control register (n), the commercial shift register (o), and the partial remainder register (t). However, in the commercial shift register (o), the enable signal generated by the enable signal generation circuit (q) is used to continuously store for two cycles.

Then, in the shift circuit (D), the value of the partial remainder register (t) is shifted to the left by 1 bit and output, and this value is selected by the minuend selector (E), and is controlled by the subtraction selector (B). By using the value of the register (n) as a selection control signal, the value of the divisor selector (c) is selected when the divisor is added to the dividend, and the value of the divisor selector (c) is complemented by 2 when the divisor is subtracted from the dividend. Select a numerical value and input it to the adder (k).

Processing of the second set of data (processing in the second stage circuit) = At the rising edge of the clock cycle "3", the processing result of the adder (k) is stored in the arithmetic processing result register (l). The sign, quotient, and partial remainder are separated from the operation result.

(5) Operation in clock cycle "4": Processing of first set of data (processing in second stage circuit) Same as operation in clock cycle "4". Processing of the second set of data (processing in the first-stage circuit) = At the rise of the clock cycle “4”, the code, quotient, and partial remainder obtained in the clock cycle “3” are stored in the control register (n) and the commercial shift register (p). ), And the partial remainder register (t). However, in the commercial shift register (p), the enable signal generated by the enable signal generation circuit (q) is used to store it continuously for two cycles.

Then, in the shift circuit (D), the value of the partial remainder register (t) is shifted to the left by one bit and output, and this value is selected by the minuend selector (E) and controlled by the subtractor selector (B). By using the value of the register (n) as a selection control signal, the value of the divisor selector (c) is selected when the divisor is added to the dividend, and the value of the divisor selector (c) is complemented by 2 when the divisor is subtracted from the dividend. Select a numerical value and input it to the adder (k).

Thereafter, the operations of the clock cycles "3" and "4" are repeatedly performed alternately, the operation result for the first set of data is output in the clock cycle "9", and the two sets are output in the clock cycle "10". The calculation result for the eye data is output.

FIG. 5 shows the configuration of an embodiment (2) of the high speed division circuit according to the present invention. In this embodiment,
As in the case of the above embodiment (1), when the data of the dividend and the divisor have the same number of bits and the data of the partial quotient are obtained bit by bit, instead of the complement generation circuit (A) of the first control circuit (i) When the adder (k) subtracts the divisor from the dividend as division processing, an inverter circuit (H) that bit-inverts the output data of the divisor selector (c) is used for subtraction by the selection signal from the data selection circuit (C). The selector (B) selects the data from the inverter circuit (H) and inputs "1" as carry data for the selection signal of the data selection circuit (C). Further, when a divisor is added to the dividend, the data selection circuit (C) controls the output data from the divisor selector (c) so that the subtraction selector (B) selects the carry data. .

FIG. 6 shows an embodiment (3) of the high speed division circuit according to the present invention. In this embodiment, the first control circuit (i) is the same as the embodiment (1) shown in FIG. The second control circuit (j) has the same structure as the control circuit (i), but the second control circuit (j) is a carry-down for selecting data having the same number of bits as the divisor data from the upper side of the dividend selector (f). A data selector (J), a fourth data selection circuit (K) for generating a selection signal for outputting data of lower 1 bit from the data selector (J), and partial remainder data of a partial remainder register (t). Of the shift circuit (D) that shifts to the left by 1 bit and outputs the output data of the dividend selector (f) or the output data of the data selector (J) as the least significant bit and the output data of the shift circuit (D) as the most significant bit. One to do A minuend selector (E) to select the over motor, the selection control signal is constituted de fifth data selection circuit (F) and for generating for the minuend selector (E).

Then, the dividend selector (f) is set only when the process of subtracting the divisor from the dividend is first performed as the division process.
The data selection circuit (F) controls so that the output data of (1) is selected from the minuend selector (E).

FIG. 7 shows an embodiment (4) of the high speed division circuit according to the present invention. In this embodiment, the first control circuit (i) in the embodiment (3) shown in FIG. 6 is shown. Similar to the embodiment (2) shown in FIG. 5, the inverter circuit (H), the subtraction selector (B) and the data selection circuit (C) are different.

Therefore, the operation is a combination of the above embodiments (2) and (3).

FIG. 8 shows an embodiment (5) of the high speed division circuit according to the present invention. In this embodiment, unlike the above embodiments, the quotient prediction method is used.

Here, the quotient prediction method will be briefly described. For example, when the dividend “7543” is divided by the divisor “3”, the verification is usually performed as shown in FIG. 9 (1). In the case of the quotient prediction method, as shown in (2) of FIG.
First, "2" is set for "7" in the dividend "7543", and the dividend "15" that consists of this partial remainder and the next value "5"
Against this, the quotient "6" determined by a certain quotient forecasting method
As a result, the partial remainder becomes “−3”, so by adding the next value “4” to the partial remainder “−30”, the partial remainder becomes “−26”. Similarly, since the quotient prediction method is applied to obtain the quotient "9", the partial remainder due to this is "1", and the last quotient is added to the value "13" to which the last dividend "3" is added. By assigning "1", the partial remainder becomes "1".

At this time, depending on whether the partial remainder is positive or negative, correction is performed from the context.

That is, in the example of FIG. 2B, the quotient "2"
Is a positive value, the value "2" is used as it is without correction. The next quotient "6" is changing from positive to negative. 5 ”, since the next quotient“ 9 ”has changed from negative to positive, the two's complement“ 1 ”for this quotient“ 9 ”is adopted, and the final quotient“ 4 ”is changed from positive to positive. Therefore, the value "4" is output as it is without correction, and as a result, the quotient becomes "2514" and the final remainder becomes "1".

As described above, the quotient prediction method requires a table for predicting one quotient from the relationship between the partial upper 5 bits and the divisor upper 9 bits, and the portion obtained from such a table is used. The quotient once obtained is corrected by the change of the sign of the remainder.

From the above, in the embodiment (5) shown in FIG. 8, in the case where the number of bits of the data of the dividend is the same as the number of bits of the divisor, the partial quotient is obtained every 4 bits by using the quotient prediction method. , A quotient prediction circuit (S) for outputting a prediction quotient obtained from the relation with the upper 5 bits of the partial remainder for each of the numbers indicated by the upper 9 bits of the data from the divisor selector (c), from the table. When,
From the timing register (R) for holding the output data of the quotient prediction circuit (S) and adjusting the timing with the arithmetic processing result register (l), and the data of the timing register (R) and the adder (k) Control register (N) for matching the timing with the partial remainder of the above, and the predicted quotient from the table of the quotient prediction circuit (S) is compared with the above partial remainder via this control register (N) and they match. A predictive quotient detection circuit (U) for detecting a predictive quotient, a predictive quotient register (V) for storing the predictive quotient data twice, and a code relation between the data of the predictive quotient register (V) and the partial remainder data described above. A quotient correction circuit (W) that corrects the predicted quotient based on the above, and a control unit (X) that generates a control signal indicating the predicted quotient data are further provided.

A third control circuit (Y) is used instead of the first control circuit (i), and the third control circuit (Y) controls the value of the divisor selector (c). Department (X)
Shift circuit (L) that shifts based on the predicted quotient from
And the output data of the shift circuit (L) and the complement generation circuit (A), and the data generated on the basis of the predicted quotient. And a divisor selector (M) for selecting.

Then, as a division process, a 4-bit quotient is predicted in advance, the quotient is corrected using the predicted quotient and the partial remainder generated next, and this is repeated to obtain the final quotient.

In order to describe the operation of the embodiment (5) in detail below, the dividend data and the divisor data (hexadecimal display) as shown in the following expressions will be taken as an example.

[0074]

[Equation 1]

In the case of such data, the partial remainder given from the operation result register (l) to the control register (N) is first the dividend, so the upper 5 bits "15" (HEX) of the first partial remainder (HEX ) Is the upper 9 bits of the divisor "1A
It will be divided by 1 ”(HEX).

Therefore, the quotient prediction circuit (S) looks at the upper 9 bits of the divisor ("1A1" for the first time) and outputs all predicted quotients to the timing register (R).

The table provided in this quotient prediction circuit (S) shows the predicted quotient obtained from the relationship between the upper 9 bits of the divisor and the upper 5 bits of the partial remainder.

That is, there is only one partial remainder for a given divisor, but the partial remainder is finally determined after the subtraction processing. This is the assumption.

Therefore, in the above example, since the upper 9 bits of the divisor are "1A1", the prediction quotient is obtained for all the partial remainder 5 bits that can be combined with this. A corresponding partial remainder number is attached to the predicted quotient data and sent to the control register (N) via the timing register (R).

In the control register (N), the partial remainder data (however, the dividend is output as it is at the first time) sent from the arithmetic processing result register (l) is given to the control register (N). In the prediction quotient detection circuit (U), the partial remainder "1" from the register (l)
5 "(HEX) is used to allocate the prediction quotient" D "with the partial remainder number" 15 "in the quotient prediction circuit (S), and this prediction quotient" D "is stored in the prediction quotient register (V). At the same time, it is given to the shift circuit (L) and the multiplication factor selector (M) via the control unit (X).

Since it has been found that the prediction quotient of this control circuit (X) is "D" (HEX), it produces a control signal so that the divisor is "D times". This "D times" is It can be realized by sending it to the shift circuit (L).

On the other hand, in the adder (k), the most significant bit of the divisor is added to the upper 5 bits of the partial remainder, and addition and subtraction are performed as shown in the following equation.

[0083]

[Equation 2]

In the above equation, (1) is the divisor ×
The case where 1 times is added is shown, and (2) shows the case where divisor × 1 times is subtracted.

Therefore, the predicted quotient is "D" as described above.
Since it is obtained as (HEX), in the shift circuit (L), the divisor is multiplied by (-8) times so as to correspond to "D" = 13.
The data multiplied by (-4) times and (-1) times is added to the partial remainder. This can be expressed by the following equation.

[0086]

(Equation 3)

The above equation shows the case of subtraction by the prediction quotient "D", and the divisor selector (M) outputs three divisor data by the control signal from the control unit (X). Therefore, the adder (k) is an adder having four data inputs in combination with the partial remainder data.

In this way, the partial remainder was found to be "010000011" by the predicted quotient "D", and it was found from the above equation that the sign was positive. The predicted quotient "D" stored in the predicted quotient register (V) is directly output as the official quotient without any correction by the quotient correction circuit (W).

Further, the upper 9 bits of such a partial remainder becomes "083" (HEX), and the next predicted quotient is obtained as "5" (HEX) by the predicted quotient generation circuit (U). In (k), addition is performed as in the following equation.

[0090]

[Equation 4]

Therefore, in this case as well, the result of the partial remainder is positive, so that the quotient correction circuit (W) outputs the formal quotient as it is without correcting the predicted quotient "5" as in the above case.

FIG. 11 shows a time chart when a set of data is subjected to the prediction quotient operation as described above.

[0093]

As described above, according to the high-speed division circuit of the present invention, two sets of dividend and divisor are input in consecutive cycles, division is performed by two-cycle processing, and one cycle is executed in the first cycle. Is configured to perform the division processing of the data of the group and the processing other than the addition / subtraction processing of the other group in the cycle of the second stage.
Compared to the cycle processing, the number of cycles until the final quotient is output takes one more cycle, but the operating performance is expressed by: operating performance = (operating frequency ÷ number of cycles) × number of required quotients. In the case of 50 MHz / 8 × 2 sets = 12.5, in the case of the present invention, 100 MH
z / 9 cycles × 2 sets = 22.2, which means that the cycle operating frequency can be increased to nearly double.

[Brief description of drawings]

FIG. 1 is a block diagram showing in principle the configuration of a high-speed division circuit according to the present invention.

FIG. 2 is a time chart diagram (1) for explaining the operation of the high-speed division circuit according to the present invention.

FIG. 3 is a time chart diagram (No. 2) for explaining the operation of the high-speed division circuit according to the present invention.

FIG. 4 is a block diagram showing an embodiment (1) of the high-speed division circuit according to the present invention.

FIG. 5 is a block diagram showing an embodiment (2) of the high-speed division circuit according to the present invention.

FIG. 6 is a block diagram showing an embodiment (3) of the high-speed division circuit according to the present invention.

FIG. 7 is a block diagram showing an embodiment (4) of the high-speed division circuit according to the present invention.

FIG. 8 is a block diagram showing an embodiment (5) of the high-speed division circuit according to the present invention.

FIG. 9 is an explanatory diagram of a quotient prediction method used in the high speed division circuit according to the present invention.

FIG. 10 is an operation time chart diagram of a quotient prediction method for a set of data in the high-speed division circuit according to the present invention.

FIG. 11 is a diagram for explaining a basic division method.

FIG. 12 is a block diagram showing a configuration of a conventionally known division circuit.

FIG. 13 is an operation time chart diagram (1) of a conventional example.

FIG. 14 is an operation time chart diagram (part 2) of the conventional example.

[Explanation of symbols]

 (A) Divisor register (b) Divisor temporary register (c) Divisor selector (d) Dividend register (e) Dividend temporary register (f) Dividend selector (g), (q) Enable signal generation circuit (h), (s) Data selection circuit (i), (j) Control circuit (k) Adder (l) Operation processing result register (n) Control register (o), (p) Commercial shift register (t) Partial remainder register (r) Quotient selector In the drawings, the same reference numerals indicate the same or corresponding parts.

Claims (5)

[Claims] 1. A divisor of 1 entered in consecutive cycles
The divisor register for storing the data of the second set, the divisor temporary register for storing the data of the second divisor, and the data of the divisor register or the divisor temporary register are alternately selected by the output signal of the first data selection circuit. Output, the dividend register that stores the first set of data of the dividend that is input in consecutive cycles, the dividend temporary register that stores the data of the second set of dividends, and the data stored in each register. A first enable signal generation circuit for generating an enable signal for performing the operation, and a dividend selector that alternately selects and outputs the data of the dividend register or the dividend temporary register by the output signal of the first data selection circuit, The data of the divisor selector is set to the two's complement value or its value according to the control data indicating whether the addition result is positive or negative. The first control circuit that outputs each value as each value, and the data of the dividend selector is first selected, and then the most significant bit of the remaining data of the dividend selector is the least significant bit and the part of the addition result The second control circuit that outputs one data whose upper bit is the data obtained by shifting the remainder data to the upper bit and the output data of both control circuits are input, and the addition processing of the first set and the second set is alternately performed. To output the control data, the partial quotient data, and the partial remainder data, an operation processing result register holding the output data of the adder, a first set output from the operation result register, and First and second commercial shift registers for storing partial quotient data for the second set of dividend and divisor, respectively, and an enable signal for storing data in both commercial registers A second enable signal generation circuit, a quotient selector that selects data to be output to the outside by an output signal of the second data selection circuit when the final quotient is stored in both shift registers, and stores the control data. A high-speed division circuit comprising: a control register to be given to the first control circuit; and a partial remainder register for storing the partial remainder data and giving it to the second control circuit. 2. The high-speed division circuit according to claim 1, wherein when the dividend and the data of the divisor have the same number of bits and the partial quotient data is obtained bit by bit, the first control circuit outputs from the divisor selector. 2's complement generation circuit using the data of the above, a subtraction selector for inputting the data from the complement generation circuit and the data from the divisor selector, and a third control circuit for generating a selection control signal of the subtraction selector from the control data. And a data selection circuit, wherein the second control circuit shifts the partial remainder data of the partial remainder register to the left by 1 bit and outputs the shift remainder, output data of the dividend selector and output data of the shift circuit. And a fourth data selection circuit that generates a selection control signal for the minuend selector. When the divisor is reduced from the third data selection circuit, the output data of the complement generation circuit is selected based on the output signal of the third data selection circuit, and when the divisor is added to the dividend, the output data of the divisor selector is selected. High speed division circuit. 3. The high-speed division circuit according to claim 1, wherein when the number of bits of the data of the dividend is larger than the number of bits of the data of the divisor, and the partial quotient data is obtained bit by bit, the first control circuit: A two's complement generation circuit using data from the divisor selector, a subtraction selector for inputting data from the complement generation circuit and data from the divisor selector, and a selection control signal for the divisor selector from the control data. A third data selection circuit for generating, the second control circuit selects a carry-down data selector for selecting data having the same number of bits as the divisor data from the upper side of the dividend selector, and the data selector. From the fourth data selection circuit for generating a selection control signal for outputting the lower 1-bit data from the A shift circuit for outputting the shifted output, a minuend selector for selecting one data whose output data of the dividend selector or output data of the data selector is the least significant bit and output data of the shift circuit is the most significant bit, and the minuend. And a fifth data selection circuit for generating a selection control signal for the selector,
A high-speed division circuit characterized in that the output data of the dividend selector is selected by the dividend selector only when first performing a process of subtracting the divisor from the dividend as the division processing. 4. The high-speed division circuit according to claim 2, wherein the first control circuit uses an inverter circuit that performs bit inversion of output data of the divisor selector instead of the complement generation circuit, When the adder subtracts the divisor from the dividend as division processing, "1" is input as carry data for the output signal of the third data selection circuit, and when the divisor is added to the dividend, do not input the carry data. High-speed division circuit. 5. The high speed division circuit according to claim 1, wherein the number of bits of the data of the dividend is the same as the number of bits of the data of the divisor, and the partial quotient is 4 by using the quotient prediction method.
A quotient prediction circuit that has a table and outputs a prediction quotient obtained from the relationship with the upper 5 bits of the partial remainder for each of the numbers indicated by the upper 9 bits of the data from the divisor selector, A timing register for holding the output data of the quotient prediction circuit and adjusting the timing with the register, and a control register for adjusting the timing of the data of the timing register with the timing of the partial remainder from the adder, A prediction quotient detection circuit that detects the matching prediction quotient by comparing the prediction quotient from the table and the partial remainder via the control register, a prediction quotient register that stores the prediction quotient data twice, and the prediction quotient A quotient correction circuit that corrects the predicted quotient based on the sign relationship between the quotient register data and the partial remainder data, and a control signal that indicates the predicted quotient data. And a shift circuit for shifting the value of the divisor selector based on the predicted quotient from the control unit, instead of the first control circuit, and output data of the shift circuit. A third control circuit including a complement generating circuit that generates a two's complement and a divisor selector that inputs the output data of the shift circuit and the complement generating circuit and selects data based on the predicted quotient is used. A high-speed division circuit characterized in that a 4-bit quotient is predicted in advance as a division process, the quotient is corrected using a predicted quotient and a partial remainder generated next, and the final quotient is obtained by repeating this.