并行计算机体系结构 东南大学计算机学院 任国林

Presentation on theme: "并行计算机体系结构 东南大学计算机学院 任国林"— Presentation transcript:

1 并行计算机体系结构 东南大学计算机学院 任国林
东南大学计算机学院 任国林

2 一、课程目标 1.并行性理论的研究 并行计算机系统模型与体系结构； 并行程序设计模型与通信模型； 并行计算机性能评测方法；
可扩展性原理及实现方法。 2.并行技术和结构的研究 微处理器并行技术； 互连网络技术； 共享存储技术及体系结构； 分布存储技术与可扩展体系结构； 通信时延包容技术。

3 二、参考教材 1、并行计算机体系结构，陈国良等著，高等教育出版社， ISBN 7-04—11558-1，2002.9
2、并行计算机体系结构，David E.Culler等著，李晓明等译，机械工业出版社，ISBN ， 3、可扩展并行计算—技术、结构与编程，黄铠、徐志伟著，陆鑫达等译，机械工业出版社，2000.5 4、计算机系统结构—一种定量的方法(第5版)，John L. Hennessy等著，郑纬民等译，清华大学出版社，2002.8 5、计算机系统结构(第二版)，郑纬民、汤志忠著，清华大学出版社，1998.9

4 第一章 系统结构设计基础

5 第一节 计算机系统结构概念 一、计算机系统结构概念 1、计算机系统层次结构 L6：应用语言级 L5：高级语言级 L4：汇编语言级
第一节 计算机系统结构概念 一、计算机系统结构概念 1、计算机系统层次结构 翻译（应用程序包） 翻译（编译程序） 翻译（汇编程序） 解释 硬件直接执行 部分解释 计算机语言实现技术 软硬件 交界面 L6：应用语言级 L5：高级语言级 L4：汇编语言级 L3：操作系统级 L2：机器语言级 L1：微程序机器级 L0：电子线路 硬件 固件 软件 虚拟机器 实际机器 回下页

6 2、计算机系统设计方法 (1)由上向下方法 从软件到硬件，适合专用机的设计 结果：形成软、硬脱节 (2)由下向上方法
从硬件到软件，适合通用机的设计 结果：形成软、硬脱节 (3)从中间开始方法 从软、硬件交界面开始设计 要求：不断进行交互、优化设计 →需要较好的评价工具和方法 转上页

7 *精确定义：机器语言程序员、编译程序编写者所看到的计算机的属性，即概念性结构和功能特性
3、系统结构定义 *基本定义：程序员所看到的计算机的属性 *精确定义：机器语言程序员、编译程序编写者所看到的计算机的属性，即概念性结构和功能特性 概念性结构—系统的软、硬件功能界面； 功能特性—界面的功能分配，即界面的接口或组织 *研究内容：数据表示、寻址方式、指令系统，寄存器组织; 存储系统； 中断机构、I/O结构； 机器工作状态定义和切换、信息保护 *实质：研究软硬件之间的界面定义及其上下的功能分配 回下页

8 计算机系统结构包含内容示意图 进程管理程序 作业管理程序 文件管理程序 存储管理程序 设备管理程序 信息保护 操作系统级机器 注：
作业管理包含用户界面功能 输入设备触发程序执行 指令系统 程序员看到的属性 信息保护 机器状态 存储系统 I/O系统 中断系统 CPU … 键盘接口 键盘 显卡 显示器 MEM 磁盘接口 磁盘 机器语言级机器 计算机系统结构包含内容示意图 转上页

9 *计算机组成： 定义—计算机系统设计人员看到的基本属性 实质—是系统结构的逻辑实现 计算机组成包含内容—数据通路宽度、专用部件设计、各种OS共享程度、功能部件并行度、控制机构组成方式、排队与缓冲技术、预估与预判技术、可靠性技术等 *系统结构、计算机组成、物理实现三者关系： 1 : n : m 系统结构 ─── 计算机组成 ─── 物理实现

10 在应用环境、所用语言种类及特性、对OS的特殊要求、所用外设特性、技术经济指标、市场分析等方面进行分析
4、计算机系统结构设计步骤 (1)需求分析 在应用环境、所用语言种类及特性、对OS的特殊要求、所用外设特性、技术经济指标、市场分析等方面进行分析 (2)需求说明 形成设计准则、功能说明、器件性能说明等需求 (3)概念性设计 进行软、硬件功能分析，确定机器级界面 (4)具体设计 机器级界面各方面的确切定义，可考虑几种方案 设计准则：造价/可靠性/可扩展性/兼容性/速度等方面的原则 (5)反复进行评价及优化设计

