US 5,649,157 A · Memory controller with priority queues

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.

Claims19

Dependent claims

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.

7 more elements

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.

7 more elements

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.

7 more elements

Dependencies are inferred from the claim text.

Memory controller with priority queues

Life of this patent

Memory controller with priority queues

Life of this patent

Abstract

Claims19