Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1998-12-16
2002-11-05
Donaghue, Larry D. (Department: 2154)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C712S023000
Reexamination Certificate
active
06477562
ABSTRACT:
FIELD OF THE INVENTION
The present invention is in the field of digital microprocessors, and pertains more particularly to such devices capable of operating with multiple processing streams, which are termed multi-streaming processors in the art.
BACKGROUND OF THE INVENTION
Multi-streaming processors capable of processing multiple threads are known in the art, and have been the subject of considerable research and development. The present invention takes notice of the prior work in this field, and builds upon that work, bringing new and non-obvious improvements in apparatus and methods to the art. The inventors have provided with this patent application an Information Disclosure Statement listing a number of published papers in the technical field of multi-streaming processors, which together provide additional background and context for the several aspects of the present invention disclosed herein.
For purposes of definition, this specification regards a stream in reference to a processor as principally hardware structure on the processor capable of supporting and processing an instruction thread. A thread is defined by software or application context. For example, a multi-streaming processor implemented as a CPU for operating a desktop computer may simultaneously process threads from two or more applications, such as a word processing program and an object-oriented drawing program. As another example, a multi-stream-capable processor may operate a machine without regular human direction, such as a router in a data-packet network. In this context there may be, for example, one or more applications (code sets) for processing and forwarding data packets on the network, and another for such as quality-of-service (QoS) negotiation with other routers and servers connected to the network. The nature of data received for processing, together with pre-programmed scheduling for internal functions will determine the calling and serving of application routines.
In either of the above cases the maximum capability of the processor to process multiple threads remains fixed at the number of hardware-limited streams. A multi-streaming processor operating a single thread therefore operates as a single-stream processor.
As described above and in the papers provided by IDS in the present case, superscalar processors are also known in the art. This term refers to processors that have more than one functional unit implemented on the processor chip, and an ability to issue instructions to individual ones of the functional units available. Most CPU processors built today have more than a single functional unit. Some have many such units, including such as Floating Point units, Integer Units, Logic Units, Branch Prediction units, Load/Store units and so forth. Multi-streaming superscalar processors are known in the art as well.
The inventors have determined that there is a significantly neglected field in the art, relative to scheduling instructions from streams to functional resources, whether there are one or more functional units. The issue is priority, and which stream is to be given priority to the functional resources. This is an issue in all multi-streaming processors, and can be a more complicated issue in superscalar processors running multiple instruction threads. In most development in the art, scheduling has been developed to maximize processor efficiency. The inventors have discovered that rapid extension of digital processing into growing technology fields has created a critical need for dynamic prioritizing of thread processing and access to processor resources.
In many application mixes it has become clear to the inventors that application criticality is a dominant issue, rather than processor utilization, although both need to be considered. Up to the present most attention has been given to processor utilization. As an example, in most real applications for multi-streaming processors, as opposed to theoretical, or academic exercises, there are real-time requirements. Moreover, the criticality of some application threads may change relative to others during run time, depending on a number of issues, and-the unsophisticated means of sharing and scheduling presently available in the art do not address real-world issues.
Accordingly, what is clearly needed in the art is apparatus and methods for more sophisticated and dynamic scheduling and prioritizing of tasks and threads for multi-streaming processors, including superscalar processors. The present invention teaches such apparatus and methods, which are disclosed below in enabling detail.
SUMMARY OF THE INVENTION
In a preferred embodiment of the present invention a multi-streaming processor is provided, comprising a plurality of streams for streaming one or more instruction threads; a set of functional resources for processing instructions from streams; an instruction scheduler for managing access for the streams to the functional resources; and a priority record of priority codes associated with streams. At any point in time the instruction scheduler manages access for a stream to the functional resources according to the priority record.
In some embodiments the priority record comprises one or more priority codes associated with at least one of the streams, and the priority record is static and not varying. In some other embodiments the priority record is varied in a consistently repeating manner. In some embodiments the processor has a priority controller coupled to the priority record, wherein the priority controller alters the one or more priority codes dynamically during processing. Alteration of priority codes may be accomplished at least in part in a manner determined by changes in on-chip processing statistics. Determination of priority codes may also, in some embodiments, be accomplished at least in part off-chip, and communicated to the priority controller. In yet other embodiments the priority controller alters priority codes according to instant states of stream instruction loading.
In one embodiment of the invention a particular priority code effectively disables a stream, preventing access for that stream to functional resources. In some cases the priority controller alters the priority record to enable and disable a stream in response to on-chip events, processing statistics, or external input. In some cases according to a processor interrupt.
In yet other embodiments of the invention the processor further comprises a tie-breaker function, the tie-breaker resolving access to functional resources for two or more streams having equal priority in the priority record.
In another aspect of the invention a multi-streaming processor is provided, comprising a plurality of streams for streaming a plurality of instruction threads; a set of functional resources for processing instructions from stream resources; a fetch unit for fetching instructions to the streams; an instruction scheduler for managing access for streams to the functional resources; a priority record of priority codes associated with streams; and a priority controller dynamically determining priorities and altering the priority record during processing.
In this aspect as well, alteration of the priority record may be accomplished at least in part in a manner determined by on-chip processing statistics. And in some embodiments alteration of the priority record may be accomplished at least in part off-chip, and communicated to the priority controller. In some embodiments a particular priority code may be used to effectively disable a stream, preventing access for that stream to functional resources. Enabling and disabling may be done in response to on-chip events, processing statistics, or external input. In some cases according to a processor interrupt. In some cases priority may be altered according to stream instruction loading. In this as well as other aspects a tie-breaker function may be provided, the tie-breaker resolving access to functional resources for two or more streams having equal priority in the priority record.
According to another aspect of the
Nemirovsky Adolfo M.
Nemirovsky Mario D.
Sankar Narendra
Boys Donald R.
Central Coast Patent Agency Inc.
Clearwater Networks, Inc.
Donaghue Larry D.
LandOfFree
Prioritized instruction scheduling for multi-streaming... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Prioritized instruction scheduling for multi-streaming..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Prioritized instruction scheduling for multi-streaming... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2955057