• Read Chapter 14, Parallel Computation
• Begin to read Chapter 15, Noncomputability
• Quiz Today

• t = A * N * log(N)
• logarithmic behavior

• Note: here N is number of moves looking ahead.
• We Have an Algorithm!
• Layers of look ahead: If I do this, then he does this, ....
• Problem Solved (?!)
• Can Represent Possibilities by Tree
• Assume 10 Possibilities Each Move
• t = A * 10^N
• !!!!
• Exponential
• Sample Numbers

• Visit N Cities in Optimal Order
• Optimal By:
  • time
  • distance
  • cost
• N factorial (N!) Possibilities
• Look at Table
• N! is roughly N^N
• Typical of some very practical problems

3	2! = 2		5	4! = 24
abc			abcde
acb 			abced
			abdce
4	3! = 6		abdec
abcd			abecd
abdc			abedc
acbd		
acdb			acbde
adbc			acbed
adcb 			acdbe
			acdeb
			acebd
			acedb
		
			adbce
			adbec
			adcbe
			adceb
			adebc
			adecb

			aebcd
			aebdc
			aecbd
			aecdb
			aedbc
			aedcb

	t = 5.49 * 10**-3 * 2**n
n	t
5	.17s
10	5.62s
15	3.00m
20	1.6h
25	2.13d
30	68.23d
35	5.98y
40	191.3y
45	6120.y
50	196K y
55	6.27M y
60	201M y
65	6.42G y
70	205G y

• Speed of Light
  • 1 foot = 1 nano-second
  • Make Smaller
  • Heat Dissipation
• Memory Size

• Manufacturing Problems with Small Sizes
  • Feature size < wavelength of light
  • UV, X-ray
  • Got to lower voltages

• Word Size
• Pipe Line
  • Assembly Line for Instructions
• Multiprocessors
• Networks of Processors
• Internet

• search: "Is name x in the list of 100 names?"
• can get constant time algorithms
• e.g. do you have a match?
• Curve?
• What about 200 names?
• 500 names?

• Speed for K Processor / Speed for 1 Processor
• What is the best you would expect?
• What is the worst?

• Apparent for N <= # Processors
• Still really t = A * N, but N is up to 100 times smaller

• no huge help for exponential programs
• either impossibly large number of processors or just cut A by some factor
• t = (A/k)*N

• Imagine Sorting of 100 Items
• Synchronization Problems
  • Assembly Line for Instructions
  • Shared resources: Deadlocks
  • Shared information: Race Conditions

• From N log N
• To N

• Bus
• Ring
• Grid
• Hypercube
• Complete Connection

• Tightly Coupled
• Loosely Coupled

• length of path between nodes

• Special Applications Work Quite Well
  • Array Processing
• General Results Hard to Come By
• Speedup Disappointing