Patent Description:
Dataflow applications are computer programs (e.g. software) that are written using dataflow programing methods. Modern dataflow applications use the operators system to maximize software compatibility and composability. Developers of modern dataflow application use operators to create new algorithms by assembling operators as building blocks for these algorithms. A dataflow graph (see <FIG>) may be used to represent how data flows among different operators (ops) of an algorithm in a dataflow application. During runtime, an execution engine of a host processing unit offloads operators in the dataflow application to different execution units such as central processing units (CPUs), graphic processing units (GPUs) or other forms of special-purpose hardware accelerators. In this approach, the hardware accelerators operate passively, i.e., they stay idle until new operators are formed and offloaded to them by the execution engine which runs on a host processing unit. The overhead of offloading a single operator to a hardware accelerator can be quite significant especially when operators have relatively small computation times.

There is a need for a method and apparatus for reducing the offload overhead related to offloading operators in dataflow applications to a hardware accelerator for execution.

Further, <CIT>refers to an apparatus for processing data under control of a program having program instructions and subgraph suggestion information identifying respective sequences of program instructions corresponding to computational subgraphs identified within said program, said apparatus comprising: a memory operable to store a program formed of separate program instructions, processing logic operable to execute respective separate program instructions from said program; and accelerator logic operable in response to reaching an execution point within said program associated with a subgraph suggestion to execute a sequence of program instructions corresponding to said subgraph suggestion as an accelerated operation instead of executing said sequence of program instructions as respective separate program instructions with said processing logic.

Further, <CIT> refers to techniques for partitioning an operator flow graph. The techniques include receiving source code for a steam processing application, wherein the source code comprises an operator flow graph, wherein the operator flow graph comprises a plurality of operators, receiving profiling data associated with the plurality of operators and one or more processing requirements of the operators, defining a candidate partition as a coalescing of one or more of the operators into one or more sets of processing elements (PEs), using the profiling data to create one or more candidate partitions of the processing elements, using the one or more candidate partitions to choose a desired partitioning of the operator flow graph, and compiling the source code into an executable code based on the desired partitioning.

An object of embodiments of the present invention is to provide a method and apparatus for improving the performance of dataflow applications by reducing the offload overhead related to offloading operators to hardware accelerators for execution. This problem is solved by the subject matter of the independent claims. Further implementation forms are provided in the dependent claims.

In a first aspect a method performed by a host processing unit hosting and running a software compiler is provided, wherein a computer system comprises the host processing unit and a hardware accelerator, the method comprising the steps of:.

In a first implementation form of the first aspect the determining whether the operators of the given candidate group are to be grouped together comprises determining whether the operators should be combined based on whether operators of the given candidate group are constrained to be executed on different hardware accelerators of a plurality of hardware accelerators.

In a second implementation form of the first aspect the determining whether the operators of the given candidate group are to be grouped together comprises determining whether the operators should be combined based on available resources of the hardware accelerator.

In a third implementation form of the first aspect the determining whether the operators of the given candidate group are to be grouped together comprises determining whether the operators should be combined based on a number of the operators of the given candidate group.

In a fourth implementation form of the first aspect the determining whether the operators of the given candidate group are to be grouped together comprises determining whether the operators should be combined based on a computation runtime associated with executing all of the operators of the given candidate group.

In a second aspect a system comprising a host processing unit hosting a software compiler and a hardware accelerator is provided, wherein the system is configured to perform any of the methods according the first aspect or its implementation forms.

In a third aspect a non-transient memory having stored therein instructions is provided, the instructions, when executed by a host processing unit, causing the host processing unit to perform the method according to the first aspect or its implementation forms.

In a fourth aspect a computer program product comprising computer program instructions is provided, wherein, when the computer program instructions are executed by a host processing unit, the computer program instructions cause the host processing unit to perform the method according to the first aspect or its implementation forms.

Embodiments of the invention comprise methods and apparatus for improving the performance of dataflow applications based on operators that are dispatched to accelerator hardware for execution. Embodiments comprise systems that enable hardware accelerators to execute super-ops (multi-operator portions) of a dataflow graph autonomously with minimal intervention from a host processor. The execution of dataflow applications is performed on a computer system that comprises a host processing unit and one or more hardware accelerators. The host processing unit controls the overall execution of the program and may dispatch ops or super-ops to be executed on hardware accelerators. The dispatching of ops (or super-ops) by an execution engine of the host processor to a hardware accelerator is referred to as "offloading.

