US5430850A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Data processing system with synchronization coprocessor for multiple threads
Assignee: Massachusetts Institute of Technology
•
Filing: 1991-07-22
•
Granted: 1995-07-04
•
Expires: 2011-07-22
Abstract
Abstract A multiprocessor system comprises a plurality of processing nodes, each node processing multiple threads of computation. Each node includes a data processor which sequentially processes blocks of code, each block defining a thread of computation. The code includes instructions to send start messages with data values to start new threads of computation. Each node also includes a synchronization coprocessor for processing start messages from the same and other nodes of the system. The coprocessor processes the start messages to store values as operands for threads of computation, to determine when all operands required for a thread of computation have been received and to provide an indication to the data processor that a thread of computation may be initiated. The data processor subsequently nonsynchronously initiates the thread of computation. Preferably, the processors load and store from and to a common memory with the translation from a local virtual address to a local physical address. The data processor creates messages to remote nodes using a global virtual address which is translated before transmission to a node designation and a local virtual address at the remote node. The synchronization coprocessor is a pipeline processor in which a data cache stage is modified to increment and test a counter value during a join operation.
Inventors
- 👤 Gregory M. Papadopoulos
- 👤 Rishiyur S. Nikhil
- 👤 Robert J. Greiner
- 👤 Arvind
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-31 17:44
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/46; G06F9/48; G06F9/4806; G06F9/4843; G06F9/30; G06F9/30003; G06F9/30076; G06F9/3009; G06F9/38; G06F9/3836; G06F9/3851
Claims Analysis
Total Claims: 28
Claim 1
Independent Claim
131 words
A data processing system comprising: a data processor for processing threads of computation with respect to frames of data, threads of computation including operations to generate messages with operands for initiating new threads of computation; and a synchronization coprocessor for responding to messages by processing message handlers which store the operands carried by the messages into the frames of data and which indicate to the data processor when conditions including availability of the operands in the frames of data are met such that new threads of computation are to be performed, the data processor being synchronized to availability of operands by initiating processing of the new threads of computation with respect to the frames of data after the synchronization coprocessor indicates that the new threads of computation are to be performed.
Claim 2
Dependent Claim
131 words
A data processing system comprising: a data processor for processing threads of computation with respect to frames of data, threads of computation including operations to generate messages with operands for initiating new threads of computation; and a synchronization coprocessor for responding to messages by processing message handlers which store the operands carried by the messages into the frames of data and which indicate to the data processor when conditions including availability of the operands in the frames of data are met such that new threads of computation are to be performed, the data processor being synchronized to availability of operands by initiating processing of the new threads of computation with respect to the frames of data after the synchronization coprocessor indicates that the new threads of computation are to be performed.
Claim 3
Dependent Claim
32 words
A data processing system as claimed in claim 1 further comprising a message formatter instructed by the data processor to create and send messages to remote nodes of the data processing system.
Claim 4
Dependent Claim
56 words
A data processing system as claimed in claim 2 wherein the message formatter comprises registers on a common bus with the data processor in the address space of the data processor and the data processor instructs the message formatter to create and send message to remote nodes by memory mapped stores to the message formatter registers.
Claim 5
Dependent Claim
75 words
A data processing system as claimed in claim 3 wherein the data processor loads global virtual addresses along its data bus into registers in the message formatter, a number of bits in the global virtual address being greater than a number of bits available in the local virtual address space of the data processor, and the message formatter translates the global virtual address to a node designation and a local virtual address on that node.
Claim 6
Dependent Claim
40 words
A data processing system as claimed in claim 4 wherein each node translates local virtual addresses to local physical addresses for local memory accesses from the data processor and for local memory accesses in response to messages from remote nodes.
Claim 7
Dependent Claim
41 words
A data processing system as claimed in claim 1 wherein the data processor and the synchronization coprocessor communicate with a common local memory in which operands are stored within activation frames by the synchronization coprocessor and fetched by the data processor.
Claim 8
Dependent Claim
22 words
A data processing system as claimed in claim 6 further comprising a cache memory shared by the data processor and synchronization coprocessor.
Claim 9
Dependent Claim
23 words
A data processing system as claimed in claim 7 wherein the data processor is a single chip microprocessor having a cache memory thereon.
Claim 10
Dependent Claim
39 words
A data processing system as claimed in claim 1 wherein the synchronization coprocessor comprises a queue to which continuations are posted to serve as indications to the data processor that the new threads of computation are to be initiated.
Claim 11
Dependent Claim
22 words
A data processing system as claimed in claim 9 wherein the queue presents continuations according to priority to continue processing active frames.
Claim 12
Dependent Claim
28 words
A data processing system as claimed in claim 10 wherein the synchronization coprocessor comprises a frame registry which identifies active frames to be given priority in the queue.
Claim 13
Dependent Claim
25 words
A data processing system as claimed in claim 11 wherein the system maintains a software list of continuations where capacity of the registry is exceeded.
Claim 14
Dependent Claim
27 words
A data processing system as claimed in claim 9 wherein the continuations comprise a pointer to an activation frame and a pointer to a data processor instruction.
Claim 15
Dependent Claim
37 words
A data processing system as claimed in claim 9 wherein the queue is on a bus of the data processor and new threads of computation are initiated by the data processor by loading continuations from the queue.
Claim 16
Dependent Claim
44 words
A data processing system as claimed in claim 1 wherein the messages include an object oriented message which identifies a method, an object and argument, and the synchronization coprocessor stores the argument in a frame and provides a frame pointer to the data processor.
Claim 17
Dependent Claim
28 words
A data processing system as claimed in claim 15 wherein the synchronization coprocessor processes the method and object identifications to locate an instruction pointer for the data processor.
Claim 18
Dependent Claim
35 words
A data processing system as claimed in claim 1 which is a multiprocessor system of a plurality of processing nodes, each processing node comprising one of said data processors and one of said synchronization coprocessors.
Claim 19
Dependent Claim
80 words
A data processing system as claimed in claim 16 wherein each data processor operates on a local virtual address space, and each node comprises means for translating from the local virtual address space to a local physical address space, each data processor generating a global virtual address space to access an address in a remote node, and each node comprising means for translating the global virtual address to a node designation and a local virtual address of the remote node.
Claim 20
Dependent Claim
32 words
A data processing system as claimed in claim 1 wherein the messages include a start message which comprises a pointer to an activation frame and a pointer to a synchronization coprocessor instruction.
Claim 21
Dependent Claim
37 words
A data processing system as claimed in claim 1 wherein the synchronization coprocessor comprises a start processor for processing start messages and a remote memory processor for processing remote memory load and store instructions from remote nodes.
Claim 22
Dependent Claim
17 words
A data processing system as claimed in claim 1 wherein the synchronization coprocessor is a programmable processor.
Claim 23
Dependent Claim
28 words
A data processing system as claimed in claim 1 wherein the synchronization coprocessor comprises a processing pipeline including hardware for counting operands received for the threads of computation.
Claim 24
Dependent Claim
53 words
A data processing system as claimed in claim 1 wherein the synchronization coprocessor comprises a processing pipeline including increment and test hardware for incrementing a value fetched from cache memory, testing the value to test whether all operands for a computational thread have been received, and returning the incremented value to cache memory.
Claim 25
Dependent Claim
141 words
In a multiprocessor system comprising a plurality of processing nodes, each node processing multiple threads of computation, the system comprising at each processing node: a data processor which processes threads of code, the code including instructions to create messages with data values to start new threads of computation; and a synchronization coprocessor for processing messages from the same node and other nodes of the system, the synchronization coprocessor processing messages to store values from the messages as operands for the threads of computation, to determine when all operands required for the threads of computation have been received and to provide indications to the data processor that the threads of computation are to be initiated, the data processor nonsynchronously initiating processing of the threads of computation after completion of prior threads of computation in response to the indications from the synchronization coprocessor.
Claim 26
Dependent Claim
141 words
In a multiprocessor system comprising a plurality of processing nodes, each node processing multiple threads of computation, the system comprising at each processing node: a data processor which processes threads of code, the code including instructions to create messages with data values to start new threads of computation; and a synchronization coprocessor for processing messages from the same node and other nodes of the system, the synchronization coprocessor processing messages to store values from the messages as operands for the threads of computation, to determine when all operands required for the threads of computation have been received and to provide indications to the data processor that the threads of computation are to be initiated, the data processor nonsynchronously initiating processing of the threads of computation after completion of prior threads of computation in response to the indications from the synchronization coprocessor.
Claim 27
Dependent Claim
157 words
A data processing system comprising: a data processor which sequentially processes, as threads of code, code blocks including local memory load and store instructions, start instructions which cause start messages to be sent with data values to start new threads of computation and remote memory load and store instructions which cause messages to be sent to remote memory locations to fetch or store data from or in the remote memory locations; and a synchronization coprocessor which receives start messages and processes the start messages to store data values from the start messages as operands for the threads of computation, to determine when all operands required for the threads of computation have been received and to provide indications to the data processor that the threads of computation are to be initiated, the data processor nonsynchronously initiating processing of the threads of computation after completion of prior threads of computation in response to the indications from the synchronization coprocessor.
Claim 28
Dependent Claim
157 words
A data processing system comprising: a data processor which sequentially processes, as threads of code, code blocks including local memory load and store instructions, start instructions which cause start messages to be sent with data values to start new threads of computation and remote memory load and store instructions which cause messages to be sent to remote memory locations to fetch or store data from or in the remote memory locations; and a synchronization coprocessor which receives start messages and processes the start messages to store data values from the start messages as operands for the threads of computation, to determine when all operands required for the threads of computation have been received and to provide indications to the data processor that the threads of computation are to be initiated, the data processor nonsynchronously initiating processing of the threads of computation after completion of prior threads of computation in response to the indications from the synchronization coprocessor.
References Cited (Backward Citations)
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) | 1998-07-03 | 1999-01-02 | 1999-07-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-07-03 | 2003-01-02 | 2003-07-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-07-03 | 2007-01-02 | 2007-07-04 | $7700.00 | Window Closed / Lapsed |