# US 2019/0317804 A1 · Method, apparatus and system for multi-module scheduling

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

- Number: US 2019/0317804 A1
- Document ID: US20190317804A1
- Status: Published application
- Kind: A1
- Application number: 16/275,984
- Filed: 2019-02-14
- Published: 2019-10-17
- Earliest claimed: 2017-12-14
- Assignees: Tusimple, Inc.
- Applicants: TuSimple
- Inventors: Yifan GONG; Zehua HUANG; Jiangming JIN; Dinghua LI; Siyuan LIU; Wei LIU; Lei SU; YiXin YANG
- Web page: https://patentgrep.com/patent/US20190317804A1

## CPC

- G06F 9/4881: {Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues}
- G06F 9/547: {Remote procedure calls [RPC]; Web services}
- G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

The present disclosure provides a method, an apparatus and a system for multi-module scheduling, capable of solving at least one of the problems associated with the multi-module scheduling technique in the related art, i.e., inconsistency in data inputted to a computing module, and a significant delay or low throughput in data transmission between computing modules. The method includes: reading, by a master process, a pre-stored configuration file storing a directed computation graph; initializing, by the master process, states of the nodes and connecting edges in a current computing period; determining a node to be called based on the computation direction of the directed computation graph and the states of the nodes, the node to be called comprising a node having all of its input edges in a complete state; transmitting, to the computing module in the slave process corresponding to the node to be called, a call request of Remote Process Call (RPC) to execute the computing module; updating the state of the node and the state of each output edge of the node upon receiving a response to the call request; and proceeding with a next computing period after determining that the states of all the nodes in the directed computation graph have been updated.

## Claims

### Claim 1

A method for multi-module scheduling, comprising:
reading, by a master process, a pre-stored configuration file storing a directed computation graph associated with a computing task, the computing task comprising a plurality of slave processes each comprising a plurality of computing modules grouped in accordance with a computation direction, the directed computation graph comprising a plurality of nodes each corresponding to one computing module in one slave process, at least two of the nodes having a connecting edge therebetween, an incoming connecting edge of a node being an input edge and an outgoing connecting edge of a node being an output edge;
initializing, by the master process, states of the nodes and connecting edges in a current computing period;
determining a node to be called based on the computation direction of the directed computation graph and the states of the nodes, the node to be called comprising a node having all of its input edges in a complete state;
transmitting, to the computing module in the slave process corresponding to the node to be called, a call request of Remote Process Call (RPC) to execute the computing module;
updating the state of the node and the state of each output edge of the node upon receiving a response to the call request; and
proceeding with a next computing period after determining that the states of all the nodes in the directed computation graph have been updated.

### Claim 2 (depends on 1)

The method of claim 1, wherein the master process comprises a master thread and a thread pool comprising a plurality of slave threads,
the state of each node comprises unready, ready, run or done, and
the state of each connecting edge comprises uncomplete or complete.

### Claim 3 (depends on 2)

The method of claim 2, wherein the computing modules in each slave process comprise parallel computing modules and serial computing modules, and
the master process initializing the states of the nodes and connecting edges comprises:
determining, by the master thread, whether there is any free storage space in a control queue based on a predetermined time interval, and if so, storing, by the master thread, one directed computation graph in one free storage space in the control queue, or otherwise setting, by the master thread, a state of the master thread to wait;
creating, when more than one directed computation graph is stored in the control queue, an output edge from a node corresponding to each serial computing module in the directed computation graph in the (i−1)-th storage space to the same node in the directed computation graph in the i-th storage space in accordance with a direction of the queue, where 2≤i≤n and n is a number of storage spaces in the control queue and is a natural number; and
initializing the states of the nodes and connecting edges in the directed computation graph that is newly stored in the control queue.

### Claim 4 (depends on 3)

The method of claim 3, wherein said initializing the states of the nodes and connecting edges in the directed computation graph that is newly stored in the control queue comprises:
determining, by the master thread, whether the directed computation graph that is newly stored is the first directed computation graph in the control queue, and
if so, setting a starting node of the directed computation graph to ready and the states of all the other nodes in the directed computation graph to unready; and setting all the connecting edges in the directed computation graph to uncomplete, or
otherwise, for a connecting edge from a node in a previous directed computation graph adjacent to the directed computation graph to the same node in the directed computation graph, setting the state of the connecting edge to complete when the state of the node in the previous directed computation graph is done, or otherwise setting the state of the connecting edge to uncomplete; setting each node in the directed computation graph having all its input edges in the complete state to ready and the states of all the other nodes to unready; and setting all the connecting edges in the directed computation graph to uncomplete.

