Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1999-03-22
2002-05-14
Donaghue, Larry D. (Department: 2154)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C712S228000
Reexamination Certificate
active
06389449
ABSTRACT:
FIELD OF THE INVENTION
The present invention is in the field of digital processors, and pertains more particularly to such devices capable of executing multiple processing streams concurrently, 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 processing system as a hardware capability of the processor for supporting and processing an instruction thread. A thread is the actual software running within a stream. 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-streaming-capable processor may operate a machine without regular human direction, such as a router in a packet switched network. In a router, for example, there may be one or more threads for processing and forwarding data packets on the network, another for quality-of-service (QoS) negotiation with other routers and servers connected to the network and another for maintaining routing tables and the like. The maximum capability of any multi-streaming processor to process multiple concurrent threads remains fixed at the number of hardware streams the processor supports. A multi-streaming processor operating a single thread runs as a single-stream processor with unused streams idle. For purposes of the present specification a stream is considered an active stream at all times the stream supports a thread, and otherwise inactive.
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 multiples of one or more types of functional units, and an ability to issue concurrent instructions to multiple functional units. Most central processing units (CPUs) built today have more than a single functional unit of each type, and are thus superscalar processors by this definition. Some have many such units, including, for example, multiple floating point units, integer units, logic 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 neglected field in the architecture for all types of multi-streaming processors, including, but not limited to the types described above: The neglected field is that of communications between concurrent streams and types of control that one active stream may assert on another stream, whether active or not, so that the activity of multiple concurrent threads may be coordinated, and so that activities such as access to functional units may be dynamically shared to meet diverse needs in processing.
Accordingly, what is clearly needed in the art is apparatus and methods for more sophisticated interstream control and communication in all processor architectures that support multi-streaming or multi-threading, including but not limited to superscalar processors and processors that interleave instructions. The present invention teaches such apparatus and methods, which are disclosed below in enabling detail. Significant added flexibility, efficiency, and robustness are provided to multistream processor architectures and the ability to handle time-critical threads is enhanced at relatively low cost in the number of additional gates for implementation, as well as considerable additional benefits.
SUMMARY OF THE INVENTION
In a preferred embodiment of the 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; and interstream control mechanisms whereby any stream may effect the operation of any other stream. In various embodiments the interstream control mechanisms include mechanisms for accomplishing one or more of enabling or disabling another stream, putting another stream into a sleep mode or awakening another stream from a sleep mode, setting priorities for another stream relative to access to functional resources, and granting blocking access by another stream to functional resources.
In some embodiments the interstream control mechanisms include a master mode, whereby one stream is granted master status, and thereby may exert any and all available control mechanisms relative to other streams without interference by any stream. Also in some embodiments the interstream control mechanisms include supervisory modes, wherein control may be granted from minimal to full control, with compliance of controlled streams, which may alter or withdraw control privileges.
A variety of mechanisms may be implemented for interstream control hierarchy, such as a mechanism wherein master status and interstream control hierarchy is recorded and amended by at least one on-chip bit map. In this mechanism each stream maintains and edits a bitmap granting or withdrawing control privileges for each other stream, the settings valid for any stream but a Master stream, which will ignore the settings.
In another aspect of the invention a method for providing cooperation among software threads running concurrently in separate streams of a multi-streaming processor is provided, comprising steps of (a) implementing interstream control mechanisms in the processor, wherein any stream,may exert control functions on any other stream; (b) establishing control access privileges associated with each stream wherein scope of control for every other stream is recorded; and (c) exercising interstream control between operating streams using the control mechanisms within the scope recorded for each stream.
In this method the scope of control may include one or more of enabling or disabling another stream, putting another stream into a sleep mode or awakening another stream from a sleep mode, setting priorities for another stream relative to access to functional resources, and granting blocking access by another stream to functional resources. There may further be a step for setting a master mode, wherein one stream is granted master status, and thereby may exert any and all available control mechanisms relative to other streams without interference by any stream. There may still further be supervisory modes, wherein control may be granted from minimal to full control, with compliance of controlled streams, which may alter or withdraw control privileges. In the method master status and interstream control hierarchy may be recorded and amended by at least one on-chip bit map, wherein each stream maintains and edits a bitmap granting or withdrawing control privileges for each other stream, the settings valid for any stream but a Master stream, which will ignore the settings.
In other aspects of the invention computing systems are taught using processors according to embodiments of the invention. In the various embodiments and applications of the invention new ability for control in multi-streaming processors is provided, bringing new and powerful concepts, processors, and systems to the art.
REFERENCES:
patent: 5546593 (1996-08-01), Kimura et al.
patent: 5812811 (1998-09-01), Dubey et al.
patent: 5860017 (1999-01-01), Sharangpani et al.
patent: 5913049 (1999-06-01), Shiell et al.
Yamamoto et al. Increasing Superscalar Performance Through Multistreaming, pp.
Nemirovsky Adolfo M.
Nemirovsky Mario D.
Sankar Narendra
Boys Donald R.
Central Coast Patent Agency Inc.
Clearwater Networks, Inc.
Donaghue Larry D.
LandOfFree
Interstream control and communications 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 Interstream control and communications for multi-streaming..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Interstream control and communications for multi-streaming... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2872959