Electrical computers and digital data processing systems: input/ – Access arbitrating
Reexamination Certificate
1999-05-04
2002-08-06
Wong, Peter (Department: 2181)
Electrical computers and digital data processing systems: input/
Access arbitrating
C710S309000
Reexamination Certificate
active
06430641
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to the field of data processing systems, and, more particularly, to bus arbitration in dual bus data processing systems.
BACKGROUND OF THE INVENTION
Data processing systems may often be comprised of multiple components or devices that communicate with one another to carry out tasks. These components may be categorized as a master function or a slave function according to their operational characteristics in carrying out a particular objective. To facilitate data transfer or communication in a data processing system, busses may be used to carry data; address, and control information between master and slave functions. Because a data processing system may include several devices that assume the role of a master function at any point in time, contention for the use of one or more busses may arise.
To resolve a bus contention problem between two or more master functions, a bus arbiter can be used to arbitrate between simultaneous bus requests. The bus arbiter acts as a gatekeeper for a bus by accepting bus requests and then using a priority scheme to determine the order in which the requests will be granted. To ensure that high priority tasks are carried out promptly, the bus arbiter may use a priority scheme in which master functions attach a priority tag to their bus requests. Access to the bus is granted to the highest priority master function currently pending in a bus arbitration queue. As a result, bus performance is enhanced as the resource is allocated to those master functions implementing the highest priority tasks.
To further enhance the performance of a data processing system, the system busses may be duplicated into a simplex configuration for increased throughput. For example, a data bus may be divided into a write data bus for carrying data transfers from a master function to a slave function and a read data bus for carrying data transfers from a slave function to a master function. Thus, two data transfers can proceed simultaneously on the dual data busses as long as they do not access the same address location. The role of the bus arbiter becomes more complicated, however, as simultaneous requests for the data bus may both be granted if they are for different operations on separate address spaces. Clearly, more parallel data transfers granted by the bus arbiter will result in better utilization of the dual bus architecture and, ultimately, improved throughput.
Prior art arbiters implementing a priority based arbitration scheme for a dual bus system as described in the foregoing may suffer from a significant drawback. Consider the following sequence of events: The arbiter grants a request for a transaction on the read data bus, which is generally called the primary request. A subsequent request for the read data bus is acknowledged by the arbiter and is pipelined. This subsequent request is generally called the secondary request. If, the highest priority request currently held pending in a bus arbitration queue is for the read data bus, then a lower priority request for the write data bus will not be granted even if the write data bus is idle. Instead, the highest priority master function in the bus arbitration queue is given control of the address and control busses. Because the pending request for the write data bus is held in abeyance despite the availability of the write data bus to perform a data transfer, the utilization of the dual bus architecture is sub-optimal.
U.S. Pat. No. 5,572,686 to Nunziata et al., describes a priority based arbitration scheme in which a low priority master function can have its priority elevated if it does not receive access to a system bus within a certain period of time. Unfortunately, elevating the priority of the master function that made the request for the write data bus in the above example provides only a momentary solution to the problem. After this master function is assigned a higher priority, it may be the source of several requests to either the read or write data busses. One or more of these requests may end up as the highest priority request pending in a bus arbitration queue, which may block a lower priority master function from accessing the other, potentially idle, data bus. Thus, elevating the priority of a master function may simply move the problem from one master function to another.
U.S. Pat. No. 5,388,232 to Sullivan et al. and U.S. Pat. No. 5,555,425 to Zeller et al. describe bus arbitration schemes in which address and data transfers are pipelined to improve the utilization of the address and data busses. These patents do not, however, address the problem of arbitrating access to a dual bus system in which the data bus is divided into a simplex write data bus and a simplex read data bus as discussed in the foregoing.
U.S. Pat. No. 5,708,784 (hereinafter the '784 patent) to Yanai et al. describes a bus arbitration scheme for a dual, parallel bus architecture. The bus arbitration scheme discussed in the '784 patent, however, is directed to a dual bus architecture in which the address and data busses are fully duplicated with each having their own arbiter. For example, if a master function submits a request to a first arbiter for a first data bus that is currently busy, then the master function may submit the same request to a second arbiter to determine if a second data bus is available. If the second data bus is available, then the second arbiter will grant the request. The '784 patent does not, therefore, address the arbitration of a dual bus system in which the data bus comprises two simplex busses as discussed in the foregoing.
Consequently, there exists a need for improved arbiters and methods of arbitration for dual bus data processing systems in which a bus is divided into multiple busses based on function or other suitable criteria (e.g., read and write data busses).
SUMMARY OF THE INVENTION
It is therefore an object of the present invention to provide improved arbiters and methods of arbitration for dual bus data processing systems.
It is another object of the present invention to improve the utilization of a dual bus architecture.
These and other objects, advantages, and features of the present invention are provided by methods, arbiters, and computer program products that determine if a request for an idle bus in a dual bus data processing system is being blocked by one or more pending requests for the other bus. In this circumstance, any such pending request for the other bus is masked by the arbiter so that the request for the idle bus can be granted. Consequently, a more efficient utilization of the dual bus architecture is achieved.
In an illustrative embodiment of the invention, a bus request is received for a first one of the dual busses. If the address and control busses are unavailable to allow the request to be granted, then an inquiry is made regarding the status of a pending request for the second one of the dual busses that has gained control of the address and control busses. In particular, it is determined whether a primary request has been granted and a secondary request has been pipelined for the second one of the dual busses. If a primary request has been granted and a secondary request has been pipelined, then the priority of the pending requests for the second one of the dual busses are examined. If the priority of the pending requests for the second one of the dual busses are at least as high as the currently pending request for the first one of the dual busses, then these requests are masked so that they no longer appears to be pending, which allows the request for the first one of the dual busses to be granted.
REFERENCES:
patent: 5265211 (1993-11-01), Amini et al.
patent: 5345566 (1994-09-01), Tanji et al.
patent: 5369748 (1994-11-01), McFarland et al.
patent: 5386517 (1995-01-01), Sheth et al.
patent: 5388232 (1995-02-01), Sullivan et al.
patent: 5469577 (1995-11-01), Eng et al.
patent: 5555425 (1996-09-01), Zeller et al.
patent: 5572686 (1996-11-01), Nunziata et al.
patent: 5708784 (1998-01-01
Hofmann Richard Gerard
LaFauci Peter Dean
Wilkerson Dennis Charles
Chung-Trans X.
Munoz-Bustamante Carlos
Myers Bigel Sibley & Sajovec P.A.
Wong Peter
LandOfFree
Methods, arbiters, and computer program products that can... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods, arbiters, and computer program products that can..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods, arbiters, and computer program products that can... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2975063