Patent ID: 12197955

DETAILED DESCRIPTION OF ILLUSTRATIVE EMBODIMENTS

This disclosure provides many applicable inventive concepts that can be embodied in a wide variety of specific contexts. The specific embodiments are merely illustrative of specific configurations and do not limit the scope of the claimed embodiments. Features from different embodiments may be combined to form further embodiments unless noted otherwise. Variations or modifications described with respect to one of the embodiments may also be applicable to other embodiments. Further, it should be understood that various changes, substitutions, and alterations can be made herein without departing from the spirit and scope of this disclosure as defined by the appended claims. While the inventive aspects are described primarily in the context of a graphics processing unit (GPU) and a central processing unit (CPU), it should also be appreciated that those inventive aspects may also be applicable to other processing units to provide for inter-node parallel processing in directed acyclic graph (DAG) model computations.

The processing of DAG computations is generally implemented using intra-node parallelism, in which multiple cores of a same processing unit process each node of the DAG in a sequential and dependent manner. In particular, each computational task in a DAG computation model is associated or mapped to an individual node, and in certain computations, the computational task may be subdivided into smaller subtasks. In intra-node parallelism processing, the scheduling granularity is constrained within a single node and no parallel processing using different processing units is achieved between multiple nodes or within each node. As an example, subtasks associated with a first node may be parallel processed by multiple cores of a CPU and subtasks associated with a second node may be parallel processed by multiple cores of a GPU. However, the scheduling of the processing by the GPU of the second node does not begin until scheduling of the processing by the CPU of the first node is complete. As such, each node in intra-node parallel processing is computed independently and sequentially by a specific processing unit. This results in wasted resource utilization in a processing system.

Embodiments of this disclosure provide for the construction and scheduling of an updated DAG computation model for inter-node parallel processing based on an original DAG computation model originally used for intra-node parallel processing. Certain embodiments of the disclosure may advantageously enable parallelism, using different processing units, to be achieved between multiple DAG nodes. In other embodiments, parallelism, using different processing units, may advantageously be achieved within subtasks of different nodes of the original DAG computation model. In particular, each subtask, previously associated with a single node, may be represented as a new node in a modified DAG computation model. The transformation of the original node into multiple new sub-nodes and the arrangement of a new DAG computation model based on the multiple new sub-nodes may then allow multiple hardware resources (i.e., CPU, GPU, etc.) to be simultaneously utilized in the computation of the new DAG computation model. As a result, the processing system is able to process a DAG computation model at a rate that is significantly faster and more efficient than previously performed using, for example, intra-node parallel processing. These and other details are discussed in greater detail below.

FIG.1illustrates a block diagram of an embodiment processing system100for performing methods described herein, which may be installed in a host device. As shown, the processing system100includes central processing units (CPUs)102and106, a graphics processing unit (GPU)110, a digital signal processor (DSP)114, an image signal processor (ISP)118, a video processing unit (VPU)122, a neural network processing unit (NPU)126, a display processing unit (DPU)130, an interconnect bus link134, a shared memory unit136, a memory controller138, memory units140and142, and peripheral interconnect144, which may (or may not) be arranged as shown inFIG.1. The processing system100may include additional components not depicted inFIG.1, such as long-term storage (e.g., non-volatile memory, etc.). In some embodiments, the processing system100may include a subset of the various processing units. The illustrated quantity of each component inFIG.1is illustrated for simplicity of the discussion. Additional number of same component types may be contemplated in various embodiments.

In some embodiments, each component of the processing system100may be located on a single chip or circuit, for example, in a system on a chip (SoC) type of integrated circuit (IC). In other embodiments, each component of the processing system100may be located on a different chip or circuit. In an embodiment, some components of the processing system100may be located on the same chip or circuit while some components may be located on a different chip or circuit.

The CPUs102and106may be used to carry out basic arithmetic, logic, input/output (I/O), and control operations of sets of instructions in the processing system100. The GPU110may be used to carry out efficient computer graphics calculations and image processing operations of sets of instructions in the processing system100. The DSP114may be used to efficiently measure, filter, or compress analog signals or process digital signal processing algorithms in the processing system100. The ISP118is a specialized type of DSP114that may be used to efficiently process images in the processing system100. The VPU122is also a specialized type of DSP114that may be used to efficiently process video in the processing system100. The NPU126may be used to process data and solve problems using neural networking in the processing system100. The DPU130may be used to process data related to the display of the processing system100. Examples of other types of processing units not shown inFIG.1that may be implemented using embodiments of this disclosure are an application processing unit (APU), a field programmable gate array (FPGA), a microcontroller, etc. Each processing unit of the processing system100may be architecturally optimized and designed to perform a non-limiting set of specific tasks in an efficient or accelerated manner. The list of processing units as illustrated inFIG.1is non-limiting example of task specific processors, each having multiple cores. As an example, the GPU110can be architecturally optimized to repeatedly operate a same operation on large batches of data more quickly and efficiently than the CPUs102and106. Each of the various processing units may independently include hardware caches104,108,112,116,120,124,128, and132organized as a hierarchy of more cache levels (L1, L2, etc.). Each processing unit may also include several or hundreds of cores that can handle many thousands of threads simultaneously.