### Claim 5 (depends on 3)

The method of claim 3, wherein said determining the node to be called based on the computation direction of the directed computation graph and the states of the nodes comprises:
traversing, by the master thread after initializing the states of the nodes and connecting edges in the directed computation graph that is newly stored in the control queue, the states of the respective nodes in each directed computation graph in the control queue in accordance with the computation direction, determining each node in the ready state as a node to be called, the node in the ready state comprising the node having all of its input edges in the complete state, modifying the state of each node to be called into run, pushing each node to be called into a computing queue and entering the wait state; or
traversing, by one slave thread in the thread pool in computation, the states of the respective nodes in each directed computation graph in the control queue in accordance with the computation direction, determining each node in the ready state as a node to be called, the node in the ready state comprising the node having all of its input edges in the complete state, modifying the state of each node to be called into run, and pushing each node to be called into a computing queue.

### Claim 6 (depends on 5)

The method of claim 5, wherein said transmitting, to the computing module in the slave process corresponding to the node to be called, the call request of RPC to execute the computing module comprises:
taking, by one slave thread in the thread pool, one node from the computing queue and transmitting the call request of RPC to the computing module in the slave process corresponding to the one node.

### Claim 7 (depends on 6)

The method of claim 6, further comprising:
determining, by one slave thread in the thread pool, an identifier of the computing module corresponding to the one node taken from the computing queue and a storage address of input data to the computing module and/or a storage address of output data from the computing module in accordance with the pre-stored configuration file, and including the identifier of the computing module, the storage address of the input data and/or the storage address of the output data in the call request.

### Claim 8 (depends on 7)

The method of claim 7, wherein the storage address of the output data from the computing module is an address corresponding to the computing module in a shared storage space corresponding to the slave process in which the computing module is comprised, or the storage address of the output data is an address corresponding to the computing module in a shared storage space corresponding to another slave process, and
the storage address of the input data to the computing module is an address in the shared storage space corresponding to the slave process in which the computing module is comprised.

### Claim 9 (depends on 2)

The method of claim 2, wherein said updating the state of the node and the state of each output edge of the node upon receiving the response to the call request comprises:
setting, by one slave thread in the thread pool upon receiving the response to the call request transmitted for one node, the state of the node to done, modifying the state of each output edge of the node into complete, and setting the state of each node having all its input edges in the complete state to ready.

### Claim 10 (depends on 3)

The method of claim 3, wherein said proceeding with the next computing period after determining that the states of all the nodes in the directed computation graph have been updated comprises:
traversing, by one slave thread in the thread pool, the states of the respective nodes in the directed computation graph at a head of the control queue, and when determining that the states of all the nodes in the directed computation graph are done, releasing a storage space at the head of the control queue and notifying the master thread in the wait state to proceed with the next computing period.

### Claim 11

A method for multi-module scheduling, comprising:
receiving, by a computing module in a slave process in a current computing period, a call request of Remote Process Call (RPC) from a master process, wherein the slave process comprises a plurality of computing modules grouped in accordance with a computation direction, and wherein for the computing module having a plurality of pieces of input data, the call request is transmitted by the master process when determining that all of the plurality of pieces of input data to the computing module are ready;
performing, by the computing module, processing in response to the call request; and
feeding, by the computing module, a response back to the master process when the processing has completed.

### Claim 12 (depends on 11)

The method of claim 11, wherein the received call request includes an identifier of the computer module, a storage address of input data to the computing module and/or a storage address of output data from the computing module, and
said the computing module performing processing in response to the call request comprises:
reading, by the computing module in response to the call request, the input data from the storage address of the input data for processing, and writing the output data into the storage address of the output data.

### Claim 13 (depends on 12)

The method of claim 12, wherein the storage address of the output data is an address corresponding to the computing module in a shared storage space corresponding to the slave process, or
the storage address of the output data is an address corresponding to the computing module in a shared storage space corresponding to another slave process.

### Claim 14 (depends on 12)

The method of claim 12, wherein the storage address of the input data is an address in a shared storage space corresponding to the slave process.

### Claim 15 (depends on 11)

