Choice of algorithm for hierarchical clustering for minimizing network communication costs

Suppose I have a large distributed task running on a cluster system where part of the workload is compute bound and part depends on network performance. Data transfer is not completely homogeneous between processes - some communication pairs are more or less sensitive to bandwidth and latency than others.

We've profiled this and have a square matrix describing how much information is transferred between each pair of processes during the job.

We also know how the network is laid out and can approximate a scalar communication cost for each entry in that matrix.

Starting from that point, which clustering algorithms should I be looking at to permute that matrix to minimize total communication distance? Or, I think equivalently: how can I compute a near-optimal clustering of processes so that the processes that communicate the most are closest to each other on the network?

• So the problem is to find an assignment of processes to machines, such that the total communication cost is minimized? (Where the community cost is the sum over all pairs, of the amount of data exchanged between those pair of processes times the communication cost for that pair of machines.) Did I get that right? Nice problem! Is the number of processes the same as the number of machines? Do you have more processes than machines? Can we assign multiple processes to the same machine, or should it be one process per machine?
– D.W.
Jul 30 '14 at 22:35
• "Clustering" is not the right kind of problem here; you don't need a clustering, you need good overall cost.
– Raphael
Jul 31 '14 at 6:20
• D.W., you've got it right. There are cases where we can be undersubscribed (fewer processes than machines). However, previous solutions have always assumed that all machines are full except for the last one and that we simply permute processes into the slots already available. I think your solution below relates. I have another question to ask there but I'm just about ready to accept this as a great answer. Thanks! Aug 1 '14 at 3:13

This is a form of assignment problem; in particular, it is an instance of quadratic assignment problem. There are some known techniques available for solving this sort of problem.

Using integer linear programming

One approach is to use integer linear programming.

Let $d_{p,q}$ denote the amount of data communicated between processes $p$ and $q$, for each pair of processes $p,q$. Also, let $c_{i,j}$ denote the communication cost for data sent between machines $i$ and $j$, for each pair of machines $i,j$. These are given.

The goal is to find an assignment of processes to machines, that minimizes the total communication cost. I'll assume that you only allow one process to be assigned to each machine. We can model this as follows. For each process $p$ and each machine $i$, let $x_{p,i}$ be an unknown that is either 0 or 1, with the intent that $x_{p,i}=1$ means process $p$ is assigned to machine $i$. You can force it to be 0 or 1 with the constraint $0 \le x_{p,i} \le 1$. You can force each process to be assigned to one machine with the constraint

$$\sum_i x_{p,i} = 1.$$

You can also force each machine to be assigned at most one process with the constraint

$$\sum_p x_{p,i} \le 1.$$

The total communication cost is

$$\sum_{p,q,i,j} x_{p,i} x_{q,j} c_{i,j} d_{p,q},$$

where the sum is over all $p\ne q$ and $i \ne j$. That's what we'd like to minimize.

This is not yet a linear objective function, so we can't apply integer linear programming directly, but we can transform it into an integer linear program as follows. Let $y_{p,q,i,j} = 1$ if process $p$ is assigned to machine $i$ and process $q$ is assigned to machine $j$. We have $y_{p,q,i,j} = x_{p,i} \land x_{q,j}$. Now logical AND can be expressed in an integer linear program by adding the constraints

$$y_{p,q,i,j} \ge x_{p,i} + x_{q,j} - 1$$ $$y_{p,q,i,j} \le x_{p,i}$$ $$y_{p,q,i,j} \le x_{q,j}$$ $$0 \le y_{p,q,i,j} \le 1.$$

With these extensions, the total communication cost becomes

$$\sum_{p,q,i,j} y_{p,q,i,j} c_{i,j} d_{p,q},$$

which is a linear function. Thus, you now obtain an integer linear program, where the goal is to minimize the total communication cost, subject to the constraints listed above. You could try solving it using an off-the-shelf integer linear programming (ILP) solver.

There is no guarantee that this will efficiently find an optimal solution -- after all, integer linear programming is NP-hard in the worst case -- but in practice ILP solvers often work surprisingly well on many problems. So, you could give it a try and see how well it works on your particular problem instances. I don't know if there is a better algorithm, but this is one approach you could try.

P.S. In fact, in this particular case, you could skip the constraints $y_{p,q,i,j} \le x_{p,i}$ and $y_{p,q,i,j} \le x_{q,j}$ without changing the final solution. This makes the program a little bit simpler, at the cost of making it a little harder to understand why it "works" correctly for your problem.

Dedicated algorithms

An alternative is to use a dedicated algorithm for the quadratic assignment problem. For instance, Wikipedia mentions QAPLIB, a dedicated solver for instances of the quadratic assignment problem. You could try using QAPLIB on your problem instance, to see how well it works.

There may be other algorithms for the quadratic assignment problem -- I recommend doing a literature search to see what you can turn up.

• Thanks for the well thought out post. This gives me a lot to chew on. Previous solutions within my group have focused on an approach related to ParMETIS (glaros.dtc.umn.edu/gkhome/metis/parmetis/overview). Do you know if framing it as a graph problem versus linear programming changes much about the quality of the heuristics or approximate solutions? Aug 1 '14 at 3:16
• @AaronAltman, Glad you found it helpful. I'm afraid I don't know much about ParMETIS, so I don't have any intuition for how the two would relate, in terms of the quality of the solution provided. You might have to do some experiments. Sorry about that.
– D.W.
Aug 1 '14 at 3:18
• No problem, options are always good. It might also be that if ILP makes for more straightforward code, that could make it a better option if the two perform comparably. Aug 1 '14 at 3:21