System and method for handling storage consistency conflict

[0002] 1. Technical Field of the Invention

[0003] This invention pertains to memory coherency control. More particularly, it relates to a memory coherency control circuit utilizing a plurality of FIFO queues and a priority selection mechanism for avoiding deadlocks and assuring memory coherency.

[0004] 2. Background Art

[0005] Memory controllers which maintain multiple queues to capture storage requests from processors and input/output (I/O) devices are required to enforce memory coherence rules which govern the order in which these requests access storage. The combinatorial logic designed to enforce these rules is complex and requires a considerable amount of circuitry to implement. Also, because of the complex nature of the design required to enforce these rules, the implementation is prone to errors, requiring additional hardware releases and inflating development costs.

[0006] Memory controller designs which include multiple queues to enforce storage coherency also can experience deadlock problems. Deadlocks can occur when two requests compete for the same resource, preventing further progress.

[0007] It is an object of the invention to provide an improved coherency control mechanism.

[0008] It is a further object of the invention to provide an improved coherency control mechanism which avoids deadlock conditions.

[0009] It is an object of the invention to reduce circuit complexity and the likelihood of design implementation error in a coherency control mechanism.

[0010] In accordance with the invention, memory coherency is controlled. Responsive to a request including a request type and request memory address, relevant queues are examined for queued addresses matching the request memory address. Responsive to a request memory address, matching at least one of the queued addresses, the request is rejected. Following a retry latency, the request is retried.

[0011] In accordance with a further aspect of the invention, when the address of a read request matches queued address in a store queue, at least one request in the store queue is prioritized higher than all other queued requests.

[0012] Other features and advantages of this invention will become apparent from the following detailed description of the presently preferred embodiment of the invention, taken in conjunction with the accompanying drawings.

[0013] FIG. 1 is a high level system diagram illustrating operation of the coherency control apparatus of the invention.

[0014] FIGS. 2A and 2B, arranged as represented in FIG. 2, are a more detailed system diagram illustrating the coherency control circuit of the invention.

[0015] FIGS. 3A and 3D, arranged as represented in FIG. 3, are a timing diagram illustrating the operation of the coherency control circuit of FIG. 2.

[0016] Referring to FIG. 1, coherency control mechanism 30 is implemented within a memory controller chip which interfaces read and write requests from processor or I/O 10 over system bus 100 with respect to memory 20 over memory interface 111. Coherency control 30 includes processor read request FIFO queue 50 and store request FIFO queue 40. As illustrated in FIG. 1, queue 40 has been loaded with store requests to memory 20 locations A, B and C; and queue 50 has been loaded with read requests from memory 20 locations Z, Y, and X. (An I/O queue 60 is also shown, and such a queue will be described hereafter in connection with queue 104, FIG. 2B.)

[0017] In operation, in accordance with the preferred embodiment of the present invention, coherency control mechanism 30 receives requests from system bus 100, inspects the type and address information of each request, and compares this information with that for entries already received in specific queues 40, 50. As will be more fully described hereafter in connection with FIG. 2, the queues chosen for comparison are selected based upon the request type and the rules for managing storage coherency. If the address information of the received request, which is significant to coherency management, successfully compares to the same portion of an address (Z,Y,X,A,B, or C) stored in a queue 40 or 50 chosen for inspection by coherency control circuitry 30, then the received request is rejected by coherency control mechanism 30. This received request is then retried on system bus 100. Retrying the request on the system bus 100 provides an opportunity for the requests held in queue 40 or 50 to advance. The request, following a retry latency, is reissued by the requesting device 10 and is again received and compared to the appropriate queues 40, 50 selected by coherency control circuitry 30. If the request previously held in queue has not yet been serviced and retired, i.e. removed from the queue, the incoming request is again rejected and retried on the system bus by the coherency control mechanism, allowing queues 40, 50 to advance further. The retry of the same incoming requests continues in this fashion until the previously queued request, or requests, which cause the coherency conflict, are serviced and retired from queue 40 or 50.

[0018] Coupled with the coherency control mechanism is circuitry to alter the priority of store requests held in queue 40. If the address of an incoming read request successfully compares to a previously queued store queue 40 entry A, B or C (pending store conflict), like other requests, the read request is retried on system bus 100. However, for this case, the control circuitry used to service and retire queue requests is designed to prioritize store queue 40 requests A, B, C higher than all other queued storage requests Z, Y, X. This action ensures forward progress (through queue 40) so storage deadlocks can be avoided.

[0019] Coherency rules implemented by the preferred embodiment of the invention assure (1) that the order of update (that is, store) requests relative to subsequent read requests is preserved; and (2) that the contents of a storage address as it appeared at the time of receipt of a read request are returned to the requestor (processor), and not reflect subsequent updates to the same address.

