11月3日笔记

矩阵乘法：

N×N 正方形矩阵，行数和列数不同时，是个普通矩阵

1 MFLOPS = 1 Million floating point operations per second

矩阵乘法函数degmm的总浮点操作数为2×N三次方

软件和硬件的并行性：软件（顺序、并发），硬件（串行、并行），软件并行和硬件并行的选择是独立的，并发软件也可以在串行硬件上运行，顺序软件也可以在并行硬件上运行

对于并行硬件有Flynn分类法

Flynn分类法：基于指令流的数量和数据流的数量，单指令流单数据流SISD、单指令流多数据流SIMD、多指令流单数据流、多指令流多数据流

最常见的并行处理编程风格是单程序多数据，简称SPMD，仅仅编写单程序在MIMD的所有处理器上运行，然后使用条件控制语句，使不同的处理器执行不同的代码段，实现跨处理器协作并行

SIMD使用专用功能硬件单元，用于处理涉及阵列的lock-step计算，eg.科学计算，机器学习，信号处理，多媒体音频和视频处理等

SISD：PU是处理单元，不利用任何数据流和指令流的并行性，eg 传统的单处理机器

SIMD：单个指令流应用于多个数据流的计算机，用于能够自然被并行化的操作，例如SIMD指令扩展和图形处理单元

MIMD：多个自治处理器同时对数据执行不同的指令，包括多核处理器，仓储级计算系统

MISD：对单数据流进行多指令流操作，用于能够被自然并行的数据操作，比如，某些类型的阵列处理器，已经不常见，应用也极少

SIMD架构：在多数据流执行相同的操作称为数据级并行，简称DLP，

例子：在一个滤波中，将一个系数向量和一个数据向量相乘，性能的提升主要来源于1、整个操作只需要读取和解码一条指令，2、乘法运算是独立的，不存在数据相关；3、访存中的流水或并发同样可以应用

第一个应用SIMD的机器：MIT Lincoln Labs TX-2 1957，第一次在计算机上使用向量系统运行程序

在Linux系统中，可以通过lscpu的命令，查看架构信息

为了实现浮点指令，例如fadd、fmul，在硬件上需要增加浮点运算单元，浮点寄存器，在RISC-V的F扩展中，寄存器的编号是f0～f31

虽然RISC-V矢量指令子集还没有定型，从草案中可以看出，RISC-V为了提升性能，使用SIMD指令和硬件，取一条指令，完成多条指令的工作，图中OP表示一个向量指令，前缀V表示向量寄存器，比如说vadd vd，vs1，vs2，表示把两个向量进行相加，把结果存在向量寄存器中，且假设向量的位宽为512比特

9.2 多指令多数据流

计算机系统的线程级并行处理技术

提高性能的方法：1、提高时钟频率，高性能处理器基本已达到当前技术工艺下的实际最大值，但通用计算机的工作频率仍低于5GHz，2、实现更低的每条指令的节拍数CPI，例如，SIMD的“instruction level parallelism”，3、同时运行多个任务，如多个CPU，可为每个CPU分配不同的任务来执行，这些任务之间可能是有关联的，例如每个CPU执行一个矩阵乘运算中的一部分运算，这些任务也可能是无关联的，例如我们可以同时运行powerpoint和浏览器

线程级并行的方法：涉及硬件中的多核架构，存储系统、输入输出系统，以及处理器核结构，

并行计算机体系结构形式：多台分布式计算机通过一些互联通信方式，如以太网，组合构成，也可以是高速通信互联的大规模计算机阵列组成，多核处理器，每个核都有一个独立的数据通路，核之间共享三级cache，主存和外设

多处理器执行机制：每个核各自执行运行指令，每个核都拥有一条独立的资源（如数据通路，片上的一级或者二级cache），这些核之间共享的资源（如主存或者三级cache）

对于多处理器中共享的主存，每个核都能访问整个主存，并且有特定的硬件负责维护cache的一致性，这样能通过一些共享的变量，简化程序间的通信，缺点：多核共享主存，使得主存的响应速度变慢，可能成为处理系统的性能瓶颈

