Electrical computers and digital processing systems: processing – Processing control – Arithmetic operation instruction processing
Reexamination Certificate
1998-11-20
2002-01-08
Maung, Zarni (Department: 2154)
Electrical computers and digital processing systems: processing
Processing control
Arithmetic operation instruction processing
C712S222000, C712S208000
Reexamination Certificate
active
06338135
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a data processing system and method for performing an arithmetic operation on a plurality of signed data values, and in particular to techniques which avoid the requirement to apply the arithmetic operation individually to each signed data value.
DESCRIPTION OF THE PRIOR ART
To enable arithmetic operations to be applied simultaneously to a number of data values. Single Instruction Multiple Data (SIMD) instructions have been developed, where a single instruction is applied to a composite data value consisting of a number of fields, with each field containing a separate data value.
To support SIMD instructions, it is necessary to provide specific SIMD hardware to ensure that the data values in each field of the composite data value do not interact with each other during the application of the SIMD operation to the composite data value. For example, SIMD extensions like Intel Corporation's MMX hardware and the SA-1500 coprocessor generally allow a wide register to be split into independent fixed size sub-fields. For example, such registers may be 64 bits wide, and hence may contain eight 8-bit values, four 16-bit values or two 32-bit values. SIMD instructions operating on these registers are usually 3-operand instructions of the type A=B top C, but they operate on each of the sub-fields in parallel.
For example, an addition of two 64-bit SIMD registers containing four 16-bit values results in four additions being performed on the four sub-fields of each register. The 64-bit result contains four 16-bit values which are the sum of the corresponding fields of the inputs.
The SIMD approach is especially useful in cases where a set of operations on data, for example 8 to 16-bit data, must be performed many times on large quantities of data. Considering the example where 64-bit registers are used, by employing SIMD instructions, up to eight independent 8-bit data sets can be processed in parallel, achieving significant processing speed improvements. One particular area where such SIMD instructions are useful is the area of IPEG or MPEG compression and/or decompression, where many Discrete Cosine Transformation (DCT) operations need to be performed. Each DCT consists of a series of additions and multiplications performed on signed data, and it has been found that the use of SIMD instructions can significantly improve processing speed.
However, there are a number of disadvantages resulting from the use of SIMD instructions. Firstly, as mentioned earlier, to enable SIMD instructions to operate correctly, special hardware is required to ensure that the data values in the various subfields of the register remain decoupled from each other as the SIMD operation is applied. Further, new SIMD instructions that use this hardware need to be defined. This tends to lead to an increase in the instruction bit space required to identify instructions, which is undesirable.
SUMMARY OF THE INVENTION
Viewed from a first aspect, the present invention provides a method of operating a data processing system to perform an arithmetic operation on a plurality ‘p’ of signed ‘n-bit’ data values, comprising the steps of encoding the plurality of signed n-bit data values as a composite value comprising p n-bit fields by performing an encoding operation equivalent to aligning each signed data value with a respective n-bit field, sign extending each signal data value to the most significant bit of the composite value, and adding the aligned and sign extended data values to form the composite value; applying the arithmetic operation to the composite valve to produce an encoded result comprising a n-bit fields; and decoding the encoded result to produce p final results by applying a decoding operation equivalent to extracting the data from each n-bit field of the encoded result and correcting for any effect caused by the addition of an adjacent sign extended data value during the encoding step; whereby each final result represents the application of the arithmetic operation to a corresponding signed n-bit data value.
In accordance with the present invention, two or more signed data values are encoded into a composite value, and the composite value is then processed using standard instructions as if they were SIMD instructions. This is made possible by use of a particular encoding of the signed data values which avoids the problems with overflow and underflow between two adjacent data values. Since this encoding enables standard instructions to be used, much of the benefits of using SIMD extensions can be achieved without the cost of extra hardware or now instructions which SIMD techniques necessitate.
In accordance with the present invention, a plurality p of signed n-bit data values are encoded as a composite value comprising p n-bit fields by performing an encoding operation equivalent to aligning each signed data value with a respective n-bit field, sign extending each signed data value to the most significant bit of the composite value, and adding the aligned and sign extended data values to form the composite value. This encoding allows many operations, for example addition, subtraction, multiplication by a constant and left shifting operations, to be used as long as each of the packed values remains within the minimum/maximum range (for example a value in a 16-bit field must remain within the range −32768 to +32767).
In accordance with the present invention, the encoding is applied to signed data values. Since the encoding of the present invention involves applying an operation equivalent to sign extending each signed data value to the most significant bit of the composite value, it is clear that the addition of the various signed data values aligned with their respective n-bit fields of the composite value will potentially result in some interaction between the various data values. For example, in preferred embodiments, by sign extending a particular signed data value, there will be no effect on the other data values if that sign extended data value is positive, but if that sign extended data value is negative, then this will have the effect of subtracting from the composite value the value 1 aligned with the adjacent data value representing the next n higher significant bits of the composite value.
Accordingly, due to this potential interaction, it is entirely counter intuitive to apply this encoding, since it would be expected that the application of the arithmetic operation to the composite value resulting from such encoding would no yield a result from which could be derived the individual results that would of arisen from the application of the arithmetic operation to each signed n-bit data value in turn. However, contrary to expectations, it has been found that by using the encoding technique of the present invention, the application of the arithmetic operation does yield an encoded result from which the individual final results can be readily derived. All that is required is to extract the data from each n-bit field of the encoded result and to correct for any effect caused by the addition of an adjacent sign extended data value during the encoding step. Hence, in preferred embodiment, all that is required is to add back to the encoded result the value 1 aligned with a particular n-bit field of the encoded result, if the data in the adjacent n-bit field representing the adjacent n lower significant bits of the encoded result is negative.
It will be appreciated that there are many different ways in which the encoding operation can be implemented, provided that the implementation chosen yields a composite value which is equivalent to aligning each signal data value with a respective n-bit field, sign extending each signed data value to the most significant but of the composite value, and adding the aligned and signed extended data values to form the composite value. For example, it is not necessary to align each signed data value with a respective n-bit field prior to sign extending each signed data value, and alternatively each
Arm Limited
Chang Jung-won
Maung Zarni
LandOfFree
Data processing system and method for performing an... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data processing system and method for performing an..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data processing system and method for performing an... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2854130