并行计算机体系结构笔记

这是本学期的第一门闭卷考试，部分内容由我的研究生导师陈衡主讲，整理一下笔记。

其实之前和老师每周对话的时候问了一下，老师说师兄们去年都考得挺好的，那可能我也能考好。

---

一、概述

计算机技术的发展需要计算机系统结构、硬件、软件、编程语言、高效应用算法通信技术等多方面发展。要改善计算机系统的性能，可以使用更合理、更快的硬件，也可以优化解决计算任务的算法，还可以使用多处理器计算机来解决特定任务。

硬件是物质基础，也是改善计算机性能最关键的因素，随着微电子技术的发展，芯片的集成度和处理速度日新月异。而计算机系统结构是改善计算机性能的极其重要因素，通过合理的新方法设计和构成综合性能指标最佳的计算机系统，可以最大限度地发挥硬件的内在潜力。

如果说硬件决定了计算机性能的上限，那么计算机系统结构则使得计算机的实际性能向着这个上限去逼近。

如何才能使计算机获得更强的计算能力？一方面当然是从硬件角度，增加处理器和存储部件的速度，但这会受到光速、热力学定律、处理器制造工艺以及制造成本的限制；另一方面，可以采用并行处理技术，连接多个处理器，使用它们合在一起的并行计算能力。

并行处理技术可以构建高性能的计算机。

时间并行的角度上，流水线技术使得功能部件得到充分利用，提高吞吐率，提高 n 个类似任务的处理速度。

空间并行角度上，超标量和多处理机技术使得各部件并行协同工作，将一个任务划分成 n 个子任务/协同处理，提高一个任务的处理速度。

并行处理技术可以很好地解决单个处理器瓶颈问题。

单核中性能变为原来的两倍，耗能变为原来的四倍。而多核可以在获取同样性能的同时，减少能量损耗。

全球高性能计算机性能排名 top500 第一名是 Frontier 。

目前计算机性能不足以满足应用要求，应用需要计算机解决的问题越来越复杂，规模也越来越大。

从传统 MPP 到集群/机器群再到虚拟现实、云计算等，网络技术的发展促进了计算机系统结构的发展。网络技术发展还促生了新的应用模式向信息化社会发展，大众而不是少数科学家也将成为高性能计算能力的使用者。

并行计算机将一个任务划分成多个子任务分别在多个处理器或计算机上同时处理，提高运算速度，突破单机系统性能的极限。容错计算机系统即使单个处理机节点故障，整个系统也可以继续降级使用，得到高可靠性。企业管理数据库系统通过共用存储器、大容量辅助外村和输入/输出设备，实现资源共享和协同。

二、相关理论基础

计算机的并行性

并行性措施使计算机逐步由低性能向高性能，计算机系统结构由低级向高级发展。

从执行程序的角度：

• 指令内部并行
  • 一条指令内部各个微操作之间的并行。
• 指令间的并行
  • 多条指令的并行执行，如超标量处理、超长指令处理等。
• 任务或进程之间的并行
• 作业或程序之间的并行
  • 企业管理系统 MIS、分布式处理等

并行性开发的途径：通过合理有效的方法，提高速度和吞吐率。

• 时间重叠：重叠流水线的工作方式。
• 空间重叠：重复设置硬件资源来提高可靠性或性能。
  • 早期受限于硬件价格，资源重复的多机系统以提高可靠性为主。
  • 现在的并行计算机和多机系统被大量用于提高系统的计算速度。
• 用户重叠：多用户资源共享，提高系统资源利用率。

计算机体系结构

• 基于指令流的体系结构：
  • 指令由操作码和数据地址码组成。
  • 指令流包括操作流与数据流，按控制流原理工作。
  • 最基本最灵活的体系结构。
  • 算法按时间映射成程序，难以实现大规模并行。
• 基于数据流的体系结构：
  • 面向单个算法设计，完成固定功能，最不灵活但最快。
  • 流件由访问地址与地址操作组成，无数据操作命令。
  • 算法按静态空间映射成 ASIC 电路，在数据流的过程中完成计算。
• 基于构令流计算的体系结构：
  • 提高了硬件的可重用性，前边的两种基于程序实现可重用性。
  • 静态可重构：一次上电，全芯片烧写。
  • 动态可重构：根据应用不同区域动态烧写。
  • 具有指令流计算体系结构的灵活性，接近基于数据流计算体系结构的高效性。
  • 算法按动态空间映射成 RC Device 电路，在构令流的过程中完成数据流计算。

时间映射模式工作的体系结构灵活、通用，但并行度有限，而空间映射模式工作的体系结构可以解决算法并行限制，扩大并行程度。并行、混合实现是未来发展趋势，一方面是从性能、成本、能耗角度考虑，另一方面是从自然问题求解是“时间+空间”的处理过程的角度考虑。

概念分类模型

Flynn 分类法

• SISD 单指令流单数据流
  • 由程序生成的一个单指令流，在任意时刻处理单独数据项。
• SIMD 单指令流多数据流
  • 多 PU 执行相同命令，处理不同的数据。
  • 如 GPU 下的矩阵向量计算。
• MISD 多指令流单数据流
  • 每个PU执行不同指令，处理相同数据。
  • 异构系统或流水处理。
• MIMD 多指令流多数据流
  • 每个 PU 执行不同程序，产生不同指令流，处理不同的数据。

Flynn 分类只能描述算法时间映射的基于指令流的并行计算。

并行计算机结构的技术模型

基于指令流计算的并行计算机实现分类：

• 并行向量处理机 PVP
  • 频繁访存，经过互连网访问 SM。SM、互连网络会成为瓶颈。
  • 交叉开关增加了网络延迟。
  • 扩展节点需要增加互连开关，极其困难。
• 对称多处理机 SMP
  • 每个处理器可同等地访问 SM、I/O 及 OS 服务。
  • 使用高速缓存，有利于缓解 SM、互连瓶颈，开发较高并行度。
  • 共享存储使得系统中的 P/C 不能太多，总线与交叉开关也难以扩展。
• 大规模并行处理机 MPP
  • 处理节点采用商品微处理器，缓解存储瓶颈。
  • 有物理上的分布式局部存储器，解决存储瓶颈。
  • 采用高通信带宽及低延迟的定制互连网络，解决互连瓶颈。
  • 异步的 MIMD 机，程序由多个进程构成，每个进程都有私有空间，由进程传递消息，通过优化数据局部性，可缓解互连瓶颈。
  • 能扩放至成百上千个处理器。

PVP、SMP 的可编程性好，可扩展性差；MPP 可编程性差，可扩展性好。

• 分布共享存储多处理机 DSM
  • 高速缓存目录 DIR 用于支持分布式存储的数据一致性、共享
  • DSM 在物理上由分布在各节点的 LM（本地内存） 形成一个共享存储器，对用户而言形成了一个单地址的编址空间。
  • 比 MPP 编程容易。
• 工作站集群 COW
  • 最低成本的变形的 MPP
  • 节点都属完整的工作站 PC 或 SMP
  • 节点通过低成本商品网络互连
  • 节点内有本地磁盘（MPP 无）
  • 节点内网络接口松散耦合到 I/O 总线上（MPP 网络接口连到存储总线上，网络接口紧耦合）

属性	PVP	SMP	MPP	DSM	COW
处理器类型	专用定制	商用	商用	商用	商用
互连网络	定制交叉开关	总线/交叉开关	定制网络	定制网络	商用网络
系统存储器	集中共享	集中共享	分布非共享	分布共享	分布非共享
地址空间	单地址空间	单地址空间	多地址空间	单地址空间	多地址空间
通信机制	共享变量	共享变量	消息传递	共享变量	消息传递
结构类型	MIMD	MIMD	MIMD	MIMD	MIMD
代表机器	Cray C-90、Cray T-90、银河1号	IBM R50、SGI Power、曙光1号	Inter Paragon、IBM BlueGen、曙光-1000、太湖之光	standford DASH、Crayon T 3D	Berkeley NOW、Alpha Farm、天河1、2号
访存模型	UMA	UMA	NORMA	NUMA	NORMA

