Method and system for constructing a program including out-of-order threads and processor and method for executing threads out-of-order

• US 5,913,925 A
• Filed: 12/16/1996
• Issued: 06/22/1999
• Est. Priority Date: 12/16/1996
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Mallick, Soummya, McDonald, Robert G., Kahle, James A.
• Primary Examiner(s): Lim, Krisna
• Application Number:
  US08/767,490
• Time in Patent Office: 918 Days
• Field of Search: 395/595, 395/676, 395/677, 395/678, 395/706, 712/206, 712/215
• US Class Current: 712/206
• CPC Class Codes: G06F 9/44 Arrangements for executing specific programs
• CPC Class Codes: G06F 9/4843 by program, e.g. task dispatcher, supervisor, operating system

Abstract

A method and system for constructing a program are provided. According to the method, each of a plurality of instructions are assigned to at least one of a plurality of threads. The plurality of threads include first, second, and third threads, where the third thread follows the first thread and precedes the second thread in a logical program order. A data structure associated with the first thread is then constructed. The data structure includes an indication that execution of the second thread is to be initiated prior to initiation of execution of the third thread. According to one embodiment, the indication within the data structure is a pointer that specifies a second data structure associated with the second thread.

Claims

1. A method of constructing a program suitable for execution by a data processing system, said method comprising:

assigning each of a plurality of instructions to at least one of a plurality of threads, said plurality of threads including first, second, and third threads, wherein said third thread follows said first thread and precedes said second thread in a logical program order; and

constructing a data structure associated with said first thread, said data structure including an indication that execution of said second thread is to be initiated prior to initiation of execution of said third thread such that said second and third threads are executed out-of-order, wherein said data structure and said plurality of threads together comprise said program.

2. The method of claim 1, wherein said data structure is a first data structure, and wherein said step of constructing a data structure includes the step of creating a pointer within said first data structure that specifies a second data structure associated with said second thread.

3. The method of claim 2, wherein said data structure is a first data structure, and wherein said step of constructing a data structure includes the step of creating a pointer within said first data structure that specifies a third data structure associated with said third thread.

4. The method of claim 1, wherein:

said method further comprises the step of determining whether said second thread is likely to be data and control independent from threads that precede said second thread in said logical program order; and

wherein said indication is placed within said data structure only in response to a determination that said second thread is likely to be data and control independent from threads that precede said second thread in said logical program order.

5. A system for constructing a program suitable for execution by a data processing system, said system comprising:

means for assigning each of a plurality of instructions to at least one of a plurality of threads, said plurality of threads including first, second, and third threads, wherein said third thread follows said first thread and precedes said second thread in a logical program order; and

means for constructing a data structure associated with said first thread, said data structure including an indication that execution of said second thread is to be initiated prior to initiation of execution of said third thread such that said second and third threads are executed out-of-order, wherein said data structure and said plurality of threads together comprise said program.

6. The system of claim 5, wherein said data structure is a first data structure, and wherein said means for constructing a data structure includes means for creating a pointer within said first data structure that specifies a second data structure associated with said second thread.

7. The system of claim 6, wherein said data structure is a first data structure, and wherein said means for constructing a data structure includes means for creating a pointer within said first data structure that specifies a third data structure associated with said third thread.

8. The system of claim 5, wherein:

said system further comprises means for determining whether said second thread is likely to be data and control independent from threads that precede said second thread in said logical program order; and

said means for constructing a data structure places said indication within said data structure only in response to a determination that said second thread is likely to be data and control independent from threads that precede said second thread in said logical program order.

9. A computer program product for constructing a program suitable for execution by a data processing system, said method comprising:

a computer-readable medium;

instruction code within said computer-readable medium for causing a data processing system to assign each of a plurality of instructions to at least one of a plurality of threads, said plurality of threads including first, second, and third threads, wherein said third thread follows said first thread and precedes said second thread in a logical program order; and

instruction code within said computer-readable medium for causing said data processing system to construct a data structure associated with said first thread, said data structure including indication that execution of said second thread is to be initiated prior to initiation of execution of said third thread such that said second and third threads are executed out-of-order, wherein said data structure and said plurality of threads together comprise said program.

10. A computer program product, comprising:

a program capable of execution by a data processing system, said program including;

a plurality of threads, said plurality of threads including first, second, and third threads, wherein said third thread follows said first thread and precedes said second thread in a logical program order;

a data structure associated with said first thread, said data structure including an indication that execution of said second thread is to be initiated prior to initiation of execution of said third thread such that said second and third threads are executed out-of-order; and

computer-readable medium containing said program.

11. A method of executing a program within a data processing system, said program including first, second, and third threads, wherein said third thread follows said first thread and precedes said second thread in a logical program order, said method comprising:

detecting whether a data structure associated with said first thread includes an indication that execution of said second thread is to be initiated prior to initiation of execution of said third

in response to said detection, initiating execution of said second thread; and

thereafter, initiating execution of said third thread, such that said second and third threads are executed out-of-order.

12. The method of claim 11, wherein said determining step comprises determining if said data structure includes a pointer to a data structure associated with said second thread.

13. The method of claim 11, said method further comprising the step of speculatively initiating execution of said first thread.

14. The method of claim 13, wherein at least a portion of said first and second threads are executed concurrently.

15. The method of claim 11, wherein said program is executed within a processor including a shared resource, said method further comprising:

assigning said first thread to a first thread region and said second thread to a second thread region; and

allocating each of said first and second thread regions a separate instance of said shared resource.

16. The method of claim 15, wherein said second thread is an out-of-order thread, and wherein said assigning step comprises assigning each out-of-order thread to a separate thread region.

17. A processor, comprising:

at least one processing element for executing threads; and

a thread scheduler, including;

means, responsive to receipt of data structure associated with a first thread of a program including first, second, and third threads, said third thread following said first thread and preceding said second thread in a logical program order, for detecting whether said data structure includes an indication that execution of said second thread is to be initiated prior to initiation of execution of said third thread; and

means, responsive to detecting that said data structure includes an indication that execution of said second thread is to be initiated prior to initiation of execution of said third thread, for assigning said second thread to said at least one processing element for execution and for thereafter assigning said third thread to said at least one processing element for execution, such that said second and third threads are executed out-of-order.

18. The processor of claim 17, wherein said means for determining comprises means for determining if said data structure includes a pointer to a data structure associated with said second thread.

19. The processor of claim 17, and further comprising means for speculatively assigning said first thread to said at least one processing element for execution.

20. The processor of claim 17, wherein said at least one processing element includes a first processing element and a second processing element, wherein said first and second processing elements execute said first and second threads concurrently.

21. The processor of claim 17, wherein said processor further comprises:

a shared resource;

means for assigning said first thread to a first thread region and said second thread to a second thread region; and

means for allocating each of said first and second thread regions a separate instance of said shared resource.

22. The processor of claim 17, wherein said second thread is an out-of-order thread, and wherein said means for assigning comprises means for assigning each out-of-order thread to a separate thread region.