Computer system with adaptive memory arbitration scheme

• US 6,286,083 B1
• Filed: 07/08/1998
• Issued: 09/04/2001
• Est. Priority Date: 07/08/1998
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Compaq Computer Corporation (HP Inc.)
• Inventors: Coffee, C. Kevin, Chin, Kenneth T., Collins, Michael J., Jones, Phillip M., Johnson, Jerome J., Piccirillo, Gary J., Lester, Robert A., Stevens, Jeffrey C.
• Primary Examiner(s): Nguyen, Hiep T.
• Assistant Examiner(s): Portka, Gary J.
• Application Number:
  US09/112,000
• Time in Patent Office: 1,154 Days
• Field of Search: 711/150, 711/151, 711/158, 710/41, 710/42, 710/44, 710/113, 710/116, 710/241, 710/244
• US Class Current: 711/151
• CPC Class Codes: G06F 13/1605 based on arbitration arbitration in handling access to a common bus or bus system G06F13/36

Abstract

A computer system includes an adaptive memory arbiter for prioritizing memory access requests, including a self-adjusting, programmable request-priority ranking system. The memory arbiter adapts during every arbitration cycle, reducing the priority of any request which wins memory arbitration. Thus, a memory request initially holding a low priority ranking may gradually advance in priority until that request wins memory arbitration. Such a scheme prevents lower-priority devices from becoming “memory-starved.” Because some types of memory requests (such as refresh requests and memory reads) inherently require faster memory access than other requests (such as memory writes), the adaptive memory arbiter additionally integrates a nonadjustable priority structure into the adaptive ranking system which guarantees faster service to the most urgent requests. Also, the adaptive memory arbitration scheme introduces a flexible method of adjustable priority-weighting which permits selected devices to transact a programmable number of consecutive memory accesses without those devices losing request priority.

Claims

1. A method for adjusting an adaptive variable that represents the priority between a first group of requests and a second group of requests during a memory arbitration cycle in a computer system, the winning request chosen from the group with highest priority, including:

(a) determining the maximum number n, for n greater than 1, of consecutive winning requests that may be chosen from the first group;

(b) determining the maximum number k, for k greater than 1, of consecutive winning requests that may be chosen from the second group;

(c) determining how many of the n+k−

1 most recent winning requests belong to the first request group;

(d) determining how many of the n+k−

1 most recent winning requests belong to the second request group; and

(e) adjusting the adaptive priority based on the n+k−

1 most recent winning requests.

2. A method as in claim 1 including:

adjusting the adaptive priority during the current arbitration cycle to award priority to the second request group in a later arbitration cycle if fewer than k of the n+k−

1 most recent winning requests belong to the second request group; and

adjusting the adaptive priority during the current arbitration cycle to award priority to the first request group in a later arbitration cycle if fewer than n of the n+k−

1 most recent winning requests belong to the first request group.

3. A method as in claim 1 including a value of n that is not equal to the value of k.

4. A method as in claim 1 including a value of n that is equal to the value of k.

5. A method as in claim 1 including a value of n that is programmable.

6. A method as in claim 1 including a value of k that is programmable.

7. A method as in claim 1 wherein the first request group of requests contains only a single request.

8. A method as in claim 7 wherein the second request group of requests contains only a single request.

9. A computer system comprising:

a memory device for storing data;

a processor coupled to said memory device and which transmits memory requests to said memory device;

a first master device coupled to said memory device via a first expansion bus, said first master device being capable of transmitting memory requests to said memory device;

a second master device coupled to said memory device via a second expansion bus, said second master device being capable of transmitting memory requests to said memory device; and

a bridge logic coupled to said memory device, said processor, and said first expansion bus, said bridge logic comprising;

a memory arbiter which classifies the memory requests into a first request group and a second request group, said memory arbiter capable of selecting one of the memory requests during an arbitration cycle as a winning request to transact with said memory device, wherein the winning request is selected based on an adaptive arbitration scheme which adapts according to the winning request,

wherein the adaptive arbitration scheme includes a first adaptive variable that determines the priority between requests belonging to the first request group and requests belonging to the second request group;

wherein said memory arbiter arbitrates between the first and second request groups by awarding no more than n number of winning requests to the first request group and no more than k number of winning requests to the second request group within a sequence of n+k−

1 winning requests;

wherein the first request group comprises a memory to processor read requests and memory to expansion bus read requests, the expansion bus read requests including read requests transmitted by said first and second master devices, and wherein the adaptive arbitration scheme further includes a second adaptive variable that determines the priority between the processor read request and the expansion bus read requests;

wherein if said memory arbiter chooses a processor read request as the winning request during the current arbitration cycle, then said memory arbiter adjusts the second adaptive variable to award priority to the expansion bus read requests during the following arbitration cycle, and if said memory arbiter chooses an expansion bus read request as the winning request during the current arbitration cycle, then said memory arbiter adjusts the second adaptive variable to award priority to processor read requests during the following arbitration cycle;

