Methods and systems for program optimization utilizing intelligent space exploration

Embodiments for program optimization are provided. A program is compiled with respect to a performance result utilizing a set of parameters. Information associated with the compiling of the program is collected. The collected information is external to the performance result. The set of parameters is changed based on the collected information.

BACKGROUND OF THE INVENTION

Field of the Invention

The present invention relates in general to computing systems, and more particularly, to various embodiments for program optimization utilizing intelligent space exploration.

Description of the Related Art

Program (or software) optimization is the process of modifying (or creating) a program (or software system) to make it more efficient or use fewer resources. For example, a computer program may be optimized so that it executes more rapidly, is capable of operating with less memory storage or other resources, or uses less power. Generally, a program can not be optimized in absolute terms but only with respect to particular performance characteristics (or results or goals), which may be in conflict with other performance characteristics. As a result, optimized systems are typically only optimal with respect to one characteristic and/or with respect to the utilization thereof for particular applications or users.

In many instances, optimization is performed utilizing an optimizing compiler, which may attempt to construct the program in such a way to, for example, minimize execution time, attain a memory requirement, limit power consumption, etc. In order to perform this task, appropriate parameters must be utilized during the compilation and/or execution process, such as transformation parameters, transformation sequence, thread affinity/scheduling for parallel code, etc. In order to identify the optimal parameters, a space exploration process may be utilized which includes a “compile, execute, result” analysis in which the desired performance characteristic is monitored (or observed), and then utilized to change the parameters (e.g., which are then applied to the compilation and/or execution process). This process may consume considerable resources (e.g., with respect to time and/or costs).

SUMMARY OF THE INVENTION

Various embodiments for program optimization, by a processor, are provided. A program is compiled with respect to a performance result utilizing a set of parameters. Information associated with the compiling (and/or execution) of the program is collected. The collected information is external to the performance result. The set of parameters is changed based on the collected information (e.g., and then applied to the compilation and/or execution process).

In addition to the foregoing exemplary embodiment, various other system and computer program product embodiments are provided and supply related advantages. The foregoing Summary has been provided to introduce a selection of concepts in a simplified form that are further described below in the Detailed Description. This Summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used as an aid in determining the scope of the claimed subject matter. The claimed subject matter is not limited to implementations that solve any or all disadvantages noted in the background.

DETAILED DESCRIPTION OF THE DRAWINGS

As discussed above, program (or software) optimization is the process of modifying (or creating) a program (or software system) to make it more efficient or use fewer resources. For example, a computer program may be optimized so that it executes more rapidly, is capable of operating with less memory storage or other resources, or uses less power. Generally, a program can not be optimized in absolute terms but only with respect to particular performance characteristics (or results or goals), which may be in conflict with other performance characteristics.

As a result, optimized systems are typically only optimal with respect to one characteristic and/or with respect to the utilization thereof for particular applications or users. In many instances, optimization is performed utilizing an optimizing compiler, which may attempt to construct the program in such a way to, for example, minimize execution time, attain a memory requirement, limit power consumption, etc.

In order to perform this task, appropriate parameters must be utilized during the compilation and/or execution process, such as transformation parameters (e.g., tile size, loop unrolling factor, loop transformations, etc.), transformation sequence, thread affinity/scheduling for parallel code, etc. The different number of possible parameters is often so large that a “brute force” search (or exploration) is often considered to be impractical, and generally, no precise analytical models are available. Approaches utilized may include heuristic methods and space exploration techniques.

More specifically, a space exploration process may be utilized which includes a “compile, execute, result” analysis in which the desired performance characteristic is monitored (or observed) and then utilized to change the parameters (e.g., which are then applied to the compilation and/or execution process). This process may be referred to as iterative compilation, adaptive compilation, or autotuning. Search methods utilized during such a process may include or utilize, for example, “greedy” algorithms/methods, genetic algorithms, Bayesian optimization, Monte Carlo searches, “hill climbing,” annealing techniques, etc. Such processes may consume considerable resources (e.g., with respect to time and/or costs).

