Cheap and Secure Web Hosting Provider : See Now

[Answers] Choice of algorithm for hierarchical clustering for minimizing network communication costs

, ,
Problem Detail:

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?

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.