The interconnect bus link134is a communication link or cache coherent interconnect used to transfer data between the various processing units, the shared memory136, and the peripheral interconnect144. The interconnect bus link134may be a software or hardware type control bus, an address bus, or a data bus that operates across multiple communication protocols. The interconnect bus link134may have a variety of topologies such as multi-drop, daisy chain, switch, etc.

The shared memory136may be any component or collection of components adapted to store programming and/or instructions, and associated input/output data and/or intermediate data for execution by any of the processing units. Each processing unit may have access to the shared memory136through the interconnect bus link134. The shared memory136may be a non-transitory computer-readable media. The non-transitory computer-readable media includes all types of computer readable media, including magnetic storage media, optical storage media, flash media, and solid state storage media. It should be understood that software can be installed in and sold with the processing system100. Alternatively, the software can be obtained and loaded into the processing system100, including obtaining the software through physical medium or distribution system, including, for example, from a server owned by the software creator or from a server not owned but used by the software creator. The software can be stored on a server for distribution over the internet, for example.

The memory controller138is used to manage flow of data going to and from the shared memory136. In some embodiments, the memory controller138may be an integrated memory controller (IMC). In some embodiments, the memory controller138may be an external component to the processing system100. The memory units140and142may be a double data rate (DDR) type of memory or a low-power DDR (LPDDR) type of memory. The peripheral interconnect144may be any component or collection of components that allow the processing system100to communicate with other devices/components and/or a user. In an embodiment, the peripheral interconnect144may be adapted to communicate data, control, or be used to manage messages from the processor100to applications installed on the host device and/or a remote device. In another embodiment, the peripheral interconnect144may be adapted to allow a user or user device (e.g., personal computer (PC), etc.) to interact/communicate with the various processing units of the processing system100.

FIG.2Ais an example DAG computation model180including three nodes N1182, N2184, and N3186. The DAG computation model180may be a graph used, for example, in image processing, video processing, or in a deep neural network processing application. In particular, the DAG computation model180may be a graph model of any type of application processing that can be split into multiple layers or separate synchronized computational tasks.FIG.2Aillustrates a DAG computation model180that includes 3 nodes; however, it should be appreciated that a DAG computation may have any number of nodes greater than 2. In this example, each node N1,182, N2184, and N3186is associated with a separate task or computational block within the DAG computation model180.

In a processing system with multiple processor types, a processing unit may be used to schedule or assign each node to a particular processing unit based on the specific task needed to be completed at the node. This type of scheduling is typically done to take advantage of the optimized processing inherent in the different processing types. As an example, in the processing system100ofFIG.1, the GPU110may be tasked to process node N1182, the DSP114may be tasked to process node N2184, and the CPU102may be tasked to process node N3186. Each node, in turn, can be divided into multiple sub-tasks or multiple computational blocks, as further detailed below.

In a processing system where different processing types include multiple cores, each sub-task or computational block within a node may be intra-node processed, using a scheduling of the processing units, by a separate core of the specific processing type. In intra-node parallel processing of the DAG computation model180, the task associated with node N2184does not begin until the task associated with node N1182is complete. In other words, the output188of node N1182is the input to node N2184; the output190of node N2182is the input to node N3186; and so forth for the other nodes.

In general, as each node of the DAG computation model180is arranged in a sequential and interdependent configuration, the total time for processing the DAG computation is the accumulation of the time to process each node. As an example, if processing all sub-nodes of node N1182takes T1 time, processing all sub-nodes of node N2184takes T2 time, and processing all sub-nodes of node N3186takes T3 time, the total time to process the computation model is Ttotal=T1+T2+T3. During time T1, the processing unit assigned to node N1182is active while the processing units assigned to node N2184and node N3186are idle. During time T2, the processing unit assigned to node N2184is active while the processing units assigned to node N1182and node N3186are idle. During time T3, the processing unit assigned to node N3186is active while the processing units assigned to node N1182and node N2184are idle. The embodiments of this disclosure provide methods to reconstruct the DAG computation model180to minimize the idle time of the different processing units.

