Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-07-18
2004-08-03
Ngo, Chuong Dinh (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S603000
Reexamination Certificate
active
06772186
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to a processor and is more particularly concerned with a microprocessor having a multimedia multiply-subtractor/adder which assures critical processing precision by properly combining multiplications, additions and subtractions in efficient execution of mass multimedia processing.
BACKGROUND OF THE INVENTION
In the conventional microprocessor, multiplication of numerical data by numerical data is generally carried out. In conventional multiplication, either an unsigned multiplicand is multiplied by an unsigned multiplier or a signed multiplicand is multiplied by a signed multiplier. That is, the multiplicand and the multiplier are generally of the same type.
With data handled by multipliers and processors becoming more diversified, there has been proposed a processor including an embedded piece of hardware capable of multiplying a signed multiplicand by a signed multiplier or an unsigned multiplicand by an unsigned multiplier. In addition, there has been proposed a multiplier capable of carrying out four types of multiplication as disclosed in Japanese Patent Prepublication Nos. Sho 63-623 and Sho 64-88831. Two of the four types are the conventional multiplication of an unsigned multiplicand by an unsigned multiplier and the conventional multiplication of a signed multiplicand by a signed multiplier. The remaining two of the four types are multiplication of an unsigned multiplicand by a signed multiplier and multiplication of a signed multiplicand by an unsigned multiplier.
In the functional aspect of a processor, it is necessary to support a multiply-addition instruction in order enhance the signal processing performance and the multimedia processing performance of the processor. In recent years, the number of processors incorporating a dedicated processing unit having the multiply-addition function has been increasing. In addition, in order to make the processing configuration suitable for multimedia processing, the number of processed bits is optimized, and there has been adopted a parallel processing mechanism called SIMD (Single Instruction stream-Multiple Data stream) wherein all input/output bits of a processor are divided into a plurality of blocks each having a size of n bits where n does not exceed ½ the number of input/output bits. An example of the processor adopting the SIMD mechanism is Intel's MMX Pentium processor.
In the multiplier or the processor described above, however, the inventor has discovered a number of problems.
In order to identify the characteristic of a multimedia processing function to which the present invention is applied, a multiply-addition processing algorithm of a discrete cosine transform used in picture processing is considered as an example. Since the processing is picture processing, the computation formula is 2-dimensional and the multiply term is a double product such as (X(i, j)·B(i))·C(j) wherei and j are subscripts of the addition in the two dimensions respectively, X(I, j) is a variable or a picture—data value and B(I) and C(j) are cosine constants. Normally, 2-dimensional multiply-addition is split into two 1-dimensional operations. That is, first of all, multiply-addition of D(j)=X(i, j)·B(i) is carried out with respect to i. Then, multiply-addition of Y=D(j)·C(j) is carried out with respect to j.
In these operations, the following problem is raised. In general, a product X×Y of a As. multiplication of an n-bit multiplier by an n-bit multiplicand is 2n bits in size as shown in FIG.
2
. For n=16, for example, the product of a multiplication of a 16-bit multiplier by a 16-bit multiplicand is 32 bits in size. Since the processing is 2-dimensional, however, the product must be multiplied by a 1-dimensional multiply-addition result once again. In this case, since the product obtained as a result of the first multiply-addition is 32 bits in size, in the second multiply-addition, the 32-bit result must be multiplied by a 16-bit multiplier. In this case, since the size of the multiplicand is different from the size of the multiplier, the same multiplier can not be used. It is thus desirable to reduce the result of the first multiply-addition to 16 bits so that, in the second multiply-addition, the 16-bit result is multiplied by a 16-bit multiplier to give a 32-bit product which is also reduced to a 16-bit final result. It is thus necessary to approximate the 32-bit product of a 16-bit multiplicand and a 16-bit multiplier by a 16-bit number.
Consider the following case. As shown in
FIG. 2
, data
10
is a number having a sign
11
. A constant
20
is also a number having a sign
21
. Used as a multiplicand and a multiplier with a uniform format, the numerical data
10
and the constant
20
are subjected to a multiply-addition with a size of 16 bits×16 bits to give a 32-bit product
30
. Then, the 32-bit product
30
is approximated by a number with a size of 16 bits obtained as a result of extraction of the 16 high-order bits from the product
30
. The multiplication result
30
has 2 sign bits, namely, bits
31
and
32
. Strictly speaking, the sign bit s is shifted to the high-order bit of the 2 sign bits, namely, bit
32
. The approximation number with a size of 16 bits is necessary to have a signed number having a precision of 15 bits. In order to solve this problem, the multiplication result
30
is shifted to the left by 1 bit to discard the extra sign bit, that is, bit
32
. That is, in order to express the final cumulative result
40
by an approximation number with a size of 16 bits, the multiplication result
30
is shifted to the left by 1 bit with its precision being maintained and stored in a cumulative register. The critical precision is considered to be insufficient unless the operations described above are carried out in the application of the SIMD technique to picture processing.
As will be appreciated from the above description, in order to assure the precision of multiplication of signed numbers as part of expansion of the conventional multiply-addition function, a function to shift a multiplication result to the left by 1 bit if necessary and to add the left-shifted multiplication result to a cumulative result obtained so far is required in multimedia processing. For this reason, there has been proposed a processing instruction whereby, in fixed-point processing of signed numbers, a multiplication result is shifted to the left by 1 bit and the position of the fixed point is restored. For details, refer to U.S. Pat. No. 5,754,456.
In the case of a constant that can have only a positive value, there is raised a problem that the precision of the absolute value is degraded by 1 bit. With the method described above, this problem is unsolved. In addition, since this method requires a shift operation, its implementation is difficult and the latency increases. With the rising operating frequency of recent more difficult to implement a processing unit with a complex function having a latency within one machine cycle. A latency of 2 to 3 or even more machine cycles may be required. As a result, multiply-addition for cumulatively adding results becomes more and more difficult to implement by using a processor with a low throughput. An example of such multiply addition is:
A←A+X
[1
]×Y
[1],
A←A+X
[2
]×Y
[2],
- - -
A←A+X[n]×Y[n]
Several problems raised in actual applications are also revealed in a document describing the four combination types of multiplication, that is, the two conventional combination types of multiplication, namely, the multiplication of signed numbers and the multiplication of unsigned numbers, and the two new combination types of multiplication, namely, the multiplication of a signed multiplicand by an unsigned multiplier and the multiplication of an unsigned multiplicand by a signed multiplier. If information indicating whether or not a number has a sign is included in the numerical data of the nu
Arakawa Fumio
Tonomura Motonobu
Miles & Stockbridge P.C.
Ngo Chuong Dinh
Renesas Technology Corp.
LandOfFree
Multimedia multiply-adder does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multimedia multiply-adder, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multimedia multiply-adder will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3306642