Mechanism for resolving ambiguous invalidates in a computer system
View Patent ↗The invention provides a system and method for resolving ambiguous invalidate messages received by an entity of a computer system. An invalidate message is considered ambiguous when the receiving entity cannot tell whether it applies to a previously victimized memory block or to a memory block that the entity is waiting to receive. When an entity receives such an invalidate message, it stores the message in its miss address file (MAF). When the entity subsequently receives the memory block, the entity “replays” the Invalidate message from its MAF by invalidating the block from its cache and issuing an Acknowledgement (Ack) to the entity that triggered issuance of the Invalidate message command.
1. A method for resolving ambiguous invalidates in a computer system having a plurality of data processing entities, a shared memory organized into a plurality of memory blocks, and one or more coherency units for maintaining status information over the memory blocks, at least some of the data processing entities having one or more caches and configured to issue requests for selected memory blocks, the method comprising:
deleting a clean version of a given memory block from the cache of a first data processing entity, and providing no notification to the one or more coherency units of the deletion;
issuing from the first data processing entity a request for read access to the given memory block;
receiving at the first data processing entity an invalidate targeting the given memory block prior to receipt of the given memory block;
storing the invalidate at the first data processing entity; and
replaying the invalidate upon receipt of the memory block at the first data processing entity.
2. The method of claim 1 further comprising:
storing the received memory block in the first data processing entity's cache; and
assigning a valid state to the memory block stored in the cache.
3. The method of claim 2 wherein the invalidate identifies a second data processing entity and the step of replaying comprises:
transitioning the memory block stored in the first processing entity's cache to an invalid state; and
issuing an Invalidate — Acknowledgement (lAck) to the second data processing entity.
4. The method of claim 3 wherein the computer system implements a relaxed consistency model that defines consistency markers whereby the data processing entities read and write memory blocks independent of having received all consistency markers for the memory blocks.
5. The method of claim 4 wherein
the consistency markers are implemented through the IAcks, and
the data processing entities read and write memory blocks, even though one or more IAcks remain outstanding for the memory blocks.
6. The method of claim 4 wherein the data processing entities include one of processors and input/output (I/O) subsystems.
7. The method of claim 4 wherein
the first data processing entity includes a miss address file (MAF) for tracking outstanding requests from the first data processing entity to the shared memory, and the invalidate is stored at the MAF.
8. The method of claim 1 wherein the one or more coherency units identify sharing entities through one or more coarse vectors.
9. The method of claim 1 wherein the one or more coherency units are free from recording sharers of memory blocks, and the method further comprises the step of broadcasting invalidates to all data processing entities.
10. The method of claim 1 wherein the one or more coherency units are free from issuing markers to the data processing entities in response to accessing the one or more coherency units.
11. The method of claim 10 further comprising providing an interconnect fabric within the computer system, the interconnect fabric providing a communication link among the data processing entities and the shared memory, the interconnect fabric supporting a plurality of channels, the channels configured to carry requests, probes and responses out of order.
12. A method for resolving ambiguous invalidates in a computer system having a plurality of data processing entities, a shared memory organized into a plurality of memory blocks, and one or more coherency units for maintaining status information over the memory blocks, at least some of the data processing entities having one or more caches and configured to issue requests for selected memory blocks, the method comprising:
deleting a clean version of a given memory block from the cache of a first data processing entity, and providing no notification to the one or more coherency units of the deletion;
issuing from the first data processing entity a request for the given memory block;
receiving at the first data processing entity an invalidate targeting the given memory block prior to receipt of the given memory block, the invalidate identifying a second data processing entity;
issuing an Invalidate — Acknowledgement (lAck) from the first data processing entity, prior to receiving the given memory block, to the second data processing entity;
storing the invalidate at the first data processing entity; and
replaying the invalidate upon receipt of the given memory block at the first data processing entity.
13. The method of claim 12 wherein
the replaying comprises the step of storing the given memory block at the first data processing entity's cache and assigning an invalid state to the given memory block as stored in the cache, and
the storing of the given memory block in the cache and the assigning of the block to the invalid state are performed as part of a single, atomic operation.
14. The method of claim 13 wherein one or more data processing entities are configured to withhold issuance of a memory block buffered at the one or more data processing entities in response to receiving a snoop message until the one or more data processing entities have received all outstanding IAcks for the memory block that is the subject of the snoop message.