US5553305A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System for synchronizing execution by a processing element of threads within a process using a state indicator
Assignee: International Business Machines Corp
•
Filing: 1992-07-15
•
Granted: 1996-09-03
•
Expires: 2012-07-15
Abstract
Abstract A method and system for synchronizing execution by a processing element of threads within a process. Before execution of a thread commences, a determination is made as to whether all of the required resources for execution of the thread are available in a cache local to the processing element. If the resources are not available, then the resources are fetched from main storage and stored in one or more local caches before execution begins. If the resources are available, then execution of the thread may begin. During execution of the thread and, in particular, an instruction within the thread, the instruction may require data in order to successfully complete its execution. When this occurs, a determination is made as to whether the necessary data is available. If the data is available, the result of the instruction execution is stored and execution of the thread continues. However, if the data is unavailable, then the thread is deferred until the data becomes available and a new thread is processed. When deferring a thread, the thread is placed in the memory location which is to receive the required data. Once the data is available, the thread is removed from the data location and placed on a queue for execution and the data is stored in the location.
Inventors
- 👤 Steven L. Gregor
- 👤 Robert A. Iannucci
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-31 05:13
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/46; G06F9/48; G06F9/4806; G06F9/4843; G06F9/52; G06F2209/00; G06F2209/50; G06F2209/503
Claims Analysis
Total Claims: 34
Claim 1
Independent Claim
231 words
A method for synchronizing execution by a processing element of threads within at least one process, said method comprising the steps of: executing a first thread and a second thread within the at least one process on said processing element, said processing element having associated therewith at least a portion of a main memory; fetching during said first thread execution from a local frame operand cache a datum field; fetching from a state bit cache a state indicator, said state indicator being associated with said datum field and having a first state value; determining based on said first state value whether said datum field includes a first datum comprising an operand available for use by said first thread; deferring execution of said first thread when said first datum is unavailable and continuing execution of said second thread on said processing element; and determining a second state for said state indicator, said second state replacing said first state during said first thread execution; wherein said second state determining step includes the steps of: selecting from said first thread a state function to be used in determining said second state; using said state function to select from one of a plurality of tables one or more possible second states for said indicator; and using said first state to choose from said one or more possible second states said second state for said indicator.
Claim 2
Independent Claim
231 words
A method for synchronizing execution by a processing element of threads within at least one process, said method comprising the steps of: executing a first thread and a second thread within the at least one process on said processing element, said processing element having associated therewith at least a portion of a main memory; fetching during said first thread execution from a local frame operand cache a datum field; fetching from a state bit cache a state indicator, said state indicator being associated with said datum field and having a first state value; determining based on said first state value whether said datum field includes a first datum comprising an operand available for use by said first thread; deferring execution of said first thread when said first datum is unavailable and continuing execution of said second thread on said processing element; and determining a second state for said state indicator, said second state replacing said first state during said first thread execution; wherein said second state determining step includes the steps of: selecting from said first thread a state function to be used in determining said second state; using said state function to select from one of a plurality of tables one or more possible second states for said indicator; and using said first state to choose from said one or more possible second states said second state for said indicator.
Claim 3
Dependent Claim
29 words
The method of claim 1, wherein said first state represents a current state of said first datum and said second state represents a next state of said first datum.
Claim 4
Dependent Claim
31 words
The method of claim 1, wherein said first thread is represented by a continuation descriptor and said deferring step includes the step of storing said continuation descriptor within said datum field.
Claim 5
Dependent Claim
31 words
The method of claim 3, wherein said continuation descriptor is compressed before being stored in said datum field and said datum field can receive a plurality of said compressed continuation descriptors.
Claim 6
Dependent Claim
25 words
The method of claim 4, further including the step of awakening said deferred first thread when said first datum is available for said first thread.
Claim 7
Dependent Claim
22 words
The method of claim 5, wherein said awakening step includes the step of removing said compressed continuation descriptors from said datum field.
Claim 8
Dependent Claim
21 words
The method of claim 6, wherein said removed compressed continuation descriptors are stored on a queue local to said processing element.
Claim 9
Dependent Claim
29 words
The method of claim 6, wherein said awakening step further includes the step of storing said first datum in said datum field when said compressed continuation descriptors are removed.
Claim 10
Independent Claim
268 words
A system for synchronizing execution by a processing element of threads within at least one process, said system comprising: a local frame operand cache, said local frame operand cache including a datum field; a state bit cache, said state bit cache including a state indicator corresponding to said datum field; means for executing by said processing element a first thread and a second thread within the at least one process, said processing element having associated therewith at least a portion of a main memory; means for fetching from said local frame cache said datum field and from said state bit cache said state indicator having a first state value; means for determining based on said first state value whether said datum field includes a first datum comprising an operand available for use by said thread; means for deferring execution of said first thread when said first datum is unavailable and continuing execution of said second thread on said processing element; and means for determining a second state for said state indicator, said second state replacing said first state during said first thread execution; wherein said second state determining means comprises: means for selecting from said first thread a state function to be used in determining said second state; a plurality of tables each having one or more possible second states for said indicator; means for using said state function to select from one of said plurality of tables said one or more possible second states; and means for using said first state to choose from said one or more possible second states said second state for said indicator.
Claim 11
Independent Claim
268 words
A system for synchronizing execution by a processing element of threads within at least one process, said system comprising: a local frame operand cache, said local frame operand cache including a datum field; a state bit cache, said state bit cache including a state indicator corresponding to said datum field; means for executing by said processing element a first thread and a second thread within the at least one process, said processing element having associated therewith at least a portion of a main memory; means for fetching from said local frame cache said datum field and from said state bit cache said state indicator having a first state value; means for determining based on said first state value whether said datum field includes a first datum comprising an operand available for use by said thread; means for deferring execution of said first thread when said first datum is unavailable and continuing execution of said second thread on said processing element; and means for determining a second state for said state indicator, said second state replacing said first state during said first thread execution; wherein said second state determining means comprises: means for selecting from said first thread a state function to be used in determining said second state; a plurality of tables each having one or more possible second states for said indicator; means for using said state function to select from one of said plurality of tables said one or more possible second states; and means for using said first state to choose from said one or more possible second states said second state for said indicator.
Claim 12
Independent Claim
29 words
The system of claims 9, wherein said first state represents a current state of said first datum and said second state represents a next state of said first datum.
Claim 13
Dependent Claim
61 words
The system of claim 10, further comprising a main storage, said main storage comprising a copy of said datum field and a copy of said state indicator, said copy of said datum field being copied from main storage to said local frame cache and said copy of said state indicator being copied from said main storage to said state bit cache.
Claim 14
Dependent Claim
30 words
The system of claim 9, wherein said thread is represented by a continuation descriptor and said means for deferring comprises means for storing said continuation descriptor within said datum field.
Claim 15
Dependent Claim
31 words
The system of claim 12, wherein said continuation descriptor is compressed before being stored in said datum field and said datum field can receive a plurality of said compressed continuation descriptors.
Claim 16
Dependent Claim
24 words
The system of claim 13, further including means for awakening said deferred first thread when said first datum is available for said first thread.
Claim 17
Dependent Claim
19 words
The system of claim 14, wherein said awakening means comprises removing said compressed continuation descriptors from said datum field.
Claim 18
Dependent Claim
26 words
The system of claim 15, further comprising a queue local to said processing element and wherein said removed compressed continuation descriptors are stored on said queue.
Claim 19
Dependent Claim
29 words
The system of claim 15, wherein said means for awakening further comprises means for storing said first datum in said datum field when said compressed continuation descriptors are removed.
Claim 20
Independent Claim
220 words
A method for synchronizing execution by a processing element of threads within at least one process, each of said threads including a plurality of instructions, said method comprising the steps of: executing an instruction of said thread on said processing elements, said processing element having associated therewith at least a portion of a main memory; fetching during said instruction execution from a local frame operand cache at least one source operand and from a state bit cache at least one state indicator having a first state value, said at least one state indicator corresponding to said at least one source operand; fetching from said instruction at least one state function associated with said at least one fetched source operand; using said at least one state function to select from one of a plurality of tables one or more possible second states for said at least one state indicator, each of said second states having a corresponding flag indicator; using said first state to choose from said one or more possible second states a second state for said state indicator; replacing said first state with said second state during said thread execution; and having said thread perform one of a plurality of actions after said instruction execution, said action being specified by said flag indicator associated with said chosen second state.
Claim 21
Independent Claim
220 words
A method for synchronizing execution by a processing element of threads within at least one process, each of said threads including a plurality of instructions, said method comprising the steps of: executing an instruction of said thread on said processing elements, said processing element having associated therewith at least a portion of a main memory; fetching during said instruction execution from a local frame operand cache at least one source operand and from a state bit cache at least one state indicator having a first state value, said at least one state indicator corresponding to said at least one source operand; fetching from said instruction at least one state function associated with said at least one fetched source operand; using said at least one state function to select from one of a plurality of tables one or more possible second states for said at least one state indicator, each of said second states having a corresponding flag indicator; using said first state to choose from said one or more possible second states a second state for said state indicator; replacing said first state with said second state during said thread execution; and having said thread perform one of a plurality of actions after said instruction execution, said action being specified by said flag indicator associated with said chosen second state.
Claim 22
Dependent Claim
29 words
The method of claim 18, wherein said plurality of actions includes the following actions: continuing execution of said thread, deferring execution of said thread and awakening a deferred thread.
Claim 23
Dependent Claim
31 words
The method of claim 19, wherein said thread is represented by a continuation descriptor and said deferring execution action includes the step of storing said continuation descriptor within a source operand.
Claim 24
Dependent Claim
26 words
The method of claim 20, wherein said continuation descriptor is compressed before being stored and said source operand can receive a plurality of compressed continuation descriptors.
Claim 25
Dependent Claim
22 words
The method of claim 21, wherein said awakening action includes the step of removing a compressed continuation descriptor from a source operand.
Claim 26
Dependent Claim
25 words
The method of claim 22, wherein said awakening action further includes the step of storing a source operand when said compressed continuation descriptor is removed.
Claim 27
Dependent Claim
20 words
The method of claim 22, wherein said removed continuation descriptor is stored on a queue local to said processing element.
Claim 28
Independent Claim
270 words
A system for synchronizing execution by a processing element of threads within at least one process, each of said threads including a plurality of instructions, said system comprising: means for executing an instruction of said thread on said processing element, said processing element having associated therewith at least a portion of a main memory; a local frame operand cache, said local frame operand cache including a plurality of source operands; a state bit cache, said state bit cache including a plurality of state indicators, each of said state indicators having a first state value, and wherein one of said state indicators corresponds to one of said source operands; means for fetching during said instruction execution from said local frame operand cache at least one source operand and from said state bit cache at least one corresponding state indicator; means for fetching from said instruction at least one state function associated with said at least one source operand; a plurality of tables each having one or more possible second states for each of said state indicators; means for using said at least one state function to select from one of said plurality of tables said one or more possible second states, each of said second states having an associated flag indicator; means for using said first state to choose from said one or more possible second states a second state for said state indicator; means for replacing said first state with said second state; and means for having said thread perform one of a plurality of actions, said action being specified by said flag indicator associated with said chosen second state.
Claim 29
Independent Claim
270 words
A system for synchronizing execution by a processing element of threads within at least one process, each of said threads including a plurality of instructions, said system comprising: means for executing an instruction of said thread on said processing element, said processing element having associated therewith at least a portion of a main memory; a local frame operand cache, said local frame operand cache including a plurality of source operands; a state bit cache, said state bit cache including a plurality of state indicators, each of said state indicators having a first state value, and wherein one of said state indicators corresponds to one of said source operands; means for fetching during said instruction execution from said local frame operand cache at least one source operand and from said state bit cache at least one corresponding state indicator; means for fetching from said instruction at least one state function associated with said at least one source operand; a plurality of tables each having one or more possible second states for each of said state indicators; means for using said at least one state function to select from one of said plurality of tables said one or more possible second states, each of said second states having an associated flag indicator; means for using said first state to choose from said one or more possible second states a second state for said state indicator; means for replacing said first state with said second state; and means for having said thread perform one of a plurality of actions, said action being specified by said flag indicator associated with said chosen second state.
Claim 30
Dependent Claim
32 words
The system of claim 25, wherein said plurality of actions includes means for continuing execution of said thread, means for deferring execution of said thread and means for awakening a deferred thread.
Claim 31
Dependent Claim
33 words
The system of claim 26, wherein said thread is represented by a continuation descriptor and said means for deferring includes means for storing said continuation descriptor within said at least one source operand.
Claim 32
Dependent Claim
36 words
The system of claim 27, further comprising means for compressing said continuation descriptor before said continuation descriptor is stored and wherein said at least one source operand can receive a plurality of said compressed continuation descriptors.
Claim 33
Dependent Claim
25 words
The system of claim 28, wherein said means for awakening includes means for removing said compressed continuation descriptors from said at least one source operand.
Claim 34
Dependent Claim
25 words
The system of claim 29, further comprising a queue local to said processing element and wherein said removed continuation descriptors are stored on said queue.
References Cited (Backward Citations)
US3573736A
Cited
US4439829A
Cited
US4583165A
Cited
US4503499A
Cited
US4953078A
Cited
EP0381655A2
Cited
US5168554A
Cited
US5197138A
Cited
US5226138A
Cited
US5301295A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-09-03 | 2000-03-04 | 2000-09-03 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-09-03 | 2004-03-04 | 2004-09-03 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-09-03 | 2008-03-04 | 2008-09-03 | $7700.00 | Window Closed / Lapsed |