当前位置：文档之家 › 第七章 多处理机

第七章 多处理机

  • 格式：ppt
  • 大小：232.00 KB
  • 文档页数：20

下载文档原格式

  / 20

合集下载

计算机体系结构-第7章 多处理机

计算机体系结构-第7章 多处理机
ห้องสมุดไป่ตู้
第7章 多处理机
主 CPU
主存
CIOP
高速系统总线 BIOP NIOP GIOP
ACOP
CIOP----字符处理机 BIOP----数组处理机 NIOP----网络处理机 GIOP----图形处理机 ACOP----向量加速处理机
图7.5 异构非对称式多处理机的一般结构
第7章 多处理机
2. 松耦合(loosely coupled)多处理机 松耦合多处理机是通过消息传递方式来实现处理机间的相互通 信的。 而每台处理机是由一个独立性较强的计算机模块组成，该模 块由处理器、较大容量的本地存储器(在运算时所需的绝大部分的 指 令 和 数 据 均 取 自 本 地 存 储 器 ) 、 I/O 设 备 以 及 与 消 息 传 递 系 统 (Message Transfer System，MTS)相连的接口组成。当不同模块上 运行的进程间需要通信时，可通过网络接口电路及消息传递系统 进行信息交换。由于这种相互间的耦合程度是很松散的，因此称 之为松耦合多处理机。 松耦合多处理机可分为非层次式和层次式两种结构。
第7章 多处理机
(5)合理地进行资源分配和任务调度。 在MIMD多处理机中，由于任务的大小不相同， 各处理机的速度也可能不相同(如异构型多处理机系统)， 互连网络的拓扑结构和通信延迟在不同的多处理机中 也有很大的差别，在执行并发任务时，并不是使用的 处理机个数越多，系统获得的性能就越高。因此需要 采用软件手段，合理地进行资源分配和任务调度，否 则系统性能将受较大影响。而在SIMD并行处理机中， 程序员只需用屏蔽的手段来设置部分处理单元为不活 跃状态，来控制实际参加并行操作的处理单元数目。
因此，Cm*是一个三层总线多处理机，三级的访 存时间分别为：计算机模块内3.5μs，计算机模块群内 9.3μs，而群间则为26μs。

计算机系统结构 第七章自考练习题答案

计算机系统结构 第七章自考练习题答案

第七章多处理机历年真题精选1. 在多处理机上，两个程序段既能顺序串行、交换串行，又能并行，则这两个程序段之间必须是（ B ）。

A. 只有数据相关B. 只有源数据相关C. 只有数据反相关D. 只有数据输出相关2. 在多处理机上，有效计算的执行时间E与处理机机间的通讯辅助开销时间C的比值较小时，任务宜采用（粗）粒度。

3．多处理机互连形式一般有总线形式，环形互连形式，（交叉开关）形式，多端口存储器形式和（开关枢纽结构）形式等几种。

4. 多处理机实现的是（作业）和（任务）间的并行。

5. 用霍纳法则给定的表达式如下：E=a(b+c(d+e(f+gh)))利用减少树高的办法加速运算，要求：（1）画出树形流程图；（2）确定运算级数TP，处理机机数P、加速比SP和效率EP等的值。

（TP=7，P=3，SP=7/4，EP=7/12）6. 简述使用多处理机的目的和多处理机具备的特点。

(P182-183)同步强化练习一．单项选择题。

1. 多处理机主要实现的是（ A ）。

A.任务级并行B.指令级并行C.操作级并行D.操作步骤的并行2. 多处理机上两个程序段之间若有先写后读的数据相关，则（ B ）。

A.可以并行执行B.不可能并行C.必须并行执行D.任何情况均可交换串行3. 若两个程序段之间没有任何相关，则两个程序段（B ）。

A.不可并行B.可并行C.不可顺序串行D.不可交换串行4. 多处理机的各自独立型操作系统（ D ）。

A. 适合于紧耦合多处理机B.要求管理程序不必是可再入的C.工作负荷较平衡D.有较高的可靠性5. 多端口存储器适合于连接（A ）。

