分布式chap.1

第一章 Architecture

大纲（outline）

• 冯诺依曼模型的修改
• 分布式硬件
  • 弗林分类法
  • 共享内存系统和分布式存储系统
  • 内存层次结构和缓存一致性
  • 互联网络
• 分布式软件
• 输入输出

---

CPU 与存储器分离是冯诺依曼模型的瓶颈

改进冯诺依曼模型：

• 缓存
• 虚拟内存
• 低级并行

缓存基础

• 缓存：可以比其他一些内存位置用更少的时间访问的内存位置的集合。
• CPU 高速缓存：CPU 可以比其访问主内存更快地访问的内存位置的集合。

CPU 高速缓存可以与 CPU 位于同一芯片上，也可以位于与普通存储芯片相比访问速度更快的单独芯片上。

• 缓存的想法

使用更广泛的互连，并在单个内存访问中传输更多数据或更多指令。

将数据块和指令块存储在实际上更靠近 CPU 寄存器的特殊内存中。

• 哪些数据或指令放 cache？
  • 程序倾向使用物理上接近最近使用的数据和指令。

局部性原理（系统使用更宽的互联结构访问数据和指令）

• 局部性 - 访问一个位置，然后访问附近的位置
  • 在访问一个内存位置后，程序将在不久的将来（时间局部性）访问附近的位置（空间局部性）。
• 为了利用局部性原理，系统使用更广泛的有效互连来访问数据和指令。（缓存块或缓存行）

​ 时间局部性

​ 空间局部性

cache 分级：
L1：最快最小
L2：
L3：最慢最大

Cache 查找由 L1 往下查找，Cache 中有信息，则命中；信息没找到，则称缺失；那么程序将会从主存读出查找的信息。

缓存写入策略
CPU 往 cache 写数据，cache 中的值和主存中的值不一致。
解决：写直达（writing-through）：写入 cache 时，立即写入主存。
写回（writing-back）：将数据更新的 cache line 标记为脏（dirty），然后 cache line 缓存替换时，dirty的行被写入主存。

Cache 映射

​ 全相联（fully associative）
​ 每个 cache line 可以放置在 cache 的任何位置
​ 直接映射（directed mapped）
​ 每个 cache line 在 cache 中有唯一位置
​ n 路组相联（n-way set associative）折中方案
​ 每个 cache line 可以放置到 cache 中 n 个不同区域中的一个

内存中的行能映射到 cache 中的多个不同位置时，如何决定替换或驱逐哪一行？
常用最近最少使用方案

虚拟存储器

大型程序，数据和指令集主存可能放不下，这时就是用虚拟存储器（虚拟内存）。
把当前程序用到的放入主存，暂时不需要的放入辅存。
虚拟内存也是对数据块和指令块进行操作，通常称为页。
辅存较主存慢非常多，所以也的大小通常比较大。

---

指令级并行

流水线

将功能分成多个单独的硬件或功能单元，

多发射

一个时钟周期发射多条指令，一般处理器有多个累加器或乘法器以实现多发射

• 编译时调度，静态多发射
• 运行时调度，动态多发射，超标量

为了能够多发射，需要用到预测，

---

硬件多线程

线程级并行

提供粗粒度的并行性，TLP 的线程 对 ILP 的指令

硬件多线程

任务阻塞，线程快速切换，继续其他任务

同步多线程

细粒度多线程变种，允许多个线程同时使用多个功能单元来利用超标量处理器的性能。
优先线程：有多条指令就绪的线程，能减轻线程减速的问题。

---

并行硬件

SISD

SIMD（好

单指令多数据，一个控制单元和多个 ALU，每个 ALU 要么在当前数据上执行同一个指令，要么空闲，下一条指令前需等待广播；通过在处理期间划分数据以提高并行性

向量处理器