Embodiment comprise an architecture that includes a development environment and a runtime environment for dataflow programming applications. Users, such as application developers utilize the architecture of the proposed system to develop and run dataflow applications. Based on a dataflow graph representation <NUM> of an application, a user uses a super-op compiler <NUM> (described below) to produce an output executable binary. The executable output of the compiler <NUM> may then be utilized by a runtime system to execute the program, which includes the offloading of super-ops (groups of ops) to accelerator hardware <NUM>.

<FIG> illustrates a flow chart of a development workflow <NUM> and a runtime workflow <NUM> according to an embodiment. The development workflow <NUM> and the runtime workflow <NUM> may be performed in sequence or independently. The development workflow <NUM> is performed by a super-op compiler <NUM> and starts with graph analyzer <NUM> analyzing <NUM> a dataflow graph representation <NUM> of the dataflow application to analyze data dependencies between the ops of the dataflow graph <NUM>. The graph analyzer identifies <NUM> a plurality of candidate groups of operators <NUM> that may be stored in the super-op candidate repository (repo) <NUM>. The determination <NUM> of which groups of operators to combine takes input from the logical accelerator resource model <NUM> which comprises parameters of capabilities or constraints of the hardware accelerator(s) <NUM> that are available to the system. Executable binary code segments are generated by the super-op code generator <NUM> and may be stored in the operators binary repository (ops bin repo) <NUM> for future use. If the super-op code generator <NUM> determines that an executable binary code segment <NUM> already exists, it can be obtained from the operators binary repository <NUM> without recompiling it. The super-op code generator <NUM> then generates <NUM> a unit of binary code. The unit of binary code contains all the necessary binaries, navigation tables <NUM>, metadata, parameters, etc. that are required by the runtime system to execute the dataflow program, including offloading to a hardware accelerator <NUM>.

The unit of binary code may be used by the runtime workflow <NUM> for immediate execution or for execution at a later time. The runtime workflow <NUM> comprises dispatching (<NUM>) the unit of code to the runtime system of a host processor for execution (<NUM>). As part of the execution by the host processor, the runtime system may then offload (<NUM>) ops and super-ops to the hardware accelerator <NUM> as instructed by the unit of binary code.

<FIG> illustrates an exemplary dataflow graph <NUM> of a dataflow application for compiling by the super-op compiler of the present disclosure. The exemplary dataflow graph <NUM> includes six operators (hereinafter referred to as ops) Op1, Op2, Op3, Op4, Op5, and Op6. Ops, such as Op5 are linked by edges of the dataflow graph <NUM> that represent data paths. Given an op-based computation represented as a dataflow graph <NUM>, a sub-graph that may be combined into a single op is identified. Then the parameters required as part of the computations of the sub-graph are analyzed. Parameters may include data types, tensor shapes, data formats, and any other hyper-parameters that are specific to the individual ops within the sub-graph. The values of the parameters of the sub-graph are used to generate code that represents the computation of the entire sub-graph as one large op, referred to herein as a super-op. The super-op may be offloaded to a hardware accelerator <NUM>. The super-op is computationally equivalent to many elementary small ops offloaded to a hardware accelerator separately, however the super-op is offloaded with far less offload overhead. It will be appreciated that although the exemplary dataflow graph illustrated in <FIG> includes six ops, a dataflow graph may include any number of ops.