A.紧耦合多处理机B.松耦合多处理机C.机数很多的的处理机D.机数可变的多处理机6. 主从型管理程序只在（C ）运行。

A.多台处理机上B.一台随意的主处理机上C.一台指定的主处理机上D.处理机之间7. 能实现作业、任务级并行的异构型多处理机属（C ）。

A.SISDB.MISDC.MIMDD.SIMD8. 属于MIMD系统的结构是（ D ）。

数字化医疗仪器第07章 单片数字信号处理机应用

数字化医疗仪器第07章 单片数字信号处理机应用

辅助寄存 器算术单 ARAU： 元ARAU： 产生访问 存储器所 需的地址。 需的地址。
4条内部总线：CPU1／CPU2和 条内部总线：CPU1／CPU2和 REG1／REG2。 REG1／REG2。 硬件乘法器： 硬件乘法器：单指令周期中完成 两个32bit浮点数乘法 32bit浮点数乘法， 两个32bit浮点数乘法，乘积为 40bit 或完成两个24bit定点数 bit， 24bit 40bit，或完成两个24bit定点数 乘法，乘积为32bit。 32bit 乘法，乘积为32bit。 桶形移位器： 桶形移位器：对 32bit bit数在一个周 32bit数在一个周 期内实现一次左 移或右移。 移或右移。
TMS320C30结构的功能方框图 TMS320C30结构的功能方框图
7.2.2 TMS320C30的CPU结构 7.2.2 TMS320C30的CPU结构
CPU 由 以 下 单 元 组 成 ： 硬件乘法器、 硬件乘法器、 算术逻辑单元、 算术逻辑单元、 桶形移位器、 桶形移位器、 内部总线、 内部总线、 辅助寄存器算术单元、 辅助寄存器算术单元 、 CPU寄存器组 寄存器组。 CPU寄存器组。
浮点和定点处理器的动态范围比较
数据类型
产品名称 RAM TMS320C10 TMS320C15 TMS320C17 TMS320C25 TMS320C25 —50 TMS320C28 TMS320C50 TMS320C51 TMS320C53 TMS320C30 TMS320C30 一50 TMS320C31 TMS320C40 144 256 256 544 544 544 10K 2K 4K 2K 2K
7.2.3 TMS320C30的存储器结构 7.2.3 TMS320C30的存储器结构

多处理机new

多处理机new

1. 二维数组的无冲突访问存储器 • 要求：一个n×n的二维数组，按行、列、对 角线和反对角线访问，并且在不同的变址位 移量情况下，都能实现无冲突访问。 • 顺序存储：按行、对角线访问没有冲突，但 按列访问每次冲突
0 号体 体内地址 0 1 2 3
2012年8月15日星期三
1 号体
2 号体
3 号体
16
3. 二维数组的无冲突访问存储方案(之二) • 规则：对于任意一个n×n的数组，如果能够 找到满足n＝22P关系的任意自然数p，则这个 二维数组就能够使用n个并行存储体实现按行、 列、对角线和反对角线的无冲突访问。 • 4×4数组用4个存储体的无访问冲突存储方案
0 号体 体内地址 0 1 2 3
或(SSM,Scalable Shared-Memory)
物理上分离的多个存储器可作为一个逻辑上共享的 存储空间进行编址.
• 通信机制:可利用Load和Store指令中的地址隐 含地进行数据通信. 2.多计算机(multicomputers)
整个地址空间由多个独立的地址空间构成,它们在逻 辑上是独立的,远程的处理器不能对其直接寻址.
2012年8月15日星期三 计算机系统结构 第九章 多处理机 18
7.2.1.2 多处理机的Cache一致性
1. Cache不一致性原因
• 在并行处理机和多处理机系统中，采用局部 Cache会引起Cache与共享存储器之间的一致 性问题。 • 出现不一致性问题的原因有三个： 共享可写的数据、进程迁移、I/O传输
第七章 多处理机
• 多处理机定义： 两个或两个以上处理机(包括PU和CU)，通 过高速互连网络连接起来，在统一的操作 系统管理下，实现指令以上级（任务级、 作业级）并行。 • 按照Flynn分类法，多处理机系统属于 MIMD计算机 • 研究多处理机的目的：提前10年得到性能 高100倍的高性能计算机系统。

