CSCE 411 Lecture 37

Lecture Slides

« previous | Monday, November 26, 2012 | next »

Multithreaded Algorithms

Measuring Performance

work

total time to execute the entire computation on a single processor

equal to sum of times taken by each thread

span

longest time to execute threads along any path of computational DAG

Running time depends on number of processors and how scheduler allocats strands to processors:

• $T_{1}$ is running time on single processor (work)
• $T_{P}$ is running time on $P$ processors
• $T_{\infty }$ is running time for as many processors as needed (span)

Example

On Fibonacci example, assuming unit time for each thread,

• work = 17 time units
• span = 8 time units

Work Law

An ideal parallel computer with $P$ processors can do at most $P$ units of work. The total work to do is $T_{1}$.

$T_{P}\geq {\frac {T_{1}}{P}}$

Span Law

A $P$-processor ideal parallel computer cannot run faster than a machine with an unlimited number of processors.

However, a computer with unlimited processors can emulate a $P$-processor machine by only using $P$ of its processors

$T_{P}\geq T_{\infty }$

Speedup and Parallelism

speedup

${\frac {T_{1}}{T_{P}}}$

parallelism

${\frac {T_{1}}{T_{\infty }}}$

Greedy Scheduler

Assigns as many strands to processors as possible

$T_{P}\leq {\frac {T_{1}}{P}}+T_{\infty }$

Vocabulary:

complete step

at least $P$ strands are ready to execute on $P$ processors

incomplete step

not a complete step.

Proof

In each complete step, $P$ processors perform a total of $P$ work. Assume number of complete steps exceeds ${\tfrac {T_{1}}{P}}$, then total work is

${\begin{aligned}P\left(\left\lfloor {\frac {T_{1}}{P}}\right\rfloor +1\right)&=P\left\lfloor {\frac {T_{1}}{P}}\right\rfloor +P\\&=T_{1}-\left(T_{1}\mod {P}\right)+P\\&>T_{1}\end{aligned}}$

CONTRADICTION: This exceeds the total work required by the computation.

In each incomplete step,

let $G'$ be the subgraph of the computation DAG $G$ that has yet to be executed at the start of an incomplete step, and

let $G''$ be the subgraph that will be remaining to be executed at the end of an incomplete step.

Longest path ind DAG must start at vertex with in-degree 0 (otherwise just follow in-edge to new start of longer path).

Greedy scheduler executes all nodes in $G'$ with in-degree 0, and so the longest path in $G''$ will be 1 less than the longest path in $G'$.

In other words, an incomplete step reduces span of DAG by 1, so number of incomplete steps is at most $T_{\infty }$.

Since each step must either be complete or incomplete, Q.E.D

Q.E.D.

Corollary

Greedy scheduler performance is within a factor of 2 of $T_{P}^{*}$, the running time of an optimal scheduling:

$T_{P}\leq {\frac {T_{1}}{P}}+T_{\infty }\leq 2\max {\left({\frac {T_{1}}{P}},T_{\infty }\right)}\leq 2T_{P}^{*}$

Slackness

ratio of parellelism by $P$:

${\frac {\frac {T_{1}}{T_{\infty }}}{P}}$

If slackness is less than 1, we can't hope to achieve linear speedup

Work of Fibonacci

$T_{1}=\gamma ^{n}$, where $\gamma ={\tfrac {1+{\sqrt {5}}}{2}}$ is the golden ratio.

Span: $T_{\infty }(n)=\max {(T_{\infty }(n-1),T_{\infty }(n-2))}+\Theta (1)\in \Theta (n)$

Parallelism: $\Theta \left({\tfrac {\gamma ^{n}}{n}}\right)$