第一章 计算机系统结构的基本概念
1. 计算机系统由硬件和软件组成，按功能划分为多级层次结构。
2. 计算机系统结构作为一门学科，主要是研究软件，硬件功能分配和对软件、硬件界面的确定，即哪些功能由软件完成，哪些功能由硬件完成。计算机系统结构，计算机组成和计算机实现是三个不同的概念。计算机系统结构是计算机系统的软硬件的界面；计算机组成是计算机系统结构的逻辑实现；计算机实现是计算机组成的物理实现。
3. 计算机系统结构的分类
(1) 通常把计算机系统按照其性能和价格的综合指标分为巨型、大型、中型、小型、微型等。
(2) 按用途可分为科学计算、事务处理、实时控制、家用等。
(3) 按处理机个数和种类，可分为单处理机、多处理机、并行处理机、关联处理机、超标量处理机、超流水线处理机、SMP（对称多处理机）、MPP（大规模并行处理机）、机群系统等。
(4) Flynn分类法。按照指令流和数据流的不同组织方式，将计算机系统结构分为以下四类：
• 单指令流单数据流SISD（Single Instruction stream Single Datastream ）
• 单指令流多数据流SIMD（Single Instruction stream Multiple Datastream ）
• 多指令流单数据流MISD（Multiple Instruction stream Single Datastream ）
• 多指令流多数据流MIMD（Multiple Instruction stream Multiple Datastream ）
（5）冯式分类法。提出用最大并行度对计算机系统结构进行分类。分为：
• 字串位串WSBS（Word Serial and Bit Serial）
• 字并位串WPBS（Word Parallel and Bit Serial）
• 字串位并WSBP（Word Serial and Bit Parallel）
• 字并位并WPBP（Word Parallel and Bit Parallel）

4．计算机系统设计的定量原理
(1) 加快经常性事件的速度(Make the common case fast)。
(2) Amdahl定律：系统中某一部件由于采用某种更快的执行方式后整个系统性能的提高与这种执行方式的使用频率或占总执行时间的比例有关。
Fe表示（改进前可改进部分占用的时间）/（改进前整个任务的执行时间），Se表示（改进前改进部分的执行时间）/（改进后改进部分的执行时间），则：
• 改进后的整个任务的执行时间为：
       , 其中 为改进前的整个任务的执行时间。
• 改进后的整个系统加速比为：

   （3）CPU性能公式。
   CPU时间=CPU时钟周期数/频率；
   CPU时间=CPU时钟周期数*时钟周期长；
   平均时钟周期数CPI=CPU时钟周期数/IC（指令的条数）；
   CPU时间=（IC*CPI）/频率f；

   （4）访问的局部性原理。
时间局部性、空间局部性。

5. 计算机系统设计者的主要任务
(1) 确定用户对计算机系统的功能、价格和性能的要求。
(2) 软硬件的平衡。
(3) 设计出符合今后发展方向的系统结构。

6. 计算机系统设计的主要方法
(1) “由下往上”（bottom-up）设计。
(2) “由上往下”（top-down）设计。
(3) “由中间开始”（middle-out）设计。

7. 系统结构的评价标准
(1) 性能
• MIPS（Million Instructions Per Second）
   MIPS = =
• MFLOPS（Million FLoating point Operations Per Second）
   MFLOPS =
• 用基准测试程序来测试评价机器的性能。
• 综合基准测试程序。
（2）性能比较
• 总执行时间。
• 加权执行时间。

（3）成本
• 成本指标。
• 硬件考虑。

8．冯•诺依曼计算机的特征可概括为：
（1） 存储器是字长固定的、顺序线形编址的一维结构。
（2） 存储器提供可按地址访问的一级地址空间，每个地址是唯一定义的。
（3） 由指令形式的低级机器语言驱动。
（4） 指令的执行是顺序的，即一般按照指令在存储器中存放的顺序执行，程序分支由转移指令实现。
（5） 机器以运算器为中心，输入输出设备与存储器之间的数据传送都途经运算器。运算器、存储器、输入输出设备的操作以及它们之间的联系都由控制器集中控制。

9．软件对系统结构的影响
(1) 采用系列机方法。
(2) 采用模拟与仿真方法。
(3) 采用统一的高级语言方法。
10．价格、应用、VLSI对系统结构的影响
11．技术的发展对价格的影响
12．算法和系统结构

第二章 指令系统
1. 指令系统(Instruction Set Architecture, ISA)是计算机系统中软件与硬件的接口；主要研究数据表示、寻址方式等内容。

