Parallel execution of a complex task partitioned into a plurality of entities

• US 5,748,489 A
• Filed: 05/30/1995
• Issued: 05/05/1998
• Est. Priority Date: 11/30/1994
• Status: Expired due to Fees

• Current Assignee: GlobalFoundries, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Elmendorf, Peter Claude, Gillis, Roland Roberto, Beatty, Harry John, Pramanick, Ira
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): PHAN, THAI Q
• Application Number:
  US08/453,680
• Time in Patent Office: 1,071 Days
• Field of Search: 364/578, 364/488, 364/900, 364/489, 364/DIG. 2, 395/425, 395/275, 395/500, 395/575, 395/375, 395/650
• US Class Current: 709/208
• CPC Class Codes: G06F 30/3312 Timing analysis
• CPC Class Codes: G06F 8/451 Code distribution considering CPU load at run-time G06F9/505; load rebalancing G06F9/5083

Abstract

In order to efficiently execute a complex task within a computer system, the task is partitioned into a plurality of entities. A master process and a slave process are started for each entity. The master processes schedule operations to be performed, while the slave processes perform the operations. One slave process is coupled to one or more other slave processes because of path interconnections between the entities. Communication is established between any coupled slave processes such that one slave process may directly communicate with another slave process without involving the master processes. The master and slave processes execute in parallel on a plurality of processors.

Claims

1. A system for executing complex static timing tasks in a computer system comprising one or more processors, said system comprising:

means for partitioning a complex static timing task into a plurality of entities;

means for starting a master process and a slave process for each of at least two of said plurality of entities, wherein the master processes and the slave processes of the at least two of said plurality of entities together form a hierarchical arrangement of processes in said system, the hierarchical arrangement of processes having at least one of the master processes subservient to another of the master processes therein, wherein a slave process of one of said at least two of said plurality of entities is coupled to a slave process of one other entity of said at least two of said plurality of entities;

means for establishing a direct communication path between said coupled slave processes for communicating between said coupled slave processes independent of their respective master processes, the hierarchical arrangement of processes thereby having at least one pair of coupled slave processes from different master processes in direct communication with each other;

means for executing said master processes and said slave processes on said one or more processors, wherein said master processes schedule operations to be performed by their respective said slave processes for said complex static timing task and said slave processes perform said operations in parallel; and

means for providing a result of said operations performed in parallel to a user of said computer system.

2. The system of claim 1, further comprising means for executing said master processes and said slave processes in parallel.

5. The system of claim 1, further comprising means for creating a shadow master process for each of said master processes and a shadow slave process for each of said slave processes, each shadow master process and each shadow slave process monitoring its respective process.

11. The system of claim 1, wherein said one other entity of said at least two of said plurality of entities is at least a partial decomposition of another of said plurality of entities, wherein the another of said plurality of entities comprises said one of said at least two of said plurality of entities or a different one of said plurality of entities.

12. The system of claim 1, wherein the means for establishing a direct communication path between said coupled slave processes includes:

means for executing the master processes in parallel while establishing the paths for the coupled slave processes.

3. A system for executing complex static timing tasks in a computer system comprising one or more processors, said system comprising:

means for partitioning a complex static timing task into a plurality of entities;

means for starting a master process and a slave process for each of at least two of said plurality of entities, wherein the master processes and the slave processes of the at least two of said plurality of entities together form a hierarchical arrangement of processes in said system, the hierarchical arrangement of processes having at least one of the master processes subservient to another of the master processes therein, wherein a slave process of one of said at least two of said plurality of entities is coupled to one or more other slave processes of said at least two of said plurality of entities;

means for establishing direct communication paths between any coupled slave processes for communicating between said coupled slave processes independent of their respective master processes, the hierarchical arrangement of processes thereby having at least one pair of coupled slave processes from different master processes in direct communication with each other;

means for executing said master processes and said slave processes on said one or more processors, wherein said master processes schedule operations to be performed by their respective said slave processes for said complex static timing task and said slave processes perform said operations in parallel thereby reaching a result;

means for thereafter substituting one of said plurality of entities with a replaceable entity, wherein at least one other entity of said plurality of entities is retained and operations relevant only to the replaceable entity are thereafter performed to thereby reach a new result; and

means for providing the new result to a user of said computer system.

4. The system of claim 3, wherein said replaceable entity has a different structure from said one of said plurality of entities being replaced.

9. The system of claim 3, wherein said one of said at least two of said plurality of entities is at least a partial decomposition of another of said plurality of entities.

10. The system of claim 3, wherein the means for establishing direct communication paths between any coupled slave processes includes:

means for executing the master processes in parallel while establishing the paths for the coupled slave processes.

6. A system for executing complex static timing tasks in a computer system comprising one or more processors, said system comprising:

means for partitioning a complex static timing task into a plurality of entities;

means for starting a master process and a slave process for each of at least two of said plurality of entities, wherein the master processes and the slave processes of the at least two of said plurality of entities together form a hierarchical arrangement of processes in said system, the hierarchical arrangement of processes having at least one of the master processes subservient to another of the master processes therein, wherein a slave process of one of said at least two of said plurality of entities is coupled to one or more other slave processes of said at least two of said plurality of entities;

means for establishing direct communication paths between any coupled slave processes for communicating between said coupled slave processes independent of the respective master processes, the hierarchical arrangement of processes thereby having at least one pair of coupled slave processes from different master processes in direct communication with each other;

means for executing said master processes and said slave processes on said one or more processors, wherein said master processes schedule operations to be performed by their respective said slave processes for said complex static timing task and said slave processes perform said operations in parallel; and

means for providing a result of said operations performed in parallel to a user of said computer system.

7. The system of claim 6, wherein said one of said at least two of said plurality of entities is at least a partial decomposition of another of said plurality of entities.

8. The system of claim 6, wherein the means for establishing direct communication paths between any coupled slave processes includes:

means for executing the master processes in parallel while establishing the paths for the coupled slave processes.