Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-01-03
2003-05-06
Malzahn, David H. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C712S221000
Reexamination Certificate
active
06560624
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a method and a data processing device, for executing either of division and remainder instructions with efficiency, each of the division and remainder instructions having a code in which information on the size of dividend data is placed.
2. Description of the Prior Art
An instruction set for 32-bit microprocessors can have division and remainder instructions. In either of division and remainder instructions, an operand that can be either one of the divisor and the dividend is handled as a 32-bit binary value.
Referring now to
FIG. 10
, there is illustrated a diagram showing the code of each of division and remainder instructions included in an instruction set provided by a prior art data processing device. In the figure, OP
1
denotes a first operand code, OP
2
denotes a second operand code, R
1
denotes a destination register identifier, R
2
denotes a source register identifier, and C denotes a constant number portion.
In general, each of division and remainder instructions provided by a data processing device can identify both a destination register and a source register using the destination and source register identifiers thereof. For example, division instructions can identify a register storing the dividend with the destination register identifier R
1
thereof, identify another register storing the divisor with the source register identifier R
2
thereof, and store the division result into the register identified by the destination register identifier R
1
. Each of division and remainder instructions does not use information placed in the constant number portion C.
Most prior art data processing devices adopt nonrestoring division as a division algorithm. Although the nonrestoring division is a typical division algorithm, one iteration of division processing computes only one-bit output and therefore much time is spent in computing all one-bit outputs in order to completely perform the division processing, thus reducing the division processing speed.
Referring next to
FIG. 11
, there is illustrated a flow diagram showing a division algorithm adopted by prior art data processing devices.
FIG. 12
shows a block diagram showing hardware required for performing the division algorithm as shown in FIG.
11
. In
FIG. 12
, reference numeral
121
denotes a 32-bit ALU for performing arithmetic operations, numeral
122
denotes a remainder register for storing a remainder, the right-hand 32 bits of the remainder register constituting an extended register, numeral
123
denotes a register, which will be referred to as divisor register, for storing a divisor, and numeral
124
denotes a control circuit for controlling the ALU
121
and the remainder register
122
.
Next, a description will be made as to a flow of division processing based on the nonrestoring division in prior art data processing devices, assuming that both the dividend and the divisor are positive numbers.
First, the control circuit
124
, in step ST
111
, stores the dividend data in the extended register, i.e., the right-hand half of the remainder register
122
, and then sets all of the left-hand 32 bits of the remainder register
122
to zero. Furthermore, the control circuit
124
causes the remainder register
122
to shift the data loaded thereinto left one bit position.
The ALU
121
then, in step ST
112
, subtracts the contents of the divisor register
123
from the contents of the left-hand half of the remainder register
122
, and then loads the subtraction result into the left-hand half of the remainder register
122
.
The control circuit
124
then, in step ST
113
, determines whether or not the remainder stored in the left-hand half of the remainder register
122
is equal to or greater than zero. If the remainder is equal to or greater than zero, the control circuit advances step ST
115
in which it causes the remainder register
122
to shift the contents thereof left one bit position and sets a new bit at the far-right position of the remainder register
122
to one. After that, the control circuit
124
advances to step ST
116
.
In performing step ST
113
, if the remainder is less than zero, the control circuit advances step ST
114
in which the ALU
121
adds the contents of the divisor register
123
to the data stored in the left-hand half of the remainder register
122
so as to return the data stored in the left-hand half of the remainder register
122
to its previous value stored before step ST
112
, and then stores the addition result in the left-hand half of the remainder register
122
. After that, the control circuit
124
causes the remainder register
122
to shift the contents thereof left one bit position and sets a new bit at the far-right position of the remainder register
122
to zero. The control circuit
124
then advances to step ST
116
.
The loop iteration comprised of the above-mentioned steps ST
112
to ST
116
is carried out thirty-two times. In step ST
116
, the control circuit
124
determines whether or not the number of times that the loop iteration comprised of the plurality of steps has been done is equal to or greater than 32. If the number of times that the loop iteration comprised of the plurality of steps has been carried out is less than 32, the control circuit
124
returns to step ST
112
, and then repeats the above-mentioned processes. After the loop iteration has been performed thirty-two times, the control circuit
124
advances to step ST
117
in which it causes the remainder register
122
to shift the data stored in the left-hand half of the remainder register
122
right one bit position.
A problem with prior art data processing devices constructed as above is that since data on which an arithmetic operation is to be performed has a fixed length of 32 bits, the number of times that the loop iteration based on the nonrestoring division is done is fixed, that is, the loop iteration must be performed thirty-two times.
According to the nonrestoring division, when data that can be handled by prior art data processing devices has a significant bit width of N bits, the number of times that the loop iteration must be performed for each of division and remainder calculations can be N that is the same as the bit width of the data. In such a prior art data processing device, since operands have a fixed length of 32 bits, the loop iteration required for each of division and remainder calculations must be done a fixed number of times, i.e., thirty-two times, even if each operand has a significant data width less than 32 bits. Either of division and remainder calculations thus needs a fixed number of clock cycles at all times. Accordingly, when an operand in either of division and remainder instructions has a significant data width less than 32 bits, some loop iterations done upon the execution of the instruction are a time-wasting. In image processing that is a typical example in which division and remainder instructions are frequently issued, data to be processed is 8 or 16 bits in length in most cases. A 32-bit data area for the dividend data thus has a significant bit width of 8 or 16 bits. In this case, although eight or sixteen loop iterations are required for performing each of division and remainder calculations based on the nonrestoring division, thirty-two loop iterations are carried out actually. In this manner, the loop iteration required for executing each of division and remainder instructions must be done thirty-two times even though the bit length of data to be processed is less than 32 bits. Accordingly, some loop iterations carried out upon the execution of each of division and remainder instructions are a time-wasting in most cases, and hence much time is spent in executing each of division and remainder instructions.
SUMMARY OF THE INVENTION
The present invention is made to overcome the above problem. It is therefore an object of the present invention to provide a method of setting a number of times that an arithmetic loop iteration based on the nonrestor
Kondo Hiroyuki
Otani Sugako
Burns Doane , Swecker, Mathis LLP
Malzahn David H.
Mitsubishi Denki & Kabushiki Kaisha
LandOfFree
Method of executing each of division and remainder... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method of executing each of division and remainder..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of executing each of division and remainder... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3025870