1

I have set up an infrastructure for grid computation. That is, an operation of N iterations is distributed and independently calculated on different servers, and the final result is the aggregation of the individual results.

Each server has a different number of CPU cores. Each core operates independently.

I have three servers: S1, S2, S3.

  • S1 has 4 cores.
  • S2 has 8 cores.
  • S3 has 4 cores.

So, in total, 16 cores.

Say I have an operation of 500.000 iterations, I distribute the calculation in the following way:

  • S1 => (500.000 / 16 * 4) = 125.000 iterations
  • S2 => (500.000 / 16 * 8) = 250.000 iterations
  • S3 => (500.000 / 16 * 4) = 125.000 iterations

Now the response times:

  • S1 completes 125.000 iterations in 4587 ms.
  • S2 completes 250.000 iterations in 8403 ms.
  • S3 completes 125.000 iterations in 9356 ms.

As you can see the servers have different performances: S3 is more than twice slower than S1.

What I want is to redistribute the calculation in a non uniform way, so that the response time is optimised (for example, S3 should be assigned approximately half of the iterations than S1).

What's the math behind this operation?

RobPratt
  • 45,619
Luca Fagioli
  • 97

1 Answers1

2

Let $r_s$ be the number of iterations per ms for server $s$. Let decision variable $x_s$ be the number of iterations assigned to server $s$. You want to minimize the makespan $$\max_{s\in\{1,2,3\}} x_s/r_s$$ subject to \begin{align} x_1 + x_2 + x_3 &= 500000 \tag1 \\ x_s &\ge 0 &&\text{for all $s$} \end{align} The optimal value will occur when $$x_1/r_1 = x_2/r_2 = x_3/r_3. \tag2$$ Solving $(1)$ and $(2)$ yields $x \approx (193646, 211414, 94940)$.

RobPratt
  • 45,619