Source-to-source transformations for graph processing on many-core platforms

Methods are provided for source-to-source transformations for graph processing on many-core platforms. A method includes receiving a graph application including one graph, expressed by a graph application programming interface configured for defining and manipulating graphs. The method further includes transforming, by a source-to-source compiler, the graph application into a plurality of parallel code variants. Each of the plurality of parallel code variants is specifically configured for parallel execution by a target one of a plurality of different many-core processors. The method also includes selecting and tuning, by a runtime component, a particular one of the parallel code variants for the parallel execution responsive to graph application characteristics, graph data, and an underlying code execution platform of the plurality of different many-core processors.

BACKGROUND

1. Technical Field

The present invention relates to data processing, and more particularly to source-to-source transformations for graph processing on many-core platforms.

2. Description of the Related Art

Many applications use graphs to represent and analyze data, but the effective deployment of graph algorithms on many-core processors is still a challenge task. Although there are good compilation and runtime frameworks for parallelizing graph applications on multi-core CPUs, such frameworks do not exist for many-core devices. There is a need for efficient source-to-source compilers that automatically compile and parallelize graph applications on many-core processors because (a) many-core devices offer higher peak performance than multi-core devices, and (b) many-core programming is still a highly specialized (and error prone) skill.

SUMMARY

These and other drawbacks and disadvantages of the prior art are addressed by the present principles, which are directed to source-to-source transformations for graph processing on many-core platforms.

According to an aspect of the present principles, a method is provided. The method includes receiving a graph application including one graph, expressed by a graph application programming interface configured for defining and manipulating graphs. The method further includes transforming, by a source-to-source compiler, the graph application into a plurality of parallel code variants. Each of the plurality of parallel code variants is specifically configured for parallel execution by a target one of a plurality of different many-core processors. The method also includes selecting and tuning, by a runtime component, a particular one of the parallel code variants for the parallel execution responsive to graph application characteristics, graph data, and an underlying code execution platform of the plurality of different many-core processors.

According to another aspect of the present principles, a method is provided. The method includes performing, using a compiling processor, source-to-source compiling on a graph application that includes at least one graph. The source-to-source compiling step includes transforming the graph application and related container data structures into platform-specific container data structures, using parallel code transformation responsive to parallel iterators, and using parallel blocks of code for primitives. The source-to-source compiling step further includes managing execution synchronizations for the graph, the platform-specific container data structures, and the iterators. The source-to-source compiling step also includes converting platform-independent synchronization primitives into platform-specific synchronization primitives.

According to yet another aspect of the present principles, a method is provided. The method includes configuring a graph-processing run-time library with a selection processor configured to select a particular parallel code variant, from among a plurality of received parallel code variants of a graph application including at least one graph, for parallel execution by a target many-core coprocessor responsive to graph application characteristics, graph data, and an underlying code execution platform of the target many-core processor. The method further includes configuring the run-time library with dynamic memory allocation management for an execution of the particular parallel code variant the graph application.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS

The present principles are directed to source-to-source transformations for graph processing on many-core platforms. Advantageously, the present principles are suitable for use with graph applications. However, it is to be appreciated that the present principles can be used with other types of applications, while maintaining the spirit of the present principles.

The present principles provide a new source-to-source compiler that automatically generates parallel code for different many-core platforms (e.g., including, but not limited to, GPUs and the Intel Xeon Phi®) starting from a single, platform-agnostic graph programming Application Programming Interface (API).

The present principles advantageously automate the development of high-performance graph applications on many-core platforms using the source-to-source compiler of the present principles.

FIG. 1shows an exemplary graph processing system100, in accordance with an embodiment of the present principles. The system100includes a graph programming Application Programming Interface (API)110, a source-to-source compiler120, a runtime library130, a graph inspector140, and a hardware profiler150.

In an embodiment, the source-to-source compiler120is processor-based. Of course, other elements ofFIG. 2can be processor-based, while maintaining the spirit of the present principles.

The source-to-source compiler120includes an internal graph data structure transformer121, an internal collections implementator122, a set of parallel basic blocks123, a set of platform-specific synchronization mechanisms transformer124, a Compute Unified Device Architecture (CUDA) code writer125, and an OpenMP code writer126.

The internal collections implementator122includes containers. The containers include, for example, a set container122A, a 31 multi-set container122B, and a queue container122C. Of course, other containers can also be used.

The set of parallel basic blocks123include primitives. The primitives include a BFS iterator123A, a reduction primitive123B, and a scan primitive123C.

The platform-specific synchronization mechanisms transformer124includes a global/local barrier124A and a flat/hierarchical atomizer125.

Online graph modifications171are provided to the runtime library130.

A graph application172is provided to the graph programming API110.

Graph data173is provided to the graph inspector140.

The source-to-source compiler120outputs variantsCPU181, variantsphi182, and variantsGPU183corresponding to the system being used with a multi-core CPU191, an INTEL XEON PHI processor192, and/or an NVIDIA Graphics Processing Unit (GPU)193, respectively.

The runtime library130includes a variant selector and tuner131a dynamic memory handler132.

In an embodiment, an application developer writes the graph application using a programming interface that includes a high-level graph programming API110and a set of platform-agnostic, sequential and parallel constructs that allow the user to define generic graph applications. The graph programming API110is implemented and executed by our new runtime library130.

