JPH08115205A - High-speed remainder arithmetic unit - Google Patents

Abstract

PURPOSE: To perform a high-speed remainder arithmetic operation with less hardware amount by selecting a numerical value for which the relation of a numerator and a denominator satisfies specified conditions and turning it to the input of an adder. CONSTITUTION: By selecting an N for which the relation of the numerator and the denominator satisfies a formula, turning it to the input of a first adder 8 and a second adder 9 and decoding the result in a decoder, the remainder of an arithmetic result is obtained. For instance, (b)=4 is selected in the formula. In this case, since (b) to be the denominator can be expressed as (b)=3+1, for the remainder in the case of dividing a binary number expressed by four bits by 3, the binary number expressed by four bits is decomposed into upper two bits a3 and a2 and lower two bits a1 and a0 and turned to the input of the first adder 8. Since the arithmetic result becomes three bits at maximum, it is decomposed into an upper one bit b2 and lower two bits b1 and b0 and turned to the input of the second adder 9. By encoding the arithmetic result in an encoder 10, the output of d0, d1 and d2 corresponding to remainder values 0, 1 and 2 is obtained.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an image processing apparatus, and more particularly to a high speed residue computing apparatus in a frame buffer memory processing apparatus which accesses frame buffer memories in parallel.

[0002]

2. Description of the Related Art In recent years, with the widespread use of workstations and personal computers, a graphics processor for performing CAD display, image processing, window processing and the like has been mounted. However, since the access time of a general frame buffer memory is slower than the operation speed, the access time of the system is improved by connecting them in parallel and accessing them in time division (interleave).

In this case, a plurality of connected frame buffer controllers are provided with means for judging whether the data received from the graphic processor is the data for which the user is in charge, and when the judgment result is the data for which the user is in charge. Only for reading / writing pixel data in the frame buffer memory. However, the determination result is obtained by the remainder when the address of the pixel data is divided by the number of connected frame buffer memory controllers, that is, the number of interleave ways of the frame buffer memory. For this reason, a complicated remainder calculation device is required, which causes a reduction in calculation speed.

Now, a conventional remainder computing device will be described. FIG. 7 is a block diagram of a conventional remainder calculation device, and FIG. 8 is an explanatory diagram of the same remainder calculation method. In FIG. 7, 1, 2, 3
Is a subtracter that executes y-x, and 4, 5 and 6 respectively output the input y when the subtraction results of the subtracters 1, 2 and 3 are negative, and when the subtraction result is positive, the subtraction result y It is a selector that outputs -x. FIG. 7 shows a configuration example in which a remainder obtained by dividing b3b2b1b0 represented by a binary number by a1a0 is obtained. As a specific calculation example, b3
The case of b2b1b0 = 1111 and a1a0 = 10 will be described with reference to FIG.

First, the value 1111 of b3b2b1b0 is used as the y input of the subtracter 1, and the value 1100 obtained by shifting a1a0 to the left by 2 bits (that is, multiplied by 4) is used as the x input of the subtractor 1. Since the result of y-x, that is, 111 is positive, the result 111 is used as the y input of the subtractor 2 in the next stage (step 1 in FIG. 8). Next, the value 100 obtained by left-shifting a1a0 by 1 bit (that is, doubled) is used as the x input of the subtracter 2,
When y-x is calculated in the same manner as described above, 11 is obtained (step 2 in FIG. 8). Since the result of this operation is positive, the selector 5 transmits this result to the y input of the subtractor 3 in the next stage. Next, when the value of a1a0, that is, 10 is used as the x input of the subtractor 3 and y-x is calculated in the same manner as described above, 1 is obtained (step 3 in FIG. 8). Since this is smaller than the divisor 10, the remainder 1 is obtained as the calculation result.

[0006]

As described above, in the conventional remainder computing device, the subtractor and the selector are combined in the required number of stages, which results in an increase in the amount of metal and a reduction in the computing speed.

Therefore, the present invention has been made to solve the above problems, and an object of the present invention is to provide a high-speed residue calculation device capable of performing high-speed residue calculation with a small amount of metal.

[0008]

To this end, the present invention selects N such that the relationship between the numerator and the denominator satisfies (Equation 3), and uses this as the first adder and the second adder. , And the result is decoded by a decoder to obtain the remainder of the operation result.

[0009]

(Equation 3)

[0010]

According to the above construction, when the denominator satisfies a certain relationship, a high-speed remainder computing device can be realized.

[0011]

Embodiments of the present invention will be described below with reference to the drawings. FIG. 1 is a configuration diagram of a high-speed residue computing device according to the first embodiment of the present invention, and FIG. 2 is a truth table diagram of the high-speed residue computing device. In order to simplify the explanation, in the first embodiment, a binary number represented by 4 bits is converted into 2 bits of 2 bits.
A case of obtaining a remainder divided by a base number will be described. FIG.
, 8 is the first adder, 9 is the second adder, 10
Is an encoder. A binary number represented by 4 bits is represented by every 2 bits, that is, by a quaternary number so as to satisfy (Equation 4).

[0012]

[Equation 4]

In Equation 4, b = 4 is selected. Here, since the denominator b can be expressed as b = 3 + 1 from (Equation 5), the remainder when dividing the binary number represented by 4 bits by (Equation 5) by 3 is (Equation 6). Since it can be realized by addition, the speed can be extremely increased.

[0014]

(Equation 5)

[0015]

(Equation 6)