2. 数据表示
（1） 基本的数据表示方法，包括定点数、逻辑数、浮点数、字符、字符串、堆栈等，以及一些新的数据表示方法和在数据表示方面的新的研究成果，如自定义数据表示、带标志符的数据表示法、数据描述符表示法及浮点数表示方面的研究成果等；
（2） 数据表示的原则：
• 缩短程序的运行时间
• 减少CPU与主存储器之间的通信量
• 数据表示的通用性和利用率
（3） 计算机内浮点数的表数范围、表数精度和表数效率，浮点数尾数基值的选择
（4） 浮点数的性质和设计方法
（5） 运用浮点数进行四则运算

3. 寻址方式
（1） 寻址技术研究的主要内容包括编址方式、寻址方式和定位方式等，研究的对象主要有寄存器、主存储器、堆栈和输入输出设备等，其中以面向主存储器的寻址技术为主要研究对象；
（2） 编址方式是指对各种存储设备进行编码的方法，主要包括编址的单位、零地址空间的个数等，另外还包括并行存储器的编址技术和输入输出设备的非线形编址技术；
（3） 寻找操作数及数据存放单元的方法称为寻址方式。在分析各种寻址技术优缺点的基础上，重点是能够在计算机系统中如何选择和确定采用哪种寻址技术；
（4） 程序的定位是指把指令和数据的逻辑地址（相对地址）转换成主存储器的物理地址（绝对地址）。定位方式可分为三种：直接定位、静态定位和动态定位。

4. 指令格式的优化设计
（1） 指令格式优化设计的主要目标有两个，一是节省程序的存储空间，二是指令格式要尽量规整，以减少硬件译码的复杂程度。指令格式优化后，不应该降低指令的执行速度。
（2） 操作码的表示方法通常有三种：固定长度操作码、Huffman编码法和扩展编码法。要重点掌握Huffman编码法和扩展编码法；
（3） 固定长操作码的主要优点：规整，译码简单；主要缺点：浪费信息量（操作码的总长位数增加）
（4） 采用最优Huffman编码法操作码的最短平均长度可以通过如下公式计算：
   其中：Pi表示第i种操作码在程序中出现的概率
固定长操作码相对于Huffman操作码的信息冗余量为：

采用Huffman编码法操作码的最短平均长度可以通过如下公式计算：

Huffman操作码的主要缺点：
• 操作码长度很不规整，硬件译码困难
• 与地址码共同组成固定长的指令比较困难
（5） 扩展编码法：由固定长操作码与Huffman编码法相结合形成；
（6） 地址码个数的选择
• 地址码个数通常有三个、两个、一个及０个等四种情况
• 评价地址码个数应该取多少的标准主要有两个：一是程序的存储容量，包括操作码和地址码；二是程序的执行速度，以程序执行过程中访问主存的信息量代表
（7） 缩短地址码长度的方法
目标：用一个短的地址码表示一个大的逻辑地址空间
• 用间址寻址方式缩短地址码长度
在主存储器的低端开辟一个专门存放地址的区域，
• 用变址寻址方式缩短地址码长度
由于程序的局部性，变址寻址方式中的地址偏移量比较短，
• 用寄存器间接寻址方式缩短地址码长度，很有效的方法

5. 指令系统的功能设计
（1） 指令系统功能设计要求：完整性、规整性、高效率和兼容性；
（2） 基本指令系统包括数据传送类指令、运算类指令、程序控制类指令、输入输出指令、处理机控制和调试指令；
（3） 指令系统的优化设计有两个截然相反的方向：
• 复杂指令系统计算机CISC（Complex Instruction Set Computer）
1）增强指令功能，设置功能复杂的指令
2）面向目标代码、面向高级语言、面向操作系统
3）用一条指令代替一串指令
• 精简指令系统计算机RISC（Reduced Instruction Set Computer）
1）只保留功能简单的指令
2）功能较复杂的指令用子程序来实现
（4） RISC与CISC各自的特点和相互比较
（5） RISC的关键技术
• 旁路技术
• 延迟转移技术
• 指令取消技术
• 重叠寄存器窗口技术
• 指令流调整技术
• 以硬件为主固件为辅

第三章 存储系统
1. 提高存储器性能的主要方法有层次存储器、并行存储器、缓冲技术、先行控制技术等。

2. 典型的并行存储器包括并行访问存储器、低位交叉存储器和高位交叉存储器。低位交叉存储器的特点是地址相邻的信息存放在不同（相邻）的存储体中。高位交叉存储器的特点是地址相邻的信息存放在同一存储体中。

3. 所谓存储系统是指两个或两个以上速度、容量和价格各不相同的存储器用硬件、软件、或软件与硬件相结合的方法连接起来而成的系统。这个系统对应用程序员透明，并且，从应用程序员看它是一个存储器，这个存储器的速度接近速度最快的那个存储器，存储容量与容量最大的那个存储器相等或接近，单位容量的价格接近最便宜的那个存储器。程序访问的局部性原理是层次存储系统构成的基础。

