# 第五章(上)-并行算法设计
芝麻开花节节高
# Embarrassingly Computations
Embarrassingly parallel 表示一个 computation 能够被分成 完全独立 的任务。
# Load Balancing & Termination
定义：表示将 computations 平均的分配给多处理器，以获得最高的执行速度。
Termination 检测
- 检测 computations 何时完成
- computations 为分布式时，终结检测更困难
# Static Load-Balancing
静态负载均衡：提前将任务分配给多处理器。
【TODO：以下三个待进一步分析，用实例分析】- Round robin algorithm: selects processes in turn
- Randomized algorithms: selects processes randomly
- Recursive bisection - recursively divides the problem into sub-problems of equal computational effort
# Dynamic Load-Balancing
动态意味着：
- 在运行时分配任务给多处理器
- 在运行时会出现额外的开销，但是比静态负载均衡的效率要高很多
方法有：
【TODO：以下三个待进一步分析】- Centralized Work Pool
- Decentralized Work Pool
- Fully Distributed Work Pool
# Divide-And-Conquer Computations
Recursively divide a problem into sub-problems that are of the same form as the larger problem.
递归的将一个问题分解为一些列的与原问题形式相同的子问题，然后解决子问题，合并结果就解决了原问题。
分而治之，是一种十分常见的解决问题的思想方法。但并不是所有问题都适用，因为分解之后的子问题要与原问题形式一致。
# Pipelined Computations
流水线计算。
# Synchronous Computations
# 参考资料
Introduction parallel computing tutorial (opens new window)
台湾新竹清华大学 平行程式 (opens new window)