Electrical computers and digital processing systems: memory – Address formation – Operand address generation
Reexamination Certificate
2001-11-26
2004-06-01
Sparks, Donald (Department: 2187)
Electrical computers and digital processing systems: memory
Address formation
Operand address generation
C711S217000, C711S219000, C711S169000, C712S035000, C712S209000
Reexamination Certificate
active
06745314
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
The present invention is directed, in general, to computer systems and, more specifically, to a circular buffer control circuit and method of operating the same.
BACKGROUND OF THE INVENTION
Over the last several years, DSPs have become an important tool, particularly in the real-time modification of signal streams. They have found use in all manner of electronic devices and will continue to grow in power and popularity.
Those skilled in the art are familiar with DSP architecture in general. Conventional DSPs employ a pipeline through which pass data representing a signal to be processed. An execution core performs various mathematical and logical operations on the data to effect changes therein. Memory is coupled to the execution core. The memory contains not only instructions concerning the way in which the data are to be modified, but also further data that may be employed in conjunction with executing the instructions.
The latest DSPs are fast and attuned to handling very large amounts of data. One function that is necessarily performed in the handling of data is memory access (i.e., storing and loading). The speed at which a DSP can store and load data is critical to the overall performance of the DSP.
Buffers are memory structures (most often a window of contiguous memory locations) that are established for the purpose of storing sequential data, usually only temporarily. Data are stored in a buffer and later loaded from the buffer. A control circuit, which may be rudimentary or complex, governs where the data are stored in and loaded from the buffer.
One particular type of buffer is germane to an understanding of the background of the present invention: a circular buffer (or “ring”) buffer. While circular buffers are made up of only a finite number of memory locations, they appear to be of limitless size, because they loop back on themselves.
As data are stored in contiguous locations within the circular buffer, a physical end of the buffer (a “boundary”) is eventually reached. However, instead of disallowing further storing, the buffer continues to receive data beginning at its other boundary. For example, if a circular buffer stores data to, or loads data from, sequentially increasing memory locations, it will eventually reach its upper boundary. At that point, the circular buffer “wraps around” and begins to store data to, or load data from, sequentially increasing memory locations beginning at its lower boundary. The same principle holds true for buffers that store data to, or load data from, sequentially decreasing memory locations.
Circular buffers have many applications, but their control circuits can be quite complex. Prior art control circuits for such buffers employed multiple layers of adders and complex logic to calculate addresses in the buffer to which to store or from which to load data. These prior art control circuits occupied space, and were time- and power-consuming. They were also limited in terms of the types of load and store instructions they could interpret and handle.
Accordingly, what is needed in the art is a faster, simpler circular buffer control circuit that is able to be used with a larger number of load and store operations than were prior art control circuits. What is further needed in the art is a general purpose processor or DSP that employs such circuit to advantage.
SUMMARY OF THE INVENTION
To address the above-discussed deficiencies of the prior art, the present invention provides a circular buffer control circuit, a method of controlling a circular buffer and a DSP incorporating the circuit or the method. In one embodiment, the circuit includes: (1) address calculation logic, having multiple datapaths, that calculates, from data regarding a buffer operation, an updated address result therefor and (2) modification order determination circuitry, coupled in parallel with the address calculation logic, that transmits a memory access request and the updated address result in an order that is based on whether the buffer operation is pre-modified or post-modified. A pre-modified buffer operation is one in which a buffer address is changed (incremented or decremented as appropriate) before the memory access takes place. A post-modified buffer operation is temporally reversed; the memory access takes place before the address is changed.
The present invention therefore introduces a circular buffer control circuit that is hardware-based and unrestricted in terms of the types of instructions it can accommodate.
In one embodiment of the present invention, the address calculation logic calculates the updated address result in a single clock cycle. Such speed is important in today's DSPs. However, those skilled in the pertinent art should understand that the broad scope of the present invention is not limited to single-cycle embodiments.
In one embodiment of the present invention, the address calculation logic further updates an address register in the processor. In a related embodiment, the circuit may be employed simply to generate addresses, and not to fulfill memory operations. Further, the hardware making up the circuit can be employed for other purposes when the circuit is not in use.
In one embodiment of the present invention, the address calculation logic employs an input address having base and offset components to calculate the updated address result. Those skilled in the pertinent art are familiar with base addressing schemes. Of course, the present invention can employ other types of addressing to advantage.
In one embodiment of the present invention, the address calculation logic accommodates opposing directions of circular buffer operation. Thus, the address calculation logic can work with both sequentially increasing addresses and sequentially decreasing addresses. Of course, the circuit could be limited to unidirectional operation.
In one embodiment of the present invention, the buffer operation involves varying numbers of words. In an embodiment to be illustrated and described, the buffer operation involves up to four words. Those skilled in the pertinent art will understand, however, that the principles of the present invention apply to buffer operations of any size.
In one embodiment of the present invention, the processor is a DSP. Those skilled in the pertinent art will understand, however, that the principles of the present invention can find application in processors of many types, including non-DSP, general purpose microprocessors.
The foregoing has outlined, rather broadly, preferred and alternative features of the present invention so that those skilled in the art may better understand the detailed description of the invention that follows. Additional features of the invention will be described hereinafter that form the subject of the claims of the invention. Those skilled in the art should appreciate that they can readily use the disclosed conception and specific embodiment as a basis for designing or modifying other structures for carrying out the same purposes of the present invention. Those skilled in the art should also realize that such equivalent constructions do not depart from the spirit and scope of the invention in its broadest form.
REFERENCES:
patent: 5333288 (1994-07-01), Kusuda
patent: 5896543 (1999-04-01), Garde
patent: 5954811 (1999-09-01), Garde
patent: 6363470 (2002-03-01), Laurenti et al.
patent: 6499098 (2002-12-01), Laurenti
patent: 6519692 (2003-02-01), Sheier et al.
Wess et al., “Minimization of Data Address Computation Overhead in DSP Programs”, © 1998, IEEE, p. 3093-3096.*
Wess et al., “Optimal DSP Memory Layout Generation as a quadratic Assignment Problem”, © 1997, IEEE, p. 1712-1715.*
Wess et al., “DSP Data Memory Layouts Optimized for Intermediate Address pointer Updates”, © 1998, IEEE, p. 451-454.
Hitt Gaines & Boisbrun P.C.
LSI Logic Corporation
Peugh Brian R.
Sparks Donald
LandOfFree
Circular buffer control circuit and method of operation thereof does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Circular buffer control circuit and method of operation thereof, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Circular buffer control circuit and method of operation thereof will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3331489