# US 11,405,312 B2 · Directed acyclic graph template for data pipeline

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 11,405,312 B2
- Document ID: US11405312B2
- Status: Granted
- Kind: B2
- Application number: 17/014,918
- Filed: 2020-09-08
- Published: 2022-03-10
- Granted: 2022-08-02
- Earliest claimed: 2020-09-08
- Assignees: Megh Computing, Inc.
- Applicants: Megh Computing, Inc.
- Inventors: Suchit Subhaschandra; Jonathan Beare; Duncan Moss
- Web page: https://patentgrep.com/patent/US11405312B2

## CPC

- H04L 69/22: Parsing or analysis of headers
- G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)}
- H04L 45/02: Topology update or discovery
- H04L 45/54: {Organization of routing tables}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A computing system is provided, including a processor configured to receive a directed acyclic graph (DAG) template specifying a data pipeline of a plurality of processing stages. For each processing stage, the processor may be further configured to select a respective processing device of a plurality of communicatively linked processing devices. The processor may be further configured to determine a routing sequence between the plurality of processing devices according to the DAG template. The processor may be further configured to transmit a plurality of input packets encoding the plurality of processing stages to the respective processing devices selected for the processing stages as specified by the routing sequence. In response to transmitting the plurality of input packets, the processor may be further configured to receive, from a processing device of the plurality of processing devices, one or more output packets encoding a processing result of the data pipeline.

## Claims

### Claim 1

A computing system comprising:
a processor configured to:
receive a directed acyclic graph (DAG) template specifying a data pipeline of a plurality of processing stages, wherein the DAG template is received from a program via a DAG application program interface (API) included in a DAG runtime environment;
for each processing stage of the plurality of processing stages, select a respective processing device of a plurality of communicatively linked processing devices;
determine a routing sequence between the plurality of processing devices according to the DAG template;
transmit one or more input packets encoding the plurality of processing stages to the respective processing devices selected for the processing stages as specified by the routing sequence; and
in response to transmitting the one or more input packets, receive, from a processing device of the plurality of processing devices, one or more output packets encoding a processing result of the data pipeline, wherein:
the processor is communicatively linked to a host processor of a host server device;
the host processor is configured to, at a processing device shell of a plurality of processing device shells:
receive an intermediate packet from a first processing device of the plurality of processing devices; and
convey the intermediate packet to a second processing device of the plurality of processing devices; and
the second processing device is specified by an intermediate packet header of the intermediate packet.

### Claim 2 (depends on 1)

The computing system of claim 1, wherein the DAG runtime environment further includes:
a resource manager at which the processor is configured to determine the routing sequence; and
a router via which the processor is configured to route the one or more input packets and the one or more output packets between the resource manager and the plurality of processing device shells.

### Claim 3 (depends on 2)

The computing system of claim 2, wherein:
the DAG runtime environment further includes a routing table indicating a plurality of communicative links between the plurality of processing device shells; and
the processor is further configured to, at the resource manager, determine the routing sequence based at least in part on the communicative links indicated in the routing table.

### Claim 4 (depends on 1)

The computing system of claim 1, wherein the processor is further configured to:
receive a respective processing capacity indication from each processing device for the plurality of processing devices; and
select the respective processing devices of the plurality of processing stages based at least in part on the processing capacity indications of the processing devices.

### Claim 5 (depends on 4)

The computing system of claim 4, wherein:
the DAG template further includes respective quality-of-service criteria for the plurality of processing stages; and
the processor is further configured to select the respective processing devices for the plurality of processing stages based at least in part on a determination that the processing devices satisfy the quality-of-service criteria as indicated by the processing capacity indications of the processing devices.

### Claim 6 (depends on 1)

The computing system of claim 1, wherein each processing device of the plurality of processing devices is configured to execute one or more predetermined processing functions specified by a device library of that processing device.

### Claim 7 (depends on 6)

The computing system of claim 6, wherein the one or more input packets are transmitted to the plurality of processing devices via a hardware abstraction layer over which the respective plurality of device libraries of the plurality of processing devices are multiplexed.

### Claim 8 (depends on 1)

The computing system of claim 1, wherein each processing device is a central processing unit (CPU), a graphical processing unit (GPU), an application-specific integrated circuit (ASIC), or a field-programmable gate array (FPGA).

### Claim 9

A method for use with a computing system, the method comprising:
receiving a directed acyclic graph (DAG) template specifying a data pipeline of a plurality of processing stages, wherein the DAG template is received from a program via a DAG application program interface (API) included in a DAG runtime environment;
for each processing stage of the plurality of processing stages, selecting a respective processing device of a plurality of communicatively linked processing devices;
determining a routing sequence between the plurality of processing devices according to the DAG template;
transmitting one or more input packets encoding the plurality of processing stages to the respective processing devices selected for the processing stages as specified by the routing sequence;
in response to transmitting the one or more input packets, receiving, from a processing device of the plurality of processing devices, one or more output packets encoding a processing result of the data pipeline; and
executing a processing device shell of a plurality of processing device shells at a host server device, wherein executing the processing device shell includes:
receiving an intermediate packet from a first processing device of the plurality of processing devices; and
conveying the intermediate packet to a second processing device of the plurality of processing devices, wherein the second processing device is specified by an intermediate packet header of the intermediate packet.

### Claim 10 (depends on 9)

The method of claim 9, further comprising:
determining the routing sequence at a resource manager included in the DAG runtime environment; and
at a router included in the DAG runtime environment, routing the one or more input packets and the one or more output packets between the resource manager and the plurality of processing device shells.

### Claim 11 (depends on 9)

The method of claim 9, further comprising:
receiving a respective processing capacity indication from each processing device of the plurality of processing devices; and
selecting the respective processing devices for the plurality of processing stages based at least in part on the processing capacity indications of the processing devices.

### Claim 12 (depends on 11)

The method of claim 11, wherein:
the DAG template further includes respective quality-of-service criteria for the plurality of processing stages; and
the respective processing devices for the plurality of processing stages are selected based at least in part on a determination that the processing devices satisfy the quality-of-service criteria as indicated by the processing capacity indications of the processing devices.

### Claim 13 (depends on 9)

The method of claim 9, further comprising:
at each processing device of the plurality of processing devices, executing one or more predetermined processing functions specified by a device library of that processing device; and
transmitting the one or more input packets to the plurality of processing devices via a hardware abstraction layer over which the respective plurality of device libraries of the plurality of processing devices are multiplexed.

### Claim 14

A computing system comprising:
a plurality of processing devices, wherein each processing device is a central processing unit (CPU), a graphical processing unit (GPU), an application-specific integrated circuit (ASIC), or a field-programmable gate array (FPGA);
a processor configured to:
receive a directed acyclic graph (DAG) template specifying a data pipeline of a plurality of processing stages, wherein the DAG template is received from a program via a DAG application program interface (API) included in a DAG runtime environment;
for each processing stage of the plurality of processing stages, select a respective processing device of the plurality of processing devices;
determine a routing sequence between the plurality of processing devices according to the DAG template; and
execute the plurality of processing stages at the respective processing devices selected for those processing stages in an order specified by the routing sequence, wherein:
executing the plurality of processing stages includes, at a processing device shell of a plurality of processing device shells:
receiving an intermediate packet from a first processing device of the plurality of processing devices; and
conveying the intermediate packet to a second processing device of the plurality of processing devices; and
the second processing device is specified by an intermediate packet header of the intermediate packet.