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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L_{NE}} is not decidable:

Show some known undecidable language Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \le_m L_{NE}}
Only choice is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H} , language corresponding to the Halting problem.
Show Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H \le_m L_{NE}}

Given arbitrary Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle H} input (program Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P} and input Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P} ), compute Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L_{NE}} input (encoding of program Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P'} such that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P} halts on Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} iff Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P'} halts on at least one input.

Reduction consists of writing code to describe Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P'} :

input: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X'} (ignored)
Call Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P(X)}
return whatever Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F_0 = 0} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F_1 = 1} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F_i = F_{i-1} + F_{i-2}} for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i > 1}

Naïve algorithm

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

Running time is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Theta(\log{n})} time using matrices:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G = (V,E)}

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle V} represents instructions (threads after grouping)
Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle E} represents dependencies between instructions: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (u,v) \in E} means that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle u} must execute before Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (u,v)}

Continuation edge: connects thread Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle u} to successor Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v} within same procedure instance.
Spawn edge: when Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle u} spawns new thread Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v}
Return edge: when Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v} returns control back to its calling procedure Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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.