The case of obtaining the remainder when the binary number represented by 4 bits is divided by 3 will be described in more detail below. The binary number represented by 4 bits is decomposed into 2 bits according to (Equation 6), and the coefficients a3 and a2 of the higher 2 bits are used as one input of the first adder 8 and the lower 2 bits a1,
Let a0 be the other input of the first adder 8. The calculation result of the first adder 8 becomes the value shown in the column of b2b1b0 in FIG. In other words, the maximum operation result is 3 bits.
According to (Equation 6), this is ranked high for the same reason as above.
It is decomposed into a bit b2 and lower two bits b1 and b0. The sun b2 is used as one input of the second adder 9, and b1, b0
Is the other input of the second adder 9. Second adder 9
The calculation result of is the value shown in the column of c1c0 in FIG.
By encoding the calculation result of the second adder 9 with the encoder 10, the output results of d0, d1, and d2 corresponding to the cases where the remainder values are 0, 1, and 2 are obtained.

FIG. 3 is a block diagram of an image processing apparatus to which the high-speed residue computing device according to the second embodiment of the present invention is applied, FIG. 4 is an explanatory diagram of the same pixel drawing, and FIG. 5 is a block diagram of the high-speed residue computing device. FIG. 6 is a truth table of the encoder. In FIG. 3, 11 is a CPU, 12 is a pixel generator that generates pixel-based data of a line segment or a figure in response to a command from the CPU 11, and 13 is whether the data from the pixel generator 12 is data that it is in charge of. A hit discriminator for discriminating, a frame buffer controller 14 for controlling reading / writing of data from / to the frame buffer 15 based on the result of the hit discriminator 13, and a multiplexer 16 for transferring the data from the frame buffer 15 to the display device 17 in a time division manner. Is.

In FIG. 3, a case where a straight line drawing command is sent from the CPU 11 to the pixel generator 12 will be described. The pixel generator 12 interprets the straight line drawing command, and the start point coordinates A (X1, Y1) and the end point coordinates B of the straight line are drawn.
Generate pixel address and data between (X2, Y2). The hit discriminator 13 arranged in parallel discriminates from the generated pixel address whether or not it is the pixel data for which it is in charge, and if it is the data in charge (hits), the data is assigned to the next frame. Transfer to the buffer controller 14. The frame buffer controller 14 writes pixel data into the frame buffer 15 which it is in charge of at appropriate timing.
A plurality of frame buffers 15 are arranged, and the output data of the frame buffers 15 is transferred to the display device 17 by the multiplexer 16 in a time division manner, and the display device 17 displays the straight line AB on the screen.

In the above process, the hit discriminator 13 determines the pixel address from the number of the frame buffer controllers 14 in order to discriminate from the generated pixel address whether it is the pixel data which the hit discriminator 13 is in charge of. It is necessary to find the remainder when divided by the number of interleave ways). Here, an example of configuring the hit discriminator 13 is shown in FIG. In FIG. 5, the pixel address is represented by 12 bits a11 to a0. In this case, the remainder when the pixel address is divided by the number of frame buffer controllers 14 (5 in the example of this figure) is expressed by (Equation 6) from (Equation 5). Therefore, in FIG.
Reference numeral 19 is a first adder for adding the pixel addresses a11 to a8 and pixel addresses a7 to a4, and 20 is the calculation result b4 to b0 of the first adder 19 and the pixel address a.
A second adder for adding 3 to a0, 21 is a third adder for adding the calculation results c5 to c4 and c3 to c0 of the second adder 20, and 22 is a third adder 21. An encoder 23 encodes a calculation result, and 23 is an encoded output thereof. FIG. 6 shows the relationship between the calculation results d3 to d0 of the third adder 21 and the output of the encoder 22. In FIG. 4, 24 is a start point pixel of the straight line AB, and 25 is a same end point pixel. As described above, the means for determining which frame buffer controller is in charge of a pixel from the pixel address can be configured by an adder and an encoder, so that a high-speed operation can be performed with a smaller amount of metal than the conventional one. The performance of the system can be improved.

[0020]

As described above, the high-speed residue computing device of the present invention includes the first adder, the second adder which receives the output of the first adder, and the decoder which decodes the output result. Since it is configured, it is possible to perform a high-speed remainder calculation with a small amount of metal, and it is possible to realize a very efficient remainder calculation.

[Brief description of drawings]

FIG. 1 is a configuration diagram of a high-speed residue computing device according to a first embodiment of the present invention.

FIG. 2 is a truth table diagram of the high-speed residue computing device according to the first embodiment of the present invention.

FIG. 3 is a configuration diagram of an image processing device to which a high-speed residue computing device according to a second embodiment of the present invention is applied.

FIG. 4 is an explanatory diagram of pixel drawing in the second embodiment of the present invention.

FIG. 5 is a block diagram of a high-speed residue computing device according to a second embodiment of the present invention.

FIG. 6 is a truth table diagram of the encoder in the second embodiment of the present invention.

FIG. 7 is a block diagram of a conventional remainder computing device.

FIG. 8 is an explanatory diagram of a conventional remainder calculation method.

[Explanation of symbols]

 8 and 9 adder 10 encoder 11 CPU 12 pixel generator 13 hit discriminator 14 frame buffer controller 15 frame buffer 16 multiplexer 17 display device 18 main memory 19, 20, 21 adder 22 encoder

Claims (1)

[Claims] 1. A high-speed residue computing device for obtaining a residue when a specific value satisfying (Equation 1) is used as a denominator,
Select N such that the relationship between the numerator and the denominator satisfies (Equation 2), use this as the input to the first adder and the second adder, and decode the result by the decoder to obtain the remainder of the operation result. A high-speed residue computing device characterized in that [Equation 1] [Equation 2]