Then, the application developer uses the source-to-source compiler120to generate an efficient, highly parallelized implementation of the graph application, which can run on different many-core processors like the Intel Xeon Phi® or a GPU.

The source-to-source compiler120generates different code variants for multi-core CPUs, Intel Xeon Phi® coprocessors and NVIDIA® GPUs. These code variants may differ in several aspects, including, for example: from the type of parallelization performed, to the implementation of the underlying data structures, to the handling of nested parallelism, and more. The generated code is written in OpenMP and CUDA and, in an embodiment, it uses the offload execution model on the Intel® Phi. During code generation, the graph and the containers (sets122A, multi-sets122B, and queues122C) are transformed into internal, platform-specific data structures by the platform-specific synchronization mechanisms transformer124. In addition, existing parallel basic blocks123are used for common primitives such as reduction123A, sort123B, and scan123C. Parallelization is enabled by the presence of parallel iterators, which can be explicitly inserted in the code by the programmer. The source-to-source compiler120automatically handles synchronizations associated with the graph, the iterators and the containers. Synchronizations associated with custom data structures can be explicitly indicated by the programmer using high-level, platform-independent synchronization primitives, which are transformed into platform-specific synchronization mechanisms by the platform-specific synchronization mechanisms transformer124.

Finally, the runtime system supports two important functions: (i) selecting, by the variant selector and tuner130A, the most suitable code variant depending on the characteristics of the application, the dataset and the underlying platform, and (ii) supporting, by the dynamic memory handler130B, dynamic memory allocation through the offset address.

In an embodiment, the variant selector and tuner130A includes a selection processor for implementing the selection and tuning. In an embodiment, the selection processor can also be used to execute a selected code variant for a graph application including at least one graph. Tuning can be performed on a selected code variant to avoid execution errors and to optimize parallel execution of at least portions of the selected code variant.

FIG. 2shows an exemplary method200for generating and executing source-to-source transformations for many-core processors, in accordance with an embodiment of the present principles. Steps210and220correspond to a code generation time, and steps230and240corresponds to runtime. It is to be appreciated that while the following steps are labeled sequentially, such labeling is not intended to imply any specific ordering, as some steps can be performed out of order as well as in parallel. These and other variations to method200are readily determined by one of ordinary skill in the art given the teachings of the present principles provided herein, while maintaining the spirit of the present principles.

At step210, receive a graph application, that includes at least one graph, expressed by a graph programming application programming interface (API) specifically configured for defining and manipulating graphs. The expression of the graph application can include node information, edge information, root information, weight information, and so forth. The expression of the graph application received at step210can further include, for example, but is not limited to, primitives. The primitives can include, but are not limited to, dynamic memory management primitives, parallel primitives, synchronization primitives, and runtime primitives.

Further regarding step210, as well as API110, the API includes methods to define and manipulate application specific attributes, container data structures, parallel code iterators, dynamic memory management primitives, parallel primitives, synchronization primitives, and runtime primitives.

At step220, transform the graph data into a source-to-source compiler to generate parallel code for different many-core processors.

At step220A, determine internal graph container data structures (e.g., ordered set, unordered set, multi-set, queue, etc.). These internal graph container data structures are typically platform-independent.

At step2220B transform the internal graph container data structures into internal, platform-specific container data structures (by the platform-specific synchronization mechanisms transformer124), using parallel code transformation performed by parallel iterators, and using parallel blocks of code for primitives.

At step220D, generate/manage synchronizations associated with the graph, the containers, and the iterators.

At step230, invoke the run-time library to perform code variant selection and tuning responsive to graph characteristics, graph data, and an underlying code execution platform.

At step240, invoke the run-time library to perform dynamic memory allocation.

An exemplary graph programming API that can be used for API110is as follows:

A description will now be given regarding some of the benefits/advantages of the present principles over the prior art.

The graph programming API210has many primitives that specifically help in automatically generating parallelized code for a variety of different many-core platforms.

The source to source compiler120has many new transformations to generate efficient parallelized code by recognizing parallelizing opportunities exposed by the use of the graph programming API210by the application developer to write the graph application.

The design of the run-time library130is specific to each many-core platform, and one key strength of the run-time library130is that it can dynamically select and tune the code variant that better fits the characteristics of the target dataset and the hardware profile, as well as enable dynamic memory allocation.

A description will now be given of some of the many attendant competitive/competitive values of the present principles.

The present principles offer at least the following two values: (a) our source-to-source compiler generates parallelized code for graph applications so that they execute as fast as manually optimized code for many-core processors, and (b) the time required to develop good parallel versions of the code that can execute on many-core processors is reduced by 10× to 100×, and our procedure is completely automatic.

The foregoing is to be understood as being in every respect illustrative and exemplary, but not restrictive, and the scope of the invention disclosed herein is not to be determined from the Detailed Description, but rather from the claims as interpreted according to the full breadth permitted by the patent laws. Additional information is provided in an appendix to the application entitled, “Additional Information”. It is to be understood that the embodiments shown and described herein are only illustrative of the principles of the present invention and that those skilled in the art may implement various modifications without departing from the scope and spirit of the invention. Those skilled in the art could implement various other feature combinations without departing from the scope and spirit of the invention.