Method of using a distinct flow of computational control as a reusable abstract data object

• US 7,140,018 B1
• Filed: 06/20/2000
• Issued: 11/21/2006
• Est. Priority Date: 06/20/2000
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Beatty, Harry J. III, Elmendorf, Peter C.
• Primary Examiner(s): An, Meng-Ai T.
• Assistant Examiner(s): To, Jennifer N.
• Application Number:
  US09/597,524
• Time in Patent Office: 2,345 Days
• Field of Search: 709/100, 709/102, 709/104, 709/106, 709/107, 709/310, 709/313, 709/330, 718100-108, 719/310, 719/330, 719312-316, 711147-173
• US Class Current: 718/102
• CPC Class Codes: G06F 9/38 Concurrent instruction execution, e.g. pipeline or look ahead
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming
• CPC Class Codes: G06F 9/544 Buffers; Shared memory; Pipes

Abstract

A method of parallel processing in which there is first provided a first thread which represents an independent flow of control managed by a program structure, the first thread having two states, a first state processing work for the program structure and a second state undispatched awaiting work to process; and a second thread which represents an independent flow of control managed by a program structure separate from the first thread. The method includes using the second thread to prepare work for the first thread to process and placing the work prepared by the second thread in a queue for processing by the first thread. If the first thread is awaiting work to process when the work prepared by the second thread is placed in the queue, the method includes dispatching the first thread and using it to process the work in the queue. If the first thread is processing other work when the work prepared by the second thread is placed in the queue, the method includes using the first thread to complete processing of the other work, access the work in the queue, and then process the work in the queue.

Claims

1. A method of parallel processing in a memory structure comprising:

creating a first thread in the memory structure which represents an independent flow of control managed by a program structure, said first thread having two states, a first state processing work for the program structure and a second state undispatched awaiting work to process;

providing a second thread in the memory structure which represents an independent flow of control managed by a program structure separate from the first thread;

using the second thread to prepare work for the first thread to process;

placing the work prepared by the second thread in a queue for processing by the first thread and marking the work as not complete;

if the first thread is in the second state awaiting work to process when the work prepared by the second thread is placed in the queue, dispatching the first thread and using it to process the work in the queue;

if the first thread is in the first state processing other work when the work prepared by the second thread is placed in the queue, using the first thread to complete processing of the other work, access the work in the queue, and then process the work in the queue; and

using the program structure to destroy the first thread in the memory structure after the first thread completes a desired amount of work.

2. The method of claim 1 wherein the second thread continues to place additional work in the queue, and the first thread sequentially processes the additional work in the queue as it completes processing prior work.

3. The method of claim 1 wherein if the first thread is processing other work when the work prepared by the second thread is placed in the queue, and when the first thread completes processing of the work in the queue, using the first thread to mark the completed work as complete, wherein subsequent work from the second thread is made to wait until the previous work in the first thread is marked complete.

4. The method of claim 1 wherein the first thread is reused to process other work before being destroyed.

5. The method of claim 1 including providing a memory structure having a plurality of planes, each plane having a context comprising:

a) a thread representing an independent flow of control managed by a program structure, b) a heap portion for data structure, and c) a plurality of stack portions for function arguments, each thread using a different stack portion, and wherein only one of the first and second threads uses a context at any particular time.

6. A method of parallel processing in a memory structure comprising:

creating a first thread in the memory structure which represents an independent flow of control managed by a program structure, said first thread having two states, a first state processing work for the program structure and a second state undispatched awaiting work to process;

providing a second thread in the memory structure which represents an independent flow of control managed by a program structure separate from the first thread;

using the second thread to prepare work for the first thread to process;

placing the work prepared by the second thread in a queue for processing by the first thread, the work placed in the queue being marked as not complete;

if the first thread is in the second state awaiting work to process when the work prepared by the second thread is placed in the queue, dispatching the first thread and using it to process the work in the queue;

if the first thread is in the first state processing other work when the work prepared by the second thread is placed in the queue, using the first thread to complete processing of the other work, access the work in the queue, and then process the work in the queue;

using the second thread to place additional work in the queue;

using the first thread to sequentially process the additional work in the queue as it completes processing prior work; and

using the program structure to destroy the first thread in the memory structure after the first thread completes a desired amount of work.

7. The method of claim 6 wherein if the first thread is processing other work when the work prepared by the second thread is placed in the queue, and when the first thread completes processing of the work in the queue, using the first thread to mark the completed work as complete, wherein subsequent work from the second thread is made to wait until the previous work in the first thread is marked complete.

8. The method of claim 6 wherein the first thread is reused to process other work before being destroyed.

9. The method of claim 6 including providing a memory structure having a plurality of planes, each plane having a context comprising:

a) a thread representing an independent flow of control managed by a program structure, b) a heap portion for data structure, and c) a plurality of stack portions for function arguments, each thread using a different stack portion, and wherein only one of the first and second threads uses a context at any particular time.

10. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps of parallel processing in a memory structure using i) a first thread which represents an independent flow of control managed by a program structure, said first thread having two states, a first state processing work for the program structure and a second state undispatched awaiting work to process, and ii) a second thread which represents an independent flow of control managed by a program structure separate from the first thread, said method steps comprising:

creating the first thread;

using the second thread to prepare work for the first thread to process;

placing the work prepared by the second thread in a queue for processing by the first thread and marking the work as not complete;

if the first thread is in the second state awaiting work to process when the work prepared by the second thread is placed in the queue, dispatching the first thread and using it to process the work in the queue;

if the first thread is in the first state processing other work when the work prepared by the second thread is placed in the queue, using the first thread to complete processing of the other work, access the work in the queue, and then process the work in the queue; and

using the program structure to destroy the first thread in the memory structure after the first thread completes a desired amount of work.

11. The program storage device of claim 10 wherein, in the method steps, the second thread continues to place additional work in the queue, and the first thread sequentially processes the additional work in the queue as it completes processing prior work.

12. The program storage device of claim 10 wherein, in the method steps, if the first thread is processing other work when the work prepared by the second thread is placed in the queue, and when the first thread completes processing of the work in the queue, using the first thread to mark the completed work as complete, wherein subsequent work from the second thread is made to wait until the previous work in the first thread is marked complete.

13. The program storage device of claim 10 wherein, in the method steps, the first thread is reused to process other work before being destroyed.

14. The program storage device of claim 10 wherein the memory structure includes a plurality of planes, each plane having a context comprising:

a) a thread representing an independent flow of control managed by a program structure, b) a heap portion for data structure, and c) a plurality of stack portions for function arguments, each thread using a different stack portion, and wherein only one of the first and second threads uses a context at any particular time.