FIG.2Billustrates an example hierarchically splitting181of a DAG node183. In a first level of the hierarchy, node A183is split into sub-nodes A1185, A2187, . . . , Ak189. In a second level of the hierarchy, sub-node A2187is illustrated to be split into sub-nodes A2-1191, A2-2193, . . . , A2-L195. The splitting of a node can continue in further hierarchical layers, such as the third layer, fourth layer, fifth layer, and so on. Although, sub-node A2187is shown to be split into further sub-nodes, it should be appreciated that any number of sub-nodes of A, such as A1-Ak185-189, may be split into further hierarchical sub-nodes. The number of sub-nodes at each hierarchical split is non-limiting and can be any number appropriate associated with a corresponding sub-task within a DAG computation model in which the DAG node183is represented.

FIG.3is an example DAG computation model200including two nodes N1202and N2204, each having multiple sub-nodes. In the context of the DAG computation model200, Node 2204is dependent on Node 1202. As shown, Node N1202includes four (4) sub-nodes N1-1206, N1-2208, N1-3210, and N1-4212. Node N2204includes sixteen (16) sub-nodes N2-1214, N2-2216, . . . , N2-15242, and N2-16244. Although four (4) sub-nodes for node N1202and sixteen (16) sub-nodes for node204are illustrated, the number of sub-nodes may be application dependent and the quantity of sub-nodes in each node, as illustrated, are for simplicity of the discussion.

In one example, with respect to intra-node parallel processing, each sub-task of node N1202may be processed by a core of a CPU102and each sub-task of node N2204may be processed by a core of a GPU110. In another example, again with respect to intra-node parallel processing, each sub-task of node N1202may be processed by a core of a GPU110and each sub-task of node N2204may be processed by a core of a DSP114. In yet another example, with respect to intra-node parallel processing, each sub-task of node N1202may be processed by a core of an ISP118and each sub-task of node N2204may be processed by a core of a DPU130. In another example, with respect to intra-node parallel processing, some sub-tasks of node N1202may be processed by cores of a CPU102and some sub-tasks of node N1202may be processed by cores of a GPU110. In this example, some sub-tasks of node N2204may be processed by cores of a DSP114and other sub-tasks of node N2204may be processed by cores of an ISP118. It is noted that each sub-task may be operated by a different core of a particular type of processing unit and the particular processing unit may be selected to improve efficiency of the computation based on the available processing implemented in the dedicated hardware unit.

In an implementation of intra-node parallel processing, used to compute the DAG computation model200, at the completion of each sub-task within a node, the subsequent node of the DAG computation model200does not begin processing any sub-task within that subsequent node until all sub-tasks of the previous node have been completed. This is presented in the form of a dependency within each node on receiving a complete set of outputs from the previous node. As such, in an example where two different processing units are used to process the DAG computation model200, the first processing unit is actively processing node N1202while the second processing unit may be idle and waiting for the first processing unit to complete the computation. Similarly, the second processing unit is actively processing node N2204while the first processing unit remains idle.

FIG.4is a flowchart of an embodiment method250for splitting a DAG computation model and constructing multiple sub-DAG computation models for inter-node parallelism, as may be performed by a processing system100. A DAG computation model has a topological ordering in which each node is directed from an earlier node in a sequence of nodes. At step252, the processing system100, identifies the set of sequential and non-cyclical nodes within the DAG computation model.

At step254, the processing system100splits each identified node into non-interdependent sub-nodes based on a task type and a computational memory requirement corresponding to each sub-node and each node. The splitting of a node into sub-nodes may be uniform, non-uniform, or overlapping. In a uniform splitting of a node, each sub-node or sub-task may have an equal size, while in a non-uniform splitting of a node, each sub-node or sub-task may have a different or non-equal size. In an overlapping splitting of a node, some sub-tasks may overlap with one or more other sub-tasks or a sub-task may have intersections in the sub-task boundary with another sub-task.

As an example, with respect to image processing and uniform splitting of the node, an image may be sub-divided into equal and smaller N by M (N×M) segments. As an example, with respect to image processing and non-uniform splitting of the node, an image may be sub-divided into non-equal and smaller N by M (N×M) segments. As an example, with respect to image processing and overlapping splitting of the node, an image may be sub-divided into non-equal or equal but overlapping smaller N by M (N×M) segments.

At step256, the processing system100constructs multiple sub-DAG computation models using multiple non-interdependent sub-nodes from different nodes of the original DAG computation model. It should be understood that a sub-DAG computation model at a minimum has a non-interdependent sub-node from two different nodes but the variations of the construction of the multiple sub-DAG computation models may vary based on the computational task associated with the sub-nodes.

In some embodiments, each sub-DAG computation model can have a single non-interdependent sub-node from each node of the original DAG computation model. In some embodiments, each sub-DAG computation model can have a non-interdependent sub-node from some nodes of the original DAG computation model. In other embodiments, some sub-DAG computation models can have a non-interdependent sub-node from each node of the original DAG computation model while some sub-DAG computation models can have a non-interdependent sub-node from some nodes of the original DAG computation model.

