Electrical computers and digital data processing systems: input/ – Intrasystem connection – Bus access regulation
Reexamination Certificate
1996-09-19
2002-05-07
Dharia, Rupal (Department: 2181)
Electrical computers and digital data processing systems: input/
Intrasystem connection
Bus access regulation
C710S111000, C710S120000, C710S123000, C709S213000, C709S240000
Reexamination Certificate
active
06385678
ABSTRACT:
BACKGROUND
1. Field of the Invention
The present invention relates to the management of shared resources in information processing systems, and more particularly to schemes for controlling access to a common bus in such a system.
2. Description of the Related Art
The growing popularity of multimedia software has increased the need for computer systems to handle high-bandwidth, real-time transfers of data. Multimedia systems are distinguished from more traditional computing systems by a high degree of real-time interactivity with the user. This interactivity is accomplished through input/output (I/O) devices, some of which must transfer large volumes of data (e.g., video data) in relatively short periods of time. A computer system must manage the competition of these I/O devices and other functional units for shared data resources, while at the same time assure that the real-time data transfer constraints of the I/O devices and other processor components are satisfied.
Data is communicated among various computer components and peripheral devices over computer buses. A bus may be incorporated onto the microprocessor chip in order to connect the CPU, various caches and peripheral interfaces with each other and ultimately to main memory through an on-chip interface. Buses may also be external to the microprocessor chip, connecting various memory and I/O units and/or processors together in a multiprocessor system. For example, processors may utilize memory as a source of data and instructions, and as a destination location for storing results. Processors may also treat I/O devices as resources for communicating with the outside world, and may utilize buses as communication paths between themselves and memory or I/O devices.
When a bus agent (a device connected to the bus, such as a CPU) wishes to communicate with another agent, the first agent sends signals over the bus that cause the second agent to respond. These signals are collectively called the address or identity. The agent that initiates the communication is called the master, and the agent that responds is called the slave. Some agents act only as masters, some only as slaves, and others as either masters or slaves. If the master's addressing of the slave is acknowledged by the slave, then a data transfer path is established.
Only one agent at a time may communicate over the bus. When two agents attempt to access the bus at the same time, an arbitration mechanism or protocol must decide which agent will be granted access to the bus. Conventional bus arbitration schemes generally implement a fixed, unchanging priority assignment among the agents. Each agent is assigned a unique priority that remains the same after each round of arbitration. Under this scheme, low priority devices may rarely be granted bus control if they must frequently contend with higher priority devices during each arbitration attempt. This unfairness can be resolved by implementing a round-robin arbitration scheme in which an agent that wins arbitration is reassigned to a very low priority after being granted bus access, thus removing that agent from competition with previously lower priority agents for a period of time.
Some computer systems, at least in multiprocessor technology, implement a mixed arbitration scheme in which bus agents are divided into classes, with each class having a different priority. Devices within a class have the same priority and are generally scheduled to access the bus in a round-robin, equal opportunity manner. Devices that require a high bandwidth and low latency (waiting period between request and grant of bus control) must be assigned to an appropriate priority class to guarantee that the devices are allocated a minimum bandwidth and maximum latency. Although this mixed arbitration scheme is relatively sophisticated, assuring the proper allocation of bus bandwidth using this technique is cumbersome and inflexible. A more flexible system that could more easily be customized to the bandwidth requirements of a particular configuration is desired.
SUMMARY OF INVENTION
The present invention provides a method and apparatus for bus arbitration with weighted bandwidth allocation. Each bus agent is assigned a weight that governs the percentage of bus bandwidth allocated to the agent. An agent is granted control of the bus based, at least in part, upon its weight. The weight corresponds to the number of arbitration states assigned to the agent, where each state represents a grant of bus control. If a first agent is assigned a weight W and all agents together are assigned a total weight Z, an arbiter of the present invention guarantees bus control to the first agent for at least W arbitrations out of Z arbitrations in which the first agent requests bus control. By employing this scheme, the first agent is guaranteed a fraction W/Z of the bus bandwidth. To ensure flexibility of bandwidth allocation, the weight may be programmed using conventional memory-mapped techniques.
The arbitration scheme of the present invention can be split into multiple levels of hierarchy, where arbitration at each level is controlled by an independent state machine. When an agent wins arbitration at one level, it is passed to the next higher level where it competes with other agents at that level for bus access. For example, if a first agent occupies a corresponding second level, level 2, and wins arbitration at the second level, then the first agent will contend for arbitration at a first level, level 1, above level 2. The first agent and all other level 2 agents are assigned level 2 priorities and weights. To win arbitration at level 2, the first agent must have the highest level 2 priority among the level 2 agents asserting requests. In general, if the first agent occupies a corresponding kth level and is assigned a kth level weight, then the first agent is granted control of the bus based, at least in part, upon W
k
. In particular, where all agents together at the kth level are assigned a total weight Z
k
, the first agent is guaranteed bus control for at least W
k
arbitrations out of Z
k
arbitrations in which the first agent requests bus control and a kth level agent wins bus control. The weight W
k
corresponds to W
k
arbitration states at the kth level out of a total of Z
k
arbitration states at the kth level. This scheme guarantees a fraction W
k
/Z
k
of the bandwidth at level k to the first agent.
If the first agent wins level 2 arbitration, then it is passed on to level 1 as the level 2 winning agent. At level 1, the level 2 winning agent and all other level 1 agents are assigned level 1 priorities and weights. The level 1 priority and weight assigned to the level 2 winning agent are not assigned to the particular level 2 agent that wins an arbitration round, e.g., the first agent, but to the class of level 2 agents that are passed on to level 1. If the level 2 winning agent has a highest level 1 priority among level 1 agents asserting requests, then the level 2 winning agent wins arbitration at level 1 and is granted control of the bus.
The present invention also allows a bus agent to raise the priority of its request based upon the urgency of the request. According to the present invention, a bus agent can indicate the priority of its request to be low or high. When a bus agent wants to initiate a data transfer, it initially posts an adjustable low priority request. If the request is not acknowledged after the expiration of a predetermined waiting period, then the agent raises the request to a high priority request. Generally, the worst case latency period in which the high priority request will be acknowledged is known for a particular computer system. Accordingly, the waiting period is selected so that the agent will be guaranteed access to the bus within the worst case latency period after asserting a request. This priority raising technique of the present invention can be incorporated into any arbitration scheme, and in particular to the weighted arbitration scheme described above.
REFERENCES:
patent: 4375639 (1983-03-01), Jo
Jacobs Eino
Tzeng Tzungren
Dharia Rupal
Fenwick & West LLP
Trimedia Technologies, Inc.
LandOfFree
Method and apparatus for bus arbitration with weighted... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for bus arbitration with weighted..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for bus arbitration with weighted... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2858095