第10章——并行编程基础；第11章——多核处理结构；第12章——计算机系统评价和性能分析。

第10章 并行编程基础

1. 计算机体系结构是描述计算机各组成部分及其相互关系的一组规则和方法，是程序员所看到的计算机属性。
2. 计算机体系结构主要研究内容包括指令系统结构(ISA) 和 计算机组织结构(CO)。
3. 微体系结构是微处理器的组织结构，并行体系结构是并行计算机的组织结构。
4. 冯诺依曼结构的存储程序和指令驱动执行是现代计算机体系结构的基础。

10.1 程序的并行行为

程序的并行行为包括：指令级并行、数据级并行、任务级并行。

10.1.1 指令级并行

1. 只有RAW数据相关 和 控制相关真正制约指令级并行执行。
2. 实现方式：微结构设计技术。例如指令流水线、多发射、动态调度、寄存器重命名、转移猜测等。
3. 喂饱“饥饿”的运算器：转移猜测（提供足够的指令）、存储管理（提供足够的数据）。

10.1.2 数据级并行

1. 数据级并行是指对集合或者数组中的元素同时执行相同的操作。
2. 实现方式：现代处理器的向量功能部件、向量处理器、多处理器中SPMD编程。

10.1.3 任务级并行

1. 任务级并行是将不同的任务（进程或线程）分布到不同的处理单元上执行。
2. 分类：进程级并行、线程级并行。
3. 实现方式：让不同处理器执行不同的进程或线程。
4. 应用：商业应用领域、多道程序工作负载(Multiprogramming Workload)。

10.2 并行编程模型

分为单任务和多任务并行模型。单任务并行模型包括单任务数据并行模型；多任务并行模型包括多任务共享存储编程模型 和 多任务消息传递编程模型。

10.2.1 单任务数据并行模型

1. 数据级并行在SIMD计算机上实现，着重开发指令级并行，为单任务数据并行；在SPMD计算机上实现，着重开发子程序级并行，为多任务数据并行。
2. 特点：单线程、同构并行、全局命名空间、隐式相互作用、隐式数据分配。

10.2.2 多任务共享存储编程模型

1. 运行在各处理器上的进程/线程通过读写共享存储器上的共享变量来进行通信。
2. 特点：多线程异步执行、单一的全局名字空间、隐式数据分配、显式或隐式负载分配、显式同步。
3. 常见模型：Pthreads、OpenMP等。

10.2.3 多任务消息传递编程模型

1. 不同处理器上的进程/线程拥有独立的地址空间，通过网络传递消息来相互通信。
2. 特点：多进程异步执行、独立的地址空间、显式相互作用、显式分配。
3. 常见模型：MPI、PVM。

10.2.4 共享存储与消息传递编程模型的编程复杂度

1. 共享存储中，所有处理器共享同一个主存储器，统一编址；消息传递中，每个处理器有一个它自己才能访问的局部存储器，每个存储器单独编址。
2. 共享存储中，程序员只需要对计算任务进行划分；消息传递中，程序员需要对计算任务、数据进行划分，并安排进程间的所有通信。

10.3 典型并行编程环境

数据并行：SIMD

共享存储编程模型：Pthreads和OpenMP

消息传递编程模型：MPI

10.3.1 数据并行SIMD编程

向量指令（vld, vadd.b, vst等），利用向量寄存器实现。龙芯的向量寄存器复用了浮点寄存器。

10.3.2 Pthreads

C语言的一套函数库。利用pthread_create, pthread_join, pthread_exit, pthread_self管理线程，利用pthread_yield, pthread_cancel调度线程，利用pthread_mutex_init, pthread_mutex_lock/unlock, pthread_cond_init, pthread_cond_wait/signal/broadcast等同步线程。

10.3.3 OpenMP

• 主要 API：制导指令、运行库、环境变量。
• 常见子句：
  • 共享：shared(var1, var2, ...)
  • 私有：private(var1, var2, ...)
  • 归约：reduction(op:var)