The construction of the multiple sub-DAG computation models may be performed manually or performed automatically by a compiler. As an example of a manual construction, in a DAG computation model with less than 5 nodes, the construction of the multiple sub-DAG computation models can be performed by a pre-configured and static mapping table. The pre-configured and static mapping table may be used to map the original DAG computation model into multiple sub-DAG computation models.

As an example of an automated construction or compiler-aided construction, generally applicable to more complicated models with multiple DAG nodes, a compiler can be used to translate the original DAG computation model into multiple sub-DAG computation models dynamically and in run-time. In some embodiments, the translation from the original DAG computation model into multiple sub-DAG computation models may be pre-compiled using an OFFLINE compiler.

At step258, the processing system100allocates, using an intermediate shared memory (cache)136, memory for the multiple sub-DAG computations. The intermediate shared memory136may be used as a temporary storage location of an output of a sub-node computation to be used as an input of a subsequent sub-node of the same sub-DAG computation model. The intermediate shared memory acts as a buffer memory and reduces read and write times associated with an off-chip memory, such as an external double data rate (DDR) type memory or the L1, L2, etc. cache memory within a processing unit. In some embodiments, if there are no resource dependencies between the steps of splitting the DAG computation, step254, and allocating memory, step258, the steps may be performed at a same time. In some embodiments, if there are no resource dependencies between the steps of constructing the sub-DAG computation model, step256, and allocating memory, step258, the steps may be performed at a same time. In some embodiments, these steps may be done at different times.

At step260, the processing system100schedules, using for example a CPU102or104, the synchronization and dynamic tasks associated with each sub-DAG computation of the multiple sub-DAG computations. In some embodiments, a generated sub-DAG computation model may be different from another non-interdependent sub-DAG computation model. Initially resources are assigned for the multiple sub-DAG computation models at a high level, and subsequently, the processing system100schedules each sub-node within each sub-DAG computation at a lower level of processing associated with each sub-task.

In a DAG computation model, each node is constrained on the completion of the prior node. Similarly, each sub-node corresponding to a sub-DAG computation model is constrained on the completion of the prior sub-node. The scheduling provides an order in which each sub-task is to be performed within a sub-DAG computation model. In other words, the scheduling provides a topological sorting of the sub-tasks within a sub-DAG computation model.

The scheduling at step260may be an inter-node and/or an intra-node scheduling over one of the processing unit types. The topological sorting provides an efficient means for executing a set of tasks between and within each sub-DAG computation model based on the interdependencies of these tasks and shared resources. The result of the scheduling is that the total time period for processing the original DAG computation model is reduced, as less idle time is associated with different processing units in the processing system100.

At step262, the processing system100processes each of the multiple sub-DAG computations and compiles an associated output file. At the completion of the inter-node parallel processing of each multiple sub-DAG computation model, a final output is generated that is equal to the final output generated by the intra-node parallel processing of the original DAG computation model.

FIGS.5A-Dillustrate the construction of multiple sub-DAG computation models from a DAG computation model300using the embodiments of this disclosure, as may be performed by a processing system100, for example, in an image processing application. An example of an image processing application that can be modeled using a DAG computation model is image blurring, which has applications in video games, demos, or high dynamic range (HDR) rendering. In these applications, image blurring or bloom shading can be used to reproduce, for example, an image effect of real-world cameras.

The DAG computation model300ofFIG.5Aincludes three nodes: a first node (Node 1)302, a second node (Node 2)304, and a third node (Node 3)306. It is noted that additional nodes may also be contemplated. Each node is mapped to a particular computational task, for example, in an image processing application.

As an example, the first node302may correspond to acquiring an input image, the second node304may correspond to a transformation of the input image to an integral image, and the third node306may correspond to generating an output image from the integral image using, for example, Gaussian filtering.

In an embodiment, the output file may be an output data buffer. In another embodiment, the output file may be an output image buffer. In another embodiment, the output may be an output image file. And in some embodiments, the output file may be a set of output features of the DAG computation model. It should be appreciated that the specific arrangement of the particular nodes in the DAG computation model300is not the main topic of this disclosure and the DAG computation model300may be used as a generic DAG computation model for discussing the construction of a new DAG computation model in other applications.

InFIG.5B, each node of the DAG computation model300, can be sub-divided into multiple sub-tasks or sub-nodes. The first node302is sub-divided into sub-node 1-1308, sub-node 1-2310, sub-node 1-3312, and sub-node 1-4314. The second node304is sub-divided into sub-node 2-1316, sub-node 2-2318, sub-node 2-3320, and sub-node 2-4322. The third node306is sub-divided into sub-node 3-1324, sub-node 3-2326, sub-node 3-3328, and sub-node 3-4330.

