Method for automated deployment of a software program onto a multi-processor architecture

• US 5,418,953 A
• Filed: 04/12/1993
• Issued: 05/23/1995
• Est. Priority Date: 04/12/1993
• Status: Expired due to Term

• Current Assignee: Lockheed Martin ROLM Mil-Spec Corporation
• Original Assignee: Loral/Rohm Mil-Spec Corporation
• Inventors: Hunt, Peter D., Morgan, Craig R., Elliott, Jon K., Herring, Alan J., Hiller, John A., Tobias, Richard J.
• Primary Examiner(s): Shaw, Gareth D.
• Assistant Examiner(s): Banankhah, Majid A.
• Application Number:
  US08/046,028
• Time in Patent Office: 771 Days
• Field of Search: 364/DIG. 1, 395/650
• US Class Current: 718/102
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451

Abstract

A method is employed for pre-assignment and pre-scheduling of tasks that enables allocation across multiple physical processors arranged in a variety of architectures. The method comprises the steps of: constructing a DFG of tasks to be performed to provide a solution for a problem; determining cost values for each task and the overall problem, such cost values taking into account a target multiprocessor architecture and factors such as elapsed task execution times. The method pre-assigns the tasks to logical processors and assures that inter-dependent tasks are executable by logical processors that are within required communications delay criteria of each other. The assigning action attempts to arrive at a minimal cost value for all tasks comprising the problem. The pre-assigned tasks are then pre-scheduled based upon a performance criteria and are converted to machine code. The machine code is then deployed to physical processors in the target multi-processor architecture. The deploying action maps the logical processors'"'"' pre-assigned programs (comprising assigned tasks) onto physical processors, using data regarding the multi-processor architecture and the current utilization of the physical processors in the architecture, all while assuring that inter-dependent tasks are mapped so as to fulfill interprocessor communication delay criteria.

Claims

1. A method for assigning, scheduling and allocating tasks that comprise a problem, to multiple physical processors in a multi-processor architecture, said method enabling allocation of said tasks to multiple physical processors arranged in any of a plurality of target architectures, said method comprising the computer implemented steps of:

(a) deriving through user-computer interaction, a data flow graph (DFG) of tasks to be performed to solve said problem;

(b) determining execution time cost values for primitive operations comprising each task and said problem;

(c) pre-assigning said tasks to logical processors, a logical processor comprising a data structure, said pre-assigning partitioning said DFG into subgraph execution programs (SEPs) employing said execution time cost values and target multi-processor architecture data and iteratively modifying partitioning of said SEPs to accomplish set cost criteria;

(d) pre-scheduling said pre-assigned tasks based upon a performance criteria that, at least, assures that pre-scheduled tasks are data dependent only upon data from earlier performed tasks; and

(e) deploying code comprising each of said logical processors and their pre-assigned tasks to physical processors arranged in a provided target multi-processor architecture, said deploying using data indicating current utilization of said physical processors arranged in said chosen target architecture to map each logical processor and pre-assigned task onto a physical processor.

2. The method as recited in claim 1 wherein said pre-assigning step (c) includes, for tasks that are interdependent upon each other, determining interprocessor communications time distance constraints for logical processors to which said interdependent tasks are assigned, said pre-assigning further attempting, by iteratively modifying said partitioning of said SEPs, to achieve a minimal cost value for each task and said problem.

3. The method as recited in claim 2, wherein said deploying in step (e) further assures that logical processors with pre-assigned tasks that are interdependent, are mapped onto said physical processors so as to fulfill interprocessor communication time distance constraints determined in step (c).

4. The method as recited in claim 1 wherein said target multi-processor architecture data is used by said pre-assigning step (c) and pre-scheduling step (d) to determine which tasks are to be assigned to said logical processors.

5. The method as recited in claim 4 wherein step (e) determines a current availability of physical processors by maintaining a current utilization record for each physical processor, said current utilization record enabling a determination to be made as to whether a physical processor is available for deployment of a said logical processor and its pre-assigned tasks.

6. The method as recited in claim 5, wherein step (e), in deploying a first logical processor and assigned first task to an available physical processor, additionally, determines whether another physical processor that fulfills an interprocessor communications time distance constraint is available for assignment of a second logical processor and assigned second task, said second logical processor requiring said interprocessor communications time distance constraint and if not available, attempts redeployment of at least one said logical processor to a physical processor that fulfills the interprocessor communications time distance constraint.

7. The method as recited in claim 1 wherein said performance criteria defined in step (d) is that each task should be executed on an as soon as possible (ASAP) basis.

8. The method as recited in claim 1, wherein step (d) further comprises:

(d1) analyzing each pre-schedule of said pre-assigned tasks to determine a quality measure of the pre-schedule, said quality measure at least dependent upon a gap time-based measure, gap time being a time that a logical processor is inactive and waiting for a previous logical processor to finish a task; and

repeating step (c) to arrive at an altered pre-assignment, said altered pre-assignment then subjected to a repeated rescheduling step (d) and analysis to determine if said gap time-based measure has been reduced.