0%

DSPC note

第一章

  • B, Bridge, 存储器总线和I/O总线间的接口
  • DIR, Cache Directory, 高速缓存目录
  • IOB, IO Bus, I/O 总线
  • LD, Local Dosk, 本地磁盘
  • MB, Memory Bus, 存储器总线
  • NIC, Network Interface Circuitry, 网络接口电路
  • P/C, Microprocessor and Cache, 微处理器和高速缓存
  • VP, Vector Processor, 向量处理器
  • SM, Shared Memory, 共享存储器
  • LM, Local Memory, 本地存储器

大型并行计算机系统有

  • SIMD, Single-Instruction Multiple-Data, 单指令多数据流

  • PVP, Parallel Vector Processor, 并行向量处理机

  • SMP, Symmetric Multiprocessor, 对称多处理机

    • 每个处理器可同等地访问共享存储器, IO设备和操作系统服务
    • 单地址空间, OS 容易调度
    • 处理器不能太多
    • 总线和交叉开关互连一旦做成也难以扩展
  • MPP, Massively Parallel Processor, 大规模并行处理机

    • 能扩放至上万个处理器
    • 程序由多个进程组成, 每个都有其私有地址空间, 进程间采用传递消息机制相互作用
    • 高带宽低延迟互连网络
  • DSM, Distributed Shared Memory, 分布共享存储多处理机

    • DIR 支持分布 cache 的一致性
    • 与 SMP 相比, 物理上有分布在各节点中的局存, 形成共享存储器
    • 单一地址编程空间, 比 MPP 编程容易
  • COW, Cluster of Workstations, 工作站机群

    • 每个节点都是一个完整的工作站 (PC, SMP)
    • 标准网络 (MPP DSM 为定制网络)
    • 网络接口松散 (MPP紧耦合, 网络连到节点 MB)
    • 每个节点都有完整操作系统

访存模型

  • UMA, Uniform Memory Access, 均匀存储访问
    • 物理存储器被所有处理器均匀共享
    • 处理器访问任何存储单元的时间均相同
    • 每台处理器可带私有 cache
  • NUMA, NonUMA, 非均匀存储访问
    • 被共享的存储器物理上分布在所有处理器中
    • 所有本地存储器的集合构成全局地址空间
    • 处理器访问存储单元的时间不同
  • COMA, Cache Only MA, 全高速缓存存储访问
    • NUMA 的一个特例
    • 全部 cache 组成全局地址空间
  • CC-NUMA, Coherent-Cache NUMA, 高速缓存一致性非均匀访问
    • 将一些 SMP 作为单节点彼此连接
  • NORMA, No-Remote MA, 非远程存储访问
    • 所有存储器都是私有的, 仅由其处理器访问

第二章

静态互连网络

动态互连网络

第三章

第一章

第四章

加速比

并行系统的加速(比): 对于一个给定的应用, 并行程序的执行速度相对于串行程序的执行速度加快了多少倍.

$p$ 处理器数
$W = W_{series} + W_{parallel}$ 问题规模
$f = W_s / W$ 串行分量比例
$1 - f$ 并行分量比例
$T_s$ 串行执行时间
$T_p$ 并行执行时间
$S$ 加速比

Amdahl 定律

固定计算负载, 提高速度, 可增大 $p$​

$S = \frac{W_s+W_p}{W_s+W_p/p} =\frac{ f + (1-f)}{f+\frac{1-f}{p}} = \frac{p}{1+f(p-1)} \rightarrow\frac{1}{f}$​

即假设 $f=0.5$, 即使 $p$ 无限大, 加速上限为 2 倍.

若考虑额外开销 $W_o$

$S = \frac{W_s+W_p}{W_s+W_p/p+W_o} = \frac{p}{1+f(p-1)+W_op/W} \rightarrow\frac{1}{f+W_o/W}$

串行分量和并行额外开销越大, 加速越小

Gustafson 定律

可扩放问题. 提高精度, 增大计算量(问题规模). 认为增多处理器必须相应地增大问题规模才有意义.

$S’ = \frac{W_s+pW_p}{W_s+pW_p/p} =p-f(p-1)$

当 $p$ 充分大, $S’$ 与 $p$ 呈线性关系, 斜率为 $1-f$

若考虑额外开销 $W_o$

$S’ = \frac{W_s+pW_p}{W_s+pW_p/p+W_o} =\frac{f+p(1-f)}{1+W_o / W}$

Sun and Ni 定律

受限于存储器. 认为只要存储许可, 应尽量增大问题规模.

设单节点使用全部存储 $M$ 求解 $W = fW +(1-f)W$.

$p$ 个节点存储为 $pM$, 设 $G(p)$ 为存储增加到 $p$ 倍时负载的增加量, 则 $W = fW + (1-f)G(p)W$