The division of the sub-tasks within each task may be uniform, non-uniform, or overlapping. As an example, the division332of the sub-tasks associated with sub-node 1-3312and sub-node 1-4314can be a carry_on line type, the division334of the sub-tasks associated with the sub-node 2-3320, and sub-node 2-4322can have an overlapping area at the boundary. In some embodiments, a DAG computation model having two adjacent sub-blocks may have inter-dependencies within each other. As an example, the input to sub-node 2-4322may be the output of sub-node 2-3320. In these embodiments, each line in the intersection area can be a carry-on line, which is an indication of the location for a carry-on result for the computation of a neighboring sub-node. The overlap area may be an intersection area between two adjacent sub-blocks, and may be one-line or multiple-lines.

Each sub-task may map to a same or different computational sub-task associated with the particular computational task of the respective node. In an intra-parallel processing of the DAG computation model300, each sub-task can be scheduled for a different core of a same processing unit. In this type of processing, scheduling granularity is constrained within a single DAG node. As such, no parallelism is achieved between the DAG nodes or within inter-DAG nodes. This results in low hardware resource utilization, as a scheduling of a subsequent node cannot begin until the scheduling of a current is completed.

FIG.5Cillustrates an embodiment DAG computation model303including multiple sub-DAG computation models, as may be computed by the processing system100. The DAG computation model303is a modified version of the DAG computation model300. The DAG computation model303includes five (5) sub-DAG computation models352,354,356,358, and360. Although five (5) sub-DAG computation models are shown inFIG.5Cfor purposes of this discussion, the total number of sub-DAG computation models can be any number greater than one (1).

In the new arrangement, computation parallelism can be achieved using inter-node parallelism as well as inter-node and intra-node parallelism. In the new DAG computation model303arrangement of sub-nodes, multiple hardware resources (e.g., processing units) may be utilized to compute the new sub-DAG computation models in parallel. In an embodiment where each sub-DAG computation model is independent of the other sub-DAG computation model, the total processing time is reduced from T1+T2+T3 to the greater total time of (T1+T2) or (T2+T3).

Each sub-node within each sub-DAG computation model is arranged and constructed to have a more optimized dependency model within the sub-nodes of all the nodes. This is done to improve efficiency and decrease processing time of the DAG computation model300. Each sub-node is processed by a different core of a processing unit. However, the arrangement of the sub-nodes within the sub-DAG computation models allow for less idle time between processing of the sub-nodes in the newly constructed model. As before, each processing unit is assigned to a sub-node in accordance with the particular capabilities of the processing unit and the sub-task associated with the sub-node.

As shown, the first sub-DAG computation model352includes sub-node 2-1316depending on sub-node 1-1308. The second sub-DAG computation model354includes sub-node 2-2318depending on sub-node 1-2310in addition to sub-node 3-1324depending on sub-node 2-1316. The third sub-DAG computation model356includes sub-node 2-3320depending on sub-node 1-3312in addition to sub-node 3-2326depending on sub-node 2-2318. The fourth sub-DAG computation model358includes sub-node 2-4322depending on sub-node 1-4314in addition to sub-node 3-3328depending on sub-node 2-3320. Finally, the fifth sub-DAG computation model360includes sub-node 3-4330depending on sub-node 2-4330.

The output of the first sub-node of sub-DAG computation model352is an input for the second sub-node of sub-DAG computation model352. Similarly, dependencies may still exist from one sub-DAG computation model to another. However, the completion time of the sub-task associated with the first sub-DAG computation model352is less than the completion time of the whole task associated with the DAG computation model300. Other cores of a processing unit may be scheduled for execution of other sub-nodes in the same or in other sub-DAG computation models. Thus, the period of time where a processing unit remains idle and waiting for a completion of a task by another processing unit is decreased significantly.

FIG.5Dillustrates an example data flow in memory blocks of the processing system100corresponding to the transformation of the DAG computation model300inFIG.5Bto the DAG computation model303inFIG.5C. Each node of the DAG computation model300is divided into smaller sub-nodes or sub-tasks, which can be uniformly divided or non-uniformly divided. Each sub-block of the first node382, each sub-block of the second node384, and each sub-block of the third node386is then allocated a location in memory. In block394, each sub-block of each node is then queued in memory and the information related to queueing address, size, shape, order information, etc. are recorded. The splitter395and the scheduler397using the information stored in block394, generate a new queue for the new sub-DAG computation models. Block398illustrates an optional intermediate memory bank accessible from each of the processing units of the processing system100. The intermediate memory may be used to store output results within and between the sub-DAG computation models for use by other processing units.

