Electrical computers and digital data processing systems: input/ – Interrupt processing – Interrupt prioritizing
Reexamination Certificate
2000-09-12
2003-11-18
Auve, Glenn A. (Department: 2664)
Electrical computers and digital data processing systems: input/
Interrupt processing
Interrupt prioritizing
C710S262000
Reexamination Certificate
active
06651126
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
This invention relates to digital processors, and more particularly relates to methods for servicing multiple interrupts on a priority basis.
BACKGROUND OF THE INVENTION
Priority based request arbitration systems determine the next request to be serviced, i.e., the “winner,” based upon which request priority is highest, pending and enabled. Priority assignments are generally based on degrees of importance, in this case of requests. If multiple requests are programmed to the same priority, fairness protocols are used to determine the next winner. A mechanism is fair when any given request is not serviced twice until all pending requests are serviced once. Such arbitration systems are frequently used in digital processor interrupt servicing systems. In fact, throughout this document the term “request” and “interrupt” are used synonymously (an interrupt is a request for service).
The simplest fairness protocol is system based and ensures that a request does not occur twice for a predetermined length of time. This type of fairness includes Rate Monotonic Scheduling Theory (Louis Sha from Carnegie Mellon University). However, for many systems, requests are not able to be deterministically scheduled a priori.
A second form of fairness protocol is “First Come First Served (FCFS)” (Udi Manber and Mary Vernon, University of Wisconsin). In this protocol, each time the source of the request loses, it increments a counter. The counter value is used as the least significant bits of the priority field to determine the next winner. When multiple requests are all of the same priority value the leftmost is selected as the winner. This mechanism is gate intensive and potentially slows the rate at which the next winner can be determined.
Another mechanism commonly used in busses like Futurebus+ is “Round Robin” (Udi Manber and Mary Vernon, University of Wisconsin). In this protocol, a module checks if it lost and the winner is to the left (arbitrarily but consistently ordered) of itself. If so, it sets a round robin bit which is used as the least significant bit of the priority value to determine the winner. When multiple requests are all of the same priority value the leftmost is selected as the winner. This mechanism is a vast improvement over First Come First Served by reducing the effect on the amount of storage needed to determine fairness and also to reduce the time required to determine the winner.
However, there is a need to further reduce the storage necessary, in most cases, and the time required to determine a winner in priority based request arbitration systems.
SUMMARY OF THE INVENTION
The present invention provides a snapshot arbiter system for servicing multiple interrupt requests for a central processing unit (CPU) in a digital processor system, and for providing interrupts to the CPU corresponding to the interrupt requests. The system includes a synchronizer adapted to synchronize interrupt requests to a clock as they are received, and an interrupt masker adapted to receive a set of indicators identifying interrupt requests to be masked and to output active indicators that are a set of active interrupt request values corresponding to received interrupt requests that are not masked. Also included is a priority encoder block adapted to receive a set of priority values for respective interrupt requests and to provide as an output priority indicators that are a set of codes representing the priority values. A snapshot enable block is included, adapted to store enable indictors that are a set of bits representing currently enabled interrupt requests, and output those bits as enable bits. Also included is a snapshot register adapted to receive the active indicators and the enable indicators, and to output snapshot indicators that are a set of values representing the currently active and enabled interrupts. An interrupt generation block is included, adapted to receive the snapshot indicators and the priority indicators, and to output an interrupt corresponding to a highest priority interrupt request, to output a highest indicator representing a highest interrupt Priority level in the snapshot register. and to output for reading by the CPU an identification indicator representing a currently selected interrupt request. Finally, an interrupt preemption block is included, adapted to receive the priority indicators. the active indicators and the highest indicator, and to output to the snapshot enable block a set of bits corresponding to each current interrupt request higher in priority than all of the interrupt requests represented in the snapshot register, for updating the snapshot enable block.
The present invention is equally applicable to any request/grant arbitration protocol.
REFERENCES:
patent: 5758169 (1998-05-01), Nizar et al.
patent: 5848279 (1998-12-01), Wu et al.
patent: 5918057 (1999-06-01), Chou et al.
patent: 6240483 (2001-05-01), Gutta et al.
Cantrell Jay T.
Granger Mark A.
Kodavarti Ravishankar
Auve Glenn A.
Brady III W. James
Moore J. Dennis
Telecky , Jr. Frederick J.
Texas Instruments Incorporated
LandOfFree
Snapshot arbiter mechanism does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Snapshot arbiter mechanism, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Snapshot arbiter mechanism will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3181263