并行计算机的访存模型

• 均匀存储访问模型 UMA
  • 特点：
    • 共享物理存储器、单一地址空间。
    • 访问任何存储字访问延迟一致（均匀）。
    • 每台处理器可带有高速缓冲 Cache。
    • 外设也可以一定形式共享。
  • 由于高度共享资源，称为紧耦合结构，技术实现有：
    • 对称多处理机 SMP ：所有处理机同等访问所有 I/O 设备，同样地执行程序。
    • 非对称多处理机：主处理器执行 OS 并操纵 I/O，从处理器只在主处理器监控之下执行用户代码。
  • UMA 适用于通用或分时应用。
• 非均匀存储访问模型 NUMA
  • 特点：
    • 地址空间统一编址：存储器物理上分布在不同位置，所有存储器的集合组成全局地址空间。
    • 各处理器访问时间不同：非均一内存访问。访问本地存储器或群内共享存储器较快，访问外地存储器或全局共享存储器较慢。
  • 全高速缓存存储访问模型 COMA
    • 无存储层次结构，全部高速缓存构成了全局地址空间。
    • 利用分布的高速缓存目录D进行远程高速缓存的访问。
    • COMA 中的高速缓存容量一般都大于2级高速缓存的容量。
    • 使用 COMA 时，数据开始时可任意分配，在运行时它最终被迁移到要用到它的地方。
  • 高速缓存一致性非均匀存储访问模型 CC-NUMA
    • 使用基于目录的高速缓存一致性协议。
    • 保留 SMP 结构易于编程的特定，也改善了 SMP 可扩展性问题。
    • 实际上是一个分布共享存储的 DSM 多处理机系统。
    • 程序员无需明确地在节点上分配数据，系统软硬件会自动将数据拷贝到它被使用的地方。
    • 网络的主要通信是为高速缓存的一致性维护。
• 非远程存储访问模型 NORMA
  • 所有存储器都是私有的，仅能由本地处理器所访问。
  • 以小溪通信方式完成信息交换，对远程 Mem 不能直接访问。
  • 没有网络、访存瓶颈，且不用维护数据一致性等，可以是巨大规模。

并行计算性能分析模型

Amdahl 定律

适用于固定负载问题，即任务规模不变，分析计算速度的加速比。

• Tex ：系统改善后的全部执行时间。
• T ：系统改善前的全部执行时间。
• r：能进行改善部分所占的比例。
• a：能进行改善部分改善的程度。

改善后的执行时间 $Tex=T((1-r)+r/a)$

性能提高衡量指标：加速比 $=T/Tex=1/((1-r)+r/a)$

实际中，一般问题规模越大，r 越大，加速效果越好，r 接近 1 时，加速比接近 a。

结论1：加速效果与改进部分占总执行时间的比例有关。

一道例题：

理想情况下，作业可以均匀分解为 P 个子任务，在 P 台处理机上运行。但实际中，并行处理中存在不可分解成分，系统将以串-并-串的方式运行，子任务划分存在不均匀情况，还有串-并切换、并行任务分发，数据传输、同步等待等非计算开销。

$S_p=\frac{T_s}{t_s+\frac{T_s-t_s}{p}}=\frac{p}{\frac{t_s}{T_s}p+1-\frac{t_s}{T_s}}=\frac{p}{\alpha p+1-\alpha}$

假设处理机的数目增大到无穷，加速比上限 $S_p=\frac{1}{\alpha}$，与串行占比 $\alpha$ 成反比。

结论2：任务规模固定时，在某个处理器数时，会达到加速比上限，再增加处理器个数没有意义。

Gustafson 定律

适用于可扩展问题，每个节点处理负载不变（时间不变），负载增加的处理时间加速比。

• n：处理器个数，即问题规模扩大 n 倍。
• a：n 个处理器并行执行时，能改善部分的并行时间所占比例。
• Tex：系统改善后的执行时间
• T：系统改善前的全部执行时间

加速比 $S_p=\frac{T}{Tex}=\frac{(1-a)+an}{1}=1+(n-1)a$

结论3：随着问题规模增加，如果每个处理器处理数据规模一定，即 a 不变，加速比和 n 有关。

并行计算机粒度模型

• 粒度：衡量计算任务所含计算量的尺度。
• R 表示程序执行时间，C 表示用于通信/访存的开销，用 R/C 比值衡量任务粒度大小尺度。
  • 粗粒度：R/C 比值比较大。每个单位计算只需要少量的通信/访存。计算量大，通信/访存少。
  • 细粒度：R/C 比值比较小。每个单位需要很大通信量和其它开销。计算量少，通信/访存多。

对软件而言，要提高计算速度，细粒度并行需要减少访问延迟、高带宽，而粗粒度并行性需要高处理性能。

• PVP、SMP
  • 通信/访存带宽高，细粒度硬件平台。
  • 适合细粒度/粗粒度并行任务。
• MPP、DSM、COW
  • 通信带宽低，粗粒度硬件平台。
  • 只适合粗粒度并行任务。

如果处理器计算速度快，数据访问或传输慢，适合用粗粒度计算，才能最大化发挥资源利用率，提高系统性能，加快并行程序执行速度。

两台处理机系统的任务分配

• M 为子任务总数
• M-K、K为两台机器任务分配数
• 假设子任务之间都要进行同样数据交换

总处理时间$=R*max(M-K,K)+C(M-K)K$，两台处理机上任务执行时间取最大，处理及内通信开销0，处理机间通信开销 C。

结论 ：当 $R/C<M/2$ 时，把所有任务分配给同一台处理机，总处理时间最小；当 $R/C>M/2$ 时，把任务平均地分配给两台处理机，总处理时间最小。任务分配参数分别为$K=0$或$K=M/2$（M为奇数时，K尽可能接近 M/2）。

N 台处理机系统的任务分配

总处理时间$=R_{max}(K_i)+C/2\sum_iK_i(M-K_i)=R_{max}(K_i)+C/2(M^2-\sum_iK_i^2)$

$K_i$表示分配给第 i 台处理机的任务。

• 若所有任务分配给一台处理机，总处理时间$=R*M$。

• 若所有任务平均分配给 N 台处理机，总处理时间$=\frac{RM}{N}+\frac{CM^2}{2}-\frac{CM^2}{2N}$

当 $\frac{RM}{N}+\frac{CM^2}{2}-\frac{CM^2}{2N}\leq RM$，有 $\frac{R}{C}\geq\frac{M}{2}$

加速比$=\frac{RM}{\frac{RM}{N}+\frac{CM^2}{2}-\frac{CM^2}{2N}}=\frac{2R}{\frac{2R}{N}+\frac{MC(N-1)}{N}}$

当 N 无限大时，加速比趋近于常数 $\frac{2R}{MC}$ 。

结论：R/C 比 M/2 大，应尽量均分任务；R/C 比 M/2 小，应尽量只用一台处理机。

假设通信开销与处理机数目成正比例，执行时间$=R*Max(K_i)+CN$

若任务平均分配，当处理机数目从N加到 N+1 时，执行时间减少量为：

$(\frac{RM}{N}+CN)-(\frac{RM}{N+1}+C(N+1))=(\frac{RM}{N}-\frac{RM}{N+1})-C=\frac{RM}{N(N+1)}-C$

当不减少时，有$N=\sqrt{\frac{RM}{C}}$。

并行程序设计中应该尽量隐藏或减少通信开销：

• 采用通信与计算过程重叠（流水并行）优化方法。
• 通过硬件/软件减少通信开销。

要增加并行度，R/C 会变小；但为了避免通信开销太大，希望 R/C 足够大，可并行度会减少。

Roofline 模型

• 算力 $\pi$：每秒最大浮点运算数。
• 带宽$\beta$：每秒最大访存带宽。
• 计算强度上限 $I_{max}=\frac{\pi}{\beta}$，访存获取的单位数据最多可以用来进行多少次计算。
• 理论性能 P：算法模型在计算平台上能达到的理论峰值计算量。

