Method, system, and program for managing requests to a cache using flags to queue and dequeue data in a buffer

• US 6,438,651 B1
• Filed: 11/01/1999
• Issued: 08/20/2002
• Est. Priority Date: 11/01/1999
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Slane, Albert Alfonse
• Primary Examiner(s): Gossage, Glenn
• Application Number:
  US09/432,044
• Time in Patent Office: 1,023 Days
• Field of Search: 711/110, 711/109, 711/133, 711/134, 711/135, 711/136, 711/137, 711/141, 711/144, 711/118, 710/39, 710/52, 710/53, 710/54, 710/55, 710/56, 710/57
• US Class Current: 711/118
• CPC Class Codes: G06F 12/0875 with dedicated cache, e.g. instruction or stack
• CPC Class Codes: G06F 12/12 Replacement control

Abstract

Provided is a system, method, and program for managing read and write requests to a cache to process enqueue and dequeue operations for a queue. Upon receiving a data access request to a data block in a memory, a determination is made as to whether any data block is maintained in a cache line entry in the cache. If so, a cache line entry maintaining the data block is accessed to perform the data access request. A first flag, such as a read flag, associated with the accessed cache line entry is set “on” if the data access request is a read request. Further, if the data access request is a write request to update the data block in the memory, a second flag, such as a write flag, associated with the cache line entry including the data to update may be set “on”. The update data may be data to be enqueued onto a queue, where the queue may be, but is not limited to, a circular buffer in the memory having a head and tail pointer. Still further, a cache line having each first flag set “on” and each second flag set “on” may be selected if there is no cache line having each first flag set “on” and each second flag set “off”, and entries in the selected cache line having their second flag set “on” may be flushed.

Claims

1. A method for managing a cache, comprising:

receiving a data access request to a requested data block in a memory;

determining whether the requested data block is maintained in any cache line entry in the cache;

accessing a cache line entry if the data block is maintained in that cache line entry to perform the data access request;

setting a first flag associated with the accessed cache line entry “

on”

if the data access request is a read request;

receiving a request to allocate one cache line; and

selecting one cache line to allocate to the request based on a setting of the first flags for the cache line entries in the cache lines.

2. The method of claim 1, wherein the data access request is a read request to read the requested data block.

3. The method of claim 1, wherein each cache line includes a valid flag set “

on”

if the cache line includes valid data from the memory and set “

off”

if the cache line does not include valid data from the memory, further comprising;

selecting one cache line that has its valid flag set “

off”

if the requested data block is not maintained in any cache line entry,

fetching consecutive data blocks from the memory including the requested data block if that requested data block is not maintained in any cache line entry; and

writing the fetched consecutive data blocks to the selected cache line.

4. The method of claim 1, wherein the data access request is a write request to update the requested data block in the memory, further comprising:

writing update data to the requested data block in the accessed cache line entry when accessing that cache line entry; and

setting a second flag associated with the accessed cache line entry “

on”

, wherein a setting of the second flag for the cache line entries is considered in combination with the setting of the first flags when selecting one cache line to allocate.

5. The method of claim 4, further comprising receiving data to enqueue onto a queue in the memory, wherein the data access request is a write request to write the received data to the data block in the memory, and wherein the update data is the received data to enqueue.

6. The method of claims 5, wherein the queue is a circular buffer in the memory having a head pointer and a tail pointer.

7. The method of claim 6, wherein two cache lines are used to store data blocks in the circular buffer, wherein one cache line includes one data block adjacent to the head pointer and another cache line includes one data block adjacent to the tail pointer.

8. A method for managing a cache, comprising:

receiving a data access request to a requested data block in a memory;

determining whether the requested data block is maintained in any cache line entry in the cache, wherein each cache line includes a valid flag set “

on”

if the cache line includes valid data from the memory and set “

off”

if the cache line does not include valid data from the memory,;

accessing a cache line entry if the data block is maintained in that cache line entry to perform the data access request;

setting a first flag associated with the accessed cache line entry “

on”

if the data access request is a read request;

selecting one cache line that has its valid flag set “

off”

if the requested data block is not maintained in any cache line entry;

fetching consecutive data blocks from the memory including the requested data block if that requested data block is not maintained in any cache line entry;