To address these needs and/or the shortcomings in the prior art, in some embodiments described herein, methods and/or systems are disclosed that, for example, provide improved space exploration for program optimization (and/or improved program/software optimization) utilizing information external to (or other than, in addition to, etc.) the performance goal (or result, characteristic, output, etc.) of the optimization process.

More specifically, in some embodiments, additional information and/or information other than the performance result is utilized in the optimization process (e.g., utilized in the search/exploration, identifying optimization parameters, changing optimization parameters, etc.). The information utilized may be collected (or retrieved, monitored, observed, etc.) from the compiler and/or runtime (and/or performance counter and/or execution process). Examples of information that may be utilized from the compiler include (and/or may be associated with), but are not limited to, instruction types and distribution, instruction categories, instruction count, program size, loop nests, variable reference features (e.g., read/write and reuse factor and distance), code layout, instruction schedule, and/or parallelism. Examples of information that may be utilized from runtime (and/or execution) include (and/or may be associated with), but are not limited to, execution stalls, cache behavior (e.g., cache misses), function unit occupancy, communication traffic, instruction dispatch, speculation failure, instructions issued/completed, and/or I/O throughput.

In some embodiments, two models are (or a two-part model is) generated and utilized (e.g., to explore the space). A first model may relate (or associate) the (previous, original, etc.) optimization parameters (or program features) to the additional information (or observation), and a second model may relate (or associate) the additional information to the performance result. As a result, the structure of the search space may be improved (e.g., “smoothed”), providing better guidance to the search and/or increasing the ease and/or speed of finding an optimal solution (i.e., optimization parameters). Additionally, the applicability of transfer learning may be increased (e.g., insight gained during one optimization may be utilized for other optimizations/programs).

In some embodiments, the additional information to be utilized (or monitored, etc.) is selected as a metric that is relatively sensitive to changes made in the parameters (or optimizations) and/or has a relatively high impact on the target value (or performance goal). The selection of the information to be utilized may be performed utilizing, for example, domain expertise (e.g., based on the knowledge of users, programmers, etc.) and/or a data driven method, such as correlation analysis or principal component analysis (PCA) (or another cognitive analysis or machine learning technique). For example, performance counter metric may be selected for memory bound and computation bound instances, while tiling usually affects memory and unrolling affects computation. As another example, cache misses may be utilized (i.e., depending on what level of cache miss has significant implications for particular applications). In some embodiments, the information is selected such that a function that relates the information to the optimization parameters (e.g., Z=g(X), where Z corresponds to the additional information and X corresponds to the optimization parameters) may be approximately decomposed into smaller functions (e.g., Zi=gi(Xgi), where Xgiis a subset of X).

As such, in some embodiments, the methods and/or systems described herein may utilize a “cognitive analysis,” “cognitive system,” “machine learning,” “cognitive modeling,” “predictive analytics,” and/or “data analytics,” as is commonly understood by one skilled in the art. Generally, these processes may include, for example, receiving and/or retrieving multiple sets of inputs, and the associated outputs, of one or more systems and processing the data (e.g., using a computing system and/or processor) to generate or extract models, rules, etc. that correspond to, govern, and/or estimate the operation of the system(s), or with respect to the embodiments described herein, program optimization, as described herein. Utilizing the models, the performance (or operation) of the system (e.g., utilizing/based on new inputs) may be predicted and/or the performance of the system may be optimized by investigating how changes in the input(s) effect the output(s). Feedback received from (or provided by) users and/or administrators may also be utilized, which may allow for the performance of the system to further improve with continued use.

In particular, in some embodiments, a method for program optimization, by a processor, is provided. A program is compiled with respect to a performance result utilizing a set of parameters. Information associated with the compiling (e.g., the compilation and/or execution) of the program is collected. The collected information is external to the performance result. The set of parameters is changed based on the collected information.

The collected information may include at least one of compiler information and runtime (and/or execution) information. If the collected information includes compiler information, the compiler information may be associated with at least one of program size, category of instruction, and instruction count. If the collected information includes runtime information, the runtime information may be associated with at least one of cache misses and I/O throughput.

