Self-adjusting elasticity data buffer with preload value

• US 6,233,629 B1
• Filed: 02/05/1999
• Issued: 05/15/2001
• Est. Priority Date: 02/05/1999
• Status: Expired due to Term

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Broadcom Corporation (Broadcom, Inc.)
• Inventors: Castellano, Andrew J.
• Primary Examiner(s): Lee, Thomas
• Assistant Examiner(s): Cao, Chun
• Application Number:
  US09/246,038
• Time in Patent Office: 830 Days
• Field of Search: 710/29, 710/34, 710/52, 710/58, 710/60, 710/61, 710/33, 710/57, 711/101
• US Class Current: 710/29
• CPC Class Codes: G06F 5/06 for changing the speed of data flow, i.e. speed regularising or timing, e.g. delay lines, FIFO buffers; over- or underrun control therefor G06F7/78 takes precedence
• CPC Class Codes: G06F 5/10 having a sequence of storage locations each being individually accessible for both enqueue and dequeue operations, e.g. using random access memory G06F5/065 takes precedence

Abstract

The drift between a write pointer and a read pointer processing packets of data through a FIFO buffer is compensated for by adjusting the start of the read pointer relative to the write pointer. The FIFO buffer is sized to include a number of storage cells equal to the product of the maximum frequency offset between the write clock and read clock and the maximum number of data units in a packet. Initially the start of the read pointer is delayed, relative to the write pointer, by a portion of the number of storage cells in the FIFO. During the processing of a data packet it is determined whether the read pointer is drifting toward or away from the write pointer. If the read pointer is drifting away from the write pointer, for subsequent data packets, the read pointer is started almost immediately after the write pointer writes to the first storage cell in the FIFO. If the read pointer is drifting toward the write pointer, for subsequent data packets, the read pointer is started almost immediately prior to the time at which the write pointer writes to the last storage cell in the FIFO.

Claims

1. A method of processing a plurality of data packets, each having a number of data units, through a buffer in accordance with a write clock and a read clock, the buffer having a plurality of sequentially numbered storage cells, said method comprising the steps of:

selecting an initial preload value;

writing the data units into the storage cells using a write pointer operating in accordance with the write clock;

when the storage cell of the buffer having the number equal to the preload value has been written to, reading data units from the storage cells using a read pointer operating in accordance with the read clock;

determining the relative frequencies of the write and read clocks; and

for subsequent data packets, selectively adjusting the preload value to compensate for differences between the write frequency and the read frequency.

2. The method of claim 1 wherein the initial preload value is equal to a portion of the total number of storage cells.

3. The method of claim 2 wherein the initial preload value is substantially equal to the total number of storage cells divided by two.

4. The method of claim 1 wherein the write pointer and read pointer each have a counter associated therewith and the step of determining the relative frequencies of the write and read clocks comprises the step of:

after the start of the reading of data by the read pointer and during the writing of data from the first data packet, comparing the value of the write-pointer counter with the value of the read-pointer counter.

5. The method of claim 4 wherein the step of selectively adjusting the preload value comprises the steps of:

if the read-pointer counter value is less than the write-pointer counter value by an amount greater than the initial preload value, setting the preload value to a low preload value having a value less than the initial preload value; and

if the read-pointer counter value is less than the write-pointer counter value by an amount less than the initial preload value, setting the preload value to a high preload value having a value greater than the initial preload value.

6. The method of claim 5 wherein the preload value is set low only if the read-pointer counter value is less than the write-pointer counter value by an amount equal to or greater than the total number of storage cells in the buffer.

7. The method of claim 5 wherein the low preload value is substantially zero.

8. The system of claim 5 wherein the preload value is set high only if the read-pointer counter value is less than the write-pointer counter value by an amount substantially equal to zero.

9. The method of claim 5 wherein the high preload value is equal to the number of storage cells in the buffer.

10. The method of claim 1 wherein the write pointer and read pointer each have a counter associated therewith and the step of determining the relative frequencies of the write and read clocks comprises the step of:

at the end of the writing of the first data packet, counting the number of words read by the read pointer in order to empty the storage cells.

11. The method of claim 10 wherein the step of selectively adjusting the preload value comprises the steps of:

if the number of words counted is greater than the initial preload value, setting the preload value to a low preload value having a value less than the initial preload value; and

