第八章 多处理机.docx

第 8 章 多处理机8.1 解释以下术语 集中式共享多处理机：也称为对称式共享存储器多处理SMP它一般由几十个处理器构成, 各处理器共享一个集中式的物理存储器，这个主存相对于各处理器的关系是对称的，分布式共享多处理机：它的共享存储器分布在各台处理机中,每台处理机都带有自己的本地 存储器,组成一个“处理机-存储器”单元但是这些分布在各台处理机中的实际存储器又 合在一起统一编址, 在逻辑上组成一个共享存储器这些处理机存储器单元通过互连网络 连接在一起 ,每台处理机除了能访问本地存储器外,还能通过互连网络直接访问在其他处 理机存储器单元中的 “远程存储器”通信延迟：通信延迟二发送开销+跨越时间+传输时间+接收开销计算/通信比：反映并行程序性能的一个重要的度量在并行计算中,每次数据通信要进行 的计算与通信开销的比值多Cache 一致性：多处理机中，当共享数据进入Cache，就可能出现多个处理器的Cache中 都有同一存储器块的副本,要保证多个副本数据是一致的监听协议：每个 Cache 除了包含物理存储器中块的数据拷贝之外，也保存着各个块的共享状 态信息Cache通常连在共享存储器的总线上，各个Cache控制器通过监听总线来判断它们 是否有总线上请求的数据块。

目录协议：用一种专用的存储器所记录的数据结构它记录着可以进入Cache的每个数据块 的访问状态、该块在各个处理器的共享状态以及是否修改过等信息写作废协议：在处理器对某个数据项进行写入之前，它拥有对该数据项的唯一的访问权写更新协议：当一个处理器对某数据项进行写入时，它把该新数据广播给所有其它Cache 这些Cache用该新数据对其中的副本进行更新栅栏同步：栅栏强制所有到达该栅栏的进程进行等待直到全部的进程到达栅栏，然后释放 全部进程，从而形成同步旋转锁：处理机环绕一个锁不停地旋转而请求获得该锁同时多线程：是一种在多流出、动态调度的处理器上同时开发线程级并行和指令级并行的技 术，它是多线程技术的一种改进细粒度多线程技术：是一种实现多线程的技术它在每条指令之间都能进行线程的切换，从 而使得多个线程可以交替执行通常以时间片轮转的方法实现这样的交替执行，在轮转的过 程中跳过处于停顿的线程粗粒度多线程技术：是一种实现多线程的技术只有线程发生较长时间的停顿时才切换到其 他线程SMP :对称式共享存储器多处理MPP :即大规模并行处理，按照当前的标准，具有几百台〜几千台处理机的任何机器都是 大规模并行处理系统。

8.2 一个具有32台处理机的系统，对远程存储器访问时间是2000ns除了通信以外， 假设计算中的访问均命中局部存储器当发出一个远程请求时，本地处理机挂起处理机的 时钟周期时间是10ns,假设指令基本的CPI为1.0 （设所有访存均命中Cache）对于下述两 种情况:（ 1） 没有远程访问；（2） 0.5%的指令需要远程访问试问前者比后者快多少？解：已知远程访问率p = 0.5%，远程访问时间t = 2000ns，时钟周期T = 10ns 远程访问开销 C = t/T = 2000ns/10ns = 200（时钟周期数） 有0.5%远程访问的机器的实际CPI2为：CPI2 = CPI] + pXC = 1.0 + 0.5% X 200 = 2.0只有局部访问的机器的基本 CPI1= 1.0CPI2/ CPI1 = 2.0/1.0 = 2（倍） 因此，没有远程访问状态下的机器速度是有0.5% 远程访问的机器速度的2 倍8.3 什么是多处理机的一致性？给出解决一致性的监听协议和目录协议的工作原理 答：（1）对多个处理器维护一致性的协议称为Cache 一致性协议2） 目录协议的工作原理：采用一个集中的数据结构——目录。

对于存储器中的每一 个可以调入Cache的数据块，在目录中设置一条目录项，用于记录该块的状态以及哪些Cache 中有副本等相关信息目录协议根据该项目中的信息以及当前要进行的访问操作，依次对相 应的Cache发送控制消息，并完成对目录项信息的修改此外，还要向请求处理器发送响应 信息3） 监听协议的工作原理：每个Cache除了包含物理存储器中块的数据拷贝之外，也 保存着各个块的共享状态信息Cache通常连在共享存储器的总线上，当某个Cache需要访 问存储器时，它会把请求放到总线上广播出去，其他各个Cache控制器通过监听总线来判断 它们是否有总线上请求的数据块如果有，就进行相应的操作8.4在标准的栅栏同步中，设单个处理器的通过时间（包括更新计数和释放锁）为C， 求 N 个处理器一起进行一次同步所需要的时间解：我们忽略读写锁的时间N个处理器中的每一个都需要C个时钟周期来锁住与栅 栏相关的计数器，修改它的值，然后释放锁考虑最坏情况，所有N个处理器都要对计数 器加锁并修改它的值，由于锁只能顺序访问计数器，在同一时间，只能有一个处理器修改计 数器的数据所以，总共要花NC个时钟周期使得所有的处理器都到达数据栅栏。

8.6采用排队锁和fetch-and-increment重新实现栅栏同步，并将它们分别与采用旋转锁 实现的栅栏同步进行性能比较解：fetch-and-increment(count)；〃□进程全部到达口〃□重置计数器〃□释放进程〃□还有进程未到达〃□等待信号口if (count=total){ count=0；release=1；}else{spin(release=1) ；}当有N个处理器时，上述代码执行fetch-and-increment操作N次，当访问释放操作的时 候，有N个Cache未命中当最后一个处理器到达栅栏条件后，release被置为“1”此时 有N-1个Cache未命中（对于最后一个到达栅栏的处理器，当它读release的时候，将在主 存中命中）所以，共有3N-1次总线传输操作如果有10个处理器，则共有29次总线传 输操作，总共需要2900个时钟周期8.7 有些机器实现了专门的锁广播一致性协议，实现上可能使用不同的总线假设使用 写广播协议，重新给出例8.3旋转锁的时间计算解：当实现了专门的锁广播一致性协议后，每当一把锁被释放的时候，和锁相关的值将 被广播到所有处理器，这意味着在处理器对锁变量进行读操作的时候，未命中的情况永远不 会发生。

假定每个Cache都有一个数据块保留锁变量的初值通过下表可以知道，10次上锁/释 放锁的平均时间是550个时钟周期，总时间是5500个时钟周期事件持续时间所有处理器都读（命中）锁0释放锁的处理器进行写（不命中）广播100读（命中）锁（处理器认为锁是空闲的）0一个处理器进行写交换广播，同时还有9个写广播1000一个处理器得到并释放锁的总时间1100。