The changing of the set of parameters may be based on the collected information and the performance result. A first model relating the set of parameters to the collected information may be generated. A second model relating the performance result to the collected information may be generated. A space exploration may be performed in the collected information domain utilizing the first model and the second model. The changing of the set of parameters may be based on the space exploration. The program may be compiled utilizing the changed set of parameters (e.g., which are applied to the compilation and/or execution process).

Characteristics are as follows:

Service Models are as follows:

Deployment Models are as follows:

In the context of the present invention, and as one of skill in the art will appreciate, various components depicted inFIG. 1may be located in, for example, personal computer systems, server computer systems, thin clients, thick clients, hand-held or laptop devices, multiprocessor systems, microprocessor-based systems, set top boxes, programmable consumer electronics, network PCs, mobile electronic devices such as mobile (or cellular and/or smart) phones, personal data assistants (PDAs), tablets, wearable technology devices, laptops, handheld game consoles, portable media players, etc., as well as computing systems in vehicles, such as automobiles, aircraft, watercrafts, etc. However, in some embodiments, some of the components depicted inFIG. 1may be located in a computing device in, for example, a satellite, such as a Global Position System (GPS) satellite. For example, some of the processing and data storage capabilities associated with mechanisms of the illustrated embodiments may take place locally via local processing components, while the same components are connected via a network to remotely located, distributed computing data processing and storage components to accomplish various purposes of the present invention. Again, as will be appreciated by one of ordinary skill in the art, the present illustration is intended to convey only a subset of what may be an entire connected network of distributed computing components that accomplish various inventive aspects collectively.

Referring now toFIG. 2, illustrative cloud computing environment50is depicted. As shown, cloud computing environment50comprises one or more cloud computing nodes10with which local computing devices used by cloud consumers, such as, for example, cellular (or mobile) telephone or PDA54A, desktop computer54B, laptop computer54C, and vehicular computing system (e.g., integrated within automobiles, aircraft, watercraft, etc.)54N may communicate.

Still referring toFIG. 2, nodes10may communicate with one another. They may be grouped (not shown) physically or virtually, in one or more networks, such as Private, Community, Public, or Hybrid clouds as described hereinabove, or a combination thereof. This allows cloud computing environment50to offer infrastructure, platforms and/or software as services for which a cloud consumer does not need to maintain resources on a local computing device. It is understood that the types of computing devices54A-N shown inFIG. 2are intended to be illustrative only and that computing nodes10and cloud computing environment50can communicate with any type of computerized device over any type of network and/or network addressable connection (e.g., using a web browser).

Device layer55as shown includes sensor52, actuator53, “learning” thermostat56with integrated processing, sensor, and networking electronics, camera57, controllable household outlet/receptacle58, and controllable electrical switch59as shown. Other possible devices may include, but are not limited to, various additional sensor devices, networking devices, electronics devices (such as a remote control device), additional actuator devices, so called “smart” appliances such as a refrigerator, washer/dryer, or air conditioning unit, and a wide variety of other possible interconnected devices/objects.

As previously mentioned, in some embodiments, methods and/or systems are provided for improved program optimization (and/or improve space exploration for program optimization). In some embodiments, rather than (only) monitoring and/or utilizing the performance goal (or result) of the optimization process to change the optimization parameters, information external to (or other than, in addition to, etc.) the performance goal is collected (and/or monitored, tracked, etc.) and utilized in the optimization process.

More specifically, in some embodiments, additional information and/or information other than the performance result is utilized in the optimization process (e.g., utilized in searching/exploring the space, identifying optimization parameters, changing optimization parameters, etc.). The information utilized may be collected (or retrieved, monitored, observed, etc.) from the compiler or runtime (and/or performance counter and/or execution). In some embodiments, two models are (or a two part model is) generated and utilized. A first model may relate the (previous, original, etc.) optimization parameters (or program feature) to the additional information (or observation), and a second model may relate the additional information to the performance result. As a result, the structure of the search space may be improved (e.g., “smoothed”), providing better guidance to the search and/or increasing the ease and/or speed of finding an optimal solution (i.e., optimization parameters). Additionally, the applicability of transfer learning may be increased (e.g., insight gained during one optimization may be utilized for other optimizations/programs).

