US4809159A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Control token mechanism for sequence dependent instruction execution in a multiprocessor
Assignee: Omron Corp
•
Filing: 1988-01-21
•
Granted: 1989-02-28
•
Expires: 2008-01-21
Abstract
Abstract A controlled flow parallel computer incorporating a node drive register which designates the location of executable instructions. The node drive register allows instructions to be executed concurrently and non-deterministically without a complex control. Control token locations in the node drive register associated with a given instruction are filled upon the completion of a prior instruction required to be executed before executing that instruction. The instruction is ready for execution once the control token locations are filled.
Inventors
- 👤 Masahiro Sowa
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 09:02
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/44; G06F9/448; G06F9/4494
Claims Analysis
Total Claims: 16
Claim 1
Independent Claim
137 words
A control flow parallel computer system comprising: a plurality of processors; a main memory means for storing information and having memory locations accessible by said plurality of processors; and node drive register means for storing information relating to execution of instructions, said node drive register means being accessible by said plurality of processors, said node drive register means storing a plurality of words, each of said words including a location storing a pointer indicating an instruction to be executed, and a plurality of control token locations for storing control tokens for indicating when the instruction indicated by said pointer is to be executed, each of said control token locations being filled with a control token upon completion of the execution of a prior instruction required to be executed before execution of said instruction indicated by said pointer.
Claim 2
Dependent Claim
137 words
A control flow parallel computer system comprising: a plurality of processors; a main memory means for storing information and having memory locations accessible by said plurality of processors; and node drive register means for storing information relating to execution of instructions, said node drive register means being accessible by said plurality of processors, said node drive register means storing a plurality of words, each of said words including a location storing a pointer indicating an instruction to be executed, and a plurality of control token locations for storing control tokens for indicating when the instruction indicated by said pointer is to be executed, each of said control token locations being filled with a control token upon completion of the execution of a prior instruction required to be executed before execution of said instruction indicated by said pointer.
Claim 3
Dependent Claim
64 words
A system as set forth in claim 1 wherein each said word also includes a location for storing an indication that all tokens necessary for the instructions indicated by the pointer of that word are being stored, thereby indicating the storage of a complete token packet designating to said processors that the instruction designated by the pointer of that word is ready for execution.
Claim 4
Dependent Claim
60 words
A system as set forth in claim 1 wherein said main memory means and said node drive register means are multiport memories available to be accessed by a plurality of said processors simultaneously whereby a plurality of complete token packets are available to be accessed simultaneously and instructions designated by said complete token packets are available to be executed simultaneously.
Claim 5
Dependent Claim
21 words
A system as set forth in claim 3 wherein said main memory means comprises a program memory and a data memory.
Claim 6
Dependent Claim
64 words
A system as set forth in claim 1 including means for storing said instruction to be executed, said instruction to be executed including an address of an operand needed for execution of said instruction, an address for storing a result of the execution of said instruction, and an address for placing a control token of a word of an instruction to be subsequently examined.
Claim 7
Dependent Claim
58 words
A system as set forth in claim 5 wherein each said word contains a location for storing an indicator for mapping said operand address and said result address into said main memory, and further including an address translation register for mapping said operand address and said result address into said main memory as a function of said indicator.
Claim 8
Independent Claim
182 words
A method of performing control flow processing using a plurality of processors, a main memory for storing programs and data, and a node drive register, said method comprising: establishing a plurality of nodes, each node including an instruction to be executed; storing a word for each of said nodes in said node drive register, each word in said node drive register having a location storing a pointer indicating its node and locations for storing controls tokens for its node, a pointer and all control tokens for one node comprising a complete token packet; for each of said processors; accessing said register and fetching a complete token packet, accessing said main memory and fetching data for executing the node indicated by the pointer of said complete token packet; after execution of an instruction of a node, creating a further token packet including a control token and pointer, sending some further token packet to said node drive register means, and storing a control token in each word of the node drive register pointing to a node to be executed subsequently to the executed node.
Claim 9
Independent Claim
182 words
A method of performing control flow processing using a plurality of processors, a main memory for storing programs and data, and a node drive register, said method comprising: establishing a plurality of nodes, each node including an instruction to be executed; storing a word for each of said nodes in said node drive register, each word in said node drive register having a location storing a pointer indicating its node and locations for storing controls tokens for its node, a pointer and all control tokens for one node comprising a complete token packet; for each of said processors; accessing said register and fetching a complete token packet, accessing said main memory and fetching data for executing the node indicated by the pointer of said complete token packet; after execution of an instruction of a node, creating a further token packet including a control token and pointer, sending some further token packet to said node drive register means, and storing a control token in each word of the node drive register pointing to a node to be executed subsequently to the executed node.
Claim 10
Dependent Claim
70 words
A method as set forth in claim 7 wherein said step of establishing a plurality of nodes comprises, for each node: storing a node packet in said main memory, said node packet containing an instruction to be executed, addresses of any operands necessary for carrying out said instruction, an address for storage of a result of said instruction, and addresses of token packets pointing to nodes to be executed subsequently.
Claim 11
Dependent Claim
30 words
A method as set forth in claim 8 including storing a color indicator code with each token packet and determining said addresses as a function of said color indicator code.
Claim 12
Dependent Claim
23 words
A method as set forth in claim 9 including assigning the same color indicator code to all token packets having a similar instruction.
Claim 13
Dependent Claim
56 words
A method as set forth in claim 8 wherein each control token location stores a value indicating the number of tokens being stored and wherein said step of storing a control token comprises incrementing the value of a control token location at each of the words at said addresses of token packets of said node packet.
Claim 14
Dependent Claim
40 words
A method as set forth in claim 11 further including, after the step of fetching a complete token packet, placing an indication in the word of the complete token packet which was fetched that the associated node is being executed.
Claim 15
Dependent Claim
24 words
A method as set forth in claim 11 including, after said incrementing step, deleting the tokens of the word of the node being executed.
Claim 16
Dependent Claim
33 words
A method as set forth in claim 11 including performing serial processing by assigning only 1 control token to each token packet and incrementing only 1 control token after execution of a node.
References Cited (Backward Citations)
US4051551A
Cited
US4228496A
Cited
US4387427A
Cited
US4414624A
Cited
US4394727A
Cited
US4491937A
Cited
US4525778A
Cited
US4553203A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1992-02-28 | 1992-08-29 | 1993-02-28 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1996-02-28 | 1996-08-29 | 1997-02-28 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2000-02-28 | 2000-08-29 | 2001-02-28 | $7700.00 | Window Closed / Lapsed |