使用多处理器有两种方式：1、任务级并行，不同的核运行互不相干的应用程序，程序间没有通信；2、单个任务划分成不同子任务部分，子任务分别运行在各个核上，例如每个核可以执行一个大的矩阵乘的一部分运算，

并行处理是计算机发展的并行选择，既能提高性能，又能降低能耗的可选途径之一，在手机、平板等移动设备系统中，都包含有多个处理器核，包括移动处理器，图像处理器，神经网络处理器在内的专用处理器

大规模计算集群则是由许多图形处理器，硬盘的计算级联组成，每个计算级联是MIMD方式的多核，以及扩展指令集的SIMD设计

线程，计算机中执行处理任务的顺序指令流，每条线程都有自己专用的1、程序计数器PC；2、各自的通用寄存器组，3、访问共享的存储器

每个物理核心都能提供1个或多个硬件线程用来执行指令，每次执行一条硬件线程，操作系统会在可获得的硬件线程上进行复用，形成多条软件线程，每次映射一条软件线程到硬件线程上执行，没有映射的软件线程则会等待执行

操作系统产生的许多条软件线程能产生一种许多线程同时被执行的错觉，这是通过将软件线程复用到硬件线程上实现的，通过切换，换掉被缓存缺失、用户输入，网络访问所阻塞的线程，或是通过定时切换，例如每1ms切换一次线程的方式，

从硬件线程上移除软件线程：中断软件线程的执行，同时在主存中保存好寄存器值和PC值

开始执行另一条软件线程的方法：将该线程之前保存在主存中的寄存器值，都装载到硬件线程配套的寄存器中，然后跳转到保存的PC值对应的地址空间去执行

多线程处理情况：某条活跃的线程遇到了一次缓存缺失，它需要等待大约1000个时钟节拍来从DRAM中读取数据，这时我们可以切换运行别的线程，直到需要读取的数据准备就绪，

问题：进行线程切换时，需要保存原线程的状态，并装载新线程的状态，如PC值，寄存器值等，那么就需要保证切换线程时保存装载状态所需时间不超过1000个时钟节拍，否则切换线程也就没有意义了

硬件协作的软件多线程：在一个处理器的数据通路中，配备有两套PC寄存器，和通用寄存器组，可以用来保存两条线程的状态，在软件看来，就如同有两个处理器核在同时运行两条线程一样

超线程，利用超标量处理器中的多发射机制，同时使两条线程具备执行状态，

这种同时将状态保存在同一个处理器核上的两个线程，称之为逻辑线程，这种设计为每条逻辑线程分配了独立的寄存器资源，但还是共用一条数据通路，ALU和Cache资源，在增加了1%额外硬件开销的同时，可提升大约10%的性能，

对比之前多核设计，多个处理器核共同工作方式，增加了50%的硬件开销，获取了约2倍的性能提升

9.3 线程级并行编程

提升计算机性能唯一途径，SIMD技术每3~4年可以实现2倍位宽提升，MIMD技术每2年有2个核的增长

处理器规模逐步提升时，如何在多处理器核上编写高性能并行程序，解决调度、负载平衡、同步、通信开销等问题。

TLP：Thread Level Parallelism

线程是指令序列，有自己的程序计数器值和处理器状态，在多核处理器中，每一个物理核上每次只执行一条线程的指令，当一条正在执行的线程需要响应输入输出事件，例如磁盘读写请求时，操作系统会控制进行线程切换，逻辑CPU的设计，能实现更细粒度的线程切换，用来处理因缓存缺失的访存读写带来的线程阻塞，超线程，简称HT，又称为同步多线程SMT，这种技术能利用超标量处理器架构将来自不同线程的多条指令同时发射执行

在超线程中，逻辑CPU数总是大于物理CPU数的，每个核都能同时运行多个线程，每个线程也都保存有各自的PC值，寄存器值等状态，同时线程间共享cache，指令单元，执行单元等硬件资源

不同场景下需求往往非常具体，科学计算中需要进行矩阵乘法运算，网页服务器需要同时处理许多不相关的访问请求，而计算系统中则是无时无刻不在处理各种输入输出请求，因此需要为特定的任务选择适用的语言，

openMP是操作系统创建的软件线程

9.4 硬件同步