算力决定屋顶高度，带宽决定房檐斜率。

当计算强度没有达到上限时，位于存储瓶颈区，主要是访存太慢，要优化访存，使得房檐变陡。

当达到理论峰值时，位于计算瓶颈区，主要是算力不够，要优化算法进一步发挥处理器性能，或换更好的处理器。

三、多处理器 Cache 一致性

Cache 一致性问题

在单机系统中，写 Cache 会引发 Cache 与主存的数据不一致，当发生 I/O 读时，主存和 Cache 数据不同就导致了矛盾。一般可以通过直写法WT或回写法WB来解决。

• WT 在修改 Cache 的同时立即修改主存，访存写性能低，增加总线负载。
• WB 被修改的Cache 在被替换时写回主存，使得长时间主存和Cache数据不一致，可靠性低。

而在多机系统中，也存在数据的不一致。

• 共享数据写操作会引发Cache与主存以及Cache之间的数据不一致。
• 进程迁移会读取不一致的数据。
• I/O操作将新的数据写入主存或直接从主存输出数据，会导致不一致。

单纯的 WT 和 WB 不能保证多处理机的多副本一致性。

Cache 一致性维护策略

及时更新或作废主存和其它 Cache 中的数据。

• 更新法，开销大，代价高，控制复杂，一般不用。
  • 基于 WT
  • 基于 WB
• 作废法。
  • 基于 WT
  • 基于 WB

要根据多处理机系统互连网络结构，采用不同的方法维护 Cache 之间、Cache 与主存一致性。

• 播写法，基于总线监听协议，广播写操作，适合总线结构。
  • 某一 PE 修改自己内部 Cache 时，采用广播方法将内容及地址由公共总线发送。
  • 其他 PE 要随时监听总线，一旦发现修改信息就记录下来，且进行相应处理。
• 目录表法，适合非总线互连网结构。
  • 为 Cache 及主存建目录表，保存一致性所需的信息，指明副本位置、状态等。

监听总线协议

基于总线的多处理机系统中，处理器可通过总线检测到所有对存储器正在进行的活动，如果总线业务破坏了本地 Cache 数据块一致性状态，Cache 控制器就应该采取相应动作使本地副本更新或无效。

• 基于 WT 策略
  • 作废法：当 P1 修改其 Cache 中的 X 为 X‘ 后，直写主存，由总线使其他高速缓存中的 X 均无效。
  • 更新法：当 P1 修改其 Cache 中的 X 为 X‘ 后，直写主存，总线广播 X’ 至其他高速缓存中。
• 基于 WB 策略
  • 作废法：当 P1 修改其 Cache 中的 X 为 X‘ 后，回写主存，由总线使其他高速缓存及主存中的 X 均无效。
  • 更新法：当 P1 修改其 Cache 中的 X 为 X‘ 后，总线广播 X’ 至其他高速缓存中，而主存中 X 无效。

典型的一致性维护数据副本状态协议基于作废法，更新法开销大、代价高、控制复杂，一般不用。

2 状态 Cache 协议 SI 协议

两状态没考虑唯一正确数据块的情况，只能先写回主存，再从主存读取数据块，效率低。

3 状态 Cache 协议 MSI 协议

三状态协议能很好地支持 Cache 之间的高速数据传递，但没有考虑程序执行过程中的特点。

4 状态 Cache 协议 MESI 协议

WT 策略每次都要修改主存，总线流量大；WB 策略在 Cache 写一次后，主存中内容就不一致。

考虑到顺序程序可能就写一次，循环程序不止写一次，为了减少发生失效的次数和各 Cache 的变换次数，基于程序执行特点，引出 Write-Once 思想。

• 第一次写，采用 WT 。
  • 有一个以上副本正确，针对顺序程序。
• 而后的写，采用 WB 。
  • 只有一个副本正确，针对循环程序。

为了区分第一次写，把三状态中的 M 分为两个状态。

• S：共享状态。多个 Cache 和主存一致。
• I：无效状态。
• E：只被写过一次。仅一个 Cache 和主存一致。
• M：不止被写过一次。唯一正确的在该 Cache 中。

5 状态 Cache 协议 MOESI协议

数据拥塞：当其他 CPU 请求数据时，S 状态下的哪一个 CPU 发送数据？

SMP 中，可以通过总线监听和总线使用权仲裁解决。

ccNUMA中，通过仲裁机制解决效率低、复杂、成本高。

因此提出增加一个特殊状态，由具有特殊状态的 Cache 发送数据。

MOESI：在 MESI 的基础上引入 O 状态，对 S 状态进行重定义。

唯一正确的 M 状态数据副本发送数据，状态变为 O，此后由 O 状态数据副本发送数据。

• CPU 写操作、本地 Cache 命中，本地状态为
  • E 或 M：数据直接写入 Cache，状态改为 M。
  • S：数据直接写入 Cache，状态改为 M；同时其他 CPU 中该数副本 Cache 行状态从S变为 I。
  • O：数据直接写入 Cache，状态改为 M；同时其他 CPU 中该数副本 Cache 行状态从S变为 I。
• CPU A 写操作、本地 Cache 没命中，CPU B 中命中，B 的状态为
  • E：Cache 行状态改为 I；A 从主存申请一个 Cache 行写入数据，状态为 M。
  • S：Cache 行状态改为 I，同样副本的其他 CPU 数据副本也改为 I；A 从主存申请一个 Cache 行写入数据，状态为 M。
  • M：将数据回写主存，Cache 行状态改为 I。A 从主存申请一个 Cache 行写入数据，状态为 M。
  • O：将数据回写主存，Cache 行状态改为 I，同样副本的其他 CPU 数据副本也改为 I；A 从主存申请一个 Cache 行写入数据，状态为 M。
• CPU 读操作、本地 Cache 命中
  • 数据从本地直接读取，状态不变。
• CPU A 读操作、本地 Cache 没命中，CPU B 命中，B 的状态为
  • M：Cache 行状态改为 O，同时 CPU B 将数据传送给 CPU A，CPU A状态改为 S。
  • O：Cache 行状态不变，同时 CPU B 将数据传送给 CPU A，CPU A状态改为 S。

一个问题：为什么 I 状态第一次写就变成 M，不应该先变成 M 吗？

看图的描述

目录表协议

监听协议仅适合总线连接多处理机，互连网络连接的多处理机使用基于目录的协议。

目录记录共享数据的所有 Cache存数据行的位置与状态。

• 目录表：存放与共享数据块副本相关的数据（目录项），可以集中存放或分散存放。
• 目录项：每个数据块一个目录项。
  • 包含多个指向该数据块多个远程副本地址的指针。
  • 一个重写位，用于说明是否有 Cache 被允许数据块写入。
• 基于目录的协议
  • 全映射目录、有限目录、链式目录
  • 不同目录协议差异在于目录表的格式及对目录表的管理。

全映射目录

共享存储器中的目录里，每个目录项有 N 个处理机指针位和1个重写位 C。

• 处理机指针位：表示相应处理机Cache中是否存在该数据块副本。
• 重写位：表示有且仅有一个处理机指针位为 1，且该处理机可对该块进行写操作。

Cache 中，当使用 2 状态 SI 协议时，每个数据块有两个状态位。

• 有效位
• 是否允许写位。

当 P3 要求写单元 X 时：

1. Cache 有效，但不允许写。
2. 向包含 X 的存储器模块发送写请求，等待回应。
3. 存储器模型向 C1、C2发送无效请求。
4. C1 和 C2 接到无效请求后，将对应块置为无效态，并向存储器模块发出回答信号。
5. 存储器模块接到回答信号，清楚指向 C1 和 C2 的指针，重写位置 1，发允许写信号到 C3。
6. C3 接收到允许写信号，激活 P3 开始写 X 单元，更新 Cache 状态。
7. 写完后，重写位复位 0。

全映射目录速度快、效率高，但目录表大、空间浪费大。

有限目录

