US5499349A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Pipelined processor with fork, join, and start instructions using tokens to indicate the next instruction for each of multiple threads of execution
Assignee: Massachusetts Institute of Technology
•
Filing: 1994-10-03
•
Granted: 1996-03-12
•
Expires: 2014-10-03
Abstract
Abstract A multithreaded parallel data processing system has at least one processing element for processing multiple threads of computation. Threads are described by thread descriptors or tokens which are stored while waiting to be processed in a thread descriptor storage. Thread descriptors are comprised of an instruction pointer and a frame pointer. The instruction pointer points to the next instruction to be executed, and the frame pointer points to a frame of memory locations that the next instruction will operate on. Included within the instruction set of the at least one processing element is a fork instruction generates two thread descriptors which are added to the current thread descriptors, a start instruction on a first processor sends a message containing a thread descriptor to a second processor, and a join instruction joins two threads by producing a single thread descriptor when both of the joining threads have reached a join instruction.
Inventors
- 👤 Rishiyur S. Nikhil
- 👤 Arvind
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 01:12
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/44; G06F9/448; G06F9/4494
Claims Analysis
Total Claims: 14
Claim 1
Independent Claim
93 words
A pipelined processor for performing imperative control flow instructions of multiple threads of computation comprising: token storage wherein tokens are stored, each token identifying a next instruction to be processed in a thread of computation; and at least one processing pipeline which successively receives tokens from token storage for processing of the next instruction identified therein, the processing pipeline processing a forking instruction identified by a token to generate two tokens, the tokens identifying respective instructions of different threads that are subsequently applied to the at least one processor pipeline and processed independently.
Claim 2
Dependent Claim
93 words
A pipelined processor for performing imperative control flow instructions of multiple threads of computation comprising: token storage wherein tokens are stored, each token identifying a next instruction to be processed in a thread of computation; and at least one processing pipeline which successively receives tokens from token storage for processing of the next instruction identified therein, the processing pipeline processing a forking instruction identified by a token to generate two tokens, the tokens identifying respective instructions of different threads that are subsequently applied to the at least one processor pipeline and processed independently.
Claim 3
Dependent Claim
32 words
A pipelined processor as recited in claim 1 wherein one of the two tokens generated by the forking instruction is a token of the thread in which the forking instruction is included.
Claim 4
Independent Claim
105 words
A method of performing a forking operation in a pipelined processor that executes imperative control flow instructions comprising the steps of: a) keeping in storage a plurality of tokens, each token identifying a next instruction to be processed in a thread of computation; b) placing a new token from storage into a processing pipeline every clock cycle; c) in the processing pipeline, processing a forking instruction to generate two tokens, the tokens identifying respective instructions of different threads that are subsequently applied to the at least one processor pipeline and processed; d) returning the two tokens into storage for subsequent processing in the processing pipeline.
Claim 5
Independent Claim
105 words
A method of performing a forking operation in a pipelined processor that executes imperative control flow instructions comprising the steps of: a) keeping in storage a plurality of tokens, each token identifying a next instruction to be processed in a thread of computation; b) placing a new token from storage into a processing pipeline every clock cycle; c) in the processing pipeline, processing a forking instruction to generate two tokens, the tokens identifying respective instructions of different threads that are subsequently applied to the at least one processor pipeline and processed; d) returning the two tokens into storage for subsequent processing in the processing pipeline.
Claim 6
Dependent Claim
88 words
A pipelined processor for performing instructions of multiple threads of computation comprising: token storage wherein tokens are stored, each token identifying a next instruction to be processed in a thread of computation and at least one processing pipeline which successively receives tokens from token storage for processing of the next instruction identified therein, the processing pipeline processing a joining instruction identified by tokens to generate only a single token to be stored in the storage in response to a joining instruction executed in each of two separate threads.
Claim 7
Dependent Claim
88 words
A pipelined processor for performing instructions of multiple threads of computation comprising: token storage wherein tokens are stored, each token identifying a next instruction to be processed in a thread of computation and at least one processing pipeline which successively receives tokens from token storage for processing of the next instruction identified therein, the processing pipeline processing a joining instruction identified by tokens to generate only a single token to be stored in the storage in response to a joining instruction executed in each of two separate threads.
Claim 8
Dependent Claim
31 words
A pipelined processor as recited in claim 4 wherein the generated token corresponds to one of the two separate threads in which the last to be executed joining instruction is executed.
Claim 9
Dependent Claim
110 words
In a pipelined data processing system, a method of joining two independently operating threads of computation, comprising the steps of: keeping in storage a plurality of tokens, each token identifying a next instruction to be processed in a thread of computation placing a new token from storage into a processing pipeline every clock cycle; in a processing pipeline, processing a join instruction of a first of two threads by marking a memory location and performing no further computations for the first thread; and in the processing pipeline, processing a join instruction of a second of two threads by reading the marked memory location and continuing processing for the second thread.
Claim 10
Dependent Claim
110 words
In a pipelined data processing system, a method of joining two independently operating threads of computation, comprising the steps of: keeping in storage a plurality of tokens, each token identifying a next instruction to be processed in a thread of computation placing a new token from storage into a processing pipeline every clock cycle; in a processing pipeline, processing a join instruction of a first of two threads by marking a memory location and performing no further computations for the first thread; and in the processing pipeline, processing a join instruction of a second of two threads by reading the marked memory location and continuing processing for the second thread.
Claim 11
Dependent Claim
171 words
In a data processing system, a method for one processing element to deliver a value to and initiate a thread in another processing element using a start instruction comprising the steps of: keeping in storage a plurality of tokens, each token identifying a next instruction to be processed in a thread of computation: placing a new token from storage into a processing pipeline every clock cycle: in a start instruction identified by a token and processed in the processing pipeline, specifying memory locations containing a data value, a token descriptor in the other processing element and the address of a location in the other processing element; as an output of the processing pipeline sending a start message to the other processing element, the message containing the data value, the token descriptor and the location address; and receiving the start message at the other processing element where the data value is stored at the designated location, and the token is supplied as an input to another processing pipeline to initiate a thread.
Claim 12
Dependent Claim
171 words
In a data processing system, a method for one processing element to deliver a value to and initiate a thread in another processing element using a start instruction comprising the steps of: keeping in storage a plurality of tokens, each token identifying a next instruction to be processed in a thread of computation: placing a new token from storage into a processing pipeline every clock cycle: in a start instruction identified by a token and processed in the processing pipeline, specifying memory locations containing a data value, a token descriptor in the other processing element and the address of a location in the other processing element; as an output of the processing pipeline sending a start message to the other processing element, the message containing the data value, the token descriptor and the location address; and receiving the start message at the other processing element where the data value is stored at the designated location, and the token is supplied as an input to another processing pipeline to initiate a thread.
Claim 13
Dependent Claim
125 words
A pipelined processor for performing imperative control flow instructions of multiple threads of computation comprising: token storage wherein tokens are stored, each token identifying a next instruction to be processed in a thread of computation; and at least one processing pipeline which successively receives tokens from token storage for processing the next instruction identified therein; the processing pipeline processing a forking instruction from a token to generate two tokens, the tokens identifying respective instructions of different threads that are subsequently applied to the at least one processor pipeline and processed; and the processing pipeline processing a joining instruction from a token to generate only a single token to be stored in storage in response to a joining instruction executed in each of two separate threads.
Claim 14
Dependent Claim
125 words
A pipelined processor for performing imperative control flow instructions of multiple threads of computation comprising: token storage wherein tokens are stored, each token identifying a next instruction to be processed in a thread of computation; and at least one processing pipeline which successively receives tokens from token storage for processing the next instruction identified therein; the processing pipeline processing a forking instruction from a token to generate two tokens, the tokens identifying respective instructions of different threads that are subsequently applied to the at least one processor pipeline and processed; and the processing pipeline processing a joining instruction from a token to generate only a single token to be stored in storage in response to a joining instruction executed in each of two separate threads.
References Cited (Backward Citations)
US3614745A
Cited
US4229790A
Cited
US4481573A
Cited
US4530051A
Cited
US4858105A
Cited
US4819155A
Cited
US4943908A
Cited
US5050070A
Cited
US5050068A
Cited
WO1990005950A1
Cited
US5241635A
Cited
US5226131A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-03-12 | 1999-09-11 | 2000-03-12 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-03-12 | 2003-09-11 | 2004-03-12 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-03-12 | 2007-09-11 | 2008-03-12 | $7700.00 | Window Closed / Lapsed |