Introduction
Serial Computing
- Divide problem into discrete instructions
- Execute instructions in sequence, one at a time
Memory wall: Disparity between processor (1ns) and memory speed ($\approx$ 100 to 1000ns)
PU is based on von Neumann model.
- Higher clock freq (Work hard)
- Pipelining, superscalar (Work smart)
- Multicore, cluster (Get help)
Parallel Computing
| |
Concurrency |
Parallelism |
| $>=2$ tasks |
Start/Run/Complete in overlapping periods |
Execute simultaneously |
| Progress via |
Interleaving their execution periods |
Running at the same time |
Motivation:
- Overcome serial computing limits
- Speedup/Save time
- Utilizing non-local resources
- Cost-saving
- Overcome memory constraints
Parallel Computing Approach
Parallel solution: Sum of $n$ numbers
- $p$ cores
- $n$ numbers
- Each core partial sum of $n/p$ numbers
- Master core adds up all values
- Optimization:
- neighboring cores add up values ($\log(p)$ iterations, each taking $O(1)$ time)
Misc
Supercomputer:
- computer performing at the highest operational rate for computers.
- many PUs with many nodes and memory spaces
- uses parallel processing to communicate and solve problems