例如，#pragma omp parallel for private(i, x), reduction(+:sum)语句表示在接下来的循环中，使用多个线程并行执行，并设置i和x变量为私有，sum变量为归约变量。

10.3.4 MPI

1. 主要API：6个基本函数：

   序号	函数名	含义
   1	MPI_Init	初始化MPI执行环境
   2	MPI_Finalize	结束MPI执行环境
   3	MPI_Comm_size	确定进程数
   4	MPI_Comm_rank	确定自己的进程标识符
   5	MPI_Send	发送一条消息
   6	MPI_Recv	接收一条消息

   comm代表communicator，通信域。通信域包含进程组和通信上下文。

2. 点对点通信方式：阻塞方式和非阻塞方式。前者等消息从本地送出后才继续执行，保证缓冲区等资源可再用；后者不等消息从本地送出就继续执行，不保证缓冲区等资源可再用。
3. 四种通信模式：
   • 标准模式：由MPI决定后面三种模式选哪一种；
   • 缓冲模式：使用缓存存储消息，发送与接收无关；
   • 同步模式：等接收开始后，发送才能返回；
   • 就绪模式：等接收启动后，发送才能开始。
4. 集体通信(Collective Communication)：
   • 栅障(MPI_Barrier)
   • 广播(MPI_Bcast)
   • 收集(MPI_Gather)
   • 散播(MPI_Scatter)
   • 归约(MPI_Reduce, MPI_Allreduce)

第11章 多核处理结构

11.1 多核处理器的发展演化

• 提出背景

1. 半导体工艺：摩尔定律放慢、面临失效。且工艺提升对性能带来的红利在缩小。
2. 功耗墙：提高单核性能功耗开销比多核大。
3. 并行结构的发展：SIMD、SMP、CC-NUMA、MPP结构……

• GPU采用什么结构？

GPU（图形处理器）采用流水线结构来实现并行化。流水线结构包括一组处理器，每个处理器都有一个特定的角色，它们协同工作，按照一定顺序处理数据。SM（Streaming Multiprocessor）是 GPU 中的一种基本组成单元，通常称为“流处理器”。SM 包含多个处理器核心，用于执行并行计算。

流水线结构是将一个大任务分解成若干个小任务，并将这些小任务分配给不同的流水线处理器来实现并行化，而 SM 就是这样的一个流水线处理器。

• 分类方式

1. 按照从核数量：多核处理器和众核处理器（一般指多于64核的处理器）；
2. 按照处理器核结构：同构和异构；
3. 按照适用应用：通用和专用（GPU可以看作是一种专用多核处理器，具有很高的浮点峰值运算性能）。

• 流行的CPU结构

1. 多核+向量处理
2. 众核（GPU是其中一种，同构）
3. 带有协处理器的异构多核

• 存储结构：通用多核处理器一般采用共享存储结构。

11.2 多核处理器的访存结构

需要关心的问题：

1. 存储一致性：多核处理器的访存指令次序如何约定？
2. 片上Cache结构：Cache结构采用私有还是共享？集中式还是分布式？
3. Cache一致性：一个数据可能在多个处理器的私有Cache中和内存中存在备份，如何保证数据一致性？

11.2.1 片上Cache结构

1. 主流结构：片内共享LLC，片间共享内存。
2. 共享LLC结构中，主要有UCA和NUCA结构。

11.2.2 存储一致性模型

