Computer system with adaptive memory arbitration scheme

• US 20010010066A1
• Filed: 02/15/2001
• Published: 07/26/2001
• Est. Priority Date: 07/08/1998
• Status: Active Grant

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Collins, Michael J., Lester, Robert A., Coffee, C. Kevin, Chin, Kenneth T., Jones, Phillip M., Johnson, Jerome J., Piccirillo, Gary J., Stevens, Jeffrey C.
• Granted Patent: US 6,505,260 B2
• Time in Patent Office: Days
• US Class Current: 711/108
• 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 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 memory request groups, said memory arbiter being 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; 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.

2. A computer system as in

claim 1

wherein the memory request groups comprise a first request group and a second request group, and 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.

3. A computer system as in

claim 2

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.

4. A computer system as in

claim 3

wherein n does not equal k.

5. A computer system as in

claim 3

wherein n equals k.

6. A computer system as in

claim 3

wherein n is programmable.

7. A computer system as in

claim 3

wherein k is programmable.

8. A computer system as in

claim 3

wherein said memory arbiter classifies only one request into the first request group.

9. A computer system as in

claim 8

wherein said memory arbiter classifies only one request into the second request group.

10. A computer system as in

claim 3

wherein said memory arbiter prioritizes memory requests within the second request group according to a fixed arbitration scheme.

11. A computer system as in

claim 10

wherein the second request group includes an AGP request.

12. A computer system as in

claim 3

further including 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.

13. A computer system as in

claim 12

wherein the first request group comprises a memory to processor read request 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.

14. A computer system as in

claim 13

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.

15. A computer system as in

claim 14

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 further includes a third adaptive variable that determines the priority between the PCI and GCI read requests.

16. A computer system as in

claim 15

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.

17. A computer system as in

claim 16

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.

18. A computer system as in

claim 17

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.

19. A computer system as in

claim 18

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.

20. A computer system as in

claim 19

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.

21. A computer system as in

claim 2

wherein the memory requests include a refresh request and wherein the refresh request is always chosen as the winning request.

22. A computer system as in

claim 2

wherein the memory requests further include a processor write to memory request, and wherein said memory arbiter assigns a fixed memory arbitration priority to the processor write request with respect to all other memory requests.

23. A computer system as in

claim 2

wherein the memory request groups further include a third memory 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.

24. A computer system as in

claim 23

further including 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.

25. A computer system as in

claim 23

wherein the first request group includes processor requests, the second request group comprises expansion bus read requests, the expansion bus read requests including read requests from said first master device and read requests from said second master device, and the third memory request group comprises expansion bus write requests, the expansion bus write requests including write requests from said first master device and write requests from said second master device.

26. A computer system as in

claim 25

wherein the adaptive arbitration scheme includes a second adaptive variable, and wherein said memory arbiter prioritizes requests within the third memory request group based on the second adaptive variable.

27. A computer system as in

claim 26

wherein said memory arbiter alternates between choosing an expansion bus write request from said first master device as the winning request and choosing an expansion bus write request from said second master device as the winning request.

28. A computer system as in

claim 25

wherein the adaptive arbitration scheme includes a third adaptive variable, and wherein said memory arbiter prioritizes requests within the second memory request group based on the third adaptive variable.

29. A computer system as in

claim 28

wherein said memory arbiter alternates between choosing an expansion bus read request from said first master device as the winning request and choosing an expansion bus read request from said second master device as the winning request.

30. A computer system as in

claim 2

wherein the adaptive arbitration scheme includes a second adaptive variable, and wherein said memory arbiter prioritizes requests within the second memory request group based on the second adaptive variable.

31. A computer system as in

claim 30

further including 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.

32. A computer system as in

claim 23

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.

33. A computer system as in

claim 32

wherein n does not equal k.

34. A computer system as in

claim 32

wherein n equals k.

35. A computer system as in

claim 32

wherein n is programmable.

36. A computer system as in

claim 32

wherein k is programmable.

37. 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 memory request groups, awards memory access to one of the memory requests based on a set of adjustable arbitration rules, and alters the arbitration rules based on which memory request is awarded memory access.

38. A computer system as in

claim 37

wherein the memory request groups include at least a first request group and a second request group, and wherein the flexible arbitration rules determine the priority between the first request group the second request group to be awarded memory access.

