Efficient resource allocation for concurrent graph workloads

1. A method comprising:

receiving a request to execute a graph processing workload on a dataset, wherein the dataset is modeled as a graph;

identifying a plurality of graph operators that constitute the graph processing workload;

determining that execution of each graph operator of the plurality of graph operators is either processor intensive or memory intensive;

assigning a task weight to each graph operator of the plurality of graph operators based on the determining;

performing, based on the task weights assigned to the plurality of graph operators, a first allocation of computing resources to execute the plurality of graph operators;

causing, according to the first allocation, execution of the plurality of graph operators by the computing resources;

monitoring computing resource usage of the plurality of graph operators executed by the computing resources according to the first allocation;

performing, responsive to monitoring the computing resource usage, a second allocation of computing resources to execute the plurality of graph operators, wherein the second allocation is different than the first allocation; and

causing, according to the second allocation instead of according to the first allocation, execution of the plurality of graph operators by the computing resources.

2. The method of claim 1 , wherein performing the second allocation of computing resources to execute the plurality of graph operators further comprises:

identifying, for each graph operator of the plurality of graph operators, an instructions per cycle (IPC) metric for execution of the plurality of graph operators according to the first allocation;

identifying a first graph operator of the plurality of graph operators with a first IPC corresponding to a highest IPC, and a second graph operator of the plurality of graph operators with a second IPC corresponding to a lowest IPC; and

assigning at least one computing resource from the second graph operator to the first graph operator.

3. The method of claim 2 , further comprising:

adjusting, responsive to performing the second allocation, one or more task weights relative to whether execution of a given graph operator is processor intensive or memory intensive, or a number of computing resources assigned, during subsequent iterations of performing other allocations of computing resources to execute the plurality of graph operators, from a graph operator with a lowest IPC to a graph operator with a highest IPC.

4. The method of claim 1 , wherein performing the second allocation of computing resources to execute the plurality of graph operators further comprises:

identifying, for each graph operator of the plurality of graph operators, an instructions per cycle (IPC) metric for execution of the plurality of graph operators according to the first allocation;

identifying a first graph operator of the plurality of graph operators with a first IPC corresponding to a highest IPC, and a second graph operator of the plurality of graph operators with a second IPC corresponding to a lowest IPC;

determining that the first IPC of the first graph operator is greater than a first threshold value;

determining that the second IPC of the second graph operator is less than a second threshold value; and

responsive to determining that the first IPC of the first graph operator is greater than the first threshold value and that the second IPC of the second graph operator is less than the second threshold value, assigning at least one computing resource from the second graph operator to the first graph operator.

5. The method of claim 4 , further comprising:

monitoring computing resource usage of graph operators executed by the computing resources according to the second allocation;

performing, responsive to monitoring computing resource usage, a third allocation of computing resources to execute the plurality of graph operators; and

causing, according to the third allocation instead of according to the second allocation, execution of the plurality of graph operators by the computing resources.

6. The method of claim 5 , wherein performing the third allocation of computing resources to execute the plurality of graph operators further comprises:

identifying, for each graph operator of the plurality of graph operators, an instructions per cycle (IPC) metric for execution of the plurality of graph operators according to the second allocation;

identifying a third graph operator of the plurality of graph operators with a third IPC corresponding to a highest IPC, and a fourth graph operator of the plurality of graph operators with a fourth IPC corresponding to a lowest IPC;

determining that the third IPC of the third graph operator is greater than the first threshold value;

determining that the fourth IPC of the fourth graph operator is less than the second threshold value; and

responsive to determining that the third IPC of the third graph operator is greater than the first threshold value and that the fourth IPC of the fourth graph operator is less than the second threshold value, assigning at least one computing resource from the fourth graph operator to the third graph operator.

7. The method of claim 1 , wherein the first allocation and the second allocation allocate one or more CPU threads from a plurality of CPU threads to execute each graph operator of the plurality of graph operators.

8. The method of claim 1 , further comprising:

processing one or more predetermined graph datasets to assign resource usage classifications to a set of one or more graph operators, wherein each of the one or more predetermined graph datasets is modeled as a graph, and wherein the resource usage classifications identify that execution of a given graph operator on the one or more predetermined graph datasets is either processor intensive or memory intensive; and

wherein the determining that execution of each graph operator of the plurality of graph operators is either processor intensive or memory intensive is performed by utilizing the resource usage classifications assigned to the set of one or more graph operators.

9. The method of claim 8 , further comprising:

adjusting, responsive to monitoring the computing resource usage of graph operators executed by the computing resources according to the first allocation, the resource usage classifications assigned to the set of one or more graph operators.

10. The method of claim 1 , wherein the first allocation allocates one or more CPU threads from a plurality of CPU threads to execute each graph operator of the plurality of operators; and

wherein performing the first allocation of computing resources to execute the plurality of graph operators further includes calculating a result by dividing a total number of CPU threads in the plurality of CPU threads by a cumulative task weight assigned to the plurality of graph operators, and multiplying the result by the assigned task weight for each graph operator.

11. One or more non-transitory computer-readable storage medium storing instructions that, when executed by one or more processors, cause the one or more processors to perform functions comprising:

receiving a request to execute a graph processing workload on a dataset, wherein the dataset is modeled as a graph;

identifying a plurality of graph operators that constitute the graph processing workload;

determining that execution of each graph operator of the plurality of graph operators is either processor intensive or memory intensive;

assigning a task weight to each graph operator of the plurality of graph operators based on the determining;

performing, based on the task weights assigned to the plurality of graph operators, a first allocation of computing resources to execute the plurality of graph operators;

