Behavior invariant optimization of maximum execution times for model simulation

• US 8,819,618 B2
• Filed: 09/26/2012
• Issued: 08/26/2014
• Est. Priority Date: 09/26/2012
• Status: Active Grant

• Current Assignee: The MathWorks, Inc.
• Original Assignee: The MathWorks, Inc.
• Inventors: MacLay, David, Urbas, Matej
• Primary Examiner(s): Dao, Thuy
• Assistant Examiner(s): BERMAN, STEPHEN DAVID
• Application Number:
  US13/627,286
• Publication Number:
  US 20140089889A1
• Time in Patent Office: 699 Days
• Field of Search: None
• US Class Current: 717/104
• CPC Class Codes: G06F 8/35 model driven
• CPC Class Codes: G06F 8/70 Software maintenance or management
• CPC Class Codes: G06F 9/4887 involving deadlines, e.g. rate based, periodic

Abstract

A device receives a model that includes model elements scheduled to execute in time slots on a hardware device. The device identifies time slots, of the time slots, that are unoccupied or underutilized by the model elements, and identifies a set of model elements that can be moved to the unoccupied time slots without affecting a behavior of the model. The device calculates a combined execution time of the model elements, determines whether the combined execution time of the model elements is less than or equal to a duration of a first time slot of the time slots, and schedules the model elements for execution in the first time slot when the combined execution time of the model elements is less than or equal to the duration of the first time slot.

Claims

1. A method, comprising:

receiving a model,

the model including model elements scheduled to execute in time slots on a hardware device,

the receiving the model being performed by a device via a technical computing environment (TCE);

identifying one or more time slots, of the time slots, that are unoccupied or underutilized by the model elements,

the identifying the one or more time slots being performed by the device;

identifying a set of one or more model elements that, when moved to the one or more time slots, preserve a behavior of the model,

the identifying the set of one or more model elements being performed by the device;

calculating a combined execution time of the model elements,

the calculating the combined execution time being performed by the device;

determining whether the combined execution time of the model elements is less than or equal to a duration of a first time slot of the time slots,

the determining whether the combined execution time of the model elements is less than or equal to the duration of the first time slot being performed by the device;

scheduling the model elements for execution in the first time slot when the combined execution time of the model elements is less than or equal to the duration of the first time slot,

the scheduling the model elements being performed by the device;

identifying a portion of model elements, from the set of one or more model elements, that fit into a second time slot, of the time slots, when the combined execution time of the model elements is greater than the duration of the first time slot,

a remaining portion of model elements, from the set of one or more model elements, fitting in the first time slot,

the identifying the portion of model elements being performed by the device;

scheduling the remaining portion of model elements for execution in the first time slot,

the scheduling the remaining portion of model elements being performed by the device; and

scheduling the portion of model elements for execution in the second time slot,

the scheduling the portion of model elements being performed by the device.

2. The method of claim 1, further comprising:

executing model elements in the first time slot when the combined execution time of the model element is less than or equal to the duration of the first time slot, the executing the model elements being performed by hardware device or the device.

3. The method of claim 1, where identifying the portion of model elements further comprises:

calculating a combined execution time of the portion of model elements;

determining whether the combined execution time of the portion of model elements is less than or equal to a duration of the second time slot; and

modifying the portion of model elements when the combined execution time of the portion of model elements is greater than the duration of the second time slot.

4. The method of claim 1, where the first time slot and the second time slot are provided in a hyperperiod, the hyperperiod defining a minimum duration within the model elements are executed at least once.

5. The method of claim 1, where the behavior of the model is an input/output behavior of the model.

6. The method of claim 1, where the behavior of the model is an order of execution of at least two model elements.

7. The method of claim 1, where the hardware device includes one of:

one or more single core processors, or

one or more multi-core processors.

8. The method of claim 1, further comprising:

adjusting the execution of the model elements in the first time slot, when the combined execution time of the model elements is less than or equal to the duration of the first time slot, based on at least one of;

a criterion specifying that the first time slot is utilized less than a first percentage,

a criterion specifying that each of the time slots is utilized less than a second percentage,

a criterion specifying that the hardware device is utilized less than a third percentage, or

a criterion specifying that utilization of a number of cores of the hardware device are maximized.

9. The method of claim 1, further comprising:

automatically generating code from the model.

