系统结构第6-9章

1、6.1 向量数据表示方式 6.2 向量处理机的结构 6.3 向量处理方式,第6章 向量处理机,具有向量数据表示和向量指令系统的处理机 向量处理机是解决数值计算问题的一种高性能计算机 向量处理机属大型或巨型机，也可以用微机加一台向量协处理器组成 向量处理机一般都采用流水线结构，通常有有多条并行工作的流水线 必须把要解决的问题转化为向量运算，才能发挥向量处理机的效率,6. 向量数据表示方式,6.1.1 从标量到向量 6.1.2 等间距向量表示法 6.1.3 带位移量的向量表示法 6.1.4 稀疏向量表示法,例6.1：一个简单的C语言程序如下：for (i = 10; i = 1010; i+) c

2、i = ai + bi+5 ; 在向量处理机上, 可以只用一条指令：C(10:1010)=A(10:1010) + B(15 :1015)一条向量指令可处理个或对操作数 在标量处理机上用10多条指令，其中有8条指令要循环1000次。 采用多寄存器结构的两地址指令编写程序 存储器采用字节编址方式，字长为32位,6.1.1 从标量到向量,三个参数表示一个等间距向量： 向量起始地址：A 向量长度：L 向量间距：f,6.1.2 等间距向量表示法,6.1.3 带位移量的向量表示法,用三个参数表示一个向量： 向量基地址：A 向量长度：L 向量位移量：f 向量有效长度：Lf 向量起始地址：Af 优点：每个向

3、量可以带有位移，能够通过控制向量实现可变增量。 能够表示稀疏向量。,带位移量的向量表示法,6.1.4 稀疏向量表示法,定义：0元素很多，非0元素很少的向量称为稀疏向量 采用压缩方法存储稀疏向量可以节省存储空间。 可以还原之后进行运算，也可以用压缩方法直接进行运算,6.2 向量处理机的结构,主要采用两种方法： 存储器存储器结构多个独立的存储器模块并行工作处理机结构简单 对存储系统的访问速度要求很高 寄存器寄存器结构运算通过向量寄存器进行需要大量高速寄存器 对存储系统访问速度的要求降低,1. 存储器存储器结构 向量处理机中有多个高速流水线运算部件， 存储器的访问速度是关键 采用多个存储体交叉和并行

4、访问来提高存 储器速度 例如：CRAY-1有64个存储体，每个处理机访问4个存储体 STAR-100采用32个存储体交叉，每个存储体并行读出8个64位数据 我国研制的YH-1向量计算机有37个存储体,操作数缓冲栈和写结果缓冲栈主要用于解决访问存储器冲突。虽然采用质数个存储体能消除访问存储器的冲突，但是，数据经过多次运算之后，在存储体中分布必然发生改变 主要优缺点： 硬件结构简单, 造价低；速度相对较低,操作数缓冲栈,写结果缓冲栈,主存储器,流水线 运算 部件,2. 寄存器-寄存器结构 把存储器-存储器结构中的缓冲栈改为向量 寄存器 运算部件需要的操作数从向量寄存器中读取， 运算的中间结果也写到

5、向量寄存器中。 向量寄存器与标量寄存器的主要差别是： 一个向量寄存器能够保存一个向量， 连续访问一个向量的各个分量。 需要有标量寄存器和地址寄存器等。,有三种处理方式： 横向处理方式，又称为水平处理方式，横向加工方式等。向量计算是按行的方式从左至右横向地进行。 纵向处理方式，又称为垂直处理方式，纵向加工方式等。向量计算是按列的方式自上而下纵向地进行。 纵横处理方式，又称为分组处理方式，纵横向加工方式等。横向处理和纵向处理相结合的方式。,6.3 向量处理方式,第7章 互连网络,7.1 互连网络的基本概念 7.2 互连网络的种类,7.1 互连网络的基本概念,7.1.1 互连网络的作用 7.1.2

