Circular buffer management

Details Circular buffer management Circular buffer management

1999-10-01

2002-03-26

Kim, Matthew (Department: 2186)

Electrical computers and digital processing systems: memory

Address formation

Combining two or more values to create address

C711S110000, C710S056000

Reexamination Certificate

active

06363470

ABSTRACT:

This application claims priority to S.N. 98402464.6, filed in Europe on Oct. 6, 1998 (TI-27691EU) and S.N. 98402455.4, filed in Europe on Oct. 6, 1998 (TI-28433EU).
FIELD OF THE INVENTION
The present invention relates to circular buffers, the management of circular buffers and processing engines providing circular buffer management.
BACKGROUND OF THE INVENTION
Circular addressing of memory can be useful in processor design for implementing many different types of processes, such as processes involving, for example, Viterbi, back-tracking, de-interleaving and vocoder computations.
It has been proposed to implement circular buffers in random access memory, where a circular buffer is defined with a defined buffer size (BK) aligned with predetermined memory boundaries. For example, it has been proposed to align circular buffers of a size R at memory boundary represented by the N lowest significant bits of the address being 0. The circular buffer then starts at an index of 0 with respect to the boundary where N is the smallest value such that 2
N
>R. For example the circular buffers could be aligned on 64 word boundaries. A circular buffer manager controls access to the circular buffer(s) through the use of pointers to the physical memory space. The requirement to align the circular buffers on memory boundaries can mean that inefficient use of space is achieved. For example, if a 38 word buffer has to be aligned on 64 word boundaries and a plurality of circular buffers are held in memory, the memory rapidly becomes fragmented, 26 words being unused between adjacent circular buffers. Also, in order to provide efficient control of circular buffers under certain programming languages, it is not desirable to have any alignment constraint.
An aim of the invention, therefore, is to provide for circular buffer management without the disadvantages of the prior approach.
SUMMARY OF THE INVENTION
Particular and preferred aspects of the invention are set out in the accompanying independent and dependent claims. Combinations of features from the dependent claims may be combined with features of the independent claims as appropriate and not merely as explicitly set out in the claims.
In accordance with a first aspect of the invention, there is provided data processing apparatus supporting circular buffers. The apparatus comprises address storage for holding a virtual buffer index, offset storage for holding an offset address and buffer size storage for holding a buffer size. Circular buffer management logic is configured to be operable to apply a modifier to a virtual buffer index held in the address storage to derive a modified virtual buffer index and to apply a buffer offset held in the offset storage to the modified virtual buffer index to derive a physical address for addressing a circular buffer.
By employing virtual addressing to a buffer index for a circular buffer management, it is possible to make efficient use of memory resources by allowing one of more circular buffers to be located contiguously with each other or other data in memory, avoiding fragmentation of the memory. The buffer index forms a pointer for the circular buffer. The modifier can be defined by a user, or could be generated automatically in response to parameters such as the buffer size.
The use of virtual addressing also allows compatibility with existing software designed for apparatus which aligns the circular buffers with memory boundaries. The virtual address modification is transparent to the pre-existing software.
The use of virtual addressing can also facilitate the implementation of circular buffers using programming languages, for example the “C” programming language, which do not support memory alignment constraints.
The buffer offset can define a buffer start address, which can be held in an offset register. This can then be added to the modified virtual buffer index to derive a physical circular buffer address. The original and modified virtual buffer addresses can be held in an address register.
The address storage can be formed by a predetermined number of lower significant bits of an address register. The modified virtual buffer index can also be held in the predetermined number of lower significant bits of the address register. Higher order bits in the address register (typically the remainder of the address register) can define a buffer start address, whereby the combination of the higher and lower order bits in the address register defines a physical address.
The buffer offset, which can be held in an offset register, can be added to the physical address in the address register to define a physical address for addressing the circular buffer.
The apparatus can include random access memory for holding the circular buffer.
As an alternative to implementing a circular buffer in memory, an embodiment of the invention can provide manipulation of a bit array, which may be held in memory or in one or more processor registers.
A pointer configuration register can be provided for selectively setting a circular buffer mode for an address register. An exception mode qualifier can be provided for dynamically overriding the setting of a circular buffer mode. The qualifier can also be used dynamically to define whether the address storage is operable in a circular or a linear addressing mode.
In a circular buffer address computation mechanism, carry signals from first and second addition/subtraction computations are used in the computation of a sign value to determine the selection of the result of one of the addition/subtraction operations for the computation of a circular buffer address. The use of the carry signals in this manner can avoid the need for an initial masking step, with a consequent improvement in the speed path of the apparatus.
The apparatus can be in the form of digital signal processing apparatus, providing a digital signal processor (DSP), and can be implemented in one or more integrated circuits. The random access memory can be internal or external to the integrated circuit(s).
An embodiment of the invention finds application to telecommunications apparatus, where circular buffer functions find particular utility for processes involving, for example, Viterbi, back-tracking, de-interleaving and vocoder computations.
In accordance with another aspect of the invention, there is provided a method for managing circular buffer addressing in a data processing apparatus. The method comprises
deriving a virtual buffer index;
modifying the virtual buffer index to derive a modified virtual buffer index;
adding a buffer offset to the modified virtual buffer index derive a circular buffer address.


REFERENCES:
patent: 4722067 (1988-01-01), Williams
patent: 4742479 (1988-05-01), Kloker et al.
patent: 4800524 (1989-01-01), Roesgen
patent: 5623621 (1997-04-01), Garde
patent: 5659698 (1997-08-01), Weng et al.
patent: 5699530 (1997-12-01), Rust et al.
patent: 5765218 (1998-06-01), Ozawa et al.
patent: 5790443 (1998-08-01), Shen et al.
patent: 5911152 (1999-06-01), Wooten
patent: 5983333 (1999-11-01), Kolagotla et al.
patent: 6049858 (2000-04-01), Kolagotla et al.
patent: 6052766 (2000-04-01), Betker et al.
patent: 6073228 (2000-06-01), Holmqvist et al.
patent: 6145061 (2000-11-01), Garcia et al.
Hendrix, “Implementing Circular Buffers With Bit-Reversed Addressing,” Texas Instruments Application Report: SPRA292, Digital Signal Processing Solutions, pp. 1-19, Nov. 1997.*
Restle, “Circular Buffer in Second Generation DSPs”, TMS320 DSP Designer's Notebook, Application Brief: SPRA203, Texas Instruments, pp 1-9, Dec. 1992.*
Horner, “Using the Circular Buffers on the TMS320C5x”, TMS320 DSP Designer's Notebook, Application Brief: SPRA264, Texas Instruments, pp 1-14, Oct. 1995.*
Kloker, K.L., et al.; The Motorola DSP56000 Digital Signal Processor, IEEE Micro, vol. 6, No. 6, Dec. 1, 1986, pp. 29-48.
Fine, B., et al.; Considerations for Selecting a DSP Processor (ADSP-2101 vs. TMS320C50), Microprocessors and Microsystems, vol. 18, No. 6, Jul. 1994, pp. 351-362.

Affiliated with

Also associated with

Rating

Circular buffer management 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 management, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Circular buffer management will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2846165