$\small I(n)$ input of size $\small n$

$\small P(I)$ problem $\small P$ taking input $\small I$

$\small P(n)$stands for$\small P(I(n))$

$\small p$dedicaed parallel processor (we also pay for idle-time)

all start at the same time and end when the last processor finishes

$\small \text{Seq}$ sequential algorithm for specified problem and input

$\small \text{Par}$ parallel algorithm for specified problem and input

$\color{pink}\small \text{Tseq}(n)$ time for $\small 1$ processor to solve $\small P(n)$ using $\small \text{Seq}$

best known worst-case time-complexity (or experimentally measured value)

$\color{pink}\small \text{Tpar}(p,n)$ time for $\small p$ processors to solve $\small P(n)$ using $\small \text{Par}$

$\color{pink}\small = \max_{0\leq i<p} T_i(n)$(alternativelymincan be used)

$\color{pink}\small \text{Wseq}(n) = \text{Tseq}(n)$ total number of executed instructions

$\color{pink}\small \text{Wpar}(n) = \sum_{0\leq i <p} T_i(n)$ by all processors (not including idle / waiting times)

Work of $\small P$ the work of the best possible algorithm.

total time in which the processors are reserved (have to be paid for)

$\color{pink}\small C(n) = p\cdot \text{Tpar}(p,n)$

Usually $\small n$ is kept fixed and $\small p$ gets varied.

• Upper boundary of processors

  Implicitly there is an upper boundary of processors for which it does not make sense to add additional processors.

  1. $\color{pink}\small S_p(n) = c_1\cdot p$

     for some $\small c_1 <1$

  2. $\color{pink}\small S_p(n) = c_2\cdot \sqrt p$

     for some $\small c_2 <1$

Linear speedup $\small S_p(n) \in O(p)$ can not be exceeded.

Perfect speed-up is rare and hardly achievable.

Sometimes we experimentally get super-linear speedup but its because of randomization, non determinism or because algorithms are not comparable (also possible by using caches on multiple processors).

• Proof through contradiction

  Sequential simulation construction

  (Wrongly) assume that we can simulate a parallel algorithm sequentially by:

  1. executing one step of each process, for $\small C(n)$ iterations

  2. all steps of a single process until a communication/synchronization point, then the steps of the next process and so on, ...

  Proof through contradiction

  Assume in $\small \text{Tsim}(n)$ simulates $\small \text{Tpar}(p,n)$

  We know that:

  $\small p \cdot \text{Tpar}(p,n) \geq \text{Tsim}(n)$

  The simulation can not take more time than than$\small p\cdot (\max_{0\leq i<p} T_i(n))$

  To assume that $\small S_p(n) > p$ for some $\small n$ :

  $S_p(n) = \frac{\text{Tseq}(n)}{\text{Tpar}(p,n)} > p$

  implies$\small \small \text{Tseq}(n) > p \cdot \text{Tpar}(p,n)$

  implies$\small \small \text{Tseq}(n) > p \cdot \text{Tpar}(p,n) \geq \text{Tsim}(n)$(see above)

  implies$\small \text{Tseq}(n) > \text{Tsim}(n)$

  Contradiction:

  $\small \text{Tseq}(n) > \text{Tsim}(n)$ would mean, that $\small \text{Tseq}(n)$ is the best known/possible time.

  ---

  Therefore:

  $S_p(n) = \frac{\text{Tseq}(n)}{\text{Tpar}(p,n)} \leq p$

  $\small \small \text{Tseq}(n) \leq p \cdot \text{Tpar}(p,n)$

$\color{pink}\small C(n) = p \cdot \text{Tpar}(p,n) \in O(\text{Tseq}(n))$

has linear speedup.

• Proof

  Cost-optimal algorithm with

  $\small p\cdot\text{Tpar}(p,n) = c\cdot\text{Tseq}(n) \in O(\text{Tseq}(n))$

  implies$\small \text{Tpar}(p,n) = c\cdot\text{Tseq}(n)/p$

  implies$\small S_p(n) = \text{Tseq}(n)/\text{Tpar}(p,n) = p/c$

  The constant $\small c$ stands for the load imbalances and overheads.

  The smaller $\small c$ is, the closer we are to the perfect speed-up.