The method of claim 11, wherein the computing module is a service function.

### Claim at position 16

16-26. (canceled)

### Claim 27

An apparatus for multi-module scheduling, comprising a processor and at least one memory storing at least one machine executable instruction, the processor being operative to execute the at least one machine executable instruction to:
read a pre-stored configuration file storing a directed computation graph associated with a computing task, the computing task comprising a plurality of slave processes each comprising a plurality of computing modules grouped in accordance with a computation direction, the directed computation graph comprising a plurality of nodes each corresponding to one computing module in one slave process, at least two of the nodes having a connecting edge therebetween, an incoming connecting edge of a node being an input edge and an outgoing connecting edge of a node being an output edge;
initialize, by a master process, states of the nodes and connecting edges in a current computing period;
determine a node to be called based on the computation direction of the directed computation graph and the states of the nodes, the node to be called comprising a node having all of its input edges in a complete state;
transmit, to the computing module in the slave process corresponding to the node to be called, a call request of Remote Process Call (RPC) to execute the computing module;
update the state of the node and the state of each output edge of the node upon receiving a response to the call request; and
proceed with a next computing period after determining that the states of all the nodes in the directed computation graph have been updated.

### Claim 28 (depends on 27)

The apparatus of claim 27, wherein the processor is operative to execute the at least one machine executable instruction to provide a master thread and a thread pool comprising a plurality of slave threads,
the state of each node comprises unready, ready, run or done, and
the state of each connecting edge comprises uncomplete or complete.

### Claim 29 (depends on 28)

The apparatus of claim 28, wherein the computing modules in each slave process comprise parallel computing modules and serial computing modules, and
the processor being operative to execute the at least one machine executable instruction to initialize, by the master process, the states of the nodes and connecting edges comprises the master thread being configured to:
determine whether there is any free storage space in a control queue based on a predetermined time interval, and if so, store one directed computation graph in one free storage space in the control queue, or otherwise set a state of the master thread to wait;
create, when more than one directed computation graph is stored in the control queue, an output edge from a node corresponding to each serial computing module in the directed computation graph in the (i−1)-th storage space to the same node in the directed computation graph in the i-th storage space in accordance with a direction of the queue, where 2≤i≤n and n is a number of storage spaces in the control queue and is a natural number; and
initialize the states of the nodes and connecting edges in the directed computation graph that is newly stored in the control queue.

### Claim 30 (depends on 29)

The apparatus of claim 29, wherein the processor being operative to execute the at least one machine executable instruction to initialize the states of the nodes and connecting edges in the directed computation graph that is newly stored in the control queue comprises the master thread being configured to:
determine whether the directed computation graph that is newly stored is the first directed computation graph in the control queue, and
if so, set a starting node of the directed computation graph to ready and the states of all the other nodes in the directed computation graph to unready; and set all the connecting edges in the directed computation graph to uncomplete, or
otherwise, for a connecting edge from a node in a previous directed computation graph adjacent to the directed computation graph to the same node in the directed computation graph, set the state of the connecting edge to complete when the state of the node in the previous directed computation graph is done, or otherwise set the state of the connecting edge to uncomplete; set each node in the directed computation graph having all its input edges in the complete state to ready and the states of all the other nodes to unready; and set all the connecting edges in the directed computation graph to uncomplete.

### Claim 31 (depends on 28)

The apparatus of claim 28, wherein the processor being operative to execute the at least one machine executable instruction to determine the node to be called based on the computation direction of the directed computation graph and the states of the nodes comprises:
the master thread being configured to traverse, after initializing the states of the nodes and connecting edges in the directed computation graph that is newly stored in the control queue, the states of the respective nodes in each directed computation graph in the control queue in accordance with the computation direction, determine each node in the ready state as a node to be called, the node in the ready state comprising the node having all of its input edges in the complete state, modify the state of each node to be called into run, push each node to be called into a computing queue and enter the wait state; or
one slave thread in the thread pool being configured to traverse, in computation, the states of the respective nodes in each directed computation graph in the control queue in accordance with the computation direction, determine each node in the ready state as a node to be called, the node in the ready state comprising the node having all of its input edges in the complete state, modify the state of each node to be called into run, and push each node to be called into a computing queue.

### Claim 32 (depends on 31)

