Electrical computers and digital data processing systems: input/ – Access arbitrating – Access prioritizing
Reexamination Certificate
2000-08-10
2004-11-30
Rinehart, Mark H. (Department: 2112)
Electrical computers and digital data processing systems: input/
Access arbitrating
Access prioritizing
C710S240000
Reexamination Certificate
active
06826644
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a peripheral component interconnect (PCI) arbiter, and in particular to a PCI arbiter with a dynamic priority scheme.
2. Discussion of the Related Art
A peripheral component interconnect (PCI) bus is an industry standardized expansion bus that conveys much of the information and signals of a computer system. Optimally, when the computer system executes its programming, information should flow as fast as possible to ensure the computer is responsive to the user. To prevent mistakes in the transmission of that information, a PCI bus design includes a special logic circuit and associated signals to control the flow of that information.
Specifically, a typical PCI bus allows a bus controller, also called an arbiter, to control bus transfers. A device that takes control of the bus to handle its own transfer is termed a “master”, whereas a device that receives data from the master is termed a “target”. The arbiter uses an algorithm to determine which master can take control of the bus and the time period of that control.
Arbitration must resolve the competing goals of fairness and priority. Fairness requires that one master should not be allowed to monopolize the bus. However, priority requires that, under certain circumstances, predetermined masters should use the bus more often to accomplish time critical goals. Some typical algorithms used by arbiters are the Single-Level Round Robin, the Multi-Level Round Robin, the Least Recently Used, and the Priority Based approaches.
In the Single Level Round Robin approach, a small unit of time, i.e. a quantum, is defined. All processes (associated with specific masters) are put in a circular queue. The arbiter follows the queue, and allocates the master's use of the bus to accomplish the process for a time interval of one quantum. Any new process is added after the last process in the queue.
If the process finishes before the end of the quantum, the master releases the bus voluntarily. However, if the process is still running at the end of the quantum, the master is preempted and the process is added to the end of the queue. In either case, the arbiter assigns the bus to the next process in the queue.
In the Multi-Level Round Robin approach, at least two circular queues are formed. For example, assuming first and second queues are formed, processes that use the bus frequently are placed in the first queue and processes that use the bus less frequently are placed in the second queue. Processes in the second queue have equal access to the bus, if in the same queue. However, the processes in the second queue, as a group, have equal access to the bus as each process in the first queue. In other words, the processes of the second queue effectively form a “super process”, wherein the super process is deemed to be one of the processes in the first queue. Thus, for every round of the first queue processes, one process of the second queue is performed. In this approach, if the process finishes before the end of the quantum, the master releases the bus voluntarily. However, if the process is still running at the end of the quantum, the master is preempted and the process is added to the end of the appropriate queue.
In the Least Recently Used approach, an arbitrary queue is formed. The arbiter initially follows the queue and allows each process to finish before allowing the next master in the queue to get control of the bus. However, if the arbiter receives a request for bus control from a master not next in the queue, the arbiter gives control of the bus (after the completion of the process running) to the master that has least recently used the bus.
Finally, in a priority-based approach, the arbiter determines bus control based solely on the priority of the associated process performed by the master. In this approach, each process completes before the next process is initiated.
Each of the above-described approaches has its disadvantages. For example, in both the Single- and Multi-Level Round Robin approaches, a quantum may not allow a master time to finish a critical process. Therefore, completion of that critical process may take several complete cycles of the queue, thereby introducing significant inefficiency in the system.
In the Least Recently Used approach, processes that are non-critical get more bus control than in other approaches. Although this allows less frequently used processes an opportunity to complete, it also necessitates losing time resources for other more critical processes. Therefore, this approach also frequently results in significant inefficiencies in the system.
In the Priority Based approach, depending on the task to be completed by the system, non-critical processes may only rarely be run. Although these non-critical processes may relate only to processes such as expansion bus requests, sporadic or even non-completion of these processes may contribute to some system inefficiency.
All of these approaches use static algorithms to determine control of the bus. As noted above, each of these static algorithms fails to provide the flexibility to optimize system efficiency. Therefore, a need arises for a flexible, arbitration scheme that optimizes system efficiency.
SUMMARY OF THE INVENTION
The present invention provides a dynamic priority scheme that uses information including the status of the target and data availability in deciding which master should be assigned ownership of a PCI bus, thereby optimizing performance and utilization of the PCI bus. Specifically, the present invention provides multiple levels of master priority. In one embodiment, three levels of priority are provided: HIGH, MEDIUM, and LOW.
Once a request from a master is posted, an arbiter in the system issues a signal to the master. At this point, the arbiter in the system assigns the requesting master a MEDIUM priority and forwards the request to the target. The arbiter then determines if data is available from the target. If data is available, then the arbiter reassigns the requesting master a HIGH priority. However, if data is not available, then the arbiter reassigns the requesting master a LOW priority and ignores the requesting master until the arbiter is notified that data is available from the target.
In accordance with the present invention, each target includes a memory interface to facilitate the prioritization process. Specifically, upon receipt of a memory access request from a master (via the arbiter), the target stores this request in a request queue, which forms part of the memory interface, and then proceeds to capture the information needed to complete the access of the memory. After the data is copied in the request queue (i.e., the data is now available), the target generates a master ID for triggering a status change of the requesting master. In a preferred embodiment, the target generates the master ID using the request from the master (called a modified request). This master ID is then provided to the arbiter.
After the arbiter receives the modified request, the arbiter changes the priority of the master to HIGH and, assuming the PCI bus is available and no other masters have an earlier high priority, sends the requesting master a final grant signal, thereby allowing the master to take control of the PCI bus. Note that if the PCI bus is currently being controlled by another master or if other masters have an earlier high priority, then the arbiter sends the final grant signal at the next earliest time period after the process performed by the last controlling master is complete.
To further increase the efficiency of the present invention, the request queue may include an input/output cache. A cache controller keeps the cache filled with data or instructions that one or more masters are most likely to need next. In this manner, information can be retrieved without delay.
REFERENCES:
patent: 5592631 (1997-01-01), Kelly et al.
patent: 5761452 (1998-06-01), Hooks et al.
patent: 5848297 (1998-12-01), Krein et al.
patent: 5850530 (1998-12-01),
Arramreddy Sujith K.
Raghavendra Appanagari
Christie Parker & Hale LLP
Huynh Kim T.
Rinehart Mark H.
ServerWorks Corporation
LandOfFree
Peripheral component interconnect arbiter implementation... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Peripheral component interconnect arbiter implementation..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Peripheral component interconnect arbiter implementation... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3324511