11 *并行计算机：是一组相互通信、相互协作的处理单元， 用以快速求解大型问题
5、并行体系结构 *并行计算机：是一组相互通信、相互协作的处理单元， 用以快速求解大型问题 总线或互连网络 ··· SM LM MB NIC P/C 互连网络 Bridge IOB

12 微体系结构—节点内部结构,主要为处理器及其壳的结构 宏体系结构—并行计算机的整体结构，包括节点间互连、通信、存储器访问等方面
*并行体系结构： 由宏体系结构、微体系结构两部分组成 微体系结构—节点内部结构,主要为处理器及其壳的结构 宏体系结构—并行计算机的整体结构，包括节点间互连、通信、存储器访问等方面 *并行体系结构研究内容： 互 连—结构模型、互连网络 存储器—访存模型、一致性模型(Cache/存储) 交 互—编程模型、通信机构、同步机构 ※微体系结构—结点体系结构，包括ALU、CU、LM、Cache、总线等； 宏体系结构—各结点间的结构，包括结点间互连、通信、存储器等

13 二、计算机系统结构分类 1、Flynn分类法 *分类原理：按指令流和数据流的多倍性进行分类
*结构种类：SISD，SIMD，MISD，MIMD SIMD CU … MMm DS1 IS MM1 PUn DSn PU1 SISD CU MM IS PU DS MISD … DS IS1 ISn MMm MM1 PU1 CU1 MIMD … DS1 IS1 ISn DSn MMm MM1 PU1 CU1 *缺点：对流水线处理机的分类不明确

14 *分类原理：在三个层次，按并行程度及流水处理程度分类 层次— PCU（程序控制部件或宏流水） K级 ALU（算术逻辑部件或指令流水） D级
2、Handler分类法 *分类原理：在三个层次，按并行程度及流水处理程度分类 层次— PCU（程序控制部件或宏流水） K级 ALU（算术逻辑部件或指令流水） D级 ELC（基本逻辑线路或操作流水） W级 描述— T(C)＝<K×K’，D×D’，W×W’> 其中：K为PCU数、K’为宏流水级数(PCU数)， D为每个PCU中ALU数、D’为指令流水级数(ALU数)， W为ALU或PE字长，W’为操作流水线级数(ELC套数) *特点：对并行及流水线的程度有清晰的描述 注：①流水属并行的一种类型，但有所不同； ②并行程度越好，性能越高

15 *分类原理：按照系统的最大并行程度进行分类 *最大并行度：单位时间内能处理的最大二进制位数 即 Pm=位片宽×字宽
3、冯氏分类法 *分类原理：按照系统的最大并行程度进行分类 *最大并行度：单位时间内能处理的最大二进制位数 即 Pm=位片宽×字宽 位片宽 字宽 SISD SIMD（MPP） SIMD MIMD 1 m n m’ n’

16 4、按控制方式分类 *分类原理：按程序执行的控制方式分类 *分类结果：共有4种 控制流方式—指令按逻辑顺序执行(如冯·诺依曼模型)； 数据流方式—只要操作数到位，指令即可执行， 无序执行(↓，源→目的求解过程)； 规约方式—当需要该指令结果时，该指令才会执行， 无序执行(↑，目的→源→目的求解过程)； 匹配方式—由谓词模式匹配驱动指令的执行， 适合非数值型数据应用，常用于智能型计算机 *特点：除控制流方式外，其它的并行程度较好

17 第二节 系统设计的定量原理 一、大概率事件优先原则 *基本思想：对大概率事件赋予优先的处理权和资源使用权,以获得全局的最优结果
第二节 系统设计的定量原理 一、大概率事件优先原则 *基本思想：对大概率事件赋予优先的处理权和资源使用权,以获得全局的最优结果 ※该原则是系统设计中最重要和最常用的原则 *应用举例： 指令系统—指令操作码采用霍夫曼编码； 溢出处理—优化不溢出情况的处理； 存储系统—层次结构使高频使用数据存取速度更快， 虚拟存储器的TLB用高速芯片组成