6、互连网络的特性 7.1.3 互连网络的性能参数 7.1.4 互连网络的表示方法 7.1.5 互连函数,7.1.1 互连网络的作用,用来实现计算机系统内部多个处理机或多个功能部件之间的相互连接。 互连网络已成为并行处理系统的核心组成部分。 互连网络对整个计算机系统的性能价格比有着决定性的影响。 一个例子：具有本地存储器、私有高速缓存、共享存储器和共享外围设备的一般处理机系统的互连结构,磁盘,SM1,SM2,SMm,PMN,Cn,Pn,LM,C1,P1,LM,PCN,PION,磁带,打印机,终端,网络,(共享存储器),(共享I/O与外设),互连网络通常是用有向边或无向边连接有限个结点的组成。互连网

7、络的主要特性有： (1)网络规模：网络中结点的个数 (2)结点度：与结点相连接的边数称为结点度 进入结点的边数叫入度 从结点出来的边数则叫出度 (3)距离：两个结点之间相连的最少边数 (4)网络直径：网络中任意两个结点间距离的最大值。用结点间的连接边数表示,7.1.2 互连网络的特性,7.1.3 互连网络的性能参数,发送方的步骤如下： (1) 用户程序把要发送的数据拷贝到系统缓冲区。 (2) 缓冲区中的数据打包并发送到网络接口部件。 (3) 网络接口硬件开始发送消息。 数据包的接收步骤如下： (1) 把数据包从网络接口部件拷贝到系统缓冲区。 (2) 检查收到的数据包，如果正确，发回答信号。 (

8、3) 把接收到的数据拷贝到用户地址空间。 发送方接收到回答信号后释放系统缓冲区,互连网络的主要性能参数： (1)频带宽度(Bandwidth)：传输信息的最大速率 (2)传输时间(Transmission time)：等于消息长度除以频宽。 (3)飞行时间(Time of flight)：第一位信息到达接收方所花费的时间。 (4)传输时延(Transport latency)：等于飞行时间与传输时间之和。 (5)发送方开销(Sender overhead)：处理器把消息放到互连网络的时间。 (6)接收方开销(Receiver overhead)：处理器把消息从网络取出来的时间。,一个消息的总时

9、延可以用下面公式表示： 总时延发送方开销飞行时间 消息长度/频宽接收方开销,为了在输入结点与输出结点之间建立对应关系，互连网络有三种表示方法： (1)互连函数表示法： 如：f(xn-1x1x0) = x0 xn-2x1xn-1 (2)图形表示法 (3)输入输出对应表示法,互连网络,0,0,1,1,n-1,n-1,输入: 0 1 2 3 4 5 6 7输出: 1 0 3 2 5 4 7 6,7.1.4 互连网络的表示方法,7.2 互连网络的种类,7.2.1 静态互连网络 7.2.2 循环互连网络 7.2.3 多级互连网络 7.2.4 全排列互连网络 7.2.5 全交叉开关网络,静态互连网络：连接

10、通路是固定的，一般不能实现任意结点到结点之间的互连。 循环互连网络：通过多次重复使用同一个单级互连网络以实现任意结点到结点之间的互连 。 多级互连网络：将多套相同的单级互连网络连接起来，实现任意结点到结点之间的互连。 全排列互连网络：能够同时实现任意结点到结点之间的互连。 全交叉开关网络：能够同时实现任意结点到结点之间的互连，还能够实现广播和多播。,第8章 并行处理机,8.1 并行处理机模型 8.2 并行处理机结构,两种并行性概念： (1)同时性并行Simultaneity：两个或两个以上事件在同一时刻发生。 (2)并发性并行Concurrency：两个或两个以上事件在同一时间间隔内发生。 三

11、条技术途径： (1)资源重复：重复设置多个部件来提高速度。 (2)时间重叠：流水线 (3)资源共享：分时系统，分布式系统,8.1 并行处理机模型,1. 并行处理机的定义： 多个处理部件PU按照一定方式互连，在同一个控制部件CU控制下，对各自的数据完成同一条指令规定的操作。从CU看，指令是串行执行的，从PU看，数据是并行处理的。 并行处理机也称为阵列处理机，按照按照佛林分类法，它属于SIMD处理机。 2. 并行处理机的主要应用领域： 用于高速向量或矩阵运算。,3. 并行处理机的操作模型可用五元组来表示： M(N，C，I，M，R), 其中： N为PE个数。如IlliacIV有64个PE。 C为控制

