Data flow programming of computing apparatus with vector estimation-based graph partitioning

Patent metadata

Field	Value
Publication number	US-10019342-B2
Application number	US-201514998137-A
Country	US
Kind code	B2
Filing date	Dec 24, 2015
Priority date	Dec 24, 2015
Publication date	Jul 10, 2018
Grant date	Jul 10, 2018

Abstract

In various embodiments, a spectral graph partitioner (“SP”) of a graph partitioning system (“GPS”) may partition a data flow graph associated with a program into a plurality of subgraphs to be used to perform analysis or debugging. The SP may generate estimated eigenvectors for a matrix representing the graph through minimization of a function on the vectors. The SP may generate multiple eigenvectors to perform the clustering in a multi-dimensional space described by the eigenvectors. The SP may refine the clustering by repeating generation of eigenvectors to describe higher-dimensional spaces and perform further clustering. The SP may also determine quality metrics for the clusters and may stop refinement based on the quality metrics. The GPS may select between utilizing the SP or utilizing one or more other partitioners based on various factors such as, for example, graph size or quality metrics. Other embodiments may be described and/or claimed.

First claim

What is claimed is:

1. A computing apparatus for analyzing or debugging a data flow program, comprising:
one or more computing hardware processors;
a spectral graph partitioner to execute on the one or more computing hardware processors to partition a data flow graph associated with the data flow program into a plurality of subgraphs and output results of the partition, wherein the data flow program operates on the one or more computing hardware processors or other one or more computing hardware processors of another computing apparatus;
wherein the spectral graph partitioner includes:
a vector estimator to generate one or more estimated vectors for a matrix describing the graph through minimization of a function on the vectors to partition the graph into the plurality of subgraphs; and
a cluster determiner to:
define a multi-dimensional space based on the one or more estimated vectors; and
cluster nodes of the graph to form the plurality of subgraphs in the multi-dimensional space;

an analyzer or debugger to execute on the one or more computing hardware processors to analyze or debug the data flow program using the plurality of subgraphs in the multi-dimensional space formed from the clustering; and
wherein to generate the one or more estimated vectors, the vector estimator generates at least a vector v using a function that depends on at least differences between a plurality of coordinates of the vector v or a difference between a number of nodes in the graph and a magnitude of the vector v.

2. The computing apparatus of claim 1 , wherein to generate the one or more estimated vectors, the vector estimator generates the one or more estimated vectors through generation of eigenvectors for a Laplacian matrix describing the graph, where the vector v is an eigenvector for the Laplacian matrix describing the graph.

3. The computing apparatus of claim 2 , wherein to generate the one or more estimated vectors, the vector estimator generates the vector v through the minimization of the function described by

f
=

∑

i
~
j

⁢

⁢

(

v
i

-

v
j

)

2

+

c
n

⁢

(

n
-


v


2

)

2

,

where n is a number of nodes in the graph, v i and v j are coordinates of the vector v, ∥v∥ is the magnitude of the vector v, and c is a constant.

4. The computing apparatus of claim 3 , wherein the minimization of the function comprises performance of a gradient descent on the function ƒ.

5. The computing apparatus of claim 3 , wherein a value of the constant c is based at least in part on an inverse of a degree of the graph.

6. The computing apparatus of claim 3 , wherein the generation of the vector v comprises:
setting one coordinate of the vector v to 0 prior to the minimization of the function ƒ; and
setting, after the minimization of the function ƒ, the coordinate which had been set to 0 to an average of its coordinate neighbors.

7. The computing apparatus of claim 1 , wherein the cluster determiner clusters the nodes of the graph to form the plurality of subgraphs through performance of a k-means clustering process.

8. The computing apparatus of claim 1 , wherein the spectral graph partitioner further comprises a quality metric determiner to determine, given the clustering of the nodes of the graph, one or more quality metrics for the clustering of the nodes.

9. The computing apparatus of claim 8 , wherein the quality metric determiner determines one or more of a modularity metric or a cluster path length metric for the clustering of the nodes.

10. The computing apparatus of claim 8 , wherein the spectral graph partitioner further comprises a refinement controller to cause repetition of the generation of estimated vectors and the clustering of the nodes of the graph based at least in part on the one or more quality metrics.

11. The computing apparatus of claim 10 , wherein the refinement controller causes the nodes of the graph to be clustered into increased numbers of clusters as additional estimated vectors are generated.

12. The computing apparatus of claim 1 , further comprising a partitioner selector to select between utilizing the spectral graph partitioner or one or more other graph partitioners of an apparatus.

13. The computing apparatus of claim 12 , wherein the partitioner selector selects based at least in part on a size of the graph or on one or more quality metrics determined for one or more clusterings generated by the spectral graph partitioner.

14. The computing apparatus of claim 12 , wherein the partitioner selector selects between the spectral graph partitioner and an edge centrality partitioner.

15. A computer-implemented method for analyzing or debugging a data flow program, comprising:
receiving, by a computing system, a data flow graph associated with the data flown program, the data flow program being operated on the computing system or another computing system;
generating, by the computing system, one or more estimated vectors for a matrix describing the graph through minimization of a function on the vectors to partition the graph into a plurality of subgraphs;
defining, by the computing system, a multi-dimensional space based on one or more estimated vectors;
clustering, by the computing system, nodes of the graph to form the plurality of subgraphs in the multi-dimensional space; and
executing, by the computing system, an analyzer or debugger to analyze or debug the data flow program, using the plurality of subgraphs in the multi-dimensional space formed by the clustering;
wherein the generating of the one or more estimated vectors comprises generating at least a vector v using a function that depends on at least differences between a plurality of coordinates of the vector v or a difference between a number of nodes in the graph and a magnitude of the vector v.

16. The method of claim 15 , wherein the generating of the one or more estimated vectors comprises generating eigenvectors for a Lapl

Assignees

• Intel Corp

Inventors

• Sun Lawrence J
• Tovinkere Vasanth R

Classifications

• G06F17/10

  Complex mathematical operations {(function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544)} · CPC title

• G06F11/3636 Primary

  by tracing the execution of the program · CPC title

• G06F11/3692 Primary

  for test results analysis · CPC title

• G06F15/82

  data or demand driven · CPC title

• G06F8/34 Primary

  Graphical or visual programming · CPC title