System and method for management of a predictive split cache for supporting FIFO queues

• US 5,502,833 A
• Filed: 03/30/1994
• Issued: 03/26/1996
• Est. Priority Date: 03/30/1994
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Byrn, Jonathan W., Delp, Gary S.
• Primary Examiner(s): Swann, Tod R.
• Assistant Examiner(s): Asta, Frank J.
• Application Number:
  US08/221,140
• Time in Patent Office: 727 Days
• Field of Search: 395/436, 395/437, 395/459, 395/600, 395/725, 364/238.8, 364/244.3, 364/246.11, 364/247.7
• US Class Current: 711/132
• CPC Class Codes: G06F 12/0875 with dedicated cache, e.g. instruction or stack
• 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

Abstract

A first-in, first-out queue is implemented on two memory elements by enqueuing and dequeuing items from a first memory element and by swapping middle portions of the queue between the first memory element and the second memory whenever the first memory element is sufficiently filled. Where the second element is system memory for a computer system, queue length can be allowed to grow almost arbitrarily while preserving the performance of first memory element.

Claims

1. Apparatus for caching items for first-in, first-out queues on a data processing system, comprising:

a backing store for supporting a wrap around buffer;

a cache store having a plurality of frames;

means for dynamically assigning some but not all of the plurality of frames to a cache tail portion and at least some remaining frames of the plurality of frames to a cache head portion;

means responsive to an enqueue command for writing an item to a free frame assigned to the cache tail portion;

means responsive to a dequeue command for reading an item from an occupied frame assigned to the cache head portion;

means for moving an item from a frame assigned to the cache tail portion to a trailing location in the wrap around buffer; and

means for moving an item from a leading location in the wrap around buffer to an unoccupied frame in the cache head portion.

2. Apparatus as claimed in claim 1, wherein the means for moving an item from a frame assigned to the cache tail portion operates responsive to a proportion of frames occupied in the cache store exceeding a threshold.

3. Apparatus as claimed in claim 2, wherein the means for dynamically assigning are responsive to the proportion of frames occupied in the cache store not exceeding a threshold for reassigning occupied frames from the cache tail portion directly to the cache head portion.

4. Apparatus as claimed in claim 3, wherein the means for dynamically assigning are responsive to the proportion of frames occupied in the cache store not exceeding a threshold for reassigning unoccupied frames from the cache head portion to the cache tail portion.

5. Apparatus as claimed in claim 4, and further comprising:

means for assigning pointers to selected ones of the plurality of frames in the cache store including, a current tail pointer for defining an entry frame in the cache tail portion, a tail intra frame pointer for defining which piece of the frame the next tail entry will be placed, a next tail pointer for defining the next frame to be used for the tail cache, a current head pointer to an output frame in the cache head portion for an oldest item in a first-in, first-out queue, a next head pointer to the location of the next frame with the next oldest item in the first in, first out queue, and a head intra frame pointer to the location within the frame where the next item to be removed is stored.

6. Apparatus as claimed in claim 5, wherein the means for moving items in frames assigned to the cache tail portion operates further responsive to a frame in the cache tail portion being full.

7. Apparatus as claimed in claim 6, wherein the means for moving an item from a leading location in the wrap around buffer to an unoccupied frame in the cache head portion operates responsive to occurrence of an open frame in the cache head portion.

8. Apparatus as claimed in claim 7, wherein the frames in the cache store hold two items.

9. A method of implementing a first-in, first-out queue on a segmented data storage system having a primary store and a backing store, comprising the steps performed by a computer of:

writing items to a tail portion of the primary store;

reading items from a head portion of the primary store;

responsive to occurrence of an item in the tail portion, determining if the primary store either currently stores items for the first-in, first-out queue or that the primary store is filled to a point indicating use of the backing store for storing items for the first-in, first-out queue;

if either determination of the preceding step is affirmative, moving the item from the tail portion to the backing store; and

responsive to both determinations being negative and the head portion having space, moving the item from the tail portion to the head portion.

10. The method of claim 9, and further comprising:

responsive to an item being in the backing store and the head portion having space, moving the item from the backing store to the head portion.

11. The method of claim 10, wherein an item moved from the tail portion is the item longest in the tail portion.

12. The method of claim 11, wherein an item moved from the backing store is the item longest in the backing store.

13. The item of claim 12, wherein an item read from the head portion is the item longest in the head portion.

14. A data communications network comprising:

at least a first node;

a communication channel;

a data buffer connecting the node to the communication channel;

a segmented data store for the data buffer including a primary store and a backing store;

means for writing items to and reading items from the primary store;

means for aging the items; and

means responsive to age of the items and excess demand for space to store the items in the primary store for swapping items in the middle by age of all the items between the primary store and the backing store.

15. The data communications network of claim 14, wherein the mean for swapping includes:

means for dividing space in the primary store into a head portion and a tail portion;

means for moving an oldest item from the tail portion into the backing store; and

means for moving an oldest item from backing store into the head portion.

16. The data communications network of claim 15, and further comprising:

means responsive to lack of excess demand for space in the primary store for moving items from the tail portion directly into the head portion.

17. The data communications network of claim 16, and further comprising:

means for returning vacated space in the head portion to the tail portion.

18. A predictive item swapping system for a segmented memory, comprising:

the segmented memory having a cache and a backing store;

means for writing items to and reading items from the cache;

means for aging any item written into the cache; and

means responsive to age of the items and excess demand for space in the cache for swapping items in the middle by age of all items written to but not yet read from the cache between the cache and the backing store.

19. A predictive item swapping system for a segmented memory as claimed in claim 18, wherein the mean for swapping includes:

means for dividing space in the cache into a head portion and a tail portion;

means for moving an oldest item from the tail portion into the backing store; and

means for moving an oldest item from backing store into the head portion.

20. A predictive item swapping system for a segmented memory as claimed in claim 19, and further comprising:

means responsive to lack of excess demand for space in the cache for moving items from the tail portion directly into the head portion.

21. A predictive item swapping system for a segmented memory as claimed in claim 20, and further comprising:

means for returning vacated space in the head portion to the tail portion.

22. A method of replacing items in a cache from a wrap around buffer, the method comprising:

dividing the cache into a tail portion and a head portion;

beginning ageing of items upon first being written to the tail portion of the cache;

responsive to demand, reading an oldest item in the cache from the head portion;

responsive to an excess number of items in the cache, moving an oldest item from the tail portion to the wrap around buffer;

responsive to an opening in the head portion and presence of an item in the wrap around buffer, moving an oldest item in the wrap around buffer to the head portion;

responsive to an opening in the head portion and lack of any items in the wrap around buffer, moving the oldest item in the tail portion directly to the head portion.