8.4.3 DMA 方式
第 3 版 · OCR 辅助 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照
<!-- page: 329 -->
计算机组成与系统结构(第3版)
312
9.假定某计算机字长16位，没有 cache,运算器一次定点加法时间等于100ns,配置的磁盘旋转速度为
每分钟3000转，每个磁道上记录两个数据块，每一块有8000字节，两个数据块之间间隙的越过时间为
2ms,主存存储周期为500ns,存储器总线宽度为16位，总线带宽为4MB/s。
(1)磁盘读写数据时的最大数据传输率是多少?
(2)当磁盘按最大数据传输率与主机交换数据时，主存存储周期空闲百分比是多少?
(3)直接寻址的“存储器-存储器”SS型加法指令在无磁盘I/O操作打扰时的执行时间为多少?当磁
盘I/O操作与一连串这种SS型加法指令执行同时进行时，则这种SS型加法指令的最快和最慢执行时间
各是多少?(假定采用多周期处理器方式，CPU时钟周期等于主存存储周期。)
10.假定某计算机所有指令都可用两个总线周期完成，一个总线周期用来取指令，另一个总线周期用
来存取数据。总线周期为250ns,因而每条指令的执行时间为500ns。若该计算机中配置的磁盘上每个磁
道有16个512字节的扇区，磁盘旋转一圈的时间是8.192ms,则采用周期挪用法进行DMA传送时，总线
宽度为8位和16位的情况下该计算机指令执行速度分别降低了百分之几?
11.假设一个主频为1GHz的处理器需要从某个成块传送的I/O设备读取1000字节的数据到主存缓
冲区中，该I/O设备一旦启动即按50KB/s的数据传输率向主机传送1000字节的数据，每字节的读取、处
理并存入内存缓冲区总计需要1000个时钟周期，则以下几种方式下，在1000字节的读取过程中，CPU花
在该设备的I/O操作上的时间分别为多少?占整个处理器时间的百分比分别是多少?
(1)采用定时查询方式，每次处理一字节，一次状态查询至少需要60个时钟周期。
(2)采用独占查询方式，每次处理一字节，一次状态查询至少需要60个时钟周期。
(3)采用中断I/O方式，外设每准备好一字节发送一次中断请求。每次中断响应需要2个时钟周期，
中断服务程序的执行需要1200个时钟周期。
(4)采用周期挪用DMA方式，每挪用一次存储周期处理一字节，一次 DMA传送完成1000字节数据
的I/O,DMA初始化和后处理的时间为2000个时钟周期，CPU和DMA控制器没有访存冲突。
(5)如果设备的速度提高到5MB/s,则上述4种方式中，哪些是不可行的?为什么?对于可行的方式，
计算出 CPU 花在该设备1/O操作上的时间占整个处理器时间的百分比。
(6)如果外设不是成块传送设备，而是字符型设备，CPU每处理完一字节后都要重新启动外设，外设
在启动后的0.02ms时准备好一字节。每一字节的读取、处理(包括启动下次操作)并存人内存缓冲区还是
1000个时钟周期，假定CPU总是在查询到就绪后立即启动外设或在中断服务程序的最开始立即启动外
设，则在(1)～(3)3种方式下，CPU花在该设备的I/O操作上的时间占整个处理器时间的百分比分别是
多少?
12.假定采用中断控制I/O方式，则以下各项工作是在4个1/O软件层的哪一层完成的?
(1)根据逻辑块号计算磁盘物理地址(柱面号、磁头号、扇区号)。
(2)检查用户是否有权读写文件。
(3)将二进制整数转换为ASCII码以便打印输出。
(4)CPU向设备控制器写入控制命令(如“启动工作”命令)。
(5)CPU从设备控制器的数据端口读取数据。
<!-- page: 330 -->
第
章
并行处理系统
随着信息技术的飞速发展，人们对计算机系统处理能力的要求越来越高。气象、生物、
医药、地质、天文等领域的高性能计算，互联网以及移动通信应用领域的海量“大数据“处理，
银行、保险、证券等大型数据库系统开发，游戏、航空模拟等各种媒体处理软件方面的开发，
都需要计算机系统具有极其快速的处理能力。采用传统的单处理器系统中的串行计算方
式，远远不能满足现代社会实际应用问题对计算能力的需求。
为了追求更高的计算性能，出现了各种不同的并行处理系统。通过采用对多个功能部
件或多个处理核或多个CPU或多台计算机的互连，使得一个系统中可同时进行多条指令
或多个数据或多个线程或多个任务的处理，从而实现计算速度和计算能力的大幅提升。本
章主要介绍几类典型并行处理计算系统的基本硬件结构，并简要介绍几种并行程序设计编
程模型。
9.1并行处理系统概述
为了获得更高的计算速度，通常采用大规模并行处理技术。采用这种技术的计算系统，
相比于单处理器计算系统，是非常复杂的。它涉及互连、数据一致性、同步控制、计算任务划
分、并行程序设计和容错等很多问题。
9.1.1并行处理的主要技术问题
根据所采用的硬件体系结构的不同，每种并行处理计算系统所涉及的主要技术问题有
所不同，但概括起来，主要包括以下几方面。
1.互连
并行处理最主要的特点就是将多个计算模块和多个存储模块进行互连，通过控制这些
模块的并行工作来提高处理速度。因此，如何实现这些模块的互连是非常重要的问题。互
连技术包括芯片内模块互连、芯片间模块互连和节点间机-机互连等。典型的互连结构包括
共享总线连接、交叉开关矩阵、交换网络、环形结构、星形结构、网格(mesh)、立方体(cube)
和超立方体(hypercube)等。
2.数据一致性
在并行处理系统中，为了加快数据处理的速度，通常利用程序访问的局部性特性，在不
<!-- page: 331 -->
计算机组成与系统结构(第3版)
314
同的计算模块中设置高速缓存，而且，这些不同的计算模块还可能设置共享的高速缓存和共
享的主存储器，因此，在并行处理系统中存在复杂的数据一致性问题。
3.同步控制
在并行处理系统中，或者多个计算模块共享一个存储模块，或者每个计算模块拥有自己
的存储模块。前者为共享存储器结构，后者为分布式存储器结构。在共享存储器结构系统
中，由于多个计算模块可能同时访问同一块数据，因而需要解决数据的互斥访问等同步控制
问题。在分布式存储器结构系统中，一个计算任务可能分解为若干子任务，被分配到多个计
算模块完成，而每个计算模块的速度和每个子任务计算量可能不同，从而导致子任务在完成
时间上有先有后，因此，需要对各个计算模块进行同步控制。
4.任务划分
引入并行处理系统的目的，就是把一个大的计算任务分解成小的子任务，使若干子任务
在系统中并行执行，从而加快处理速度。因此，如何对任务进行合理划分是并行处理中的一
个重要问题。通常，从算法分解和数据划分两方面来考虑。
5.并行程序设计
计算机完成的所有任务都必须编写成程序才能交给计算机执行，为了充分利用并行处
理计算系统中的计算资源和存储资源，需要对系统中运行的程序进行并行化处理的描述，以
说明哪些处理逻辑段可以并行执行，哪些处理逻辑段之间有先后顺序关系，以及处理的数据
可以怎样划分等。
不同硬件体系结构的并行处理系统，所采用的并行程序设计方法不一样。目前主要包
括共享内存式(多线程并行)、消息传递式以及MapReduce等并行处理模式。所采用的并行
程序设计方式包括在编程语言中增加编译指导指令(如OpenMP提供了C、C++、FORTRAN
语言中的编译指导语句或命令，用以指示哪个程序段可以并行执行),提供并行计算库函数
和编程接口(如Pthread、MPI和 CUDA等)以及提供自动化处理能力的并行计算软件框架
(如 Hadoop MapReduce,Spark 并行编程框架等)。
6.资源调度和管理
不管采用哪种并行处理模式和哪种并行程序设计方式，最终都要将反映处理逻辑的机
器代码调度到不同的计算模块中执行，将处理逻辑所操作的数据部署到存储模块中，这就涉
及并行处理系统中计算资源的调度和存储资源的管理问题，这将比在串行处理系统中复杂
得多。
7.容错性和安全性
大规模并行处理系统依靠大量的计算节点互连而成，因而可能经常发生节点出错或失
效，因此，需要预防由于单个节点失效可能带来的数据丢失、程序出错或系统崩溃等问题。
这就要求系统必须考虑良好的可靠性设计以及失效检测和恢复机制。
8.性能分析与评估
并行处理性能通常用加速比来度量，加速比可以是一个作业在串行系统中的执行时间
与并行处理计算系统中的执行时间的比值，也可以是并行处理系统的作业吞吐量与串行系
统的作业吞吐量的比值。当然，评价一个并行处理系统的好坏，应该有很多指标，包括可用
性、可扩展性、负载均衡、可靠性等。
由于并行处理系统在硬件架构、软件架构以及所处理的应用问题等各方面的多样性和
<!-- page: 332 -->
并行处理系统
复杂性，使得并行处理各个技术问题的解决都面临着很大的挑战。
9.1.2并行处理系统的分类
并行处理系统面临各种技术问题的挑战，为此，人们提出了各种并行处理解决方案，针
对这些解决方案，又有不同的并行处理技术分类，包括按指令和数据的处理方式划分、按地
址空间访问方式划分、按存储访问时间是否一致划分、按处理单元的位置及其互连方式划分
等不同的分类方式。
1.Flynn 分类
1966年，美国斯坦福大学的 Michael J.Flynn 教授提出了按照指令和数据的处理方式
进行划分的 Flynn分类法，将计算机体系结构分成以下4种。
1)单指令流单数据流(SISD)结构
SISD(single-instruction stream and single-data stream)是传统的串行计算机处理方
式，这种计算机通常仅包含一个处理器和一个存储器，处理器在一段时间内仅执行一条指令
流，按指令流规定的顺序串行完成指令流中若干条指令的执行，并且每条指令最多仅对两个
数据(双目运算)或一个数据(单目运算)进行处理。为了提高程序执行速度，有些 SISD计
算机采用各种指令流水线或运算操作流水线方式执行指令，因此，SISD计算机的处理器中
有时会设置多个功能部件，而且采用多模块交叉方式组织存储器。本书前8章介绍的内容
多属于 SISD计算机结构。
2)单指令流多数据流(SIMD)结构
SIMD(single-instruction stream and multiple-data stream)指一个指令流同时对多个
数据流进行处理，这种结构的计算机通常由一个指令控制部件、多个处理单元和多个存储器
组成。各处理单元和各存储器之间通过系统内部的互连网络进行通信。在程序执行过程
中，指令控制部件执行的还是一个串行的指令流，所有处于执行状态的处理单元同时执行相
同的指令，所需的数据从连接在各个处理单元上专用的局部存储器中取得，因此，不同处理
单元执行的同一条指令所处理的数据是不同的。
随着计算机应用技术的不断发展，在20世纪90年代初，出现了多媒体应用技术，图形、
图像、视频和音频处理存在大量具有共同特征的操作，因而Intel公司于1997年在多能奔腾
处理器中推出了MMX(multi media extension,多媒体扩展)指令集，它是Intel公司产品中
最早采用的 SIMD技术。随着网络、通信、语音、图形、图像、动画和音/视频等多媒体处理软
件对处理器性能的要求越来越高，Intel 公司在多能奔腾以后的处理器中加入了更多流式
SIMD扩展(stream SIMD extension,SSE)指令集，包括 SSE、SSE2、SSE3、SSSE3、SSE4 以
及AVX(advanced vector extensions)等，这些都是典型的数据级并行处理技术。
3)多指令流单数据流(MISD)结构
MISD(multiple-instruction stream and single-data stream)指在同一时刻有多个指令
在执行，并且处理的是同一个数据。这种方式实际上很少出现，仅作为一种理论模型提出，
现实中这种工作方式的计算机根本不存在。
4)多指令流多数据流(MIMD)结构
MIMD(multiple-instruction stream and multiple-data stream)指同时有多个指令分别
处理多个不同的数据。这种系统中一定包含有多个计算机或多个处理器。MIMD方式是
第9章
315
<!-- page: 333 -->
计算机组成与系统结构(第3版)
316
目前大多数并行处理计算系统的处理方式。
根据Flynn分类法，并行处理计算系统有 SIMD和 MIMD两种并行计算模式，其中，
SIMD是一种数据级并行模式，而MIMD是一种并行程度更高的线程级并行或线程级以上
的并行计算模式。
2.按地址空间的访问方式划分
采用 MIMD计算模式的系统中一定包含多个计算机或多个处理器。为了区分不同的
并行处理计算结构，有人提出从主存地址空间的访问方式上来区分多计算机(multicomputers)
系统和多处理器(multiprocessor)系统。
1)多计算机系统
多计算机系统指具有多个私有地址空间的并行处理系统，因此，多计算机系统中每个计
算节点都具有各自私有的存储器，并各自具有独立的主存地址空间，因此，这种并行处理系
统采用的是一种分布式存储器访问方式。显然，在这种多计算机系统中，某一个计算节点无
法通过执行load指令和store指令来访问另一个节点的私有存储器，而是通过消息传递方
式进行数据传送，因此，也称为消息传递系统。
2)多处理器系统
多处理器系统是共享存储多处理器(shared memory multiprocessor,SMP)系统的简
称，它是一种具有共享的单一地址空间的并行处理系统。因此，在多处理器系统中，每个处
理器都可以通过load指令和store指令访问系统中的存储器，不管这些存储器是连接在一
条总线上的共享存储器，还是连接在某个处理器上的本地存储器，这类系统也被称为共享存
储系统。
3.按存储访问时间是否一致划分
对于多处理器系统，可以按照存储访问时间是否一致分为一致性内存访问(UMA)和非
一致性内存访问(NUMA)两类。
1)一致性内存访问(UMA)结构
UMA(uniform memory access)结构指每个处理器对所有存储单元的访问时间是一致
的。如果所有处理器都共享一个存储器，那么,每个处理器通过load指令和store指令访问
任何一个存储单元，其访问时间是相同的。它是一种普遍使用的并行处理计算机结构。
2)非一致性内存访问(NUMA)结构
NUMA(non-uniform memory access)结构指处理器对不同的存储单元的访问时间可
能不一致，访问时间与存储单元的位置有关，若是本地存储器访问时间就短，若是其他处理
器所连接的存储器则访问时间就长。如果在 NUMA结构中引入高速缓存一致性确认机
制，则称为高速缓存一致的非一致性内存访问(cache coherent NUMA,CC-NUMA)。
4.按处理单元的位置及其互连方式划分
按处理单元的位置及其互连方式来分，可以分为多核(multi-core)、众核(many-core)、
对称多处理器(SMP)、大规模并行处理机(MMP)、集群、网格等。
1)多核芯片
在一个CPU芯片中包含多个处理单元，每个处理单元称为一个核(core),所有核可能
共享一个 LLC(last-level cache),并共享主存储器。通常将多核芯片称为片级多处理器
(chip-level multiprocessing,CMP)。通常多核 CPU芯片的核数为2、4、8等几种。
<!-- page: 334 -->
并行处理系统
2)众核芯片
在一个面向三维图形、视频和可视化处理的GPU(graphics processing unit)芯片中，包
含多达几百甚至上千个简单核，众核 GPU 芯片的设计着力于在众多的简单核上有效地执
行众多的并行线程，并在线程组之间对数据的并行处理进行优化。
3)对称多处理器
所谓对称多处理器 SMP(symmetric multiprocessor),是指将多个相同类型的 CPU 通
过总线互连，并等同地位地共享系统所有资源，即多个 CPU对称工作，无主次或从属关系。
因为各CPU共享相同的物理内存，每个 CPU访问内存中的任何地址所需时间是相同的，
因此，对称多处理器就是一种UMA结构多处理器。多核处理器系统、高档微机、工作站或
服务器多用 SMP结构。
4)大规模并行处理机
MPP(massive parallel processing)是指以专用内联网络连接数量众多处理单元而构成
的一种并行计算系统。例如，可以通过专用互连网络(如 mesh、交叉开关)将数量达几百甚
至几千个的对称多处理器(SMP)连接成大规模并行处理机，众多SMP服务器协同工作，完
成相同的任务，因此从用户的角度来看是一个服务器系统，每个SMP服务器称节点，每个
节点只能直接访问自己的本地资源(内存、磁盘等)。大多数 MPP是消息传递系统，共享存
储 MPP系统的典型代表是20世纪90年代风靡全球的 SGI Origin 2000,但与同期的消息
传递 MPP系统相比，由于其硬件的复杂性，其可伸缩性相对有限。
5)集群
集群(cluster)指通过高性能网卡将若干普通 PC或 SMP服务器或工作站连接而成的
并行处理系统。集群中的每个计算节点(PC、SMP或工作站)都有各自的内存储器和磁盘，
主存地址空间都是计算节点各自私有的，因此，集群是一种典型的紧密耦合的同构多计算机
系统。显然，集群属于消息传递系统。
6)网格
网格(grid)是指用因特网等广域网络连接起来的远距离分布的一组异构计算机系统构
成的分布式并行处理系统。它是一种松散耦合的异构多计算机系统。云计算(cloud
computing)服务器就是由网格发展而来的。
9.2多处理器系统
多处理器系统是共享存储多处理器系统的简称，它是一种具有共享的单一地址空间的
并行处理系统。因此，在多处理器系统中，每个处理器都访问一个全局的主存储器，因而每
个处理器在执行指令时所产生的物理地址都属于同一个物理地址空间。
采用单地址空间的多处理器系统中，每个处理器可以通过load和 store 指令访问共享
存储器，处理器之间通过共享内存变量进行通信，因而，可能会同时有多个处理器访问同一
个共享变量，所以需要处理器之间进行相互协调，即需要进行同步控制。如果没有同步控制
机制，很可能一个处理器还没有完成对一个共享内存变量的修改时就被另一个处理器打断
而修改了该共享变量的值。常用的同步机制是通过对共享变量加锁的方式来控制处理器对
共享变量互斥访问。
第9章
317
<!-- page: 335 -->
计算机组成与系统结构(第3版)
318
多处理器系统的硬件结构有以下3种：一致性内存访问(UMA)、非一致性内存访问
(NUMA)和高速缓存一致的非一致性内存访问(CC-NUMA)。
9.2.1UMA多处理器结构
UMA多处理器系统中，每个处理器对所有存储单元的访问时间是一致的，即每个处理
器通过load和store指令访问共享存储器时，其访问时间与处理器和存储器的相对位置没
有关系。因此，UMA多处理器就是对称多处理器(SMP)。根据处理器与共享存储器之间
的连接方式，分为基于总线、基于交叉开关网络和基于多级交换网络连接等几种UMA多处
理器系统。
1.基于总线连接的UMA多处理器系统
基于总线的 UMA多处理器系统通过总线将多个相同类型的处理器互连，并共享同一
个存储器，其互连结构如图9.1所示。
CPU
CPU
共享
存储器
MM
高速
缓存
CPU
CPU
MM
私有
存储器
CPU
CPU
共享
存储器
MM
总线
(a)没有高速缓存
总线
总线
(b)有高速缓存
(c)有高速缓存和私有存储器
图9.1 基于总线互连的UMA多处理器系统
图 9.1(a)是CPU中不带高速缓存(cache)的 UMA多处理器系统，多个 CPU 模块通过
总线与一个共享存储器相连。当某个CPU需要访问主存时，它首先检查总线是否忙。如
果检测到总线忙，则等待，直到总线空闲；否则，该 CPU通过总线与主存进行一次数据交
换。显然，在这种方式下，当CPU只是少数几个时问题不是很大，但是其扩展性较差，当
CPU个数很多时，就会经常发生多个CPU访问主存冲突的问题，使得在很多时间内，大多
数 CPU 都会因为总线忙而处于等待状态，导致 CPU 利用率极其低下。
图9.1(a)中的 CPU 利用率低下问题的解决方案是在 CPU中加入高速缓存，其硬件结
构如图9.1(b)所示。在每个CPU模块中添加了高速缓存后，由于程序访问的局部性特点，
使得CPU需要的信息大多可以在内部的高速缓存中访问到，因此总线就不会太繁忙，所以
可以在总线上连接更多的 CPU 模块。
在 CPU中添加高速缓存，在解决CPU 利用率低下的同时，也会带来新的问题，那就是
cache一致性问题。因为每个CPU内的高速缓存中存放的是共享主存中的信息的副本，主
存中的一个主存块有可能同时在多个CPU的高速缓存中，如果某个 CPU修改了存放在本
地高速缓存中的一个副本中的内容，那么就会发生与其他CPU中的副本以及主存中的副
本不一致的情况，从而导致程序执行结果出错，这种现象称为 cache一致性(cache
coherency)问题。
为了解决 cache一致性问题，需要有专门的cache一致性协议。最流行的协议称为监听
协议(snooping cache coherency),其基本思想是：所有的高速缓存控制器都会监视或侦听
总线，以便确认本地是否存在其他CPU内高速缓存中的相同副本。对于读操作来说，多个
<!-- page: 336 -->
并行处理系统
相同副本不会产生问题；对于写操作来说，则必须互斥访问，并更新其他副本。因此，在写操
作发生时，监听协议必须能对所有其他副本设置为无效，或者用刚写入的数据对所有其他副
本进行更新，前者称为写无效(write invalidate)方式，后者称为写更新(write update)方式。
在Pentium 4和其他Intel公司的许多处理器中都用到一个称为MESI的协议，它采用的就
是写无效方式。
还有一种总线连接共享存储器的UMA多处理机采用图9.1(c)所示的方式，每个 CPU
模块除了有高速缓存外，还连接了一个本地的私有存储器，它通过专门的私有总线和CPU
相连。在这种结构的多处理器系统中，共享的主存储器只用来存放可写的共享变量，而将所
有程序的代码、各种非共享的常量和变量、只读数据以及栈内信息等都存入本地私有存储器
中。在大多数情况下，这种设计方式会使得总线繁忙程度比图9.1(b)所示的设计方式更
低，从而可以在总线上连接更多的CPU模块。不过，在这种方式下，因为涉及可执行文件
生成时如何分配程序代码和数据的存储地址空间问题，所以需要编译器、链接器和操作系统
等各种系统软件的功能进行相应的调整。
2.基于交叉开关网络的UMA多处理器系统
在基于总线连接的方式中，因为所有CPU都通过单一的总线访问共享存储器，很容易
造成总线繁忙，即使使用高速缓存和私有存储器，也会限制所连接的 CPU模块的数量，最
多只能连接16～32个。要连接更多的 CPU,应使用其他互连方式。连接m个 CPU 模块
到n个存储器模块的最简单电路是交叉开关连接网路，它允许任何连接在一组进线上的
CPU模块通过网络上的交叉开关连接到任何出线上的存储器模块。图9.2所示的是一个8
×8的交叉开关连接方式。
二一
开关打开
CPU
000
中4
,f
。界
开关闭合
ò
4
甲
I
图9.2 8×8的交叉开关连接方式
在图9.2 所示的交叉开关连接多处理器系统中，水平线(进线)和垂直线(出线)的每个
交叉点是一个电子开关，其开闭状态取决于进线和出线是否需要相连。每个 CPU 模块可
以根据需要选择和哪个存储器模块连接。图9.2所示的连接状态是CPU模块1连接到存
储模块2,CPU模块2连接到存储模块1,CPU模块4连接到存储模块4,CPU模块5连接
到存储模块6,CPU模块7连接到存储模块7。CPU和存储器的相连状态可以根据需要
改变。
使用交叉开关互连，使得不同的 CPU可以方便地连接到不同的存储器，因而大大降低
了多个 CPU同时访问一个存储器的访问冲突，从而降低了CPU的等待时间，提高了 CPU
第9章
319
<!-- page: 337 -->
计算机组成与系统结构(第3版)
320
的利用率。不过，因为交叉开关的数量为m×n,所以，在CPU和存储器模块的个数很大的
情况下，交叉开关的数量急剧上升，因此，不可能用交叉开关的方式构建大规模系统。
3.基于多级交换网络的UMA 多处理器系统
为了减少连接网络的硬件，可以采用一种基于2×2交叉开关的多级交换网络连接方式。
Omega交换网络是一种简单经济的多级交换网络。图9.3是Omega交换网络连接示意图。
A-
B-
<
-X
-Y
(a)2×2交叉开关
M
A
R/W V
(b)消息格式
CPU
000
001
010
011
100
101
110
X
y
1A
IB
1C
y
1D
2A
2B}
X
2C
2D
y
X
(c) Omega交换网络
图9.3 Omega交换网络连接方式
3A
3B
3C
3D
y~
X
存储器
000
001
010
011
100
101
110
图9.3(a)是一个2×2交叉开关示意图，A、B是两个输入端，X、Y是两个输出端，任一
输入端可以被交换至任一输出端。图9.3(b)给出了通过交换网络传递的消息的格式，由4
个字段组成，M字段表示存储器模块号；A字段表示模块内的地址；R/W字段表示读/写操
作；V字段表示写操作时的写入值。对于8个CPU及8个存储器模块的连接，图9.3(c)所
示的Omega交换网络仅用了12个2×2交叉开关，即总共48个交换器，而对于交叉开关网
络则需要64个交换开关。
Omega交换网络的连接过程很简单，每个 2×2交叉开关利用消息中的 M字段来确定
消息应继续发送到哪个输出，M中相应位为0,则选择输出到X;否则选择输出到Y。例如，
假定CPU模块2要读取存储器模块4中第8单元的内容，则它将先发送一个消息(100,
1000,read)到开关1C。因为消息中M=100,所以，1C根据M中最左边一位1选择 2B作
为下一站。开关2B接收到消息后，它将根据 M中中间一位0选择3C作为下一站。开关
3C接收到消息后，它将根据M中最右一位0选择存储器4作为需访问的存储模块进行读
操作。图9.3(c)中的路径x表示了CPU模块2访问存储模块4的消息传递过程，路径y表
示了CPU模块3访问存储模块3的消息传递过程。显然，这两个访问操作不会使用任何相
同的开关、连线和存储模块，因此，两者可以并行进行。
在Omega交换网络中，如果两个访问操作同时进行并且它们的消息传递路径中使用到
了相同的开关或连线，则其中一个访问操作必须等待，即Omega交换网络是一种阻塞网络。
为了减少因等待而引起的阻塞，应尽量减少访存冲突。而要减少访存冲突，应使 CPU模块
对存储模块的访问操作均衡地分布在多个存储模块中，为此，存储器模块应采用交叉编址
方式。
9.2.2NUMA 多处理器结构
因为 UMA多处理器系统要保证每个处理器的访存时间与处理器和存储模块之间的相
<!-- page: 338 -->
并行处理系统
对位置无关，所以，其连接的处理器规模受到一定的限制。基于总线的 UMA多处理器会因
为总线冲突而无法连接很多CPU,交叉开关和多级交换网络也因为需要额外的交换器硬件
而限制了网络的规模。如果要构建规模更大的多处理器系统，则必须打破访存时间一致的
限制，在保证单一地址空间的前提下允许访存时间不一致，因此，出现了非一致内存访问
(NUMA)多处理器。
在NUMA多处理器系统中，每个处理器都带有一个本地存储模块，与UMA一样，所
有共享存储模块统一编址，以形成具有单一地址空间的一个逻辑存储器。只不过在UMA
中必须保证访存时间一致，而在NUMA 中处理器访问本地存储模块要快于对非本地存储
模块的访问。因为所有本地存储模块和非本地存储模块都在同一个地址空间，所以，非本地
存储模块也通过load和store指令来访问。由此可见，NUMA计算机上运行的所有 UMA
程序无须做任何改变，但在相同的主频下其性能不如UMA 计算机上的性能。
因为NUMA多处理器系统中共享的存储空间分布在不同的处理器节点上，因此，在节
点互连、并行编程、cache一致性方面所遇到的问题与UMA多处理器不同。处理器中不带
高速缓存时，系统被称为NC-NUMA(no cache NUMA);处理器中带有一致性高速缓存时，
系统被称为CC-NUMA。CC-NUMA多处理器系统必须考虑如何维持处理器cache的一致
性，在CC-NUMA中最常见的是基于目录的cache一致性机制。图9.4给出了一个基于目
录的CC-NUMA多处理器结构。
节点0
CPU 存储器
节点1
CPU 存储器
节点255
CPU 存储器
目录
目录
目录
局部总线
局部总线
局部总线
互连网络
(a)CC-NUMA互连结构
218-1