# US 6,295,581 B1 · Method and apparatus for assuring cache coherency > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 6,295,581 B1 - Document ID: US6295581B1 - Status: Granted - Kind: B1 - Application number: 09/026,942 - Filed: 1998-02-20 - Granted: 2001-09-25 - Earliest claimed: 1998-02-20 - Assignees: ATI Technologies, Inc. - Inventors: John E. DeRoo - Web page: https://patentgrep.com/patent/US6295581B1 ## CPC - G06F 11/182: {based on mutual exchange of the output between redundant processing components} - G06F 13/1621: {by maintaining request order} - G06F 11/1683: {at instruction level} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract 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. ## Claims ### 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 memory commands 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. ### Claim 2 (depends on 1) 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. ### Claim 3 (depends on 2) 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. ### Claim 4 (depends on 2) 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. ### Claim 5 (depends on 4) 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. ### Claim 6 (depends on 4) 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. ### Claim 7 (depends on 1) 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 longer contain the selected cache location as the associated cache location. ### Claim 8 (depends on 7) 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 the memory commands containing the select block address as the associated cache location. ### Claim 9 (depends on 1) 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. ### Claim 10 (depends on 1) 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. ### Claim 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 the operation 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 data commands; 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 a second sequential order. ### Claim 12 (depends on 11) 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. ### Claim 13 (depends on 11) 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. ### Claim 14 (depends on 13) 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. ### Claim 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. ### Claim 16 (depends on 15) 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. ### Claim 17 (depends on 16) The method of claim 16, wherein the processing of the flush commands is dependent upon the processing of the memory commands. ### Claim 18 (depends on 17) The method of claim 17, wherein the processing of the flush commands is independent of the processing of the fill commands. ### Claim 19 (depends on 15) 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. ### Claim 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. ### Claim 21 (depends on 20) 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. ### Claim 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 the operation 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 data commands; 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. ### Claim 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.