<FIG> illustrates a super-op compiler <NUM> according to an embodiment of the present disclosure. The super-op compiler <NUM> is software that includes instructions that are executable by a processor of a computing system, such as computing system <NUM> (see <FIG>). The super-op compiler <NUM> includes a logical accelerator resource model <NUM>, a graph analyzer <NUM>, a super-op candidate repository <NUM>, a super-op code generator <NUM>, and an operators bin repository <NUM> (hereinafter referred to as ops bin repository <NUM>). The graph analyzer <NUM> of the super-op compiler receives a dataflow graph <NUM> of a dataflow application, analyzes the dataflow graph <NUM>, identifies which ops in the dataflow graph <NUM> can be combined into a super-op that can be passed to the super-ops code generator <NUM>, and outputs super-op candidates that include the ops that can be combined. The graph analyzer <NUM> may utilize information and constraints from a logical accelerator resource model <NUM> and a variety of other sources when making this identification. The logical accelerator resource model <NUM> comprises information on available resources of the hardware accelerator <NUM>, and constraints of the hardware accelerator <NUM>. The dataflow graph <NUM> may include information that indicates which ops can be offloaded to a hardware accelerator, (including specifying which hardware accelerator if there is more than one hardware accelerator available) or if offloading is allowable at all. Decisions regarding the offloading of ops (referred to as offloading decisions) may be provided explicitly or implicitly by programmers. Offloading decisions may also be determined by an offload analyzer (not shown) that indicates which ops may be offloaded. The graph analyzer <NUM> analyzes the dataflow graph to determine the feasibility and the performance cost of dispatching (i.e., offloading) each operator or group of ops. An example of a constraint is that two ops that are specified to be dispatched (i.e., offloaded) to different hardware accelerators may not be combined. Other constraints include whether the target hardware accelerator possesses sufficient on-chip resources (for example, computing capabilities, memory size, bandwidth, etc.) to efficiently run the prospective super-op. The cost model also considers heuristic factors like the number of ops inside a super-op, the op's computational requirements, the resulting number of super-ops in the final graph, and the execution dependency between ops inside one super-op to balance the super-op benefits and the parallelism opportunity of the system.

In some cases, the super-op compiler may drastically reduce the offloading overhead. Therefore, the offload analyzer (not shown) and super-op graph analyzer <NUM> can utilize common heuristics amongst both to decide their respective outputs. In some embodiments, users are also able to provide directives that indicate which ops or sub-graphs are to be combined. In these embodiments, users only need to specify which sub-graph to combine and do not need to provide a fused implementation for the sub-graph. Ops are combined based on a method of "shallow fusion", in which the existing implementation of the ops is taken as is and then combined together to build a super-op. Using the shallow fusion method, it is not necessary to create a new implementation of the fused op with additional restrictions.

The super-ops candidate repository <NUM> receives the super-op candidates from the graph analyzer <NUM> and stores valid data-flow graph structures that define which ops <NUM> are to be combined. The nodes in these sub-graphs <NUM> are the same ops (for example, Op5 <NUM>) as the ones that were from the original dataflow graph <NUM>.

The super-op code generator <NUM> receives a candidate super-op (i.e., the combined ops representation <NUM>) from the super-ops candidate repo <NUM> and generates a new super-op that is computationally equivalent to the sub-graph of the individual ops used to create the super-op. Note that the generation of the new super-op is done systematically and does not require programmers to provide a new implementation for the combined ops in order to generate a super-op. Additional metadata can be generated and attached to the new super-op to allow debugging and profiling of an individual op's Op4, Op5, Op6 computations within the candidate super-op <NUM>. This allows users to debug and profile the super-op as if they were the individual ops from dataflow graph <NUM>.

The super-ops code generator <NUM> generates new host source code that indicates which ops have been combined. It also generates a navigation table <NUM> that contains a list of parameters which represents all the individual ops' parameters, and additional metadata that enables the accelerator <NUM> to navigate from one op's set of computation to the next. The new generated super-op <NUM> generated by the super-ops code generator <NUM> is appended to the list of accelerator library ops. During run time, the super-op <NUM> is selected by a runtime system of the host processing unit <NUM> for offloading to the hardware accelerator instead of the individual ops being offloaded individually.

In order for the super-op compiler to systematically generate super-ops, (basic) ops are represented in a 'basic-op Intermediate Representation' (IR) format that help the graph analyzer <NUM> determine whether an op can be combined with other ops into a super-op.

An ops bin repository (repo) <NUM> stores existing target specific implementation of the super-ops. For example, each super-op has its target specific implementation as a precompiled shared object file. Any other application that is targeted for the same architecture as the shared object is able to include and link the precompiled shared object file during compile time. The repository <NUM> can also store the source level implementation <NUM> of the super-ops and their included ops. This provides the flexibility of recompilation into binary using different compiler optimizations.