由于同时刻的副本数不会太多，可以限制数据块副本的数量，减少目录表大小。

因此也会产生数据块副本数目大于目录表项的问题，要采取目录副本指针替换算法。

有限目录表小、节省空间，但副本数较多时会降低效率，替换算法很关键。

链式目录

链式目录允许任意数目副本，通过链表实现副本指针的扩展。

对副本的查询、删除等操作按链式数据结构方法进行。

链式目录表占存储空间小，但查表时间长，为了加快链式查表过程，可以采用双向链。

链式目录表最小、副本数可扩展，但链表目录查询、删除开销大。

ccNUMA 的 MESIF 协议

MESIF 协议 主要解决 ccNUMA 架构中 SMP 子系统之间 L3 Cache 一致性的问题。

在 ccNUMA 中使用目录表协议，不能使用总线监听协议。

MESIF 引入 F 状态：

• 多个处理器 Cache 副本中只有 1 个 Cache 行状态为 F，其他为 S。
• Cache 行状态为 F 时，Cache 中数据与存储器一致。
• 只有 F 状态的 Cache 行可以转发数据副本。
• F 状态的数据副本被其他 CPU 拷贝时，新副本变为 F，老副本变为 S。
• F 状态的数据副本被改写后，状态为 S 的其他副本置 I ，该 Cache 行变为 M。

Cache 一致性维护中，关键是解决减轻网络负载和多副本同时写操作冲突问题。

对连续处理倾向的进程，作废法较好；对多个处理器频繁交换处理的进程，更新法较好。

四、互连网络

互连网络特性

计算/处理单元、存储单元和 I/O 单元等称为节点，节点间通过互联网络连接以交换信息，互连网络由有向或无向图来表示，是并行计算机系统的关键部件，它决定了系统能效和规模可扩展性，决定了系统的体系架构、适应的应用领域。

互连网络分类

专门定制和高速商用互连网络：

• 专门定制互连网络：用于处理器、存储器和 I/O 设备之间的互连。
• 商用网络：用于连接独立完整的计算机节点，组成 COW 结构集群，当前已有用于 MPP 的商用网络。

互连网络的技术分类：

• 静态互连网：节点间直接相连，连接方式固定不变。
• 动态互连网：由开关实现，可以动态改变节点间连接。

互连网络结构性参数

• 节点度：与节点相连接的边数（即链路或通道）。
  • 反映了节点需要的 I/O 端口数。
  • 反映了节点的复杂度、价格成本。
• 网络直径：任意两个节点之间最短距离的最大值。
  • 用遍历路径的链路数度量，是网络通信性能的一个指标。
  • 网络直径应尽可能小，以减少通信延迟。
• 等分宽度：网络被切分成相等的两半，沿切口的最小边数（通道），用 w 表示。
  • 线等分宽度 $B=w \times b$，$b$表示通道宽度（位）。
• 节点间线长：两个节点间线的长度。
• 对称性：从任何节点看网络的拓扑结构都是一样的，乘该网络为对称网络。
• 寻径功能：实现节点间连接方法。

互连网络的性能指标

1. 通信时延：从源节点到目的节点传送一条消息所需的总时间。包括：软件开销、通道时延、选路时延、竞争时延。
2. 网络时延：通道时延、选路时延。
3. 端口带宽：单位时间传送到其他端口的最大信息量。
4. 聚集带宽：从一半节点到另一半节点，单位时间传送的最大信息量。
5. 对剖带宽：最小对剖平面的所有边单位时间传送的最大信息量。

互连网络表示法

• 函数表示法
  • 变量 x ：输入
  • 函数 $f(x)$：输出
• 输入输出对表示法

• 图形表示法
  • 用输入输出的连线图表示变换关系。
• 循环互连函数表示法
  • $f(x_0)=x_1,f(x_1)=x_2,…,f(x_{j-1})=x_j$。
  • $(x_0,x_1,x_2,…,x_j),j+1$称为循环长度。

寻径函数

寻径函数描述相互连接的输入端号和输出端号之间的一一对应关系。

设 $n=log_2N,(N=2^n)$，则可以用 n 位二进制表示 N 个输入端和输出端的二进制地址，互连函数表示为： $f(x_{n-1}x_{n-2}…x_1x_0)$。

交换置换

$\varepsilon_{(k)}(x)=\{b_{n-1}b_{n-2}…\bar{b_k}…b_1b_0\}$

实现节点二进制编址中第k位值不同的输入端和输出端之间的连接。

全混洗置换

全混洗是把节点的二进制编码 循环左移 一位。

$\sigma(x)=\{b_{n-2}b_{n-3}…b_0b_{n-1}\}$

子混洗 最低 k 位进行混洗，高位不变。

$\sigma_{(k)}(x)=\{b_{n-1}b_{n-2}…b_kb_{k-2}…b_0b_{k-1}\}$

超混洗 最高 k 位进行混洗，低位不变。

$\sigma^{(k)}(x)=\{b_{n-2}b_{n-3}…b_{n-k}b_{n-1}b_{n-k-1}…b_0\}$

蝶式置换

节点编址的 最高位和最低位交换 。

$\beta(x)=\{b_0b_{n-2}…b_1b_{n-1}\}$

子蝶式 最低 k 位进行蝶式置换，高位不变。

$\beta_{(k)}(x)=\{b_{n-1}b_{n-2}…b_kb_0b_{k-2}…b_1b_{k-1}\}$

超蝶式 最高 k 位进行蝶式置换，低位不变。

$\beta^{(k)}(x)=\{b_{n-k}b_{n-2}…b_{n-k+1}b_{n-1}b_{n-k-1}…b_0\}$

位序颠倒置换

将输入端二进制地址的位序颠倒过来。

$\rho(x)=\{b_0b_1…b_{n-2}b_{n-1}\}$

子反位序

$\rho_{(k)}(x)=\{b_{n-1}b_{n-2}…b_kb_0b_1…b_{k-1}\}$

超反位序

$\rho^{(k)}(x)=\{b_{n-k}b_{n-k+1}…b_{n-1}b_{n-k-1}…b_0\}$

移数置换

在 n 位末尾加 1，再对 $2^n$ 取模防溢出。

子移数 最低 k 位移数置换，高位不变。

超移数 最高 k 位移数置换，低位不变。

恒等置换

相同编号的输入端与输出端一一对应。

$I(x)=x$

逆置换

若置换$f(x),g(x)$满足$f(x)\times g(x)=I(x)$，则称$f(x),g(x)$互为逆置换。

$f(x)$的逆置换记作$f^{-1}(x)$。

静态互连网络

静态互连网络的入/出端节点固定。一个节点可以和多个节点直接连接，每种连接可以用一种寻径函数表示。

一个静态互连网络 SW，可用多寻径函数表示为$SW={f_1,f_2,…,f_m}$。

当和没有直接连接的节点通信时，需要循环使用该互连网络。

一维线性阵列

环形互连网络

带弦环网，解决数据拥塞，减少路径长度。

增加的链路越多，网络直径越小，但节点度越高。

树形网络

根及叶子节点具有 I/O 功能，叶子节点执行并行计算，内节点仅负责节点间的通信。

最长通信路径为树高的倍数。

在树形网络中，根节点为通信性能和故障瓶颈。

• 使用 X- 树，使同级兄弟节点相连。

• 使用胖树，除根外共两层，每个节点有4个子节点和2个父节点。

从通信性能的角度看，树的跳数少，优于网孔。将二者结合成树-网连接。

• 原网孔的水平和纵向连接用二叉树构成。
• 原网孔的节点变成二叉树的叶子节点。

既具有良好的通信性能，又具有许多网孔上的有效算法。

除此以外，金字塔连接也是一种树与网孔的结合。

超立方体网

• 节点个数为 $2^n$。
• 节点用 n 位二进制数表示。
• 节点的编号每位取反得到的编号构成该节点的邻居节点。

路由方法： 当前节点与目的节点编号从高位到地位依次比较，相同不动，不同则按该位取反的相邻节点移动。