18 二、Amdahl定律 *基本思想：优化某部件所获得的系统性能的改善程度，取决于该部件被使用的频率，或所占总执行时间的比例
*举例：某功能处理时间占系统时间的40%，将其处理速度加快10倍后，整个系统性能提高多少？ 0.0 0.5 1.0 fe Sp 10 1 5 解—已知fe=0.4，re=10，利用Amdahl定律，则 Sp=1.56 re=10时Sp和fe的关系如右图： *应用：使用该定律可改善“系统瓶颈”性能 方法—若改善某部件性能后，系统性能急剧提高， 则该部件为“系统瓶颈”

19 三、程序访问的局部性原理 *基本思想：程序执行时，呈现出频繁重复使用那些“簇聚”的数据和指令的规律，包含时间局部性和空间局部性
时间局部性-- 近期被访问的信息，可能马上被访问 空间局部性-- 与被访问地址相邻的信息可能会一起被访问 *应用：层次存储体系设计

20 四、软硬件取舍原则 1、现有软硬件条件下，所选方法应有助于提高系统的性能/价格 例： 研制费用 生产费用 产品费用 硬件方法 Dh Mh
Dh/V+Mh 软件方法 C×Ds R×Ms C×Ds/V+R×Ms 说明：V—设备数量，C—重复设计次数，R—复制次数 2、所选方法应尽量不限制计算机组成和实现技术 例：数据表示设计不应限制数据宽度与之一一对应； 主存容量设计不应限制是否采用多体交叉存储器等 D—研制费用，M—生产费用； C-软件需要重新设计的次数；R—同一功能软件重复复制和存储次数； V—生产台数。 3、所选方法应能够对编译程序和操作系统的实现提供好的支持 例：指令系统中增加OS所需指令； 根据编译要求设置一定数量通用寄存器等

21 第三节 计算机系统性能评价 一、计算机系统性能 *计算机性能：正确性、可靠性和工作能力 ·正确性：与数学计算结果比较，通常认为是正确的
第三节 计算机系统性能评价 一、计算机系统性能 *计算机性能：正确性、可靠性和工作能力 ·正确性：与数学计算结果比较，通常认为是正确的 ·可靠性：用平均无故障时间表示，通常认为是可靠的 ·工作能力：即系统的速度，通常用程序执行时间表示； 可分为峰值性能和持续性能 响应时间—指任务从输入到结果输出的所有时间， 反映CPU、I/O系统及OS等的总体性能； 吞吐率—指单位时间内能处理的作业或任务数量， 反映系统的多任务处理性能

22 T响应＝TCPU＝T系统CPU＋T用户CPU＝IN×CPI×TC CPI包含ALU、访问MEM及I/O的时间(含等待时间)
1、响应时间 响应时间指一个任务从输入到输出的总时间 T响应＝TCPU＝T系统CPU＋T用户CPU＝IN×CPI×TC CPI包含ALU、访问MEM及I/O的时间(含等待时间) *特点：能够反映软硬件系统的总体性能，但不易测量 *影响TCPU的因素： TCPU ＝IN×CPI×TC＝IN×(p＋m×k)×TC 其中 p—处理周期数/指令，m—访存次数/指令，k—访存时延 性能因子 系统属性 IN p m k TC 指令系统结构 × 编译技术 PE实现与控制技术 Cache和内存层次结构

23 2、吞吐率 *定义：指单位时间内能够处理作业(或任务)的数量 吞吐率 = n÷n个任务总时间 *常用标准：对作业(或任务)的定义无法统一 MIPS(每秒百万次指令)-- MIPS不能反映指令功能强弱，常用相对MIPS表示 MFLOPS(每秒百万次浮点运算)— 不同操作通过正则化方法实现关联， MFLOPS只能反映浮点操作能力

24 *特点：吞吐率与I/O软硬件组织方式及OS有很大关系；
能够反映软硬件系统对多任务的响应能力 *提高吞吐率方法： 流水化--使多个作业流水处理； 并行处理--给每个PE分配多个作业，各PE相互协调 3、利用率 *定义：利用率＝持续性能÷峰值性能 *特点：不直接表示系统性能，与前两种指标有密切关系； 对系统性能优化及结构改进起着至关重要的作用！

