US5418953A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for automated deployment of a software program onto a multi-processor architecture
Assignee: Lockheed Martin Rolm Mil Spec Corp
•
Filing: 1993-04-12
•
Granted: 1995-05-23
•
Expires: 2013-04-12
Abstract
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.
Inventors
- 👤 Peter D. Hunt
- 👤 Jon K. Elliott
- 👤 Richard J. Tobias
- 👤 Alan J. Herring
- 👤 Craig R. Morgan
- 👤 John A. Hiller
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 16:20
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/46; G06F9/50; G06F9/5061; G06F9/5066
Claims Analysis
Total Claims: 9
Claim 1
Independent Claim
209 words
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.
Claim 2
Independent Claim
209 words
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.
Claim 3
Dependent Claim
61 words
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.
Claim 4
Dependent Claim
43 words
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).
Claim 5
Dependent Claim
36 words
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.
Claim 6
Dependent Claim
56 words
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.
Claim 7
Dependent Claim
88 words
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.
Claim 8
Dependent Claim
30 words
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.
Claim 9
Dependent Claim
94 words
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.
References Cited (Backward Citations)
US5021947A
Cited
US5247675A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-05-22 | 1998-11-21 | 1999-05-23 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-05-22 | 2002-11-21 | 2003-05-23 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-05-22 | 2006-11-21 | 2007-05-23 | $7700.00 | Window Closed / Lapsed |