• 顺序一致性模型；在顺序一致性约束下，多处理机的表现与对应的单处理机多进程表现一致（和OS中研究的那种表现一致）。
• 处理器一致性模型：在任意load开始执行前，先于它的load操作都要完成；在任意store开始执行前，先于它的load和store操作都已完成。换句话说，可以在某个load执行时，先于它的store操作还没有执行或没有执行完。也就是允许load越过store操作执行。实际上是把write buffer变得让用户可见。
• 弱一致性模型：同步操作和访存操作满足顺序一致性，也就是说，同步操作执行前的访存操作都已完成，访存操作执行前的同步操作都已完成。
• 释放一致性模型：把同步操作拆分成acquire和release操作。同步操作满足顺序一致性。release操作执行前的访存操作都已完成（收工之后才能释放锁），访存操作执行前的acquire操作都已完成（可以进到临界区）。

11.2.3 Cache一致性协议

1. 定义：一种把新写的值传播到其它处理器核的机制。
2. 分类：
   • 如何传播：写无效(Write Invalidate)和写更新(Write Update);
   • 向谁传播：侦听协议(Snoopy)和目录协议(Directory)。
3. 写无效协议与写更新协议：
   • 写无效协议：某个处理器Cache值更新时，先令其它处理器中相应单元的值标记为无效，等其他处理器要用到该单元时，再更新为新值。
   • 写更新协议：某个处理器Cache值更新时，即把新值更新到其它处理器的Cache中。
4. 侦听协议与目录协议：
   • 侦听协议：写数的处理机把新写的值或要读取的地址广播出去；其它处理机侦听广播，广播中内容与自己有关时接受新值或提供数据。适用于总线互连结构。
   • 目录协议：每个Cache存储行都维护一个目录项，目录项记录了每个处理器核是否含有该行的备份。目录项另有一个改写位，记录是否有某个处理器改写了改行。可以避免广播，但是存储开销大，需要动态维护。
5. Cache状态：Cache一致性协议是通过维护每个Cache行的一致性状态来实现的。具体有ESI、MESI和MOESI，其中ESI最简单，MESI较常见。
6. ESI：（※ESI状态转换重要）
   • E（Exclusive，独占）：对应Cache行被当前处理器核独占。其它处理器核需要等当前处理器释放；
   • S（Shared，共享）：多处理器核共享，因此是只读的。
   • I（Invalid，无效）：当前Cache行无效。
7. MESI：增加M状态。这时，E状态修改为，当前Cache行虽然被独占，但是还没有被修改；M状态自然表示被独占且已经被修改。
8. 存储一致性与Cache一致性：Cache一致性都是针对某种存储一致性设计的。常用弱一致性模型。

11.3 互连结构

1. 常见片上互连结构：片上总线、交叉开关、片上网络。
2. 连接处理器核、Cache、内存控制器、IO接口等模块。

11.3.1 片上总线

1. 由一组信号线连接各功能模块。
2. 包括数据总线、地址总线、控制总线等。
3. 优点：实现简单->利于广播通信。
4. 缺点：独立资源->可伸缩性差。
5. 结点间采用握手方式建立直通链路。

11.3.2 交叉开关

1. 以矩阵形式组织的开关，任意输入端口可以接上任意输出端口。
2. 具有非阻塞特性，在不冲突的前提下可以建立多个输入输出连接。
3. 优点：并行非阻塞通信->高带宽。
4. 缺点：复杂度为O(mn)->可伸缩性有限。
5. 结点间采用握手方式建立直通链路。

11.3.3 片上网络

• 概念

1. 数据封装成数据包，通过路由器之间的分组交换和存储转发机制实现处理器核间通信。
2. 抽象成节点、互连网络、网络接口。
3. 研究内容：拓扑结构、路由算法、流量控制。

• 拓扑结构

环(ring)、网格(mesh)。

• 路由算法

1. 环的路由方法：只有唯一一种。
2. Mesh网的路由方法：维序路由（一路走到头）、全局自适应路由（优选负载较轻方向）。

• 路由器结构

1. 路由器由寄存器、交叉开关、功能单元和控制逻辑组成。
2. 适合Mesh结构的路由器：输入端口连接buffer；分配器管理buffer和交叉开关；buffer连接到交叉开关，从而连接到输出上。
3. 分配器作用：路由计算、虚通道分配、交叉开关分配。
4. 数据包传输有四个流水级：路由计算(RC)、虚通道分配(VA)、交叉开关分配(SA)、交叉开关上传输(ST)。head flit经过四个流水级，body flit经过后两个流水级。

