互连网络的寻径方式

多种不同的设计方案
　　■电路交换：预约资源（端口和缓冲区），预先建立固定交换结点链路，分组能够全速发送。
　　■存储转发分组交换：不预约资源，各个交换结点缓存整个分组。需要有缓存策略：
　　　　◆输入缓存、输出缓存、公共缓冲区
　　■虚拟直通寻径：当分组第一个单元不能移动时，分组的其余单元可以继续向第一个单元所在的结点传送。
　　■虫蚀寻径：当第一个单元不能移动时，通知源结点，源结点就停止传送，因此分组就像一条虫子一样停留在两个或者更多个交换结点中。

互连网络的寻径算法

源寻径和分布式寻径
　　■在源寻径中，源结点预先决定穿过互连网络的完整的路径，使用路径中每个结点的端口号的列表来表示。
　　■在分布式寻径算法中，每个交换结点自己决定把到达的分组发送到哪个输出端口。一般来说在各个交换结点都设立一个路径表，而分组的头部含有一个寻径字段说明分组的目的地址和选择路径的依据。
静态寻径算法和自适应寻径算法
　　■算法对所有到相同目的结点的分组都做出相同的决策，那么这样的寻径算法就称为静态的。
　　■算法在做路径选择时考虑了当前情况，该算法就是自适应的。

本章主要内容

并行计算机系统结构概述
并行计算机系统的设计问题
　　■并行计算机系统的互连网络
　　■并行计算机系统的性能问题
　　■并行计算机系统的软件问题
SIMD计算机简介
MIMD多处理机简介
MIMD多计算机简介

并行计算机系统的性能问题

硬件性能指标
　　■重要的性能指标是CPU和输入/输出的速度以及互连网络的性能。
　　■互连网络的性能有两个重要的指标：延时（Latency）和带宽（Bandwidth）。
　　　　◆延迟时间是指从CPU发送分组至接收到响应的时间间隔。
　　　　◆对分带宽、聚集带宽和平均带宽（按照CPU能力计算 ）。
软件性能指标
　　■最关键的性能指标是加速比（speedup）：一个程序在有n个处理器的计算机上运行和在只有一个处理器的计算机上运行相比快多少倍。

理想的加速比不可能达到的部分原因是几乎所有的程序都有串行部分。
　　■假定一个程序在单处理器计算机上运行需要T秒，其中一部分是串行代码，所占比例记为f，那么剩余的（1－f）就是可以并行的。
　　■后一部分代码运行在n个CPU上而且没有任何其它开销，那么在最理想的情况下，执行时间可以从（1－f）T减少到（1－f）T/n。
　　■串行部分加并行部分的整个执行时间就是fT＋（1－f）T/n 。
　　■加速比就是原来程序的执行时间除以新的程序的执行时间：

本章主要内容

并行计算机系统结构概述
并行计算机系统的设计问题
　　■并行计算机系统的互连网络
　　■并行计算机系统的性能问题
　　■并行计算机系统的软件问题
SIMD计算机简介
MIMD多处理机简介
MIMD多计算机简介

并行计算机软件的四种设计方法

第一种方法是为普通的串行语言增加特殊的函数库。这种方法的问题在于只是在很少的库函数中实现了并行性，而大量的程序代码仍然是串行的。

第二种方法是为编程语言增加包括通信和控制原语的库函数。程序员仍然使用传统的编程语言编程，但是程序员需要使用这些原语来创建和管理并行性。

第三种方法是为现有的编程语言增加一些特殊的结构，比如可以很容易地创建新的并行进程的能力，并行执行循环的能力和同时对一个向量的所有元素执行算术运算的能力。

第四种方法是发明一种全新的用于并行处理的语言。使用新语言的一个显而易见的优势是这样的语言肯定很适合于并行处理，但是缺点也同样明显，程序员必须学习一种新语言。

本章主要内容

并行计算机系统结构概述
并行计算机系统的设计问题
　　■并行计算机系统的互连网络
　　■并行计算机系统的性能问题
　　■并行计算机系统的软件问题
SIMD计算机简介
MIMD多处理机简介
MIMD多计算机简介

SIMD计算机

单指令流多数据流计算机用于解决使用向量和阵列这样比较规整的数据结构的复杂科学计算和工程计算问题。

只有一个控制单元，每次只能执行一条指令，但是这一条指令可以同时对多个数据进行操作。

SIMD计算机可以分为阵列处理机和向量处理机两大类。

阵列处理机

设计阵列处理机基本思想
　　■用一个单一的控制单元提供信号驱动多个处理单元同时运行，如下图所示。每个处理器单元都由CPU或者是功能增强的ALU和本地内存组成。由于所有的处理单元都是由一个控制单元驱动的，因此它们的执行是同步的。
各种阵列处理机的不同之处
　　■处理单元的结构：处理单元的结构可能很简单，也可能很复杂。
　　■处理单元如何连接：从原理上来说前面列出的拓扑结构都是可行的，网格是比较常用的结构。
　　■处理单元自治能力：每个处理单元都可以选择执行或不执行某条指令。
没有那个公司的产品在市场上取得较大的成功，从并行计算机系统体系结构来看，阵列处理机没有好的发展前景。