4. 存储器的主要性能参数：
（1）存取时间：
从CPU到第i层存储器的往返时间。
（2）存储器容量：
第i层的字节或字的数量。
（3）每字节成本：
（4）传输带宽：
相邻层之间传输信息的速率。
（5）传输单位：
相邻两层之间数据传输的粒度（如字、块、页等）。

5. 层次存储器性质
（1）包含性：
    内层的信息必然包含于其外层。所有的信息最初放在最外层。在处理过程中，其子集被一步步复制到内层。

（2）一致性：
同一个信息项在后继存储器层次上的副本是一致的。
如果在缓存中的一个字被修改过，那么在所有高层上该字的副本也必须立即或最后加以修改。
维护一致性的两种策略：写直达和写回。前者指如果在内层中修改了一个字，在外层中必须立即加以修改。而后者的处理方法是：在外层中的修改延迟到内层中被修改的字被替换时才进行。

（3）局部性：
• 时间局部性：
最近的访问项很可能在不久的将来再次被访问。
• 空间局部性：
一个进程所访问的各项其地址彼此很近。
• 顺序局部性：
在典型程序中，除转移指令产生不按次序的转移外，指令都是顺序进行的。

6. 层次存储系统的设计的目的是使有效存取时间接近于最内层存储器的存取时间，使总体的平均每字成本接近于最外层存储器的每字成本，容量接近于最大存储器的容量。
本章主要论述两个二级层次存储系统cache和虚拟存储器。要解决的问题主要有：
（1） 块/页的定位问题。
（2） 替换问题。
（3） 一致性问题。（写无效和写更新）

7. 虚拟存储器由主存储器和联机工作的外部存储器共同组成。虚拟存储器有段式、页式、段页式等地址映像与变换方法。加快内部地址变换的技术主要有目录表、快慢表、散列函数等。页面替换算法主要有RAND、FIFO、LRU、LFU和OPT等算法。

8. Cache的地址映像与变换方法有全相联、直接相联、组相联和段相联几种。Cache的替换算法有轮转法、FIFO、LRU、LFU、比较对法和堆栈法。Cache的实现全部是由硬件完成的。

9. 影响主存命中率的主要因素有：
（1） 程序在执行过程中的页地址流分布情况
（2） 所采用的页面替换算法
（3） 页面大小
（4） 主存储器的容量
（5） 所采用的页面调度方法。

10. Cache的命中率主要与如下几个因素有关：
（1） 程序在执行过程中的地址流分布情况
（2） 当发生Cache块失效时，所采用的替换算法
（3） Cache的容量
（4） 在组相联映象方式中，块的大小和分组的数目
（5） 所采用的Cache预取算法等。

11. 解决Cache与主存的不一致性问题，首先要选择合适的Cache更新算法。一般有两种Cache更新算法，写直达法和写回法。
12. Cache预取算法一般有按需取、恒预取和不命中预取等几种。

