Component extensible parallel execution of multiple threads assembled from program components specified with partial inter-component sequence information

• US 6,205,465 B1
• Filed: 07/22/1998
• Issued: 03/20/2001
• Est. Priority Date: 07/22/1998
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Schleimer, Stephen I., Schoening, Charles B., Smith, Richard J. Jr.
• Primary Examiner(s): Kim, Kenneth S.
• Application Number:
  US09/120,984
• Time in Patent Office: 972 Days
• Field of Search: 709/102, 709/202, 709/106, 709/223
• US Class Current: 718/102
• CPC Class Codes: G06F 8/456 Parallelism detection
• CPC Class Codes: G06F 9/4843 by program, e.g. task dispatcher, supervisor, operating system

Abstract

A method and apparatus for parallel processing is provided. A parallel execution object organizes and initiates execution of two or more parallel processing threads that act on members in the context of a transaction. The members comprise one or more sets of data for which parallel processing is needed, for example, sets of network device data. The threads are organized by receiving a set of execution components that have a partial order defined by preconditions and resource requirements. A partial order evaluator resolves the partial order into a final order of execution of the components. The parallel execution object, members, transaction, and partial order can be declared in the context of an application program. Optionally, the threads are organized by selecting execution components that are optimized for use with a particular current phase of execution of the application program.

Claims

1. A method of executing a plurality of program components in parallel, comprising the steps of:

defining and storing a plurality of members of a parallel execution;

defining and storing evaluation sequence information that describes a partial order of execution of the plurality of program components;

ordering the plurality of program components into one or more execution threads based on the evaluation sequence information; and

initiating parallel execution of at least two of the execution threads with respect to two different members among the plurality of members.

2. The method recited in claim 1, in which the step of defining and storing a plurality of members of a parallel execution comprises the steps of defining and storing a plurality of data sets in which each of the data sets is associated with a type attribute.

3. The method recited in claim 2, in which the step of ordering includes the step of arranging parallel execution of a subset of the plurality of program components in which all program components within the subset act upon members having the same type attribute.

4. The method recited in claim 3, in which the type attribute is associated with a network device type.

5. The method recited in claim 1, in which the step of initiating parallel execution includes the step of initiating parallel execution within a transaction context.

6. The method recited in claim 5, in which the step of initiating parallel execution includes the steps of:

initiating a transaction;

executing at least two of the execution threads in parallel with respect to two different members among the plurality of members; and

committing and terminating the transaction.

7. The method recited in claim 1, in which the step of defining and storing evaluation sequence information comprises the steps of defining and storing an ordered set of the plurality of program components, in which each of the program components is characterized by a time value that indicates when the program components should be executed.

8. The method recited in claim 7, in which the step of defining and storing evaluation sequence information comprises the steps of defining and storing an ordered set of the plurality of program components, in which a first program component among the plurality of the program components is characterized by a precondition that identifies a second program component to be executed before the first program component.

9. The method recited in claim 1, in which the step of initiating parallel execution comprises the steps of initiating parallel execution of at least two of the execution threads with respect to two different members among the plurality of members and according to a time schedule.

10. The method recited in claim 1, in which the step of ordering and the step of initiating include the steps of:

creating and storing a plurality of container objects, each of the container objects associated with one of the execution threads;

executing a set of the plurality of program components in association with each of the container objects.

11. The method recited in claim 1, further comprising the steps of:

defining and storing a second plurality of program components, in which each of the second plurality of program components is associated with a phase of execution from a plurality of phases of execution;

receiving execution phase information that identifies a current phase of execution from the plurality of phases of execution; and

initiating parallel execution of one of the program components in the second plurality of program components that is associated with one of the plurality of phases of execution that matches the current phase of execution.

12. A computer-readable medium carrying one or more sequences of instructions for executing a plurality of program components in parallel, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

defining and storing a plurality of members of a parallel execution;

defining and storing evaluation sequence information that describes a partial order of execution of the plurality of program components;

ordering the plurality of program components into one or more execution threads based on the evaluation sequence information; and

initiating parallel execution of at least two of the execution threads with respect to two different members among the plurality of members.

13. An apparatus that executes a plurality of computer program components in parallel, comprising:

one or more processors;

one or more stored sequences of processor instructions that carry out a process of executing a plurality of program components in parallel and which, when executed by the one or more processors, cause the one or more processors to carry out the steps of;

defining and storing a plurality of members of a parallel execution;

defining and storing evaluation sequence information that describes a partial order of execution of the plurality of program components;

ordering the plurality of program components into one or more execution threads based on the evaluation sequence information; and

initiating parallel execution of at least two of the execution threads with respect to two different members among the plurality of members.

