Electrical computers and digital processing systems: memory – Storage accessing and control – Control technique
Reexamination Certificate
2000-08-23
2004-01-13
Sparks, Donald (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Control technique
C711S119000, C711S126000, C711S201000
Reexamination Certificate
active
06678806
ABSTRACT:
BACKGROUND OF THE INVENTION
In many systems which process large amounts of data, such as image data processing systems, large memories are required. Depending on their types and sizes, memories can be expensive. It is therefore beneficial to make the most efficient use possible of the available memory space. In many cases, it is efficient to select a memory such that the size of each memory location is larger than the data items to be stored at the locations. Multiple data items can then be stored at each location, with each data item occupying a portion of the location. When an individual data item is processed, the memory location in which it is located is accessed. The portion of the data stored at the location that includes the relevant data item is processed. The data item can be extracted from the data stored at the location for processing and inserted into the location after processing. The extraction and insertion must be performed such that the location of the appropriate portion of data within the location and other relevant information are known.
SUMMARY OF THE INVENTION
The present invention is directed to an apparatus and method for processing portions of data words stored in a memory. In accordance with the invention, at least one data register is provided for temporarily storing a data word associated with a memory location. At least one address register associated with the data register is also provided. The address register temporarily stores an address word that is associated with the particular data item or portion of the data word that is to be processed. The address word includes information related to the portion of the data word to be processed. The portion of the data word is processed using the information stored in the address register.
In one embodiment, the information stored in the address word identifies the size of the data item to be processed. The information can identify the size in terms of the number of bytes or the number of bits. For example, this information can identify the portion of the data word as being one byte long or as being eight bits long The information can also identify the position of the data item within the data word. For example, where each data word is 32 bits long and each individual portion of the data word is one byte long, the position information can identify the one of four possible locations within the data word at which the pertinent byte of data is located.
The information can also identify the type of data in the portion of the data word to facilitate processing of the data. For example, this information can identify the data as being signed or unsigned.
The approach of the invention can be used to both extract a data item from the full data word and to insert a data item into the full data word. In one embodiment, when the portion is extracted, the full data word is first read into a shifting device such as a shift register. Using the position and size information stored in the address register, the pertinent portion can be shifted into a predetermined position within the shifting device such as the least significant bit positions. Then, the portion of the data word can be read out of the shifting device. The unused bits in the shifting device can be masked such that only data bits of the relevant portion of data are read out of the shifting device.
The approach of the invention is typically used in conjunction with one or more processors or processing elements executing program instructions. In accordance with the invention, the instruction extracts one of the smaller data item fields from the larger data word and performs an operation on the extracted data item. Likewise, an instruction can insert a smaller field into the larger word at a particular position. In one embodiment, if the result of an operation is larger than the allocated partial field, the result can be truncated and shifted into the correct space within the data register.
In accordance with the invention, the insertion and extraction of the data items into and out of the full data word is performed during an instruction using the information stored in the address register. The instruction is able to process the data item using the position, bit field width (size) and type (signed or unsigned) information.
The information stored in the address register may be referred to as a tag, and the address register may be referred to as a pointer in the C programming language. The address register therefore may be referred to as a tagged pointer.
When an instruction starts, the data register and the address register are read out in parallel. The field width and position information from the address register are used to control the shifter on the data side. In one embodiment, the shifter shifts the smaller bit field containing the data item to the right so that it starts at bit position zero. The unused part of the data register can be masked off, and the data type information can be used to determine whether the data item field is to be sign extended out to the data register width (in the case of signed data) or zero extended (in the case of unsigned data). Next, all the normal operations, e.g., arithmetic operations, can be performed.
When the instruction finishes, an analogous approach can be applied to insert the result back into a data register. The address register associated with the pertinent data register supplies the position and width for the field to be inserted. The signed/unsigned information can be used to determine whether a signed or unsigned saturation operation is to be performed.
During the instruction, the address register can be incremented to point to the next small data item to be extracted from a data register. Likewise, the destination address in the address register can be incremented so that the next result is inserted into a new slot in the destination data register.
The approach of the invention can be readily applied in a single instruction stream, multiple data stream (SIMD) processing system. In such a system, a single instruction operates on multiple data items. In the context of the present inventions a single address register can specify operations on many data registers simultaneously.
The approach of the invention has numerous advantages. For example, in the approach of the invention, the shift and mask functions can be performed as part of instructions, instead of as separate instructions. This saves a considerable number of instructions and therefore increased processing throughput. Also, the function of incrementing the address register to point to a new field can be embedded within an arithmetic instruction instead of being performed as a separate instruction. Again, a significant number of instructions can be saved.
Also, using the approach of the invention, the size of a particular operation is known in advance from the address register. This can aid in expediting certain arithmetic operations. For example, a 32-by-32 multiply can take several cycles, while a 16-by-16 can by done in one.
Using the approach of the invention, data of different sizes can be mixed in one instruction, since each operand can specify a different size via its address register word. In the absence of the tag information of the invention, a separate opcode for, each combination of sizes would be required.
REFERENCES:
patent: 4138720 (1979-02-01), Chu et al.
patent: 4592013 (1986-05-01), Prame
patent: 4604695 (1986-08-01), Widen et al.
patent: 4679140 (1987-07-01), Gotou et al.
patent: 5224214 (1993-06-01), Rosich
patent: 5604913 (1997-02-01), Koyanagi et al.
patent: 6282623 (2001-08-01), Halahmi et al.
patent: 6292879 (2001-09-01), Fong
patent: 0 552 816 (1993-07-01), None
patent: 0 679 991 (1995-11-01), None
patent: 0 945 783 (1999-09-01), None
Hennessey, et al., “Enhancing Vector Performance,” Computer Architecture a Quantitative Approach, Second Edition, Section B5, pp. B23-B29, 1996.
ChipWrights Design, Inc.
Mills & Onello LLP
Peugh Brian R.
Sparks Donald
LandOfFree
Apparatus and method for using tagged pointers for extract,... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for using tagged pointers for extract,..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for using tagged pointers for extract,... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3185555