FIGS.6A-Cillustrate the construction of multiple sub-DAG computation models from a DAG computation model450using the embodiments of this disclosure, as may be performed by a processing system100in, for example, a deep neural network (DNN) type of an application. Deep neural network is a type of machine learning that uses data representatives and typically includes multiple layers: an input layer, intermediate layers (i.e., hidden layers), and an output layer. Each layer or node has an associated function that may be different from any of the other layers, such as image convolution, pooling, normalization, feature map generation, etc.

In the deep neural network DAG computation model450, data flows from the input layer or the first node (Node 1)452to the output layer or third node (Node 3)456without looping back. The first node452and the second node454of the deep neural network DAG computation model450include a matrix input and a corresponding matrix weight. The output node456of the deep neural network DAG computation model450is a normalized exponential representation using, for example, a softmax function470. The deep neural network model has a first layer and a second layer, however additional nodes may also be contemplated.

The first node452includes a first matrix input462and a first matrix weight464. The second node454includes a second matrix input466and a second matrix weight468. In a typical deep neural network application, the input matrix and the weight matrix in each node is multiplied and a functional output representation between 0 and 1 is resulted. The deep neural network adjusts the weights and a respective output is evaluated until a particular pattern is recognized.

InFIG.6B, each input matrix462and466of each node452and454is sub-divided into four (4) sub-matrices. Although the input matrix in this example is sub-divided into four sub-matrices, in other examples the sub-divisions can be any number greater than one (1).

In a typical solution for solving a deep neural network in a DAG computation using intra-node parallelism, such as those found in CAFFE or TensorFlow, each computation task associated with a node is scheduled layer-by-layer. Within each layer, intra-node parallelism may be achieved by multiple cores of a particular processing unit of the processing system100. In intra-node parallel processing, the scheduling of the second node (input2×weight2) does not begin until the scheduling of the first node (input1×weight1) is complete. The completion of the first node corresponds to solving the first node (i.e., multiplying each input node with the weight in that node and completing a pattern recognition process).

FIG.6Cillustrates the modified DAG computation model455based on the sub-divided input matrices and corresponding weights. The DAG computation model455includes four (4) sub-DAG computation models510,520,530, and540. Although four (4) sub-DAG computation models are shown inFIG.6Cfor purposes of this discussion, the total number of sub-DAG computation models can be any number greater than one (1). In the new arrangement, computation parallelism can be achieved using inter-node parallelism as well as inter-node and intra-node parallelism. In the new DAG computation model455arrangement of sub-nodes, multiple hardware resources (e.g., processing units) may be utilized to compute the new sub-DAG computation models. Each sub-divided matrix corresponds to a sub-task within a node of the DAG computation model450. In this modified model, by splitting the original model into smaller sub-tasks and re-arranging the dependencies from within a task in the DAG computation model450to within the sub-tasks in each of the sub-DAG computation models, inter-node parallel processing can be achieved.

Each sub-node within each sub-DAG computation model is arranged and constructed to have a more optimized dependency model within the sub-nodes of all the nodes. This is done to improve efficiency and decrease processing time of the DAG computation model450. Each sub-node is processed by a different core of a processing unit. However, the arrangement of the sub-nodes within the sub-DAG computation models allow for less idle time between processing of the sub-nodes in the newly constructed model. As before, each processing unit is assigned to a sub-node in accordance with the particular capabilities of the processing unit and the sub-task associated with the sub-node.

As shown, the first sub-DAG computation model510includes sub-node 2-1504depending on sub-node 1-1502and sub-node 3-1506depending on sub-node 2-1504. The second sub-DAG computation model520includes sub-node 2-2514depending on sub-node 1-2512and sub-node 3-2516depending on sub-node 2-2514. The third sub-DAG computation model530includes sub-node 2-3524depending on sub-node 1-3522and sub-node 3-3526depending on sub-node 2-3524. And, the fourth sub-DAG computation model540includes sub-node 2-4534depending on sub-node 1-4532and sub-node 3-4536depending on sub-node 2-4534.

FIG.7illustrates an example DAG computation model550used in a computer vision type of an application. An example of a computer vision type of an application is OpenVX graph. OpenVX graph is an open and royalty free standard method for cross platform acceleration of computer vision applications. An OpenVX graph includes multiple steps for end-to-end image and/or video computation. Some examples of these individual steps are color conversion, channel extraction, image pyramid, optical flow, etc.

Each step of the computer vision type of an application, such as OpenVX graph, can be represented by a DAG node. The DAG computation model550is an example of an OpenVX graph. The DAG computation model550includes a color conversion node552, a channel extract node554, an image pyramid node556, a Pyramid node558, an optical flow node560, a Harris corners node562, and a keypoints node564. The understanding of the specific function of each node is not necessary to understanding the conversion of the DAG computation model550from a model arranged for intra-node parallel processing to a model that allows for inter-node parallel processing. The illustration is used to show that in a typical computer vision application, the computational tasks (e.g., YUV frame or Gray frame generation) may be arranged in a DAG computational model.