第四章 输入输出系统
1．磁盘存储器的技术指标。
（1） 磁盘存储器的主要技术指标包括存储密度、存储容量、存取时间和数据传输率。
（2） 存储密度分为道密度与位密度。道密度是指沿磁盘半径方向单位长度上的磁道密度。位密度是指磁道单位长度上能记录的二进制代码位数。
（3） 存储容量是指一个磁盘存储器所能存储的字节总数。
（4） 存取时间是指从发出读写命令后，磁头从某一起始位置移动到新的记录位置，到开始从盘片表面读出或写入信息所需要的时间。它包括寻道时间（定位时间）和等待时间。寻道时间指将磁头定位到所要求的磁道上所需的时间。等待时间是指从寻道完成后至磁道上需要访问的信息到达磁头下的时间。平均存取时间等于平均寻道时间和平均等待时间之和。平均等待时间用磁盘旋转一周所需时间的一半来表示。
（5） 数据传输率指磁盘存储器在单位时间内向主机传送数据的字节数。假设磁盘旋转速度为n转每秒，每条磁道容量为N字节，则数据传输率Dr = nN（B/s）。或Dr = D • V（B/s），其中D为位密度，V为磁盘旋转的线速度。
（6） 目前国际上通用的标准磁带是1/2英寸9道启停式磁带。它用两种方式存储信息，一是文件形式，二是数据块形式。磁带的块化系数是指每个数据块所容纳的记录条数。
2．输入输出系统
（1） 在计算机系统中，通常把处理机和主存储器之外的部分称为输入输出系统，它包括输入输出设备、输入输出接口和输入输出软件等。
（2） 输入输出系统的特点是异步性、实时性和设备无关性。
（3） 基本的输入输出方式有三种：程序控制输入输出方式、直接存储器访问方式（DMA）和中断输入输出方式。
（4） 程序控制输入输出方式完全受CPU控制，数据的输入输出都要经过CPU，用于连接低速外围设备。
（5） 直接存储器访问方式（DMA）主要用于连接高速外围设备，它使得存储器既可被CPU访问，也可被外围设备访问。目前使用的DMA方式主要有三种：周期窃取方式、直接存取方式和数据块传送方式。
（6） 中断输入输出方式使得CPU与外围设备可以并行工作，并可以处理例外事件。中断方式常用于连接低速外围设备。
3．中断系统
（1） 中断系统通常由硬件和软件同时实现。软硬件的功能分配决定了中断响应时间。
（2） 中断响应时间是指从一个中断源向处理机发出中断服务请求开始，到处理机实际开始执行这个中断源的中断服务程序时为止的时间。它由以下四个因素决定：最长指令执行时间、在一条指令执行完成后处理其他更紧急的任务所用时间、从第一次关中断到第一次开中断所需的时间、找到中断服务程序入口所需的时间。
（3） 中断源的识别有几种方法。最简单的一种方法是查询法，灵活性好，但速度慢。串行排队链法和中断向量法用软硬件相结合的方法来实现中断排队，速度快，但灵活性和可靠性差。独立请求法克服了串行排队链法可靠性差的缺点，但灵活性差的缺点依然存在。
（4） 根据中断的紧迫性、设备的工作速度、数据恢复的难易程度和要求处理机提供的服务质量等，把中断源分为优先程度不同的几个级别，称为中断源的优先级。处理机在执行某一个中断源的中断服务程序时，只能响应比它优先级高的中断请求，不能响应与它同级或低级的中断请求。
（5） 为提高中断系统的灵活性，可以动态地改变中断源的优先级，这就需要设置中断屏蔽。设置中断屏蔽还可以决定设备是否采用中断方式工作，或在多处理机系统中把中断请求分配到不同的处理机中。
（6） 中断屏蔽的实现方法主要有两种：一是为每个或每级中断源都设置一个中断屏蔽位，二是改变处理机的优先级。
4．通道处理机
（1） 在大型计算机系统中，为把对外围设备的管理工作从CPU中分离出来，普遍采用通道处理机技术。采用通道方式组织的输入输出系统，多采用主机——通道——设备控制器——IO设备四级连接方式。通道通过执行通道程序实现对IO系统的统一管理和控制。在CPU启动通道后，通道自动地去内存取出通道指令并执行指令。直到数据交换过程结束向CPU发出中断请求，CPU才进行通道结束处理工作。
（2） 通道可分为三类：字节多路通道、选择通道和数组多路通道。字节多路通道常用于连接低或中速的设备，选择通道和数据多路通道用于连接高速设备。
（3） 对于以上的三种通道，当每个通道上连接有P台外围设备，每台设备都传送n个字节时，总共所需的时间分别为：
TBYTE =（TS + TD）• P • n
TSELECT =（TS / n + TD）• P • n
TBLOCK =（TS / n + TD）• P • n
其中TS指设备选择时间，TD指传送一个字节所需的时间。
（4） 通道的流量是指一个通道在数据传送期间内，单位时间内能够传送的最大数据量。一个通道在满负荷工作下的流量称为通道最大流量。三种通道的最大流量计算公式如下：
f MAX•BYTE =（P • n）/ [（TS + TD）• P • n ] = 1 /（TS + TD）
f MAX•SELETE =（P • n）/ [（TS / n + TD）• P • n ] = 1 /（TS / n + TD）
f MAX•BLOCK =（P • n）/ [（TS / k + TD）• P • n ] = 1 /（TS / k + TD）
（5） 字节多路通道的实际流量是指连接在这个通道上的所有设备的数据传输率之和。而选择通道和数据多路通道的实际流量是指连接在这个通道上的所有设备数据传输率的最大值。

5．输入输出处理机
在大型、巨型计算机系统中，常采用输入输出处理机来分担中央处理机的输入输出任务。输入输出处理机是一台独立的处理机，具有一定的运算功能，它具有自己的存储器，不必通过主存储器就能完成与外围设备的数据交换，大大提高了系统性能。