• 流量控制

1. 片上网络的主要资源：信道和缓冲区。
2. 好的流量控制策略：公平性和无死锁。
3. 每个结点都有向相邻节点发送数据的缓冲区Buffer，和记录相邻节点缓冲区使用量的计数器S[0-3]。流量控制方法详见课本。

11.4 多核处理器的同步机制

1. 对共享变量需要进行同步，否则同一个并行程序可能在不同的运行中产生不同的结果。
2. 三种常见的同步机制：锁、栅障、事务内存。
3. 常用硬件同步指令实现上述同步机制。

11.4.1 硬件同步指令

主要是“读-改-写”指令和“LL/SC”指令。

• 读-改-写

名称	含义
Test_and_Set	取出对应地址上的值，并为其赋一个新值。
Swap	交换两个地址上的值。
Compare_and_Swap	如果对应地址上的值和A相等，则把B赋给这个地址，否则这个地址的值不动。
Fetch_and_Op	取出对应地址上的值，进行某种运算Op，然后存回去。

• LL/SC

LL指令将某个地址上的值读取到寄存器中，并将LLbit置为1。

LL执行完但SC指令尚未执行时，如果该地址上的值被其他处理器访问，或者执行了eret操作，则将LLbit置为0。

SC指令检查LLbit，如果是1，则将寄存器的值更新到该地址上，并且把寄存器的值重新设为1，表示成功；否则不更新该地址上的值，并把寄存器的值重新设为0，表示失败。

如果失败，一般需要回到开头LL处，重新执行。

11.4.2 锁

1. 使用Test_and_Set实现，是一种基本的实现方式。
2. 缺点：获取锁失败时要循环访问，产生大量片上互连通信。
3. 解决方式：可以在相邻两次循环访问之间引入延迟。

11.4.3 栅障

1. 使用Fetch_and_Inc实现：

   barrier(){
       Fetch_and_Inc(count);
       while(count != Max) ;
   }
   

2. 缺点：与自旋锁相同，有大量通信。

11.4.4 事务内存

1. 事务：事务内存中，访问共享变量的代码区域声明为一个事务。
2. 事务的性质：
   • 原子性：这个代码区域中的所有指令要么都执行要么都不执行。
   • 一致性：任何时刻内存一致。
   • 隔离性：不同事务内部对象状态互不可见。事务执行结束后，如果执行成功，将所有结果提交到内存中；如果执行失败，中止并取消所有结果。
3. 实现方式：
   • 软件事务内存：库函数或编程语言；
   • 硬件事务内存：主要对多核处理器的Cache结构进行改造。例如Intel TSX新增了三条指令XBEGIN, XEND和XABORT，以Cache行为单位跟踪事务的读集和写集。

11.5 典型多核处理器

第12章 计算机系统评价和性能分析

1. 性能最本质的定义：完成一个任务所需要的时间。
2. 性能分析方法：分析、模拟、测量。

12.1 计算机系统性能评价指标

1. 不同系统所关注的性能：
   • 桌面计算机：大文件压缩、音视频播放……
   • Web服务器：每秒所完成的Web请求数，衡量指标是吞吐率（每秒完成的交易事务）。
   • 高性能计算机：衡量指标是完成一个大的并行任务的速度。
2. 影响性能的因素：应用（影响最大，不同系统各有所长各有所短）、算法、编译系统、指令系统、微结构（影响IPC、主频）、工艺（主要影响主频）。