• Example 1

  For$\small \text{Tseq}(n) \in O(n)$

  any$\small \text{Tpar}(p,n) \in O(n/p)$is cost-optimal.

  Proof:

  $\small \text{Tpar}(p,n) \in O(n/p)$

  implies$\small p \cdot \text{Tpar}(p,n) \in p \cdot O(n/p)$

  implies$\small p \cdot \text{Tpar}(p,n) \in p \cdot O(n/p) \leq p \cdot (c\cdot n/p) = c \cdot n \in O(n)$

  for some constant $\small c$

  implies$\small p \cdot \text{Tpar}(p,n) \in O(n)$

• Example 2

  For$\small \text{Tseq}(n) \in O(n)$

  the parallel time$\small \text{Tpar}(p,n) \in O(n/\sqrt{p})$is not cost-optimal.

  Proof:

  $\small \text{Tpar}(p,n) \in O(n/\sqrt{p})$

  implies$\small p \cdot \text{Tpar}(p,n) \in p \cdot O(n/\sqrt{p})$

  implies$\small p \cdot \text{Tpar}(p,n) \in p \cdot O(n/\sqrt{p})\leq p \cdot (c\cdot n/\sqrt p) = c \cdot n \cdot \sqrt{p} \notin O(n)$

  for some constant $\small c$

  implies$\small p \cdot \text{Tpar}(p,n) \notin O(n)$

• Example 3

  For$\small \text{Tseq}(n) \in O(n)$

  the parallel time$\small \text{Tpar}(p,n) \in O(n/(p/\log p)) = O((n \log p)/p)$is not cost-optimal.

  Proof:

  $\small \text{Tpar}(p,n) \in O(n/(p/\log p)) = O((n \log p)/p)$

  implies$\small p \cdot \text{Tpar}(p,n) \in p \cdot O((n \log p)/p)$

  implies$\small p \cdot \text{Tpar}(p,n) \in p \cdot O((n \log p)/p)\leq p \cdot (c \cdot (n \log p) / p)= c \cdot n \cdot \log p\notin O(n)$

  for some constant $\small c$

  implies$\small p \cdot \text{Tpar}(p,n) \notin O(n)$

$\color{pink}\small \text{Wpar}(n) \in O(\text{Wseq}(n)) = O(\text{Tseq}(n))$

has potential for linear speedup.