$S’’ = \frac{fW + (1-f)G(p)W}{fW + (1-f)G(p)W /p} = \frac{f + (1-f)G(p)}{f + (1-f)G(p) /p}$

若考虑额外开销 $W_o$

$S’’ =\frac{f + (1-f)G(p)}{f + (1-f)G(p) /p+W_o / W}$​

  • 当 $G(p)$ = 1, 变为 Amdahl
  • 当 $G(p)$​ = $p$, 变为 Gustafson

一般 $\frac{p}{\log p} \le S \le p$

可扩放性

区别于加速比的另一种性能指标: 性能随 $p$ 的增加而按比例提高的能力.

衡量程序能否有效利用扩充的处理器.

等效率度量标准

$t_e^i$ 第 $i$ 个处理器的有用计算时间
$t_o^i$ 第 $i$ 个处理器的额外开销时间
$T_p = t_e^i + t_o^i = (T_e + T_o) / p$ 处理器并行算法运行时间
$W = T_e = \sum\limits_{i=0} ^{p-1} t_e^i$ 问题规模, 工作负载, 最佳串行算法所完成计算量
$S = \frac{T_e}{T_p} = \frac{p}{1+\frac{T_o}{W}}$ 加速
$E=\frac{S}{p} = \frac{1}{1+\frac{T_o}{W}}$ 效率

为了维持 $E$​ 不变, 需在增大 $p$​ 的同时增大 $W = f_E(p)$​

若 $W$ 随 $p$ 线性或亚线性增长, 则算法具有良好的可扩放性.

若 $W$ 随 $p$ 指数等快速增长, 则算法不可扩放.

等速度度量标准

速度能以处理器数的增加而线性增加(平均速度不变), 则可扩放性好.

速度 $V = W / T$

平均速度 $\bar{V} = \frac{V}{p} = \frac{W}{pT}$​

定义标准 $\Psi(p,p’) = \frac{W/p}{W’/p’}\in(0,1)$​​, 越大可扩放性越好.

若平均速度保持不变, $\Psi = T/T’$

$\Psi(1,p’) = \frac{T_1}{T_p’}=\frac{W}{W’/p’} = \frac{解决工作量为 W 的问题所需串行时间}{解决工作量为 W 的问题所需并行时间}$

平均延迟度量标准

$T_i$: $p_i$ 的执行时间, 包括运行时导致的延迟 $L_i$

定义系统平均延迟时间 $\bar{L}(W,p) = \sum\limits_{i=1}^p(T_{para} - T_i + L_i) / p = T_{para} - T_{series} / p$

定义标准 $\Phi(E,p,p’)=\frac{$\bar{L}(W,p)}{$\bar{L}(W’,p’)} \in (0,1)$, 越大可扩放性越好.

第五章

对比于串行计算的冯诺依曼模型, 并行计算有以下模型

PRAM

Parallel Random Access Machine

并行随机存取机器

共享存储的 SIMD 模型

在任何时刻各处理器均可通过共享存储单元相互交换数据

PRAM-EREW

PRAM Exclusive-Read and Exclusive-Write

不允许同时读和同时写的 PRAM

PRAM-CREW

PRAM Concurrent-Read and Exclusive-Write

允许同时读和同时写的 PRAM

PRAM-CRCW

PRAM Concurrent-Read and Concurrent-Write

允许同时读和同时写的 PRAM

然而允许同时写不现实

  • 只允许同时写相同的数 CPRAM-CRCW Common
  • 只允许最优先的处理器先写 PPRAM-CRCW Priority
  • 允许任意处理器自由写 APRAM-CRCW Arbitrary

$T_{EREW} \ge T_{CREW} \ge T_{CRCW} $

$T_{EREW} = O (T_{CREW}) \cdot \log p = O (T_{CRCW}) \cdot \log p$

EREW 是最慢的

APRAM

异步 Asynchronous PRAM

每个处理器都有局存, 局部时钟和局部程序. 通过共享全局存储通信.

无全局时钟, 各处理器异步独立执行各自指令

时间依赖关系需明确在各程序中加入同步路障

指令:

  • 全局读: 全局存储->读入->局存
  • 局部操作: 计算, 改写局存
  • 全局写: 局存->写入->全局存储
  • 同步: 等待别的处理器到达
p1 p2 pn
phase1 read x1 read x3 read xn
read x2 * *
* write to B *
write to A write to C write to D
同步障 同步障 同步障
phase2 read B read A read C
同步障 同步障 同步障
phase3

$T = \Sigma ~每个~phase~的小霸王时间 + 同步障时间~ B \times 同步障次数 $

BSP

Bulk Synchronous Parallel

计算由一系列用全局同步分开, 周期为 L 的超级步组成

各超级步中每个处理器执行局部计算, 并通过选路器接发信息. 然后作一全局检查看是否所有处理器都已完成.

分布存储的 MIMD