12、部件CU执行的指令集，包括标量指令和程序控制指令。 I为所有PE并行执行的指令集，包括ALU、数据传送等操作 M为屏蔽操作集，将PE划分为允许操作和禁止操作两个子集 R是数据寻径集，互连网络中PE间通信所需要的各种模式,4. H.J.Siegel提出的并行处理机模型,8.2 并行处理机结构,8.2.1 并行处理机的基本结构 8.2.2 分布存储器并行处理机 8.2.3 共享存储器并行处理机 8.2.4 并行处理机的特点,8.2.1 并行处理机的基本结构,一台并行处理机由五个部分组成： 多个处理单元PE， 多个存储器模块M， 一个控制器CU， 一个互连网络ICN， 一台输入输出处理机IOP。 并

13、行处理机有两种典型结构： 分布存储器并行处理机， 共享存储器并行处理机。,8.2.2 分布存储器并行处理机,目前的大部分并行处理机属于基于分布式存储器模型。 分布式存储器并行处理机比较容易构成MPP(Massively Parallel Processor)，可以有几十万个处理部件PE。 CU是控制部件。对于标量指令，在CU中直接执行；对于向量指令，CU把它广播到各个PE中去执行。 在CU中通常有一个较大容量的存储器，用来存放程序和共享数据。,IOP是输入输出处理机，或称为主机。在IOP上安装操作系统，它除了负担输入输出工作外，还负责程序的编辑、编译和调试等工作。 IOP可以是一台通用计算机。

14、 分布式存储器并行处理机必须依靠并行算法来提高PE的利用率。因此，应用领域有限，可以认为是一种专用计算机。 数据在局部存储器中的分布是一个很关键的问题。 标量指令与向量指令可以并发执行。,分布式存储器并行处理机的结构框图,8.2.3 共享存储器并行处理机,共享多体并行存储器SM通过互连网络与各处理单元PE相连。 存储模块的数目等于或略大于处理单元的数目。为了实现无冲突访问，存储模块的个数为质数。 在存储模块之间合理分配数据，通过灵活、高速的互连网络，使存储器与处理单元之间的数据传送在大多数向量运算中都能以存储器的最高频率进行，而最少受存储器冲突的影响。,共享存储器模型的处理单元数目一般不多，几

15、个至几十个。 Burroughs Scientific Processor(BSP)采用了这种结构。16个PE通过一个1617的对准互连网络访问17个共享存储器模块。 存储器模块数与PE数互质可以实现无冲突并行访问存储器。 对互连网络的要求很高。,共享存储器并行处理机的结构框图,8.2.4 并行处理机的特点,并行处理机的主要特点如下： 1. 速度快，而且潜力大 2. 模块性好，生产和维护方便 3. 可靠性高，容易实现容错和重构 4. 效率低 与流水线处理机、向量处理机等比较。 依靠的是资源重复，而不是时间重叠，它的每个处理单元要担负多种处理功能，其效率要低一些。,第9章 多处理机,9.1 多处

16、理机结构 9.2 多处理机性能模型 9.3 多处理机的Cache一致性,多处理机定义： 两个或两个以上处理机(包括PU和CU)，通过高速互连网络连接起来，在统一的操作系统管理下，实现指令以上级（任务级、作业级）并行。 按照Flynn分类法，多处理机系统属于MIMD计算机 研究多处理机的目的：提前10年得到性能高100倍的高性能计算机系统。,9.1.1 多处理机分类 9.1.2 松散偶合多处理机 9.1.3 紧密偶合多处理机 9.1.4 多处理机系统的特点,9.1 多处理机结构,9.1.1 多处理机分类,多处理机系统由多个独立的处理机组成，每个处理机都能够独立执行自己的程序。 按照处理机之间的连