3. 常见性能指标：CPI、 MIPS、 MFLOPS、 TPS、 FPS、 MBPS、 MHz

   名称	全称	含义
   CPI	Cycles Per Instruction	每条指令的时钟周期数
   MIPS	Millon Instructions Per Second	每秒执行百万条指令数
   MFLOPS	Mllion Floating Point Operations Per Second	每秒执行 百万浮点运算数
   TPS	Transactions Per Second	每秒执行的事务数
   FPS	Frames Per Second	每秒帧数
   MBPS	MB Per Second	每秒完成多少MB的访存操作，带宽的单位
   MHz	-	兆赫兹，主频的单位

4. CPU时间 = 指令数 × IPC × 主频
   • 指令数：算法、编译器、ISA
   • IPC：微结构、编译器、ISA
   • 主频：微结构、工艺技术、逻辑设计（如串行进位和并行进位加法器）、物理设计（如动态电路的使用）
5. 并行系统的评价指标：可扩展性、加速比。
6. 阿姆达尔定律：系统中对某一部分改进后获得的整体性能提升程度，取决于部分被使用的频率，或所占总执行时间的比例。

12.2 测试程序集（黑盒法）

1. 特点：
   • 公平性：拿程序来测，看看实际性能表现，而不是只看个别技术指标。
   • 侧重性：不同计算机侧重点不同，需要不同的测试程序。
   • 全面性：测试程序要有代表性，覆盖面足够广。
   • 公开性：测试报告要详细，便于查阅。
2. 常见基准测试程序类型：
   • 微基准测试程序：Sim-alpha的microbench, LMbench, STREAM, CoreMark, UnixBench等。
   • 串行CPU基准测试程序：SPEC CPU, EEMBC。
   • 并行CPU基准测试程序：SPLASH-2（测并行加速比）, PARSEC（测并行加速比）, Linpack（测并行浮点峰值）。
   • 专项基准测试程序：SPEC jvm, SPEC jbb, SPECSFS, SPEC viewperf, TPC。
3. 微（基准）测试程序：小的测试程序，能在短时间内跑完，可以用于处理器某些模块的专门优化。

12.3 性能分析方法（白盒法）

1. 分类：
   • 性能建模
     • 分析建模：概率模型、队列模型、马尔可夫模型、Petri网模型。
     • 模拟建模：踪迹驱动模拟、执行驱动模拟、全系统模拟、事件驱动模拟、统计方法模拟。
   • 性能测量：片上硬件监测器（如性能计数器）、片外硬件监测器、软件监测器、微码插桩。
2. 基于分析和统计的建模（分析建模）：基于对处理器结构和程序特性的分析，建立处理器的性能公式，通过数学公式计算出处理器的性能信息。
3. 基于模拟的建模（模拟建模）：用高级语言编写模拟器，模拟CPU进行建模。是处理器设计中用得最为广泛的方法。
4. 常用的模拟器：SimpleScalar, SimOS, GEM5, IBM的Mambo和Turandot, AMD的SimNow等。有两种分类：
   • 系统模拟器和部件模拟器
   • 全系统模拟器和用户态模拟器
5. 模拟加速技术：在模拟速度和精度之间折中。代表性技术是采样模拟技术和统计模拟技术。
   • 采样模拟技术：截取程序的一小部分进行模拟，近似代表整个程序的模拟结果。SMART：周期采样；SimPoint：采样能够代表每个相位的部分。
   • 统计模拟技术：用统计方法分析工作负载，得出多种类型的统计信息，由此生成合成的程序踪迹，包含有工作负载抽象提炼出的信息，因此能在模拟器上很快地收敛。
6. 模拟器和真实系统的绝对误差是无法避免的，但是模拟结果和真是系统的偏差是稳定的，可以用同一个模拟器模拟多个不同的系统来进行相对比较。
7. 性能计数器的优势：可以统计复杂应用的行为，实时监测系统行为（模拟器办不到，只能运行简单的程序）。
8. Perf性能分析工具：集成在Linux系统中的性能分析工具，基于事件采样原理，采样硬件事件、软件事件、tracepoint触发的事件。