25 *性能加速比：多机系统相对于单机系统性能提高的比例
4、系统可扩放性 常用于评价多机系统的并行处理能力 *性能加速比：多机系统相对于单机系统性能提高的比例 其中 p--问题规模，n--处理器数量，h--通信时间 *系统可扩放性：系统性能随处理机数n增加而增长的比例 Ψ=fS(n) S n 1 B系统 A系统 衡量方法--测量不同n时的加速比， 得到性能可扩放性曲线 影响因素—结构、处理器数、问题规模、存储系统等

26 二、性能评价与比较 1、评价技术 (1)分析技术
*思路：在一定假设条件下，计算机系统参数与性能指标间存在着某种函数关系，按其工作负载的驱动条件列出方程，用数学方法求解后评价 *发展：从脱离实际的假设发展到近似求解 近似求解算法—聚合法、均值分析法、扩散法等 *应用：可应用于设计中系统的分析与评价 A机：TCPUA=INA×(0.2×2+0.2×1+0.6×1)×TCA=1.2 INA×TCA B机：TCPUB=0.8INA×((0.2/0.8)×2+(1- 0.2/0.8)×1)×1.15TCA=1.15 INA×TCA 结果：B机比A机工作速度快。 例—A机执行的程序中有20%转移指令(需2TC)，转移指令都需要一条比较指令(需1TC)配合，其他指令均为1TC。B机中转移指令包含比较指令功能，但TC比A机慢15%。执行该程序时，A机、B机哪个工作速度快？ 回下页

27 *思路：建立模拟器，模拟系统性能模型和工作负载模型，对运行后的数据进行统计、分析和评价
(2)模拟技术 *思路：建立模拟器，模拟系统性能模型和工作负载模型，对运行后的数据进行统计、分析和评价 *方法： 按被评价系统的运行特性建立系统模型； 按系统可能有的工作负载特性建立工作负载模型； 用语言编写模拟程序，模仿被评价系统的运行； 设计模拟实验，依照评价目标，选择与目标有关因素，得出实验值，再进行统计、分析 *应用：可应用于设计中或实际应用中系统的分析与评价； 可与分析技术相结合，构成一个混合系统 转上页

28 *思路：通常采用基准测试程序对系统进行实际性能评价
(3)测量技术 *思路：通常采用基准测试程序对系统进行实际性能评价 *基准测试程序： 有实际应用程序、核心程序、合成测试程序三个层次 第一个层次—用于测试系统总体性能； 后两个层次--用于测试部件(如CPU、I/O系统等)性能 基准测试程序—具有三个层次的测试程序组，典型的有SPEC程序组，包含测试多个领域、三个层次的测试程序 *应用：只能应用于实际使用中系统的分析与评价； 通常根据系统的设计需求(应用领域)选择基准测试程序组中的部分测试程序进行测量

29 *目的：根据多种测试结果，比较不同系统的优劣
2、比较技术 *目的：根据多种测试结果，比较不同系统的优劣 *方法：算术平均、几何平均、调和平均方法 (1)算术平均方法 基准测试程序 处理机 X Y Z B1 20(1.00) 10(0.50) 40(2.00) B2 40(1.00) 80(2.00) 20(0.50) Am (1.00) (1.25) 基准测试程序 处理机 X Y Z B1 20(2.00) 10(1.00) 40(4.00) B2 40(0.50) 80(1.00) 20(0.25) Am (1.25) (1.00) (2.13) *特性：选择不同的参考机，Am结论不同 回下页

30 依据—Gm(Xi)/Gm(Yi)=Gm(Xi/Yi)
(2)几何平均方法 基准测试程序 处理机 X Y Z B1 20(1.00) 10(0.50) 40(2.00) B2 40(1.00) 80(2.00) 20(0.50) Gm (1.00) 基准测试程序 处理机 X Y Z B1 20(2.00) 10(1.00) 40(4.00) B2 40(0.50) 80(1.00) 20(0.25) Gm (1.00) 特性：Gm性能与参考计算机性能无关 依据—Gm(Xi)/Gm(Yi)=Gm(Xi/Yi) (3)调和平均方法 特性：Hm最接近CPU的实际性能 依据—Hm与所有测试程序时间总和成反比关系 转上页