17、接程度：紧密偶合和松散偶合多处理机 按照是否共享主存储器：共享存储器和分布存储器多处理机 按照处理机类型：同构型和异构型多处理机 按照处理机的个数：大规模并行处理机MPP和对称多处理机SMP,按照PE与IOP之间互连方式： 对称型：每个IOP能够连接到所有PE上 非对称型：每个IOP只与一个PE连接。 冗余对称型：一个PE与多个IOP连接。 按照存储器的访问方式： 均均存储器，UMA模型 非均均存储器，NUMA模型 只有Cache，COMA模型 另外，多向量处理机，机群系统等也称为多处理机系统。,处理机之间的连接频带比较低 处理机之间互为外围设备进行连接。 通过并行口或串行口把多台计算机连接起

18、来。 多台计算机之间的连接需要有多个接口。 通过Ethernet网络接口连接多台计算机。 速度达10Mb、100Mb、1Gb，Mynet已经达到1.28Gb和2.56Gb。 当通信速度要求更高时，可以通过一个通道和仲裁开关CAS (Channel and Arbiter Switch)直接载存储器总线之间建立连接。,9.1.2 松散偶合多处理机,处理机之间共享主存储器，通过高速总线或高速开关连接。 每个CPU能够访问任意一个存储器模块 通过映象部件把全局逻辑地址变换成局部物理地址 通过互连网络寻找合适的路径，并分解访问存储器的冲突 多个输入输出处理机IOP也连接在互连网络上，输入输出设备与CP

19、U共享主存储器。 处理机个数不能太多，一般几个到几十个。,9.1.3 紧密偶合多处理机,1. 结构灵活 并行处理机：专用，PE数多，固定有限通信 多处理机： 通用，PE数少，高速灵活通信 2. 程序并行性 并行处理机的并行性存在于指令内部，识别比较容易。多处理机的并行性存在于指令外部，在多个任务之间，识别难度较大。,9.1.4 多处理机系统的特点,3. 并行任务派生 并行处理机把同种操作集中，由指令直接启动各PE同时工作。 多处理机用专门的指令来表示并发关系，一个任务执行时能够派生出与它并行的另一些任务 如果没有空闲处理机，任务进入排队器等待 4. 进程同步 并行处理机仅一个CU，自然是同步的

20、。 多处理机中，各处理机执行不同的指令，工作进度不会也不必保持相同。先做完的要停下等待。有数据相关和控制相关也要停下等待。,要采取同步措施来保持程序要求的正确顺序 5. 资源分配和进程调度 并行处理机的PE是固定的，用屏蔽来改变实际参加操作的PE数目。 多处理机执行并发任务，需用处理机的数目不固定，各处理机进出任务的时刻不相同，所需共享资源的品种、数量随时变化。 资源分配和进程调度问题，对整个系统的效率有很大的影响。,引起峰值性能下降的原因： (1)由于处理机之间通信而产生的延迟。 (2)一台处理机与其它处理机同步所需的开销。 (3)当没有足够多任务时，一台或多台处理机处于空闲状态。 (4)由

21、于一台或多台处理机执行无用的工作。 (5)系统控制和操作调度所需的开销。,9.2 多处理机性能模型,研究多处理机的目的： 单处理机的速度提高很快， 为什么还要研究多处理机？ 提前5年得到速度高10倍的机器。 或用1/10的价格获得一台高性能的机器。 在某些适合进行并行处理得应用领域，可以达到：提前10年得到速度高100倍的机器。 或用1/100的价格获得一台高性能的机器。,并行性在很大程度上依赖于R/C比值 其中：R: 程序执行时间，C: 通信开销 R/C小，并行度低。R/C大，并行性高。 把作业分解成较大的块，能得到较大的R/C，但所得到的并行性小 R/C是衡量任务粒度(Granularity)的尺度 粗粒度(Coarsegrain)并行：R/C大，通信开销小 细粒度(Finegrain)并行：R/C小，通信开销大 细粒度并行性是程序尽可能地分解成小任务，在极端情况下，一个小任务只完成一个操作,在并行处理机和多处理机系统中，采用局部Cache会引起Cache与共享存储器之