• 性能优异
  • 网络直径短，为 n。
  • 点与点之间的跳数少，小于 n。
  • 对剖宽度大，$2^{n-1}$。
• 路由简单，包容性好，应用算法扩展性好。
• 容错能力强。
  • 任意两个节点距离为$D$，则它们有 $D!$ 条最短互连路径。
• 大规模时，网络物理端口、链路连接实现太困难。
  • 大规模时不会采用。

带环立方体 结合环网与立方体的优点及性质，将立方体的每一个顶点由一个环替代。

k 元 n 立方体，n 表示立方体维数，k 是基数（每个方向节点数）。

节点用基数为 k 的 n 位地址表示 $A=\{a_1a_2…a_n\}$。

动态互连网络

总线结构

处理机、存储模块及 I/O 作为节点连接到总线上。各节点以均等竞争方式使用总线，但容易引发冲突。

总线仲裁

• 排队器：优先权编码器。
  • 当多个节点同时发出请求，排队器仲裁，仲裁结果经过译码器控制节点发送信息。
• 菊花链：
  • 静态菊花链：每个节点分配固定优先权。
    • 节点测试总线状态。
    • 当总线“空”时发出总线请求。
    • 总线控制器发出响应信号。
    • 没有申请总线的节点传递响应信号。
    • 发出总线申请的节点接收到响应信号，不再传递并置状态线为“忙”。
    • 节点发送信息到总线。
    • 传送结束，置状态线为“空”。
  • 动态菊花链：节点优先权动态变化。
    • 循环法：节点最高优先权依次循环，刚使用过的总线具有最低优先权。
    • 基于某种函数确定优先权。

全互连开关

任何时刻任何节点可以访问任一其他节点，无冲突，但对于 $n\times n$ 的交叉开关，开关数为 $n^2$，成本高、连接复杂。

多级交叉开关网

• 开关形式
  • 如 $2 \times 2$ 交叉开关：具有 2 个输入及 2 个输出的交换单元。

• 级间拓扑结构
• 开关控制方式
  • 级控制：同级开关使用同一个控制信号。
  • 单元控制：每个开关都有自己的控制信号。
  • 部分级控制：用 m 个控制信号控制 n 个开关。

多级开关路径冲突：存在多个消息寻径共享一个开关或路径。引发冲突的多级开关网称为阻塞网。

• 解决阻塞：增加冗余路径。
  • 将两个多级开关网串接。
    • 发生冲突时，一个走正确的路径，一个走剩下的路径。
    • 时间延迟增加了一倍。
• 缓解阻塞：减少使用链路，如数据包合并。

无阻塞网不一定耐故障。

通过增加冗余路径：

• 增加段：会增加延时。
• 增加旁路：会使控制复杂。

消息传递机制

共享内存系统基于变量共享完成子任务之间的数据传输，而多机系统基于消息传递完成子任务之间的数据传输。

寻径方式

• 线路交换：传递消息前，先建立一条源到目的节点的物理通路，再传递消息。
  • 物理通道不共享、开销大。
• 存储转发寻径：包从源节点经中间节点存储转发到达目的节点。
  • 包缓冲区大、时延与节点距离成正比。
• 虚拟直通寻径：没有必要等到整个消息全部接收后再寻径，只要收到消息头部就寻径。
  • 遇到阻塞时依然是存储转发，节点需要包缓冲区大，且包缓冲区独立在寻径芯片外，转发时延大。
• 虫蚀寻径：包分成更小的数据片，节点的寻径硬件中只设置片缓冲区。
  • 缓冲区较小、网络传输时延低、通道共享性好、易于实现选播和广播通信方式。
  • 数据包仍然是传送的最小单位，所有数据片必须跟着头片，不能交叉。
  • 因为包会同时占用多个节点寻径器的缓存和通道，通道争用时更容易引起阻塞、死锁。
    • 防死锁路由算法：限制某方向传输，不形成死锁循环等待。
    • 缓解死锁：增加物理硬件通道。
  • 虫蚀寻径更适合虚拟通道，物理链路由所有虚拟通道分时共享。

包冲突时处理策略

当两个包到达同一个节点时，可能请求同一个接收缓冲区或用同一个输出通道。

• 阻塞法：后续包不再前进。
  • 控制简单，但可能引起大面积阻塞。
• 扬弃并重发法：后续包扬弃。
  • 控制简单，重发效果未知，会加大网络负载。
• 虚拟直通法：后续包缓冲。
  • 不浪费已分配资源，但需要一个能存放整个包的存储器作为缓冲区，存储延迟较大。
• 绕道法：后续包转发到其他寻径器。
  • 绕道结果未知。

防死锁寻径算法

• 维序寻径：按维度次序依次寻径。先编址高位相等，再低位相等。
  • 无死锁、可扩展、最短路径。
  • 针对链路故障问题，需要增加物理或虚拟通道，只能缓解。
  • 针对节点故障问题，需要绕道自适应寻径，破坏维序规则，可能形成环，造成死锁。
• 自适应寻径：Subnet 法。
  • 网格网络中，同一维的所有连接使用多个虚拟通道。

通信模式

• 单播模式：一个源节点到一个 目的节点。
• 选播模式：一个源节点到多个目的节点。（多播、组播）
• 广播模式：一个源节点到全体节点。
• 会议模式：多个源节点与多个目的间相互。

寻径算法效率需考虑的因素：

• 信道量：传输有关消息所使用的通道数。
• 通信时延：包最长传输时间。

不同寻径方法关注的因素：

• 虫蚀寻径占信道多、易阻塞、延时与跳数关系不大，信道量参数比较重要。
• 存储转发中，占信道少、不易阻塞、延时与跳数成正比，通信时延较重要。

广播树： 节点中的数字表示树的层次号。

贪婪树法： 向可达最多剩余节点的维方向发包。

五、并行计算机系统结构

UMA

Bus

• 单总线：资源共享、独占资源，适用规模较小。
  • 减少使用总线
    • 硬件：增加 Cache，基于局部性特征以减少总线使用
    • 软件：开发数据局部性，充分发挥 Cache 作用
• 多总线：扩展性能
• 多层总线：扩展系统

总线仲裁：

• 集中式仲裁
  • 排队器
• 分散式仲裁
  • 静态菊花链
  • 动态菊花链
• 需要解决饥饿问题

Switch

• Crossbar 经纬线
  • 开关控制，速度快
  • 严重受 PIN 数量限制；开关数多，成本高
• MIN 多级 IN
  • 硬件成本高，适用规模较小

动态网的消息控制存在麻痹问题：数据在传输过程中，经过的路径过于集中造成的阻塞现象。

• 减少请求：合并消息
• 增加可选路径：多级、多重输出网络

NUMA

cc-NUMA

• HM 中的数据管理方式：就是目录表法

  • 全映射法

  • 有限指针法

  • 指针法

• Cache 一致性

CC-NUMA 数据一致性维护太复杂，成本高，性能损失大； HM仅数据开始、结束用到，中间可以不保存/修改HM中数据块，但目录表是需要的。

简化数据一致性维护的 HM 开销，仅维护 Cache 中数据一致性；用高速小容量目录 D 替代 HM 。提出 COMA 结构。

COMA

使用阶层总线，目录 D 用于存储页的位置信息。初始时数据随机分配在 Cache ，并在 D 中记录，P 待访问数据通过 Cache 和 D 找到后，拷贝本地 Cache，一段时间后，数据分布达到最优。

访问数据地址虚拟化，Cache 数据变化时 D 需要重新映射。

分布式缓存比共享主存中页的替换复杂、频繁。

DASH

• 高速地址映射 D 将全局地址翻译为本地地址。
• 采用分布式目录方式的缓存一致性协议，使用硬件保持缓存数据一致性，减少访问延迟。
• 网络接口含目录，目录具有与配置在群里主存相对应的项，并保持着其他群的缓存状态信息。
• 数据分布在各群的局部主存中，但有局部性的数据尽量分布在相应群中。

