US5887166A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and system for constructing a program including a navigation instruction
Assignee: International Business Machines Corp
•
Filing: 1996-12-16
•
Granted: 1999-03-23
•
Expires: 2016-12-16
Abstract
Abstract A method and system are provided for constructing a program executable by a processor including one or more processing elements for executing threads and a thread scheduler for assigning threads to the processing elements for execution. According to the method, a plurality of threads are provided that each include at least one control flow instruction. From one or more control flow instructions within the plurality of threads, a condition upon which execution of a particular thread depends is determined. In response to the determination, at least one navigation instruction executable by the thread scheduler is created that indicates that the particular thread is to be assigned to one of the processing elements for execution in response to the condition.
Inventors
- 👤 Soummya Mallick
- 👤 Robert G. McDonald
- 👤 Edward L. Swarthout
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 13:05
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/46; G06F9/48; G06F9/4806; G06F9/4843; G06F9/4881
Claims Analysis
Total Claims: 29
Claim 1
Independent Claim
143 words
A method of constructing a program executable by a processor, said processor including one or more processing elements for executing threads and a thread scheduler for assigning threads to said one or more processing elements for execution, said method comprising: providing a plurality of threads, each of said plurality of threads including at least one control flow instruction; determining, from one or more control flow instructions within said plurality of threads, a condition upon which execution of a particular thread among said plurality of threads depends; and in response to said determination, creating at least one navigation instruction, said at least one navigation instruction indicating that said particular thread is to be assigned to one of said one or more processing elements in response to said condition, wherein said plurality of threads and said at least one navigation instruction together comprise said program.
Claim 2
Independent Claim
143 words
A method of constructing a program executable by a processor, said processor including one or more processing elements for executing threads and a thread scheduler for assigning threads to said one or more processing elements for execution, said method comprising: providing a plurality of threads, each of said plurality of threads including at least one control flow instruction; determining, from one or more control flow instructions within said plurality of threads, a condition upon which execution of a particular thread among said plurality of threads depends; and in response to said determination, creating at least one navigation instruction, said at least one navigation instruction indicating that said particular thread is to be assigned to one of said one or more processing elements in response to said condition, wherein said plurality of threads and said at least one navigation instruction together comprise said program.
Claim 3
Dependent Claim
47 words
The method of claim 1, said method further comprising constructing a plurality of data structures that are each associated with a respective one of said plurality of threads, wherein each of said plurality of data structures specifies a plurality of possible exit points of an associated thread.
Claim 4
Dependent Claim
23 words
The method of claim 1, wherein said step of creating at least one navigation instruction comprises the step of creating a loop construct.
Claim 5
Dependent Claim
23 words
The method of claim 1, wherein said step of creating at least one navigation instruction comprises the step of creating an if-then-else construct.
Claim 6
Dependent Claim
40 words
The method of claim 1, wherein said method further comprises the steps of: providing a plurality of instructions of a selected instruction set architecture; and assigning each of said plurality instruction to at least one of said plurality of threads.
Claim 7
Independent Claim
108 words
A method of executing a program within a processor including one or more processing elements and a thread scheduler, said method comprising: providing a program including a plurality of threads and at least one navigation instruction, said at least one navigation instruction indicating that a particular thread is to be assigned to one of said one or more processing elements in response to a particular condition; executing said at least one navigation instruction to determine if said particular condition is present; and in response to a determination that said particular condition is present, assigning said particular thread to one of said one or more processing elements for execution.
Claim 8
Independent Claim
108 words
A method of executing a program within a processor including one or more processing elements and a thread scheduler, said method comprising: providing a program including a plurality of threads and at least one navigation instruction, said at least one navigation instruction indicating that a particular thread is to be assigned to one of said one or more processing elements in response to a particular condition; executing said at least one navigation instruction to determine if said particular condition is present; and in response to a determination that said particular condition is present, assigning said particular thread to one of said one or more processing elements for execution.
Claim 9
Dependent Claim
26 words
The method of claim 6, and further comprising the step of: thereafter, executing said particular thread within said one of said one or more processing elements.
Claim 10
Dependent Claim
46 words
The method of claim 6, and further comprising: in response to a determination that said particular condition does not exist, assigning a thread subsequent to said particular thread in logical program order to one of said one or more processing elements without assigning said particular thread.
Claim 11
Dependent Claim
37 words
The method of claim 6, and further comprising: speculatively assigning a thread among said plurality of threads that is not associated with said at least one navigation instruction to one of said one or more processing elements.
Claim 12
Dependent Claim
35 words
The method of claim 6, said at least one navigation instruction comprising a loop construct, wherein said executing step comprises the step of comparing a value of a loop iteration variable to a second value.
Claim 13
Dependent Claim
35 words
The method of claim 6, said at least one navigation instruction comprising an if-then-else construct wherein said executing step comprises the step of determining whether an if statement within said if-then-else construct is logically true.
Claim 14
Independent Claim
147 words
A system for constructing a program executable by a processor including one or more processing elements for executing threads and a thread scheduler for assigning threads to said one or more processing elements for execution, said system comprising: means, responsive to receipt of a plurality of threads, each of said plurality of threads including at least one control flow instruction, for determining, from one or more control flow instructions within said plurality of threads, a condition upon which execution of a particular thread among said plurality of threads depends; and means, responsive to said determination, for creating at least one navigation instruction, said at least one navigation instruction indicating that said particular thread is to be assigned to one of said one or more processing elements in response to said condition, wherein said plurality of threads and said at least one navigation instruction together comprise said program.
Claim 15
Independent Claim
147 words
A system for constructing a program executable by a processor including one or more processing elements for executing threads and a thread scheduler for assigning threads to said one or more processing elements for execution, said system comprising: means, responsive to receipt of a plurality of threads, each of said plurality of threads including at least one control flow instruction, for determining, from one or more control flow instructions within said plurality of threads, a condition upon which execution of a particular thread among said plurality of threads depends; and means, responsive to said determination, for creating at least one navigation instruction, said at least one navigation instruction indicating that said particular thread is to be assigned to one of said one or more processing elements in response to said condition, wherein said plurality of threads and said at least one navigation instruction together comprise said program.
Claim 16
Dependent Claim
49 words
The system of claim 12, said system further comprising means for constructing a plurality of data structures that are each associated with a respective one of said plurality of threads, wherein each of said plurality of data structures specifies a plurality of possible exit points of an associated thread.
Claim 17
Dependent Claim
22 words
The system of claim 12, wherein said means for creating at least one navigation instruction comprises means for creating a loop construct.
Claim 18
Dependent Claim
22 words
The system of claim 12, wherein said means for creating at least one navigation instruction comprises means for creating an if-then-else construct.
Claim 19
Dependent Claim
41 words
The system of claim 12, wherein said system further comprises: means, responsive to receipt of a plurality of instructions of a selected instruction set architecture, for assigning each of said plurality instruction to at least one of said plurality of threads.
Claim 20
Dependent Claim
86 words
A processor, comprising: one or more processing elements for executing threads; means, responsive to loading at least one navigation instruction, said at least one navigation instruction indicating that a particular thread is to be assigned to one of said one or more processing elements in response to a particular condition, for determining if said particular condition is present; and means, responsive to a determination that said particular condition is present, for assigning said particular thread to one of said one or more processing elements for execution.
Claim 21
Dependent Claim
86 words
A processor, comprising: one or more processing elements for executing threads; means, responsive to loading at least one navigation instruction, said at least one navigation instruction indicating that a particular thread is to be assigned to one of said one or more processing elements in response to a particular condition, for determining if said particular condition is present; and means, responsive to a determination that said particular condition is present, for assigning said particular thread to one of said one or more processing elements for execution.
Claim 22
Dependent Claim
49 words
The processor of claim 17, said processor further comprising: means, responsive to a determination that said particular condition does not exist, for assigning a thread subsequent to said particular thread in a logical program order to one of said one or more processing elements without assigning said particular thread.
Claim 23
Dependent Claim
40 words
The processor of claim 17, said processor further comprising: means for speculatively assigning a thread among said plurality of threads that is not associated with said at least one navigation instruction to one of said one or more processing elements.
Claim 24
Dependent Claim
35 words
The processor of claim 17, said at least one navigation instruction comprising a loop construct, wherein said means for determining comprises means for comparing a value of a loop iteration variable to a second value.
Claim 25
Dependent Claim
35 words
The processor of claim 17, said at least one navigation instruction comprising an if-then-else construct, wherein said means for determining comprises means for determining whether an if statement within said if-then-else construct is logically true.
Claim 26
Dependent Claim
155 words
A computer program product for creating a program executable by a processor including one or more processing elements for executing threads and a thread scheduler for assigning threads to said one or more processing elements, said computer program product comprising: signal bearing means; instruction code within said signal bearing means for causing a data processing system to determine, from one or more control flow instructions within a plurality of threads, a condition upon which execution of a particular thread among said plurality of threads depends; and responsive to said determination, instruction code within said signal bearing means for causing said data processing system to create at least one navigation instruction, said at least one navigation instruction indicating that said particular thread is to be assigned to one of said one or more processing elements in response to said condition, wherein said plurality of threads and said at least one navigation instruction together comprise said program.
Claim 27
Dependent Claim
155 words
A computer program product for creating a program executable by a processor including one or more processing elements for executing threads and a thread scheduler for assigning threads to said one or more processing elements, said computer program product comprising: signal bearing means; instruction code within said signal bearing means for causing a data processing system to determine, from one or more control flow instructions within a plurality of threads, a condition upon which execution of a particular thread among said plurality of threads depends; and responsive to said determination, instruction code within said signal bearing means for causing said data processing system to create at least one navigation instruction, said at least one navigation instruction indicating that said particular thread is to be assigned to one of said one or more processing elements in response to said condition, wherein said plurality of threads and said at least one navigation instruction together comprise said program.
Claim 28
Dependent Claim
78 words
A computer program product, comprising: a program executable by a processor including one or more processing elements for executing instructions and a thread scheduler for assigning threads to said one or more processing elements, said program including at least one navigation instruction, said at least one navigation instruction indicating that said particular thread is to be assigned to one of said one or more processing elements in response to said condition; and signal bearing means bearing said program.
Claim 29
Dependent Claim
78 words
A computer program product, comprising: a program executable by a processor including one or more processing elements for executing instructions and a thread scheduler for assigning threads to said one or more processing elements, said program including at least one navigation instruction, said at least one navigation instruction indicating that said particular thread is to be assigned to one of said one or more processing elements in response to said condition; and signal bearing means bearing said program.
References Cited (Backward Citations)
US5179702A
Cited
US5339415A
Cited
US5421014A
Cited
US5524250A
Cited
US5524247A
Cited
US5452459A
Cited
US5404898A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-03-22 | 2002-09-21 | 2003-03-23 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-03-22 | 2006-09-21 | 2007-03-23 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-03-22 | 2010-09-21 | 2011-03-23 | $7700.00 | Window Closed / Lapsed |