31 第四节 系统结构的发展 一、影响计算机系统结构发展因素 1、软件对系统结构发展的影响 *影响因素：软件可移植性 (1)系列机
第四节 系统结构的发展 一、影响计算机系统结构发展因素 1、软件对系统结构发展的影响 *影响因素：软件可移植性 (1)系列机 *思想：具有相同系统结构或扩充原系统结构，组成或实现技术不同，来实现软件可移植性 *影响一：新的组成与实现技术很快得到应用，大量兼容产品的出现，推动了系统结构的发展 时间 机器档次 当前机器 向上兼容 向下兼容 高 低 向后兼容 向前兼容 影响二：量变到质变 系列机要求—保证向后兼容， 力争向上兼容 *影响二：要求系统结构基本不变，限制了系统结构的发展 回下页

32 *比较：解释程序存放位置、是否有硬件参与方面不同； 在解释指令系统、存储系统、I/O系统、OS方面相同
(2)模拟与仿真 *模拟：用机器语言解释来实现软件移植 需模拟目标机指令系统、存储系统、I/O系统、OS等的操作 *仿真：用微程序直接解释另一种指令系统 需解释目标机I/O系统、OS等的操作 *比较：解释程序存放位置、是否有硬件参与方面不同； 在解释指令系统、存储系统、I/O系统、OS方面相同 (3)统一高级语言方法 存在一定的困难，可争取汇编语言或接口/技术的统一 *方案1：采用统一的中间语言(如Java)，通过解释执行以适应不同的系统结构 *方案2：采用标准的开放系统(具有可移植性、交互操作性),用硬件抽象层技术适应不同的系统结构 转上页

33 *应用背景：应用领域、功能及性能要求有所不同 *应用需求：高速度、大容量、大吞吐率
2、应用对系统结构发展的影响 *应用背景：应用领域、功能及性能要求有所不同 *应用需求：高速度、大容量、大吞吐率 *系统结构设计思路： 分成不同级别的系统，以提高性能/价格 巨、大型机—研究专用系统结构、组成技术 其它型机—研究通用系统结构(吸纳先进结构与技术) *系统结构发展趋势： ·保持价格基本不变，提高性能 ·保持性能基本不变，降低价格 价格 时间 等性能线 巨型机 大型机 中、小型机 微型机 *对系统结构影响： 专用系统结构—无限制(应用是原动力) 通用系统结构—如何有效实现专用结构→通用结构

34 ·器件的发展推动了系统结构与组成技术的发展
3、器件对系统结构发展的影响 *器件使用方法： 通用片→现场片→半用户片→用户片 *对系统结构影响： ·器件的发展推动了系统结构与组成技术的发展 如—器件性能、使用方法影响系统结构及组成方法， 器件性/价提高，使结构、组成下移速度更快， 器件的发展，推动算法、语言的发展 ·系统结构的发展要求器件不断发展 如—新结构的使用，取决于器件发展能否提供可能 提高器件性能/价格，要求改变器件逻辑设计方法

35 二、并行性的发展 并行性—包括同时性(时刻)、并发性(时段) 1、并行性开发 *并行性等级划分： 执行程序角度 处理数据角度 信息加工步骤
执行程序角度 处理数据角度 信息加工步骤 操作级 位串字串 存储器操作并行 指令级 位并字串 处理器操作步骤并行 任务或过程级 位串字并 处理器操作并行 作业或程序级 全并行 任务或作业并行 *开发方法： 时间重叠、资源重复、资源共享 PE操作步骤并行指流水、操作并行指超标量

36 用三种并行性实现方法进行开发，得到如下系统结构树：
2、并行性发展 用三种并行性实现方法进行开发，得到如下系统结构树： 标量 顺序的 先行控制 I/E重叠 功能并行 多个功能部件 流水线 隐式向量 显式向量 存储器-存储器 寄存器-寄存器 SIMD MIMD 联想处理机 处理机阵列 多计算机 多处理机 计算机系统结构树 空间并行 时间并行

37 本章思考 1、系统结构精确定义、包含内容是什么？ 与计算机组成和实现的关系是什么？ 进行系统结构设计的方法和步骤是什么？
2、系统结构的分类方法有哪些？ 影响系统结构发展的因素又哪些？如何影响的？ 3、系统结构设计的定量原理有哪些？举例说明其应用。 4、计算机系统的性能指标有哪些？其特点和影响因素是什么？ 5、评价系统性能的方法有哪些？如何比较测量的结果？ 6、并行计算机与单处理器计算机在系统结构上有哪些区别？ 影响其性能的因素有哪些？如何评价？ 7、并行性包含的内容是什么？开发并行性的方法有哪些？ 系统结构树中结点采用哪些技术可实现变迁？