Navigation tables <NUM> are provided in order to enable the accelerator <NUM> to use a single offloaded super-op to perform multiple ops worth of computation. The super-op uses a packed data format. Navigation tables <NUM> are used for data serves as a navigation guide for the super-op in order for it to be able to provide the necessary parameters to each op, and also the control flow from one op to the next. A parameter table is generated that stores data-structure of input and output parameters for ops within the super-op. The data structure contents are populated by the host. In addition to the input and output parameters being stored, the navigation table <NUM> also contains metadata that indicates the control flow from the current op to the next op to be called within the super-op. In some embodiments, this metadata comprises function pointers of the ops themselves. This information is provided to the hardware accelerator <NUM>, as illustrated in <FIG>. The hardware accelerator <NUM> receives the super-ops containing header code <NUM>, ops <NUM>, <NUM>, and <NUM>, and navigation tables <NUM>, performs the operations, and returns any resulting data as instructed. The operators binary repository <NUM> stores the binary of each op in the super-op and the super-ops code generator <NUM> provides the super-op header code plus the binaries for the ops to the runtime system of the host processor.

As part of the offloading process, individual ops (called basic-ops) take in provided parameters needed for their computation. In order to facilitate automatic generation of super-ops, implementations of basic-ops must be represented in a intermediate representation (IR). Associated with the IR is a compiler that can generate separate host and accelerator hardware <NUM> code out of the IR of a basic-op. Accelerator hardware <NUM> code comprises kernel functions that implement ops or super-ops on the accelerator hardware <NUM>. The compiler will combine together the host and accelerator hardware <NUM> code of all basic-ops in a super-op by defining input parameters and data across basic-ops according to the navigation table <NUM> information. The IR allows the compiler, to generate binary ops code, that may be executed by the accelerator hardware <NUM>, and host code, which is executed by the host processor to prepare parameters for the binary ops code and invoke the binary ops code on the accelerator hardware <NUM>. This is done for individual ops separately and allows for the defining of input parameters in the host and binary ops codes to be updated based on how a basic op is combined with other basic ops within the super-op. In some embodiments, the IR consists of an interface descriptor that specifies properties of input and output data to a device-side basic-op kernel function. In some embodiments, input and output data of basic-op kernel functions are specified as function parameters and must be referenced by symbol names (i.e., no hard-coded memory addresses) in the kernel function. In some embodiments, the body of the kernel function cannot have any side-effect other than those specified on the interface descriptor. The IR can express arithmetic operations, variable accesses, and limited form of control-flow. It also supports calling external functions (i.e., functions that are not implemented in the IR) as long as the interface properties of the basic-op kernel function are not violated.

In embodiments, a super-op contains multiple ops worth of computation. When a super-op is offloaded to hardware accelerator, it includes a navigation table <NUM> of parameters. The navigation table <NUM> of parameters includes the parameters required by each of the individual original ops and additional metadata that helps the super-op determine the order of ops that function calls must be made for.

<FIG> illustrates the structure of the navigation table <NUM>. The navigation table <NUM> has a base address <NUM> and a sub-table <NUM> & <NUM>, for each op in the super-op. The super-op code is aware of which sub-table <NUM> or <NUM> it should be retrieving data from. With reference to the opl sub-table <NUM>, the header parameter, entry size <NUM>, describes the total size of each sub-table <NUM>. With this information, the super-op is able to calculate the offset to traverse from one sub-table <NUM> to the next <NUM>.

After calculating the offset to load in the successive sub-table, the super-op is able to read the entry in the sub-table that indicates what op to call as a function - e.g., a function pointer. This function pointer is called, and the sub-table's parameter entries are passed in as function parameters.

Conventional programming of the host processing unit <NUM> would require the hardware accelerator <NUM> to incur an expensive communication between the host processing unit and the hardware accelerator <NUM> in order to figure out what is the next set of computations it should perform. The navigation table <NUM> relaxes this constraint and enables the hardware accelerator <NUM> to become self-aware of subsequent computation tasks it is supposed to perform, without having to iteratively communicating with the host processing unit for the next set of instructions.

The process of offloading an op to a hardware accelerator incurs a large offload overhead that is difficult to reduce due to constrained hardware design of the hardware accelerator. The super-op is a single op that produces the computation equivalent of many individual ops, while incurring the offload overhead only once. The function calls made by the super-op to multiple ops are within the hardware accelerator itself and therefore the offload overhead is much smaller compared to the overhead related to communication between the host processing unit and the hardware accelerator.