数据在其他群(称为主群)中时，由目录间协调将数据发送到本地缓存，并由主群目录将其他群中缓存副本无效化等。

需要硬件、编译和应用共同完成数据同步。

多使用改进后的五状态+总线监听四状态协议。

NORA

• MPP
  • 结构特点
    • 不共享内存，无统一地址空间
    • 通过消息传递方式进行协调
    • 规模较大
  • 结构分析
    • 静态网连接 IN 严重影响性能
    • 任务逻辑结构由算法决定，网络结构影响算法执行效率
  • 消息传输的寻径控制方式
    • 线路交换
    • 存储转发
    • 虚拟直通
    • 虫蚀
• COW
  • 目的
    • 提高性能
    • 降低成本
    • 提高可扩展性
    • 增强可靠性
  • 分类
    • 科学集群
    • 负载均衡集群
    • 高可用性集群
  • 关键技术
    • 网络层：网络互连结构、通信协议、信号技术
    • 节点机及操作系统层：高性能客户机或基于微内核操作系统等
    • 集群系统管理层：资源管理、资源调度、负载平衡
    • 应用层：并行程序开发环境、并行应用
  • 消息的传输控制方式
    • VIA：实现零拷贝、旁路操作系统
    • RDMA

节点并行技术

• 一般是 SMP、cc-NUMA架构
• 芯片 ：定制、商用
• 多芯片、大容量内存、高速网络接口
• 处理器芯片：多核、众核、异构多核/众核
• 协处理器加速
  • CELL、GPU、MIC
  • 逻辑上是 主处理器+协处理器，实现上可集成在芯片内，可在同一主板上，可是加速卡。

多核/众核具有性能/能耗优势。

多核架构采用协处理器 CELL，从统一的对等设计到“主核心+协处理器”的非对等设计。

CELL 可以对处理器内核的数量进行任意裁剪：

• 嵌入式设备：单核心，低频，低能耗。
• PC：可使用与 PS3 游戏机一样标准的 CELL，或对核心适当裁剪。
• 工作站/服务器系统：可将两枚 CELL 处理器集成在一起，获得更高效能。

六、资源管理与任务调度

多机操作系统

多机操作系统主要功能

多机操作系统用中间件实现，处于节点操作系统和用户环境中间。

它由软件基础结构的两个子层组成：

• SSI 基础结构：与节点操作系统相联系，提供对系统资源的统一访问。
  • 单一用户接口：用户通过与单机工作站外观一致的单一 GUI 使用系统。
  • 单一 I/O 空间：任一节点透明使用本地或远程外设与存储设备的 I/O 操作。
  • 单一进程空间：每一进程在系统范围内拥有独立 ID，可以与系统中任一进程通信。
• 系统可用性基础结构：在各个节点上提供可用性服务，如检查点、自动故障检测、故障恢复、容错、迁移调度和负载重均衡支持。
  • 检查点机制定期保存进程状态和中间结果，失效时，故障节点进程可以迁移到另一节点重新从检查点开始。
  • 进程迁移支持了节点间的动态负载平衡和容错。

多机操作系统分类

• 主从式：操作系统在指定主处理机上运行。
  • 主处理机管理系统，为从处理器分配任务。
  • 从处理器通过软中断或访管访问主存等。
  • 适用非对称系统，以及工作负载不太重的情况。
• 单独管理：每个处理器有自己的操作系统或管理程序。
  • 按自身需要独立运行和管理。
  • 适合于松散耦合的多处理机系统。
• 浮动管理：主处理机可从一个处理机浮动到另一个处理机。
  • 任何处理机都能成为主处理机。
  • 适用于同构多机系统。

资源管理和调度 RMS

系统资源管理和调度，一方面可以提高系统效率与可靠性，它通过实现负载平衡、尽可能地利用空闲的 CPU 周期、提供容错机制，为应用程序提供了更强、更可靠的服务以及更高的吞吐量；另一方面，可以提高可编程性和易管理性，使得资源能被更便捷地管理与访问。

资源管理和调度的目标是实现 SSI 基础结构，使得系统更加自动、智能，使应用程序达到最大吞吐量/最短完成时间，使资源被有效、节能地利用。

• 线程/进程迁移：负载不均衡或节点故障时，线程/进程挂起、移动和重启动。
• 检查点：故障时，程序可以从检查点重新开始。
• 容错：隔离故障节点，进程迁移，并从检查点重启。
• 空闲周期搜索：使用空闲的 CPU 周期以提高资源利用率。
• 减少用户干预：将用户干预减到最少，提供透明服务。
• 负载平衡：在特定结构中作业可以分布在所有可用的处理器上。
• 多应用程序队列：在特定结构中协助管理资源，实现作业调度，每一队列可以配置为一定属性。
  • 大系统中有全局多应用程序队列和局部多应用程序队列。

RMS 的由资源管理器和作业调度器组成。前者组织管理物理资源，包括处理和定位计算资源的配置、验证，监控资源状态，故障诊断与恢复，进程迁移，动态负载均衡等；后者实现任务与物理资源的有效匹配，包括处理应用程序队列等待任务，以及资源定位与任务分配。

作业调度要考虑用户优先级与任务优先级，并考虑任务调度算法、调度时机、调度过程，同时考虑调度的基本单位是计算节点或是更细粒度的资源。

不同的应用场景考虑不同的因素，采取不同的调度策略和方法。

调度概述

调度，指在一组具有任意特性的处理机中，对一组进程进行调度。好的调度应该最大化资源利用率并最快完成任务执行。

• 最小完成时间
• 所需最少处理机数
• 最小平均等待时间
• 处理机最大利用率
• 处理机最小空闲时间

调度策略有两类：

• 确定性调度：求解问题前给出表示问题特征的所有信息，如任务运行时间和任务间关系。
• 不确定性调度：运行过程中根据系统状态对任务进行分配。

调度实现方法有：

• 抢先调度
• 非抢先调度

确定性调度

单作业并行调度

子任务之间有数据、控制等相关性，调度时必须考虑同步等问题。

单作业多进程调度过程一般采用 Gantt 图表示。

非抢先调度方法

对于一个给定的任务图，如下所示，结点表示子任务，有向线表示各子任务之间的关系，结点右侧的数字表示子任务的运行时间。

最小完成时间由最长路径决定，所需的最多处理器个数由图宽度决定，调度系统可以根据结点的最早开始时间调度，或者根据结点的最晚完成时间调度。

处理机空闲时立即分配任务不一定获得最小完成时间。任务图的任务分配是网络规划问题，实际调度时也要考虑任务数据相关性和局部性，相关任务尽量调度到同一个节点，提高数据复用等。

任务图可以由图 $G=(T,Q)$表示：

• $T$ 为任务集，$T=\{t_1,t_2,t_3,…,t_n\}$，$t_i$ 为结点权，表示子任务运行时间。
• $Q$ 为通信集，$Q=\{q_1,q_2,q_3,…,q_m\}$，$q_j=(t_i,t_k)$ 为$t_i$与$t_k$两个结点之间边的权，表示两个子任务之间的通信量。

在确定性调度中，结点权为常数，不确定性调度中，结点权是不确定数。

多机系统可由系统图$H=(P,E)$表示：

• $P$ 为处理机集，$P=\{p_1,p_2,…,p_s\}$，$p_i$为结点权，表示处理机速度。
• $E$ 为通信链路集，$E=\{e_1,e_2,…,e_r\}$，$e_j$为有向边权，表示两个处理机之间通信链路带宽。

调度过程就是从任务图到系统图的映射。

最小完成时间的非抢先调度：

• 设定任务图结点标号：
  • 结点 $T_i$ 用 $a_i=x_i+1$进行标号，其中 $x_i$ 是 $T_i$ 到结束结点的最大路径长度。
  • 任务图最小完成时间 $T_{min} \geq a_{max}$。

• 给定处理机数目 P，确定执行任务图最小完成时间。
  • 调度最多 P 个最大标号结点，可能包括两层。
  • 把处理过的 P 个结点从图中删除，剩下没有数据、控制相关的结点为开始结点。
  • 重复上述过程。
