patternMinor
Analyzing load balancing schemes to minimize overall execution time
Viewed 0 times
minimizeoverallanalyzingtimeexecutionbalancingloadschemes
Problem
Suppose that a certain parallel application uses a master-slave design to process a large number of workloads. Each workload takes some number of cycles to complete; the number of cycles any given workload will take is given by a known random variable $X$. Assume that there are $n$ such workloads and $m$ equivalent slaves (processing nodes). Naturally, a more general version of this question addresses the case of slaves of differing capabilities, but we ignore this for now.
The master cannot process workloads, but can distribute workloads to slave nodes and monitor progress of slave nodes. Specifically, the master can perform the following actions:
For simplicity's sake, assume $k$ divides $n$.
There are at least two categories of load balancing strategies for minimizing the total execution time of all workloads using all slaves (to clarify, I'm talking about the makespan or wall-clock time, not the aggregate process time, which is independent of the load-balancing strategy being used under the simplifying assumptions being made in this question): static and dynamic. In a static scheme, all placement decisions are made at time $t = 0$. In a dynamic scheme, the master can make placement decisions using information about the progress being made by some slaves, and as such, better utilization can be attained (in practice, there are overheads associated with dynamic scheduling as compared to static scheduling, but we ignore these). Now for some questions:
The master cannot process workloads, but can distribute workloads to slave nodes and monitor progress of slave nodes. Specifically, the master can perform the following actions:
- Instantaneously begin processing of any $k$ workloads on any free node.
- Instantaneously receive confirmation of the completion by a node of a previously initiated batch of $k$ workloads.
- At any point in time, and instantaneously, determine the state of all nodes (free or busy) as well as the number of workloads completed and the number of workloads remaining.
For simplicity's sake, assume $k$ divides $n$.
There are at least two categories of load balancing strategies for minimizing the total execution time of all workloads using all slaves (to clarify, I'm talking about the makespan or wall-clock time, not the aggregate process time, which is independent of the load-balancing strategy being used under the simplifying assumptions being made in this question): static and dynamic. In a static scheme, all placement decisions are made at time $t = 0$. In a dynamic scheme, the master can make placement decisions using information about the progress being made by some slaves, and as such, better utilization can be attained (in practice, there are overheads associated with dynamic scheduling as compared to static scheduling, but we ignore these). Now for some questions:
- Is there a better way to statically schedule workloads than to divide batches of $k$ workloads among the $m$ slaves as evenly as possible (we can a
Solution
Update:
For the new version where you try to minimize the makespan, your static schedule still has the optimal expected value.
Let $M$ be the random variable for the makespan. Let $F_i$ be the time slave $i$ is finished. We then have that $M = \max_i(X_i)$. Let $c_i$ be the number of jobs allocated to slave $i$. Then we have that $X_i = \sum_{i=1}^{c_i} X = c_i X$.
If $F_i(x)$ is the cumulative probability distribution function for $X$, then $P(M < m) $ $ = P(\max_i(X_i) < m) $ $ = \prod_i P(X_i < m) $ $ = \prod_i P(c_i X < m) $ $ = \prod_i P(X < \frac{m}{c_i}) $ $ = \prod_i F(\frac{m}{c_i})$ is the cumulative probability distribution function for $M$. This means that $EM = \int_{-\infty}^{\infty} x (\prod_i F(\frac{x}{c_i}))' dx$ and $stddev(M) = \sqrt{\int_{-\infty}^{\infty} (x - EM)^2 (\prod_i F(\frac{x}{c_i}))' dx}$, as normal.
Minimizing $EM$ amounts to minimizing $\prod_i F(\frac{x}{c_i})$, which means we want to keep all $c_i$s equally low (as $F$ is monotonically increasing and between 0 and 1). This means we should equally distribute all tasks among the slaves, which is exactly what your static schedule achieves.
For the new version where you try to minimize the makespan, your static schedule still has the optimal expected value.
Let $M$ be the random variable for the makespan. Let $F_i$ be the time slave $i$ is finished. We then have that $M = \max_i(X_i)$. Let $c_i$ be the number of jobs allocated to slave $i$. Then we have that $X_i = \sum_{i=1}^{c_i} X = c_i X$.
If $F_i(x)$ is the cumulative probability distribution function for $X$, then $P(M < m) $ $ = P(\max_i(X_i) < m) $ $ = \prod_i P(X_i < m) $ $ = \prod_i P(c_i X < m) $ $ = \prod_i P(X < \frac{m}{c_i}) $ $ = \prod_i F(\frac{m}{c_i})$ is the cumulative probability distribution function for $M$. This means that $EM = \int_{-\infty}^{\infty} x (\prod_i F(\frac{x}{c_i}))' dx$ and $stddev(M) = \sqrt{\int_{-\infty}^{\infty} (x - EM)^2 (\prod_i F(\frac{x}{c_i}))' dx}$, as normal.
Minimizing $EM$ amounts to minimizing $\prod_i F(\frac{x}{c_i})$, which means we want to keep all $c_i$s equally low (as $F$ is monotonically increasing and between 0 and 1). This means we should equally distribute all tasks among the slaves, which is exactly what your static schedule achieves.
Context
StackExchange Computer Science Q#134, answer score: 5
Revisions (0)
No revisions yet.