METHOD AND SYSTEM FOR ON-THE-FLY GRAPH PARTITIONING RESOURCE UTILIZATION

1 . A method for performing on-the-fly partitioning of a graph having a plurality of subgraphs comprising hierarchies of subsets of ternary keys having one or more wildcards, comprising:

identifying a move operation to be executed under which ternary keys and associated structures for a subset in a source subgraph are to be moved to a destination subgraph;

projecting, prior to executing the move operation, there are sufficient memory and hardware resources to execute the move operation without hitting resource capacity limits; and

executing the move operation when it is projected the move operation can be executed without hitting the resource capacity limits.

2 . The method of claim 1 , wherein resource capacity limits include capacity limits comprising resource utilization including one or more of:

space utilization in a space partitioner;

stash utilization; and

graph utilization comprising utilization of the graph stored in hardware.

3 . The method of claim 1 , further comprising:

performing emulation of the move operation considering resource utilization required to execute the move operation;

determining whether the emulated move operation is successful under which the resource utilization to execute the move operation will not exceed available resource capacities; and

executing the move operation if the emulated move is determined to be successful.

4 . The method of claim 1 , further comprising:

compiling current resource utilization for the graph across memory resources and hardware resources;

projecting peak resource utilization for the move operation;

determining whether the peak resource utilization would not exceed a capacity of the memory and hardware resources; and

executing the move operation if the peak resource utilization is projected to not exceed said capacity of memory and hardware resources.

5 . The method of claim 1 , further comprising:

computing a system load;

determining whether the system load exceeds a threshold; and

when the system load exceeds the threshold,

performing emulation of the move operation considering resource utilization required to execute the move operation;

determining whether the emulated move operation is successful under which the resource utilization to execute the move operation will not exceed available resource capacities; and

executing the move operation if the emulated move is determined to be successful;

otherwise, when the system load does not exceed the threshold,

compiling current resource utilization for the graph across memory resources and hardware resources;

projecting peak resource utilization for the move operation;

determining whether the peak resource utilization would not exceed a capacity of the memory and hardware resources; and

executing the move operation if the peak resource utilization is projected to not exceed said capacity of memory and hardware resources.

6 . The method of claim 5 , wherein system load is computed from one or more resource utilization metrics.

7 . The method of claim 1 , further comprising:

estimating graph leaf resources to be utilized during execution of the move operation, wherein estimation of graph resources is performed by analysis of quantum keys of the subset to be moved, the source subgraph, and the destination subgraph.

8 . The method of claim 1 , further comprising:

estimating graph node resources to be utilized during execution of the move operation, wherein estimation of graph node resources is performed by at least one of,

analysis of quantum keys; and

projection of internal vertex fan-out and external-to-internal vertex ratio.

9 . The method of claim 1 , further comprising:

prior to executing a main move operation, performing an initial reorganization of the graph under which the graph is reorganized by executing one or more initial move operations; and

executing the main move operation following the initial reorganization of the graph.

10 . The method of claim 1 , further comprising constructing a hierarchy of subsets for a subgraph by pairwise merging smaller subsets.

11 . A non-transitory machine-readable medium having instructions stored thereon configured to be executed on one or more processing elements in a computing apparatus, wherein execution of the instructions on the one or more processing elements enables the computing apparatus to perform on-the-fly partitioning of a graph having a plurality of subgraphs comprising hierarchies of subsets of ternary keys having one or more wildcards by:

identify a move operation to be executed under which ternary keys and associated structures for a subset in a source subgraph are to be moved to a destination subgraph;

project, prior to executing the move operation, there are sufficient memory and hardware resources to execute the move operation without hitting resource capacity limits; and

execute the move operation when it is projected the move operation can be executed without hitting the resource capacity limits.

12 . The non-transitory machine-readable medium of claim 11 , wherein execution of the instructions enables the computing apparatus to:

perform emulation of the move operation considering resource utilization required to execute the move operation;

determine whether the emulated move operation is successful under which the resource utilization to execute the move operation will not exceed available resource capacities; and

execute the move operation if the emulated move is determined to be successful.

13 . The non-transitory machine-readable medium of claim 11 , wherein execution of the instructions enables the computing apparatus to:

compile current resource utilization for the graph across memory resources and hardware resources;

project peak resource utilization for the move operation;

determine whether the peak resource utilization would not exceed a capacity of the memory and hardware resources; and

execute the move operation if the peak resource utilization is projected to not exceed said capacity of memory and hardware resources.

14 . The non-transitory machine-readable medium of claim 11 , wherein execution of the instructions enables the computing apparatus to:

compute a system load;

determining whether the system load exceeds a threshold; and

when the system load exceeds the threshold,

perform emulation of the move operation considering resource utilization required to execute the move operation;

determine whether the emulated move operation is successful under which the resource utilization to execute the move operation will not exceed available resource capacities; and

execute the move operation if the emulated move is determined to be successful;

otherwise, when the system load does not exceed the threshold,

compile current resource utilization for the graph across memory resources and hardware resources;

project peak resource utilization for the move operation;

determine whether the peak resource utilization would not exceed a capacity of the memory and hardware resources; and

execute the move operation if the peak resource utilization is projected to not exceed said capacity of memory and hardware resources.

15 . The non-transitory machine-readable medium of claim 11 , wherein execution of the instructions enables the computing apparatus to:

prior to executing a main move operation, perform an initial reorganization of the graph under which the graph is reorganized by executing one or more initial move operations; and

execute the main move operation following the initial reorganization of the graph.

16 . An apparatus comprising means for performing on-the-fly partitioning of a graph having a plurality of subgraphs comprising hierarchies of subsets of ternary keys having one or more wildcards by:

identifying a move operation to be executed under which ternary keys and associated structures for a subset in a source subgraph are to be moved to a destination subgraph;

projecting, prior to executing the move operation, there are sufficient memory and hardware resources to execute the move operation without hitting resource capacity limits; and

executing the move operation when it is projected the move operation can be executed without hitting the resource capacity limits.

17 . The apparatus of claim 16 , wherein the means for partitioning the set of ternary keys having one or more wildcards comprises one or more processing elements coupled to memory and instructions configured to be executed on the one or more processing elements.

18 . The apparatus of claim 16 , wherein the means for partitioning the set of ternary keys having one or more wildcards comprises one or more programmable or preprogrammed logic components comprising one or more of a Field Programmable Gate Array (FPGA), and Application Specific Integrated Circuit (ASIC), and a programmable logic device.

19 . The apparatus of claim 18 , wherein the apparatus comprises an infrastructure processing unit (IPU), a data processing unit (DPU), or an edge processing unit (EPU).

20 . The apparatus of claim 16 , wherein means for partitioning the set of ternary keys having one or more wildcards comprises:

one or more processing elements coupled to memory and instructions configured to be executed on the one or more processing elements; and

one or more programmable or preprogrammed logic components comprising one or more of a Field Programmable Gate Array (FPGA), and Application Specific Integrated Circuit (ASIC), and a programmable logic device.