Electrical computers and digital data processing systems: input/ – Access arbitrating – Hierarchical or multilevel arbitrating
Reexamination Certificate
2001-07-03
2004-03-09
Auve, Glenn A. (Department: 2181)
Electrical computers and digital data processing systems: input/
Access arbitrating
Hierarchical or multilevel arbitrating
C710S116000
Reexamination Certificate
active
06704821
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Filed of the Invention
The present invention relates to arbitration in complex systems, such as digital systems.
2. Description of the Related Art
A complex digital system is comprised of a number of devices which need to access other devices, such as memories, peripherals, and more. Accesses take place through proper routing networks (datapath) through which data flow. Current terminology defines sources or initiators the devices accessing the further devices, and resources or targets the devices accessed by the former.
Accesses to the different resources must be in some way controlled to ensure that each initiator may achieve possession of the buses, and then to be able to perform data transfers toward the proper resource, for the required time.
A system whose task is to allow the various initiators to access the required targets, following a well defined logic, is called interconnect, and its core is called arbiter, since its task is to perform an arbitration between the requests coming from the initiators which require to transmit their data over the buses.
Arbitration is necessarily performed following some priority scheme, because when more than one initiator require at the same time possession of the buses, the arbiter must know which one of them must be served at that time.
The problem of arbitrating simultaneous requests of access to resources so as to ensure the required performance in terms of bandwidth and latency to the traffic sources of the system has already been studied and a number of solutions have been found.
In U.S. Pat. No. 5,956,493 a solution is disclosed implemented by using a bus arbiter including programmable latency counters to dynamically vary arbitration priority. The bus arbiter includes a request detection unit for detecting bus request signals of a plurality of bus masters, and a grant generator for generating corresponding grant signals to indicate a grant of ownership of the bus. A set of counters referred to as “request latency” counters is further provided wherein a separate counter unit corresponds to each bus master. Each counter is configured to generate a latency signal or value indicative of the time lapsed since the peripheral requested ownership of the bus. An arbitration control unit is coupled to the request latency counters, the request detection unit and the grant generator for processing incoming bus request signals. The arbitration control unit is configured to dynamically vary the level of arbitration priority given to each peripheral device based upon the latency signal corresponding to the device. Accordingly, as the time interval lapsed since a peripheral device requests the bus increases, the level of arbitration priority given to that peripheral also increases. A set of programmable registers are provided to allow software programming of the initial count value associated with each request latency counter. The request latency counter for a particular device may further be held or inhibited from counting to provide a constant level of priority for that particular peripheral device.
Since the level of arbitration priority given to a peripheral device may be based upon the span of time the peripheral has been waiting to gain ownership of the bus, improved overall system performance may be obtained, particularly for real time processing environments.
BRIEF SUMMARY OF THE INVENTION
An embodiment of the present invention provides an improved solution for interconnect arbitration, including a method and circuit architecture.
The arbitration strategy of an embodiment of the invention is a programmable one, that is one enabling proper decision as to the algorithm to be followed by the arbiter to grant the requests asserted by the initiators. Basically, the possibility exists of programming the priorities of the initiators, including the possibility of changing them dynamically.
The possible priority schemes are the following:
positional fixed priority;
programmed fixed priority; and
variable priority based on the concept of latency.
This latter scheme can follow two different strategies if more than one initiator have reached their threshold (typically maximum) accepted latency value.
Depending on the traffic requirements of the system for each of its initiators, arbitration can be programmed by selectively and alternatively choosing one of at least two (and preferably all) of said schemes so as to ensure the best system performance.
Specifically, arbitration can follow one of the schemes described in the following:
positional fixed priority without latency check: initiators priorities are fixed, given by connectivity, and no latency check is performed; grant is always given to the highest priority initiator making a request;
programmed fixed priority without latency check: initiators priorities are fixed, given by the values stored in priority registers, and no latency check is performed; grant is always given to the highest priority initiator making a request;
fixed priority with latency check (first version): initiators priorities can dynamically change depending on the latency an initiator reaches; when two or more initiators reach their maximum accepted latency, the initiator having the highest priority will be granted; and
fixed priority with latency check (second version): initiators priorities can dynamically change depending on the latency an initiator reaches; when two or more initiators reach their maximum accepted latency, the initiator having reached it first will be granted.
A preferred embodiment of the invention allows one to choose among four different criteria, and ensures a quite low grant delay, namely initiators are granted in a relatively small time within a clock cycle. This last property is principally due to the arbitration logic which uses the priority values stored in registers to take its decisions.
A significant feature of the invention is however programmability. The possibility to change runtime the arbitration scheme in terms of initiator priorities, latency requirements and priorities dynamic change management allows the system to easily meet the specifications in terms of initiators data rates (band-width) and latencies.
A significant preferred feature is the Latency Management Unit block, introducing a feature which in some cases could be very important to ensure performance and avoid deadlock: the possibility to grant, among the initiators having been kept waiting for the maximum tolerated time, the one having reached this maximum accepted latency first. This ensures that the “history” of the system is remembered by the arbiter while taking the decision of what initiator is to be granted, thus ensuring a more uniform distribution in time of the grants to all initiators.
In prior art solutions no timing information is available and priority and latency are linked (the higher the latency, the lower the priority). Latency count starts once the request is asserted and what happens if more initiators asserting requests have the same priority is left unclear.
Conversely, in an embodiment of the invention, very fast grant generation (e.g., <3 ns for eleven initiators in HCMOS7) is possible. Priority and latency are independent. As latency count does not depend on the request when more initiators reach maximum latency, grant can be given the one having reached it first (depending on arbitration programming).
An embodiment of the invention finds application in systems in which the devices accessing memories and resources in general are present in a high number, while the traffic generated is very high and could lead to congestion of the system.
Systems having similar features are generally those devoted to graphical processing, such as digital still cameras. In these system a number of image processing blocks can access with high traffic rates the only resource of the system, an SDRAM.
In a such situation it is very useful to have programmable arbitration algorithm, allowing software programming of priorities and maximum latencies for the various traffic sources so as t
Pisasale Salvatore
Scandurra Alberto
Auve Glenn A.
Iannucci Robert
LandOfFree
Arbitration method and circuit architecture therefore does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Arbitration method and circuit architecture therefore, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Arbitration method and circuit architecture therefore will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3220522