The embodiments of this disclosure provide methods to split each node of the DAG computation model550into multiple sub-tasks. Each sub-task may then be re-arranged, similar to the methods previously discussed in image processing, with sub-tasks or sub-nodes of other nodes of the DAG computation model550as illustrated, for example, inFIGS.5A-C. The new sub-DAG computation models allow for inter-node processing between and within each node. As a result, the new DAG computation models allow for faster processing time and with less idle processing time of other processing units.

It should be noted that the examples mentioned-above, with respect to image processing, deep neural network, and video processing, are non-limiting examples and the corresponding discussions for splitting of an original DAG computation model and constructing new sub-DAG computation models can apply to any application that can be formed using a DAG computation model.

FIG.8illustrates an embodiment DAG computation model600and a corresponding constructed embodiment DAG computation model620having a one-to-many mapping graph model, as may be computed by the processing system100. In a general application, for example in image processing, video processing, or in deep neural network processing, each sub-DAG of a corresponding DAG computation model may have 2 or more sub-nodes. In this arrangement, one or more sub-nodes may depend on the input of multiple sub-nodes. And, one or more sub-nodes may provide an input for multiple sub-nodes.

The DAG computation model600is illustrated as having three nodes: Node 1602, Node 2604, and Node 3606. It should be appreciated that a DAG computation model with greater number of nodes may also be contemplated. However, for simplicity of the discussion, three nodes are shown.

The DAG computation model620illustrates a splitting of each node in the DAG computation model600into multiple sub-nodes and construction of multiple sub-DAG computation models. Node 1602is split to sub-node 1-1632, sub-node 1-2634, sub-node 1-3636, and sub-node 1-4638. Node 2604is split to sub-node 2-1640, sub-node 2-2642, sub-node 2-3644, and sub-node 2-4646. Node 3606is split to sub-node 3-1648, sub-node 3-2650, sub-node 3-3652, and sub-node 3-4654.

The construction of the DAG computation model620and the dependency of one or more sub-nodes are illustrated as an example arrangement corresponding to a one-to-many mapping graph model inFIG.8. As shown, sub-node 2-1640depends on sub-node 1-1632. Sub-node 2-2642depends on inputs from sub-node 1-2634and sub-node 2-1640. Sub-node 3-1648depends on sub-node 2-1640. Sub-node 2-3644depends on sub-node 1-3636. Sub-node 3-2650depends on inputs from both sub-node 1-3636and sub-node 2-2642. Sub-nodes 2-4646and sub-node 3-3652each depend on inputs from both sub-node 1-4638and sub-node 2-3644. Sub-node 3-4654depends on sub-node 2-4646. Although the example ofFIG.8is shown to have a variety of dependencies for each sub-node, it should be appreciated that in some embodiments the arrangement of the dependency may vary. As an example, some sub-nodes that have a single input as a dependency may have multiple dependencies. In some embodiments, the scheduling of each sub-node of the DAG computation model600may be performed by the CPU102,106, the GPU110, or the DSP114processing units of the processing system100.

FIG.9is diagram of a network700for communicating data. The network700includes a base station710having a coverage area701, a plurality of UEs720, and a backhaul network730. As shown, the base station710establishes uplink (dashed line) and/or downlink (dotted line) connections with the UEs720, which serve to carry data from the UEs720to the base station710and vice-versa. Data communicated over the uplink/downlink connections may include data communicated between the UEs720, as well as data communicated to/from a remote-end (not shown) by way of the backhaul network730. As used herein, the term “base station” refers to any network-side device configured to provide wireless access to a network, such as an enhanced Node B (eNodeB or eNB), agNB, a transmit/receive point (TRP), a macro-cell, a femtocell, a Wi-Fi Access Point (AP), and other wirelessly enabled devices. Base stations may provide wireless access in accordance with one or more wireless communication protocols, e.g., 5th generation new radio (5G NR), LTE, LTE advanced (LTE-A), High Speed Message Access (HSPA), Wi-Fi 802.11a/b/g/n/ac, etc. As used herein, the term “UE” refers to any user-side device configured to access a network by establishing a wireless connection with a base station, such as a mobile device, a mobile station (STA), a vehicle, and other wirelessly enabled devices. In some embodiments, the network700may include various other wireless devices, such as relays, low power nodes, etc. While it is understood that communication systems may employ multiple access nodes capable of communicating with a number of UEs, only one base station710, and two UEs720are illustrated for simplicity.