ILLIAC IV型阵列处理机

向量处理机
向量处理机在商业上取得了很大成功。Cray Research公司设计的系列计算机，从Cray-1到后来的C90和T90，在科学计算领域占据了数十年的统治地位。
从数学的概念上讲，标量是指单个量，而向量是指一组标量。例如，有一个数组A＝（a₁，a₂，a₃，…，a_n），其中括号内的每一个元素a_i就是一个标量。而A称为向量，它由一组标量组成。
向量处理方式：引入向量数据表示，需要向量指令处理。
　　标量处理：for（i＝0；i＜N；i＋＋）
　　　　　　　　　A[i]＝B[i]＋C[i]
　　向量处理：A＝B＋C

向量处理方法 　　■例子：D＝A×(B＋C) 其中A、B、C、D都是长度为N的向量。 　　■横向处理方法：逐个求向量D中N个分量 。 　　■纵向处理方法：先求B＋C各个分量得向量K，然后计算D＝A×K。 　　■纵横处理方法：分组处理，组内采用纵向处理，组间采用横向处理。 最简单的向量处理结构 向量处理和流水线结合 对语言结构和编译程序提出新的要求

本章主要内容

并行计算机系统结构概述
并行计算机系统的设计问题
　　■并行计算机系统的互连网络
　　■并行计算机系统的性能问题
　　■并行计算机系统的软件问题
SIMD计算机简介
MIMD多处理机简介
MIMD多计算机简介

共享内存的多处理机

具有多个CPU并且所有的CPU共享同一个映射到共享物理内存上的虚拟地址空间。多处理机系统有时也被称为共享内存系统（Shared Memory System）。

从软件的角度来说，多处理机系统很容易扩展。任何一个处理器都可以通过执行LOAD/STORE指令访问内存。两个处理器之间可以通过很简单的方式进行通信，只要一个处理器把数据写入内存而另一个处理器从内存中把数据读出就可以了。

多处理机系统也有磁盘、网络适配器和其它的输入/输出设备。如果在一个系统中，每个CPU都能平等地访问所有的内存模块和输入/输出设备，而且在操作系统看来这些CPU是可以互换的，那么这种系统就是对称多处理机系统SMP（Symmetric MultiProcessor）。

多处理机系统中只有一个操作系统，操作系统负责管理一系列的表。这种单一系统映像是多处理机系统区别于多计算机系统的主要特点。

UMA多处理机系统

UMA系统特点
　　■物理存储器被所有处理器均匀共享
　　■所有处理器访问任何存储字需相同的时间
　　■每台处理器可带私有高速缓存或私有内存
基于总线的UMA多处理机系统

NUMA多处理机系统

NUMA系统特点
　　■所有的CPU都看到一个单一的地址空间
　　■使用LOAD和STORE指令访问远程内存
　　■访问远程内存比访问本地内存慢
　　■NUMA系统中的处理器可使用高速缓存
NC-NUMA与CC-NUMA
　　■不使用Cache的NUMA系统被称为NC-NUMA多处理机系统，也就是说这种系统中不隐藏远程内存的访问时间。如果使用了Cache，那么系统就被称为CC-NUMA多处理机系统。

NC-NUMA多处理机系统

CC-NUMA多处理机系统

Cache一致性问题与Cache一致性协议

Cache一致性问题产生原因
　　■现代并行计算机中，处理器往往带有Cache。一个内存数据在整个系统内可能有多份拷贝。这就引发了Cache一致性问题。
Cache一致性协议
　　■由Cache、CPU和内存共同实现的防止多个Cache中出现相同数据的不同版本的规则集合就组成了Cache一致性协议。
Cache一致性协议通常可以分为两类
　　■监听总线的协议
　　■基于目录的协议

监听总线的协议
　　■在监听总线协议中，所有的处理器都监听总线，当某个处理器修改了私有Cache中的数据后，它在总线上广播无效信息或更新后的数据，以使其它副本无效或得到更新。
　　■监听总线协议适用于互连网络可以实现广播功能的并行系统。
基于目录的协议
　　■基本思想：当处理机数目较多时，一般不用总线结构，而采用多级交换网络，而多级交换网络实现广播功能代价很大。那么能不能只发送给存放该副本的Cache?
　　■基于目录的协议是用一个目录来记录系统中哪些处理机的Cache中有指定存储块的副本。当一台处理机希望写某个共享块时，通过目录向有该块的副本的那些处理机“点对点”的发无效信号，使所有其它的副本无效。

基于监听总线的两种Cache一致性协议

