Address conflict detection system employing address indirection for use in a high-speed multi-processor system
First Claim
1. For use in a data processing system in which multiple requesters are each coupled to a first memory for requesting access to the first memory at a request address and wherein ones of the multiple requesters can come in conflict by attempting to gain access to the same request address, the data processing system further having memory priority logic coupled to each of the multiple requesters and to the first memory for selecting ones of the request addresses to be provided to the first memory, wherein the first memory determines whether each of the selected ones of the request addresses is a non-resident request address which is not resident within the first memory, the data processing system further having a second memory coupled to the memory priority logic, an improved conflict detection system, comprising:
- pointer generation means coupled to each of the multiple requesters for generating pointer signals indicative of a selected one of the multiple requesters requesting a selected one of the request addresses;
pointer queue means coupled to the first memory and to said pointer generation means for storing said pointer signals indicative of ones of the multiple requesters requesting non-resident request addresses; and
queue priority means coupled to said pointer queue means and to the memory priority logic for selecting from said pointer queue means predetermined ones of said stored pointer signals, and for providing said pointer signals to the memory priority logic, whereby the memory priority logic provides to the second memory a non-resident request address from one of the multiple requesters as indicated by said selected ones of said stored pointer signals.
11 Assignments
0 Petitions
Accused Products
Abstract
An improved conflict detection system for use in maintaining memory coherency in a multiprocessor, shared-cache memory system. The system includes a queue for storing pointers to request addresses that resulted in cache misses. The addresses associated with the queued pointers will generally be presented to a main memory for processing based on a predetermined priority scheme. The system further includes conflict detection logic which uses the queue pointers and the request addresses provided by associated ones of the processors to determine if any two of the queued requests are associated with the same request address. If so, a conflict exists, and the request queue later in time must be re-directed to cache instead of being presented to main memory to maintain cache coherency. The system further includes a mechanism for using pointers to detect conflict situations associated with flush and replacement cache operations. Because the conflict detection system queues pointers to addresses, instead of the addresses themselves, a large amount of silicon area can be saved. In addition, the system performs all conflict detection operations using full address compares to eliminate the detection of false conflicts.
126 Citations
21 Claims
-
1. For use in a data processing system in which multiple requesters are each coupled to a first memory for requesting access to the first memory at a request address and wherein ones of the multiple requesters can come in conflict by attempting to gain access to the same request address, the data processing system further having memory priority logic coupled to each of the multiple requesters and to the first memory for selecting ones of the request addresses to be provided to the first memory, wherein the first memory determines whether each of the selected ones of the request addresses is a non-resident request address which is not resident within the first memory, the data processing system further having a second memory coupled to the memory priority logic, an improved conflict detection system, comprising:
-
pointer generation means coupled to each of the multiple requesters for generating pointer signals indicative of a selected one of the multiple requesters requesting a selected one of the request addresses; pointer queue means coupled to the first memory and to said pointer generation means for storing said pointer signals indicative of ones of the multiple requesters requesting non-resident request addresses; and queue priority means coupled to said pointer queue means and to the memory priority logic for selecting from said pointer queue means predetermined ones of said stored pointer signals, and for providing said pointer signals to the memory priority logic, whereby the memory priority logic provides to the second memory a non-resident request address from one of the multiple requesters as indicated by said selected ones of said stored pointer signals. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. For use in a data processing system, memory priority logic coupled to multiple requesters and to a first memory to receive one or more request signals from each of the multiple requesters, wherein each of the request signals is associated with a stored memory address provided by one of the requesters, and wherein ones of the multiple requesters can come in conflict by providing the same stored memory address, the memory priority logic to select as selected request signals ones of the multiple request signals to be provided to the first memory, the first memory to detect for each of the selected request signals whether the associated stored memory address is a nonresident address which is not resident within the first memory, the first memory being further coupled to a second memory, the improved conflict and detection system, comprising:
-
pointer generation logic coupled to each of the multiple requesters to receive the one or more request signals from each of the multiple requesters, and to generate for each of the selected request signals associated pointer signals pointing to the associated stored memory address; a pointer queue coupled to the first memory and to said pointer generation logic to stores said pointer signals for each of the selected request signals if said associated selected request signals is associated with a non-resident address; and queue priority logic coupled to said pointer queue and to the memory priority logic to select from said pointer queue based on a predetermined priority scheme ones of said stored pointer signals as selected pointer signals, and to provide to the memory priority logic said selected pointer signals, whereby the memory priority logic, based on a second predetermined priority scheme, provides the stored memory address associated with said selected pointer signals to the second memory. - View Dependent Claims (9, 10, 11, 12, 13, 14, 15)
-
-
16. For use in a system having a plurality of storage devices coupled to a first memory, the first memory being coupled to an associated tag memory for providing tag signals indicative of the addresses resident within the first memory, each of the plurality of storage devices for presenting an associated stored memory address to the first memory for processing, and wherein ones of the storage devices can come in conflict by presenting the same stored memory address, the first memory further being coupled to a second memory, the improved conflict detection system, comprising:
-
priority means coupled to each of the plurality of storage devices for receiving each of the associated stored memory addresses, and for selecting ones of the associated stored memory addresses as selected addresses to be presented to the first memory; pointer generation means for generating pointer signals associated with each of said selected addresses and indicative of the associated storage device; queue means for storing said pointer signals for each of said associated selected addresses which is as non-resident address that is not resident within the first memory, wherein said queue means is capable of storing ones of said pointer signals for every storage device in the system; and queue priority means for selecting predetermined ones of said stored pointer signals as said selected pointer signals for presentation to said priority means, whereby said priority means provides the stored memory address from the storage device indicated by said selected pointer signals to the second memory. - View Dependent Claims (17, 18, 19, 20, 21)
-
Specification