wherein the expansion bus read requests include a memory to PCI read request and a memory to GCI read request, and wherein the adaptive arbitration scheme includes a third adaptive variable that determines the priority between the PCI and GCI read requests; and

a memory controller that receives the memory requests and asserts control, data, and address signals to said memory device to transact the winning request.

10. A computer system as in claim 9 wherein:

if said memory arbiter chooses a PCI read request as the winning request during the current arbitration cycle, then said memory arbiter adjusts the third adaptive variable to award priority to GCI read requests during a later arbitration cycle;

if said memory arbiter chooses a GCI read request as the winning request during the current arbitration cycle, then said memory arbiter adjusts the third adaptive variable to award priority to PCI read requests during a later arbitration cycle.

11. A computer system as in claim 10 wherein the first request group further includes expansion bus write requests to memory, and wherein said memory arbiter fixes the priority of expansion bus write requests below the priority of processor read requests and below the priority of expansion bus read requests.

12. A computer system as in claim 11 wherein the expansion bus write requests include a PCI write request and a GCI write request and wherein the adaptive arbitration scheme further includes a fourth adaptive variable that determines the priority between PCI and GCI write requests.

13. A computer system as in claim 12 wherein:

if said memory arbiter chooses a PCI write request as the winning request during the current arbitration cycle, then said memory arbiter adjusts the fourth adaptive variable to award priority to GCI write requests during a later arbitration cycle;

if said memory arbiter chooses a GCI write request as the winning request during the current arbitration cycle, then said memory arbiter adjusts the fourth adaptive variable to award priority to PCI write requests during a later arbitration cycle.

14. A computer system as in claim 13 wherein the first request group further includes a processor write request, and wherein said memory arbiter fixes the priority of processor write requests below the priority of processor read requests and above the priority of expansion bus read requests.

15. A computer system comprising:

a memory device for storing data;

a processor coupled to said memory device and which transmits memory requests to said memory device;

a first master device coupled to said memory device via a first expansion bus, said first master device being capable of transmitting memory requests to said memory device; and

a bridge logic coupled to said memory device, said processor, and said first expansion bus, said bridge logic comprising;

a memory arbiter which classifies the memory requests into a first request group, a second request group and a third memory request group, said memory arbiter capable of selecting one of the memory requests during an arbitration cycle as a winning request to transact with said memory device, wherein the winning request is selected based on an adaptive arbitration scheme which adapts according to the winning request;

wherein the adaptive arbitration scheme includes a first adaptive variable that determines the priority between requests belonging to the first request group and requests belonging to the second request group, and wherein said memory arbiter fixes the priority of the third memory request group below the priority of the first memory request group and below the priority of the second memory request group;

wherein the second memory request group includes a PCI request and a GCI request, and wherein said memory arbiter arbitrates between PCI and GCI requests by awarding no more than n number of winning requests to PCI requests and no more than k number of winning requests to GCI requests throughout a sequence of n+k−

1 winning requests; and

a memory controller that receives the memory requests and asserts control, data, and address signals to said memory device to transact the winning request.

16. A computer system as in claim 15 wherein n does not equal k.

17. A computer system as in claim 15 wherein n equals k.

18. A computer system as in claim 15 wherein n is programmable.

19. A computer system as in claim 15 wherein k is programmable.

20. A computer system comprising:

a memory device for storing data;

a processor coupled to said memory device and which transmits memory requests to said memory device;

a first master device coupled to said memory device via a first expansion bus, said first master device being capable of transmitting memory requests to said memory device;

a second master device coupled to said memory device via a second expansion bus, said second master device being capable of transmitting memory requests to said memory device; and

a bridge logic connected to said memory device, said processor, said first expansion bus, and said second expansion bus, said bridge logic comprising;

a memory arbiter that classifies the memory requests into at least a first request group and a second request group, awards memory access to one of the memory requests based on a set of flexible arbitration rules, and alters the arbitration rules based on which memory request is awarded memory access, and wherein the flexible arbitration rules determine the priority between the first request group the second request group to be awarded memory access;

wherein said memory arbiter arbitrates between the first and second request groups by awarding no more than n number of memory accesses to the first request group and no more than k number of memory accesses to the second request group throughout a sequence of n+k−

1 memory accesses;

wherein the first request group includes PCI read requests and GCI read requests and wherein the flexible arbitration rules determine the memory access priority among the expansion bus read requests;

said memory arbiter alternates between awarding memory access to PCI requests and awarding memory access to GCI requests; and

a memory controller that asserts appropriate signals to said memory device to perform the memory accesses.

21. A computer system comprising:

a memory device for storing data;

a processor coupled to said memory device and which transmits memory requests to said memory device;

a first master device coupled to said memory device via a first expansion bus, said first master device being capable of transmitting memory requests to said memory device; and