为了避免数据竞争，通过同步写入和读取来获得确定的行为，用户级例程来完成同步，一般采用硬件同步指令

硬件同步：原子读、原子写，读和写都是单独的指令，在进行内存原子读，或者原子写操作的时候，不允许其它访问，必须使用共享内存的多处理器，常见的实现有使用原子交换，功能是将内存中的值和寄存器中的值进行交换，使用指令对，包含链接取数和存数，如果内存位置的值在链接读取以后被修改，则写入失败

RISC-V有两种变体，

原子内存操作（Atomic Memory Operations， AMOs）原子操作能够对内存中的操作数执行原子操作，并且设置目标寄存器为内存中的原始值，采用R型指令的常见格式有：Add、And、Or、Swap、Xor、Max、Max Unsigned、Min、Min Unsigned

如何保证只有一个线程进入临界区，假设锁在主存中的位置存储在寄存器a0中，

openMP中同步通常用于更高级的并行编程库中，openMP在通常情况下适用#pragmas编译指导语句，比如：critical、atomic、barrier、ordered等指示词

OpenMP还提供更多功能，例如，私有变量，规约等，

critical 临界区，一次只有一个线程进入

死锁：两个或以上进程在执行过程中，因为资源竞争而造成的互相等待的阻塞的系统状态，例如，哲学家就餐问题，

9.5 共享内存多处理器 SMP

多核通过存储总线，采用总线侦听协议，实现共享一个连续的内存空间

多处理器的关键问题：1、它们如何共享数据？2、它们如何协作？3、能够支持的处理器数量是多少？

对称多处理器：1、所有处理器（核心）都共享一个地址空间；2、处理器通过内存中的共享变量来进行协作和通信，共享数据的使用必须通过同步原语来协调，同步原语每次只允许一个处理器访问一个数据，现在所有的多核计算机都是SMP架构，即使只有一个处理器，访问内存也是系统的性能瓶颈，使用cache来减少主存的带宽需求，对多处理器每个核都有一个私有的cache来保存最近访问过的数据，只有cache缺失，才需要访问共享内存

硬件如何保证cache的一致性？每个cache都跟踪cache中的每个块的状态，一是共享状态shared，最新的数据，别的cache都可能有副本，二是修改状态modified，经过修改，别的cache中都没有副本，内存中数据过时，可写回，三是独占状态，最新的数据，其它cache中没有副本，可以写，内存中的数据是最新的，如果块被替换了，避免写入内存，提供数据以便被读取，而不需要访问内存；四是所有者状态，owner是最新的数据，其它cache可能有副本，其它cache中的数据必须是共享的状态，这个cache是多个有副本的cache的一个，修改数据时需要广播给所有共享该数据的cache中，所有者状态的引入，允许脏数据的共享，也就是说一个经过修改的数据块，可以在不更新主存的情况下，在各个cache中移动数据，在使所有的共享副本失效以后，可以将状态改成修改状态，或者通过将修改后的数据写回到主存，来将状态修改成其共享状态，所有状态的cache行，必须要响应数据的监听请求，

常用的cache一致性协议：MOESI

Modified（in cache） Owned（in cache） Exclusive（in cache） Shared（in cache） Invalid（not in cache）无效状态，cache中数据无效

伪共享：两个处理器在访问不同的变量，数据在处理器对应的cache中来回交换，数据在同一块的不同位置

cache中3C模型，第一类缺失为强制缺失，出现在冷启动或者进程迁移时，第一次访问的时候，解决办法是增加块大小，但同时会导致缺失代价增加，且过大的块会增加缺失率；第二类容量缺失，即使在有完美替换策略的全相联中，cache也不可能容纳程序所要访问的所有的块，解决办法是增加cache的容量，但是会增加访问时延，第三类是冲突缺失，多个内存地址映射到cache的同一个位置，解决办法：增加cache大小，增加关联度，这可能会增加访问时延，改进替换策略，如LRU算法，

Cache缺失模型的第四个C：一致性缺失，Coherence Missets，和其他处理器之间为了保持cache一致性而导致的cache缺失，也称为通信缺失，因为表示在并行程序中，一个并行程序中多个处理器上数据移动，对于有些并行程序，一致性缺失占据了cache缺失的主要部分