Electrical computers and digital processing systems: memory – Storage accessing and control – Access timing
Reexamination Certificate
1997-09-08
2002-10-15
Verbrugge, Kevin (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Access timing
C711S220000, C711S221000
Reexamination Certificate
active
06467035
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a system and method for accessing data from a data memory and, more particularly, to a system and method that accomplishes indirect address table look-ups in a single instruction cycle.
BACKGROUND OF THE INVENTION
Data processing devices such as digital signal processors and microprocessors are key components of most electronic equipment in use today. While the tasks performed by these devices is, at times, incredibly complex, the basic operation of these devices is not. To accomplish tasks of great complexity, the devices perform a large number of relatively simple operations very quickly. For example, a typical digital signal processor (“DSP”) performs millions of operations each second.
The operations performed by a data processing device (referred to hereafter as a “data processor”) are controlled by a series of instructions that are executed by the data processor. An instruction specifies the operation to be performed and may include parameters to be used during the associated operation. Typical instructions define operations such as adding one item of data (typically referred to as a word of data) to another word of data or moving a word of data from one location in data memory to another location.
Inasmuch as the basic operation of a data processor consists of the manipulation of data, a significant percentage of its operations involve retrieving data from and sending data to data memory. In its simplest form, a data access instruction specifies the address at which the data resides in the memory. Upon execution of this instruction, the data processor retrieves the data at the specified address.
To perform more robust tasks, the data processor may use a more complicated form of addressing referred to as “indirect addressing.” Indirect addressing allows programmers to specify locations of data, without knowing the physical address at which the data is actually stored. For example, in a data memory with one million data locations, one thousand contiguous data locations may be designated as a data table. The address of the first data location in the table is referred to as the “base address” of the table. Data within the table can be accessed by reference to an “offset” from the base address. Thus, the first data location would be identified by offset=0, the second data location by offset=1, and so forth.
To perform an indirect address data memory access, the data processor combines the offset and the base address. Typically, this involves performing the operations of reading the offset from a data memory, adding the offset to the (previously obtained) base address, and accessing the data memory location specified by the combined address.
Conventional data processors require several instructions to accomplish an indirect addressing data access. For example, a DSP sold under the product name “TMS320C54x” by Texas Instruments requires several cycles to perform the indirect addressing operation described above. See, for example, Table 7-2 in the TMS320C54x 1995 User's Guide. Similarly, a DSP sold under the product name “DSP16” by Lucent Technologies, may require five instruction cycles per table look-up access. See, for example, the bit reverse operation in the WE® DSP16 and DSP16A Application Software Library Reference Manual.
Given the relatively large number of indirect memory accesses that may be performed by these data processors, a need exists for a data processor that can more efficiently perform data accesses using indirect addressing.
The invention provides an improved table look-up/indirect addressing system and method. The invention makes use of a dual-fetch Harvard architecture for a processor to implement one full table look-up access per instruction cycle.
The dual-fetch Harvard architecture provides two data paths that can be accessed during the same clock cycle. The invention uses these two data paths to access the offset and the data, respectively.
To accomplish a full table look-up during one clock cycle, the invention accesses data using a data pipeline. That is, the offset data accessed during a previous cycle is used during the current cycle to retrieve the data from the table. During each clock cycle, the invention reads a data word from a data memory using the address calculated during the previous cycle, adds the base address of the table to the offset obtained during the previous cycle, and reads the next offset from a data memory.
REFERENCES:
patent: 4439827 (1984-03-01), Wilkes
patent: 5150471 (1992-09-01), Tipon et al.
patent: 5165026 (1992-11-01), Kusakabe
patent: 5233694 (1993-08-01), Hotta et al.
patent: 5577230 (1996-11-01), Argade et al.
patent: 5829049 (1998-10-01), Walker et al.
patent: 5860130 (1999-01-01), Yamanaka et al.
patent: 5961637 (1999-10-01), Sturges et al.
Tate Larry R.
Thierbach Mark
Agere Systems Guardian Corp.
Verbrugge Kevin
LandOfFree
System and method for performing table look-ups using a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for performing table look-ups using a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for performing table look-ups using a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2954748