计算机系统结构课后答案uint7

计算机系统结构课后答案uint7

第七章课后题1.多处理机在结构、程序并行性、算法、进程同步、资源分配和调试上与并行处理机有什么差别？答：多处理机与并行处理机的主要差别是并行性的等级不同。

（1）结构灵活性。

多处理机制结构灵活性高于并行处理机。

（2）程序并行性。

多处理是指令、任务、作业并行，并行性的识别较难;并行处理机是操作级并行，并行性的识别较易。

（3）并行任务派生。

并行处理机工作能否并行工作由指令决定，多处理机必须有专门指令指明程序能否并行执行，派生的任务数是动态变化的。

（4）进程同步。

并行处理机的进程同步是自然的，而多处理机必须采取同步措施。

（5）资源分配和任务调度。

多处理机的资源分配和任务调度比并行处理机复杂得多。

2.多处理机有哪些基本特点？发展这种系统的主要目的可能有哪些？多处理着重解决哪些技术问题？答：○多处理机的基本特点：多处理机具有两台以上的处理机,在操作系统控制下通过共享的主存或输入/输出子系统或高速通讯网络进行通讯.结构上多个处理机用多个指令部件分别控制,通过机间互连网络通讯;算法上不只限于处理向量数组,还要实现更多通用算法中的并行;系统管理上要更多地依靠软件手段,有效解决资源分配和管理,特别是任务分配,处理机调度,进程的同步和通讯等问题.○使用多处理机的目的:一是用多台处理进行多任务处理协同求解一个大而复杂的问题来提高速度,二是依靠冗余的处理机及其重组来提高系统的可靠性,适应性和可用性.○多处理着重要解决的技术问题:（1）硬件结构上，如何解决好处理机、存储器模块及I/O子系统间的互连。

（2）如何最大限度开发系统的并行性，以实现多处理要各级的全面并行。

（3）如何选择任务和子任务的大小，即任务的粒度，使并行度高，辅助开销小。

（4）如何协调好多处理机中各并行执行任务和进程间的同步问题。

（5）如何将任务分配到多处理机上，解决好处理机调度、任务调度、任务调度和资源分配，防止死锁。

（6）一旦某个处理发生故障，如何对系统进行重新组织，而不使其瘫痪。

第7章习题解答

第7章习题解答

第七章习题解答一、填空1．一个操作系统的可扩展性，是指该系统能够跟上先进计算技术发展的能力。

2．在引入线程的操作系统中，线程是进程的一个实体，是进程中实施调度和处理机分派的基本单位。

3．一个线程除了有所属进程的基本优先级外，还有运行时的当前优先级。

4．在Windows 2000中，具有1~15优先级的线程称为可变型线程。

它的优先级随着时间配额的用完，会被强制降低。

5．Windows 2000在创建一个进程时，在内存里分配给它一定数量的页帧，用于存放运行时所需要的页面。

这些页面被称为是该进程的“工作集”。

6．Windows 2000采用的是请求调页法和集群法相结合的取页策略，把页面装入到内存的页帧里的。

7．分区是磁盘的基本组成部分，是一个能够被格式化和单独使用的逻辑单元。

8．MFT是一个数组，是一个以数组元素为记录构成的文件。

9．只要是存于NTFS卷上的文件，在MFT里都会有一个元素与之对应。

10．在Windows 2000的设备管理中，整个I/O处理过程都是通过I/O请求包（IRP）来驱动的。

二、选择1．在引入线程概念之后，一个进程至少要拥有D 个线程。

A． 4 B．3 C．2 D．12．在Windows 2000中，只有A 状态的线程才能成为被切换成运行状态，占用处理器执行。

A．备用B．就绪C．等待D．转换3．Windows 2000是采用C 来实现对线程的调度管理的。

A．线程调度器就绪队列表B．线程调度器就绪队列表、就绪位图C．线程调度器就绪队列表、就绪位图、空闲位图D．线程调度器就绪队列表、空闲位图4．在Windows 2000里，一个线程的优先级，会在A 时被系统降低。

