Question

amdahls law on the data-parallel stage

setup
take t3 from problem 1 in isolation: 1-minute setup, 8 minutes of parallelizable compute, 1-minute combine. on one worker, t3 takes 10 minutes total.

amdahls law
\\(\text{speedup}(n) = 1 / (s + (1 - s)/n)\\)

• \\(s =\\) serial fraction (setup + combine, not speedable)
• \\(n =\\) number of workers in the parallel stage
• as \\(n \to \infty\\), \\(\text{speedup} \to 1/s\\) (a hard ceiling)

compute
(a) what is the serial fraction \\(s\\) for t3?
(b) speedup at \\(n = 2, 4, 8, 16\\)? fill a table.
(c) asymptotic speedup as \\(n \to \infty\\)? floor on t3 runtime?
(d) worth upgrading \\(4 \to 16\\) workers at \\(4\times\\) cost, for t3 alone?

Explanation:

Identify given parameters

We analyze the setup parameters.
The total sequential runtime is:

$$ T_{\text{total}} = 10\text{ minutes} $$

The non-parallelizable (serial) parts are:

• Setup: \(1\text{ minute}\)
• Combine: \(1\text{ minute}\)

The parallelizable compute part is:

• Compute: \(8\text{ minutes}\)

Calculate serial fraction

We find the serial fraction \(s\).
The serial portion is:

$$ T_{\text{serial}} = 1 + 1 = 2\text{ minutes} $$

The serial fraction \(s\) is:

$$ s = \frac{T_{\text{serial}}}{T_{\text{total}}} = \frac{2}{10} = 0.2 $$

Compute speedup values

We apply Amdahl's Law:

$$ \text{Speedup}(N) = \frac{1}{s + \frac{1 - s}{N}} = \frac{1}{0.2 + \frac{0.8}{N}} $$

We calculate for each \(N\):

• For \(N = 2\):

$$ \text{Speedup}(2) = \frac{1}{0.2 + \frac{0.8}{2}} = \frac{1}{0.2 + 0.4} = \frac{1}{0.6} \approx 1.67 $$

• For \(N = 4\):

$$ \text{Speedup}(4) = \frac{1}{0.2 + \frac{0.8}{4}} = \frac{1}{0.2 + 0.2} = \frac{1}{0.4} = 2.50 $$

• For \(N = 8\):

$$ \text{Speedup}(8) = \frac{1}{0.2 + \frac{0.8}{8}} = \frac{1}{0.2 + 0.1} = \frac{1}{0.3} \approx 3.33 $$

• For \(N = 16\):

$$ \text{Speedup}(16) = \frac{1}{0.2 + \frac{0.8}{16}} = \frac{1}{0.2 + 0.05} = \frac{1}{0.25} = 4.00 $$

Determine asymptotic limits

We find the limits as \(N \to \infty\).
The asymptotic speedup limit is:

$$ \lim_{N \to \infty} \text{Speedup}(N) = \frac{1}{s} = \frac{1}{0.2} = 5 $$

The minimum possible runtime (floor) is:

$$ T_{\text{floor}} = T_{\text{serial}} = 2\text{ minutes} $$

Evaluate upgrade cost-benefit

We analyze upgrading from \(4 \to 16\) workers.

• At \(N = 4\), speedup is \(2.5\).
• At \(N = 16\), speedup is \(4.0\).
• The speedup improvement factor is:

$$ \frac{4.0}{2.5} = 1.6\times $$

• The cost increases by \(4\times\) (\(16\) workers vs \(4\) workers).

Since a \(4\times\) cost increase yields only a \(1.6\times\) speedup, this upgrade is highly inefficient and not worth it for T3 alone.

Answer:

(a) The serial fraction \(s\) is:

$$ s = 0.2 \quad (20\%) $$

(b) Speedup table:

Number of Workers (\(N\))	Speedup
4	\(2.50\)
8	\(3.33\)
16	\(4.00\)

(c) Asymptotic limits:

• Asymptotic speedup as \(N \to \infty\): \(5\)
• Floor on T3 runtime: \(2\text{ minutes}\)

(d) Upgrade evaluation:

• No, it is not worth upgrading. Increasing workers from \(4 \to 16\) increases the resource cost by \(4\times\) but only improves performance by \(1.6\times\) (\(2.5 \to 4.0\) speedup), which is highly cost-inefficient.