• Proof

  Lets say there is a work-optimal algorithm with:

  $\small \text{Tpar}(p,n) = \max_{0\leq i<p} T_i(n)$

  $\small \sum_{0\leq i <p} T_i(n) = \text{Tseq}(n)$

  We schedule $\small \text{Par}$ on a smaller number of processors $\small p'$ in such a way that no processor has any “idle time” (pretty difficult to do this in practice) .

  Then:

  $\small \sum_{0\leq i <p'}T_i(n) = p' \cdot \text{Tpar}(p',n)\in O(\text{Tseq}(n))$

  This way the algorithm is cost-optimal and therefore has linear speedup.

= $\small p$ required to be faster than sequential algorithm.

• Example

  Given $\small \text{DumbSort(n)}$ with $\small T(n)$ that can be perfectly parallalized:

  $\small \text{Tpar}(p, n) \in O(n^2/p)$

  $\small \text{Tseq}(n) \in \theta(n \log n)$

  $\small S_p(n) = \text{Tseq}(n)/\text{Tpar}(p,n) = O(n \log n)/O(n^2/p) = O(p (\log n)/n)$

  • Linear speedup for fixed $\small n$ .

  • Not work-optimal: Speedup decreasing with $\small n$ .

  Break even

  Number of processors for parallel algorithm to be faster than sequential algorithm:

  $\small \text{Tpar}(p,n) <\text{Tseq}(n) \Lrarr n^2/p < n \log n \Lrarr n/p <\log n \Lrarr p > n/\log n$

  $\small \text{Tpar}(p,n) <\text{Tseq}(n) \Lrarr p > n/\log n$

Expresses scalability = how well the processors get utilized.

Relative speedup is good if $\small SRel_p(n) \in \Theta(p)$

Easier to to achieve than absolute.

= smallest possible running-time of $\small \text{Par}$ with arbitrarily many processors

$\small T_\infin(n) = \text{Tpar}(p',n)$

$\color{pink}\small \forall n,p: T_\infin(n) \leq \text{Tpar}(p,n)$

Used in parallelism:

If work-optimal, then absolute AND relative speedup are the same asymptotically:

$\small \text{Tpar}(1,n) = O(\text{Tseq}(n))$

= largest number of processors that can still give linear, relative speedup (adding more processors is pointless)

• Example

  CRCW, Max finding algorithm

  par (0<=i<n) b[i] = true; // set all to true
  par (0<=i<n, 0<=j<n)
  if (a[i] < a[j]) b[i] = false; // set those where a larger one exists to falsepar (0<=i<n)
  if (b[i]) x = a[i];

  $\small \text{Wpar}(p,n) \in O(n^2)$

  $\small \text{Tseq}(n) = \text{Wseq}(n) \in O(n)$(best known sequential algorithm)

  Absolute speedup

  Not work-optimal: $\small \text{Wpar}(n) \notin O(\text{Tseq}(n))$

  $\small S_p(n) = \textcolor{green}{\text{Tseq}(n)}/\text{Tpar}(p,n) = O(\textcolor{green}n)/O(n^2/p) = O(p/n)$

  • Linear absolute speedup for fixed $\small n$ .

  • Absolute speedup decreasing with $\small n$ .

  Break even

  Number of processors for parallel algorithm to be faster than sequential algorithm:

  $\small \text{Tpar}(p,n) <\text{Tseq}(n) \Lrarr n^2/p < n \Lrarr p > n$

  $\small \text{Tpar}(p,n) <\text{Tseq}(n) \Lrarr p > n$

  This is bad! We need as many processors as we the problem size.

  ---

  Relative speedup

  $\small SRel_p(n) =\textcolor{green}{ {\text{Tpar}(1,n)}}/{\text{Tpar}(p,n)} \small = O(\textcolor{green}{n^2}) / O(n^2/p) = O(p)$

  Linear relative speedup.

  Parallelism

  $\small T_\infin(n)= O(1)$

  $\large\frac {\text{Tpar}(1,n)}{\text{T}_\infin(n)} \small = O(n^2) / O(1) = O(n^2)$

  Great parallelism.

  Conclusion: This (terrible) parallel algorithm has

  linear relative speedup for $\small p$ up to $\small n^2$ processors.

= Work that does not have to be done by a sequential algorithm like cooridination (communication, synchronization) and redundant computation.

When there is no overhead we can parallelize perfectly: $\small \text{Tpar}(p,n) = \text{Tseq}(n)/p$

Each Processor has Task $\small T_i(n)$ and Overhead $\small O_i(n)$ in its work:

Therefore

$\color{pink} \small \text{Toverhead}(p, n_i) = \alpha(p) + \beta \cdot n_i$for processor$\small i$:

$\small \alpha(p)$ latency, dependent on $\small p$

$\small \beta \cdot n_i$ cost per data item, that needs to be exchanged by processor $\small i$

for synchronization operations it’s$\small n_i = 0$

If cost-optimal

absolute speedup still is linear (but not perfect)

Differece betweeen max and min work+overhead.

Achieving an even amount of work for all processors $\small i,j$ :

Static, oblivious

Static, problem dependent, adaptive

Dynamic

A)$\small \text{Seq}$ perfectly parallelizable:

B)$\small \text{Seq}$ has a fraction$\small s(n)$ that can’t be parallelized dependens on$\small n$ :

C)$\small \text{Seq}$ has a fraction$\small s$ that can’t be parallelized constant and independent of$\small n$ :

Let program of $\small \text{Seq}$ contain two fractions, independent of $\small n$ :

The maximum achievable speedup (independent of$\small n$) :