• 给定任务图执行时间 $T=a_{max}+c$，确定最小处理机数目。
  • $p\geq \frac{1}{r^*+c}\sum_{j=1}^{r^*}\rho(a_{max}+1-j)$
  • 其中$\rho(i)$表示途经标号$a_i$的结点数，$r^*$是给定表达式值为最大的常数$r$值。
  • $r^*$的确定只要把所有的可能都算一遍，取最大的那个就行。

抢先调度方法

公度结点权

• 基于最小完成时间的抢先调度
  • 假设对 n 个相互独立任务和 p 台处理机进行调度，n 个任务的权分别是$w_1,w_2,…，w_n$。
  • 最小完成时间是 $w=max\{max(w_i),\frac{1}{p}\sum_{i=1}^nw_i\}$ 当$n\leq p$取前者，$n>p$取后者。
• 基于公度结点权的抢先调度，前提是任务之间没有相关性

• 最小完成时间的抢先调度算法，假设任务图为一棵根树，树结点权可公度
  • 按公度结点权值将结点拆分，并划分为若干个不相交的子集，子集内的结点相互独立。
  • 任务图按层分割，结束结点为第一层，向上扩展。
  • 首先调度最高层，逐步向下获得最小完成时间。

粒度尽量大以减小开销；每层粒度最好相当，不浪费资源。

在程序的初始应该尽可能细分。粒度太小通信和调度开销会大，因此要折衷。如果加大粒度可以消除不必要的通信时延或降低总调度开销，则合并多个细粒度结点为粗粒度结点。粒度太大导致处理器空闲，因此合并后并行度尽量与处理器数相匹配。

静态多处理机调度优化：结点复制

不复制时：

复制时：

多作业并行调度

• 各作业间无相关，独立执行
  • 最长处理时间优先：时间最短。
  • 最短处理时间优先：作业启动执行前等待时间最短，用户体验好。
  • 最短最长循环：兼顾时间和用户体验。

• 多个作业内并行子任务多处理机调度
  • 多作业和多处理器调度优化
  • 单并行作业和多处理器调度优化

并行度优先，再最长时间优先。

不确定性调度

• 通过动态获取任务的执行时间或相应运行参数，探索进程执行的时间规律。
• 在运行过程中保证各处理机满负荷运行。

排队系统的三个主要组成部分：

1. 输入过程：任务到达情况
   • 任务总体——有限多、无限多
   • 到达方式——单个、成批
   • 到达时间间隔——确定、随机
   • 到达相关——独立的、前后相关
   • 到达稳定性——到达时间间隔分布
2. 排队规则
   • 即时。立即服务，无资源满足不等待
   • 等待。排队
   • 等待调度次序——先来先服务，优先权服务等。
3. 任务调度
   • 调度器数目
   • 串行或并行处理任务调度
   • 单任务或成批调度
   • 服务时间确定或不确定
   • 服务时间间隔平稳情况

三个最大的影响因素：任务到达时间间隔分布、任务执行时间分布、处理器数。

基于优先权的动态调度

$优先权=\frac{等待时间+要求服务时间}{要求服务时间}$

防止饥饿。

七、并行文件系统

并行计算机存储墙问题

计算机性能提高速度远远大于存储访问带宽提升。

• 众核处理器与主存之间的存储墙如何解决？
  • 高速缓存提高访存速度，且数据复用减少主存访问。
  • 核间设置高速网络、寄存器通信，提高核间通信速度。
  • 从核局部存储与主存之间的 DMA 机制。
• 计算阵列与存储系统的存储墙如何解决？
  • 并行文件系统：并行读写数据，以提高数据读写速度。
• 众核处理器面临的存储墙问题？
  • 神威众核处理器计算性能高，但访存带宽相对比较低。
    • 充分提高带宽利用率，DMA 方式数据读写，核间寄存器通信。
    • 访存与计算的充分重叠，以发挥处理器强大的计算能力。
  • GPU 处理器中的 SM 结构
    • 片上存储需要软件显式精确地使用，减少因 Cache 冲突核颠簸带来的额外访存流量，避免带宽浪费。
    • 采用 SIMT 执行机制，实现访存延迟和计算充分重叠。
  • Cell 处理器也采用非 Cache 结构
    • 异步 DMA 机制，并通过软件多缓冲有效实现计算与访存的重叠。
  • 受芯片资源总量限制，用于发掘数据局部性的片上缓存往往会被减小，片上数据的重用机制是众核处理器体系结构研究最为关键的问题之一。
  • 片上数据重用机制：包括共享片上存储和片上通信两种方式。
    • Intel MIC 采用了共享 L2 Cache 的数据复用机制。
    • Tile64、Intel SCC、神威等处理器都设计了较为强大的片上 2D Mesh 通信网络，增强核间通信带宽。
      • 神威处理器设置了核间寄存器通信，减少中间结果使用缓存。

磁盘阵列 RAID 技术

独立磁盘构成的具有冗余能力的阵列。

基本功能：

• 高性能
  • 对磁盘上的数据进行条带化，实现对数据按块存取，提高数据存取速度。
  • 对阵列中几块磁盘同时读取，提高数据存取速度，同时提供大容量。
• 大容量
  • 多块独立磁盘组合成磁盘阵列，提供巨大存储容量。
• 容错
  • 镜像或奇偶校验–>多副本或纠删码。
  • 实现对数据的冗余保护。

RAID 分类

• RAID 0：无容错的数据条带。
  • 提高磁盘性能和吞吐量。
  • 无冗余或错误修复能力。
  • 实现成本最低。

• RAID 1：无校验的相互镜像。
  • 磁盘镜像，保证可靠性和可修复性。
  • 成本增加，磁盘利用率 50%。
  • 同步镜像时间长，影响系统性能。
  • 应用在保存关键性重要数据的场合。

1. MTTF：平均无故障时间，度量可靠性。
2. FIT：故障率，MTTF 的倒数，通常以运行10亿个小时的故障数表示。
3. MTTR：服务中断的平均修复时间。
4. MTBF：平均故障间隔时间，$MTBF=MTTF+MTTR$。
5. 可用性$=MTTF/(MTTF+MTTR)$。

例题：

• RAID 2：海明码校验
  • 带海明码校验。
  • 用编码技术提供错误检查及恢复。
  • 多个磁盘存放检查及恢复信息，技术实施复杂，性能低，在商业环境中很少使用。
  • 输出数据的速率与驱动器组中速度最慢的相等。

• RAID 3：带有专用位校验的数据条带。
  • 带奇偶校验码并行传送，只能查错不能纠错。
  • 要有三个以上的驱动器，写入速度与读出速率都很高。
  • 校验位少，计算时间相对较少。
  • 主要用于图形等要求吞吐率比较高的场合。

• RAID 4：带有专用块级校验的数据条带 纠删码技术
• 可容忍一个磁盘失效。
• 写操作只涉及当前数据盘和校验盘两个盘，多个 I/O 请求可以同时处理，提高系统性能。
• 读性能好，但校验盘是系统性能瓶颈，且校验盘已磨损。

• RAID 5：带分散校验的数据条带
  • 校验数据分布在阵列所有磁盘上，可容忍一个磁盘失效。
  • 不存在并发写操作时校验盘性能瓶颈问题。
  • 具备很好的可扩展性，拥有更高容量及更高性能。
  • 目前最常用的 RAID。

• RAID 6：带双重分散校验的数据条带
  • 可容忍两个磁盘失效。
  • 最常见实现方式是采用两个独立校验算法，P 和 Q。
  • 具有快速读取性能、更高的容错能力。
  • 控制器比其他等级更复杂、更昂贵，写性能也较差。
  • 主要用于数据安全等级要求非常高的场合。

并行文件系统

并行文件系统概述

并行文件系统是应用于多机环境的网络文件系统，单个文件的数据采用分条等形式存放于不同的 I/O 节点之上，支持多机多个进程的并发存取，同时支持元数据和数据的分布存放，并提供单一的目录空间。

