# US 11,113,103 B2 · Task parallel processing method, apparatus and system, storage medium and computer device > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,113,103 B2 - Document ID: US11113103B2 - Status: Granted - Kind: B2 - Application number: 16/702,502 - Filed: 2019-12-03 - Published: 2020-04-23 - Granted: 2021-09-07 - Earliest claimed: 2017-11-20 - Assignees: Shanghai Cambricon Information Technology Co., Ltd. - Applicants: Shanghai Cambricon Information Technology Co., Ltd - Inventors: Yongwei Zhao; Xiaofu Meng - Web page: https://patentgrep.com/patent/US11113103B2 ## CPC - G06F 9/4881: {Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues} - G06F 9/38: Concurrent instruction execution, e.g. pipeline or look ahead - G06F 9/4856: {resumption being on a different machine, e.g. task migration, virtual machine migration (G06F9/5088 takes precedence)} - G06F 9/5038: {considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration (scheduling strategies G06F9/4881 and subgroups)} - G06F 9/54: Interprogram communication - G06F 9/547: {Remote procedure calls [RPC]; Web services} - G06N 3/04: Architecture, e.g. interconnection topology - G06N 3/045: Combinations of networks - G06N 3/0464: Convolutional networks [CNN, ConvNet] - G06N 3/063: using electronic means - G06N 3/08: Learning methods - G06N 3/10: Interfaces, programming languages or software development kits, e.g. for simulating neural networks - G06N 5/022: Knowledge engineering; Knowledge acquisition - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS ## Abstract Systems and methods for scheduling an instruction list for parallel processing tasks are provided. An exemplary method includes obtaining an instruction set in the instruction list to be scheduled and determining data dependencies among instructions in the instruction set by performing a data dependency analysis on the instruction set. The method also includes obtaining, based on the data dependencies, selection nodes for performing instruction selections during the scheduling of the instruction list. The method further includes determining, based on a preset rule, an order of instructions in a scheduled instruction list according to a corresponding order of the selection nodes. ## Claims ### Claim 1 A method for scheduling an instruction list, the method comprising: obtaining an instruction set in the instruction list to be scheduled; determining data dependencies among instructions in the instruction set by performing a data dependency analysis on the instruction set; obtaining, based on the data dependencies, selection nodes for performing instruction selections during the scheduling of the instruction list; and determining, based on a preset rule, an order of instructions in a scheduled instruction list according to a corresponding order of the selection nodes, comprising: accessing a selection node and obtaining a longest execution time corresponding to the selection node; and when the longest execution time is shorter than an initial execution time: determining an order of sorted instructions of the selection node as the order of corresponding instructions in the scheduled instruction list; and changing the initial execution time to the longest execution time, wherein the initial execution time corresponds to an execution time of an instruction sequence in the instruction list to be scheduled. ### Claim 2 (depends on 1) The method of claim 1, wherein accessing the selection node comprises: accessing the selection node within a preset time period. ### Claim 3 (depends on 1) The method of claim 1, comprising: when the longest execution time is equal to or longer than the initial execution time, determining an order of instructions in the instruction list to be scheduled as the order of instructions in the scheduled instruction list. ### Claim 4 (depends on 1) The method of claim 1, wherein accessing the selection node comprises: accessing the selection node based on a random-first rule. ### Claim 5 (depends on 1) The method of claim 1, wherein accessing the selection comprises: accessing the selection node based on a breadth-first rule. ### Claim 6 (depends on 1) The method of claim 1, wherein accessing the selection node comprises: accessing the selection node based on a depth-first rule. ### Claim 7 (depends on 1) The method of claim 1, wherein accessing the selection node comprises: selecting selection nodes that are smaller than a preset order for accessing based on a breadth-first rule or a random-first rule; and selecting selection nodes that are equal to or larger than the preset order for accessing based on a depth-first rule. ### Claim 8 (depends on 1) The method of claim 1, comprising: obtaining a shortest execution time corresponding to the selection node; and when the shortest execution time is longer than the initial execution time, terminating accessing selection nodes that are correlated with the selection node currently being accessed. ### Claim 9 (depends on 1) The method of claim 1, wherein determining the order of instructions in the scheduled instruction list comprises: evaluating selection nodes corresponding to a current order based on preset priorities of the instructions to obtain an evaluation result; and determining corresponding instructions of the current order based on the evaluation result. ### Claim 10 (depends on 9) The method of claim 9, comprising: setting priorities of respective instructions based on at least one of a content or type of a current selection node. ### Claim 11 (depends on 1) The method of claim 1, wherein determining the order of instructions in the scheduled instruction list comprises: determining corresponding instructions of a current order based on a shortest execution time of a respective selection node of the current order. ### Claim 12 A system for scheduling an instruction list, the system comprising: a memory storing a computer program; and a processor coupled to the memory and configured to execute the computer program to perform operations, the operations comprising: obtaining an instruction set in the instruction list to be scheduled; determining data dependencies among instructions in the instruction set by performing a data dependency analysis on the instruction set; obtaining, based on the data dependencies, selection nodes for performing instruction selections during the scheduling of the instruction list; and determining, based on a preset rule, an order of instructions in a scheduled instruction list according to a corresponding order of the selection nodes, comprising: accessing a selection node and obtaining a longest execution time corresponding to the selection node; and when the longest execution time is shorter than an initial execution time: determining an order of sorted instructions of the selection node as the order of corresponding instructions in the scheduled instruction list; and changing the initial execution time to the longest execution time, wherein the initial execution time corresponds to an execution time of an instruction sequence in the instruction list to be scheduled. ### Claim 13 (depends on 12) The system of claim 12, wherein the operations comprise: when the longest execution time is equal to or longer than the initial execution time, determining an order of instructions in the instruction list to be scheduled as the order of instructions in the scheduled instruction list. ### Claim 14 (depends on 12) The system of claim 12, wherein the operations comprise: accessing the selection node based on at least one of a random-first rule, a breadth-first rule, or a depth-first rule. ### Claim 15 (depends on 12) The system of claim 12, wherein the operations comprise: obtaining a shortest execution time corresponding to the selection node; and when the shortest execution time is longer than the initial execution time, terminating accessing selection nodes that are correlated with the selection node currently being accessed. ### Claim 16 A non-transitory processor-readable storage medium storing a computer program that, when executed by a processor, causes the processor to perform operations comprising: obtaining an instruction set in the instruction list to be scheduled; determining data dependencies among instructions in the instruction set by performing a data dependency analysis on the instruction set; obtaining, based on the data dependencies, selection nodes for performing instruction selections during the scheduling of the instruction list; and determining, based on a preset rule, an order of instructions in a scheduled instruction list according to a corresponding order of the selection nodes, comprising: accessing a selection node and obtaining a longest execution time corresponding to the selection node; and when the longest execution time is shorter than an initial execution time: determining an order of sorted instructions of the selection node as the order of corresponding instructions in the scheduled instruction list; and changing the initial execution time to the longest execution time, wherein the initial execution time corresponds to an execution time of an instruction sequence in the instruction list to be scheduled.