A．时间配额用完B．请求I/O C．等待消息D．线程切换5．在单处理机系统，当要在进程工作集里替换一页时，Windows2000实施的是B 页面淘汰策略。

A． FIFO（先进先出）B．LRU（最近最久未用）C．LFU（最近最少用）D．OPT（最优）6．在页帧数据库里，处于下面所列A 状态下的页帧才可以变为有效状态。

计算机操作系统【第七章】 汤子瀛版

计算机操作系统【第七章】1．试画出微机和主机中常采用的I/O系统结构图。

微机中常采用的I/O系统结构图为：主机中常采用的I/O系统结构图为：2．试说明设备控制器的构成。

设备控制器的构成如图所示：由上图可见，设备控制器由以下三部分组成：（1）设备控制器与处理机的接口，该接口用于实现CPU与设备控制器之间的通信，提供有三类信号线：数据线、地址线和控制线。

（2）设备控制器与设备的接口，可以有一个或多个接口，且每个接口连接一台设备。

每个接口都存在数据、控制和状态三种类型的信号。

（3）I/O逻辑，用于实现对设备的控制。

其通过一组控制线与处理机交互，处理机利用该逻辑向控制器发送I/O命令，I/O逻辑对收到的命令进行译码。

3．为了实现CPU与设备控制器之间的通信，设备控制器应具有哪些功能？为了实现CPU与设备控制器之间的通信，设备控制器应具有如下功能：（1）接受和识别命令。

CPU可以向控制器发送多种不同的命令，设备控制器应能接收并识别这些命令。

设置控制寄存器来存放所接收的命令和参数。

（2）数据交换，指实现CPU与控制器之间、控制器与设备之间的数据交换。

设置数据寄存器来存放有关数据。

（3）设备状态的了解和报告。

控制器记录下所连接设备的状态以供CPU了解。

为此，要在控制器中设置一状态寄存器，用其中的每一位反映设备的某一状态。

（4）地址识别。

配置地址译码器以便于正确识别设备地址。

4．分别就字节多路通道、数据选择通道和数组多路通道进行解释。

①字节多路通道含有许多非分配型子通道分别连接在低、中速I/O设备上，子通道按时间片轮转方式共享主通道，按字节方式进行数据传送。

具体而言，当第一个子通道控制其I/O 设备完成一个字节的交换后，便立即腾出字节多路通道（主通道），让给第二个子通道使用；当第二个子通道也交换完一个字节后，又依样把主通道让给第三个子通道使用，以此类推。

转轮一周后，重又返回由第一个子通道去使用主通道。

②数组选择通道只含有一个分配型子通道，一段时间内只能执行一道通道程序、控制一台设备按数组方式进行数据传送。

