Electrical computers and digital data processing systems: input/ – Access arbitrating
Reexamination Certificate
2001-04-02
2004-10-26
Dang, Khanh (Department: 2111)
Electrical computers and digital data processing systems: input/
Access arbitrating
C710S244000
Reexamination Certificate
active
06810456
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to an arbiter and a bus system adopting the arbiter, and more particularly, to an arbiter using a priority mapper for priority arbitration and a bus system adopting the arbiter. The present application is based on Korean Patent Application No. 2000-43333, which is incorporated herein by reference.
2. Description of the Related Art
In a bus system in which multiple master devices share a common data bus, an arbiter serves to appropriately arbitrate a plurality of requests for access to a bus submitted by the multiple devices at the same time. A representative arbitration approach therefor is priority arbitration. According to priority arbitration, each master device is assigned a priority level and bus access or control is granted to the master device based on a priority scheme. This priority arbitration is classified into two types: one is a fixed priority scheme in which each device is assigned a fixed priority, and the other is a priority designation scheme in which a priority level is modified when necessary. An arbiter adopting the fixed priority scheme is simple to design, but the arbiter cannot be employed if the priority level assigned needs to be modified during operation of a bus system. The priority designation scheme is advantageous in supporting a master device which frequently transmits and receives data across a bus, if necessary. To this end, a priority level is dynamically assigned to each master device, and access to a bus is initially granted to the master device having the highest priority.
However, the priority designation scheme has a problem in that hardware is large and complicated compared to the fixed priority scheme. More specifically, the priority designation is performed by comparing each input port, to which a bus request is input from each master device, to look for the input port having the highest priority. Thus, for example, if the number of input ports is 3 or 4, three or six comparators are needed. That is, a number nC2 of comparators are needed for a number N of input ports, where “nC2” represents “n(n−1)
!”. An increase in the number of master devices increases the number of comparators exponentially, which may result in an extremely large arbiter circuit and slow arbitration speed. As a consequence, to achieve an arbiter circuit of an appropriate size and high arbitration speed, the number of master devices may be restricted.
SUMMARY OF THE INVENTION
To solve the above problems, it is an objective of the present invention to provide an arbiter of a priority designation scheme which can be implemented as a simple circuit, and a bus system adopting the arbiter.
It is another objective of the present invention to provide an arbiter providing a priority designation scheme without restriction on the number of master devices, and a bus system using the arbiter.
Accordingly, to achieve the above objectives, the present invention provides an arbiter including a bus request receiver, connected to a plurality of master devices, for receiving bus request inputs from the master devices, a priority level extractor for outputting priority level signals indicating predesignated priority levels corresponding to the master devices if the bus requests are input through the bus request receiver, and generating a priority level summation signal indicating all priority levels of the bus requests based on the output priority level signals, a priority output unit for outputting priority levels in order of decreasing priority based on the priority level summation signal generated by the priority level extractor, a priority mapper comprising a master device identifier output unit for extracting identifiers of the master devices submitting bus requests based on the priority level signals and outputting the extracted master device identifiers based on the order of the priority levels output from the priority output unit, and an arbitration circuit for granting access to the bus, to the master device having the identifier output from the priority mapper.
Preferably, the bus request receiver comprises a plurality of input ports connected to the plurality of master devices for receiving bus request inputs from the master devices, and a plurality of registers provided in the input ports for storing priority levels designated for the input ports. The priority level signal is represented using the same number of bits as the priority level.
Preferably, the priority level extractor performs an OR operation on one or more priority level signals on a bit-by-bit basis to generate the priority level summation signal represented in the same number of bits as the priority level signal. The OR operation is based on negative logic.
Preferably, the master device identifier output unit includes an identifier extractor and an identifier output unit. The identifier extractor extracts a bit column, including a bit indicating a priority level, requested from a matrix constructed of the priority level signals in order to generate an identifier signal, extracts a corresponding master device identifier based on the generated identifier signal and includes decoders for receiving input identifier signals to extract corresponding master device identifiers.
Preferably, the identifier output unit outputs an identifier of the master device having the priority level output from the priority output unit, wherein the output identifier is one of the identifiers extracted by the identifier extractor.
The bus system also provides a bus request receiver, connected to a plurality of master devices, for receiving bus request inputs from the master devices, a priority level extractor for outputting priority level signals indicating predesignated priority levels corresponding to the master devices if the bus requests are input through the bus request receiver, and generating a priority level summation signal indicating all priority levels of the bus requests based on the output priority level signals, a priority output unit for outputting priority levels in order of decreasing priority based on the priority level summation signal generated by the priority level extractor, a priority mapper comprising a master device identifier output unit for extracting identifiers of the master devices submitting bus requests in order to output the extracted master device identifiers corresponding to the priority levels output from the priority output unit, and an arbitration circuit for granting an access to bus to the master device having the identifier output from the priority mapper.
The bus request receiver includes a plurality of input ports connected to the plurality of master devices for receiving bus request inputs from the master devices, and a plurality of registers provided in the input ports for storing priority levels designated for the input ports. The priority level signal is represented using the same number of bits as the priority level.
Preferably, the priority level extractor performs an OR operation on one or more priority level signals on a bit-by-bit basis in order to generate the priority level summation signal represented in the same number of bits as the priority level signal.
Preferably, the master device identifier output unit includes an identifier extractor and an identifier output unit. The identifier extractor extracts a bit column, including a bit indicating a priority level, requested from a matrix constructed of the priority level signals to generate an identifier signal, extracts a corresponding master device identifier based on the generated identifier signal, and includes decoders for receiving inputs of the identifier signals in order to extract corresponding master device identifiers.
The identifier output unit outputs an identifier of the master device having the priority level input from the priority output unit, wherein the output identifier is one of the identifiers extracted by the identifier extractor.
REFERENCES:
patent: 5487168 (1996-01-01), Geiner et al.
patent: 5617575 (1997-0
Dang Khanh
Sughrue & Mion, PLLC
LandOfFree
Arbiter and bus system therefor does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Arbiter and bus system therefor, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Arbiter and bus system therefor will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3286663