39. A computer system as in

claim 38

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.

40. A computer system as in

claim 39

wherein n does not equal k.

41. A computer system as in

claim 39

wherein n equals k.

42. A computer system as in

claim 39

wherein n is programmable.

43. A computer system as in

claim 39

wherein k is programmable.

44. A computer system as in

claim 39

wherein the first request group further includes expansion bus read requests and wherein the flexible arbitration rules determine the memory access priority among the expansion bus read requests.

45. A computer system as in

claim 44

wherein:

the expansion bus read requests include PCI read requests and GCI read requests;

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

said bridge logic further includes a memory controller that asserts appropriate signals to said memory device to perform the memory accesses.

46. A computer system as in

claim 44

wherein the first request group further includes a processor request, and wherein the flexible arbitration rules determine the memory access priority between processor requests and expansion bus read requests.

47. A computer system as in

claim 46

wherein said memory arbiter alternates between awarding memory access to processor requests and expansion bus read requests, and wherein said bridge logic further includes a memory controller that asserts appropriate signals to said memory device to perform the memory accesses.

48. A computer system as in

claim 46

wherein the first request group further includes expansion bus write requests and wherein the flexible arbitration rules determine the memory access priority among the expansion bus write requests.

49. A computer system as in

claim 48

wherein:

the expansion bus write requests include PCI write requests and GCI write requests;

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

said bridge logic further includes a memory controller that asserts appropriate signals to said memory device to perform the memory accesses.

50. A computer system as in

claim 48

wherein the first request group further includes a processor write request, and wherein said memory arbiter fixes the memory access priority of the processor write request with respect to the memory access priorities of other requests in the first request group.

51. A computer system as in

claim 50

wherein said memory arbiter fixes the memory access priority of the processor write request above the priority of the expansion bus read requests and above the priority of the expansion bus write requests.

52. A computer system as in

claim 50

wherein the memory requests further include a refresh request, and wherein said memory arbiter fixes the memory access priority of the refresh request with respect to the memory access priorities of all other memory requests.

53. 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 memory request groups;

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

(c) adjusting the arbitration rules based on which request was selected as the winning request.

54. A method as in

claim 53

further including:

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.

55. A method as in

claim 54

further including:

(d) determining the maximum number n of consecutive winning requests that may be chosen from the first group;

(e) determining the maximum number k of consecutive winning requests that may be chosen from the second group;

(f) adjusting the first adaptive variable to award priority to the second request group if fewer than k of the n+k−

1 most recent winning requests were chosen from the second request group; and

(g) adjusting the first adaptive variable to award priority to the first request group if fewer than n of the n+k−

1 most recent winning requests were chosen from the first request group.

56. A method as in

claim 55

wherein k does not equal n.

57. A method as in

claim 55

wherein k equals n.

58. A method as in

claim 55

wherein k is programmable.

59. A method as in

claim 55

wherein n is programmable.

60. A method as in

claim 54

including choosing the winning request from the second request group if the first adaptive variable awards priority to the second request group, and including arbitrating within the second request group using a fixed arbitration scheme.

61. A method as in

claim 54

further including dividing memory requests within the first request group into processor read requests and expansion bus read requests, and including determining the priority between the processor read requests and the expansion bus read requests based on a second adaptive variable.

62. A method as in

claim 61

further including:

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; and

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.

63. A method as in

claim 61

including using a third adaptive variable to arbitrate among expansion bus read requests.

64. A method as in

claim 63

further including:

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

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

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.

65. A method as in

claim 62

further including classifying expansion bus write requests into the first request group, and including using a fourth adaptive variable to arbitrate among expansion bus write requests.

66. A method as in

claim 65

further including:

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

adjusting the fourth adaptive variable during the current arbitration cycle to award priority to 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

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

67. A method as in

claim 66

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.

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

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

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

(c) choosing a winning request from the pending memory requests; and

(d) adjusting the first adaptive variable based on the winning request.

69. A method as in

claim 68

further including adjusting the first adaptive variable to award priority to the second request group if the winning request is chosen from the first request group.

70. A method as in

claim 68

further including:

(e) determining the maximum number n of consecutive winning requests that may be chosen from the first group;

(f) determining the maximum number k of consecutive winning requests that may be chosen from the second group;