writing the fetched consecutive data blocks to the selected cache line;

receiving a request to allocate one cache line if no cache line has the valid flag set “

off”

; and

selecting one cache line to allocate to the request having each first flag set “

on” and

each second flag set “

off”

.

9. The method of claim 8, further comprising:

selecting one cache line having each first flag set “

on” and

each second flag set “

on”

if there is no cache line a having each first flag set “

on” and

each second flag set “

off”

; and

flushing entries in the selected cache line having their second flag set “

on”

.

10. The method of claim 9, further comprising selecting one cache line having each first flag set “

off” and

each second flag set “

on”

if there is no cache line having each first flag set “

on”

.

11. The method of claim 10, wherein at least two cache lines are allocated to store data blocks in a circular buffer, wherein one cache line includes one data block adjacent to the head pointer and another cache line includes one data block adjacent to the tail pointer.

12. A system for managing a cache, comprising:

a cache;

means for receiving a data access request to a requested data block in a memory;

means for determining whether the requested data block is maintained in any cache line entry in the cache;

means for accessing a cache line entry if the data block is maintained in that cache line entry to perform the data access request;

means for setting a first flag associated with the accessed cache line entry “

on”

if the data access request is a read request;

means for receiving a request to allocate one cache line; and

means for selecting one cache line to allocate to the request based on a setting of the first flags for the cache line entries in the cache lines.

13. The system of claim 12, wherein the data access request is a read request to read the requested data block.

14. The system of claim 12, wherein each cache line includes a valid flag set “

on”

if the cache line includes valid data from the memory and set “

off”

if the cache line does not include valid data from the memory, further comprising;

means for selecting one cache line that has its valid flag set “

off”

if the requested data block is not maintained in any cache line entry;

means for fetching consecutive data blocks from the memory including the requested data block if that requested data block is not maintained in any cache line entry; and

means for writing the fetched consecutive data blocks to the selected cache line.

15. The system of claim 12, wherein the data access request is a write request to update the requested data block in the memory, further comprising:

means for writing update data to the requested data block in the accessed cache line entry when accessing that cache line entry; and

means for setting a second flag associated with the accessed cache line entry “

on”

, wherein a setting of the second flag for the cache line entries is considered in combination with the setting of the first flags when selecting one cache line to allocate.

16. The system of claim 15, further comprising means for receiving data to enqueue onto a queue in the memory, wherein the data access request is a write request to write the received data to the data block in the memory, and wherein the update data is the received data to enqueue.

17. The system of claims 16, wherein the queue is a circular buffer in the memory having a head pointer and a tail pointer.

18. The system of claim 17, wherein two cache lines are used to store data blocks in the circular buffer, wherein one cache line includes one data block adjacent to the head pointer and another cache line includes one data block adjacent to the tail pointer.

19. A system for managing a cache, comprising:

a cache;

means for receiving a data access request to a requested data block in a memory;

means for determining whether the requested data block is maintained in any cache line entry in the cache, wherein each cache line includes a valid flag set “

on”

if the cache line includes data from the memory and set “

off”

if the cache line does not include data from the memory;

means for accessing a cache line entry if the data block is maintained in that cache line entry to perform the data access request;

means for setting a first flag associated with the accessed cache line entry “

on”

if the data access request is a read request;

means for selecting one cache line that has its valid flag set “

off”

if the requested data block is not maintained in one cache line entry;

means for fetching consecutive data blocks from the memory including the requested data block to access if the requested data block is not maintained in one cache line entry;

means for writing the fetched consecutive data blocks to the selected cache line;

means for receiving a request to allocate one cache line;

means for selecting one cache line to allocate to the request based on a setting of the first flags for the cache line entries in the cache lines;

receiving a request to allocate one cache line if no cache line has the valid flag set “

off”

; and

means for selecting one cache line to allocate to the request having each first flag set “

on” and

each second flag set “

off”

.

20. The system of claim 19, further comprising:

means for selecting one cache line having each first flag set “

on” and

each second flag set “

on”

if there is no cache line having each first flag set “

on” and

each second flag set “

off”

; and

means for flushing entries in the selected cache line having their second flag set “

