# US 12,182,633 B2 · Method, system, computer readable medium, and device for scheduling computational operation based on graph data > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,182,633 B2 - Document ID: US12182633B2 - Status: Granted - Kind: B2 - Application number: 17/160,212 - Filed: 2021-01-27 - Published: 2021-05-20 - Granted: 2024-12-31 - Earliest claimed: 2018-07-27 - Assignees: Zhejiang Tmall Technology Co., Ltd. - Applicants: Zhejiang Tmall Technology Co., Ltd. - Inventors: Wenfei Fan; Wenyuan Yu; Jingbo Xu; Xiaojian Luo - Web page: https://patentgrep.com/patent/US12182633B2 ## CPC - G06F 9/5088: {involving task migration} - G06F 9/4856: {resumption being on a different machine, e.g. task migration, virtual machine migration (G06F9/5088 takes precedence)} - G06F 9/4881: {Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues} - G06F 9/5027: {the resource being a machine, e.g. CPUs, Servers, Terminals} - G06F 9/5061: {Partitioning or combining of resources} - G06F 16/9024: {Graphs; Linked lists (G06F16/9027 takes precedence)} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A method for scheduling a computational operation based on graph data, which includes: dividing graph data into multiple partitions; scheduling the partitions to be allocated to multiple processors; successively assigning the partitions to corresponding threads of the processors for computation according to a respective degree of criticality of each partition; determining whether an idle processor exists, a processor being the idle processor when the processor includes one or more idle threads; communicating the idle processor with other processor(s) to find partition(s) to be computed and corresponding to the other processor(s); selecting and determining a partition to be computed; and migrating and binding the determined partition to be computed to thread(s) of the idle processor for processing. The present disclosure further relates to a system, a computer readable medium, and a device for scheduling a computational operation based on graph data. ## Claims ### Claim 1 A method implemented by a computing device, the method comprising: determining that an idle processor of multiple processors exists, the multiple processors being allocated with multiple partitions of graph data; considering an execution time of a respective partition to be computed and a migration overhead of the respective partition to be computed to obtain an evaluation result by evaluating losses and profits, the migration overhead of the respective partition to be computed including a respective time overhead including a first time overhead of transferring data of the respective partition to be computed from a first machine to a second machine and a second time overhead of rebuilding the respective partition on the second machine; causing the idle processor to communicate with one or more other processors to determine one or more partitions to be computed, according to respective degrees of criticality of respective partitions and the evaluation result, corresponding to the one or more other processors; and migrating and binding the determined one or more partitions to be computed to one or more threads of the idle processor for processing. ### Claim 2 (depends on 1) The method as recited in claim 1, wherein a specific processor is determined to be the idle processor in response to determining that the specific processor includes one or more idle threads. ### Claim 3 (depends on 1) The method as recited in claim 1, further comprising: dividing the graph data into the multiple partitions. ### Claim 4 (depends on 3) The method as recited in claim 3, further comprising: successively assigning the multiple partitions to corresponding threads of the multiple processors for computation according to the respective degrees of criticality of the respective partitions. ### Claim 5 (depends on 1) The method as recited in claim 1, wherein a number of partitions allocated to each processor is greater than a number of threads corresponding to each processor. ### Claim 6 (depends on 1) The method as recited in claim 1, wherein: the one or more partitions to be computed comprise multiple partitions to be computed. ### Claim 7 (depends on 1) The method as recited in claim 1, further comprising: determining a mode for migrating data of the determined one or more partitions to be computed to the idle processor. ### Claim 8 One or more computer readable media storing executable instructions that, when executed by a computing device, cause the computing device to perform acts comprising: determining that an idle processor of multiple processors exists, the multiple processors being allocated with multiple partitions of graph data; considering an execution time of a respective partition to be computed and a migration overhead of the respective partition to be computed to obtain an evaluation result by evaluating losses and profits, the migration overhead of the respective partition to be computed including a respective time overhead including a first time overhead of transferring data of the respective partition to be computed from a first machine to a second machine and a second time overhead of rebuilding the respective partition on the second machine; causing the idle processor to communicate with one or more other processors to determine one or more partitions to be computed, according to respective degrees of criticality of respective partitions and the evaluation result, corresponding to the one or more other processors; and migrating and binding the determined one or more partitions to be computed to one or more threads of the idle processor for processing. ### Claim 9 (depends on 8) The one or more computer readable media as recited in claim 8, wherein a specific processor is determined to be the idle processor in response to determining that the specific processor includes one or more idle threads. ### Claim 10 (depends on 8) The one or more computer readable media as recited in claim 8, the acts further comprising: dividing the graph data into the multiple partitions. ### Claim 11 (depends on 10) The one or more computer readable media as recited in claim 10, the acts further comprising: successively assigning the multiple partitions to corresponding threads of the multiple processors for computation according to the respective degrees of criticality of the respective partitions. ### Claim 12 (depends on 8) The one or more computer readable media as recited in claim 8, wherein a number of partitions allocated to each processor is greater than a number of threads corresponding to each processor. ### Claim 13 (depends on 8) The one or more computer readable media as recited in claim 8, wherein: the one or more partitions to be computed comprise multiple partitions to be computed. ### Claim 14 (depends on 8) The one or more computer readable media as recited in claim 8, the acts further comprising: determining a mode for migrating data of the determined one or more partitions to be computed to the idle processor. ### Claim 15 A system comprising: one or more processors; memory; a determination module stored in the memory and executable by the one or more processors to determine whether an idle processor of multiple processors exists, the multiple processors being allocated with multiple partitions of graph data; a selection module stored in the memory and executable by the one or more processors to consider an execution time of a respective partition to be computed and a migration overhead of the respective partition to be computed, and evaluate losses and profits, the migration overhead of the respective partition to be computed including a respective time overhead including a first time overhead of transferring data of the respective partition to be computed from a first machine to a second machine and a second time overhead of rebuilding the respective partition on the second machine; a communication module stored in the memory and executable by the one or more processors to cause the idle processor to communicate with one or more other processors to determine one or more partitions to be computed and corresponding to the one or more other processors based on an evaluation result of the selection module; and a migration module stored in the memory and executable by the one or more processors to migrate and bind the determined one or more partitions to be computed to one or more threads of the idle processor for processing. ### Claim 16 (depends on 15) The system recited in claim 15, wherein a specific processor is determined to be the idle processor when the specific processor includes one or more idle threads. ### Claim 17 (depends on 15) The system recited in claim 15, further comprising: a division module configured to divide the graph data into the multiple partitions; an allocation module configured to schedule the multiple partitions to the multiple processors; and a submission module configured to successively assign the multiple partitions to corresponding threads of the multiple processors for computation according to respective degrees of criticality of respective partitions. ### Claim 18 (depends on 17) The system as recited in claim 17, wherein a number of partitions allocated to each processor by the allocation module is greater than a number of threads corresponding to each processor. ### Claim 19 (depends on 15) The system as recited in claim 15, wherein: the determined one or more partitions to be computed comprise multiple partitions to be computed, and the selection module is further configured to: determine which specific partition to be computed is allocated to the idle processor according to the evaluation result. ### Claim 20 (depends on 19) The system as recited in claim 19, wherein the selection module is further configured to: determine a mode for migrating data of the determined one or more partitions to be computed to the idle processor.