Computational complexity of multithreaded algorithms

Multi-core architecture

Possible problems:

• deadlocks (happen under Coffman conditions): processes wait for each other
• livelock: processes loop in useless work
• starvation: processes don’t get to use some resource
• race conditions: operations must be done in proper sequence

Race conditions

Leading to non-deterministic results
Solution - low-level synchronization mechanisms:

• monitor: ability of waiting/blocking based on condition
• semaphore: counting variable controlling access to resource
• atomic operations: program operations that cannot be preemptied

Dynamic threads

New constructs: Parallel, Spawn, Sync

Computational complexity analysis of multithreaded model

Assuming constant time for thread spawning and scheduling

• complexity (total time) ~ span: critical/longest path in execution graph
• work (time of parallel threads) ~ $\sum$ of all calls

$P$ … number of processors
$T_P$ … time using $P$ processors ($T_1$ … time of sequential processing, $T_{\infty }$ … time using unlimited number of processors)
$S$ … speedup, $S_p=\frac{T_1}{T_P}$ … speedup using $P$ processors

(Same work, but only max() of times)

Fibonnaci

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

Limits of parallelization

Amdahl’s law

Viewing single problem
$S=\frac{T_1}{T_P}$ … speedup

$$S=\frac{T_1}{f\ast \frac{T_1}{P}+(1-f)\ast T_1}=\frac{1}{\frac{f}{P}+(1-f)}$$

$f$ … proportion of parallelizable code

Gustafson’s law

View more/larger problems with more available processors
$T_1=a+P\ast b$ ; $a$ … sequential time, $b$ … parallel time
$\alpha$ … sequential share of work, $1-\alpha$ … share of parallel work

$$S_p=\frac{T_1}{T_P}=\frac{a+Pb}{a+b}=\frac{a}{a+b}+\frac{Pb}{a+b}=\alpha +P(1-\alpha )=P-\alpha (P-1)$$