Embodiments of are not limited to any specific dataflow frameworks. Embodiments may also be implemented for neural network applications that use dataflow programming techniques. Neural network frameworks that may implement embodiments include TensorFlow, PyTorch, etc,. Furthermore, embodiments can be applied to different variations of hardware accelerators that uses the host-device offloading model such as GPUs, DSPs, FPGAs, etc..

<FIG> illustrates a programming model <NUM> and how ops are offloaded by code running on a host processor (referred to as host code <NUM>) as ops to a accelerator hardware <NUM>. The host code <NUM> represents execution that determines which op should be offloaded based on the op. The super kernel <NUM> comprises a prolog <NUM> to initialize the hardware accelerator <NUM>. It is followed by a first conventional kernel call <NUM>. Glue code <NUM> comprising synchronization, a navigation table, etc. is provided between kernel calls. By reducing the number of times, during runtime that the host processing unit needs to communicate with the hardware accelerator <NUM>, the end-to-end execution time of the dataflow application is reduced.

The following describes a systematic approach in generating a super-op according to an embodiment. First, a target specific function object is created that describes the op's characteristics. This includes the op type, input/output shapes, data types, hyper-parameters, and target architecture. Next, the input/output dataflow with uniquely identified place holders is described. This has the function of variables that are evaluated at runtime. These place holders are bound to the function object. This process is iterated through each op.

As part of the heuristic, a subset list of all the function objects that represent ops that can be combined into a Super-op is selected. Other variables in the heuristic include a cost-benefit model of the offloading overhead time incurred. One criteria is that all the function objects must be of the same target architecture. A compose API is called that takes in a list of function objects that will return a new function object that represents the super-op. This will combine all the metadata information contained in each of the individual function objects, which is described above with respect to the navigation table <NUM>.

The newly returned function object can then be invoked as a function and offloaded to the device and the host-device run time overhead is incurred once per super-op.

<FIG> is block diagram of a computing system that runs a software compiler that performs the method disclosed herein. In some aspects, a functions may be performed across a plurality of computing systems across a plurality of geographic locations. Computing system <NUM> may provide an example of computing hardware that be used by an application developer to develop software according to embodiments. This may include hosting and running the super-ops compiler <NUM> and the runtime system <NUM>. It may also be used to execute software according to embodiments. Computing system <NUM> may act as a host system to dispatch super-ops to accelerator hardware <NUM>. Accelerator hardware <NUM> is couple to a host processing unit <NUM> by a number of means. It may be coupled as a core on the same die as the computing system. It may be a separate die within a multi-chip package integrated circuit (IC). It may be a separate IC on the same PCB as the computing system. It may be a separate module, or card within a computer chassis. It may also be housed separately and be in close proximity, or be remotely located from the computer system. The accelerator hardware <NUM> may be coupled by any number of means including an internal bus to an IC or multi-chip module, an I/O interface <NUM> such as SATA, USB, or Thunderbolt. It may also be coupled using wired or wireless technology through a network interface <NUM>. The accelerator hardware <NUM> may be coupled to the host computer system <NUM> using multiple means.

Specific embodiments may utilize all of the components shown or only a subset of the components, and levels of integration may vary amongst computing systems. Furthermore, a computing system may contain multiple instances of a component, such as multiple processing units, processors, memories, transmitters, receivers, etc. The computing system <NUM> typically includes a central processing unit (CPU) <NUM>, a bus and a memory <NUM>, and may optionally also include a mass storage device <NUM>, a video adapter <NUM>, and an I/O interface <NUM> (each shown in dashed lines to indicate they are optional). The computing system may further include one or more network interface(s) <NUM> for connecting the computing system to communication networks <NUM>.

The CPU may comprise any type of electronic data processor, and may include one or more cores or processing elements. The memory may comprise any type of non-transitory system memory such as static random access memory (SRAM), dynamic random access memory (DRAM), synchronous DRAM (SDRAM), read-only memory (ROM), or a combination thereof. In an embodiment, the memory may include ROM for use at boot-up, and DRAM for program and data storage for use while executing programs. The bus may be one or more of any type of several bus architectures including a memory bus or memory controller, a peripheral bus, or a video bus.

