计算机系统结构 第10章

《计算机系统结构 第10章》由会员分享，可在线阅读，更多相关《计算机系统结构 第10章（98页珍藏版）》请在金锄头文库上搜索。

1、1/981. 单处理机系统结构正在走向尽头？2. 多处理机正起着越来越重要的作用。近几年来，人们 确实开始转向了多处理机。 Intel于2004年宣布放弃了其高性能单处理器项目 ，转向多核（multi-core）的研究和开发。IBM、SUN、AMD等公司 并行计算机应用软件已有了稳定的发展。充分利用商品化微处理器所具有的高性能价格比 的优势。 3.本章重点：中小规模的计算机(处理器的个数32) （多处理机设计的主流）第10章 多处理机2/98FrequencyVoltagePowerAggregate BandwidthPerformance3.16 GHz0.95 V62W1.62 Tera

2、bits/s1.01 Teraflops5.1 GHz1.2 V175W2.61 Terabits/s1.63 Teraflops5.7 GHz1.35 V265W2.92 Terabits/s1.81 TeraflopsThe Teraflops Research Chip 3/9810.1 引 言Flynn分类法SISD、SIMD、MISD、MIMDMIMD已成为通用多处理机系统结构的选择，原因：MIMD具有灵活性；MIMD可以充分利用商品化微处理器在性能价格比方面的优势。计算机机群系统（cluster）是一类广泛被采用的MIMD机器。10.1.1 并行计算机系统结构的分类 4/9810.

3、1 引 言3. 根据存储器的组织结构 ，把现有的MIMD机器分为两类：（每一类代表了一种存储器的结构和互连策略）集中式共享存储器结构 q最多由几十个处理器构成。q各处理器共享一个集中式的物理存储器。 这类机器有时被称为 qSMP机器（Symmetric shared-memory MultiProcessor）qUMA机器（Uniform Memory Access） 5/9810.1 引 言对称式共享存储器多处理机的基本结构6/9810.1 引 言分布式存储器多处理机 q存储器在物理上是分布的。 q每个结点包含：n处理器n存储器nIOn互连网络接口q在许多情况下，分布式存储器结构优于集中式共

4、享存储器结构。7/9810.1 引 言8/9810.1 引 言q将存储器分布到各结点有两个优点n如果大多数的访问是针对本结点的局部存储器，则可降低对存储器和互连网络的带宽要求；n对本地存储器的访问延迟时间小。q最主要的缺点n处理器之间的通信较为复杂，且各处理器之间访问延迟较大。q簇：超级结点 n每个结点内包含个数较少（例如28）的处理器；n处理器之间可采用另一种互连技术（例如总线）相互连接形成簇。 9/9810.1 引 言两种存储器系统结构和通信机制共享地址空间 q物理上分离的所有存储器作为一个统一的共享逻辑 空间进行编址。q任何一个处理器可以访问该共享空间中的任何一个 单元（如果它具有访问权

5、），而且不同处理器上的 同一个物理地址指向的是同一个存储单元。q这类计算机被称为分布式共享存储器系统（DSM: Distributed Shared-Memory)NUMA机器 （NUMA: Non-Uniform Memory Access)10.1.2 存储器系统结构和通信机制 10/9810.1 引 言把每个结点中的存储器编址为一个独立的地址空间，不同结点中的地址空间之间是相互独立的。 q整个系统的地址空间由多个独立的地址空间构成q每个结点中的存储器只能由本地的处理器进行访问，远程的处理器不能直接对其进行访问。 q每一个处理器-存储器模块实际上是一台单独的计算机q现在的这种机器多以集群的

6、形式存在2. 通信机制 共享存储器通信机制q共享地址空间的计算机系统采用11/9810.1 引 言q处理器之间是通过用load和store指令对相同存储器地址进行读/写操作来实现的。消息传递通信机制q多个独立地址空间的计算机采用 q通过处理器间显式地传递消息来完成q消息传递多处理机中，处理器之间是通过发送消息来进行通信的，这些消息请求进行某些操作或者传送数据。 12/9810.1 引 言例如：一个处理器要对远程存储器上的数据进行访问或操作：n发送消息，请求传递数据或对数据进行操作；远程进程调用(RPC， Remote Process Call)n目的处理器接收到消息以后，执行相应的操作或代替远

7、 程处理器进行访问，并发送一个应答消息将结果返回。q同步消息传递 请求处理器发送一个消息后一直要等到应答结果才继续运行。q异步消息传递 数据发送方知道别的处理器需要数据，通信也可以从数据发送方来开始，数据可以不经请求就直接送往数据接受方。发送方在发出消息后，可立即继续执行原来的程序。 13/9810.1 引 言并行处理面临着两个重要的挑战程序中的并行性有限远程访问延迟10.1.3 并行处理面临的挑战 系统加速比 =14/9810.1 引 言第一个挑战有限的并行性使计算机要达到很高的加速比十分困难。 例10.1 假设想用100个处理器达到80的加速比，求原计算程序中串行部分最多可占多大的比例？解

8、 Amdahl定律为：由上式可得：并行比例0.9975 15/9810.1 引 言2. 第二个挑战：多处理机中远程访问的延迟较大在现有的机器中，处理器之间的数据通信大约需要501000个时钟周期。主要取决于：通信机制、互连网络的种类和多处理机的规模 16/9810.1 引 言例10.2 假设有一台32台处理器的多处理机，对远程存储器访问时间为200ns。除了通信以外，假设所有其它访问均命中局部存储器。当发出一个远程请求时，本处理器挂起。处理器的时钟频率为2GHz，如果指令基本的CPI为0.5（设所有访存均命中Cache），求在没有远程访问的情况下和有0.2%的指令需要远程访问的情况下，前者比后