• Proof

  $\small \text{Tseq}(n) = (s+r)\cdot \text{Tseq}(n)$

  $\small \text{Tpar}(p,n) = s \cdot \text{Tseq}(n) + \large \frac{r}{p} \small \cdot \text{Tseq}(n)$

  $\small S_p(n) = \text{Tseq}(n) / \text{Tpar}(n)= 1/(s+r/p)$

  $\color{pink}\small S_p(n) = 1/(s+r/p)$

  $\color{pink}\small \lim_{p ~\rarr~ \infin}~~ S_p(n) = 1/s$

We want to avoid Amdahl’s law at all cost.

I/O, initialization of global data structures, shared data structures, everything that takes $\small O(n)$ time and work

Let program of $\small \text{Seq}$ contain two fractions dependent on $\small n$ :

We can therefore reach linear speedup through increasing $\small n$

We get

• Proof

  We know that

  $\small \lim_{n \rarr \infin} t(n) = 0$

  $\color{pink}\small \lim_{n\rarr \infin} \large \frac{t(n)}{T(n)} \small = 0$

  Therefore

  $\small S_p(n) = \large \frac{\text{Tseq}(n)}{\text{Tpar}(p,n)} \small = \large \frac{t(n) + T(n)}{t(n) + T(n)/p} \small = \large \frac{t(n)/T(n) + 1}{t(n)/T(n) + 1/p}$

  $\small \lim_{n\rarr \infin} S_p(n) = \large\frac{0 + 1}{0 + 1/p} \small = \large \large\frac{1}{1/p} \small = p$

  $\color{pink}\small \lim_{n\rarr \infin} S_p(n) = p$

• If the speedup is not linear

  $\small \text{Tpar}(p,n) = t(n) + T(n)/f(p)$

  with $\small f(p) < p$

• using $\small t(n,p)$ instead of $\small t(n)$

  Assuming that the parallel algorithm is work optimal we can allow the non-parallelizable part to depend on $\small p$ :

  $\small t(n,p) \in O(T(n))$for fixed$\small p$

  $\small \text{Tseq}(n) \in O(T(n))$

  $\small \text{Tpar}(p,n) \in O(t(n, p) + T(n)/p)$

$\color{pink}\small T_\infin(n) = t(n)$

$\textcolor{pink}{\small \text{Parallelism} =}\large\frac {\text{Tpar}(1,n)}{\text{T}_\infin(n)} \small = \large \frac{t(n) + T(n)/1}{t(n)} \small = \textcolor{pink}{1+T(n)/t(n)}$

A small $\small t(n)$ relative to $\small T(n)$ means large parallelism.

$\small C(n) = p\cdot \text{Tpar}(p,n) = p \cdot t(n) + T(n)$

$\small W \in O( p \cdot \text{Tpar}(p,n))$

Assume

then

Ratio of perfect parallel time / actual parallel time

Ratio of sequential cost / parallel cost

$\small \textcolor{pink}{E(p,n)} = \large \frac{\text{Tseq}(n) \textcolor{pink}{/p}}{\text{Tpar}(p,n)} \small = S_p(n) /p = \large\frac{\text{Tseq}(n)}{\textcolor{pink} p \cdot \text{Tpar}(p,n)}$

• $\small E(p,n) \leq 1$

  because$\small S_p(n) = \large \frac{\text{Tseq}}{\text{Tpar}(p,n)} \small \leq p$

• $\small E(p,n) = c$(constant)

  has a linear speedup (because cost-optimal algorithms have constant efficiency)

increasing the problem size $\small n$ with the number of processors $\small p$

using the iso-efficiency function.

Parallel algorithm scales weakly relative to sequential algorithm

if there is a slowly growing iso-function$\small f$ such that:

The growth of $\small f$ is given by the input-size-scaling-function$\small g$ .

Exception to this rule:

Algorithm is strongly scalable if $\small f(p) = O(1)$ .