计算机系统结构(第2版(课后习题答案

word 文档下载后可自由复制编辑你计算机系统结构清华第 2 版习题解答word 文档下载后可自由复制编辑1 目录1.1 第一章（P33）1.7-1.9 （透明性概念），1.12-1.18 （Amdahl定律），1.19、1.21 、1.24 （CPI/MIPS）1.2 第二章（P124）2.3 、2.5 、2.6 （浮点数性能），2.13 、2.15 （指令编码）1.3 第三章（P202）3.3 （存储层次性能）， 3.5 （并行主存系统），3.15-3.15 加 1 题（堆栈模拟），3.19 中（3）（4）（6）（8）问（地址映象/ 替换算法-- 实存状况图）word 文档下载后可自由复制编辑1.4 第四章(P250)4.5 （中断屏蔽字表/中断过程示意图），4.8 （通道流量计算/通道时间图）1.5 第五章（P343）5.9 （流水线性能/ 时空图），5.15 （2种调度算法）1.6 第六章（P391）6.6 （向量流水时间计算），6.10 （Amdahl定律/MFLOPS）1.7 第七章（P446）7.3 、7.29（互连函数计算），7.6-7.14 （互连网性质），7.4 、7.5 、7.26（多级网寻径算法），word 文档下载后可自由复制编辑7.27 （寻径/ 选播算法）1.8 第八章(P498)8.12 ( SISD/SIMD 算法)1.9 第九章(P562)9.18 ( SISD/多功能部件/SIMD/MIMD 算法)（注：每章可选1-2 个主要知识点，每个知识点可只选 1 题。

有下划线者为推荐的主要知识点。

）word 文档 下载后可自由复制编辑2 例 , 习题2.1 第一章 (P33)例 1.1,p10假设将某系统的某一部件的处理速度加快到 10倍 ,但该部件的原处理时间仅为整个运行时间的40%，则采用加快措施后能使整个系统的性能提高多少？解：由题意可知： Fe=0.4, Se=10，根据 Amdahl 定律S n To T n1 (1Fe )S n 1 10.6 0.4100.64 Fe Se 1.56word 文档 下载后可自由复制编辑例 1.2,p10采用哪种实现技术来求浮点数平方根 FPSQR 的操作对系统的性能影响较大。

计算机科学导论 第七章 操作系统

作业都是程序，但并不是所有的程 序都是作业;
二、状态图
三、调度器：作业调度器和进程调度器 1、作业调度器
将一个作业从保持状态转入到就绪状态，或从运 行状态转入终止状态 即负责从作业中建立一个进程和终止一个进程
保持
作业调度器
终止
2、进程调度器
将一个进程从一个状态转入另一个状态
四、队列 计算机资源是有限的，和很多作业和进程都需 要使用计算机的资源。那么，谁先使用？何时 使用？怎么办？
7.2 演化
操作系统的发展过程 一、无操作系统的计算机系统（1945-50年代中期） 1. 人工操作方式
2. 脱机输入输出方式
1. 人工操作方式
工作流程：
（1）由程序员事先穿孔（对应程序和数据）
（2）将穿孔的纸带（卡片）装入纸带（卡片)输入机 （3）再启动输入机将程序和数据输入计算机 （4）然后启动计算机运行 （5）运行完毕取走计算机结果 （6）下一位用户
2、饥饿
这种情况与死锁相反。由于OS对于资源控制过严， 只有在所需要的资源都准备好后才能执行。限制太 多，造成永远得不到资源。 P136 图7-18
设备管理器
主要任务：监视I/O设备，保证其正常运行 维护I/O设备队列 控制I/O设备访问策略
文件管理器
主要任务：文件访问权限控制 文件的创建、删除、修改 文件的命名 存储管理，存在那儿？如何存？ 归档与备份
共享主机：多个用户都希望以“独占”方式共享一台计算 机。

方便上机：用户希望有一个终端设备直接将作业传递给计 算中心主机，并能直接对其作业控制。

三、分时系统
分时系统示意图
计算机硬件 分时操作系统
响应时间
…
123 n 时间片

提高“计算机系统结构”课程授课质量初探


专业 的－ ￣关键性课程 ，而且也是培养合格 Ｉ －＇ Ｊ Ｔ产业人才不可或缺 的课程 ，国内外各个 院校多年 来一直十分重视 “ 系统结构”的教学工作 。由于 “ 系统结构”内容抽象、枯燥 ，教学难度 比较 大 ，但其又是计算机专业承上启下的课程及与其他专业 区别 的重要课程之一 ，因而上好本课程 、 提高本课程的课程质量有着重要的意义。
二、明确学 习目标
有不少往届的学生反映 ， 从一开始学习 “ 系统结构”就处于混沌的状态 ，在枯燥 的学习中度 过一学期后 ，还是不清楚这门课讲 了些什么， 自己学了什么。之所以会这样 ，从我们教学的实践
来看 。原因在于学生不清楚 “ 系统结构”的课程结构 ，没有 明确的学习目标。 计算机系统按功能分为存储 、传输和处理三大块 ，存储 的设计 目标就是提供一个大的存储空 间；处理的设计 目标是采取各种措施来提高运算的速度；传输的设计 目标是为信息准确地找到 目 的地 ，并保证传输过程的安全性 。学生需要从一开始就 明确每一部分 的设计 目 ，并把这样的思 标 想贯穿在知识点 的学习中。例如 ，在学习流水线结构原理部分时 ，明确加快指令 的解释是计算机 采用流水线结构 的基本任务 ， 以这部分的学习就围绕着如何加快指令的解释进行。 所 学习 “ 系统结构” ，应该把握这门课程的特点 ，即从分析 、评测 的角度学习计算 机系统结构 的设计 和实现 ，对计算机 的结构不仅知其然 ，还需知其所 以然。在 “ 系统结构”课程教学时 ，需 要始终强调这一点。以处理流水线的数据相关为例 ，处理主存空间数相关采用 “ 推后法” ，而处 理通用寄存器组相关采用 了增加硬件的方法— 设置 “ 相关专用通路” 。后者采用增加硬件提高 了指令解释的速度 ，而前者以牺牲速度为代价 ，并未增加硬件 ，这是为什么呢？上课时我们让学 生利用学过的知识来解释。经过经常性事件” ；而主存空间数 相关发生的概率小 ，不属 于 “ 经常性事件” ，根据 Ａ ｄｈ 定律， ｍ ａｌ 应该 “ 加快经常性事件” 。这样 ，学生在学 习时知其所 以然 ，对 问题理解了 ，知识掌握很牢固； 另一方面 ，也有利于培养他们发现 问题 、分析问题 、解决问题的能力。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

7.2.2 机间互连形式
多处理机机间互连的形式是决定多处理机性能的一个重要 因素。在满足高通讯速率、低成本的条件下，互连还应灵活多 样，以实现各种复杂的乃至不规则的互连而不发生冲突 1.总线形式 多个处理机、存储器模块和外围设备通过接口和公用总线 相连，采用分时或多路转接技术传送。 为解决多处理机同时访问公用总线冲突，有静态优先级、 固定时间片、动态优先级、先来先服务等多种总线仲裁算法 总线形式适于机数少的多处理机。它结构简单、造价低、 可扩充性好；但总线性能和可靠性受物理因素的影响 2.环形互连形式 构造了一种逻辑总线，让各处理机之间点点相连成环状， 称为环形互连，如图7.6P187所示。在这种多处理机上，信息的 传递过程由发送进程将信息送到环上，经环形网络不断向下一 台处理机传递，直到信息又回到发送者为止
2.松耦合多处理机 松耦合多处理机中，每台处理机都有一个容量较大 的局部存储器，用于存储经常用的指令和数据，以减少 紧耦合系统中存在的访主存冲突。不同处理机间或者通 过通道互连实现通讯，以共享某些外部设备；或者通过 消息传送系统MTS来交换信息，这时各台处理机都带有 自己的外部设备。 一般，松耦合多处理机较适合做粗粒度的并行计算。 处理的作业分割成若干相对独立的任务，在各个处理机 上并行，而任务间的信息流量较小。如果各处理机任务 交互作用较少时。这种耦合度很松的系统是很有效的， 可看作一个分布系统。 图7.4P186给出了典型的经消息传送系统互连的松耦 合非层次型多处理机。
7.4.2 性能模型与分析
假定一个应用程序含T个任务，在N台处理机上运行，每个 任务的执行时间为E，不同处理机间一次通讯开销时间为C。 1.N=2且计算与通讯不能重叠 如果将I个任务分配给一台处理机，余下的T-I给另一台处理 机，则R=Emax{T-I,I}+C(T-I)I 据此，可得到如图7.19P198。由图可见，E/C的大小不影响 总执行时间，只影响总通讯时间。当E/C<=T/2时，所有任务分 配给一台处理机，可使总运行时间R最少；而E/C>T/2时，将任 务分配给两台处理机，可使总运行时间R最少。 2.N>2且计算与通讯不能重叠 若将IK个任务分配给第K台处理机，则 R=Emax{IK}+C/2∑IK (T-IK) 由于∑IK =T，故R=Emax{IK}+C/2(T2-∑IK2)
根据双处理机的分析，N台处理机总运行时间最短的情况， 或者是将所有任务集中分配给一台处理机上以免去通讯开销， 或者将任务尽可能平均分配给所有各处理机。 究竟采用平均分配还是集中分配，可以通过计算这两种任 务分配策略的总运行时间差来决定。经过分析，发现当E/C>T/2 时，采用平均分配；反之，则采用集中分配。 平均分配时，分析发现，当E/C>>T(N-1)/2时，并行系统的 加速比Sp可接近N。即当任务数T及处理机数N均较少而E/C又较 大时，并行系统的加速比随处理机机数N的增加而接近线性地提 高。但当N增大到较大时，Sp就趋近于2E/(CT)，只与E/C及任务 数T有关，而与机数N基本无关。 3.额外开销与计算工作可以重叠 当ET/N>=CT2(1-1/N)/2时，辅助开销将被完全覆盖。如果N 值很大，让总运行时间最少时，有N<=2E/(CT)，即选择的最佳 机数与可提供的任务数T成反比。
第7章 多处理机
7.1 多处理机的特点及主要技术问题 7.2 多处理机的硬件结构 7.3 程序并行性 7.4 多处理机的性能 7.5 多处理机的操作系统 习题
7.1 多处理机的特点及主要技术问题
多处理机具有两台以上的处理机，在操作系统控制下通过 共享的主存或输入/输出子系统或高速通讯网络进行通讯。使用 多处理机的目的：一是用多处理机进行多任务处理协同求解一 个大而复杂的问题来提高速度；二是依靠冗余的处理机及其重 组来提高系统的可靠性、适应性和可用性。因为应用目的和结 构的不同，多处理机可以有同构型、异构型和分布型三种。 多处理机属于多指令流多数据流系统，与单指令流多数据 流系统的并行处理有很大的差别： 结构灵活性 程序并行性 并行任务派生 进程同步 资源分配和任务调度
7.2 多处理机的硬件结构
7.2.1 紧耦合和松耦合 7.2.2 机间互连形式
7.2.1 紧耦合和松耦合
1.紧耦合多处理机 紧耦合多处理机通过共享主存实现处理机之间的通讯， 其通讯速率受限于主存频宽。各处理机与主存经互连网络连 接，处理机数受限于互连网络带宽及各处理机访主存冲突的 概率。 为减少访主存冲突，主存采用模m多体交叉存取。模数m 越大，发生冲突的概率越低，但要解决好数据在各存储器模 块中的分配和定位。各处理机可以自带小容量局部存储器存 放该处理机运行进程的核心代码和常用系统表格；还可自带 cache以减少访主存次数。 图7.1P184是紧耦合多处理机的两种构形。它们的主要差 别是处理机是否带有专用cache.系统由p台处理机、m个存储 器模块和d个I/O通道组成。通过处理机-存储器互联网络 (PMIN)、I/O-处理机互联网络(IOPIN)和中断信号互联网络 (ISIN)进行互联。
ቤተ መጻሕፍቲ ባይዱ
7.3 程序并行性
7.3.1 并行算法 7.3.2 程序并行性的分析 7.3.3 并行程序设计语言
7.3.1 并行算法
多处理机低层次的并行通过向量化实现；高层次的任务和 作业的并行主要看算法、编译、语言及操作系统来开发。 算法必须适应具体的计算机结构。串行处理机上习惯采用 的循环和迭代算法往往不适合于多处理机，采用直接解法有时 反而能揭示更多的并行性。 类似于图7.12P191所示，问题运算过程可以表示成树型结 构，这样提高运算的并行性就是如何对树进行变换，减少运算 的级数，即降低树高。树型结构可以用交换率、结合率和分配 率来变换。如图7.13P192到图7.14P192的变换。 运算的级数就是树高TP；P代表所需处理机的数目；顺序 运算的级数T1与P台处理机运算的级数TP的比值为加速比SP； SP/P=EP称为效率。SP>=1时，会使EP<=1，即运算的加速总 是伴随效率的下降。
处理机-存储器互连网络实现各处理机与各存储器模块的 连接，使之经仲裁后，每个存储器模块在一个存储周期只响 应其中一台处理机的访存请求。为了减少各处理机同时访问 同一存储器模块的冲突，存储器模块数m一般等于或大于处 理机数p。每台处理机自带局部存储器的方案，可以减少访 主存信息量，降低访主存冲突概率，也可以减少处理机-存 储器互连网络的使用冲突。如果再有cache就可以进一步减 少这种冲突。 处理机间通过中断信号互连网络，由一台处理机向另一 台处理机发出中断信号来实现处理机间的进程同步。 处理机和连接外设的I/O通道，经I/O-处理机互连网络来 实现通讯。一般，多数多处理机采用非对称互联，即如图 7.2P185所示，连到一台处理机的设备不能被另一台处理机 直接访问。 紧耦合多处理机常用于并行执行作业中的多个任务，以 提高系统的速度性能。因此各处理机一般是同构形的，即系 统是多个同类型至少是功能相同的处理机组成。
多处理机存在的主要技术问题： 硬件结构上，如何解决处理机、存储器模块及I/O 子系统间的互连 如何最大限度开发系统的并行性，以实现多处理机 各级的全面并行 如何选择任务的粒度，使并行度高，辅助开销小 如何协调多处理机中各并行执行的任务和进程间的 同步 资源分配和任务调度 一旦某个处理机故障，如何对系统进行重组织 多处理机机数增多时，如何提供良好的编程环境， 减轻程序的复杂性
7.3.3 并行程序设计语言
为加强程序并行性的识别能力，有必要在程序语言 中增加能明确表示并发进程的成分，这就要使用并行 程序设计语言。 并行程序设计语言的基本要求是能使程序员在其程 序中灵活方便地表示出各类并行性，并能在各种并行/ 向量计算机系统中高效地实现。 并行进程的特点是这些进程在时间上重叠执行，一 个进程未结束，另一个进程就开始了。 包含并行性的程序在多处理机上运行时，需要有相 应的控制机构来管理，其中包括并行任务的派生和汇 合。并行任务的派生和汇合常用软件手段控制。
7.4 多处理机的性能
7.4.1 任务粒度与系统性能 7.4.2 性能模型与分析
7.4.1 任务粒度与系统性能
使用多处理机的主要目的是用多个处理机并发执行多个任 务来提高解题速度。但是，在实际解题算法中，总是会有不可 并行的部分，解题过程需花费辅助开销，用于并行检测、并行 任务的派生和汇合、处理机间的通讯传输、同步、系统控制和 调度，这使得多处理机的性能比期望的要小得多。 任务粒度的大小会显著影响多处理机的性能和效率。任务 粒度过小，辅助开销大，系统效率低；粒度过大，并行度低， 性能不会提高。因此，要合理选择任务粒度的大小，并使其尽 可能均匀，还要采取措施减少辅助开销，以保证系统性能随处 理机数目的增加能有较大的提高。 衡量任务粒度大小的一个依据就是程序用于有效计算的执 行时间E与处理机间的通讯等辅助开销时间C的比值。只要E/C 值较大，开发并行性才有好处。 此外，任务粒度还与系统的应用有关。系统设计应使其能 与应用问题的粒度取得较佳适配。
7.3.2 程序并行性的分析
任务间能否并行，除了算法以外，很大程度还取决于程序 的结构。程序中各类数据相关是限制程序并行的重要因素。数 据相关既存在于指令之间，也存在于程序段之间。 程序段之间也可能出现数据相关(类似于流水处理中的“先 写后读”相关)、数据反相关(类似于流水处理中的“先读后写” 相关)和数据输出相关(类似于流水处理中的“写-写”相关)等多 种数据相关。 一般，两个程序段之间若有数据相关，不能并行，只在特 殊情况下可以交换串行；若有数据反相关，可以并行执行，但 必须保证其写入共享主存时的先读后写次序，不能交换串行； 若有数据输出相关，可以并行执行，但同样需保证其写入的先 后次序，不能交换串行；若同时有先写后读和先读后写两种相 关，以交换数据为目的时，必须并行执行，且读写要完全同步， 不许顺序串行和交换串行；若没有任何相关或仅有源数据相同 时，可并行、顺序串行和交换串行。