if the number of words counted is less than the initial preload value, setting the preload value to a high preload value having a value greater than the initial preload value.

12. The method of claim 11 wherein the low preload value is set to substantially zero if the number of words counted is greater than the initial preload value by an amount equal to or greater than the total number of storage cells in the buffer.

13. The method of claim 11 wherein the high preload value is set to a value substantially equal to the number of storage cells in the buffer if the number of words counted is zero.

14. The method of claim 1 wherein the write clock and the read clock each have a frequency counter associated therewith and the step of determining the relative frequencies of the write and read clocks comprises the steps of:

counting the cycles of the write clock during a fixed period of time; and

counting the cycles of the read clock during the same fixed period of time.

15. The method of claim 14 wherein the step of adjusting the preload value comprises the steps of:

if the write clock frequency is greater than the read clock frequency, setting the preload value to a low preload value having a value less than the initial preload value; and

if the write clock frequency is less than the read clock frequency, setting the preload value to a high preload value having a value greater than the initial preload value.

16. A method of compensating for the drift between a write pointer and a read pointer processing packets of data having a number of data units through a FIFO buffer, the write and read pointers operating in accordance with a write and read clock respectively, said method comprising the steps of:

sizing the FIFO buffer to include a number of storage cells equal to the product of the maximum frequency offset between the write clock and read clock and the maximum number of data units in a packet;

delaying the start of the read pointer, relative to the write pointer, by a portion of the number of storage cells in the FIFO;

determining if the read pointer is drifting toward or away from the write pointer;

if the read pointer is drifting away from the write pointer, for subsequent data packets, starting the read pointer almost immediately after the write pointer writes to the first storage cell in the FIFO; and

if the read pointer is drifting toward the write pointer, for subsequent data packets, starting the read pointer almost immediately prior to the time at which the write pointer writes to the last storage cell in the FIFO.

17. The method of claim 16 wherein the write pointer and read pointer each have a counter associated therewith and the step of determining if the read pointer is drifting toward or away from the write pointer comprises the steps of:

after the start of the reading of data by the read pointer and during the writing of data from the first data packet, comparing the value of the write-pointer counter to the value of the read-pointer counter;

if the read-pointer counter value is less than the write-pointer counter value by an amount greater than the number of storage cells which the start of the read pointer was delayed, indicating that the read pointer is drifting away from the write pointer; and

if the read-pointer counter value is less than the write-pointer counter value by an amount less than the number of storage cells which the start of the read pointer was delayed, indicating that the read pointer is drifting toward the write pointer.

18. The method of claim 16 wherein the write pointer and read pointer each have a counter associated therewith and the step of determining if the read pointer is drifting toward or away from the write pointer comprises the steps of:

at the end of the writing of the first data packet, counting the number of words read by the read pointer in order to empty the FIFO storage cells;

if the number of words counted is greater than the number of storage cells which the start of the read pointer was delayed, indicating that the read pointer is drifting away from the write pointer; and

if the number of words counted is less than the number of storage cells which the start of the read pointer was delayed, indicating that the read pointer is drifting toward the write pointer.

19. The method of claim 16 wherein the write clock and the read clock each have a frequency counter associated therewith and the step of determining if the read pointer is drifting toward or away from the write pointer comprises the steps of:

counting the cycles of the write clock during a fixed period of time;

counting the cycles of the read clock during the same fixed period of time;

if the write clock frequency is greater than the read clock frequency, indicating that the read pointer is drifting away from the write pointer; and

if the write clock frequency is less than the read clock frequency, indicating that the read pointer is drifting toward the write pointer.

20. A method of processing a plurality of data packets, each having a number of data units, through a buffer in accordance with a write clock and a read clock, the buffer having a plurality of sequentially numbered storage cells, said method comprising the steps of:

writing data to the storage cells in accordance with the write clock frequency;

reading data from the storage cells in accordance with the read clock frequency; and

adjusting the time at which data is begun to be read relative to the time at which data is begun to be written to prevent the over writing of data into a storage cell which contains data which has not yet been read and to prevent the reading of storage cells which have not yet had data written to.

21. The method of claim 20 wherein data is written using a write pointer operating in accordance with the write clock and data is read using a read pointer operating in accordance with the read clock and the step of adjusting the time at which data is begun to be read comprises the steps of:

determining the position of the read pointer relative to the write pointer;

if the read pointer is drifting away from the write pointer such that the write pointer will write data into a storage cell which contains data which has not yet been read by the read pointer, adjusting the read-pointer start time to start close to the write-pointer start time; and

if the read pointer is drifting toward the write pointer such that the read pointer will read data from a storage cell which has not yet had data written to, adjusting the read-pointer start time to start far from the write-pointer start time.

22. The method of claim 20 wherein the step of adjusting the time at which data is begun to be read comprises the steps of:

determining the operating frequencies of the write and read clocks; and

if the write clock frequency is greater than the read clock frequency, adjusting the read-pointer start time to start close to the write-pointer start time; and

if the write clock frequency is less than the read clock frequency, adjusting the read-pointer start time to start far from the write-pointer start time.

23. A system for processing packets of data having a number of data units, said system comprising:

a read clock having an operating frequency;

a write clock having an operating frequency;

a FIFO having a number of storage cells substantially equal to the product of the maximum frequency offset and the maximum number of data units in the data packets;

a write pointer for writing data to the storage cells in accordance with the write clock frequency;

a read pointer for reading data from the storage cells in accordance with the read clock frequency; and

a state machine for controlling the time at which the read pointer starts reading data.

24. The system of claim 23 wherein the state machine comprises:

means for delaying the start of the read pointer relative to the write pointer by a default preload value equal to a portion of the total number of storage cells in the FIFO;

means for calculating the relative positions of the write pointer and read pointer; and

means for selectively adjusting the preload value depending on the relative positions of the write pointer and read pointer.

25. The system of claim 24 wherein the calculating means comprises:

a write-pointer counter for counting the number of storage cells written to by the write pointer;

a read-pointer counter for counting the number of storage cells read by the read pointer; and

means for comparing the values of the read-pointer counter and the write-pointer counter after the start of the reading of data by the read pointer and during the writing of data from the first data packet.

26. The system of claim 25 wherein the adjusting means comprises:

means for setting the preload value to a low preload value having a value less than the initial preload value if the read-pointer counter value is less than the write-pointer counter value by an amount greater than the initial preload value; and

means for setting the preload value to a high preload value having a value greater than the initial preload value if the read-pointer counter value is less than the write-pointer counter value by an amount less than the initial preload value.

27. The system of claim 26 wherein the preload value is set low only if the read-pointer counter value is less than the write-pointer counter value by an amount equal to or greater than the total number of storage cells in the FIFO.

28. The system of claim 26 wherein the preload value is set high only if the read-pointer counter value is less than the write-pointer counter value by an amount substantially equal to zero.

29. The system of claim 25 wherein the reading of the values of the write counter and read counter is performed continuously during the writing of data by the write pointer.

30. The system of claim 24 wherein the calculating means comprises:

a read-pointer counter for counting the number of words read by the read pointer in order to empty the FIFO storage cells after the end of the writing of a data packet.

31. The system of claim 30 wherein the adjusting means comprises:

means for setting the preload value to a low preload value having a value less than the initial preload value if the number of words counted is greater than the initial preload value; and

means for setting the preload value to a high preload value having a value greater than the initial preload value if the number of words counted is less than the initial preload value.

32. The method of claim 31 wherein the low preload value is set to substantially zero if the number of words counted is greater than the initial preload value by an amount equal to or greater than the total number of storage cells in the FIFO.

33. The method of claim 31 wherein the high preload value is set to a value substantially equal to the number of storage cells in the FIFO if the number of words counted is zero.

34. The system of claim 24 wherein the calculating means comprises:

a write-clock frequency counter for determining the frequency of the write clock;

a read-clock frequency counter for determining the frequency of the read clock; and

a device for comparing the write-clock frequency and the read-clock frequency and producing as output, the difference between the two.

35. The system of claim 34 wherein the adjusting means comprises:

means for setting the preload value to a low preload value having a value less than the initial preload value when the write clock frequency is greater than the read clock frequency; and

means for setting the preload value to a high preload value having a value greater than the initial preload value when the write clock frequency is less than the read clock frequency.

36. The system of claim 35 wherein the low preload value is substantially zero.

37. The system of claim 35 wherein the high preload value is equal to the number of storage cells in the buffer.