The apparatus of claim 31, wherein the processor being operative to execute the at least one machine executable instruction to transmit, to the computing module in the slave process corresponding to the node to be called, the call request of RPC to execute the computing module comprises one slave thread in the thread pool being configured to:
take one node from the computing queue and transmit the call request of RPC to the computing module in the slave process corresponding to the one node.

### Claim 33 (depends on 32)

The apparatus of claim 32, wherein the processor is further operative to execute the at least one machine executable instruction to:
determine an identifier of the computing module corresponding to the one node taken from the computing queue and a storage address of input data to the computing module and/or a storage address of output data from the computing module in accordance with the pre-stored configuration file, and include the identifier of the computing module, the storage address of the input data and/or the storage address of the output data in the call request,
wherein the storage address of the output data from the computing module is an address corresponding to the computing module in a shared storage space corresponding to the slave process in which the computing module is comprised, or the storage address of the output data is an address corresponding to the computing module in a shared storage space corresponding to another slave process, and
the storage address of the input data to the computing module is an address in the shared storage space corresponding to the slave process in which the computing module is comprised.

### Claim 34 (depends on 28)

The apparatus of claim 28, wherein the processor being operative to execute the at least one machine executable instruction to update the state of the node and the state of each output edge of the node upon receiving the response to the call request comprises one slave thread in the thread pool being configured to:
set, upon receiving the response to the call request transmitted for one node, the state of the node to done, modify the state of each output edge of the node into complete, and set the state of each node having all its input edges in the complete state to ready.

### Claim 35 (depends on 28)

The apparatus of claim 28, wherein the processor being operative to execute the at least one machine executable instruction to proceed with the next computing period after determining that the states of all the nodes in the directed computation graph have been updated comprises one slave thread in the thread pool being configured to:
traverse the states of the respective nodes in the directed computation graph at a head of the control queue, and when determining that the states of all the nodes in the directed computation graph are done, release a storage space at the head of the control queue and notify the master thread in the wait state to proceed with the next computing period.

### Claim 36

An apparatus for multi-module scheduling, comprising a processor and at least one memory storing at least one machine executable instruction, the processor being operative to execute the at least one machine executable instruction to:
receive, in a current computing period, a call request of Remote Process Call (RPC) from a master process, wherein for the apparatus for multi-module scheduling having a plurality of pieces of input data, the call request is transmitted by the master process when determining that all of the plurality of pieces of input data to the apparatus for multi-module scheduling are ready;
perform processing in response to the call request; and
feed a response back to the master process when the processing has completed.

### Claim 37 (depends on 36)

The apparatus of claim 36, wherein the processor is further operative to execute the at least one machine executable instruction such that the received call request includes an identifier of the computer module, a storage address of input data to the computing module and/or a storage address of output data from the computing module, the storage address of the output data being an address corresponding to the computing module in a shared storage space corresponding to the slave process or being an address corresponding to the computing module in a shared storage space corresponding to another slave process, and the storage address of the input data being an address in the shared storage space corresponding to the slave process, and
the processor being operative to execute the at least one machine executable instruction to perform processing in response to the call request comprises the processor being operative to execute the at least one machine executable instruction to:
read, in response to the call request, the input data from the storage address of the input data for processing, and write the output data into the storage address of the output data.

### Claim 38

A system for multi-module scheduling, comprising a master process and a plurality of slave processes each comprising a plurality of computing modules grouped in accordance with a computation direction, wherein
the master process is configured to read a pre-stored configuration file storing a directed computation graph associated with a computing task, the computing task comprising a plurality of slave processes each comprising a plurality of computing modules grouped in accordance with a computation direction, the directed computation graph comprising a plurality of nodes each corresponding to one computing module in one slave process, at least two of the nodes having a connecting edge therebetween, an incoming connecting edge of a node being an input edge and an outgoing connecting edge of a node being an output edge; initialize states of the nodes and connecting edges in a current computing period; determine a node to be called based on the computation direction of the directed computation graph and the states of the nodes, the node to be called comprising a node having all of its input edges in a complete state; transmit, to the computing module in the slave process corresponding to the node to be called, a call request of Remote Process Call (RPC) to execute the computing module; update the state of the node and the state of each output edge of the node upon receiving a response to the call request; and proceed with a next computing period after determining that the states of all the nodes in the directed computation graph have been updated, and
one computing module in the slave process is configured to receive the call request of RPC from the master process, perform processing in response to the call request; and feed a response back to the master process when the processing has completed.