写直达Cache一致性协议
　　■对Cache行中的数据进行写操作的同时，将对应的存储器中的内容也进行修改，任意时刻都保持存储器中的数据是最新的。
写回Cache一致性协议
　　■写操作不直接写入内存。相反，当Cache行被修改后，Cache中的某一位被设置以表示该Cache行中的数据是正确的而内存中的数据是过时的。当然最终该行将会被写回内存，但是可能是在多次写操作之后了。

写直达Cache一致性协议

监听型Cache按此协议进行读写操作时的四种情况

写直达Cache一致性基本协议存在多种变化
　　■远程写命中采用更新策略（Update Strategy）还是无效策略（Invalidate Strategy）
　　■当Cache写缺失时是否把相应的字调入Cache，这就是是否采用写分配策略（Write-allocate Policy）。

MESI协议：它是用协议中用到的四种状态首字母来命名的。这个协议中每个Cache项都处于下面四种状态之一：
　　■无效（Invalid）：该Cache项包含的数据无效。
　　■共享（Shared）：多个Cache项中都有这行数据，内存中的数据是最新的。
　　■独占（Exclusive）：没有其它的Cache项包括这行数据，内存中的数据是最新的。
　　■修改（Modified）：该项的数据是有效的，但内存中的数据是无效的，而且在其它Cache项中没有该项数据的拷贝。

MESI协议状态转换规则

针对总线不同活动，进行不同的响应

处理器读请求：有效态(M/S/E)行读命中，状态不变；读丢失时，分配新行并读入数据，状态从I变至S或E。
处理器写请求：有效态(M/S/E)行写命中，M/E变为M，S先成为“独有”(其它Cache共享拷贝无效)后再进入M态；写丢失时，不按写分配法写存后不读入，按写分配法先读入此行(I)修改后变为M态,两种方法均有先“独有”(其它Cache共享拷贝无效) 的处理过程。
Cache读监听命中：S态不变，E态变为S态，M态抢占总线写回主存后，变为S态。
Cache写监听命中：有效态(S/E)行变为I态，M态抢占总线写回主存后，变为I态。

MESI协议工作过程

本章主要内容

并行计算机系统结构概述
并行计算机系统的设计问题
　　■并行计算机系统的互连网络
　　■并行计算机系统的性能问题
　　■并行计算机系统的软件问题
SIMD计算机简介
MIMD多处理机简介
MIMD多计算机简介

基于消息传递的多计算机系统

在多计算机体系结构中，每个CPU都有自己的私有内存，私有内存只能供自己使用而其它的CPU则不能访问。每个CPU都有自己独立的物理地址空间。

多计算机系统具有良好的可扩展性，与多处理机系统相比可以达到更大的规模。

多计算机系统中没有硬件实现的共享内存这一特点也在很大程度上影响了其软件体系结构。多计算机系统中的CPU不能通过读写共享内存进行通信，在系统中通信是通过使用互连网络传递消息来实现的。多计算机系统的编程比多处理机系统的编程要复杂的多。

多计算机系统中的每个结点都由一个或者多个CPU、RAM、磁盘以及其它的输入/输出设备和通信处理器组成。而且每个结点上都有操作系统，至少是操作系统核心部分。

通用多计算机体系结构
　　■每个结点都由一个或者多个CPU、RAM、磁盘以及其它的输入/输出设备和通信处理器组成。
　　■通信处理器通过互连网络相互连接起来。可以使用多种不同的拓扑结构，交换策略和寻径算法。

两种不同的多计算机系统

MPP系统
　　■MPP系统是由成百上千台处理机组成的大规模并行计算机系统。
　　■过去主要用于科学计算、工程模拟等以计算为主的场合，目前也广泛应用于商业和网络应用中。
　　■开发困难，价格高，市场有限。是国家综合实力的象征。

系统特点
　　■MPP系统一般使用标准的商用CPU作为它们的处理器。
　　■MPP系统使用了高性能的私用的互连网络，可以在低延时和高带宽的条件下传递消息。
　　■MPP系统具有强大的输入/输出能力。
　　■MPP系统能够进行特殊的容错处理。

大规模并行处理机MPP

两种不同的多计算机系统

COW系统
　　■COW系统是由大量的PC机或者工作站通过商用网络连接在一起构成的。
　　■COW可以完全使用可以买到的商用组件装配而成，这些商用组件都是大规模生产的产品，因此能够获得较高的性价比。
　　■占主导地位的COW主要有两种：集中式的和分散式的。
COW与MPP的区别（体系结构方面）
　　■第一，COW的结点是更完整的计算机，计算机可以是同构的也可以是异构的。结点都有自己的磁盘，驻留有自己的完成的操作系统；并且，一般都有一定的自主性。结点计算机脱离COW照样能运行。而MPP系统结点一般没有磁盘，只驻留操作系统内核。
　　■第二，MPP使用制造厂商专有（或者说是有专利权）的高速通信网络；COW一般采用公开销售的标准高速局域网或系统域网，网络通常是与结点计算机的I/O总线相连（松散耦合），而MPP的网络接口是连到处理结点的存储总线上（紧耦合） 。

工作站机群COW

COW的体系结构