FIG. 4illustrates a system (and/or method)400for optimizing a program (or software system) according to an embodiment of the present invention. It should be understood that the system400shown inFIG. 4may repeat the process described below multiple times as the system “searches” for optimal parameters (or transformation, etc.) to compile the program with respect to achieving a selected performance goal (or output), such as execution time. For the sake of simplicity, it may be assumed that the method400begins at block402with a particular (e.g., initial) set of parameters (Xi) being selected.

At block404, the program is compiled and executed, as will be appreciated by one skilled in the art. As shown, a result of the compilation/execution of the program may include a target output406(yi) (or performance result/goal/characteristic, such as execution time) being monitored or detected. In contrast with convention methods in which the target output406is solely utilized to make changes to the parameters (e.g., via a model that relates the parameters to the target output), in some embodiments described herein, an additional observation is made and/or additional information it utilized.

More specifically, at block408information (Zi) (i.e., additional information, external to the target output406) is collected (or monitored). The information may be collected (or retrieved, monitored, observed, etc.) from the compiler and/or runtime (or performance counter or execution). Examples of information that may be utilized from the compiler include, but are not limited to, (and/or may be associated with) instruction types and distribution, instruction categories, instruction count, program size, loop nests, variable reference features (e.g., read/write and reuse factor and distance), code layout, instruction schedule, and/or parallelism. Examples of information that may be utilized from runtime include, but are not limited to, (and/or may be associated with) execution stalls, cache behavior (e.g., cache misses), function unit occupancy, communication traffic, instruction dispatch, speculation failure, instructions issued/completed, and/or I/O throughput.

In the example shown, the information collected at block408and the target output406are sent to (or retrieved by) an analysis module410. The analysis module410may utilize both the collected information and the target output to, for example, conduct a space exploration in the domain of the collected information to select the best point for the collected information and/or identify the best configuration/optimization method (or parameters) to achieve the desired target output406.

More specifically, in some embodiments, the analysis module410generates two models (or a two-part model). In the example shown, the analysis module410includes (or generates) a first model412and a second model414. The first model412relates the (previous, original, etc.) optimization parameters (or program feature) (e.g., X) to the additional information (or observation) (Z). The second model414relates the additional information (Z) to the target output406(or performance result) (y). The utilization of the two functions412and414may allow for the structure of the search space to be improved (e.g., “smoothed”), providing better guidance to the search and/or increasing the ease and/or speed of finding an optimal solution (i.e., optimization parameters). Based on the output of the analysis module410, the parameters utilized for compiling and/or executing the program (e.g., at block402) may be changed (or re-selected). The process may then be repeated multiple times (e.g., until the desired target output406is achieved).

In some embodiments, information collected at block408is selected as, for example, an information type that is relatively sensitive to changes made in the parameters (or optimizations) and/or has a relatively high impact on the target value (or performance goal). The selection of the (additional) information may be performed utilizing, for example, domain expertise (e.g., based on the knowledge of users, programmers, etc.) and/or a data driven method, such as correlation analysis or principal component analysis (PCA) (or another cognitive analysis or machine learning technique).

For example, performance counter metric may be selected for memory bound and computation bound instances, while tiling usually affects memory and unrolling affects computation. As another example, cache misses may be utilized (i.e., depending on what level of cache miss has significant implications for particular applications). In some embodiments, the information is selected such that a function that relates the information to the optimization parameters (e.g., Z=g(X), where Z corresponds to the additional information and X corresponds to the optimization parameters) may be approximately decomposed into smaller functions (e.g., Zi=gi(Xgi), where Xgiis a subset of X).

