Patent US5353418A successfully refreshed from Google Patents.
US5353418A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System storing thread descriptor identifying one of plural threads of computation in storage only when all data for operating on thread is ready and independently of resultant imperative processing of thread
Assignee: Massachusetts Institute of Technology
•
Filing: 1990-05-21
•
Granted: 1994-10-04
•
Expires: 2010-05-21
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 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 on set of the at least one processing element is a load instruction that loads global data into local processing element memory that is performed to two phases: a request phase and a response phase. Also included are instructions to fork a thread into two threads and to join two threads into a single thread.
Inventors
- 👤 Rishiyur S. Nikhil
- 👤 Arvind
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-31 04:08
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/44; G06F9/448; G06F9/4494
Claims Analysis
Total Claims: 22
Claim 1
Independent Claim
295 words
A data processing system comprising: plural processing elements, each having a thread descriptor storage, for imperative processing of each of plural threads of computation in response to thread descriptors from the thread descriptor storage, each of said thread descriptors identifying a next instruction to be processed in one of said plural threads of computation and a frame of storage locations on which the next instruction is to operate; a memory for storing data and instructions for the plural processing elements in executing the plural threads of computation; a memory controller for controlling the memory, the controller responding to request messages from respective ones of the plural processing elements for memory access to the memory by returning a response message to the respective one of said processing elements, the response message including requested data and also including one of said thread descriptors; wherein each of the plural processing elements responds to a load instruction to retrieve data from the memory by generating one of said request messages comprised of a thread descriptor that is not retained by said processing element and by transmitting said request message to the memory controller which, in turn, generates a response message that includes the thread descriptor of the request message and the requested data, said processing element processing the response message by storing the requested data in the frame identified in the thread descriptor, said processing element storing the thread descriptor of the response message in said thread descriptor storage only upon the storing of all data required for processing of the next instruction identified by the thread descriptor, such that the storing of the thread descriptors in the thread descriptor storage and resultant imperative processing of the plural threads of computation are independently performed by the plural processing elements.
Claim 2
Dependent Claim
295 words
A data processing system comprising: plural processing elements, each having a thread descriptor storage, for imperative processing of each of plural threads of computation in response to thread descriptors from the thread descriptor storage, each of said thread descriptors identifying a next instruction to be processed in one of said plural threads of computation and a frame of storage locations on which the next instruction is to operate; a memory for storing data and instructions for the plural processing elements in executing the plural threads of computation; a memory controller for controlling the memory, the controller responding to request messages from respective ones of the plural processing elements for memory access to the memory by returning a response message to the respective one of said processing elements, the response message including requested data and also including one of said thread descriptors; wherein each of the plural processing elements responds to a load instruction to retrieve data from the memory by generating one of said request messages comprised of a thread descriptor that is not retained by said processing element and by transmitting said request message to the memory controller which, in turn, generates a response message that includes the thread descriptor of the request message and the requested data, said processing element processing the response message by storing the requested data in the frame identified in the thread descriptor, said processing element storing the thread descriptor of the response message in said thread descriptor storage only upon the storing of all data required for processing of the next instruction identified by the thread descriptor, such that the storing of the thread descriptors in the thread descriptor storage and resultant imperative processing of the plural threads of computation are independently performed by the plural processing elements.
Claim 3
Dependent Claim
44 words
A data processing system as recited in claim 1 wherein the processing elements execute forking instructions that generate two threads of computation from a single thread of computation and execute joining instructions that merge multiple threads of computation into a single thread of computation.
Claim 4
Dependent Claim
18 words
A data processing system as recited in claim 1 wherein the threaded descriptor storage is a FIFO queue.
Claim 5
Dependent Claim
40 words
A data processing system as recited in claim 1 wherein each of the plural processing elements begins processing a next thread in the thread descriptor storage if continuing processing of a current thread would cause the processing element to idle.
Claim 6
Dependent Claim
23 words
A data processing system as recited in claim 1 wherein each of the plural processing elements is a reduced instruction set processing element.
Claim 7
Dependent Claim
50 words
A data processing system as claimed in claim 1 wherein each of the plural processing elements responds to the response message by storing data from the response message at a memory location identified in the response message and stores the thread descriptor in said thread descriptor storage without the data.
Claim 8
Dependent Claim
44 words
A data processing system as claimed in claim 1 wherein each of the plural processing elements processes a join instruction by incrementing a value stored in a memory location and determining from said value whether a continuation to a next instruction is to issue.
Claim 9
Dependent Claim
259 words
In a multithreaded data processing system having a processing element for imperative processing of plural threads of computation, a method for executing load instructions by the processing element to load data from a global memory location of global memory to a local memory location of local memory, the local memory being local to the processing element, the method comprising, for each of said load instructions, the steps of: a) generating a request message from the processing element to a memory controller to read the data held at the global memory location, the request message including a thread descriptor identifying a next operation in one of said plural threads of computation to be processed and an identification of the local memory location; b) generating a response message to respond to the request message using the memory controller wherein the response message comprises the data from the global memory location, the thread descriptor of the request message, and the identification of the local memory location, such that the response message is generated independent of current activity of the processing element; and c) from the response message loading the data from the global memory into the local memory location and storing the thread descriptor of the response message in said thread descriptor storage only upon the storing of all data required for processing of the next operation identified by the thread descriptor, such that the storing of the thread descriptors in the thread descriptor storage and resultant imperative processing of the plural threads of computation are independently performed by the processing element.
Claim 10
Dependent Claim
259 words
In a multithreaded data processing system having a processing element for imperative processing of plural threads of computation, a method for executing load instructions by the processing element to load data from a global memory location of global memory to a local memory location of local memory, the local memory being local to the processing element, the method comprising, for each of said load instructions, the steps of: a) generating a request message from the processing element to a memory controller to read the data held at the global memory location, the request message including a thread descriptor identifying a next operation in one of said plural threads of computation to be processed and an identification of the local memory location; b) generating a response message to respond to the request message using the memory controller wherein the response message comprises the data from the global memory location, the thread descriptor of the request message, and the identification of the local memory location, such that the response message is generated independent of current activity of the processing element; and c) from the response message loading the data from the global memory into the local memory location and storing the thread descriptor of the response message in said thread descriptor storage only upon the storing of all data required for processing of the next operation identified by the thread descriptor, such that the storing of the thread descriptors in the thread descriptor storage and resultant imperative processing of the plural threads of computation are independently performed by the processing element.
Claim 11
Dependent Claim
26 words
A method as recited in claim 8 wherein multiple request messages generated for distinct load instructions are sent before a single corresponding response message is returned.
Claim 12
Dependent Claim
28 words
A method as recited in claim 8 wherein a response message for a second load instruction is returned prior to a response message for a first load instruction.
Claim 13
Dependent Claim
214 words
A data processing system comprising: at least one processing element for imperative processing, in response to thread descriptors from a thread descriptor storage, of individual imperative control flow instructions of each of plural threads of computation; a working memory, coupled to said at least one processing element, comprising frames of memory on which the at least one processing element operates in processing instructions; said thread descriptor storage, coupled to said at least one processing element, for storing a plurality of thread descriptors each of which identifies a next instruction to be processed in one of said plural threads of computation and identifies one of said frames of memory for processing by the at least one processing element; said at least one processing element matching operands required for processing of said next instruction and storing said operands in the frame of memory identified by the thread descriptor, said at least one processing element storing the thread descriptor in said thread descriptor storage only upon the storing of all operands required for processing of said next instruction identified by the thread descriptor, such that said storing of the thread descriptors in said thread descriptor storage and resultant imperative processing of the individual imperative control flow instructions are independently performed by said at least one processing element.
Claim 14
Dependent Claim
214 words
A data processing system comprising: at least one processing element for imperative processing, in response to thread descriptors from a thread descriptor storage, of individual imperative control flow instructions of each of plural threads of computation; a working memory, coupled to said at least one processing element, comprising frames of memory on which the at least one processing element operates in processing instructions; said thread descriptor storage, coupled to said at least one processing element, for storing a plurality of thread descriptors each of which identifies a next instruction to be processed in one of said plural threads of computation and identifies one of said frames of memory for processing by the at least one processing element; said at least one processing element matching operands required for processing of said next instruction and storing said operands in the frame of memory identified by the thread descriptor, said at least one processing element storing the thread descriptor in said thread descriptor storage only upon the storing of all operands required for processing of said next instruction identified by the thread descriptor, such that said storing of the thread descriptors in said thread descriptor storage and resultant imperative processing of the individual imperative control flow instructions are independently performed by said at least one processing element.
Claim 15
Dependent Claim
58 words
A data processing system as recited in claim 11 wherein the thread descriptors are comprised of two parts: a frame pointer that identifies the frame of storage elements residing in local memory to be transferred to working memory for processing by the processing element and an instruction pointer which identifies an instruction which operates on multiple memory locations.
Claim 16
Dependent Claim
28 words
A data processing system as recited in claim 12 wherein memory space allocated for the frames of storage elements is not fixed a priori at a fixed size.
Claim 17
Dependent Claim
16 words
A data processing system as recited in claim 11 wherein the working memory comprises a cache.
Claim 18
Dependent Claim
26 words
A data processing system as recited in claim 11 wherein the at least one processing element comprises a plurality of processing elements that process in parallel.
Claim 19
Dependent Claim
23 words
A data processing system as recited in claim 11 wherein the at least one processing element is a reduced instruction set processing element.
Claim 20
Dependent Claim
30 words
A data processing system as recited in claim 11 wherein the processing element comprises a pipeline such that each stage of the pipeline may operate on separate threads of computation.
Claim 21
Dependent Claim
42 words
A data processing system as recited in claim 17 further comprising a clocking means that clocks thread descriptors out of the thread descriptor storage into the pipeline so that the processing element may act on the thread specified by the thread descriptor.
Claim 22
Dependent Claim
36 words
A data processing system as recited in claim 17 wherein the clocking means also clocks successive stages of the pipeline to shift data from one stage of the pipeline to a next stage of the pipeline.
References Cited (Backward Citations)
US4229790A
Cited
US4481573A
Cited
US4858105A
Cited
US4819155A
Cited
US4943908A
Cited
US5050070A
Cited
US5050068A
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) | 1997-10-03 | 1998-04-04 | 1998-10-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-10-03 | 2002-04-04 | 2002-10-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-10-03 | 2006-04-04 | 2006-10-04 | $7700.00 | Window Closed / Lapsed |