爱华网第一章 并行计算简介
并行计算：一般是指许多指令得以同时进行的计算模式。
开发并行处理技术的目的：单用户来说，可以提高加速比，对于多用户来说，可以提高吞率。
典型的并行应用：天气预报、地震预报、石油工业、航空航天等。
并行处理计算机系统：并行处理计算机系统是指同时执行多个任务或多条指令或同时对多个数据项进行处理的计算机系统。
第二章 加速比性能模型与可扩展性分析
处理机—时间积：处理机数目与处理时间的乘积，用以度量这些处理机运行时的资源利用率。
最大工作量：若一程序在P台处理机上运行的时间为Tp，则此P台处理机在Tp时间间隔内完成的工作最大数量为Tp×P。
有效工作量：处理机实际工作曲线对时间的积分。
效率：有效工作量与最大工作量之比。
并行度（Degree OfParallelism）：在一定时间间隔内执行一个程序所用的处理机的数目。
工作负载：DOP与对应时间的间隔之积即为处理机要完成的工作或工作负载。
绝对加速比：将最好的串行算法与并行算法相比较。
相对加速比：同一并行算法在单节点上运行时间与在多个相同节点构成的处理机系统上的运行时间之比。
线性加速比：中间开销小，通信少，弱耦合计算；
超线性加速比：当应用需要大内存时可能出现；
病态加速比：加速比递减，可能是计算量太小。
三种加速比模型名称和特点：
固定负载加速比性能模型——Amdahl定律：在许多实时应用领域，计算负载的大小常固定。在并行机中，此负载可分布至多台并行执行，获得的加速比称为fixed-loadspeedup。则n个节点情况下，加速比可以表示如下：
其中，串行因子α为串行部分所占的比例。固定负载模型有缺陷：因为Amdahl’law中，α取决于问题及并行编译器的效率，无法描述系统固有的特性。
固定时间加速比性能模型——Gustafsun定律：当机器的规模扩大时，解题的规模也随着扩大，从而得到更加精确的解，而使运行时间保持不变。
受限于存储器的加速比模型——Sun-Li定律：大型科学计算和工程设计需要较大的存储空间，许多应用问题是存储器受限，而不是CPU受限或者I/O受限。基本思想：要在存储空间有限条件下解尽可能大的问题，这同样需要扩展工作负载，才能提供较高的加速比、较高的精度和较好的资源利用率。加速比可以表示如下：
而G(n)反映的是存储容量增加n倍时并行工作负载增加的倍数。
1. G(n) = 1，即为固定负载的情况；
2. G(n) = n，即存储器增加n倍，负载也增加n倍，为固定时间的情形；
3. G(n) > n，计算负载的增加情况比存储器增加快，会有较高的加速比。
可扩展性的直观定义：对任意数量（n）的处理机和任意规模（s）的问题，若所有算法的系统效率 E = 1，则系统是可扩展的。
规模可扩展性：系统性能随处理机数量线性增长，包括：
处理速度和效率
存储速度和容量
互连带宽和时延
I/O速度和容量
软件开销
换代（时间）可扩展性：对系统各部分更换成新技术后，性能随之扩展，要求算法能兼容运行。
问题可扩展性：问题规模扩大时，系统仍能很好的运行，或说问题规模扩展到很大时，系统能在给定粒度下高效运行。
恒等效率：恒等效率定义为一个并行算法在并行计算机上实现时，为保持效率E固定所需的工作负载与机器规模n的相对关系。
设W = W（s）为工作负载，
h = h（s，n）为通信开销，它随s、n增加而增大。其中，s为问题规模，n为机器规模。则效率可以表示为：
为了使E保持不变，工作负载W（s）应该与开销h(s,n)成比例增长，由此可以得出以下条件：为了得到恒等效率，只要使W(s)与h(s,n)同一个数量级就可以了。（计算）
例1：
矩阵乘法的W(s) = O（s3）（其中s为维数），还设h（s，n）= O（nlogn+s2n0.5）。求fE(n) 。
解：
要满足W与h同数量级的条件，需要在两种情况中选出较大的：
第三章 互连与通信
互连网络：由开关元件按一定拓扑结构和控制方式构成的网络以实现计算机系统内部多个处理机或多个功能部件间的相互连接。
操作方式：
同步通信（Synchronous Communication)
异步通信(Asynchronous Communication)
控制策略：
集中控制(Centralized control)
分布控制(Distributed control)
交换方式：
电路交换(Circuit switching)
分组交换(Packet switching)
Wormhole交换(Wormhole switching)
网络拓扑结构：
静态网络(Static network)
动态网络(Dynamic network)
静态网络的网络指标：
特点：点点相连，不会改变。
结点度：与结点相连接的边（链路或通道）数，表示节点所需要的I/O端口数，模块化要求结点度保持恒定。根据通道到结点的方向，结点度可以进一步表示为：
结点度 = 入度 + 出度，其中入度是进入结点的通道数，出度是从结点出来的通道数。
距离：与两个结点之间相连的最少边数。
网络直径：网络中任意两个结点间距离的最大值。
网络规模：网络中结点数，表示该网络功能连结部件的多少。
等分宽度：某一网络被切成相等的两半时，沿切口的最小边数称为该网络的等分宽度。
结点间的线长：两个结点间的线的长度。
对称性：从任何结点看，拓扑结构都一样，这种网络实现和编程都很容易。
结点是否同构。
通道是否有缓冲。
典型的静态网络：
线性阵列：对N个结点的线性阵列，有N-1条链路，直径为N-1（任意两点之间距离的最大值），度为2，不对称，等分宽度为1。
环：双向环：链路数为N，直径N/2，度为2，对称，等分宽度为2。
单向环：链路数为N，直径N-1，度为2，对称，等分宽度为2。
带弦环、全链接、树形
星形：星形实际上是一种二层树（如右图）。有N个结点的星形网络，有N - 1条链路，直径为2，最大结点度为N -1，非对称，等分宽度为1。
网格：有N个结点的r×r网格，有2N - 2r (请证明)条链路，直径为2(r-1)，结点度为4，非对称，等分宽度为r。
超立方体、带环立方体。
带环树和二叉胖树可以缓解根结点的瓶颈问题。
消息（Message）：是在多计算机系统的处理节点之间传递包含数据和同步消息的信息包。它是一种逻辑单位，可由任意数量的包构成。
包（Packet）：包的长度随协议不同而不同，它是信息传送的最小单位，64-512位。
片（Flit）：片的长度固定，一般为8位。
传输时延：一个消息的传输时延：从它在源结点进行发送初始化到它在目的结点完整的被接收所耗费的时间。一个网络的传输时延：在一定条件下发送消息的平均时延。传输时延可以表示为：，
建立时延Ts：一个消息在源结点和目的结点上装配和分解、从存储器拷贝到通信缓冲区以及正确性验证等所耗费的时间。
网络时延Tn：消息头部从源结点进入网络到消息的尾部到达目的结点的时间间隔。
阻塞时延Tb：消息传递过程中其他所有可能的时延（主要原因是资源冲突）。
网络的吞吐量：单位时间内网络所能传输的消息数目或长度。
四种寻径方式：
线路交换（CircuitSwitching）：在传递一个消息前，先建立一条从源结点到目的结点的物理通路，然后再传递消息。其传输时延用公式表示为：
T=(Lt/B)×D+L/B，
其中Lt为建立路径所需的小信息包的长度，L为信息包的长度，D为经过的结点数，B为带宽（以下同）。
存储转发（Store-and-Forward）：在存储转发网络中包是信息流的基本单位。每个结点有一个包缓冲区。包从源结点经过一系列中间结点到达目的结点。当一个包到达一个中间结点时，它首先被存入缓冲区。当所要求的输出通道和接收结点的包缓冲区可使用时，然后再传送给下一个结点。存储转发网络的时延与源和目的地之间的距离（段数）成正比。其时延用公式表示成为T=(D+1)×L/B。
虚拟直通（Virtual cutthrough）：其思想是为了减少时延，没有必要等到整个消息全部缓冲后再作路由选择，只要收到用作寻径的消息头部即可以判断。
其通信时延用公式表示为T=(Lh/B)×D+L/B，Lh是消息的寻径头部的长度。一般说来，L>>Lh×D，所以公式可近似为T=L/B，可以看出此时通信时延与结点数无关，这相对于存储转发寻径方式来说是一个非常大的改进。
Wormhole交换（WormholeSwitching)：把包进一步分成更小的片。与结点相连的硬件寻径器中有片缓冲区。当消息的头片到达一个结点的寻径器后，寻径器根据头片的寻径消息立即做出路由选择。
虫蚀寻径的通信时延用公式表示为T=Tf×D+L/B=(Lf/B)×D＋L/B=(Lf×D＋L)/B，Lf是片的长度，Tf是片经过一个结点所需时间。一般来说，L>>Lf×D，所以公式可以近似为T＝L/B，可以看到此时通信时延也与结点数无关。
虚拟通道(逻辑链)：由源结点的片缓冲区、结点间的物理通道和接收结点的缓冲区组成。
死锁产生的原因：缓冲区产生死锁、通信产生死锁。
四种包冲突的解决方法：用缓冲实现虚拟直通寻径、阻塞流控制（Wormhole寻径）、抛弃并重发、阻塞后绕道。
通信模式：
单播模式（Unicast）：一个源结点——一个目的结点。
选播模式（Multicast）：一个源结点——多个目的结点。（多播、组播）
广播模式（Broadcast）：一个源结点——全体结点。
会议模式（Conference）：多个源结点——多个目的结点。
寻径效率：
通信流量（Channel traffic）：用传输有关消息所使用的通道数来表示。
通信时延（Communication latency）：用包的最长传输时间来表示。
第四章 并行存储器系统
存储器系统的层次结构：
五个参数：
存取时间ti：从CPU到第i层存储器的往返时间
存储器容量Si：第i层的字节的数量
每字节成本Ci：第i层存储器的成本为CiSi
传输带宽bi：相邻层之间传送信息的速率
传输单位Xi：i和i+1层之间数据传送的粒度
写直达（write-through,WT），即如果在Mi（i=1，2，…，n-1）中修改了一个字，则在Mi+1中需要立即修改。
写回（write-back,WB），即如果在Mi+1 中的修改延迟到Mi中正在修改的字被替换时才进行。
时间局部性：最近的访问项（指令或数据）很可能在不久的将来再次被访问。
空间局部性：一个进程访问的各项的地址彼此很近，例如，表操作或数组操作含对地址空间中某一区域的集中访问。
对Mi的访问频率为：
，是指在较低层次有i-1次缺失而在Mi有一次命中时访问Mi成功的概率。
有效存取时间Teff：
需要解决的问题：定位问题、寻址问题、替换问题、一致性策略。
共享存储和分布存储的优缺点：
共享存储器：
易于编程，是单机的自然延伸；
程序员没有数据划分的负担；
多进程并发的开销小，效率高，易于进程迁移，任务动态分配简单；
由于每个处理器都通过总线访问存储器，因而限制了处理器的个数，可扩展性差。
分布存储器：
系统结构灵活，可扩展性好；
处理机数目可达成百上千，处理速度有巨大的发展潜力；
算法设计、编程以及任务动态分配比较困难；
很难在处理机之间传递复杂的数据结构，难于进程迁移；
不能支持需要存储空间的大规模数据处理要求。
DSM与SVM：共享分布存储器（Distributed shared Memory，DSM）、虚拟共享存储器（SharedVirtual Memory，SVM）。
低位交叉方式：存储器地址的低a位用来指明存储器模块，高b位是每个模块内的字地址。
高位交叉方式：存储器地址的高a位作为存储器模块地址，邻接的存储器单元被分配在同一个存储器模块中，在每个存储器周期内，只能对各模块存取一个字。所以不支持邻接单元的成块存取。
容错：将高位与低位交叉存取加以组合。
第五章 Cache一致性
Cache不一致性引起的原因：
共享可写数据的不一致性
进程迁移的不一致性
绕过Cache的I/O操作带来的不一致性
设计Cache一致性协议的两种策略：
写无效：任一处理器写它的私有Cache时，它都使所有其它的Cache中的副本失效。对Write-through，它也更新memory中的副本（最终是一个Cache中的副本和memory中的副本是有效的）。对Write-back，它使memory中的副本也失效（最终只有一个Cache中的副本是有效的）。
写更新：任一处理器写它的私有Cache时，它都立即更新所有其它的Cache中的副本。对Write-through，它也更新主存储器中的副本。对Write-back，对存储器中副本的更新延迟到这个Cache被置换的时刻。
一致性协议包括：
（1）Cache可能出现的状态集合
（2）共享主存的状态
（3）为维护一致性而引起的状态转换。
每份Cache中的副本可能出现的四种状态 ：
（1）有效（validstate）：与主存储器副本一致的Cache副本，即该副本未经修改，所以这个Cache副本不是唯一的副本。
（2）保留（reservedstate）：这一Cache副本是第一次修改，并用写通过方法写入主存，所以这一Cache副本和主存储器副本一致。
（3）重写（dirtystate）：Cache副本不止一次被修改过，由于不再采用写通过方法，所以这个Cache副本是唯一的副本。与存储器和其它的Cache副本都不一致。主存储器中的副本也是无效的。
（4）无效（invalid state）与存储器或其它的Cache副本不一致，或在Cache中找不到。
局部命令（Local commands）：
（1）P-Read：本地处理机读自己的Cache副本。
（2）P-Write：本地处理机写自己的Cache副本。
一致性命令
（1）Read-blk：从另一Cache读一份有效的副本。
（2）Write-inv：在写命中时在总线上广播一个无效命令。
（3）Read-inv：在写缺失时在总线上广播一个无效命令。
“写一次”协议的状态转换图：
Cache一致性协议的开销分析
（1）采用写无效协议：无效后，当其它处理机再读该副本时，出现Read miss，要有开销
（2）采用写更新协议：需要更新所有Cache和memory中的副本，所以开销大，有些处理机对更新后的数据可能不会使用。
基于目录的Cache一致性协议的基本思想：只发送给存放该副本的Cache。
三种目录实现(全映射、有限、链式)及其各自优缺点：
全映射（fullmap）目录：存放与全局存储器中每个块有关的数据。系统中的每个Cache可以同时存储任何数据块的副本，即每个目录项包含N个指针（N是处理机数目）。目录的总所占空间和N2成正比，不便于扩展
有限（limited）目录：每个目录项有固定数目的指针（小于N）。
链式（chained）目录：将目录分布到各个Cache（其余同全映射目录）。所占的空间及可扩展性同有限目录。
采用Write-Once策略的Cache状态转移：
如果处于“有效”状态：
（1）本地读Rl，不影响状态。
（2）本地写Wl（第一次写），采用Write-Through策略，这时要发无效命令给其它Cache中相应的副本，并修改memory。
有效——保留
（3）远程写Wr（不管是第几次写），远程CPU会发无效命令。
（4）远程读Rr：不影响状态
如果处于“保留”状态：
（1）本地读Rl，不影响状态。
（2）远程读Rr：这时Cache中只有处于保留状态的数据块是正确的，所以把该数据块送到远程CPU的Cache中（远程Cache中该数据块变为有效），本数据块状态已变为有效。
（3）本地写Wl：第二次及以后的写，采取Write-Back策略，不修改Memory，状态由Reserved变为Dirty（这时只有一个副本有效），发无效命令给其它Cache的对应的副本，使Memory中的副本也无效。
（4）远程写Wr：远程CPU会发无效命令，使状态由Reserved变为Invalid。
如果处于“重写”状态：
（1）本地读Rl：不影响状态。
（2）本地写Wl：不影响状态。
（3）远程读Rr：这时只有这个Cache的数据块是正确的，所以把该数据块发送给远程的Cache，远程Cache的数据块和本Cache中的数据块都变得有效。
（4）远程写Wr：远程CPU写后，发无效命令使状态由重写®无效。
如果处于“无效”状态：
（1）本地读Rl：这时产生Read-Miss，设法找到有效的数据块调入Cache：读入后相应数据块进入“有效”状态。
（2）远程读Rr：状态不变
（3）本地写Wl：一定是Write-Miss，系统首先把正确的内容调入Cache，然后写Cache，因为是第一次写，所以Write-Through策略，同时写memory，将本地Cache状态置为“保留”，同时将系统中其它相应的数据块置为“无效”
（4）远程写Wr：状态不变
多核技术的优点和面临的挑战：
多核处理器比相同工艺、相同面积的单核处理器具有以下的优点：
逻辑简单、高主频、低通信延迟、低功耗、设计和验证周期短
挑战：
(1) 程序是否具备扩展性
(2) 程序能否更精确
(3) 产品是否易于编程和维护
(4) 并行开发模式
