Urgency based reordering for priority order servicing of memory requests

Patent metadata

Field	Value
Publication number	US-10223298-B2
Application number	US-201615376442-A
Country	US
Kind code	B2
Filing date	Dec 12, 2016
Priority date	Dec 12, 2016
Publication date	Mar 5, 2019
Grant date	Mar 5, 2019

Abstract

Embodiments of the invention include a machine-readable medium having stored thereon instructions, which if performed by a machine causes the machine to perform a method that includes assigning an urgency of requests based on a priority level for incoming requests and associated entries in at least one priority queue, assigning an urgency delta for anti-starvation that indicates urgency promotion to prevent starvation for the incoming requests in the at least one priority queue, determining conflict information including whether an incoming request is dependent on any request already present in the at least one queue, determining all contending requests within the at least one priority queue during a cycle, and sending a selected contending request to a memory controller for accessing memory.

First claim

What is claimed is:

1. A non-transitory machine-readable medium having stored thereon instructions, which if performed by a machine causes the machine to perform a method comprising:
assigning an urgency of requests based on a priority level for incoming requests and associated entries in at least one priority queue, wherein the at least one priority queue includes first and second priority queues;
assigning an urgency delta for anti-starvation that indicates urgency promotion to prevent starvation for the incoming requests in the at least one priority queue;
determining conflict information including whether an incoming request is dependent on any request already present in the at least one queue;
performing urgency inherency for all requests in the first priority queue that have a same address as an incoming request into the first priority queue;
determining all contending requests within the at least one priority queue during a cycle; and
sending a selected contending request to a memory controller for accessing memory.

2. The non-transitory machine-readable medium of claim 1 , further comprising:
selecting a contending request that is most urgent among all contending requests in the at least one priority queue based on the urgency and the urgency delta.

3. The non-transitory machine-readable medium of claim 1 , further comprising:
updating the urgency for each entry in the at least one priority queue every cycle based on the urgency delta for each entry.

4. The non-transitory machine-readable medium of claim 1 , wherein determining conflict information including whether an incoming request is dependent on any request already present in the at least one queue comprises determining conflict information for each request and associated entry in the first and second priority queues by determining whether each incoming request for the first priority queue is dependent on any request that is already present in the first queue and by determining whether each incoming request for the second priority queue is dependent on any request that is already present in the second queue.

5. The non-transitory machine-readable medium of claim 4 , further comprising: and
performing urgency inherency for all requests in the second priority queue that have a same address as an incoming request into the second priority queue;
setting a disable field for an entry when an associated incoming request in the first priority queue depends upon another request in the first priority queue, wherein determining all contending requests within the at least one priority queue during a cycle comprises determining for each request whether the request is valid, not disabled, and has read or write credits available for a memory controller.

6. An apparatus comprising:
an address conflict resolution circuit (ACRC), the ACRC to determine conflict information including whether an incoming request is dependent on any request already present in a priority queue; and
the priority queue coupled to the ACRC, the priority queue to assign an urgency based on a priority level for incoming requests and associated entries in the priority queue, to assign an urgency delta for urgency promotion to prevent starvation for the incoming requests and to determine all contending requests within the priority queue during a cycle,
wherein the priority queue to perform urgency inherency for all requests in the priority queue that have a same address as an incoming request into the priority queue.

7. The apparatus of claim 6 , wherein the priority queue to select a contending request that is most urgent among all contending requests in the priority queue and to send the selected contending request to an arbiter, wherein the priority queue to update the urgency for each entry in the priority queue every cycle based on the urgency delta for each entry.

8. The apparatus of claim 7 , wherein the ACRC to determine conflict information including whether an incoming request is dependent on any request already present in the priority queue based on determining whether an entry in a table of the ACRC has an address that matches an address of an incoming request, wherein each entry of the table of the ACRC includes an address field indicating an address of a request, a write count field indicating a number of writes in the priority queue to the address of the request, a read count field indicating a number of reads in the priority queue to the address of the request, a last write index indicating an index of a last write request to the address of the request in the priority queue, and a valid field indicating whether the entry is valid.

9. The apparatus of claim 8 , wherein the priority queue to set a disable field for an entry when an associated incoming request in the priority queue depends upon another request in the priority queue, wherein the priority queue to determine all contending requests within the at least one priority queue during a cycle based on determining for each request whether the request is valid, not disabled, and has read or write credits available for a memory controller.

10. A system comprising:
a first priority queue circuit to determine conflict information including whether an incoming request is dependent on any request already present in the first priority queue circuit, to assign an urgency based on a priority level for incoming requests and associated entries in the first priority queue circuit, to assign an urgency delta for urgency promotion to prevent starvation for the incoming requests, and to determine all contending requests within the first priority queue circuit during a cycle, wherein the first priority queue circuit to perform urgency inherency for all requests in the first priority queue circuit that have a same address as an incoming request into the first priority queue circuit;
a second priority queue circuit to determine all contending requests within the second priority queue circuit during the cycle; and
an arbiter to receive a first request from the first priority queue circuit and to receive a second request from the second priority queue circuit.

11. The system of claim 10 , wherein the arbiter to compare a first urgency level of the first request with a second urgency level of the second request for the cycle, select the first request when the first urgency level is greater than the second urgency level and select the second request when the second urgency level is greater than the first urgency level, and send the selected request to a memory controller, wherein the arbiter to select one of the first and second requests based on weighted round-robin arbitration when the second urgency level is equal the first urgency level.

12. The system of claim 10 , wherein the first priority queue circuit to select a contending request that is most urgent among all contending requests in the first priority queue circuit and to send the selected contending request to the arbiter, wherein the first priority queue circuit to update the urgency for each entry in the first priority queue circuit every cycle based on the urgency delta for each entry.

13. A processor comprising:
at least one processor core to execute instructions to process data;
a system agent unit coupled to the at least processor core, the system agent unit to receive requests from the at least one processor core; and
a memory aggregator coupled to the system agent unit, the memory aggregator includes a first priority queue circuit and a second priority queue circuit, wherein the first priority queue circuit to determine conflict information including whether an incoming request from the system agent unit is dependen

Assignees

• Chhabra Siddhartha
• Long Men
• Ornelas Carlos Cornelas
• Borrayo Edgar
• Narendra Trivedi Alpa T
• Intel Corp

Inventors

• Chhabra Siddhartha
• Long Men
• Ornelas Carlos Cornelas
• Borrayo Edgar
• Narendra Trivedi Alpa T

Classifications

• G06F13/18

  based on priority control (G06F13/1605 takes precedence) · CPC title

• G06F13/1642

  with request queuing · CPC title

• G06F13/1626 Primary

  by reordering requests · CPC title