Download presentation
Presentation is loading. Please wait.
1
计算机组织与体系结构 第十一章 并行体系结构 裴 颂 文 上海理工大学 2011年春季
2
第十一章 并行体系结构 11.1 体系结构中的并行性 11.2 超长指令字处理机 11.3 多线程与超线程处理机 11.4 向量处理机
11.5 对称多处理机 11.6 机群系统
3
11.1 体系结构中的并行性 并行性的概念 提高并行性的技术途径 单处理机系统中并行性的发展 多处理机系统中并行性的发展 并行处理机的体系结构类型
4
11.1 体系结构中的并行性 所谓并行性，是指计算机系统具有可以同时进行运算或操作的特性，它包括同时性与并发性两种含义。
11.1 体系结构中的并行性 所谓并行性，是指计算机系统具有可以同时进行运算或操作的特性，它包括同时性与并发性两种含义。 同时性--两个或两个以上的事件在同一时刻发生。 并发性--两个或两个以上的事件在同一时间间隔发生。 并行性等级--从处理数据的角度分 计算机系统中的并行性有不同的等级。 从处理数据的角度看，并行性等级从低到高可分为： 字串位串 同时只对一个字的一位进行处理。这是最基本的串行处理方式，不存在并行性。 字串位并 同时对一个字的全部位进行处理，不同字之间是串行的。这里已开始出现并行性。 字并位串 同时对许多字的同一位进行处理。这种方式有较高的并行性。 全并行 同时对许多字的全部位进行处理。这是最高一级的并行。
5
11.1 体系结构中的并行性 并行性等级--从执行程序的角度分 指令内部并行 一条指令执行时各微操作之间的并行。 指令级并行
11.1 体系结构中的并行性 并行性等级--从执行程序的角度分 指令内部并行 一条指令执行时各微操作之间的并行。 指令级并行 并行执行两条或多条指令。 任务级或过程级并行 并行执行两个以上过程或任务（程序段）。 作业或程序级并行 并行执行两个以上作业或程序。
6
11.1 体系结构中的并行性 提高并行性的技术途径： 时间重叠 即时间并行
11.1 体系结构中的并行性 提高并行性的技术途径： 时间重叠 即时间并行 多个处理过程在时间上相互错开，轮流重叠地使用同一套硬件设备的各个部分 资源重复 即空间并行 通过重复设置硬件资源，大幅度提高计算机系统的性能 时间重叠+资源重复---主流技术 资源共享 用软件方法实现多个任务按一定时间顺序轮流使用同一套硬件设备
7
11.1 体系结构中的并行性 单处理机系统中并行性的发展 在发展高性能单处理机过程中，起着主导作用的是时间并行（流水线）技术 。
单处理机系统中并行性的发展 在发展高性能单处理机过程中，起着主导作用的是时间并行（流水线）技术 。 空间并行技术的运用也已经十分普遍 资源共享的概念即所谓虚拟机的概念 单处理机并行性发展的代表作有: 奔腾系列机 安腾系列机
8
11.1 体系结构中的并行性 多处理机系统中并行性的发展
多处理机系统中并行性的发展 多处理机系统也遵循时间重叠、资源重复、资源共享原理，向不同体系结构的多处理机方向发展。 耦合度 反映多处理机系统各机器之间物理连接的紧密程度与交互作用能力的强弱 多处理机系统，分为： 紧耦合系统（又称直接耦合系统） 通过总线或高速开关实现互连，共享主存。 处理机之间物理连接具有相对较高的信息传输率 松耦合系统（又称间接耦合系统） 通过通道或通信线路互连，共享外存设备（磁带、磁盘）。 处理机之间的作用是在文件或数据集一级上进行。
9
11.1 体系结构中的并行性 技术路线 异构型多处理机系统 同构型多处理机系统 发展状况 20世纪70年代以来，各类并行计算机系统问世
许多主要功能交由专用处理机完成 同构型多处理机系统 为了使并行处理的任务能在处理机之间随机地进行调度，就必须使各处理机具有同等的功能 发展状况 20世纪70年代以来，各类并行计算机系统问世 20世纪80年代，我国研制了向量处理机YH-1/2和757
10
11.1 体系结构中的并行性 天河1号 国防科大 Xeon E Cluster ATI RADEON
11
天河1号 2009年居TOP500世界第五位 峰值速度 4700万亿次
“天河一号”峰值运算速度为4700万亿次。做个换算对比，“天河一号”运算1小时，就相当于全国13亿人同时计算340年以上的时间。“天河一号”运算1天，就相当于1台双核的高档桌面电脑运算620年以上的时间。563．1万亿次的Linpack实测性能 。 存储容量 2000万亿字节 “天河一号”存储容量为2PB，也就是2千万亿个字节。做个换算对比，1个汉字平均为2个字节，“天河一号”即可在线存储1000万亿个汉字，相当于存储100万字的书籍10亿册。 24小时功耗 10万千瓦时（10万度电/天：低功耗） “天河一号”满负荷运行的总功耗是4.04兆瓦，也就是每小时耗电4040千瓦时，24小时满负荷工作耗电接近10万千瓦时。这个数字令人惊叹，但实际上“天河一号”在超级计算机当中是一台相对节能的、绿色的超级计算机。经过测算，它的能效值仅低于目前能效排名世界第一的IBM蓝色基因系统。 总重量 160吨 “天河一号”由140个机柜组成，占地约700平方米，总重量约160吨。大家站在“天河一号”前，会觉得它气势宏伟、震撼人心。但实际上，“天河一号”在世界上已有的千万亿次超级计算机中（多数是近千平方米的占地），算是一个身材苗条的小个子。
12
天河1号
13
11.1 体系结构中的并行性 并行处理机的体系结构类型 指令流和数据流的不同组织方式：（Flynn分类法）
并行处理机的体系结构类型 指令流和数据流的不同组织方式：（Flynn分类法） 单指令流单数据流（SISD) ，其代表机型是单处理机。 单指令流多数据流（SIMD) ，其代表机型是向量处理机。 多指令流单数据流（MISD) ，这种结构从来没有实现过。 多指令流多数据流（MIMD) ，其代表机型是多处理机和机群系统。
14
11.2 超长指令字处理机 VLIW (very long instruction word）超长指令字
由编译程序在编译时找出指令间潜在的并行性，进行适当调度安排，把多个能并行执行的操作组合在一起，成为一条具有多个操作段的超长指令。 用一条指令实现多个操作的并行执行，减少对存储器的访问。并行操作主要在流水的执行阶段进行的。
15
11.2 超长指令字处理机 VLIW处理机的特点 1、超长指令字的生成由编译器来完成的，将串行的操作序列合并为可并行执行的指令序列，以最大限度实现操作并行性。 2、单一的控制流，只有一个控制器，每个时钟周期启动一条长指令。 3、超长指令字被分成多个控制字段，每个字段直接独立地控制每个功能部件。 4、含有大量的数据通路和功能部件。由于编译时已解决可能出现的数据相关和资源冲突，故控制硬件比较简单。
16
11.2 超长指令字处理机 VLIW处理机的结构模型
17
11.2 超长指令字处理机 【例1】 假设要执行以下赋值语句： C=A+B K=I+J L=M-K Q=C×K
18
11.2 超长指令字处理机 如果在VLIW机器中，采用表调度的编译方式，可以将串行的13条指令序列压缩为6条长字指令，仅需6个周期就能完成同样的操作。 见p326表11.3
19
11.2 超长指令字处理机 典型处理机结构
20
11.3 多线程与超线程处理机 指令级并行与线程级并行 硬件多线程技术是提高处理机并行度的有效手段。
11.3 多线程与超线程处理机 指令级并行与线程级并行 硬件多线程技术是提高处理机并行度的有效手段。 2002年，英特尔公司推出的采用超线程(Hype Threading)技术的Pentium 4处理机，就是将同时线程技术的具体实现。 同时多线程SMT技术是加州大学-圣地亚哥分校UCSD计算机系教授Dean Tellusen教授最先提出的。 提高处理机性能的传统方法： 1、提高处理机的时钟频率，增大Cache容量。 2、超标量和超长指令字的方式，设置多条并行指令的指令流水线，实现指令级并行(ILP)。 3、提出新的线程级并行方法(TLP)。
21
11.3 多线程与超线程处理机 指令级并行与线程级并行
11.3 多线程与超线程处理机 指令级并行与线程级并行 2002年秋，英特尔公司推出一款采用超线程（Hyper Threading, HT）技术的Pentium 4处理机 原有的单个物理内核经过简单扩展后被模拟成两个逻辑内核 垂直浪费 如：资源冲突会导致不能继续执行新指令 水平浪费 如：指令相关导致多条流水线中部分流水线被闲置
22
11.3 多线程与超线程处理机 超线程处理机结构 超线程技术是同时多线程技术在Intel处理机中的具体实现。
11.3 多线程与超线程处理机 超线程处理机结构 超线程技术是同时多线程技术在Intel处理机中的具体实现。 每条指令需要经过10个功能段组成的流水线。 为了支持两个硬件线程同时运行，让每级流水线中的资源通过以下三种方式之一复用于两个线程： 复制、分区或共享。 支持超线程技术的NetBurst微体系结构的流水线结构
23
11.3 多线程与超线程处理机 超线程处理机结构 代价：作业调度策略、取值和发射策略、寄存器回收机制、存储系统层次设计将变得非常复杂。
11.3 多线程与超线程处理机 超线程处理机结构 统计表明：原来单线程的NetBurst的流水线在执行典型指令序列时仅仅利用了35%的资源。 复制：为处理机多个线程（2个）设置独立的部件。包括处理机状态、指令指针寄存器、寄存器冲命名部件和TLB表等。 分区：将用于单线程的独立资源分割为两部分，分别供两个线程使用。主要有各种缓冲区和队列，如重排缓冲区、存/取数缓冲区等。 共享：处理机在执行指令的过程中根据使用资源的需要在两个线程之间动态分享资源。如乱序执行部件和Cache。 代价：作业调度策略、取值和发射策略、寄存器回收机制、存储系统层次设计将变得非常复杂。
24
11.4 向量处理机 向量处理的基本概念 标量是指单个量，而向量是指一组标量 【例2】Y=a*X+Y其中a为标量，X和Y为向量。
11.4 向量处理机 向量处理的基本概念 标量是指单个量，而向量是指一组标量 【例2】Y=a*X+Y其中a为标量，X和Y为向量。 用标量处理机来计算。 用向量处理机来计算。
25
11.4 向量处理机 对比两段程序，发现： 向量处理机只需执行6条指令，而标量处理机共需要执行2+9×64=578条指令。
11.4 向量处理机 对比两段程序，发现： 向量处理机只需执行6条指令，而标量处理机共需要执行2+9×64=578条指令。 可以看出，一条向量指令可以处理N个或N对操作数。 向量处理 把N个互相独立的数叫做向量，对这样一组数的运算叫做向量处理 向量指令的处理效率要比标量指令的处理效率高得多
26
11.4 向量处理机 【例4】 计算表达式如下： 【例4】解答 解 ① 使用FORTRAN语言所写的DO语句循环部分为：
11.4 向量处理机 【例4】 计算表达式如下： Ci=ai+5 + bi i=10,11,12, …,1000 ① 用高级语言写出此表达式的循环部分； ② 用一条向量加法指令描述此表达式。 【例4】解答 解 ① 使用FORTRAN语言所写的DO语句循环部分为： DO 40 I= 40 C (I) =A (I+5) +B (I) ② 这种DO语句，在具有向量数据表示的机器中可用如下一条向量加法指令来实现，即 C (10∶1000) =A(10+5:1000+5)+B(10:1000)
27
11.4 向量处理机 向量的运算 向量的运算可以采用3种不同的处理方法： 1. 横向处理方法
11.4 向量处理机 向量的运算 向量的运算可以采用3种不同的处理方法： 1. 横向处理方法 横向处理方法中，向量计算是按行的方式从左至右横向进行 横向处理方法不适合于向量流水处理 2. 纵向处理方法 在纵向处理方法中，向量计算是按列的方式自上而下纵向地进行 可获得较高的吞吐率，适合于在向量处理机中应用 3. 纵横处理方法 又称为分组处理方法 组内采用纵向处理，组间采用横向处理 纵横处理方法适合于寄存器-寄存器工作方式的向量处理机。 由于向量寄存器的长度有限（如CRAY-1的长度为64) ，当向量长度N超过向量寄存器可表示的最大限度n时，就不得不分组加以处理。
28
11.4 向量处理机 向量处理机的结构 向量处理机原理框图 基本思想是把两个向量的对应分量进行计算，产生一个结果向量
29
11.4 向量处理机 向量计算C=A+B的时空图 假定一个存取周期为两个CUPU时钟周期，加法执行过程由4个流水段组成，向量ABC各有8个元素。 在时钟周期6时有6个存储模块同时工作。此时运算器和存储器的工作衔接得非常好，在整个计算进行过程中没有任何冲突发生。 之所以如此，是特意将向量各元素按上述方式存放在各存储模块中
30
11.4 向量处理机 Cray-1系统 寄存器-寄存器型向量处理机 然而实际情况并非与图11.12所示理想化的流水运行一样 读写冲突而断流
11.4 向量处理机 寄存器-寄存器型向量处理机 然而实际情况并非与图11.12所示理想化的流水运行一样 读写冲突而断流 有效方法是：由一级或多级中间存储器形成一个层次结构的存储器系统 Cray-1系统 CRAY-1是一台典型的寄存器-寄存器结构的向量处理机，其运算速度达亿次/秒以上
31
11.4 向量处理机 多功能部件的并行操作 在向量处理机中，为了加快向量操作，通常都采用独立的多个功能部件 共4组12个功能部件。
11.4 向量处理机 多功能部件的并行操作 在向量处理机中，为了加快向量操作，通常都采用独立的多个功能部件 共4组12个功能部件。 上述12个功能部件都是独立的，它们可并行工作，只要满足一定的约束条件： ①不存在向量寄存器使用冲突； ②不存在功能部件使用冲突。 每个功能部件的左边数字表示该部件的流水线延迟周期。
32
11.5 对称多处理机 多处理机系统的分类 多处理机系统由多个独立的处理机组成，每个处理机能够独立执行自己的程序
11.5 对称多处理机 多处理机系统的分类 多处理机系统由多个独立的处理机组成，每个处理机能够独立执行自己的程序 并行向量处理机(PVP) ：由几台巨型向量处理机采用共享存储器的方式互连而成。 对称多处理机(SMP) ：由一组处理机和一组存储器模块经过互连网络连接而成。紧耦合系统。 分布共享存储器多处理机(DSM) ：共享存储器分布在各台处理机中，每台处理机都带有自己的本地存储器，组成一个处理机-存储器单元。这些存储器采用统一编址。紧耦合系统。 大规模并行处理机(MPP) ：每个计算机模块称为一个结点。松耦合系统。
33
11.5 对称多处理机
34
11.5 对称多处理机 SMP的基本概念 SMP定义为具有如下特征的独立计算机系统： (1)有两个以上功能相似的处理机。
(2)这些处理机共享同一主存和I/O设施，以总线或其他内部连接机制互连在一起；这样，存储器存取时间对每个处理机都是大致相同的。 (3)所有处理机共享对I/O设备的访问，或通过同一通道，或通过提供到同一设备路径的不同通道。 (4)所有处理机能完成同样的功能。 (5)系统被一个集中式操作系统（OS）控制。
35
11.5 对称多处理机 SMP的结构和实例 为便利来自I/O处理器的DMA传送，应提供如下特征
(1) 寻址：区别总线上各模块，确定数据的源和目标。 (2) 仲裁：任何I/O模块都能临时具备主控器的功能。 (3) 分时共享：保证分时共享总线 一般来说，工作站和个人机SMP都有两级Cache 。现在，某些处理机还使用了L3 Cache
36
11.5 对称多处理机 多处理机操作系统 一个SMP操作系统管理多个处理机和其他计算机资源，而使用户感觉到单一操作系统控制着系统资源。呈现为一个单处理机多道程序设计系统。
37
11.5 对称多处理机 多道程序设计的关键问题 同时并发进程管理 OS例程必须是可重入的，要避免死锁或无效操作
调度 任何处理机都可完成调度，因此必须避免冲突 同步 由于有多个活动进程可能访问共享地址空间，或共享I/O资源，因此必须提供有效的同步 存储管理 协调不同处理机上的分页机制，保证共享页发生页替换时的一致性。 可靠性和容错 面对处理机故障，操作系统应提供优秀的降级使用。
38
11.5 对称多处理机 多处理机的Cache一致性 在单处理机系统中，Cache一致性问题只存在于Cache与主存之间
产生内容不一致的原因： ① 可写数据的共享：同一副本的不一致 ② I/O活动：I/O处理机直接接在系统总线上 ③ 进程迁移：尚未执行完的进程调度到另一个空闲的处理机中去执行 解决办法：大体有两类 软件方法：编译时“预防” 硬件方法
39
11.6 机群系统（集群系统） 机群（集群）系统的基本概念 1.机群系统的定义 2.机群和MPP差别
机群系统 (Cluster）是并行或分布计算机系统的一种类型，它是由一组完整的计算机通过高性能的网络或局域网互连而成的系统，它作为一个统一的计算资源一起工作，并能产生一台机器的印象 2.机群和MPP差别 MPP的结点上采用的处理机往往比较简单，结点之间用频带较宽的专用网络互连 机群的结点则是一台完整的计算机，结点之间采用的一般是商品化的网络互连
40
11.6 机群系统 机群系统的特点 机群系统的优点： 机群也有不足之处： 现在很多机群采用SMP作为结点 使用方便
可靠性好，软硬件冗余，各结点有自己的操作系统 可缩放性好 机群也有不足之处： 维护工作量和费用较高 SMP管理员要维护的只是一个计算机系统 现在很多机群采用SMP作为结点
41
11.6 机群系统 机群系统的体系结构 依据是系统中的计算机是否共享对同一磁盘的存取
无共享（shared-nothing）配置，采用局域网连接 共享磁盘（shared-disk）配置，共享磁盘一般使用RAID
42
11.6 机群系统 各计算机都安装有中间件 (middleware）和软件工具层 中间件的系统映像服务
① 单一入口点 用户登录到机群上而不是登录到个别计算机上。 ② 单一文件层次 用户看到的是同一根目录下的单一文件目录层次体系。 ③ 单一控制点 一台默认的工作站用于整个机群的管理和控制。 ④ 单一虚拟网络 实际的机群配置可能由多个互连的网络组成，担任一结点都能存取机群中任何其他结点。因此有单一虚拟网络的操作。 ⑤ 单一存储空间 分布式共享存储器允许程序共享变量。 ⑥ 单一作业管理系统 在机群作业调度程序管理下，用户提交作业无须指定执行此作业的宿主计算机。 ⑦ 单一用户接口 一个公共图形接口支持所有用户，不管用户由哪台工作站进入机群。
43
11.6 机群系统 中间件保证机群系统的可用性 ① 单一I/O空间 任一结点都能远程访问任何I/O外设或磁盘设备，而无须知道它们的物理位置。
② 单一进程空间 使用一致的进程证实方案，任何结点上的进程都能在远程结点上生成一进程，并与之通信。 ③ 故障检查 该功能周期性地保存进程状态和中间计算结果，以便在故障修复后重新运算。 ④ 进程迁移 该功能可使负载平衡。中间件机构需要识别机群系统不同成员上所出现的业务，并可将业务由一个成员移植到另一个成员上。
44
11.6 机群系统 IBM SP2系统 1997年战胜卡斯伯洛夫的“深蓝”，就是一个采用30个RS/6000工作站结点的IBM SP2机群。
SP2机群是异步的MIMD SP2的结点通过网络接口开关（NIC）接到HPS, IBM把这种NIC叫做开关适配器
45
11.6 机群系统 超级刀片系统 深圳星盈科技公司研发的实时协作式超级刀片系统是最新一代的通用超级计算机系统设计
1. 超级刀片机群在系统和应用方面的特点 (1) 革命性的设计理念 (2) 崭新的系统架构,商业组件 (3) 高速运算和海量存储 (4) 安全性与可靠性 (5) 实时协作式应用和研发网格的信息平台
46
11.6 机群系统 2. 刀片的概念与技术规格 以通用的运算处理架构技术为基础，可以支持Intel Xeon EM64T处理机。
每个刀片带有一个独立的管理控制模块 刀片的技术规格如下： 处理机: 支持2个Intel Xeon EM64T处理机 存储器: 支持8GB内存 硬盘数量: 支持2个硬盘，最大支持800GB Interconnect节点互连: InfiniBand 2X 10Gb接口 3. 可用的系统软件和开发工具 该系统的每个节点安装经过定制优化的RedHat LinuxAS 3.1操作系统 GNU编译器和调试器 在Linux和Unix上广泛使用，包括C/C++、Fortran 77, 提供最好的程序兼容性。
47
11.6 MPP系统 (补充) 6.1 互连网络 在拓扑上，互连网络为输入和输出两组结点之间提供一组互连或映象（mapping）。
6.1 互连网络 互连网络是将集中式系统或分布式系统中的结点连接起来所构成的网络，这些结点可能是处理器、存储模块或者其它设备，它们通过互连网络进行信息交换。 在拓扑上，互连网络为输入和输出两组结点之间提供一组互连或映象（mapping）。
48
11.6 MPP系统 (补充) 互连网络的性能参数 互连网络的拓扑可以采用静态或动态的结构。静态网络由点和点直接相连而成，这种连接方式在程序执行过程中不会改变。 动态网络是用开关通道实现的，它可动态地改变结构，使其与用户程序中通信要求匹配。 静态网络常用来实现一个系统中子系统或计算结点之间的固定连接。动态网络常用于集中式共享存储器多处理系统中。
49
11.6 MPP系统 (补充) 定义几个常用于估算网络复杂性、通信效率和价格的参数。 网络可用图来表示。这种图由用有向边或无向边连接的有限个结点构成。其结点数称为网络规模(network size)。 结点度 与结点相连接的边的数目称为结点度(node degree)。这里的边表示链路或通道。链路或通道是指网络中连接两个结点并传送数字信号的通路。在单向通道的情况下，进入结点的通道数叫做入度(in degree)，而从结点出来的通道数则称为出度(out degree),结点度是这两者之和。结点度应尽可能地小并保持恒定。
50
11.6 MPP系统 (补充) 网络直径 网络中任意两个结点间最短路径长度的最大值称为网络直径。网络直径应当尽可能地小。 等分宽度 在将某一网络切成相等两半的各种切法中，沿切口的最小通道边数称为通道等分宽度b (channel bisection width)。 结点间的线长(或通道长度)。它会影响信号的延迟、时钟扭斜和对功率的需要。 对于一个网络，如果从其中的任何一个结点看，拓扑结构都是一样的话，则称此网络为对称网络。对称网络较易实现，编制程序也较容易。
51
11.6 MPP系统 (补充) 路由（routing） 在网络通信中对路径的选择与指定。通常见到的处理单元之间的数据路由功能有移数、循环、置换(一对一)、广播(一对全体)、选播(多对多)、个人通信(一对多)、混洗、交换等。 为了反映不同互连网络的连接特性，每一种互连网络可用一组互连函数来定义。如果把互连网络的N个入端和N个出端各自用整数0，1，…，N-1代表，则互连函数表示互连的出端号和入端号的一一对应关系。 令互连函数为f,则它的作用是：对于所有的0≤j≤N-1, 同时存在入端j连至出端f(j)的对应关系
52
11.6 MPP系统 (补充) 下面介绍几种数据路由功能： 1.循环(rotation) 若把互连函数f(x)表示为：
(x0,x1,x2,……,xj) 则代表对应关系为： f(x0)=x1,f(x1)=x2,……,f(xj)=x0 j+1称为该循环的周期。
53
11.6 MPP系统 (补充) 2.置换（permutation）
指对象的重新排序。对于n个对象来说，有n!种置换。n个对象可照此重新排序，全部的置换形成一个与复合运算有关的置换集合。例如，置换π=(a,b,c)(d,e)表示了置换映射： f(a)=b,f(b)=c,f(c)=a,f(d)=e和f(e)=d。 这里循环(a,b,c)周期为3，循环(d,e)周期为2。可以用交叉开关来实现置换，也可以用一次或多次通过多级网络来实现某些置换，还可用移数或广播操作实现置换。 2.置换（permutation）
54
11.6 MPP系统 (补充) 根据最低位C0路由 根据中间位C1路由 根据最高位C2路由
55
11.6 MPP系统 (补充) 5.广播和选播 广播是一种一对全体的映射，选播是一个子集到另一子集(多对多)的映射。消息传递型多处理机一般有广播信息机构，广播常常作为多处理机中的全局操作来处理。 6．消息传递机制 消息由任意长度固定的包构成。 存储转发 每个结点有一个包缓冲区，包先进入缓冲区，当所需要的输出通道和接收结点的包缓冲区可用时，就将它传输给下一结点。
56
11.6 MPP系统 (补充) (1)功能特性——即网络如何支持路由、中断处理、同步、请求／消息组合和一致性。
通过上面的讨论，我们可概括出影响互连网络性能的因素为： (1)功能特性——即网络如何支持路由、中断处理、同步、请求／消息组合和一致性。 (2)网络时延——即单位消息通过网络传送时最坏情况下的时间延迟。 (3)带宽——即通过网络的最大数据传输率，用M字节／秒表示。 (4)硬件复杂性——即诸如导线、开关、连接器、仲裁和接口逻辑等的造价。 (5)可缩放性——即在增加机器资源使性能可缩放的情况下，网络具备模块化可缩放的能力。
57
11.6 MPP系统 (补充) 静态连接网络 静态网络使用直接链路，它一旦构成后就固定不变。这种网络比较适合于构造通信模式可预测或可用静态连接实现的计算机系统。 线性阵列(linear array) 这是一种一维的线性网络，其中N个结点用N-1个链路连成一行。内部结点度为2，端结点度为1。直径为N-1，N较大时，直径就比较长。等分宽度b=1。线性阵列是连接最简单的拓扑结构。这种结构不对称，当N很大时，通信效率很低。
58
11.6 MPP系统 (补充) 在N很小的情况下，实现线性阵列是相当经济和合理的。由于直径随N线性增大，因此当N比较大时，就不应使用这种方案了。 线性阵列与总线的区别是很大的，总线是通过切换与其连接的许多结点来实现时分特性的，而线性阵列则允许不同的源结点和目的结点对并行地使用其不同的部分(通道)。
59
11.6 MPP系统 (补充) (a)线性阵列 (b)环
60
11.6 MPP系统 (补充) 星形是一种2层树，结点度较高，为d=N-1。直径较小，是一常数2。
树形和星形(tree and star) 一棵5层31个结点的二叉树如图。一般说来，一棵k层完全平衡的二叉树有N=2k-1个结点。最大结点度是3，直径是2(k-1)。由于结点度是常数，因此二叉树是一种可扩展的结构，但其直径较长。 星形是一种2层树，结点度较高，为d=N-1。直径较小，是一常数2。
61
11.6 MPP系统 (补充) 使用传统二叉树的主要问题之一就是通向根结点的瓶颈问题，这是因为根部的交通最忙。胖树的提出使该问题得到了缓解。
胖树形 1985年Leiserson提出将计算机科学中所用的一般树结构修改为胖树形(fat tree)。胖树的通道宽度从叶结点往根结点上行方向逐渐增宽，它更象真实的树，愈靠近树根的枝叉愈粗。 使用传统二叉树的主要问题之一就是通向根结点的瓶颈问题，这是因为根部的交通最忙。胖树的提出使该问题得到了缓解。
62
11.6 MPP系统 (补充) 二叉胖树
63
11.6 MPP系统 (补充) 网格形和环网形 N=nk 个结点的k维网络的内部结点度为2k ，网络直径为k(n-1)。纯网络形不是对称的。边结点和角结点的结点度分别为3或2。 二维网格两个结点之间的路径数为K=(X+Y)!/(X!Y!) ，XY分别为两结点之间距离增量。对三维网格，两个结点之间的路径数为K=(X+Y+Z)!/(X!Y!Z!) ，XYZ分别为两结点之间距离增量
64
11.6 MPP系统 (补充) 二维网格和环形网
65
11.6 MPP系统 (补充) 环形网可看做是直径更短的另一种网格。这种拓扑结构将环形和网格组合在一起，并能向高维扩展。环形网沿阵列每行和每列都有环形连接。一般说来，一个n×n二元环网的结点度为4，直径为2*[n/2」. 环网是一种对称的拓扑结构，所有附加的回绕连接可使其直径比网格结构减少二分之一。
66
11.6 MPP系统 (补充) 超立方体 这是一种二元n-立方体结构，它已在nCUBE和CM-2等系统中得到了实现。一般说来，一个n-立方体由N=2n 个结点组成，它们分布在n维上，每维有两个结点。 4-立方体可通过将两个3-立方体的相应结点互连组成。一个n-立方体的结点度等于n，也就是网络的直径。实际上，结点度随维数线性地增加，所以很难设想超立方体是一种可扩展结构。
67
(a)3-立方体 (b)由2个3-立方体组成的4-立方体
11.6 MPP系统 (补充) (a)3-立方体 (b)由2个3-立方体组成的4-立方体
68
11.6 MPP系统 (补充) 低维网络在负载不均匀情况下运行较好，因为它们有较多的资源共享。在高维网络中，连线常分配给指定的维，各维之间不能共享。例如，在二元n-立方体中，可能有的线已达到饱和，而物理上分配给其它维的相邻的连线却都还空闲。 网络直径的变化范围很大。但随着硬件路由技术的不断革新(如虫孔方式），路由已不是一个严重问题，因为任意两结点间的通信延迟在高度流水线操作下几乎是固定不变的。链路数会影响网络价格，等分宽度将影响网络的带宽。对称性会影响可扩展性和路由效率。
69
11.6 MPP系统 (补充) 动态连接网络 为了达到多用或通用的目的，需要采用动态连接网络，它能根据程序要求实现所需的通信模式。它不用固定连接，而是沿着连接通路使用开关或仲裁器以提供动态连接特性。 按照价格和性能增加的顺序，动态连接网络的排队次序为总线系统、多级互连网络(MIN)和交叉开关网络。 采用动态网络的多处理机的互连是在程序控制下实现的。定时、开关和控制是动态互连网络的三个主要操作特征。
70
11.6 MPP系统 (补充) 根据级间连结方式，单级网络(single-stage network)也称循环网络(recirculating network), 因为数据项在到达最后目的地之前可能在单级网络中循环多次。单级网络的成本比较低，但在建立某种连接时可能需要多次通过网络。交叉开关和多端口存储器结构都属于单级网络。
71
11.6 MPP系统 (补充) 多级网络由一级以上的开关元件构成。这类网络可以把任一输入与任一输出相连。级间连接模式的选择取决于网络连接特性。 不同级的连接模式可能相同也可能不相同，这与所设计的网络的类型有关。 Omega网、Flip网和Baseline网都是多级网络。
72
11.6 MPP系统 (补充) 如果同时连接多个输入输出对时,可能会引起开关和通信链路使用上的冲突，这种多级网络称为阻塞网络(blocking network)。 阻塞网络的实例有Omeage网(Lawrie,1975)、Baseline网(Wu和Feng,1980)、Banyan网(Goke和lipovski,1973)和Delta网(Patel,1979)。 如果多级网络通过重新安排连接方式可以建立所有可能的输入输出之间的连接，则称之为非阻塞网络(nonblocking network)。这类网络中，任何输入输出对之间总可以建立连接通路。Benes网络(Benes,1965)具有这种功能
73
11.6 MPP系统 (补充) 1.总线系统 总线系统实际上是一组导线和插座，用于处理与总线相连的处理器、存储模块和外围设备间的数据业务。总线只用于源(主部件)和目的(从部件)之间处理业务。在多个请求情况下，总线仲裁逻辑必须每次能将总线服务分配或重新分配给一个请求。 系统总线在处理机、I／O子系统、存储模块或辅助存储设备(磁盘、磁带机等)之间提供了一条公用通信通路。 公用总线是在分时基础上工作的。总线研制中的重要问题有总线仲裁、中断处理、一致性协议和总线事务的处理等。
74
11.6 MPP系统 (补充) 一种总线连接的多处理机系统
75
11.6 MPP系统 (补充) 2.交叉开关网络 在交叉开关网络中，每个输入端通过一个交叉点开关可以无阻塞地与一个空闲输出端相连。交叉开关网络是单级网络，它由交叉点上的一元开关构成。交叉网络主要用于中小型系统。 从存储器读出的数据一旦可用时，该数据通过同一交叉开关回送给请求的处理器。通常，这类交叉开关网络需要使用n×m个交叉点开关。正方形交叉开关网络(n＝m)可以无阻塞地实现n!种置换。
76
11.6 MPP系统 (补充) 交叉开关网络的带宽和互连特性最好。
在交叉开关网络的每一行中可以同时接通多个交叉点开关，所以交叉点开关网络中n对处理器可以同时传送数据。 交叉开关网络的带宽和互连特性最好。 交叉开关网络每个周期可以实现n个数据传输，与每个总线周期只传一个数据相比，它的频宽最高。交叉开关网络对小型多处理机系统来说性能价格比较高。但单级交叉开关网络一旦构成后将不能扩充。
77
11.6 MPP系统 (补充) 多端口存储器则负责分解各台处理器的请求冲突。
多端口存储器结构是一个折衷方案，它介于低成本低性能的总线系统和高成本高带宽的交叉开关系统之间。总线被所有处理器和与之相连的设备模块分时地共享。 多端口存储器则负责分解各台处理器的请求冲突。 当m和n值很大时，这种多端口存储器结构将变得十分昂贵。典型的多处理机应用配置是四台处理机和16个存储器模块。
78
11.6 MPP系统 (补充) 4.多级网络 多级网络可用于构造大型多处理机系统。每一级都用了多个a×b开关，相邻级开关之间都有固定的级间连接。为了在输入和输出之间建立所需的连接，可用动态设置开关的状态来实现。 各种多级网络的区别就在于所用开关模块和级间连接模式的不同。一个a×b开关模块有a个输入和b个输出。一个二元开关与a=b=2的2×2开关模块相对应。在理论上a与b不一定要相等，但实际上a和b经常选为2的整数幂，即a=b=2k，k≥1。最简单的开关模块是2×2开关。常用的级间连接模式包括混洗、交叉、立方体连接等。
79
11.7 本章小结 并行性是指计算机系统具有同时进行运算或操作的特性，它包括同时性（两个以上事件在同一时刻发生）与并发性（两个以上事件在同一时间间隔发生）两种含义。并行性的四种技术是： ①时间并行（时间重叠）; ②空间并行（资源重复）; ③时间并行+空间并行； ④资源共享（软件方法）. Flynn将计算机体系结构分为SISD、SIMD、MISD、MIMD四种类型。虽然MISD没有实际机器，但是四种分类方法确实纲目清晰，有利于认识计算机系统的总体结构。 超长指令字处理机是由编译程序找出指令间潜在的并行性，把多个能并行执行的操作组合在一起形成一条具有多个操作段的超长指令。每个操作段控制一个功能部件，相当于一个机器周期中同时执行多条指令。其并行度取决于操作段数目。 向量处理机是解决数值计算问题的一种高性能计算机体系结构，采用数组方式和流水方式执行运算。典型机器有早期的SIMD处理机Cray-1, 20世纪90年代推出的MIMD并行向量处理机Cray y-MP和C90。它们采用时间并行技术+空间并行技术，并行地处理多条流水线上独立无关的数据。
80
11.7 本章小结 对称多处理机SMP是当今高性能、高可用性计算机系统的主要研究对象，它属于MIMD结构，是实现粗粒度（作业级或任务级）并行性的主要方式。SMP由多个独立的处理机组成，每个处理机都能独立执行自己的程序，为此需要多处理机操作系统支持。为解决SMP中Cache一致性的问题，提出了目录协议和监听协议。SMP的典型机器有IBM z990系列机。 机群系统是MIMD计算机系统的一种类型，它是由一组完整的计算机（结点）通过高性能的网络或局域网连接而成的系统。它们作为一个统一的计算资源一起工作，并能产生一台机器的印象。“单一系统形象”意指一台计算机离开机群系统仍能运行自己的任务。机群系统的体系结构有两种： ①无共享结构； ②共享磁盘结构。典型的机群系统有IBM SP2和国产超级刀片系统。
81
作业 第2、7、13题 本章内容不在期末考试范围内。
Similar presentations