第五章 标量处理机与流水线
1. 先行控制技术（look-ahead）。先行控制技术的关键是缓冲和预处理技术。指令的执行过程可以被分解为相互独立的几个阶段（取指令，分析指令，执行指令），采用重叠执行方式，使每个功能段相对独立地运行，就能提高运行速度。为了平衡给功能段之间的由于速度不确定带来的速度差异，在各功能段之间设置了缓冲栈(先行指令缓冲栈，先行操作栈，先行读数栈，后行写数栈)，同时为了解决数据相关和控制相关带来的停顿问题，使用了不同的预处理技术。对数据相关和控制相关的分析和解决办法是整个预处理技术的核心。
2. 流水线的原理、特点及其分类。流水线方式是把一个重复的过程分解为若干个子过程，每个子过程可以和其他的子过程同时进行，即所谓的时间并行性。流水线的工作可以用时空图来描述。流水线有以下的特征：为了提高流水线的效率，应该尽可能的为流水线提供连续的任务；流水线由很多相联的功能段组成，为了平衡功能段之间的速度差，功能段之间需要设置缓冲寄存器；流水线中每个功能段的时间应该尽量相等，以免形成“瓶颈”，否则应该对功能段再划分或者采用多个功能部件；流水线需要装入和排空时间，只有在流水线完全充满时，它才能充分发挥效率。根据不同的角度，流水线可以被划分成以下的类别：线性流水线，非线性流水线；指令流水线，运算操作流水线，宏流水线；单功能流水线，多功能流水线；静态流水线，动态流水线等。
3. 流水线的性能分析。衡量流水线性能的主要指标有吞吐率，加速比，效率。流水线的吞吐率TP定义为单位时间内流水线所完成的任务数量或者输出的结果数量，基本公式如下：
n为任务数，Tk是完成n个任务所用的时间。
流水线的加速比S指完成一批任务，不使用流水线所用的时间与使用流水线所用的时间之比称为流水线的加速比：
其中T0指顺序执行所用的时间，Tk时使用流水线的执行时间。
流水线的效率E是指流水线的设备利用率，在时空图上，流水线的效率定义为n个任务占用的时空区与k个功能段总的时空区之比。
     
4. 非线性流水线的调度。非线性流水线需要一个各功能段的连接图和一张预约表来共同表示。非线性流水线中，一个任务可能要使用同一功能段多次，因此，可能发生流水线的冲突。为了避免冲突，需要找出一个最小的循环周期来对任务进行调度。采用无冲突调度方法，能够得到线性流水线的最小启动循环。但是，这种调度方法不是最优调度，即它的平均启动距离不等于最小平均启动距离。为了达到最优调度，可以采用预留算法，通过插入非计算延迟功能段的方法来得到平均启动距离最小的调度。
5. 数据相关和控制相关的解决方法。数据相关和控制相关（局部相关和全局相关）产生的流水线停顿会使流水线的效率严重下降。指令级并行（ILP）技术用来解决这些问题。它的思想是开发串行指令的并行性。循环的展开和调度是一种软件的指令级并行技术。它是一种优化的编译技术，将要执行的循环体展开多次，通过增加源代码长度的办法，为并行执行调度提供更多的机会。用于指令级并行的硬件技术有Tomasulo动态指令调度算法和CDC记分牌算法。他们用动态建立专用路径的方法来解决一些数据相关的问题。对于全局相关，可以使用延迟转移技术和指令取消技术，以及转移预测技术。

第六章 向量处理机
1. 把N个互相独立的数叫做“向量”，对这样一组数的运算叫做“向量处理”。一条向量指令可以处理N个或N对操作数。

2. 向量处理的方式
(1)． 横向处理方式：向量计算是按行的方式从左至右横向进行。
(2)． 纵向处理方式：向量计算是按列的方式自上而下纵向进行。
(3)． 纵横处理方式：横向处理和纵向处理相结合的方式

3. 向量处理机一般有如下两种结构：
(1)． 利用几个独立的内存模块来支持对相互独立的资料的并发访问，从而达到所要求的内存带宽，即存储器—存储器结构。在运算流水线的输入端和输出端增加了缓冲器以便消除争用内存的现象。
(2)． 构造一个具有所要求带宽的高速中间内存，并能实现该高速中间内存与主存储器之间的快速资料交换，即寄存器—寄存器结构。设计这种系统结构的主要思想是使操作数离处理器很近，以保证处理器一直处于忙状态。中间内存提供给处理器快速存取的资料，而成本又比较低。

4. 向量处理机系统结构的设计目标
(1)． 较好的维持向量/标量性能平衡。
(2)． 可扩展性随处理机数目的增加而增加。
(3)． 可扩展性的三个目标是：规模可扩展性，换代可扩展性，问题可扩展性。
(4)． 增加内存系统的容量和性能。
(5)． 提供高性能的I/O和易访问的网络。

5. 提高向量处理机性能的常用技术
(1)． 链接技术
(2)． 向量循环或分段开采技术
(3)． 向量递归技术
(4)． 稀疏矩阵的处理技术