并行文件系统需要实现两个主要方面：

• 单一文件映像：文件数据存放的具体分布情况对于用户是透明的，并行文件系统在用户看来是一完整的树型结构，在调用时只要给出文件名即可。
• 采用条和分区技术：支持一个文件数据在多个磁盘/节点之上分布和在多个进程之间共享，即多个进程并发读写多个磁盘/节点上的数据。

并行文件系统的特点：

• 很好的性能和容量扩展性
  • 随着存储节点增加，I/O 吞吐量、读写性能、容量线性增长。
  • 存储节点、存储对象数、存储对象空间具有可扩展性。
• 高访问性能
  • 大规模海量数据访问高度并行。
• 具有全局唯一的对象标识和文件属性信息
• 采用文件数据与元数据分离存储机制
  • 文件数据分解为条带化存储到存储节点。
  • 文件元数据保存在元数据存储节点。
  • 控制流与数据流分离传输，有效分布 I/O 负载，提高系统 I/O 性能。

存储区域网并行文件系统

PVFS 并行虚拟文件系统

PVFS 为 Linux 集群提供了高性能和可扩展的并行文件系统。

其中由三种类型的节点：

• 管理节点 mgr：元数据服务器，处理文件元数据（描述文件信息文件）。
• I/O 节点 iod：I/O 服务器，存储文件数据，负责数据存储和检索。
• 计算节点：处理应用访问，利用 libpvfs 客户端 I/O 库，从底层访问 PVFS 服务器。

1. 当打开、关闭、创建或删除一个文件时，计算节点上的应用通过 libpvfs 直接与管理节点通信。
2. 管理节点定位到文件后，向 libpvfs 返回文件位置。
3. libpvfs 直接对数据 I/O 节点进行并行读写操作，不必与元数据服务器通信，提高了访问效率。

并行文件系统 Lustre

Lustre 消除了传统网络文件系统可扩展性、可用性和性能问题。它是基于 Linux 平台的可扩展并行文件系统，基于对象存储，替代以往的数据块管理方法，是基于廉价硬盘构建的大规模存储系统，支持大多数高速网络类型，具有高吞吐量、高扩展性和高性能，具有数据管理机制、全局数据共享、失效容错等功能。

客户端缓存机制

在客户端的内存空间开辟一段缓存区，把首次访问的文件对象保存在缓存区中，尽量减少与数据服务器的交互次数，从而提高性能、降低网络开销。

客户端执行文件读取操作时，

• 向 MDS 发送元数据请求，获得元数据信息，并保存到客户端本地的缓存区中。
• 客户端与相应 OST 建立连接，将需要的文件数据读入缓存区，应用程序再从缓存区中执行文件读取操作。

备份服务器 Failover

Lustre 系统每个节点（MDS/OST）都可以配置备份服务器，两个服务器采用共享硬盘存储方式存放数据。当服务器或网络连接发生失效时：

• 会导致客户端数据访问超时，客户端查询备份服务器数据。
• 客户端得到信息后，立即将后续请求重定向到备份服务器。

借鉴 RAID 将文件数据以某种 RAID 模式分布存储在多个 OST 的存储对象中，能够同时容忍硬盘和节点失效。

元数据服务器集群 CMD

单一元数据服务器存在局限：单一故障点、性能瓶颈。

随着客户端和对象存储节点的增加，会成为整个系统的性能瓶颈。

分布式文件系统

HDFS

名字节点双备份，信息交互采用不同协议。

Ceph

分为四个层次：

• 基础存储系统：RADOS 可靠的、自主的、分布式的对象存储。
• 基础库：LIBRADOS
• 高层应用接口：RADOS GW、RBD、Ceph FS
• 应用层

Ceph 底层关键是 RADOS，它由两个组件组成：

• OSD：提供存储资源的存储设备，负责对象存储和查找，及向该对象的复制节点分发和恢复。
• Monitor：维护整个 Ceph 存储集群全局状态，提供强一致性的决策。
• OSD 和 Monitor 相互传输节点状态和信息，形成系统全局状态记录数据结构 cluster map。该数据结构与 RADOS 特定算法相配合，实现”无需查表，算算就好“核心机制。实现了去中心化，自动容错、负载均衡等。

RADOS 具有很强的扩展性和可编程性。

Ceph 另外两个组件：

• MDS：用于保存 CephFS 的元数据。
• RADOS Gateway：对外提供 REST 接口，兼容 S3 和 Swift 的 API。

寻址流程

数据访问

数据访问过程具有强一致性，读写操作采用 Primary-Replica 模型，只向 Object 所对应 OSD set 的 Primary 发起读写请求。

数据冗余

• 多副本策略：多份相同数据放置在不同 OSD 上。
• 纠删码策略

节点状态检测

通过 heartbeat 及时发现 osd 状态变化，由 monitor 更新 osdmap，并同步到相关的 osd 上。

• osd 之间的 heartbeat
  • 同一个 PG 内的 OSD 进行 heartbeat，如果发现有 osd 未能建立心跳汇报至 monitor。
• osd 与 monitor 之间
  • 发现有 osd down 或者 up，会汇报至 monnitor 端，并修改 osdmap；同时，某一个 osd 会汇报子集的状态。

故障恢复

• 暂时性故障：用日志同步恢复不一致。
• 永久性故障：数据回填，将损坏节点的数据放置在其他节点之上。

一致性检查功能

• Scrub：仅仅通过对比对象各副本的元数据，来检查数据的一致性。
• Deep-scrub：进一步检查对象的数据内容是否一致，几乎要扫描磁盘上所有数据计算 crc32 校验值。

Ceph 主要技术特点：

• 统一：提供对象存储、块存储和文件系统存储。
• 分布式：无中心结构和理论上的无限系统规模可扩展性。
• 先进核心设计思想：无需中心查表，算算就好。

Ceph 功能特点：

• 高扩展性
• 高可靠性
• 高性能
• 兼容性

八、并行编程模型与并行程序设计

并行编程模型

并行编程模型是并行计算机体系结构的抽象化描述，是程序员关于算法或应用程序详细执行的思维模型。不同的并行计算机可以支持同一种并行编程模型，提高软件的可移植性以及开发者的效率。

并行编程模型根据并行进程间的交互方式，可分为：共享内存、消息传递，根据问题分解方式，可分为：数据并行、任务并行。

常见的并行编程模型有：

• 消息传递编程模型：MPI
• 共享内存编程模型：OpenMP
• GPU 编程模型：CUDA

Foster 设计方法

一个并行算法设计过程分为四步：划分、通信、聚集、映射。

• 划分：三维矩阵是最大和最频繁访问的数据结构，可划分为：二维切片集合、一维切片集合、矩阵元素集合。
• 通信
  • 局部通信
  • 全局通信
  • 通信结构评估：
    • 平衡任务间的通信操作。
    • 每个任务仅与少量邻居进行通信。
    • 任务能够并发执行它们的通信。
    • 任务能够并发执行它们的计算。
• 聚集：聚集和映射阶段要考虑怎样将原始任务合并成大的任务并映射到物理处理器上以减少并行开销。
  • 降低通信开销。
  • 维护并行设计的可扩展性。
  • 减少软件工程上的开销。
• 映射：将任务分配给处理器，最大化处理器的利用率和最小化处理器之间的通信。

MPI

涉及通信集合中所有进程的通信函数成为集合通信。

在集合通信中，如果属于一个进程的数据被发送到通信集合中的所有进程，这样的集合通信就是广播。

OpenMP

编译制导语句。

归约子句

归约是将相同的归约操作符重复地应用到操作数序列来得到一个结果的计算。

性能分析

系统级性能优化通常包括两个阶段：性能剖析、代码优化

• 性能剖析的目标是寻址性能瓶颈，查找引发性能问题的原因及热点代码。
  • IPM
  • TAU
• 代码优化的目标是针对具体性能问题优化代码或编译选项，以改善软件性能。
  • SCALASCA
  • MPE