9、者快多少?17/9810.1 引 言解 有0.2%远程访问的机器的实际CPI为：CPI基本CPI远程访问率远程访问开销0.50.2%远程访问开销远程访问开销为：远程访问时间/时钟周期时间200ns/0.5ns400个时钟周期 CPI0.50.2%4001.3因此在没有远程访问的情况下的机器速度是有0.2%远程访问的机器速度的1.3/0.5=2.6倍。18/9810.1 引 言问题的解决q并行性不足： 采用并行性更好的算法q远程访问延迟的降低：靠系统结构支持和编程技术 3. 并行程序的计算通信比率反映并行程序性能的一个重要的度量：计算与通信的比率计算通信比率随着处理数据规模的增大而增加；随着处理

10、器数目的增加而减少。19/98多个处理器通过共享总线共享一个存储器大容量、多级Cache降低了对内存带宽和总线带宽的要 求 2005，AMD sends invalidate and generates write-back from P2. 8环绕测试 是否lock=0 无3个处理器利用原子交换争用旋转锁所进行的操作 74/9875/9810.4 同 步LLSC原语的另一个优点：读写操作明显分开LL不产生总线数据传送，这使下面代码与 使用经过优化交换的代码具有相同的特点：lockit：LLR2, 0（R1）BNEZR2, lockitDADDIU R2, R0, #1SCR2, 0（R1）B

11、EQZR2, lockit第一个分支形成环绕的循环体，第二个分支解决了两个处理器同时看到锁可用的情况下的争用问题。76/9810.4 同 步简单旋转锁不能很好地适应可缩扩性。大规模多处理机中，若所有的处理器都同时争用同一个锁，则会导致大量的争用和通信开销。 10.4.3 同步性能问题77/9810.4 同 步例10.3 假设某条总线上有10个处理器同时准备对同一变量加锁。如果每个总线事务处理（读不命中或写不命中）的时间是100个时钟周期，而且忽略对已调入Cache中的锁进行读写的时间以及占用该锁的时间。（1）假设该锁在时间为0时被释放，并且所有处理器都在旋转等待该锁。问：所有10个处理器都获得

12、该锁所需的总线事务数目是多少？（2）假设总线是非常公平的，在处理新请求之前，要先全部处理好已有的请求。并且各处理器的速度相同。问：处理10个请求大概需要多少时间？78/9810.4 同 步解：此题应根据由LL/SC指令实现的旋转锁工作过程分析。解法可以从推导任意n个处理器的公式入手。开始时，有n个处理器竞争，n个Cache中都没有锁的复件，所以它们的 LL操作会导致n个读失效，产生n个读主存的总线事务，分别将锁变量调入 n个Cache；接着，n个处理器执行SC操作，试图上锁(try to lock the lock)动作最快 的1个处理机抢先完成了SC操作，它把主存中的锁原件“加锁”了，通知其

13、 余n-1个Cache复件作废，这样其余n-1个SC操作都发生写失效，需要用1个 写主存的总线事务写回，以及n-1个读主存的总线事务重新调入Cache（“按 写分配”策略，因为随后还要多次读Cache），合计n个总线事务；在“加锁”成功的那个处理机对临界资源使用期间，其余n-1个处理器只 是循环对各自的Cache做LL读，并无总线事务发生。最后成功者需要“开锁 ”，再次通知其余n-1个Cache复件作废，接着又用了1个写主存的总线事务写回。79/98这样总共有2n+1个总线事务；由于收到通知的n-1个Cache复件作废，对应n-1个处理器的LL操作立即 产生读失效，又重演刚才n个处理器竞争的过

14、程，只是参与者下降到n-1个 ，.。依此类推，当最后1个处理器将锁释放后，前后发生的总线事务次数共有本题中n=10，总线事务数共有120个，每个总线事务花费100个时钟 周期，合计需要12000个时钟周期。80/9810.4 同 步本例中问题的根源：锁的争用、对锁进行访问的串行性以及总线访问的延迟。旋转锁的主要优点：总线开销或网络开销比较低，而且当一个锁被同一个处理器重用时具有很好的性能。 81/98如何用旋转锁来实现一个常用的高级同步原语：栅栏栅栏强制所有到达该栅栏的进程进行等待，直到全部的进程到达栅栏，然后释放全部的进程，从而形成同步。 栅栏的典型实现用两个旋转锁：q用来保护一个计数器，它

15、记录已到达该栅栏的进程数；q用来封锁进程直至最后一个进程到达该栅栏。 82/9810.4 同 步一种典型的实现qlock和unlock提供基本的旋转锁q变量count记录已到达栅栏的进程数qtotal规定了要到达栅栏的进程总数 83/9810.4 同 步q对counterlock加锁保证增量操作的原子性。 qrelease用来封锁进程直到最后一个进程到达栅栏。qspin（release=1）使进程等待直到全部的进程到达 栅栏。 实际情况中会出现的问题栅栏通常是在循环中使用，从栅栏释放的进程运行一段后又会再次返回栅栏，这样有可能出现某个进程永远离不开栅栏的状况(它停在旋转操作上)。because

16、 one process is trapped at the last instance。84/9810.4 同 步q一种解决方法当进程离开栅栏时进行计数（和到达时一样），在 上次栅栏使用中的所有进程离开之前，不允许任何进程 重用并初始化本栅栏。但这会明显增加栅栏的延迟和竞 争。q另一种解决办法n采用sense_reversing栅栏，每个进程均使用一个私有变量local_sense，该变量初始化为1。85/9810.4 同 步Figure I.3 Code for a sense-reversing barrier. The key to making the barrier reusable is the use of an alternating pattern of values for the flag release, which controls the exit from the barrier86/98例10.4（教材2