[0020] In accordance with the first coherency rule, read requests are compared to store request queue 40 to identify a coherency conflict, and upon noting conflict, rejecting the request and in so doing take advantage of the ability to continue to honor queue requests (driving to memory) and, hopefully, allowing the conflicting storage request to move to storage 20 thereby enabling the request to read from storage to be honored. If coherency conflicts occur in subsequent requests, these are again rejected.

[0021] In accordance with the second coherency rule, anything queued in read queue 50 has been previously received (say, three addresses x, y and z) from processor 10 on system bus 100. This second rule dictates that the contents of storage address y should be read and returned to processor 10 as it appeared at the time the read request was received, and not reflect subsequent updates to the same address y. If such a coherency conflict occurs, at least one store is eliminated from the queue to assure forward progress and avoid deadlock.

[0022] For all request types, except those resulting in a pending store conflict, queue entries are serviced and retired in a manner that is independent of the action which updates a queue with a new request. The order in which physically distinct queues are serviced is independent of the coherency rules. The only request ordering which must be maintained is the order a particular queue is updated with requests (FIFO). This greatly reduces the complexity of the coherency controls by eliminating the need for tracking the relationship between, and progress of, requests held in separate queues. Also, the independence of incoming versus outgoing queue requests favors a queue's ability to drain, making it less likely for a coherency conflict to exist.

[0023] Referring to FIGS. 2A and 2B, in accordance with the preferred embodiment of the invention, coherency control mechanism 30 includes internal register 101, store address FIFO queue 102, processor read address FIFO queue 103, I/O read address FIFO queue 104, fully associative address compare circuits 105-107, logical OR 112, interface register 108, memory request prioritization circuit 109 and queued request select circuit 110.

[0024] System bus 100 is fed to internal register 101, the output of which is fed on bus 113 to queues 102-104. Control lines 114-116 selectively gate the output of address bus 113 to queues 102-104. I/O read address 0-N line 114 is fed to address compare circuit 105, store address 0-N line 115 is fed to address compare circuits 106 and 107, and processor read address 0-N line 116 is fed to address compare circuit 105. Queued addresses 0, 1, . . . ,X are fed on lines 131-133 to address compare 105; queued addresses 0,1, . . . ,Y are fed on lines 134-136 to address compare 106; and queued addresses 0,1, . . . ,Z are fed on lines 137-139 to address compare 107.

[0025] The output of queue 102 is fed on store address 0-X line 124 to queued request select circuit 110. The output of queue 103 is fed on processor read address 0-Y line 125 to queued request select circuit 110. The output of queue 104 is fed on I/O read address 0-Z line 126 to queued request select circuit 110.

[0026] The output of address compare 105 is fed on store queue address hit/miss line 121 to logical OR 112. The output of address compare 106 is fed on processor read queue address hit/miss line 122 to logical OR 112 and memory request prioritization 109. The output of address compare 107 is fed on I/O read queue address hit/miss line 123 to logical OR 112 and memory request prioritization 109. The output of logical OR 112 is fed to interface register 108 and thence to system bus request accept/reject line 117. The output of memory request prioritization 109 is fed to queued request select 110, the output of which is fed to memory interface 111.

[0027] Referring further to FIGS. 2A and 2B, in operation, a storage access request is received from a unit capable of sourcing a storage request, i.e. a processing unit 10 on System Bus 100, is latched in Interface Register 101. A request received in Interface Register 101 is forwarded to the appropriate queue, i.e. 102, 103, or 104, determined by the request type. Requests of type “Processor Read” are sent to Processor Read Queue 103, “I/O Read” requests are sent to I/O Read Queue 104, and store requests, either I/O or Processor which are directed to main memory, are sent to Store Queue 102. If all queue entries in the target queue are in use, the request is rejected until a request is retired, making a queue entry available. When a request is latched in its target queue, the request's address is compared to addresses stored in other queues which may comprise entries which may conflict with the address just latched. Address bits which define a coherency block address are compared in fully associative address compare circuits 105-107, and if a match is found, a rejection (hit) signal is latched from compare output lines 121, 122 and/or 123 in System Bus Interface Register 108 which is driven to System Bus 100. If no addresses match, an accept (miss) signal is latched in register 108 and driven on to System Bus 100.

[0028] Addresses belonging to read requests which successfully compare to the coherency block address of an entry stored in Store Queue 102 are rejected via the aforementioned mechanism. When such requests are rejected, Memory Request Prioritization logic 109 selects a store request from Store Queue 102 via queued request select circuit 110 as the next request to be delivered to Memory Interface 111. This ensures forward progress such that deadlock is avoided.

