CSCE 411 Lecture 36

Lecture Slides

« previous | Wednesday, November 21, 2012 | next »

Happy Thanksgiving!

Undecidability

Some problems (like the Halting problem) just cannot be solved.

Undecidable Set: A set that no program can determine whether a candidate is a member or not.

Example Reduction

Consider language $L_{NE}$ of strings that encode a program that halts (i.e. doesn't go into infinite loop).

Use reduction to show that $L_{NE}$ is not decidable:

• Show some known undecidable language $\leq _{m}L_{NE}$
• Only choice is $H$, language corresponding to the Halting problem.
• Show $H\leq _{m}L_{NE}$

Given arbitrary $H$ input (program $P$ and input $X$ for $P$), compute $L_{NE}$ input (encoding of program $P'$ such that $P$ halts on $X$ iff $P'$ halts on at least one input.

Reduction consists of writing code to describe $P'$:

• input: $X'$ (ignored)
• Call $P(X)$
• return whatever $P$ returns

Properties about Programs

set of strings that encode programs.

property corresponds to whatever programs have in common (e.g. terminates in 10 steps for input $y$).

property called functional if it refers to the language accepted by program and not about program code itself:

• not functional: terminates in 10 steps for input $y$
• functional: program never goes into an infinite loop

functional probability is nontrivial if some programs have property and others do not

• nontrivial: program accepts a finite number of strings
• trivial: program accepts 0 or more inputs

Rice's Theorem

Every nontrivial (functional) property about programs is undecidable.

Implication: To show that some property is undecidable, we only need to show that it is nontrivial and functional, then appeal to Rice's theorem.

Consider property "program accepts a finite number of strings".

• functional (about language and not about code)
• nontrivial (some programs accept a finite number of strings, others do not)
• therefore not possible to design algorithm to determine.

Multithreaded Algorithms

Lecture Slides

Last regular topic before final

We've discussed serial algorithms that are suitable for running on a uniprocessor computer. Let's look at parallel algorithms that can run on multiprocessor computers.

Computational Model

Currently many different competing models: We'll focus on one with shared memory

Dynamic Multithreading

difficult and error-prone:

• difficult to partition work equally
• competition over resources (race conditions, deadlock)

Concurrency platform: software layer that manages parallel-computing reources. We'll use similar concept:

simple extension of serial programming model that has concurrency instructions parallel, spawn, and sync

• spawn: If spawn proceeds a procedure call, then the procedure instance that executes the spawn (parent) continues to execute in parallel with the spawned subroutine (child) instead of waiting for child to complete.
  • Does not say that procedure must execute concurrently, but simply that it may.
  • scheduler decides which subcomputations run concurrently.
• sync: procedure must wait for all spawned children to complete.
• parallel: many algorithms contain loops, where all iterations can operate in parallel. This keyword indicates that loop body can be executed in parallel.

Fibonacci Numbers

"NOT how you want to compute Fibonacci numbers"

Defined by recurrence $F_{0}=0$, $F_{1}=1$, $F_{i}=F_{i-1}+F_{i-2}$ for $i>1$

Naïve algorithm

def fib n
  return n if n < 2
  fib(n-1) + fib(n-2)
end

Running time is $T(n)=T(n-1)+T(n-2)+\Theta (1)\in \Theta \left(\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}\right)$

Can be computed in $\Theta (\log {n})$ time using matrices:

${\begin{pmatrix}1&1\\1&0\end{pmatrix}}^{n}={\begin{pmatrix}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{pmatrix}}$

but we'll just try to make the stupid algorithm faster with multithreading:

def fib_t n
  return n if n < 2
  x = spawn fib n-1
  y = spawn fib n-2
  sync
  x+y
end

Now it takes up an exponential number of processors and memory...

Computation DAG

Computing the 4^th Fibonacci number using the multithreaded naïve algorithm.

Multithreaded computation can be understood better with help of computation DAG $G=(V,E)$

• $V$ represents instructions (threads after grouping)
• $E$ represents dependencies between instructions: $(u,v)\in E$ means that $u$ must execute before $v$
• Group instructions into threads:
  • A sequence of instructions containing no parallel control (spawn, sync, return from spawn, parallel) can be grouped into a single strand
  • strand of maximal length is thread

Edge classification: $(u,v)$

• Continuation edge: connects thread $u$ to successor $v$ within same procedure instance.
• Spawn edge: when $u$ spawns new thread $v$
• Return edge: when $v$ returns control back to its calling procedure $u$

Going back to Fibonacci example,

def fib_t n
  return n if n < 2 # thread A
  x = spawn fib n-1
  y = spawn fib n-2 # thread B
  sync
  x+y               # thread C
end

Threads with no edges between them can be run in parallel.