causing, according to the first allocation, execution of the plurality of graph operators by the computing resources;

monitoring computing resource usage of the plurality of graph operators executed by the computing resources according to the first allocation;

performing, responsive to monitoring the computing resource usage, a second allocation of computing resources to execute the plurality of graph operators, wherein the second allocation is different than the first allocation; and

causing, according to the second allocation instead of according to the first allocation, execution of the plurality of graph operators by the computing resources.

12. The one or more non-transitory computer-readable storage medium of claim 11 , further comprising instructions that, when executed by one or more processors, cause the one or more processors to perform functions comprising:

performing the second allocation of computing resources to execute the plurality of graph operators by performing functions that further comprise:

identifying, for each graph operator of the plurality of graph operators, an instructions per cycle (IPC) metric for execution of the plurality of graph operators according to the first allocation;

identifying a first graph operator of the plurality of graph operators with a first IPC corresponding to a highest IPC, and a second graph operator of the plurality of graph operators with a second IPC corresponding to a lowest IPC; and

assigning at least one computing resource from the second graph operator to the first graph operator.

13. The one or more non-transitory computer-readable storage medium of claim 12 , further comprising instructions that, when executed by one or more processors, cause the one or more processors to perform functions comprising:

adjusting, responsive to performing the second allocation, one or more task weights relative to whether execution of a given graph operator is processor intensive or memory intensive, or a number of computing resources assigned, during subsequent iterations of performing other allocations of computing resources to execute the plurality of graph operators, from a graph operator with a lowest IPC to a graph operator with a highest IPC.

14. The one or more non-transitory computer-readable storage medium of claim 11 , further comprising instructions that, when executed by one or more processors, cause the one or more processors to perform functions comprising:

performing the second allocation of computing resources to execute the plurality of graph operators by performing functions that further comprise:

identifying, for each graph operator of the plurality of graph operators, an instructions per cycle (IPC) metric for execution of the plurality of graph operators according to the first allocation;

identifying a first graph operator of the plurality of graph operators with a first IPC corresponding to a highest IPC, and a second graph operator of the plurality of graph operators with a second IPC corresponding to a lowest IPC;

determining that the first IPC of the first graph operator is greater than a first threshold value;

determining that the second IPC of the second graph operator is less than a second threshold value; and

responsive to determining that the first IPC of the first graph operator is greater than the first threshold value and that the second IPC of the second graph operator is less than the second threshold value, assigning at least one computing resource from the second graph operator to the first graph operator.

15. The one or more non-transitory computer-readable storage medium of claim 14 , further comprising instructions that, when executed by one or more processors, cause the one or more processors to perform functions comprising:

monitoring computing resource usage of graph operators executed by the computing resources according to the second allocation;

performing, responsive to monitoring computing resource usage, a third allocation of computing resources to execute the plurality of graph operators; and

causing, according to the third allocation instead of according to the second allocation, execution of the plurality of graph operators by the computing resources.

16. The one or more non-transitory computer-readable storage medium of claim 15 , further comprising instructions that, when executed by one or more processors, cause the one or more processors to perform functions comprising:

performing the third allocation of computing resources to execute the plurality of graph operators by performing functions that further comprise:

identifying, for each graph operator of the plurality of graph operators, an instructions per cycle (IPC) metric for execution of the plurality of graph operators according to the second allocation;

identifying a third graph operator of the plurality of graph operators with a third IPC corresponding to a highest IPC, and a fourth graph operator of the plurality of graph operators with a fourth IPC corresponding to a lowest IPC;

determining that the third IPC of the third graph operator is greater than the first threshold value;

determining that the fourth IPC of the fourth graph operator is less than the second threshold value; and

responsive to determining that the third IPC of the third graph operator is greater than the first threshold value and that the fourth IPC of the fourth graph operator is less than the second threshold value, assigning at least one computing resource from the fourth graph operator to the third graph operator.

17. The one or more non-transitory computer-readable storage medium of claim 14 , wherein the first allocation and the second allocation allocate one or more CPU threads from a plurality of CPU threads to execute each graph operator of the plurality of graph operators.

18. The one or more non-transitory computer-readable storage medium of claim 11 , further comprising instructions that, when executed by one or more processors, cause the one or more processors to perform functions comprising:

processing one or more predetermined graph datasets to assign resource usage classifications to a set of one or more graph operators, wherein each of the one or more predetermined graph datasets is modeled as a graph, and wherein the resource usage classifications identify that execution of a given graph operator on the one or more predetermined graph datasets is either processor intensive or memory intensive; and

wherein the function of determining that execution of each graph operator of the plurality of graph operators is either processor intensive or memory intensive is further performed by utilizing the resource usage classifications assigned to the set of one or more graph operators.

19. The one or more non-transitory computer-readable storage medium of claim 18 , further comprising instructions that, when executed by one or more processors, cause the one or more processors to perform functions comprising:

adjusting, responsive to monitoring the computing resource usage of graph operators executed by the computing resources according to the first allocation, the resource usage classifications assigned to the set of one or more graph operators.

20. The one or more non-transitory computer-readable storage medium of claim 11 , wherein the first allocation allocates one or more CPU threads from a plurality of CPU threads to execute each graph operator of the plurality of graph operators; and

wherein the function of performing the first allocation of computing resources to execute the plurality of graph operators further includes the functions of calculating a result by dividing a total number of CPU threads in the plurality of CPU threads by a cumulative task weight assigned to the plurality of graph operators, and multiplying the result by the assigned task weight for each graph operator.