FIG.10illustrates a block diagram of another embodiment processing system800for performing methods described herein, which may be installed in a host device. As shown, the processing system800includes a processor802, a memory804, and interfaces806,808,810which may (or may not) be arranged as shown inFIG.10. The processor802may be any component or collection of components adapted to perform computations and/or other processing related tasks, and the memory804may be any component or collection of components adapted to store programming and/or instructions and associated data for execution by the processor802. In an embodiment, the memory804includes a non-transitory computer readable medium. The interfaces806,808,810may be any component or collection of components that allow the processing system800to communicate with other devices/components and/or a user. In an embodiment, one or more of the interfaces806,808,810may be adapted to communicate data, control, or management messages from the processor802to applications installed on the host device and/or a remote device. As another embodiment, one or more of the interfaces806,808,810may be adapted to allow a user or user device (e.g., personal computer (PC), etc.) to interact/communicate with the processing system800. The processing system800may include additional components not depicted inFIG.10, such as long-term storage (e.g., non-volatile memory, etc.).

In some embodiments, the processing system800is included in a network device that is accessing, or part otherwise of, a telecommunications network. In one embodiment, the processing system800is in a network-side device in a wireless or wireline telecommunications network, such as a base station, a relay station, a scheduler, a controller, a gateway, a router, an applications server, or any other device in the telecommunications network. In other embodiments, the processing system800is in a user-side device accessing a wireless or wireline telecommunications network, such as a mobile station, a user equipment (UE), a personal computer (PC), a tablet, a wearable communications device (e.g., a smartwatch, etc.), a wireless capable vehicle, a wireless capable pedestrian, a wireless capable infrastructure element or any other device adapted to access a telecommunications network.

In some embodiments, one or more of the interfaces806,808,810connects the processing system800to a transceiver adapted to transmit and receive signaling over the telecommunications network.FIG.11illustrates a block diagram of a transceiver900adapted to transmit and receive signaling over a telecommunications network. The transceiver900may be installed in a host device. As shown, the transceiver900comprises a network-side interface902, a coupler904, a transmitter906, a receiver908, a signal processor910, and a device-side interface912. The network-side interface902may include any component or collection of components adapted to transmit or receive signaling over a wireless or wireline telecommunications network. The coupler904may include any component or collection of components adapted to facilitate bi-directional communication over the network-side interface902. The transmitter906may include any component or collection of components (e.g., up-converter, power amplifier, etc.) adapted to convert a baseband signal into a modulated carrier signal suitable for transmission over the network-side interface902. The receiver908may include any component or collection of components (e.g., down-converter, low noise amplifier, etc.) adapted to convert a carrier signal received over the network-side interface902into a baseband signal. The signal processor910may include any component or collection of components adapted to convert a baseband signal into a data signal suitable for communication over the device-side interface(s)912, or vice-versa. The device-side interface(s)912may include any component or collection of components adapted to communicate data-signals between the signal processor910and components within the host device (e.g., the processing system1300, local area network (LAN) ports, etc.).

The transceiver900may transmit and receive signaling over any type of communications medium. In some embodiments, the transceiver900transmits and receives signaling over a wireless medium. In some embodiments, the transceiver900may be a wireless transceiver adapted to communicate in accordance with a wireless telecommunications protocol, such as a cellular protocol (e.g., long-term evolution (LTE), etc.), a wireless local area network (WLAN) protocol (e.g., Wi-Fi, etc.), or any other type of wireless protocol (e.g., Bluetooth, near field communication (NFC), etc.). In such embodiments, the network-side interface902comprises one or more antenna/radiating elements. In some embodiments, the network-side interface902may include a single antenna, multiple separate antennas, or a multi-antenna array configured for multi-layer communication, e.g., single input multiple output (SIMO), multiple input single output (MISO), multiple input multiple output (MIMO), etc. In other embodiments, the transceiver900transmits and receives signaling over a wireline medium, e.g., twisted-pair cable, coaxial cable, optical fiber, etc. Specific processing systems and/or transceivers may utilize all of the components shown, or only a subset of the components, and levels of integration may vary from device to device.

Although the description has been described in detail, it should be understood that various changes, substitutions and alterations may be made without departing from the spirit and scope of this disclosure as defined by the appended claims. The same elements are designated with the same reference numbers in the various figures. Moreover, the scope of the disclosure is not intended to be limited to the particular embodiments described herein, as one of ordinary skill in the art will readily appreciate from this disclosure that processes, machines, manufacture, compositions of matter, means, methods, or steps, presently existing or later to be developed, may perform substantially the same function or achieve substantially the same result as the corresponding embodiments described herein. Accordingly, the appended claims are intended to include within their scope such processes, machines, manufacture, compositions of matter, means, methods, or steps. The specification and drawings are, accordingly, to be regarded simply as an illustration of the disclosure as defined by the appended claims, and are contemplated to cover any and all modifications, variations, combinations or equivalents that fall within the scope of the present disclosure.