on”

.

21. The system of claim 20, further comprising means for selecting one cache line having each first flag set “

off” and

each second flag set “

on”

if there is no cache line having each first flag set “

on”

.

22. The system of claim 21, wherein at least two cache lines are allocated to store data blocks in a circular buffer, wherein one cache line includes one data block adjacent to the head pointer and another cache line includes one data block adjacent to the tail pointer.

23. An article of manufacture for managing a cache, the article of manufacture comprising computer readable storage media including at least one computer program embedded therein that is capable of causing a processor to perform:

receiving a data access request to a requested data block in a memory;

determining whether the requested data block is maintained in any cache line entry in the cache;

accessing a cache line entry if the data block is maintained in that cache line entry to perform the data access request;

setting a first flag associated with the accessed cache line entry “

on”

if the data access request is a read request;

receiving a request to allocate one cache line; and

selecting one cache line to allocate to the request based on a setting of the first flags for the cache line entries in the cache lines.

24. The article of manufacture of claim 23, wherein the data access request is a read request to read the requested data block.

25. The article of manufacture of claim 23, wherein each cache line includes a valid flag set “

on”

if the cache line includes valid data from the memory and set “

off”

if the cache line does not include valid data from the memory, further causing the processor to perform;

selecting one cache line that has its valid flag set “

off”

if the requested data block is not maintained in any cache line entry;

fetching consecutive data blocks from the memory including the requested data block if that requested data block is not maintained in any cache line entry; and

writing the fetched consecutive data blocks to the selected cache line.

26. The article of manufacture of claim 23, wherein the data access request is a write request to update the requested data block in the memory, further causing the processor to perform:

writing update data to the requested data block in the accessed cache line entry when accessing that cache line entry; and

setting a second flag associated with the accessed cache line entry “

on”

, wherein a setting of the second flag for the cache line entries is considered in combination with the setting of the first flags when selecting one cache line to allocate.

27. The article of manufacture of claim 26, further causing the processor to perform receiving data to enqueue onto a queue in the memory, wherein the data access request is a write request to write the received data to the data block in the memory, and wherein the update data is the received data to enqueue.

28. The article of manufacture of claims 27, wherein the queue is a circular buffer in the memory having a head pointer and a tail pointer.

29. The article of manufacture of claim 28, wherein two cache lines are used to store data blocks in the circular buffer, wherein one cache line includes one data block adjacent to the head pointer and another cache line includes one data block adjacent to the tail pointer.

30. An article of manufacture for managing a cache, the article of manufacture comprising computer readable storage media including at least one computer program embedded therein that is capable of causing a processor to perform:

receiving a data access request to a requested data block in a memory;

determining whether the requested data block is maintained in any cache line entry in the cache, wherein each cache line includes a valid flag set “

on”

if the cache line includes valid data from the memory and set “

off”

if the cache line does not include valid data from the memory,

accessing a cache line entry if the data block is maintained in that cache line entry to perform the data access request;

setting a first flag associated with the accessed cache line entry “

on”

if the data access request is a read request;

selecting one cache line that has its valid flag set “

off”

if the requested data block is not maintained in any cache line entry;

fetching consecutive data blocks from the memory including the requested data block if that requested data block is not maintained in any cache line entry;

writing the fetched consecutive data blocks to the selected cache line;

receiving a request to allocate one cache line if no cache line has the valid flag set “

off”

; and

selecting one cache line to allocate to the request having each first flag set “

on” and

each second flag set “

off”

.

31. The article of manufacture of claim 30, further causing the processor to perform:

selecting one cache line having each first flag set “

on” and

each second flag set “

on”

if there is no cache line having each first flag set “

on” and

each second flag set “

off”

; and

flushing entries in the selected cache line having their second flag set “

on”

.

32. The article of manufacture of claim 31, further causing the processor to perform selecting one cache line having each first flag set “

off” and

each second flag set “

on”

if there is no cache line having each first flag set “

on”

.

33. The article of manufacture of claim 32, wherein at least two cache lines are allocated to store data blocks in a circular buffer, wherein one cache line includes one data block adjacent to the head pointer and another cache line includes one data block adjacent to the tail pointer.