Electrical computers and digital data processing systems: input/ – Intrasystem connection – Bus access regulation
Reexamination Certificate
1999-10-19
2002-10-15
Auve, Glenn A. (Department: 2181)
Electrical computers and digital data processing systems: input/
Intrasystem connection
Bus access regulation
C710S123000, C710S243000
Reexamination Certificate
active
06467002
ABSTRACT:
TECHNICAL FIELD
The present claimed invention relates to the field of priority arbitration. More specifically, the present claimed invention relates to fair and efficient arbitration in a computer environment wherein a common resource is shared by multiple devices or agents.
BACKGROUND ART
A modern computer system or computer network typically has a common resource (e.g., a bus or a memory subsystem in a computer system; a network adapter in a computer network) that is shared by multiple devices and/or agents (e.g., peripherals coupled to the common bus; workstations coupled to the network adapter) which issue service requests to the shared resource from time to time. In such a computer environment, a priority arbitration mechanism is needed to regulate access by the various devices to the shared resource and to resolve access contentions and conflicts that may arise, as is the case when more than one of those devices attempt to gain access to the same shared resource at the same time.
However, arbitration inevitably adds latency to operations and adversely affects the performance of the computer system or network. Prior art approaches to priority arbitration have been unsatisfactory with respect to the speed of arbitration. In particular, such prior art schemes generally require multiple clock cycles to complete the arbitration process. For example, under the traditional round-robin arbitration scheme, during a given clock cycle only one of the various devices potentially requesting access to a shared resource is checked to determine whether a request has been issued. As a result, multiple clock cycles are required to check all of the potentially requesting devices. Indeed, while a more efficient arbitration scheme is highly desirable in any environment with shared resources, it is especially critical in today's high speed applications, such as Gigabit Ethernet. Therefore, an efficient mechanism for priority arbitration is much needed in such a shared-resource environment in order to optimize the performance of computer systems and networks.
Moreover, one prior art approach to priority arbitration involves assigning a fixed priority order to the various devices which share the common resource. As such, when an access contention arises among the various devices, the requester device with the higher priority could always win in an arbitration. More particularly, since this prior art priority arbitration approach fails to address the problem that a requester device having a low priority is virtually deprived of access to the shared resource when competing with another device having a high priority under such an arrangement, this prior art approach cannot be applied to a shared-resource environment to provide fair arbitration among the various devices. Thus, a method and system for priority arbitration which achieves fairness in granting access to the shared resource is needed.
Yet another prior approach to priority arbitration attempts to remove the stranglehold that a high priority device has over other devices in a shared-resource environment by remembering the most recently served device (e.g., by using a “mark bit”) and ensuring that the same device does not prevail in the next arbitration. Unfortunately, this prior art approach not only requires additional memory to implement but also increases the complexity of implementation as a result. Therefore, a method and system for priority arbitration which does not require extra memory in its implementation is desired.
Additionally, a method and system for priority arbitration suitable for use in a shared-resource environment must not require complete revamping of existing computer systems and/or networks. That is, in implementing a viable method and system for priority arbitration in a shared-resource environment, components that are well known in the art and are compatible with existing computer systems and/or networks need to be used so that the cost of realizing the method and system for priority arbitration is low. In so doing, the need to incur costly expenditures for retrofitting existing computer systems and/or networks or for building custom components is eliminated.
Thus, a need exists for a method and system for priority arbitration in a shared-resource computer environment which is highly efficient with minimal latency. A further need exists for a method and system which meets the above listed need wherein the method and system renders fair arbitration. An additional need exists for a method and system which satisfies both of the above needs and wherein no extra memory is required for its implementation. Still another need exists for a method and system which fulfills all of the above cited needs and wherein the method and system is conducive to use with existing computer systems and/or networks.
DISCLOSURE OF THE INVENTION
The present invention provides a method and system for priority arbitration in a shared-resource computer environment which is highly efficient with minimal latency, and which renders fair arbitration. The present invention further provides a method and system which does not require additional memory to implement. The present invention accomplishes the above achievements with a method and system which performs priority arbitration using a novel single cycle modified round-robin arbitration mechanism with embedded priority and which is conducive to use with existing computer systems.
Specifically, in one embodiment, the present invention assigns an initial priority order to the plurality of devices such that those devices have priorities which are distinct. The present invention then identifies those of the plurality of devices which have issued service requests to the shared resource in a first clock cycle as requesting devices. Provided that there are more than one requesting device in the first clock cycle, the present invention selects one of the requesting devices to be serviced by the shared resource in a second clock cycle following the first clock cycle, where the selected device has the highest of the priorities among the requesting devices based on the initial priority order. The present invention also reassigns the priorities among the plurality of devices such that the selected device is assigned the lowest one of the priorities. In so doing, this. embodiment of the present invention provides a novel method and system for single cycle priority arbitration which is fair and which does not require extra memory storage for its implementation.
In another embodiment, the present invention includes the above recited steps and further the present invention identifies those of the plurality of devices having priorities lower than that of the selected device before the reassignment of the priorities. The present invention then reassigns the priorities among the plurality of devices such that those of the plurality of devices identified above as having priorities lower than that of the selected device are assigned the highest ones of the priorities.
In yet another embodiment, the present invention includes the above recited steps and further the present invention identifies those of the plurality of devices having priorities higher than that of the selected device before the reassignment of the priorities. The present invention then reassigns the priorities among the plurality of devices such that those of the plurality of devices identified above as having priorities higher than that of the selected device are assigned those priorities which are lower than the priorities of those of the plurality of devices identified above as having priorities lower than that of the selected device before the reassignment.
These and other advantages of the present invention will no doubt become clear to those of ordinary skill in the art after having read the following detailed description of the preferred embodiments which are illustrated in the various drawing figures.
REFERENCES:
patent: 5623672 (1997-04-01), Popat
patent: 5884051 (1999-03-01), Schaffer et al.
patent: 6016528 (2000-01-01), Jaramillo e
3Com Corporation
Auve Glenn A.
Wagner , Murabito & Hao LLP
LandOfFree
Single cycle modified round-robin arbitration with embedded... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Single cycle modified round-robin arbitration with embedded..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Single cycle modified round-robin arbitration with embedded... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2961398