Adaptable and extensible runtime and system for heterogeneous computer systems

Patent metadata

Field	Value
Publication number	US-9557976-B2
Application number	US-201514750994-A
Country	US
Kind code	B2
Filing date	Jun 25, 2015
Priority date	Dec 17, 2013
Publication date	Jan 31, 2017
Grant date	Jan 31, 2017

Abstract

A method for accelerating processing of program code in a heterogeneous system may be provided. It may include identifying at runtime a code region having an acceleration potential, creating a dependency graph of the program code, expanding the dependency graph based on a first set of predefined rules to generate variants of the code region, and determining segments within the variants based on a second set of predefined rules. The segments may be dedicated and assigned and compiled for use to/by a specific execution unit such that a cost function is minimized.

First claim

The invention claimed is:

1. A method for accelerating processing of program code in a heterogeneous system comprising different execution units, the method comprising:
identifying at runtime of the program code a code region in the program code, wherein the code region has an acceleration potential which is determined based on a trigger;
creating a dependency graph of the program code of the code region;
expanding the dependency graph based on a first set of predefined rules, thereby generating variants of the code region, wherein at least one of the variants of the code region is generated by reversing select functions within the code region to create an expanded dependency graph that includes i) an original code of the code region and ii) a variation of the code region having dependencies of the select functions reversed, and wherein the original code of the code region and the variation of the code region are linked within the expanded dependency graph;
determining segments within each of the variants of the code region within the expanded dependency graph based on a second set of predefined rules, wherein each of the segments is assignable to a specific one of the execution units;
selecting the segments out of the variants such that a set of selected segments is equivalent to a program code functionality of the code region, and wherein a total cost function for an execution of the set of selected segments is minimized;
compiling the set of selected segments at runtime of the program code; and
assigning each segment of the set of selected segments to a respective specific one of the execution units.

2. The method according to claim 1 , wherein the trigger comprises one out of the group consisting of: a counter for a repetition of the code region, a marker in the program code, and execution time of the program code of the code region in comparison to stored execution time data of a comparable code region.

3. The method according to claim 1 , wherein only the set of selected segments are compiled.

4. The method according to claim 1 , wherein the variants of the code region generate a same result, and wherein the functions within the code region define nodes of the dependency graph, and wherein replacement functions of the functions represent an alternative node to a given node.

5. The method according to claim 1 , wherein the selecting the segments comprises building groups of segments.

6. The method according to claim 1 , wherein the compiling the set of selected segments comprises using execution unit specific compilers.

7. The method according to claim 1 , wherein the total cost function is a combination of cost functions relating to the segments and the execution units.

8. The method according to claim 1 , wherein at least one of the variants of the code region is generated by replacing one of the functions within the code region with another function which, at runtime, is assigned to a different one of the execution units.

9. The method according to claim 1 , further comprising:
determining whether the variants accelerate the program code by compiling the variants and then evaluating whether the compiled variants accelerate the program code.

10. The method according to claim 1 , wherein the selecting the segments is based on parameters of an actual status at runtime of the heterogeneous system.

11. The method according to claim 10 , wherein the parameters comprise at least one out of the group consisting of: the execution units of the heterogeneous system available, the program code, and input parameters to the program code.

12. The method according to claim 1 , wherein the segments comprise communication nodes.

13. The method according to claim 12 , wherein the communication nodes are implemented using one out of the group consisting of: buffers, queues, serial buses, and direct memory access.

Assignees

• IBM

Inventors

• Angerer Christoph M
• Polig Raphael

Classifications

• G06F9/5066

  Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs (mappping at compile time, see G06F8/451) · CPC title

• Y02B60/167

  Cross-Sectional Technologies · mapped topic

• G06F8/433

  Dependency analysis; Data or control flow analysis · CPC title

• Y02B60/142

  Cross-Sectional Technologies · mapped topic

• G06F9/4552

  Involving translation to a different instruction set architecture, e.g. just-in-time translation in a JVM · CPC title