(g) adjusting the first adaptive variable to award priority to the second request group if fewer than k of the n+k−

1 most recent winning requests were chosen from the second request group; and

(g) adjusting the first adaptive variable to award priority to the second request group if fewer than n of the n+k−

1 most recent winning requests were chosen from the first request group.

71. A method as in

claim 70

including a value of n that is not equal to the value of k.

72. A method as in

claim 70

including a value of n that is equal to the value of k.

73. A method as in

claim 70

including a value of n that is programmable.

74. A method as in

claim 70

including a value of k that is programmable.

75. A method as in

claim 68

further including:

(e) dividing the memory requests within the second request group into a first request and a second request;

(f) using a second adaptive variable to arbitrate between the first and second request; and

(g) adjusting the second adaptive variable based on the winning request.

76. A method as in

claim 75

including adjusting the second adaptive variable to award priority to the second request if the first request is chosen as the winning request.

77. A method as in

claim 68

further including:

(e) dividing the memory requests within the second request group into a first request and a second request; and

(f) assigning the first request a fixed priority over the second request.

78. A method as in

claim 68

including:

(e) dividing the first request group into processor requests and expansion bus read requests;

(f) using a second adaptive variable to arbitrate between the processor read requests and the expansion read bus requests; and

(g) adjusting the second adaptive variable based on the winning request.

79. A method as in

claim 78

including adjusting the second adaptive variable to award priority to expansion bus read requests if the winning request is a processor read request, and including adjusting the second adaptive variable to award priority to processor read requests if the winning request is an expansion bus read request.

80. A method as in

claim 78

further including classifying a processor write request into the first request group and assigning to processor write requests a fixed priority with respect to all other requests in the first request group.

81. A method as in

claim 80

further including awarding the processor write request priority over expansion bus read requests.

82. A method as in

claim 80

further including awarding processor read requests priority over the processor write requests.

83. A method as in

claim 68

including:

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

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

(g) fixing the priority of the expansion bus write requests with respect to the processor request and expansion bus read request priorities.

84. A method as in

claim 83

wherein expansion bus read requests have a fixed priority over expansion bus write requests.

85. A method as in

claim 84

wherein processor requests have a fixed priority over expansion bus write requests.

86. A method as in

claim 83

further including:

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

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

(j) adjusting the third adaptive variable based on the winning request.

87. A method as in

claim 86

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.

88. 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 of consecutive winning requests that may be chosen from the first group;

(b) determining the maximum number k 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.

89. A method as in

claim 88

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.

90. A method as in

claim 88

including a value of n that is not equal to the value of k.

91. A method as in

claim 88

including a value of n that is equal to the value of k.

92. A method as in

claim 88

including a value of n that is programmable.

93. A method as in

claim 88

including a value of k that is programmable.

94. A method as in

claim 88

wherein the first request group of requests contains only a single request.

95. A method as in

claim 94

wherein the second request group of requests contains only a single request.

96. 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 memory request groups;

(b) defining a set of adaptive arbitration rules that determine the priorities of the memory request groups;

(c) defining a set of fixed arbitration rules that determine the priorities of the memory requests within the memory request groups;

(e) selecting one of the memory requests as a winning request based on the adaptive and fixed priorities; and

(f) adjusting the adaptive arbitration rules based on the winning request.

97. A method as in

claim 96

including:

establishing a first group of requests and a second group of requests;

assigning a first adaptive variable to arbitrate between the first and second request groups;

determining the maximum number n of consecutive winning memory requests that may be chosen from the first request group;

determining the maximum number k of consecutive winning memory requests that may be chosen from the second request group;

adjusting the adaptive variable to award priority to the second request group if fewer than k of the n+k−

1 most recent winning requests are chosen from the second request group; and

adjusting the adaptive variable to award priority to the first request group if fewer than n of the n+k−

1 most recent winning requests are chosen from the first request group.

98. A method as in

claim 97

including a value of n that is not equal to the value of k.

99. A method as in

claim 97

including a value of n that is equal to the value of k.

100. A method as in

claim 97

including a value of n that is programmable.

101. A method as in

claim 97

including a value of k that is programmable.

102. A method as in

claim 97

wherein only a single request is classified into the first group of requests.

103. A method as in

claim 102

wherein only a single request is classified into the second group of requests.