The mass storage may comprise any type of non-transitory storage device configured to store data, programs, and other information and to make the data, programs, and other information accessible via the bus. The mass storage may comprise, for example, one or more of a solid state drive, hard disk drive, a magnetic disk drive, or an optical disk drive.

The video adapter <NUM> and the I/O interface <NUM> provide optional interfaces to couple external input and output devices to the processing unit. Examples of input and output devices include a display <NUM> coupled to the video adapter <NUM> and an I/O device <NUM> such as a touch-screen coupled to the I/O interface <NUM>. Other devices may be coupled to the processing unit, and additional or fewer interfaces may be utilized. For example, a serial interface such as Universal Serial Bus (USB) (not shown) may be used to provide an interface for an external device. Alternatively, the computing system may rely upon the network interface(s) for connection to available mass storage(s), video adapter(s), and I/O interface(s) available on the networks.

Through the descriptions of the preceding embodiments, the present invention may be implemented by using hardware only or by using software and a necessary universal hardware platform. Based on such understandings, the technical solution of the present invention may be embodied in the form of a software product. The software product may be stored in a non-volatile or non-transitory storage medium, which can be a compact disk read-only memory (CD-ROM), USB flash disk, or a removable hard disk. The software product includes a number of instructions that enable a computer device (personal computer, server, or network device) to execute the methods provided in the embodiments of the present invention. For example, such an execution may correspond to a simulation of the logical operations as described herein. The software product may additionally or alternatively include number of instructions that enable a computer device to execute operations for configuring or programming a digital logic apparatus in accordance with embodiments of the present invention. each op, and also the control flow from one op to the next. A parameter table is generated that stores data-structure of input and output parameters for ops within the super-op. The data structure contents are populated by the host. In addition to the input and output parameters being stored, the navigation table <NUM> also contains metadata that indicates the control flow from the current op to the next op to be called within the super-op. In some embodiments, this metadata comprises function pointers of the ops themselves. This information is provided to the hardware accelerator <NUM>, as illustrated in <FIG>. The hardware accelerator <NUM> receives the super-ops containing header code <NUM>, ops <NUM>, <NUM>, and <NUM>, and navigation tables <NUM>, performs the operations, and returns any resulting data as instructed. The operators binary repository <NUM> stores the binary of each op in the super-op and the super-ops code generator <NUM> provides the super-op header code plus the binaries for the ops to the runtime system of the host processor.

<FIG> illustrates the structure of the navigation table <NUM>. The navigation table <NUM> has a base address <NUM> and a sub-table <NUM> & <NUM>, for each op in the super-op. The super-op code is aware of which sub-table <NUM> or <NUM> it should be retrieving data from. With reference to the op1 sub-table <NUM>, the header parameter, entry size <NUM>, describes the total size of each sub-table <NUM>. With this information, the super-op is able to calculate the offset to traverse from one sub-table <NUM> to the next <NUM>.

Claim 1:
A method performed by a host processing unit hosting and running a software compiler, wherein a computer system comprises the host processing unit and a hardware accelerator, the method comprising the steps of:
• analyzing (step <NUM>), by the software compiler, a dataflow graph representing data dependencies between operators of a dataflow application to identify a plurality of candidate groups of the operators, wherein a candidate group of operators is a group of operators, which can be combined into a single operator;
• based on characteristics of the hardware accelerator and the operators of a given candidate group of the plurality of candidate groups, determining (step <NUM>), by the software compiler, whether the operators of the given candidate group are to be combined; and
• in response to determining that the operators of the given candidate group are to be combined:
∘ retrieving, by the software compiler, executable binary code segments corresponding to the operators of the given candidate group;
∘ generating (step <NUM>), by the software compiler, a unit of binary code including the executable binary code segments and including a navigation table, wherein the navigation table is a navigation guide in order for providing to the hardware accelerator the necessary parameters to process each operator among the operators in the given candidate group and also for providing to the hardware accelerator an execution control flow among the executable binary code segments from one operator to a next operator of the given candidate group; and
∘ dispatching, by the host processing unit, the unit of binary code to the hardware accelerator for execution of the unit of binary code.