14. An apparatus as recited in claim 13, in which the sequences of instructions that provide the step of defining and storing a plurality of members of a parallel execution comprise one or more sequences of instructions that provide the steps of defining and storing a plurality of data sets in which each of the data sets is associated with a type attribute.

15. An apparatus as recited in claim 14, in which the instructions for carrying out the step of ordering include instructions for carrying out the step of arranging parallel execution of a subset of the plurality of program components in which all program components within the subset act upon members having the same type attribute.

16. An apparatus as recited in claim 13, in which the instructions for carrying out the step of initiating parallel execution include instructions for carrying out the step of initiating parallel execution within a transaction context.

17. An apparatus as recited in claim 16, in which the instructions for carrying out the step of initiating parallel execution include instructions for carrying out the steps of:

initiating a transaction;

executing at least two of the execution threads in parallel with respect to two different members among the plurality of members; and

committing and terminating the transaction.

18. An apparatus as recited in claim 13, in which the instructions for carrying out the step of defining and storing evaluation sequence information comprise instructions for carrying out the steps of defining and storing an ordered set of the plurality of program components, in which each of the program components is characterized by a time value that indicates when the program components should be executed.

19. An apparatus as recited in claim 18, in which the instructions for carrying out the step of defining and storing evaluation sequence information comprise instructions for carrying out the steps of defining and storing an ordered set of the plurality of program components, in which a first program component among the plurality of the program components is characterized by a precondition that identifies a second program component to be executed before the first program component.

20. An apparatus as recited in claim 13, in which the instructions for carrying out the step of initiating parallel execution comprise instructions for carrying out the steps of initiating parallel execution of at least two of the execution threads with respect to two different members among the plurality of members and according to a time schedule.

21. An apparatus as recited in claim 13, in which instructions for carrying out the step of ordering and the step of initiating include instructions for carrying out the steps of:

creating and storing a plurality of container objects, each of the container objects associated with one of the execution threads;

executing a set of the plurality of program components in association with each of the container objects.

22. An apparatus as recited in claim 13, further comprising instructions for carrying out the steps of:

defining and storing a second plurality of program components, in which each of the second plurality of program components is associated with a phase of execution from a plurality of phases of execution;

receiving execution phase information that identifies a current phase of execution from the plurality of phases of execution; and

initiating parallel execution of one of the program components in the second plurality of program components that is associated with one of the plurality of phases of execution that matches the current phase of execution.

23. An apparatus that executes a plurality of computer program components in parallel, comprising:

means for defining and storing a plurality of members of a parallel execution;

means for defining and storing evaluation sequence information that describes a partial order of execution of the plurality of program components;

means for ordering the plurality of program components into one or more execution threads based on the evaluation sequence information; and

means for initiating parallel execution of at least two of the execution threads with respect to two different members among the plurality of members.

24. An apparatus as recited in claim 23, in which the means for defining and storing a plurality of members of a parallel execution comprises means defining and storing a plurality of data sets in which each of the data sets is associated with a type attribute.

25. An apparatus as recited in claim 24, in which the means for ordering includes means for arranging parallel execution of a subset of the plurality of program components in which all program components within the subset act upon members having the same type attribute.

26. An apparatus as recited in claim 23, in which the means for initiating parallel execution includes means for initiating parallel execution within a transaction context.

27. An apparatus as recited in claim 26, in which the means for initiating parallel execution includes:

means for initiating a transaction;

means for executing at least two of the execution threads in parallel with respect to two different members among the plurality of members; and

means for committing and terminating the transaction.

28. An apparatus as recited in claim 23, in which the means for defining and storing evaluation sequence information comprise means for defining and storing an ordered set of the plurality of program components, in which each of the program components is characterized by a time value that indicates when the program components should be executed.

29. An apparatus as recited in claim 28, in which the means for carrying out the step of defining and storing evaluation sequence information comprise means for carrying out the steps of defining and storing an ordered set of the plurality of program components, in which a first program component among the plurality of the program components is characterized by a precondition that identifies a second program component to be executed before the first program component.

30. An apparatus as recited in claim 23, in which the means for carrying out the step of initiating parallel execution comprises means for initiating parallel execution of at least two of the execution threads with respect to two different members among the plurality of members and according to a time schedule.

31. An apparatus as recited in claim 23, in which the means for ordering and initiating includes:

means for creating and storing a plurality of container objects, each of the container objects associated with one of the execution threads;

means for executing a set of the plurality of program components in association with each of the container objects.

32. An apparatus as recited in claim 23, further comprising:

means for defining and storing a second plurality of program components, in which each of the second plurality of program components is associated with a phase of execution from a plurality of phases of execution;

means for receiving execution phase information that identifies a current phase of execution from the plurality of phases of execution; and

means for initiating parallel execution of one of the program components in the second plurality of program components that is associated with one of the plurality of phases of execution that matches the current phase of execution.