8    向量指令的处理时间
其中，Ts为向量流水线的建立时间，它包括向量起始地址的设置、计数器加1、条件转移指令执行等。Tvf为向量流水线的流过时间，它是一条指令从开始译码到流过流水线得到第一个结果元素的时间。Tc为流水线“瓶颈”段的执行时间。
一组向量操作的执行时间主要取决于下面三个因素：向量的长度、向量操作之间是否存在流水功能部件的冲突和数据的相关性。

9     最大性能R∞表示当向量长度为无穷大时的向量流水线的最大性能。常在评价峰值性能时使用，单位为MFLOPS。它可表示为：
因为分子的值与n无关，所以

10 n1/2为达到一半R∞值所需的向量长度。它是评价向量流水线建立时间对性能影响的参数。它表示为建立流水线而导致的性能损失。

11 向量长度临界值nv表示向量流水方式的工作速度优于标量串行方式工作时所需的向量长度临界值。该参数既衡量建立时间，也衡量标量、向量速度比对性能的影响。

第七章 互连网络
1. 互连网络基本概念

（1）互连网络
互连网络是一种由开关元件按照一定拓扑结构和控制方式构成的网络,用来实现计算机系统内部多个处理机或多个 功能部件之间的相互连接.
（2）互连函数
为了反映不同互连网络的连接特性,每种互连网络可用 一组互连 函数来描述.如果将互连网络的N个输入端和N个输出端分别用0,1,2,...,N-1来表示,则互连函数表示相互连接的输入端和输出端号之间的一一对应关系.或者说,存在互连函数f,在它的作用下,输入i应与f(i)相连, 这里0<=i<=N-1.表示互连函数常用两种方法:函数表示法和输入输出对应表示法. 基本互连函数有如下几种
 恒等置换
        I( … )= …
 交换置换
                E( … )=
 方体置换
                 ( … … )= … …
           显然这是上述交换置换的一般情况。
 均匀洗牌置换
                 ( … )= …  
                 还可定义子洗牌 和超洗牌 如下
( … … )= … …  
( … … )= … …
          以及均匀洗牌的逆函数逆均匀洗牌
( … )=   …

 蝶式置换
                 ( … )= …
           同样可以定义子蝶式和超蝶式置换。
 位序颠倒置换
                 ( … )= …
            同样也可以定义子位序颠倒置换和超位序颠倒置换。
 移数置换
                 (X)=(X+k) mod N, 0 X N;
 加减 置换
                PM (X)=X+ mod N
          PM (X)=X- mod N
                其中0 X N; 0 i n-1;n=logN

2. 互连网络的特性
        (1)网络规模 : 网络中结点数目;
        (2)结点度     : 与结点相连的边数;
        (3)距离         : 两结点间相连的最少边数;
        (4)网络直径 : 网络中任意两个结点间距离的最大值
        (5)等分宽度 : 网络被切成相等的两半时沿切口的最小边数
        (6)结点间线长 : 任两个结点间线的长度
        (7)对称性         : 若从任何结点看网络的拓扑结构都一样,则称该网络为对称网络.

3. 网络的传输性能特性
        (1)频宽
           消息进入网络后,互连网络传输消息的最大速率,单位用bit/sec(或mb/s).
        (2)传输时间
           消息通过网络的时间,等于消息长度除以频宽;
        (3)"飞行"时间
           消息的第一位信息到达接收方所花费的时间,它包括由于网络中转发或者其他硬件
     所引起的时延
        (4)传输时延
           它是消息在互连网络上所花费的时间,但不包括消息进入网络和到达目的结点后从
           网络接口硬件取出数据所花费的时间,它等于"飞行"时间和传输时间之和.
        (5)发送方开销
           处理器把消息放到互连网络的时间,包括硬件和软件所花费的时间
        (6)接收方开销
           处理器把到达的消息从互连网络取出来的时间,包括软件和硬件所花费的时间.

4. 互连网络分类
     （1） 分类法I
     静态互连网络：各结点间有专用连接通路且运行中不能改变的网络。
 线性阵列
 环和带弦环
 循环移数网络
 树和星型
 胖树形
 网格型和环网型
 搏动阵列
 超立方体
 带环立方体
 k元n立方体网络

动态互连网络：设置有源开关，可以根据需要借助控制信号对连接通路加以重新组
                             合实现要求的通信模式的网络。
 总线
 开关模块
 多级网络
 omega网络
 基准网络
 交叉开关网络

   （2）分类法II
 共享介质网络：同一时间只允许一个设备进行存取；
 非阻塞网络：逻辑上的交叉开关网络，除非存在不同输入端口向同一输出
                                           端口发送消息；否则消息通信将不会阻塞；
 直接网络：指网络中的处理器是点到点连接的（静态网络）。
 间接网络：网络中的结点不是通过直接相连的通道进行消息通信，而是通
                                       过网络的开关机构进行；
 混合网络：指一个互连网络中混合了多种以上网络。

