Facsimile and static presentation processing – Static presentation processing – Detail of medium positioning
Reexamination Certificate
2001-09-21
2004-05-11
Williams, Kimberly (Department: 2626)
Facsimile and static presentation processing
Static presentation processing
Detail of medium positioning
C358S001120, C358S001170, C710S260000, C710S263000
Reexamination Certificate
active
06734984
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a computer system, peripheral device, or component having a circuit for determining the maximum or minimum of a plurality of codes.
BACKGROUND OF THE INVENTION
As an introduction to problems solved by the present invention, consider the conventional interrupt controller of a computer system. An interrupt controller is used with a processor or bus manager for determining which of several competing requests should be granted, based on a hierarchy of priority levels. For example, a conventional printer includes a processor for device control and data communications functions. This processor must service perhaps a dozen input/output circuits (called interrupt sources), each having an independent function (e.g. out of paper indicator, input data buffer full, scan line format complete, etc.). Although the processor could perform stored program instructions to determine in what order to service these numerous requests, these functions are more economically and efficiently performed by a dedicated circuit conventionally called an interrupt controller.
An interrupt controller generally receives an interrupt signal on a separate line from each interrupt source. Generally, when an interrupt signal is received, the interrupt controller signals the processor and the processor performs an interrupt acknowledge procedure to transfer control from the currently running task to the task that will service the interrupt. Transfer of processor execution control to a new address is conventionally accomplished via a table of addresses (called a vector table) indexed by an interrupt identifier. During the interrupt acknowledge procedure, the interrupt controller passes to the processor the interrupt identifier associated with the interrupt request signal.
In a system having numerous interrupt sources, various interrupt sources may require servicing ahead of other interrupt sources. And, the processor may require uninterrupted processing time. In such a system multiple interrupt requests may be asserted during a time when the processor is unavailable to service an interrupt. The interrupt controller, during such a time, maintains a request to the processor for interrupt servicing. When the processor becomes available and so indicates to the interrupt controller by beginning the interrupt acknowledgement procedure, the interrupt controller determines the currently pending highest priority interrupt and responds with an interrupt identifier for the appropriate interrupt source.
In a system where the program executed by the processor assigns interrupt identifiers to various input/output functions (either at system initialization or from time to time for sophisticated control functions), the value of an interrupt identifier may conveniently indicate by its binary magnitude the priority of the associated interrupt source over other interrupt sources. The interrupt identifier passed to the processor in an interrupt acknowledge procedure may be the interrupt identifier having the maximum binary value.
When a design having a large number of interrupt sources is to be expanded to service additional interrupt sources by a single processor in a conventional computer system design, the conventional interrupt controller design in its expanded form cannot avoid the undesirable side effects of increased circuit complexity and increased propagation delay. To be expandable, such a system design often propagates one or more carry signals from stage to stage in either an asynchronous or clocked manner. An expanded conventional circuit for accommodating additional interrupt sources has a considerably increased number of logic gates. Signal propagation through these additional gates also increases interrupt controller propagation delay. In other applications, the possibility of increasing propagation delay and/or circuit complexity cannot be accommodated within economic constraints of the planned product.
The problem of selecting the highest priority interrupt to service as discussed above with respect to input/output devices is similar in some respects to problems in other computer system components. For example, a multipurpose data communication bus shared by several devices is conventionally designed with a bus controller that permits exclusive use of the bus to a highest priority device. Priorities are designated conventionally by codes having a magnitude; the device associated with the code having the highest magnitude operates as the highest priority device. Generally any computer system resource (e.g. a processor, a bus, an input/output circuit, etc.) may be shared using a conventional circuit for arbitration. When presented with multiple pending requests to share the resource, such a circuit determines the highest priority request by determining the code having the highest magnitude. As another example, dedicated sorting logic for selecting data words in a sequence may also use a conventional circuit for selecting a “next” data word based on determining the highest magnitude data word not previously selected. Excessive circuit complexity and excessive propagation delay in these and related applications raise severe constraints on the practical design and economic marketing of a wide range of computer systems and products controlled by digital logic circuits.
Markets continue to demand sophisticated computer systems and computer operated products. Because sophisticated products increasingly operate with a large number of input/output circuits, and because the control of input/output circuits by interrupt servicing is more efficient than control using polling techniques, there is a continuing need for an interrupt controller design that is expandable with less added complexity and that operates with less added propagation delay. Similarly, in applications for selecting a device or a data word according to a code (or the data word itself) having the highest magnitude, as discussed above, there is a continuing need for a circuit design that is expandable with less added complexity and that operates with less added propagation delay.
SUMMARY OF THE INVENTION
An arithmetic-logic circuit according to aspects of the present invention receives a plurality of input codes and determines an output code. Each code has a respective magnitude and is conveyed in parallel by a plurality of respective (input or output) code signals. The circuit includes several product term generators (one for each respective plurality of input code signals), a summary term generator, and a selection circuit. Each product term generator provides a respective plurality of product term signals. Each product term signal is indicative of an AND combination of respective input code signals. The summary term generator provides a plurality of summary term signals in parallel. Each summary term signal is indicative of an OR combination of a corresponding product term signal from each product term generator. The selection circuit provides the plurality of output code signals according to an extreme of the respective magnitudes of the input codes. At least one output code signal is indicative of an AND combination of a multiplicity of summary term signals of the plurality of summary term signals.
When such a circuit is used in an interrupt controller, as described above, expansion of the design to accommodate an additional interrupt source can be accomplished with little added complexity and no added propagation delay. For example, when the number of bits in the input code is sufficient to accommodate the additional interrupt source, then the additional input code is received by an additional product term generator that generates additional product terms and the summary term generator is modified to merely add an additional gate input for each additional product term. Propagation delay of the interrupt controller is substantially unaffected by these modifications.
When the number of input code bits must be incremented to accommodate an additional interrupt source, then the modifications described above
Lee Chang H.
Prenn M. Therese
Ebrahimi Saeid
Hewlett--Packard Development Company, L.P.
Williams Kimberly
LandOfFree
System having an arithmetic-logic circuit for determining... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System having an arithmetic-logic circuit for determining..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System having an arithmetic-logic circuit for determining... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3262088