Electrical computers and digital data processing systems: input/ – Access arbitrating
Reexamination Certificate
2000-04-29
2003-07-15
Ray, Gopal C. (Department: 2181)
Electrical computers and digital data processing systems: input/
Access arbitrating
C710S107000, C710S124000
Reexamination Certificate
active
06594718
ABSTRACT:
BACKGROUND
In computer systems, single resources are shared between competing multiple agents through arbitration algorithms that ensure that each of the agents has equitable access to the single resource. For example, if four comparable agents required access to a single device or resource, one arbitration algorithm might ensure that each agent had access to the single device, or resource, 25% of the time. A common arbitration scheme uses a round robin. In a round robin arbitration each of the multiple agents is given equal priority in the arbitration and the round robin arbitration algorithm cycles in a fixed order through the multiple agents that are competing for the resource. Typically, the successful agent is chosen through numerically increasing order. In a specific arbitration cycle, the reference number of a selected agent is stored and then, during the next arbitration window, the next highest agent number is selected. For example, if eight agents request access to a single device or resource, this scheme would assign the competitive agents reference numbers 0 through agent 7 respectively. If the requested device or resource had most recently been accessed by agent 0, this value would be stored and in the succeeding cycle, agent 1 would have exclusive use of the device or resource.
While each competing agent has equal priority for the single resource and receives a pro-rata allotment for accessing the resource, such equal distribution of time slots and periods between multiple agents does not readily adapt to competing agents having different bandwidth requirements or speed capabilities. For example, if one agent operates at a speed such that it requires a resource twice as often as a second agent, this technology makes no provision for these greater requirements. Instead, using the round robin arbitration described, both agents would win the arbitration equally often and each would have equal access to the single resource even though one agent requires the resource twice as often as the other agent. This mismatch between the agent's bandwidth capabilities and its access to the shared resource impairs overall efficiency.
For example, in a computer system there are often many input/output (I/O) devices which have different bandwidth requirements. A system that supports different speeds of peripheral component interface (PCI) buses, may have cards which utilize data at different speeds. While the following description uses a PCI bus, the invention is not limited to any particular type of bus architecture. Some cards on a PCI bus may run at 33 MHZ while other cards run at 66 MHZ. Assuming an identical number of bits of data used by the two cards, the 66 MHZ card will use data twice as fast as the 33 MHZ card. The PCI card that runs at 33 MHZ are designated as 2X PCI bus cards. These cards use 64 bits of data. Conversely, the PCI bus cards that run at 66 MHZ are designated 4X PCI bus cards and also use 64 bits of data. A third speed of bus card is available which doubles the bandwidth of the 4X PCI bus cards and is designated the 8X PCI bus cards. The 8X PCI bus cards runs at double the bandwidth. If a 2X PCI bus card, a 4X PCI bus card, and an 8X PCI bus card were all configured with a standard round robin arbitration, the three speed cards would be given equal priority for the single resource. However, because of the greater data rates, the 4X PCI bus card and the 8X PCI bus cards are not being used efficiently in this round robin arbitration between the cards of various speeds and bandwidth.
Arbitration schemes have attempted to address this mismatch between high speed agents by devoting additional resource access periods to the higher speed agents. For instance, if an 8 cycle access period is divided between two 2X PCI bus cards (2X PCI#1 and 2X PCI#2), and a single 4X PCI card (4X PCI) a standard round robin arbitration scheme would allow each agent to access the resource {fraction (
1
/
3
)} of the time. However, prior arbitration schemes have attempted to give the 4X PCI card twice as much access to the resource then either of the two 2X PCI cards. In an 8 cycle access period, access to the resource could be divided as follows: cycle 0-2X PCI#1; cycle 1-2X PCI#2; cycle 2-4X PCI; cycle 3-4X PCI; cycle 4-2X PCI#1; cycle 5-2X PCI#2; cycle 6-4X PCI and cycle 7-4X PCI.
While this division of the resource among competing agents does lessen the problem, other difficulties are encountered. First, during the cycles in which 4X PCI card has exclusive access to the resource, both the 2X PCI#1 and 2X PCI#2 are deprived of access to the resource. Unless both 2X PCI bus cards have stored enough data to continue processing during that time, the overall efficiency of the system is reduced. Secondly, buffers associated with the 2X PCI bus cards may have to be increased to ensure their access to data during the excluded cycles. These problems are only exacerbated when an 8X PCI bus card is included within the system and increasingly the bandwidth mismatch. In addition, the startup time is delayed for the 2X device if the 4X of 8X card is selected first.
A need therefore exists for an efficient arbitration scheme which accommodates multiple speeds of the competing agents and which efficiently distributes access to the resource in accordance with the various speeds of the competing multiple agents. A further need exists for an efficient arbitration scheme that distributes access to the resource among the multiple agents in an efficient manner, allowing each of the competing agents to effectively use the single resource.
SUMMARY OF THE INVENTION
These and other objects, features and technical advantages are achieved by a system and method which according to one aspect of the invention, includes a device for arbitrating access to a resource by a plurality of agents includes logic configures to associate requesting ones of the agents with access tokens. The number of the access tokens assigned to each requesting agent is proportional to its bandwidth or speed in comparison with the other requesting agents. A selector is configured to sequence through the access tokens and select respective ones of the requesting agents associated with the access tokens. The logic may dynamically reconfigure token allocation and distribution to only those agents having a pending service request or may skip tokens allocated to agents not having a pending request. The distribution of tokens is preferably uniform over the total bandwidth space of the agents or requesting agents. In one implementation tokens are in the form of binary numbers. Sequencing through the binary numbers may be based on a reversal of the bits of the numbers or selection of winning agents may be based on a reversal of the bits.
According to another aspect of the invention, a method of arbitrating access to a resource by a plurality of agents associates requesting ones of the agents with access tokens. Numbers of access tokens are associated with each of the requesting agents in proportion to that agent's bandwidth capabilities and/or requirements with respect to the total bandwidth of all agents. The access tokens are sequenced through and respective ones of the requesting agents are selecting in response to selection of one of its tokens. The method may further include dynamically allocating the access tokens to the requesting ones of the agents and/or skipping selection of nonrequesting ones of the agents in response to an arbitration request. The tokens may be binary numbers wherein the selecting step sequences through the token in a reverse bit sequence order. Selection of agents may be based on a reverse bit sequence order of the binary numbers. The tokens associated with a particular agent may be uniformly distributed amongst all of the tokens.
According to another aspect of the invention, a device equitably arbitrates access to a resource by a plurality of agents such as DMA by a plurality of I/O devices, memory access by plural processors, etc. The invention includes methods and stru
Das Sharma Debendra
Ebner Sharon M.
LandOfFree
Arbitration scheme for equitable distribution of bandwidth... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Arbitration scheme for equitable distribution of bandwidth..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Arbitration scheme for equitable distribution of bandwidth... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3007604