As such, in some embodiments, methods and/or systems for intelligent space exploration for program optimization utilizing, for example, additional compiler and/or runtime information are provided. Compiler and/or runtime information may be collected. An analysis may be conducted to select appropriate intermediate runtime (and/or compiler) data (i.e., the additional information). A first functional model relating program/compiler configuration to the intermediate data may be constructed. A second functional model relating a target performance goal to the intermediate data may be constructed. A space exploration in the intermediate data domain may be conducted to select best intermediate data point (e.g., runtime target point) using the second model. A configuration/optimization method (and/or parameters) to achieve the performance goal may be identified or selected using the first model.

FIGS. 5, 6, and 7are visual representations of search spaces generated utilizing the methods and systems described herein. In particular,FIG. 5illustrates a visual representation of a search space500generated utilizing a function (g1) that relates particular optimization parameters (X) (e.g., filter size and block size) to instruction count (i.e., a particular additional observation, as described above) (Z). In other words, the function may be expressed as Z=g1(X).FIG. 6illustrates a visual representation of a search space600generated utilizing a function (g2) that relates particular optimization parameters (X) (e.g., filter size and block size) to Level 2 (L2) cache misses (i.e., a particular additional observation, as described above) (Z). In other words, the function may be expressed as Z=g2(X).FIG. 7illustrates a visual representation of a search space700generated utilizing a function (h) that relates the instruction count and L2 cache misses ofFIGS. 5 and 6to a particular target output (or performance goal), in particular, cycles and/or execution time (i.e., y=h(instruction count, L2 cache misses). As will be appreciated by one skilled the art, the structures of the search spaces inFIGS. 5, 6, and 7are relatively “smooth” and/or “regular” (i.e., compared to search spaces generated utilizing convention methods), and as such, may provide better guidance to the search and/or increasing the ease and/or speed of finding an optimal solution (i.e., optimization parameters).

As mentioned above, the additional observation of, for example, compile/runtime information and the mapping to and from may enhance the structure in the exploring space and facilitate searching. Additionally, the exploration may be assisted utilizing domain knowledge from users or programmers (e.g., insight may be gained through the performance counter). Various methods may be utilized for generating the different functions used, which may be guided by the influence the additional information has on the functions. With an appropriate selection made for the additional information, the function(s) may have a reduced dimension and may further facilitate exploration. Further, the applicability of transfer learning may be increased (e.g., insight gained during one optimization may be utilized for other optimizations/programs).

Turning toFIG. 8, a flowchart diagram of an exemplary method800for program (or software) optimization is provided. The methods800begins (step802) with, for example, a set (e.g., an initial set) of optimization parameters (and/or transformations) for compiling and/or executing a program being selected. The initial parameters may be selected based on a desired performance result (or goal) and/or target output.

The program is compiled (and/or executed) with respect to the performance result utilizing the set (or initial set) of parameters (step804). The performance result may include, for example, at least one of execution time, attain a memory requirement, limit power consumption, etc.

Information associated with the compiling (i.e., associated with the compilation and/or execution) of the program is collected (or monitored, observed, etc.) (step806). The collected information may be external to (or other than, in addition to, etc.) the performance result. In other words, in some embodiments, information besides the desired performance result or goal is collected or observed and utilized in the optimization process, as described herein. The collected information may include at least one of compiler information and runtime (and/or execution) information. If the collected information includes compiler information, the compiler information may be associated with at least one of program size, category of instruction, and instruction count. If the collected information includes runtime information, the runtime information may be associated with at least one of cache misses and data transfer rate (or I/O throughput).

The set of parameters is changed based on the collected information (step808). The changing of the set of parameters may be based on the collected information and the performance result. In some embodiments, the changing of the parameters (and/or method800as a whole) includes generating a first model relating the parameters to the collected information and generating a second model relating the performance result to the collected information. A space exploration in the collected information domain may be performed utilizing the first model and/or the second model, and the changing of the set of parameters may be based on the space exploration.

Method800ends (step810) with, for example, the program being (re)compiled (and/or (re)executed) utilizing the changed set of parameters. The process may then be repeated (i.e., multiple times) utilizing the changed parameters and may continue until the desired performance result is achieved. In some embodiments, feedback from users may be utilized to improve the performance of the system over time.