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

• US 5,615,127 A
• Filed: 11/30/1994
• Issued: 03/25/1997
• Est. Priority Date: 11/30/1994
• Status: Expired due to Term

• Current Assignee: GlobalFoundries, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Pramanick, Ira, Beatty, Harry J., Elmendorf, Peter C., Gillis, Roland R.
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): PHAN, THAI Q
• Application Number:
  US08/347,641
• Time in Patent Office: 846 Days
• Field of Search: 364/488, 364/489, 364/490, 364/491, 364/578, 364/200, 364/DIG. 2, 395/500, 395/200.01, 395/200.03, 395/200.05, 395/550
• US Class Current: 716/131
• 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 method for executing complex static timing tasks in an application environment of a computer system, said system comprising one or more processors, said method comprising:

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

starting a master process and a slave process for at least two of said plurality of entities, 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;

establishing a direct communication path between said coupled slave processes for communicating between said coupled slave processes independent of their respective master processes;

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

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

2. The method of claim 1, wherein said master processes and said slave processes are executed in parallel.

3. The method of claim 1, further comprising 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.

4. The method 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.

5. The method of claim 1, wherein the steps of starting and partitioning are included in a step of:

forming the master processes and the slave processes of the at least two of said plurality of entities into a hierarchical arrangement of processes in said computer system, the hierarchical arrangement of processes having at least one of the master processes subservient to another of the master processes therein, the hierarchical arrangement of processes further having at least a pair of coupled slave processes, each slave process of the pair of coupled slave processes being associated with a different respective master process, the pair of coupled slave processes being in direct communication with each other.

6. The method of claim 1, wherein multiple slave processes are coupled to other respective slave processes, and wherein the step of establishing a direct communication path further includes:

executing the respective master processes in parallel while establishing direct communication paths between the coupled slave processes.

7. A method for executing complex static timing tasks in an application environment of a computer system, said system comprising one or more processors, said method comprising:

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

starting a master process and a slave process for at least two of said plurality of entities, 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 said at least two of said plurality of entities;

establishing direct communication paths between any coupled slave processes;

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

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

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

8. The method of claim 7, wherein said replaceable entity has a different structure from said one of said plurality of entities being replaced.

9. The method of claim 7, 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, and 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.

10. The method of claim 7, wherein the steps of starting and partitioning are included in a step of:

forming the master processes and the slave processes of the at least two of said plurality of entities into a hierarchical arrangement of processes in said computer system, the hierarchical arrangement of processes having at least one of the master processes subservient to another of the master processes therein, the hierarchical arrangement of processes further having at least a pair of coupled slave processes, each slave process of the pair of coupled slave processes being associated with a different respective master process, the pair of coupled slave processes being in direct communication with each other.

11. The method of claim 7, wherein the step of establishing direct communication paths further includes:

executing the respective master processes in parallel while establishing the direct communication paths.

12. A method for performing static timing analysis on a logic design comprising a plurality of logic circuits, said method comprising:

partitioning said logic design into a first entity and a second entity, said first entity comprising a first portion of logic circuits and said second entity comprising a second portion of logic circuits;

starting, in an application environment, a first master process and a first slave process for said first entity and a second master process and a second slave process for said second entity;

establishing a communication path between said first slave process and said second slave process, wherein said first slave process and said second slave process directly communicate with one another;

performing timing operations for said first portion of logic circuits using said first slave process and for said second portion of logic circuits using said second slave process, said timing operations indicating a performance of said logic design; and

providing a result of said timing operations to a user of said computer system.

13. The method of claim 12, wherein said performing comprises:

calculating using said first slave process a first output arrival time for a first circuit of said first portion of logic circuits;

calculating using said second slave process a second output arrival time for a second circuit of said second portion of logic circuits, said first slave process and said second slave process operating in parallel;

sending from said first slave process to said second slave process said first output arrival time when said first output arrival time is different from a previously determined first output arrival time; and

recalculating said second output arrival time using as input said first output arrival time sent to said second slave process.

14. The method of claim 13, wherein said first slave process calculates one or more output arrival times for each of a plurality of said first portion of logic circuits, and wherein said sending comprises forwarding to said second slave process only those first output arrival times which are different from previously determined first output arrival times.

15. The method of claim 13, further comprising:

said first slave process sending a first completion indication to said first master process after calculating said first output arrival time; and

said second slave process sending a second completion indication to said second master process after calculating said second output arrival time.

16. The method of claim 13, wherein said partitioning further comprises partitioning said logic design into a third entity, said third entity comprising a third portion of logic circuits, and wherein said starting further comprises starting a third master process and a third slave process, and wherein said communication path is established between the first slave process and the second slave process or between the first slave process and the third slave process or between the second slave process and the third slave process, and further comprising calculating using said third slave process a third output arrival time, said first slave process, said second slave process and said third slave process operating in parallel.

17. The method of claim 16, further comprising:

forwarding to said third slave process said first output arrival time when there is a difference between said first output arrival time and said previously determined first output arrival timer and there is a communication path between said first slave process and said third slave process; and

forwarding to said third slave process said second output arrival time when there is a difference between said second output arrival time and a previously determined second output arrival time, and there is a communication path between said second slave process and said third slave process.

18. The method of claim 17, further comprising recalculating said third output arrival time when said first output arrival time or second output arrival time is forwarded.

19. The method of claim 16, further comprising forwarding to said third slave process a recalculated second output arrival time when there is a difference between said second output arrival time and said recalculated second arrival time and there is a communication path between said second slave process and said third slave process.

20. The method of claim 12, further comprising determining whether said logic design is performing according to a user specification.

21. The method of claim 20, further comprising modifying said logic design by replacing said first entity or said second entity with another entity when said logic design is not performing according to said user specification.

22. The method of claim 12, further comprising modifying said logic design by substituting said first entity or said second entity with a replaceable entity.

23. The method of claim 22, further comprising repeating said timing operations on only that portion of said logic design coupled to said replaceable entity.

24. The method of claim 23, wherein said replaceable entity is of a different structure from said first entity or said second entity being replaced.

25. The method of claim 12, wherein said partitioning includes partitioning said first entity into a third entity, and wherein said starting includes starting a third master process and a third slave process for said third entity, and wherein a second communication path is established between the first slave process and the third slave process, wherein said first slave process and said third slave process directly communicate with one another via said second communication path.

26. The method of claim 12, wherein the steps of starting and establishing are included in a step of:

forming the first and second master and slave processes into a hierarchical arrangement of processes, the hierarchical arrangement of processes having the second master process subservient to the first master process therein.

27. The method of claim 12, wherein the step of establishing a direct communication path further includes:

executing the first and second master processes in parallel while establishing the direct communication path.