5. 消息传递机制
       （1） 消息寻径方式
 线路交换
 存储转发寻径
 虚拟直通
 虫蚀寻径

       （2） 死锁和虚拟通道
 虚拟通道
                虚拟通道是两个结点间的逻辑链,它是由源结点的片缓冲区, 结点间的物理通道
                 以及接收结点的片缓冲区组成.
 死锁的产生和避免
                缓冲区或通道上的循环等待可能产生死锁.利用虚拟通道可以解决死锁

6. 流控制策略
（1）包冲突的解决
 用缓冲实现虚拟直通
 阻塞策略
 扬弃并重发策略
 阻塞后绕道
        （2）确定寻径和自适应寻径

7. 选播和广播寻径
                (1)单播 : 对应于一对一的通信情况,即一个源结点发送消息到一个目的结点.
        (2)选播 : 对应于一到多的通信情况,即一个源结点发送同一个消息到多个目的结点
        (3)广播 : 对应于一到全体的通信情况,即一个源结点发送同一个消息到全部结点.
        (4)会议 : 对应于多到多的通信情况.
8. 通道流量和通道时延
        通道流量和通道时延是描述效率常用的两个参数.优化的寻径网络应该能以最小流量和最小时延实现有关的通信模式.然而这两个参数并不是毫不相关的,达到最小流量同时不
一定能达到最小时延,相反的情况也如此.