10. The method of claim 1, further comprising:

automatically determining execution times of the model elements; and

calculating the combined execution time of the model elements based on the determined execution times.

11. The method of claim 1, where the model includes one of:

a single tasking model, or

a multitasking model.

12. A device, comprising:

a processor to;

receive a model,

the model including model elements scheduled to execute in time slots on a hardware device,

the model being received via a technical computing environment (TCE),

identify one or more time slots, of the time slots, that are unoccupied or underutilized by the model elements,

identify a set of one or more model elements that can be moved to the one or more time slots without affecting a behavior of the model,

calculate a combined execution time of the model elements,

determine whether the combined execution time of the model elements is less than or equal to a duration of a first time slot of the time slots,

schedule the model elements for execution in the first time slot when the combined execution time of the model elements is less than or equal to the duration of the first time slot,

identify a portion of model elements, from the set of one or more model elements, that fit into a second time slot, of the time slots, when the combined execution time of the model elements is greater than the duration of the first time slot,

a remaining portion of model elements, of the set of one or more model elements, fitting in the first time slot,

schedule the remaining portion of model elements for execution in the first time slot, and

schedule the portion of model elements for execution in the second time slot.

13. The device of claim 12, where, when identifying the portion of model elements, the processor is further to:

calculate a combined execution time of the portion of model elements, and

modify the portion of model elements when the combined execution time of the portion model elements is greater than a duration of the second time slot.

14. The device of claim 12, where, when identifying the portion of model elements, the processor is further to:

identify the portion of the model elements when the combined execution time of the portion of model elements is less than or equal to a duration of the second time slot,

calculate a combined execution time of the remaining portion of model elements, and

modify the portion of model elements when the combined execution time of the remaining portion of model elements is greater than the duration of the first time slot.

15. The device of claim 14, where, when identifying the portion of the model elements, the processor is further to:

identify the remaining portion of model elements when the combined execution time of the remaining portion of model elements is less than or equal to the duration of the first time slot.

16. The device of claim 12, where the first time slot and the second time slot are provided in a hyperperiod, the hyperperiod defining a minimum duration within which the model elements are executed at least once.

17. The device of claim 12, where the behavior of the model is an input/output behavior of the model or an order of execution of at least two model elements.

18. The device of claim 12, where the hardware device includes one of:

one or more single core processors, or

one or more multi-core processors.

19. One or more non-transitory computer-readable media storing instructions, the instructions comprising:

one or more instructions that, when executed by a processor of a device, cause the processor to;

receive a model,

the model including model elements scheduled to execute in time slots on a hardware device,

the model being received via a technical computing environment (TCE),

identify one or more time slots, of the time slots, that are unoccupied or underutilized by the model elements,

identify a set of one or more model elements that can be moved to the one or more time slots without affecting a behavior of the model,

calculate a combined execution time of the model elements,

determine whether the combined execution time of the model elements is less than or equal to a duration of a first time slot of the time slots,

schedule the model elements for execution in the first time slot when the combined execution time of the model elements is less than or equal to the duration of the first time slot,

identify a portion of model elements, from the set of one or more model elements, that fit into a second time slot, of the time slots, when the combined execution time of the model elements is greater than the duration of the first time slot,

a remaining portion of model elements, of the set of one or more model elements, fitting in the first time slot,

schedule the remaining portion of model elements for execution in the first time slot, and

schedule the portion of model elements for execution in the second time slot.

20. The one or more non-transitory media of claim 19, further comprising:

one or more instructions that, when executed by the processor, cause the processor to;

modify the portion of model elements when a combined execution time of the portion of model elements is greater than the duration of the first time slot.

21. The one or more non-transitory media of claim 19, further comprising:

one or more instructions that, when executed by the processor, cause the processor to;

modify the portion of model elements when a combined execution time of the remaining portion of model elements is greater than a duration of the second time slot.

22. The one or more non-transitory media of claim 19, where the first time slot and the second time slot are provided in a hyperperiod,

the hyperperiod defining a minimum duration within which the model elements are executed at least once.

23. The one or more non-transitory media of claim 19, where the behavior of the model is an input/output behavior of the model or an order of execution of at least two model elements.

24. The one or more non-transitory media of claim 19, where the hardware device includes one of:

one or more single core processors, or

one or more multi-core processors.