• Example 1

  What we know:

  • $\small \text{Tpar}(p,n)\in O(\large{\frac{n^2}{p}} \small + (\log n)^2)$

  • $\small \text{Tseq}(n) \in O(n^2)$

  • $\small \text{Wpar}(n) = \sum_{0\leq i <p} T_i(n)\in O(\text{Tseq}(n))$because work optimal

  We want to get a constant efficiency $\small e$as$\small E(p,n)$:

  $\small e = \large\frac{\text{Tseq}(n)}{\textcolor{pink} p \cdot \text{Tpar}(p,n)} \small = \large \frac{n^2}{\textcolor{pink}p \cdot ({\frac{n^2}{p}} + (\log n)^2)} \small = \large \frac{n^2}{n^2 +p\cdot (\log n)^2}$

  $\small e = \large \frac{n^2}{n^2 +p\cdot (\log n)^2}$

  $\small e \cdot (n^2 +p\cdot (\log n)^2)= n^2$

  $\small e \cdot n^2 +e \cdot p\cdot (\log n)^2= n^2$

  $\small e \cdot p\cdot (\log n)^2= n^2 - e \cdot n^2$

  $\small e \cdot p\cdot (\log n)^2= n^2 \cdot (1 - e)$

  $\cdots$$\small O$constants normalized to 1

  $\large \frac{n}{\log n}\small = \sqrt{e/(1-e)} \cdot \sqrt{p}$

  This means we can maintain efficiency, at least $\small e$ , if:

  $\large \frac{n}{\log n}\small \geq \sqrt{e/(1-e)} \cdot \sqrt{p}$

• Example 2

  What we know:

  • $\small \text{Tpar}(p,n)\in O(\large{\frac{n^2}{p}} \small + (\log \textcolor{green} p)^2)$

  • $\small \text{Tseq}(n) \in O(n^2)$

  • $\small \text{Wpar}(n) = \sum_{0\leq i <p} T_i(n)\in O(\text{Tseq}(n))$because work optimal

  We want to get a constant efficiency $\small e$as$\small E(p,n)$:

  $\small e = \large\frac{\text{Tseq}(n)}{\textcolor{pink} p \cdot \text{Tpar}(p,n)} \small = \large \frac{n^2}{\textcolor{pink}p \cdot ({\frac{n^2}{p}} + (\log \textcolor{green} p)^2)} \small = \large \frac{n^2}{n^2 +p\cdot (\log \textcolor{green} p)^2}$

  $\small e = \large \frac{n^2}{n^2 +p\cdot (\log \textcolor{green} p)^2}$

  $\small e \cdot (n^2 +p\cdot (\log \textcolor{green} p)^2)= n^2$

  $\small e \cdot n^2 +e \cdot p\cdot (\log \textcolor{green} p)^2= n^2$

  $\small e \cdot p\cdot (\log \textcolor{green} p)^2= n^2 - e \cdot n^2$

  $\small e \cdot p\cdot (\log \textcolor{green} p)^2= n^2 \cdot (1 - e)$

  $\cdots$$\small O$constants normalized to 1

  $\small n = \sqrt{e/(1-e)} \cdot \sqrt{p \log p}$

  This means we can maintain efficiency, at least $\small e$ , if:

  $\small n \geq \sqrt{e/(1-e)} \cdot \sqrt{p \log p}$

• Comparision of examples

  Both kinds of algorithms occur frequently, none of them is easier to handle than the other.

  Example 1)

  $\small \text{Tpar}(p,n)\in O(\large{\frac{n^2}{p}} \small + (\log n)^2)$

  $\large \frac{n}{\log n}\small \geq \sqrt{e/(1-e)} \cdot \sqrt{p}$

  parallel overhead = a function of problem size

  Example 2)

  $\small \text{Tpar}(p,n)\in O(\large{\frac{n^2}{p}} \small + (\log \textcolor{green} p)^2)$

  $\small n \geq \sqrt{e/(1-e)} \cdot \sqrt{p \log p}$

  parallel overhead = a function of number of processors, caused by parallelization alone

= absolute speedup

Assumes that $\small \text{Tseq}(n)$ can be measured.

Not the case for very large $\small n,p$ .

Goal: running larger problem in same amount of time.

Weakly scalable if $\small \text{Tpar}(p,n)$ remains constant for non scaled input.

Goal: running same problem size faster.

Strongly scalable up to $\small \text{Prallelism}$ -cores if $\small \text{Tpar}(p,n)$ decreases proportionally to $\small p$ .

Means linear speedup $\small S_p(n) \in \Theta(p)$ independently of sufficiently large $\small n$ .