第八章并行处理机和多处理机
1. SIMD计算机模型
（1）SIMD计算机的抽象模型
在同一个控制部件的管理下,有多个处理单元。所有处理单元均收到从控制部件广播来的同一条指令，但操作对象是不同的数据。
（2）SIMD计算机的操作模型
SIMD计算机的操作模型用五元组表示：
M = （N，C，I，M，R）。
其中, 五元组中各符号的含义：
N--机器的处理单元（PE）数；
C--由控制部件（CU）直接执行的指令集，包括标量和程序流控制指令；
I--由CU广播至所有PE进行并行执行的指令集，包括算术运算、逻辑运算、数据寻径、屏蔽以及其他由每个活动的PE对它的数据所执行的局部操作；
M--屏蔽方案集，其中每种屏蔽将PE集划分为允许操作和禁止操作两种子集；R--数据寻径功能集，说明互连网络中PE间通信所需要的各种设置模式。
（3）可以用上述五元组描述一台具体的SIMD机器。
（4）SIMD计算机处理单元的粒度：细粒度、中粒度。
2. SIMD计算机的基本结构
（1）分布式存储器结构
分布式存储结构的体系模型、工作原理和特点。
（2）共享存储器结构
共享存储结构的体系模型、工作原理和特点。
3. SIMD计算机的特点
(1) SIMD计算机的实质是利用了多PE的空间并行性来提高计算速度。
(2) SIMD计算机与流水线向量处理机的相同与不同。
4. 多处理机结构由如何台独立的计算机组成，每台计算机能够独立执行自己的程序，又称多指令流多数据流（MIMD）结构。多处理机系统中的处理机之间通过某种方式（如互连网络）互连，从而实现程序之间的数据交换和同步。
5. 使用多处理机的主要目的是利用多台处理机并发地执行一个作业，使得执行速度比单处理机快；有时候，使用使用多处理机的主要目的是提高可靠性而不是高性能，如果某台处理机出现故障，那么它的程序可以由系统中其它处理机来执行。
6. 多处理机有两种基本的结构：共享存储器结构和本地存储器结构。共享存储器方案中，存储器和I/O设备是独立的子系统，为所有处理机所共享，这是实现信息交换和同步最简单的办法，任何两台处理机都可以通过共享存储器的单元实现通信。本地存储器结构每台处理机都有自己的存储器和I/O设备，处理机之间通过点对点的信息交换实现通信。
7. 多处理机的主要特点包括：
（1） 结构的灵活性。与SIMD计算机相比，多处理机的结构具有较强的通用性，它可以同时对多个数组或多个标量数据进行不同的处理，这要求多处理机能够适应更为多样的算法，具有灵活多变的系统结构。
（2） 程序并行性。并行处理机实现操作一级的并行，其并行性存在于指令内部，主要用来解决数组向量问题；而多处理机的并行性体现在指令外部，即表现在多个任务之间。
（3） 并行任务派生。多处理机是多指令流操作方式，一个程序中就存在多个并发的程序段，需要专门的程序段来表示它们的并发关系以控制它们的并发执行，这称为并行任务派生。
（4） 进程同步。并行处理机实现操作级的并行，所有处于活动状态的处理单元受一个控制器控制，同时执行共同的指令，工作自然同步；而多处理机实现指令、任务、程序级的并行，在同一时刻，不同的处理机执行着不同的指令，进程之间的数据相关和控制依赖决定了要采取一定的进程同步策略。
8. 如果多处理机系统以峰值速度运行时，所有处理机都在做着有用的工作，并且忽略通信开销，那么N台处理机所构成的多处理机系统其效率和性能应该是单个处理机的N倍。实际上，由于以下原因，多处理机的峰值性能很难达到：多处理机间的通信延迟；处理机间的同步开销；没有足够多的任务时，若干台处理机处于空闲状态或执行无关工作；系统控制和操作调度所需的开销。多处理机的性能很大程度依赖于R/C比值，其中R代表程序的执行时间，C代表用于通信的开销。常见的多处理机性能模型包括：基本模型、随机模型、通信开销为线性函数的模型、完全重叠通信的理想模型、具有多条通信链的模型等。
9. 在并行多处理机系统中的私有Cache会引起Cache中的内容相互之间以及与共享存储器之间互不相同的问题，即多处理机的Cache一致性问题。
（1） 出现Cache一致性问题的原因主要有三个：共享可写的数据、进程迁移、I/O传输。共享可写数据引起的不一致性。
比如P1、P2两台处理机各自的本地高速缓冲存储器C1、C2中都有共享存储器是M中某个数据X的拷贝，当P1把X的值变成X/后，如果P1采用写通过策略，内存中的数据也变为X/，C2中还是X。如果通过写回策略，这是内存中还是X。在这两种情况下都会发生数据不一致性。
（2） 进程迁移引起的数据不一致性。
P1中有共享数据X的拷贝，某时刻P1进程把它修改为X/并采用了写回策略，由于某种原因进程从P1迁移到了P2上，它读取数据时得到X，而这个X是“过时”的。
（3） I/O传输所造成的数据不一致性。假设P1和P2的本地缓存C1、C2中都有某数据X的拷贝，当I/O处理机将一个新的数据X/写入内存时，就导致了内存和Cache之间的数据不一致性。
10. 有两类解决Cache不一致性问题的协议机制：监听协议和基于目录的协议，它们实用于不同的系统结构。
（1） 监听协议
在基于总线互连结构的系统中，由于系统中每个处理机都能觉察到存储器系统正在进行的活动，在每个活动破坏了Cache的一致性时，Cache控制器将采取相应的动作使有关的拷贝无效或更新，这就是监听协议。
使用监听协议时，有两种保持Cache一致性的方法：写无效（Write-Invalidate）策略和更新（Write-Update）策略。前者是在本地Cache的数据块修改时使远程数据块都无效，后者是在本地Cache数据块修改时通过总线把新的数据块广播给含该数据块的所有其它Cache。由于Write-Update策略增加了总线的负担，故实际系统常采用Write-Invalidate策略。
（2） 基于目录的协议
当采用非总线方式构造大型系统或当在多级网络上实现广播功能代价很大时，监听协议无法使用，这时采用基于目录的协议。基于目录的协议的核心是把其它Cache数据块无效的一致性命令只发给存放相应数据块的Cache。在多级网络中，用Cache目录存放有关Cache拷贝驻留在哪里的信息，从而支持Cache一致性。
各种基于目录协议的不同之处主要在于目录如何维护及存放什么样的信息。Cache目录的方案有集中式和分布式两种，它们的主要区别在于Cache目录的存放形式。Cache目录的内容是大量指针，用于指明块拷贝的地址。每个目录项，用以指明是否有一个Cache允许把有关的数据写入。
根据目录的结构，把目录协议分成三类：全映射（full-map）目录、有限（limited）目录、链式（chained）目录。全映射目录存放与全局存储器中每个块有关的数据，系统中每个Cache可以同时存储任何数据块的拷贝。而对有限目录，无论系统规模多大，它的每个目录项的指针数是固定的，所以每个数据块能够装入Cache的数是有限的。链式目录的特点是把目录分布到全部的Cache中，其余部分与全映射相同。
目录的使用方法是：在一个CPU对Cache进行了写操作时，系统根据Cache目录的内容将其它存有相同内容的Cache拷贝无效，并置重写位为“重写”。在CPU对Cache进行读操作的情况下，如果重写未置位，说明该内容未经重写，此时若Cache读缺失，则从主存储器中或拥有正确内容的Cache中读入块并修改目录；如果读命中，则直接读。

11．多处理机系统主要有四类：第一类是多向量处理系统，以CRAY YMP-90、NEC SX-3和FUJITSU VP-2000等为代表；第二是基于共享存储的多处理机系统（SMP，shared memory mulptiprocessors），如SGI Challenge和Sun SparcCenter 2000；第三类是基于分布存储的大规模并行处理系统（MPP），比如Intel Paragon、CM-5、Gray T3D等；第四类是机群系统。