Method and apparatus for assuring cache coherency

Access to memory is facilitated by a cache memory access system that includes individual buffers for storing and processing data access commands asynchronously, while also assuring data coherency and avoiding deadlock. Data access commands are placed in discrete buffers, in dependence upon their type: read and write to and from a client process, fill from memory, and flush to memory. To maintain data coherency, the read and write commands are processed substantially sequentially. To optimize memory access, fills are processed as soon as they are submitted, and flushes may be given lower priority than fills. To avoid deadlock, fills are generated so as to be independent of all other commands. The use of discrete buffers for cache memory access is particularly well suited to pipeline processes.

If you were to search for Method and apparatus for assuring cache coherency using relaxed search criteria, these patents would come up:

I claim:

1. A memory access system comprising:

a memory that includes a plurality of memory blocks,

a cache memory that includes a plurality of cache locations,

a cache controller operably coupled to receive client commands from a client process, wherein the cache controller generates fill commands, flush commands, and memory commands, based on the client commands;

a fill processor operably coupled to process the fill commands and store a source memory block of the plurality of memory blocks into a destination cache location of the plurality of cache locations;

a flush processor operably coupled to process the flush commands and store a source cache location of the plurality of cache locations into a destination memory block of the plurality of memory blocks;

a memory command processor operably coupled to process the memory commands and transfer a data item to and from a cache location of the plurality of cache locations from and to the client process; and wherein the processing of the memorycommands by the memory command processor is dependent upon the fill commands in the fill buffer, and independent of the flush commands in the flush buffer.

2. The memory access system of claim 1, wherein:

the fill processor includes a fill buffer that temporarily stores the fill commands,

the flush processor includes a flush buffer that temporarily stores the flush commands, and

the memory command processor includes a memory command buffer that temporarily stores the memory commands.

3. The memory access system of claim 2, wherein the processing of the flush commands by the flush processor is dependent upon the memory commands in the memory command buffer, and independent of the fill commands in the fill buffer.

4. The memory access system of claim 2, wherein

the memory commands include read commands and write commands;

the memory command buffer includes a read/write command buffer and a write command buffer;

the read commands in the read/write command buffer are processed by the memory command processor;

the write commands in the read/write command buffer are stored in the write command buffer; and,

the memory command processor processes the write commands in the write command buffer independent of the memory commands in the read/write command buffer.

5. The memory access system of claim 4, wherein the processing of the flush command is dependent upon the write commands, and independent of the read commands.

6. The memory access system of claim 4, wherein the processing of at least one of the fill commands by the memory control is dependent upon:

at least one of the read commands in the memory command buffer having a first cache location, and

at least one of the fill commands in the fill buffer also having the first cache location.

7. The memory access system of claim 1, wherein

the fill commands, the flush commands, and the memory commands each include an associated cache location, and

the cache controller further includes a deallocation buffer for storing a selected cache location of the plurality of cache locations and an associated block address corresponding to one of the plurality of memory blocks, and wherein

the selected cache location and associated block address is removed from the deallocation buffer when the fill commands in the fill buffer, the flush commands in the flush buffer and the memory commands in the memory command buffer no longercontain the selected cache location as the associated cache location.

8. The memory access system of claim 7, wherein the selected cache location and associated block address is removed from the deallocation buffer when the cache controller generates at least one of the fill commands, the flush commands, or thememory commands containing the select block address as the associated cache location.

9. The memory access system of claim 1, wherein:

the cache controller generates the fill commands, flush commands, and memory commands relative to a plurality of logical indexes, and

the cache controller maintains a mapping of each of the plurality of logical indexes to a corresponding one of the plurality of cache locations,

and wherein the quantity of the plurality of cache locations is greater than the quantity of the plurality of logical indexes.

10. The memory access system of claim 1, wherein the processing of the fill commands by the fill processor is given priority over the processing of the flush commands by the flush controller.

11. A processing system comprising:

a client process;

a memory that includes a plurality of blocks,

a cache memory operably coupled to temporarily store at least some of the plurality of blocks at a plurality of cache locations in the cache memory;

an operation generator operably coupled to receive client commands from the client process, wherein each of the client commands includes a memory address associated with one of the plurality of blocks having a block address, and wherein theoperation generator generates fill commands, flush commands, and memory commands based on the client commands, such that:

each of the fill commands includes the block address and the cache location to which the block of memory is to be stored,

each of thee flush commands includes the block address and the cache location from which the block of memory is to be stored, and

each of the memory commands includes a cache address relative to the cache location, corresponding to the memory address relative to the block address;

a fill buffer operably coupled to temporarily store the fill commands;

a memory command buffer operably coupled to temporarily store the memory commands;

a flush buffer operably coupled to temporarily store the flush commands;

a memory control operably coupled to the fill buffer, the flush buffer, and the memory command buffer to process the fill commands, the flush commands, and the memory commands, and, therefrom, effect a transfer of data to perform the datacommands; and

wherein the operation generator generates the fill commands, the flush commands, and the memory control commands in a first sequential order, and the memory control processes the fill commands, the flush commands, and the memory commands in asecond sequential order.

