CPS 1 - Spring, 1997 - Ramm 4/21/97 #37
- Announce
- Read Chapter 13, Noncomputability
- Missing a textbook?
Chapter 12. Parallel Computation
- Limitation on Processor Speed
- Speed of Light
- 1 foot = 1 nano-second
- Make Smaller
- Heat Dissipation
- Memory Size
- Limitation on Processor Speed
- Manufacturing Problems with Small Sizes
- Feature size < wavelength of light
- UV, X-ray
- Got to lower voltages
- Ultimately Parallelism is Only Hope
- Forms of Parallelism
- Word Size
- Pipe Line
- Assembly Line for Instructions
- Multiprocessors
- Networks of Processors
- Internet
- What can we do with 100 processors in a row?
- 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?
- Speedup
defined
- Apparent for N <= # Processors
- Still really t = A * N, but N is up to 100 times smaller
- Even with optimal speedup
- no huge help for NP programs
- either impossibly large number of processors or just cut A by some factor
- t = (A/k)*N
- Communicating Processes
- Imagine Sorting of 100 Items
- Synchronization Problems
- Assembly Line for Instructions
- Shared resources
- Shared information
- Sort Speed Up
- Work by Committee
- Variations on Architecture
- Bus
- Ring
- Grid
- Hypercube
- Complete Connection
- Tightly Coupled
- Loosely Coupled
- length of path between nodes
- Parallel Processing a Difficult Area
- Special Applications Work Quite Well
- General Results Hard to Come By
- Speedup Disappointing