Partitioning of structured programs

• US 20040216096A1
• Filed: 04/28/2003
• Published: 10/28/2004
• Est. Priority Date: 04/28/2003
• Status: Abandoned Application

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Messer, Alan, Greenberg, Ira
• Application Number:
  US10/425,063
• Publication Number:
  US 20040216096A1
• Time in Patent Office: Days
• US Class Current: 717/154
• CPC Class Codes: G06F 8/456 Parallelism detection
• 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

Partitioning of programs that exploits the granularity of structured programs and enables partitioning and re-partitioning of a program at run-time. A run-time executable is partitioned according to the present techniques by building a graph of an execution history of the run-time executable such that the graph includes a set of nodes each corresponding to a software component of the run-time executable and a set of weighted edges that indicate a level of interaction among the software components. A set of intermediate partitionings of the nodes is then determined in response to the weighted edges and one of the intermediate partitionings is selected that meets a partitioning goal.

Claims

1. A method for partitioning a run-time executable, comprising the steps of:

building a graph of an execution history of the run-time executable such that the graph includes a set of nodes each corresponding to a software component of the run-time executable and a set of weighted edges that indicate a level of interaction among the software components;

determining a set of intermediate partitionings of the nodes in response to the weighted edges;

selecting one of the intermediate partitionings that meets a partitioning goal and partitioning the software components accordingly.

2. The method of claim 1, wherein the step of determining a set of intermediate partitionings comprises the step of determining an intermediate partitioning for each of the software components that is re-locatable.

3. The method of claim 2, wherein the step of determining an intermediate partitioning comprises the steps of:

selecting a next node from among the nodes such that the software component corresponding to the next node is re-locatable;

selecting a first node having a highest valued weighted edge from among a subset of the nodes that are neighbors to the next node;

grouping together the next node and the first node.

4. The method of claim 1, further comprising the step of obtaining the execution history while executing the run-time executable.

5. The method of claim 4, wherein the step of obtaining the execution history includes the step of modifying the run-time executable to record interactions among the software components.

6. The method of claim 4, wherein the step of obtaining the execution history includes the step of modifying a runtime system to record interactions among the software components.

7. A software execution system, comprising:

platform for executing a run-time executable;

execution history that provides a record of interactions among a set of components of the run-time executable;

partitioner that partitions the run-time executable into a pair of partitions in response to the execution history by building a graph that includes a set of nodes corresponding to the software components and a set of weighted edges that indicate a level of interaction among the software components and determining a set of intermediate partitionings of the nodes in response to the weighted edges and selecting one of the intermediate partitionings that meets a partitioning goal.

8. The software execution system of claim 7, wherein the run-time executable is structured as a set of software components in which routines and associated data are encapsulated together.

9. The software execution system of claim 7, wherein the run-time executable is executable binary code compiled from C++ source code.

10. The software execution system of claim 7, wherein the run-time executable is Java byte code.

11. The software execution system of claim 7, wherein the execution history is recorded while executing the run-time executable.

12. The software execution system of claim 11, wherein a time window of the execution history is selected such that the record reflects past and immediate resource demands and predict future resource demands of the run-time executable.

13. The software execution system of claim 11, wherein the software components of the run-time executable are provided with hooks that record a set pertinent information for the execution history.

14. The software execution system of claim 11, wherein the platform records the execution history by detecting a call to a software component of the run-time executable and inserting a record of a source and a destination of the call into the execution history.

15. The software execution system of claim 7, wherein the partitioner partitions the run-time executable so as to minimize a level of interaction among the partitions.

16. The software execution system of claim 7, wherein the partitioning goal is based on communication bandwidth.

17. The software execution system of claim 7, wherein the partitioning goal is based on power consumption.

18. A method for run-time partitioning of a run-time executable, comprising the steps of:

executing the run-time executable on an initial computing device;

recording an execution history of interactions among a set of components of the run-time executable as the run-time executable executes;

monitoring one or more factors that influence partitioning and detecting a trigger point;

partitioning the run-time executable into a pair of partitions in response to the execution history by building graph that includes a set of nodes corresponding to the software component and a set of weighted edges that indicate a level of interaction among the software components and determining a set of intermediate partitionings of the nodes in response to the weighted edges and selecting one of the intermediate partitionings in response to the trigger point;

relocating one of the partitions to another computing device.

19. The method of claim 18, wherein the step of detecting a trigger point comprises the step of detecting when resource consumption on the initial computing device exceeds a predetermined threshold.

20. The method of claim 18, wherein the step of detecting a trigger point comprises the step of detecting when memory consumption on the initial computing device exceeds a predetermined threshold.

21. The method of claim 18, wherein the step of detecting a trigger point comprises the step of detecting when power consumption on the initial computing device exceeds a predetermined threshold.

22. A computer-readable storage media that contains a program that when executed by a computer partitions a run-time executable by performing the steps of:

executing the run-time executable on an initial computing device;

recording an execution history of interactions among a set of components of the run-time executable as the run-time executable executes;

monitoring one or more factors that influence partitioning and detecting a trigger point;

partitioning the run-time executable into a pair of partitions in response to the execution history by building graph that includes a set of nodes corresponding to the software component and a set of weighted edges that indicate a level of interaction among the software components and determining a set of intermediate partitionings of the nodes in response to the weighted edges and selecting one of the intermediate partitionings in response to the trigger point;

relocating one of the partitions to another computing device.

23. The computer-readable storage media of claim 22, wherein the step of detecting a trigger point comprises the step of detecting when resource consumption on the initial computing device exceeds a predetermined threshold.

24. The computer-readable storage media of claim 22, wherein the step of detecting a trigger point comprises the step of detecting when memory consumption on the initial computing device exceeds a predetermined threshold.

25. The computer-readable storage media of claim 22, wherein the step of detecting a trigger point comprises the step of detecting when power consumption on the initial computing device exceeds a predetermined threshold.