Repository files navigation

Indistributed computing systems, a group of computers work together to achievea common goal. For example, a group of computers might work together toanalyze a large data set. In these types of computing systems, each computermanages a piece of the problem and interacts with the other computingsystems by passing messages. Each computer handles a subset of the requiredoperations, and some operations might require inputs computed by a differentcomputer. By passing a message containing the required input, the operation canthen be completed. These messages might contain information required tocontinue the computations, and so can become a bottleneck to efficientcomputation. By minimizing the number of messages required between computers wecan also minimize the number of dependencies between the operations performedon different systems, making the overall computation faster and more efficientby minimizing waiting time.

To solve the problem of minimizing messaging between computers in a distributedcomputing system, we build a graph or network model. Each operation for theoverall computation is represented by a node, or vertex, in the graph, and anedge between nodes indicates that there is a dependency between two operations.To minimize the number of messages passed, we would like to partition theoperations amongst the available computers so that the number of messagesbetween computers (or partitions) is minimized. Additionally, we would alsolike to balance the workload across our available computers by partitioning theoperations evenly.

To solve this problem in our graph model, we are looking to partition the setof nodes into a fixed number of subsets of equal size so that the total numberof edges between subsets is minimized. This is known as the graphk-partitioning problem. In the case where k = 2, it is straightforward to usebinary variables to indicate the subsets for each operation and solve using abinary quadratic model, as shown in thegraph partitioning code example. Fork > 2, the problem becomes significantly more complex.

To run the demo, type:

python demo.py

Additional options are available to select different graphs to run the problemon. To see the full list of options, type:

python demo.py -h

During a successful run of the program, two images are produced and saved. Thefirst is the original input graph, saved asinput_graph.png.

The second highlights the partition of the population into groups.

Several different types of graphs or networks are available for this demo usingthe options provided. These are all built using NetworkX graph generatorfunctions, and the details of these functions can be foundhere.

• partition: Partition graph; specify number of nodes, number of partitions,and inter- and intra-partition edge probabilities.
• internet: Internet Autonomous System network; specify number of nodesand partitions.
• rand-reg: A random d-regular graph; specify number of nodes and value for d.
• ER: Erdos-Renyi random graph; specify number of nodes and edge probability.
• SF: Barabasi-Albert scale-free graph; specify number of nodes and number ofedges to add from a new node to any existing nodes.

The default graph is the partition graph on 100 nodes with 4 partitions withinter-partition edge probability of 0.5 and intra-partition edge probability of0.001. The largest number of nodes times the number of partitions allowed forany problem instance can be at most 5,000.

The demo program formulates this graph k-partitioning problem as a constrainedquadratic model (CQM), and solves it using the hybrid CQM solver.

The formulation of this problem defines a binary variable x for each pair(n, p), where n is a node in the graph and p is a partition. If the solutionreturns variable (n, p) = 1, then node n is assigned to partition p. Otherwise,if the solution returns variable (n, p) = 0, then node n isnot assigned topartition p.

The objective for this problem is to minimize the number of inter-partitionedges. We can formulate this as a binary quadratic expression that needs to beminimized by considering an arbitrary edge (i, j) between nodes i and j in thegraph. For each partition p, we add the expression(i, p) + (j, p) - 2*(i, p)*(j, p) to decrease the overall cost when i and jare assigned to the same partition, and increase the overall cost when theyare not. To see how this expression maps to these costs, we examine thefollowing table which demonstrates the cost of edge (i, j), depending onwhether i and j are each assigned to partition p.

Now that we have an expression for the appropriate cost for each edge and eachpartition, we simply sum over all edges and all partitions to build theobjective function that will minimize the number of inter-partition edges inthe entire graph.

Objective: minimize Σ_(i,j) Σ_p x_(i,p) + x_(j,p) - 2*x_(i,p)*x_(j,p)

Each node in our graph must be assigned to exactly one partition, so we mustenforce aone-hot constraint on each node. That is, for each node i, we musthave that the sum of all binary variables associated with i is equal to 1.

Constraint 1: Σ_k x_(i,p) = 1, for each node i

To efficiently distribute the operational load across computers in our system,we would like the partitions to have equal size. If N is the total number ofnodes in the graph and k is the number of partitions available, each partitionshould have size N/k. We enforce this by requiring that the sum of binaryvariables associated with each partition is equal to N/k. Note that thisrequires that N is evenly divisble by k, and so the demo file will adjust N asneeded to enforce this requirement.

Constraint 2: Σ_i x_(i,p) = N/k, for each partition p.

Released under the Apache License 2.0. SeeLICENSE file.