a second master device coupled to said memory device via a second expansion bus, said second master device being capable of transmitting memory requests to said memory device; and

a bridge logic connected to said memory device, said processor, said first expansion bus, and said second expansion bus, said bridge logic comprising;

a memory arbiter that classifies the memory requests into at least a first request group and a second request group, determines priority and awards memory access to one of the memory request based on a set of flexible arbitration rules, and alters the arbitration rules based on which memory request is awarded memory access;

wherein said memory arbiter arbitrates between the first and second request groups by awarding no more than n number of memory accesses to the first request group and no more than k number of memory accesses to the second request group throughout a sequence of n+k−

1 memory accesses;

wherein the first request group includes expansion bus read requests, processor requests and expansion bus write requests, and wherein the flexible arbitration rules determine the memory access priority among the processor requests, among the expansion bus read requests, and among the expansion bus write requests;

the expansion bus write requests include PCI write requests and GCI write requests, and said memory arbiter alternates between awarding memory access to PCI requests and awarding memory access to GCI requests; and

a memory controller that asserts appropriate signals to said memory device to perform the memory accesses.

22. A method for selecting a memory request to service among a plurality of pending memory requests in a computer system comprising:

classifying the memory requests into a first request group and a second request group based on request type, and determining the priority between the first request group and the second request group based on a first adaptive variable;

(b) dividing memory requests within the first request group into processor read requests and expansion bus read requests, and determining the priority between the processor read requests and the expansion bus read requests based on a second adaptive variable;

(c) dividing the expansion bus read requests into PCI read requests and GCI read requests, and determining the priority among expansion bus read requests based on a third adaptive variable;

(d) selecting one of the memory requests as a winning request based on a set of predetermined arbitration rules; and

(f) adjusting the arbitration rules based on which request was selected as the winning request by;

(f1) adjusting the third adaptive variable during the current arbitration cycle to award priority to the GCI read requests in a later arbitration cycle if the winning request is a PCI read request for the current arbitration cycle; and

(f2) adjusting the third adaptive variable during the current arbitration cycle to award priority to the PCI read requests in a later arbitration cycle if the winning request is a GCI read request for the current arbitration cycle.

23. A method for selecting a memory request to service among a plurality of pending memory requests in a computer system comprising:

(a) classifying the memory requests into a first request group and a second request group based on request type, and determining the priority between the first request group and the second request group based on a first adaptive variable;

(b) dividing memory requests within the first request group into processor read requests and expansion bus read requests, and determining the priority between the processor read requests and the expansion bus read requests based on a second adaptive variable;

(c) classifying expansion bus write requests into the first request group, and including using a fourth adaptive variable to arbitrate among expansion bus write requests;

(d) dividing the expansion bus write requests into PCI write requests and GCI write requests;

(e) selecting one of the memory requests as a winning request based on a set of predetermined arbitration rules; and

(f) adjusting the arbitration rules based on which request was selected as the winning request by;

(f1) adjusting the second adaptive variable during the current arbitration cycle to award priority to expansion bus read requests in a later arbitration cycle if a processor read request is chosen as the winning request for the current arbitration cycle;

(f2) adjusting the second adaptive variable during the current arbitration cycle to award priority to processor read requests in a later arbitration cycle if an expansion bus read request is chosen as the winning request for the current arbitration cycle;

(f3) adjusting the fourth adaptive variable during the current arbitration cycle to award priority to a PCI write requests in a later arbitration cycle if a GCI write request is chosen as the winning request for the current arbitration cycle; and

(f4) adjusting the fourth adaptive variable during the current arbitration cycle to award priority to the GCI write requests in a later arbitration cycle if a PCI write request is chosen as the winning request for the current arbitration cycle.

24. A method as in claim 23 further including classifying processor write requests into the first request group and assigning a fixed priority to processor write requests with respect to the priorities of all other requests within the first request group.

25. A method for prioritizing pending memory requests in a computer system comprising:

classifying the pending memory requests into memory request groups, the memory request groups including a first request group and a second request group;

using a first adaptive variable to determine the priority between the first and second request groups;

choosing a winning request from the pending memory requests;

adjusting the first adaptive variable based on the winning request;

dividing the first request group into processor requests, expansion bus read requests, and expansion bus write requests;

using a second adaptive variable to arbitrate between processor requests and expansion bus read requests;

fixing the priority of the expansion bus write requests with respect to the processor request and expansion bus read request priorities;

dividing the expansion bus write requests into PCI write requests and GCI write requests;

using a third adaptive variable to arbitrate between GCI write requests and PCI write requests; and

adjusting the third adaptive variable based on the winning request.

26. A method as in claim 25 including:

adjusting the third adaptive variable to award priority to GCI write requests if the winning request is a PCI write request; and

adjusting the third adaptive variable to award priority to PCI write requests if the winning request is a GCI write request.