[0029] When no read store conflict exists, and if one or both read queues 103, 104 contain requests not yet retired, requests are selected and retired from these queues in a manner that provides fairness, i.e., the queues 103, 104 are accessed in a round-robin fashion. Read requests are selected and retired by a particular queue via Memory Request Prioritization 109 and Queued Request Select 110. Once selected, a read request is driven to Memory Interface 111.

[0030] When all read requests have been retired, Memory Request Prioritization 109 selects requests from Store Queue 102, if any exist, and delivers these to Memory Interface 111 until all store requests are retired, or a new read request is queued.

[0031] Referring to FIGS. 3A and 3B in connection with FIGS. 2A and 2B, let the initial queue states be as follows: store queue 102 contains addresses 500, 600 and 7050; processor read queue 103 contains addresses 300, 2000 and 1150; and I/O read queue 104 contains addresses 9060, 5020 and 4000.

[0032] In operation, an I/O Read request 114 for address 500 is driven on System Bus 100 at clock cycle 0. Also, Memory Request Prioritization 109 and Queued Request Select 110 select and drive an entry from Processor Read Address Queue 103 to Memory Interface 111.

[0033] During cycle 1 the I/O Read request of cycle 0 is latched in Interface Register 101 and a Processor Read request for address 820 is driven on System Bus 100. Memory Request Prioritization 109 and Queued Request Select 110 select an entry from I/O Read Address Queue 104 to be driven to Memory Interface 111 during this same cycle.

[0034] The I/O read request for address 500 is added to I/O Read Address Queue 104 in cycle 2 and the same address is compared to the address of each store request contained within Store Address Queue 102. Coincident with this cycle a Processor Read request for address 820 is latched in Interface Register 101.

[0035] The comparison of the I/O Read request's address to addresses in Store Queue 102 in cycle 2 results in a match (hit) on I/O Read Queue Hit/Miss line 123 since I/O Read address 500 successfully compares to store address 500. Successful comparison of a read request's address to a previously queued store address causes a queued store request to be prioritized for delivery to Memory Interface 111 by Memory Request Prioritization 109 and Queued Request select 110. During cycle 3 the I/O Read request to address 500 is rejected when a reject indication is latched in Interface Register 108 and is driven on to System Bus 100. Coincident with this, a Processor Read request to address 820 is queued in Processor Read Address Queue 103. Like the I/O Read request's address, the Processor Read address is compared to addresses contained within Store Address Queue 102. Since Processor Read address 820 does not successfully compare to any Store Address Queue 102 addresses, an accept indication is latched in Interface Register 108 and is driven on to System Bus 100 in cycle 4.

[0036] Since both read queues contain requests, Memory Request Prioritization 109 and Queued Request Select 110 alternates its selection of which queued request to drive to Memory Interface 111 during cycles 3 through 6.

[0037] During cycle 6 the previously rejected I/O read request to address 500 is driven on System Bus 100 by the device originating the request.

[0038] In cycle 7 the I/O read request is latched in Interface Register 101. Since all queued read requests have been retired, Memory Request Prioritization 109 and Queued Request Select 110 selects queued store requests from Store Address Queue 102 to be driven to Memory Interface 111.

[0039] The I/O read request latched in Interface Register 101 in cycle 7 is placed in I/O Read Address Queue 104 in cycle 8. Coincident with this, the I/O Read request's address is compared to all store addresses currently contained in Store Address Queue 102. In this same cycle Memory Request Prioritization 109 and Queued Request Select 110 selects the I/O Read request to be driven to Memory Interface 111.

[0040] Since in cycle 8 I/O Read address 500 does not successfully compare to any address in Store Address Queue 102, an accept indication is latched in Interface Register 108 and is driven to System Bus 100 in cycle 9. Coincident with cycle 9 the Memory Request Prioritization 109 and Queued Request Select 110 select a store to be driven to Memory Interface 111 from Store Address Queue 102 since all read requests from both read queues have been retired.

[0041] It is an advantage of the preferred embodiment of the invention that there is provided an improved coherency control mechanism.

[0042] It is a further advantage that there is provided an improved coherency control mechanism which avoids deadlock conditions.

[0043] It is a further advantage that there is provided reduced circuit complexity and likelihood of design implementation error in a coherency control mechanism.

[0044] It will be appreciated that, although specific embodiments of the invention have been described herein for purposes of illustration, various modifications may be made without departing from the spirit and scope of the invention. In particular, it is within the scope of the invention to provide a memory device, such as a transmission medium, magnetic or optical tape or disc, or the like, for storing signals for controlling the operation of a computer according to the method of the invention and/or to structure its components in accordance with the system of the invention.

[0045] Accordingly, the scope of protection of this invention is limited only by the following claims and their equivalents.