对数组或数据向量操作；
向量寄存器：存储多个操作数组成的向量，并能对其内容进行操作
向量化和流水化的功能单元：相同操作应用于向量中的每个元素
向量指令：向量上的操作
交叉存储器：内存系统有多个内存体组成，访问一个内存体后，想再访问他有延迟，访问其他的内存体则很快
步长式存储器访问和硬件散射/聚集操作：固定步长访问向量元素；对无规律间隔的数据进行读（聚集）、写（散射）

优点：

• 速度快，易于使用
• 向量编译器擅长识别向量化代码
• 识别不能向量化的循环并提供不能向量化的原因
• 高内存带宽
• 每个加载的数据都使用

缺点：

• 可扩展性有限
• 不能处理不规则的数据结构

MISD

---

MIMD（好

多指令多数据，包括一组完全独立的处理单元或核，每个处理单元或核都有自己的控制单元和 ALU；
通常是异步的，即各个处理器能按照他们的节奏运行；
没有全局时钟，不同处理器的系统时间没有联系，除非强制同步。

共享内存系统

一个或者多核处理器，通过互联网络，与内存系统相互连接，处理器可以访问每个内存区域，处理器之间隐式通信。
通常每个核都拥有私有的 L1cache，其他级 cache 可能共享也可能不共享；

• 一致内存访问

互连网络将所有处理器直接连接到主存，每个处理器访问内存任意区域的时间相同

• 非一致内存访问

互连网络将每个处理器连接到一块内存，通过处理器中的硬件达到访问内存中其他块的目的，0 号处理器访问直接连接的 0 号内存速度快，0 号处理器访问 1 号处理器直接连接的 1 号内存速度慢。

分布式内存系统

分布式内存系统又称集群：由一组商品化系统组成，通过商品化网络连接（以太网）。
每个系统中的处理器连接系统内的自己的内存，每个系统通过互连网络进行显式通信。

---

互连网络

对两种内存系统有影响

• 共享内存互连网络

  共享内存系统，最常用总线和交叉开关矩阵

  总线

​ 交叉开关矩阵

​ 使用交换器控制数据传递，线表示双向链路。允许在不同设备间通信，速度比总线快；开销相对较高，成本也比较高。

• 分布式内存互连网络

1. 直接互连

交换器处理器一对一，交换机之间相互连接，形成一个环或者环面网格。比总线高级，因为允许多个通信同时发生。
环面网格比环成本高，因为交换器更复杂。

​ 等分宽度：
​ 衡量同时通信的链路数目或连接性的标准，计算链路数量

​ 链路带宽：
​ 传输数据的速度

​ 等分带宽：
​ 衡量网络质量，计算链路带宽。

最理想直接互联网络是：全相连网络
等分宽度：p^2/4
节点数量多不可能做这样的连接，因为他总共需要 p^2/4+p/2 条链路，不切实际。
所以一般作为衡量其他互连网络的基础

超立方体：
用于实际系统中的高度互连的直接互连网络，递归构造。
一维超立方体：全互连系统；二维超立方体：由两个一维组成，通过相应交换器相连，形成一个正方形；n 维超立方体有p=2^n个节点，每个节点和 n 个节点相连，等分宽度为p/2，连接性更高，但需要更强大交换器，以支持连线数量。
编号方法：直接相连的节点，编号只改变一位，例如 000 连 001、010、100。

2. 间接互连

通常由单向连接和一组处理器组成，每个处理器有一个输入链路和一个输出链路，链路通过交换网络连接

​ 交叉开关矩阵：
​ 类似共享内存系统中的交叉开关矩阵，但把双向链路改为单向链路，使用p^2个交换器。

​ omega 网络：
​ 交换器是 2x2 的交叉开关矩阵。成本较交叉开关网络低。共用了**1/2plog2^(p)个交换器，因为 2x2，所以总共是2plog2^(p)**个。

​ 胖树：

延迟与带宽

消息传送时间 = l + n / b

延迟（latency）：发送源开始传输数据到目的地接收数据的时间。

带宽（bandwidth）：目的地开始接收数据的速度。

---

内存结构层次

多个层次，cpu 内 cache 有多级，内存延迟，

Cache 一致性