12. The processing system of claim 11, wherein:

the memory commands are stored in the memory command buffer in a first memory command order, and

the memory control processes the memory commands in the first memory command order.

13. The processing system of claim 11, wherein

the client process includes a transmit buffer and a receive buffer for communicating data to and from the cache memory, and

the memory commands include read commands and write commands, and

wherein the memory control:

processes the read commands so as to effect the transfer of data from the cache memory to the receive buffer, and

processes the write commands so as to effect the transfer of data from the transmit buffer to the cache memory.

14. The processing system of claim 13, wherein the operation generator generates the memory commands in a first sequential order, and the memory control processes the memory commands in a second sequential order.

15. A method of memory access comprising the steps of:

receiving client commands from a client process;

generating fill commands, flush commands, and memory commands, based on the client commands;

storing the fill commands in a fill buffer;

storing the flush commands in a flush buffer;

storing the memory commands in a memory command buffer;

processing the fill commands to store a source memory block of a plurality of memory blocks into a destination cache location of a plurality of cache locations;

processing the flush commands to store a source cache location of the plurality of cache locations into a destination memory block of the plurality of memory blocks;

processing the memory commands to transfer a data item to and from a cache location of the plurality of cache locations from and to the client process;

wherein processing of the fill commands is independent of the processing of the flush commands and independent of the processing of the memory commands; and

the processing of the memory commands is dependent upon the processing of the fill commands.

16. The method of claim 15, wherein

the processing of the fill commands is independent of the processing of the flush commands and independent of the processing of the memory commands.

17. The method of claim 16, wherein

the processing of the flush commands is dependent upon the processing of the memory commands.

18. The method of claim 17, wherein

the processing of the flush commands is independent of the processing of the fill commands.

19. The method of claim 15, wherein

the client commands are received from the client process in a first sequential order; and

the processing of the fill commands, the flush commands, and the memory commands is in a second sequential order.

20. A memory access system comprising:

a memory that includes a plurality of memory blocks,

a cache memory that includes a plurality of cache locations,

a cache controller operably coupled to receive client commands from a client process, wherein the cache controller generates fill commands, flush commands, and memory commands, based on the client commands;

a fill processor operably coupled to process the fill commands and store a source memory block of the plurality of memory blocks into a destination cache location of the plurality of cache locations;

a flush processor operably coupled to process the flush commands and store a source cache location of the plurality of cache locations into a destination memory block of the plurality of memory blocks; and

a memory command processor operably coupled to process the memory commands and transfer a data item to and from a cache location of the plurality of cache locations from and to the client process; and wherein

the cache controller generates the fill commands and the flush commands in a sequential order, and

the processing of the fill commands and the flush commands are independent of the sequential order generated by the cache controller.

21. The memory access system of claim 20, wherein:

the fill processor includes a fill buffer that temporarily stores the fill commands,

the flush processor includes a flush buffer that temporarily stores the flush commands, and

the memory command processor includes a memory command buffer that temporarily stores the memory commands.

22. A processing system comprising:

a client process;

a memory that includes a plurality of blocks,

a cache memory operably coupled to temporarily store at least some of the plurality of blocks at a plurality of cache locations in the cache memory;

an operation generator operably coupled to receive client commands from the client process, wherein each of the client commands includes a memory address associated with one of the plurality of blocks having a block address, and wherein theoperation generator generates fill commands, flush commands, and memory commands based on the client commands, such that:

each of the fill commands includes the block address and the cache location to which the block of memory is to be stored,

each of thee flush commands includes the block address and the cache location from which the block of memory is to be stored, and

each of the memory commands includes a cache address relative to the cache location, corresponding to the memory address relative to the block address;

a fill buffer operably coupled to temporarily store the fill commands;

a memory command buffer operably coupled to temporarily store the memory commands;

a flush buffer operably coupled to temporarily store the flush commands;

a memory control operably coupled to the fill buffer, the flush buffer, and the memory command buffer to process the fill commands, the flush commands, and the memory commands, and, therefrom, effect a transfer of data to perform the datacommands; and

wherein the client process includes a transmit buffer and a receive buffer for communicating data to and from the cache memory, and

the memory commands include read commands and write commands, and wherein the memory control:

processes the read commands so as to effect the transfer of data from the cache memory to the receive buffer, and

processes the write commands so as to effect the transfer of data from the transmit buffer to the cache memory.

23. A method of memory access comprising the steps of:

receiving client commands from a client process;

generating fill commands, flush commands, and memory commands, based on the client commands;

storing the fill commands in a fill buffer;

storing the flush commands in a flush buffer;

storing the memory commands in a memory command buffer;

processing the fill commands to store a source memory block of a plurality of memory blocks into a destination cache location of a plurality of cache locations;

processing the flush commands to store a source cache location of the plurality of cache locations into a destination memory block of the plurality of memory blocks;

processing the memory commands to transfer a data item to and from a cache location of the plurality of cache locations from and to the client process;

wherein the client commands are received from the client process in a first sequential order; and

the processing of the fill commands, the flush commands, and the memory commands is in a second sequential order.