US5649157A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Memory controller with priority queues
Assignee: Hewlett Packard Development Co LP
•
Filing: 1995-03-30
•
Granted: 1997-07-15
•
Expires: 2015-03-30
Abstract
Abstract A memory controller receives reads, memory writes, and cache writes. A pending read is selected and issued to memory. When a response is received from memory, all cache writes are checked to determine whether any correspond to the pending read. If there is a corresponding cache write, the data from the corresponding cache write is used to respond to the pending read. Otherwise, prior memory writes arc checked to determine whether any correspond to the pending read. If there is a corresponding prior memory write, the data from the corresponding prior memory write is used to respond to the pending read. A coherency check from associated caches may also be performed, and the appropriate data returned to the processor that requested the read. Three queues may control the order in which memory access is performed. A read queue that contains read requests is typically given highest priority, and therefore reads are generally serviced first. A wait queue contains read requests and memory write requests, and is incremented to the pending read before the pending read is completed. As the wait queue is incremented, memory writes from the wait queue are entered onto a ready queue. Each request retrieved from the wait queue is checked against pending requests in the ready queue. Cache writes are entered directly onto the ready queue. When either a conflict is detected for the pending ready, or when the ready queue contains a certain amount of requests, the ready queue is flushed.
Inventors
- 👤 James B. Williams
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 14:52
CPC Classifications
G; G06; G06F; G06F13/00; G06F13/14; G06F13/16; G06F13/18
Claims Analysis
Total Claims: 22
Claim 1
Independent Claim
257 words
A memory controller for controlling access to a main memory from at least one processor having a local cache, the memory controller comprising: a read queue, having an input that receives read requests from the at least one processor and an output that provides the read requests in an order in which the read requests are received by the read queue; a wait queue, having an input that receives memory write requests and the read requests from the at least one processor and an output that provides the memory write requests and the read requests in an order in which the memory write requests and the read requests are received by the wait queue; a ready queue, having an input that receives ready requests including cache write requests from the at least one processor and memory write requests and read requests from the output of the wait queue, the ready queue having an output that provides the ready requests in an order in which the ready requests were received by the ready queue; and a control circuit, coupled to the read queue, the wait queue, and the ready queue, including circuitry that: processes read requests from the read queue; transfers ready requests from the wait queue to the ready queue until a read request corresponding to a currently processed read request is reached; identifies conflicts of the currently processed read request with requests in the ready queue to determine valid data; and returns the valid data to the at least one processor in response to read requests.
Claim 2
Dependent Claim
257 words
A memory controller for controlling access to a main memory from at least one processor having a local cache, the memory controller comprising: a read queue, having an input that receives read requests from the at least one processor and an output that provides the read requests in an order in which the read requests are received by the read queue; a wait queue, having an input that receives memory write requests and the read requests from the at least one processor and an output that provides the memory write requests and the read requests in an order in which the memory write requests and the read requests are received by the wait queue; a ready queue, having an input that receives ready requests including cache write requests from the at least one processor and memory write requests and read requests from the output of the wait queue, the ready queue having an output that provides the ready requests in an order in which the ready requests were received by the ready queue; and a control circuit, coupled to the read queue, the wait queue, and the ready queue, including circuitry that: processes read requests from the read queue; transfers ready requests from the wait queue to the ready queue until a read request corresponding to a currently processed read request is reached; identifies conflicts of the currently processed read request with requests in the ready queue to determine valid data; and returns the valid data to the at least one processor in response to read requests.
Claim 3
Dependent Claim
23 words
The memory controller of claim 1, wherein the control circuit processes each ready request in the ready queue when a conflict is identified.
Claim 4
Dependent Claim
59 words
The memory controller of claim 1, wherein the ready queue includes an indicator circuit having an output activated when an amount of requests stored in the ready queue exceeds a predetermined level, and wherein the control circuit processes at least part of the ready requests in the ready queue when the indicator output of the indicator circuit is activated.
Claim 5
Dependent Claim
93 words
The memory controller of claim 1, wherein the memory controller is coupled to a plurality of processors, a plurality of local caches corresponding to the plurality of processors, and a plurality of cache checkers corresponding to the plurality of local caches, each of the plurality of cache checkers providing an indication of whether the currently processed read request contains stale data, and wherein the control circuit receives the indications from the cache checkers and cancels the currently processed read request when the indication is that the currently processed read request contains stale data.
Claim 6
Dependent Claim
49 words
The memory controller of claim 1, wherein the memory write requests and cache write requests are stored in the wait queue and the ready queue as address locations, the memory controller further comprising temporary memory that contains data corresponding to the memory write requests and the cache write requests.
Claim 7
Dependent Claim
86 words
The memory controller of claim 1, further including: a wait queue comparator, coupled to the wait queue and the ready queue, that provides an indication of read requests and memory write requests in the wait queue corresponding to a request at the output of the ready queue; and a ready queue comparator, coupled to the wait queue and the ready queue, that provides an indication of whether any request in the ready queue corresponds to a request that is at the output of the wait queue.
Claim 8
Independent Claim
206 words
A method for controlling memory access to a main memory from a plurality of processors, the method comprising the steps of: receiving reads, memory writes, and cache writes from the plurality of processors; placing the reads onto a read queue; placing the reads and the memory writes onto a wait queue; and placing the cache writes onto a ready queue that has an input coupled to an output of the wait queue; requesting a response from the main memory for data corresponding to a pending read selected from the received reads, the pending read having been received from a first processor of the plurality of processors; determining whether a cache write corresponding to the pending read has been received by comparing the pending read with items in the ready queue, the cache write being indicative of a second processor of the plurality of processors expelling cache data from a local cache that is associated with the second processor; providing data expelled from the local cache to the first processor when a cache write corresponding to the pending read has been received; and providing the data from the main memory to the first processor when a cache write corresponding to the pending read has not been received.
Claim 9
Independent Claim
206 words
A method for controlling memory access to a main memory from a plurality of processors, the method comprising the steps of: receiving reads, memory writes, and cache writes from the plurality of processors; placing the reads onto a read queue; placing the reads and the memory writes onto a wait queue; and placing the cache writes onto a ready queue that has an input coupled to an output of the wait queue; requesting a response from the main memory for data corresponding to a pending read selected from the received reads, the pending read having been received from a first processor of the plurality of processors; determining whether a cache write corresponding to the pending read has been received by comparing the pending read with items in the ready queue, the cache write being indicative of a second processor of the plurality of processors expelling cache data from a local cache that is associated with the second processor; providing data expelled from the local cache to the first processor when a cache write corresponding to the pending read has been received; and providing the data from the main memory to the first processor when a cache write corresponding to the pending read has not been received.
Claim 10
Dependent Claim
91 words
The method of claim 7, further including steps of determining whether a memory write that corresponds to the pending read has been received prior to reception of the pending read, the memory write being indicative of a third processor of the plurality of processors writing data retained in a local cache associated with the third processor to the main memory; and providing data from the memory write that corresponds to the pending read to the first processor when a prior memory write that corresponds to the pending read has been received.
Claim 11
Dependent Claim
56 words
The method of claim 8, further including the steps of: writing data to the main memory in accordance with memory writes that were received prior to the pending read; writing data to the main memory in accordance with cache writes that have been received, and requesting from the main memory data corresponding to the pending read.
Claim 12
Dependent Claim
61 words
The method of claim 9, further including the steps of: determining whether at least one of a received read and a memory write corresponds to each cache write and memory write for which data is written to main memory; and labeling each of the received read and memory write that is determined to correspond to each cache write and memory write.
Claim 13
Dependent Claim
38 words
The method of claim 9, wherein the steps of writing data to the main memory in accordance with memory writes and cache writes includes the step of retrieving each cache write and memory write from the ready queue.
Claim 14
Dependent Claim
82 words
The method of claim 7, wherein the plurality of processors includes a plurality of local caches corresponding to the plurality of processors, and a plurality of cache checkers corresponding to the plurality of local caches, the method further comprising the steps of: determining whether any of the plurality of local caches contain recent data corresponding to the pending read; and providing data from a local cache as the valid data when the local cache contains recent data corresponding to the pending read.
Claim 15
Dependent Claim
54 words
The method of claim 7, further including the steps of: determining whether a predetermined number of memory writes received prior to the pending read and cache writes have been received: performing a number of the memory writes received prior to the pending read and the cache writes when a predetermined number have been received.
Claim 16
Independent Claim
217 words
An apparatus for controlling memory access to a main memory from a plurality of processors, the apparatus comprising: means for receiving reads, memory writes, and cache writes from the plurality of processors; means for placing the reads onto a read queue; means for placing the reads and the memory writes onto a wait queue; and means for placing the cache writes onto a ready queue that has an input coupled to an output of the wait queue; means for requesting a response from the main memory data corresponding to a pending read selected from the received reads, the pending read having been received from a first processor of the plurality of processors; means for determining whether a cache write corresponding to the pending read bas been received by comparing the pending read with items in the ready queue, the cache write being indicative of a second processor of the plurality of processors expelling cache data from a local cache that is associated with the second processor; means for providing data from the cache write to the first processor when a cache write corresponding to the pending read has been received; and means for providing the data from the main memory to the first processor when a cache write corresponding to the pending read has not been received.
Claim 17
Independent Claim
217 words
An apparatus for controlling memory access to a main memory from a plurality of processors, the apparatus comprising: means for receiving reads, memory writes, and cache writes from the plurality of processors; means for placing the reads onto a read queue; means for placing the reads and the memory writes onto a wait queue; and means for placing the cache writes onto a ready queue that has an input coupled to an output of the wait queue; means for requesting a response from the main memory data corresponding to a pending read selected from the received reads, the pending read having been received from a first processor of the plurality of processors; means for determining whether a cache write corresponding to the pending read bas been received by comparing the pending read with items in the ready queue, the cache write being indicative of a second processor of the plurality of processors expelling cache data from a local cache that is associated with the second processor; means for providing data from the cache write to the first processor when a cache write corresponding to the pending read has been received; and means for providing the data from the main memory to the first processor when a cache write corresponding to the pending read has not been received.
Claim 18
Dependent Claim
94 words
The apparatus of claim 14, further including: means for determining whether a memory write that corresponds to the pending read has been received prior to reception of the pending read, the memory write being indicative of a third processor of the plurality of processors writing data retained in a local cache associated with the third processor to the main memory; and means for providing data from the prior memory write that corresponds to the pending read to the first processor when a prior memory write that corresponds to the pending read has been received.
Claim 19
Dependent Claim
59 words
The apparatus of claim 15, further including: means for writing data to the main memory in accordance with memory writes that were received prior to the pending read; means for writing data to the main memory in accordance with cache writes that have been received, and means for requesting from the main memory data corresponding to the pending read.
Claim 20
Dependent Claim
62 words
The apparatus of claim 16, further including: means for determining whether at least one of a received read and a memory write corresponds to each cache write and memory write for which data is written to main memory; and means for labeling each of the received read and memory write that is determined to correspond to each cache write and memory write.
Claim 21
Dependent Claim
93 words
The apparatus of claim 14, wherein the plurality of processors includes a plurality of local caches corresponding to the plurality of processors, and a plurality of cache checkers corresponding to the plurality of local caches, and wherein the means for determining whether the response contains stale data further includes: means for determining whether any of the plurality of local caches contain recent data corresponding to the pending read; and means for providing data from a local cache as the valid data when a local cache contains recent data corresponding to the pending read.
Claim 22
Dependent Claim
56 words
The apparatus of claim 14, further including: means for determining whether a predetermined number of memory writes received prior to the pending read and cache writes have been received: means for performing a sufficient number of the memory writes received prior to the pending read and the cache writes when a predetermined number have been received.
References Cited (Backward Citations)
US3771137A
Cited
US4141067A
Cited
US4493019A
Cited
US4881163A
Cited
US4980852A
Cited
US5257374A
Cited
US5163142A
Cited
US5125083A
Cited
US5432918A
Cited
US5434993A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-07-14 | 2001-01-13 | 2001-07-15 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-07-14 | 2005-01-13 | 2005-07-15 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-07-14 | 2009-01-13 | 2009-07-15 | $7700.00 | Window Closed / Lapsed |