每个 CPU 有自己的 Cache，所以在进行对数据的修改时，会遇到一致性的问题，过时的数据仍存储在 CPU 中。如果多 CPU 对一个 Cache 则不会，但因为是串行访问 cache，速度会慢。

一致性协议

直写和写回

处理器 A 和处理器 B，各自本地的 Cache Line 有同一个变量的拷贝，此时该 Cache Line 处于Shared状态。
处理器 A 在本地修改了变量，除了把本地变量的 Cache Line 改为Modified状态外，还需要在处理器 B 读同一个变量前把处理器 B 存这个变量的 Cache Line 改为Invalid状态。后续处理器 B 需要对这个变量读写时，会 Cache Miss。会重新从内存拷贝新的数据到 CacheLine 中。

监听 Cache 一致性协议

想法基于总线系统，监听总线，看到变量更新，则广播，并标记过时的变量为非法。
由于每次监听到改变都要广播，广播开销很大。

基于目录的 Cache 一致性协议

通过目录的数据结构，目录存储每行的状态，对应每个 Cache Line，更新 Cache，对应行的目录项就会更新。当变量要更新时，就会查目录，并将包含这个变量的 cache 置为非法状态。

伪共享

多个 CPU 的多个线程同时修改自己的变量。。。

---

并行软件

软件是负担，

SPMD（single program,multiple data）：

仅包含一段可执行代码，通过使用条件转移语句，让这段代码在执行时表现得像是在不同处理器上执行的程序。

进程或线程的协调

1. 分配任务，每个进程/线程分配大致相同的工作量，且使得通信量最小
2. 安排进程/线程之间的同步
3. 安排进程/线程之间的通信

共享内存

动态线程

共享内存程序使用。主线程等待任务，派生出新的线程，线程处理结束，被终止合并回主线程

静态线程

派生所有的线程，工作结束前，所有线程都在运行，所有线程合并回主线程后，主线程做清理工作（释放内存），然后终止。

静态线程比动态线程性能更好，但可能会浪费系统资源（对资源的利用不是很高效）

非确定性

定义：给定的输入产生不同的输出。MIMD 中，异步运行可能引发。

竞争条件

临界区

互斥

互斥锁（增强了临界区串行性）

忙等待

分布式内存

消息传递

char message [ 1 0 0 ] ;
. . .
my_rank = Get_rank ( ) ;
if ( my_rank == 1) {
     sprintf ( message , "Greetings from process 1" ) ;
     Send ( message , MSG_CHAR , 100 , 0 ) ;
} else if ( my_rank == 0) {
     Receive ( message , MSG_CHAR , 100 , 1 ) ;
     printf ( "Process 0 > Received: %s\n" , message ) ;
}

1. 程序段是 SPMD，两个程序使用相同的可执行代码，但执行不同的操作。执行的操作以来与他们的序号。
2. 不同进程中，变量指的是不同的内存块

单向通信

1. 单向通信或远程内存访问中，单个处理器调用一个函数
2. 能够简化通信，大大降低通信成本
3. 实践难以实现

划分全局地址空间的语言（PGAS 语言）

允许用户使用共享内存技术来对分布式内存硬件进行编程。

私有变量在运行程序的核的局部内存空间中分配，共享数据结构中数据的分配由程序员分配。

---

输入与输出

并行程序输入输出时，制定一些规则

• 在分布式内存程序中，只有进程 0 能够访问 stdin。共享内存程序中，只有主线程可以访问。
• 分布式内存和共享内存系统中，所有进程/线程都可以访问 stdout 和 stderr
• 因为输出到 stdout 的非确定顺序，一般只有一个进程/线程回将结果输出到 stdout。输出调试程序的结构是例外，它可以多个进程/线程写到 stdout
• 只有一个进程/线程你会尝试访问一个除 stdin、stdout 或者 stderr 以外的文件。例如每个进程/线程能打开自己私有的文件进行读/写，但没有两个进程/线程能打开相同的文件。
• 调试程序输出在生成输出结果时，应该包括进程/线程的序号或进程标识符。