Outline:
1. General speedup formula
2. Amdahl's Law
3. Gustfson-Barsis' Law
4. Karp-Flatt metric
5. Isoefficiency metric
General speedup formula:
※ Inherently sequential computations : δ(n)
※ Potentially parallel computations : φ(n)
※ Communication operations : k(n,p)
Amdahl's Law:
f-sequential(serial) p-processors
The Limitation of Amdahl's Law: ignores overhead associated with the introduction of parallelism.(忽略了引入并行性所带来的开销)
Amdahl's Effect: Speedup is usually an increasing function of the problem size for a fixed number of processors.（对于固定数量的处理器，加速比是问题规模的增函数）
Amdahl's Law assumes that minimizing execution time is the focus of parallel computing.(Amdahl定律假设并行计算的主要目标是缩短执行时间)
Gustafson-Barsis's Law
(Amdahl定律从串行程序开始，通过预测其在多个处理器上的计算速度来确定加速比。Gustafson-Barsis定律正好相反。从并行程序出发，估计并行计算比在单处理器上执行同样的计算可以快多少)
Karp-Flatt metric
Experimentally Determined Serial Fraction -- 实验决定的串行比例
* Takes into account parallel overhead
* Detects other sources of overhead or inefficiency ignored in speedup model （发现并行程序执行模型中所忽略的其他开销的来源）
* Process startup time
* Process synchronization time
* Imbalanced workload
* Architectural overhead
(由于实验确定的串行部分比例并没有随着处理器的个数增加而增加。可以看出性能不好的主要原因是有限的并行性，即大部分计算是本质上的串行)
（由于实验确定的串行部分的比例随着处理器的个数增加而稳定增加，可以看出加速比差的主要原因是并行开销。这可能是由于进程启动、通信或同步所需的时间，或是由于系统结构上的限制）
Isoefficiency metric
* Parallel system: parallel program executing on a parallel computer
* Scalability of a parallel system: measure of its ability to increase performance as number of processors increases
* A scalable system maintains efficiency as processors are added
* Isoefficiency: way to measure scalability
Isoefficiency Derivation Steps
Begin with speedup formula
Compute total amount of overhead
Assume efficiency remains constant
Determine relation between sequential execution time and overhead
Scalability Function
Suppose isoefficiency relation is n >= f(p)
Let M(n) denote memory required for problem of size n
M(f(p))/p shows how memory usage per processor must increase to maintain same efficiency
We call M(f(p))/p the scalability function
Meaning of Scalability Function
To maintain efficiency when increasing p, we must increase n
Maximum problem size limited by available memory, which is linear in p
Scalability function shows how memory usage per processor must grow to maintain efficiency
Scalability function a constant means parallel system is perfectly scalable
KEY TERMS
Amdahl effect -- Amdahl效应
Amdahl's Law -- Amdahl定律
efficiency -- 效率
experimentally determined serial fraction -- 实验确定串行比例
Gustafson - Barsis's Law
isoefficiency relation -- 等效关系
Karp - Flatt metric -- ... 度量
parallel system -- 并行系统
scalability -- 可扩展性
scalability function -- 可扩展函数
scaled speedup -- 比例加速比
speedup -- 加速比
