Electrical computers and digital data processing systems: input/ – Access arbitrating – Access prioritizing
Reexamination Certificate
2000-08-11
2003-09-09
Lefkowitz, Sumati (Department: 2189)
Electrical computers and digital data processing systems: input/
Access arbitrating
Access prioritizing
C710S241000, C710S040000, C711S151000
Reexamination Certificate
active
06618778
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a arbiter and a method of arbitration and in particular, but not exclusively to an arbiter for requests for obtaining memory access.
BACKGROUND OF THE INVENTION
Hardware memory arbiters of various different types are known. The simplest type is a fixed priority system. In this system, each device requesting access to the memory is allocated a priority. The device having the highest allocated priority and which is requesting access will always win access to the memory. Whilst fixed priority arbiters ensure that it is always known which device wins access to the memory, it can result in a device with a low priority being starved of access to the memory. In other words, low priority devices may, in certain circumstances, be prevented from having access to the memory. However, this scheme does allow those devices which require frequent access to the memory to have a greater share of the available accesses.
A second type of memory arbiter is a rotating priority or round robin arbiter. This is illustrated in
FIG. 1. A
, B, C and D represent devices requesting access to the memory. The device with the current highest priority is at the top of the list whilst the device with the current lowest priority is at the bottom of the device. An X next to the device indicates that the device is requesting access to the memory. Initially, as device A has the highest priority and is requesting access to the memory, it is granted access to the memory. This is illustrated in
FIG. 1
a.
Subsequently, as illustrated in
FIG. 1
b
, device A is assigned the lowest priority and device B now has the highest priority. As device B is requesting access to the memory, and it has the highest priority, it is granted access to the memory. Next, as shown in
FIG. 1
c
, device B is given the lowest priority and device C now has the highest priority. As device C has requested access to the memory it wins access to the memory.
Likewise, in
FIG. 1
d
, device D has the highest priority and has requested access to the memory and thus wins access to the memory. Device C has the lowest priority.
However, in
FIG. 1
e
, device A has the highest priority but has not requested access to the memory. Accordingly, the device having the highest priority and which has requested access to the memory wins. In the case of
FIG. 1
e
that is device B.
Device B is then assigned the lowest priority but device A maintains its highest priority. This is shown in
FIG. 1
f
. However, device C is the highest priority device requesting access and thus wins the arbitration.
This system has the advantage that each device has an equal chance of winning over time. However, this does not allow for one device to have a greater proportion of the available bandwidth. This means that the operation of the system can be slowed unnecessarily.
More complex schemes have been proposed which, for example, consider the last N accesses/cycles and determine the winner for a current access or cycle taking into account the number of past wins of each device as well as its priority. However, these systems require a large amount of hardware to implement. This may mean that the arbiter may take up a large area on a integrated circuit, which is undesirable as this slows down the time taken to make arbitration decisions. This latter disadvantage can result in delays being introduced into the system which may offset any advantage obtained from the particular use of the complex arbitration scheme.
SUMMARY OF THE INVENTION
Accordingly, it is an aim of embodiments of the present invention to provide an arbiter and a method of arbitration which overcomes the disadvantages of the various known schemes.
According to one aspect of the present invention, there is provided an arbiter for arbitrating between a plurality of requests from a plurality of requesters, said arbiter being arranged to assign an order of priority of said requesters, the requester having the highest priority and which has made a request winning the arbitration, wherein the arbiter determines a new priority for said winning requester, said winner being given a priority different from the lowest priority.
Arbiters embodying the present invention can be implemented simply and yet provide a degree of complexity to the arbitration.
Preferably, the arbiter is arranged to assign relegation information to each of the requesters, the relegation information determining the priority of a winner of the arbitration after the winner has won an arbitration. The relegation information may comprise an arbitration value which defines the number of positions by which the winner of the arbitration is relegated. Alternatively, the relegation information may take the form of a relegation position which defines the position to which the winner of the arbitration is relegated.
The relegation information can be changed during use of the arbiter. In other words, the arbiter can be configured during use.
Preferably, the arbiter has a list of requesters, the list defining the priority of the requesters, wherein the list is arranged to include at least one requester in at least two different positions in the list. The list is preferably longer than the number of requesters. The winner of an arbitration can either go to the end of the list or be inserted into a position within the list.
It should be appreciated that not all winners will be given a priority different from the lowest priority. In some embodiments of the present invention, at least one winner may be given a priority different from the lowest priority.
According to a second aspect of the present invention, there is provided an arbiter for arbitrating between a requests from a plurality of requesters, said arbiter being arranged to assign an order of priority to said requesters and relegation information to each of said requesters, the relegation information determining the priority of a winner of said arbitration after the winner has won an arbitration.
According to a third aspect of the present invention there is provided an arbiter for arbitrating between a plurality of requests from a plurality of requesters, said arbiter having a list of requesters, at least some of said requesters making requests, the list defining the priority of said requesters, wherein said list is arranged to include at least one requester in at least two different positions in said list.
In this example, the length of the list may be changed during use of the arbiter. The winner of an arbitration may be sent to the end of the list or may be inserted at a given position within the list.
According to a fourth aspect of the present invention, there is provided an arbiter for arbitrating between a plurality of requests from a plurality of requesters, said arbiter assigning a priority to each of said requesters, the priority assigned to each requester determining the frequency with which each requester wins an arbitration, wherein said arbiter is configurable to provide to the required priority for each requester.
The arbiter may be configured prior to use and/or be alterable during use.
The arbiter may arbitrate between requests from requesters requesting access to a memory. The requester can be a device or a channel.
The arbiter may be arranged to consider only some of the requesters when arbitrating between the requesters, the considered requesters having the highest priority.
It should be appreciated that the various aspects described hereinbefore can be used in conjunction with each other.
According to a still further aspect of the present invention, there is provided a method of arbitrating between a plurality of requests from a plurality of requesters, said method comprising assigning an order of priority to the requesters, determining which requester has the highest priority and which has made a request, said requester winning the arbitration, determining a new priority for the winning requester, the new priority being different from the lowest priority.
REFERENCES:
patent: 3701109 (1972-10-01), Peters
patent: 4760515 (1988-07-
Lefkowitz Sumati
Morris James H.
Skrivanek, Jr. Robert A.
STMicroelectronics Limited
Wolf Greenfield & Sacks P.C.
LandOfFree
Arbiter for arbitrating between a plurality of requesters... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Arbiter for arbitrating between a plurality of requesters..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Arbiter for arbitrating between a plurality of requesters... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3047056