Optimizing execution of single-threaded programs on a multiprocessor managed by compilation

• US 8,312,455 B2
• Filed: 12/19/2007
• Issued: 11/13/2012
• Est. Priority Date: 12/19/2007
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Bell, Robert H. Jr., Capps, Louis Bennie Jr., Paolini, Michael A., Shapiro, Michael Jay
• Primary Examiner(s): Puente, Emerson
• Assistant Examiner(s): KIM, SISLEY NAHYUN
• Application Number:
  US11/960,021
• Publication Number:
  US 20090164755A1
• Time in Patent Office: 1,791 Days
• Field of Search: None
• US Class Current: 718/100
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming
• CPC Class Codes: G06F 9/4843 by program, e.g. task dispatcher, supervisor, operating system

Abstract

A method for optimizing execution of a single threaded program on a multi-core processor. The method includes dividing the single threaded program into a plurality of discretely executable components while compiling the single threaded program; identifying at least some of the plurality of discretely executable components for execution by an idle core within the multi-core processor; and enabling execution of the at least one of the plurality of discretely executable components on the idle core.

Claims

1. A method for optimizing execution of a single threaded program on a multi-core processor comprising:

dividing the single threaded program into a plurality of discretely executable components while compiling the single threaded program;

identifying at least some of the plurality of discretely executable components for execution by an idle core within the multi-core processor; and

enabling execution of the at least one of the plurality of discretely executable components on the idle core;

generating a graph of relationships between the plurality of discretely executable components, the graph comprising a main component and a plurality of discretely executable sub-components;

assigning the main component to execute on a first core of the multi-core processor; and

,

assigning each of the plurality of discretely executable sub-components to execute on at least one idle core of the multi-core processor; and

,

dynamically recording addresses accessed by the main component and the plurality of discretely executable sub-components as well as changes of values to the addresses in the order in which the changes occur on a list; and

wherein the graph groups a plurality of dependencies together within a single sub-thread so as to make execution of the sub-thread more favorable to speculative execution threads,

wherein the addresses are memory addresses included in the list of addresses that were read from or written to by the main component and the plurality of discretely executable sub-components.

2. The method of claim 1, wherein:

the dividing further comprises embedding hints into a compiled version of the single threaded program, the hints facilitating execution of the single threaded program by the multi-core processor, the hints being backwards compatible so as to be ignored by single core processors.

3. The method of claim 2, wherein:

the hints direct certain discretely executable components to be executed by certain cores of the multi-core processor.

4. The method of claim 1, further comprising:

optimizing the graph for certain types of multi-core processors.

5. An apparatus for optimizing execution of a single threaded program on a multi-core processor comprising:

means for dividing the single threaded program into a plurality of discretely executable components while compiling the single threaded program;

means for identifying at least some of the plurality of discretely executable components for execution by an idle core within the multi-core processor; and

means for enabling execution of the at least one of the plurality of discretely executable components on the idle core;

means for generating a graph of relationships between the plurality of discretely executable components, the graph comprising a main component and a plurality of discretely executable sub-components;

means for assigning the main component to execute on a first core of the multi-core processor; and

,

means for assigning each of the plurality of discretely executable sub-components to execute on at least one idle core of the multi-core processor; and

,

means for dynamically recording addresses accessed by the main component and the plurality of discretely executable sub-components as well as changes of values to the addresses in the order in which the changes occur on a list; and

wherein

the graph groups a plurality of dependencies together within a single sub-thread so as to make execution of the sub-thread more favorable to speculative execution threads,

wherein the addresses are memory addresses included in the list of addresses that were read from or written to by the main component and the plurality of discretely executable sub-components.

6. The apparatus of claim 5, wherein:

the means for dividing further comprises means for embedding hints into a compiled version of the single threaded program, the hints facilitating execution of the single threaded program by the multi-core processor, the hints being backwards compatible so as to be ignored by single core processors.

7. The apparatus of claim 5, wherein:

the hints direct certain discretely executable components to be executed by certain cores of the multi-core processor.

8. The apparatus of claim 5, further comprising:

means for optimizing the graph for certain types of multi-core processors.

9. A computer program product for determining policy follow-up action, the computer program product comprising:

a non-transitory computer usable medium having computer usable program code embodied therewith, the computer usable program code comprising instructions

executable by a processor for;

dividing the single threaded program into a plurality of discretely executable components while compiling the single threaded program;

identifying at least some of the plurality of discretely executable components for execution by an idle core within the multi-core processor; and

enabling execution of the at least one of the plurality of discretely executable components on the idle core;

generating a graph of relationships between the plurality of discretely executable components, the graph comprising a main component and a plurality of discretely executable sub-components;

assigning the main component to execute on a first core of the multi-core processor; and

,

assigning each of the plurality of discretely executable sub-components to execute on at least one idle core of the multi-core processor; and

,

dynamically recording addresses accessed by the main component and the plurality of discretely executable sub-components as well as changes of values to the addresses in the order in which the changes occur on a list; and

wherein the graph groups a plurality of dependencies together within a single sub-thread so as to make execution of the sub-thread more favorable to speculative execution threads,

wherein the addresses are memory addresses included in the list of addresses that were read from or written to by the main component and the plurality of discretely executable sub-components.

10. The non-transitory computer program product of claim 9, wherein the instructions for dividing further comprise instructions for:

embedding hints into a compiled version of the single threaded program, the hints facilitating execution of the single threaded program by the multi-core processor, the hints being backwards compatible so as to be ignored by single core processors.

11. The non-transitory computer program product of claim 9, wherein:

the hints direct certain discretely executable components to be executed by certain cores of the multi-core processor.

12. The non-transitory computer program product of claim 9, wherein the instructions further comprise instructions for:

optimizing the graph for certain types of multi-core processors.