Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-03-16
2002-05-28
Malzahn, David H. (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S402000
Reexamination Certificate
active
06397235
ABSTRACT:
The invention relates to a data processing device.
Such a data processing device is known from PCT patent application No. 97/31308. This data processing device allows for parallel processing under control of parallel instructions like SIMD instructions (Single Instruction Multiple Data). A SIMD instruction applies the same operation a number of times in parallel. The SIMD instruction typically defines two operands, normally in terms of register addresses. The content of each of these operands is treated as a plurality of segments of packed data. For example, the content of a 64-bit register may be treated as four 16 bits numbers, located at bit positions
0
-
15
,
16
-
31
,
32
-
47
,
48
-
63
in the register respectively. When the data processing device encounters the SIMD instruction, the same operation is applied to several different pairs of numbers from the operands in parallel. For example, the content of bit positions
0
-
15
in a first operand register is added to the content of bit positions
0
-
15
in a second operand register, the content of bit positions
16
-
31
in a first operand register is added to the content of bit positions
16
-
31
in a second operand register and so on.
The SIMD instructions can be used to reduce the number of instructions that needs to be executed to perform a given function. For example, consider the function of performing a discrete cosine transform (IDCT) of individual columns of a block of pixel values. The pixel values of different rows of the blocks are stored in different operands. In each operand, the pixel value is stored in a segment at a position determined by its column. Thus, a first register might contain a pixel value from a first row, first column at bit positions
0
-
15
, and a pixel value from the first row, second column at bit positions
16
-
32
and so on. A second register might contain pixel values from a second row, pixel values from different rows being stored in the same way according their column. As a result execution of a series of instructions that code for the operations for applying the IDCT to one column automatically performs the IDCT for a number of columns in parallel if the arithmetic operations are all performed using SIMD instructions. This reduces the number of instructions that needs to be executed.
In case of a separable two-dimensional IDCT the one dimensional IDCT needs to be applied to individual columns and to individual rows of the block. In this case a similar reduction in the number of instructions can be obtained when the roles of rows and columns are interchanged between the transformation of the columns and the transformation of the rows. The roles of rows and columns can be interchanged by means of transposition of the block. Transposition brings different pixel values of a column into the same register instead of different pixel values from the same row. Transposition involves moving the content of corresponding positions (corresponding to the same column) from different registers to different positions in another register. Unfortunately, transposition itself requires execution of a considerable number of additional instructions. As a result the two dimensional transform requires more than twice the number of instructions needed for the one dimensional transform.
This limitation on the advantage of SIMD occurs more generally if functions have to be programmed that require the combination of data from noncorresponding positions in the packed data. In this case one cannot use SIMD parallelism to treat content of operands as a packed format containing independent numbers, or at least additional operations are needed to reshuffle the data before SIMD operations can be used.
It is an object of the invention to provide for a processing device as set forth in the preamble which makes it possible to reduce the number of instructions that needed to be executed even further.
Thus it is possible to program parallel operations that make mutually different combinations of segments of the operands, combining segments at positions in the operands that are not equal to each other or using mutually different operations. This in contrast to the prior art SIMD instructions which apply the same operation to each time to a pair of segments located at identical positions. For example, an instruction according to the invention might cause the number stored at bit positions
0
-
15
of an operand register to added to the number stored at bit positions stored at bit positions
16
-
31
in parallel with adding of the numbers stored at bit positions
32
-
47
and the number stored at bit positions
48
-
63
.
One may provide instructions both for operations that combine segments located in the same operand register and for operations that combine segments located in different operand registers. Any one or more segments may be used in more than one operation. The operations executed in parallel may all be the same type of operation, say all additions, or they may be mutually different operations, say additions and subtractions.
Usually, only a very limited set of application specific instructions for combining segments will be provided in addition to SIMD instructions. For example, when an instruction is available which provides for an operation like addition between certain segments at different positions, it is not necessary to provide a set of instructions which program for that operation between all possible pairs of segments. Similarly, if an instruction is available which combines certain pairs of segments each with its own operation (at least one of the operations being different from the others) then is not necessary to provide an instruction set for all possible combinations of operation applied to those segments. For any given application one needs to provide only a small fraction of all possible operations or combinations of operations and/or a small fraction of all possible combined segments.
For a separable two-dimensional transformation on a block the invention makes it possible to reduce the number of required instructions without transposing the block. Each register may still contain different pixel values from one row, with different register storing pixel values from the same column in the same segment. Then the transformation of the columns will still be performed using SIMD instructions, but the transformation of the rows is performed by means of parallel operations that combine pixel values from the same row, located in different segments.
For example, one might provide an IDCT instruction which computes the IDCT of an entire row from pixel values of that row stored in the different segments of the operand registers referred to in the IDCT instruction. Also one might provide operations which compute the sum and difference of the contents of pairs of different segments in a register. This is a type of operation that is typically required in an IDCT transforms and similar transforms.
REFERENCES:
patent: 5638068 (1997-06-01), Nickerson
patent: 5754457 (1998-05-01), Eitan et al.
patent: 5893145 (1999-04-01), Thayer et al.
patent: 6092920 (2000-07-01), Sakamoto
patent: 6119140 (2000-09-01), Murata et al.
patent: 9731308 (1997-08-01), None
patent: WO9731308 (1997-08-01), None
patent: WO9733236 (1997-09-01), None
“Practical Fast 1-D DCT Algorithms with 11 Multiplications”, Proceedings International Conference on Acoustics, Speech and Signal Processing 1989 (IC-IASSP '89) pp. 988-991.
Sijstermans Fransiscus W.
Van Eijndhoven Josephus T. J.
Koninklijke Philips Electronics , N.V.
Malzahn David H.
LandOfFree
Data processing device and method of computing the costine... 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 device and method of computing the costine..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data processing device and method of computing the costine... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2836529