本文最后更新于：2022年7月7日上午

第一章概念

计算机系统层次结构

分成6层每层的功能

解释：L0-L2级每当一条N+1级指令被译码后就直接去执行一串等效的N级指令，然后再去取下一条N+1级的指令，依次重复进行

翻译：L3-L5级先把N+1级程序全部转换成N级程序后再去执行新产生的N级程序，在执行过程中N+1级程序不再被访问

解释执行比翻译执行所花的时间多，但占用的存储空间更少

计算机系统结构的定义

计算机系统结构研究的是==软、硬件之间的功能分配==以及==对传统机器级界面的确定==，为机器语言、汇编语言程序设计者或编译程序生成系统，提供使其设计或生成的程序能在机器上正确运行而应看到和遵循的计算机属性

计算机系统的分类（Flynn分类法）

按照指令流和数据流的多倍性特征进行分类

指令流：机器执行的指令序列

数据流：由指令流调用的数据序列

多倍性：在系统性能瓶颈部件上同时处于同一执行阶段的指令或数据的最大可能个数

单指令流单数据流 SISD

典型顺序处理计算机
单指令流多数据流 SIMD

并行处理机、向量处理机、超标量处理机、超流水线处理机

多个PU按一定方式互连，在同一个CU控制下，对各自的数据完成同一条指令规定的操作；从CU看指令顺序执行，从PU看数据并行执行
多指令流单数据流 MISD

几条指令对同一个数据进行不同的处理
多指令流多数据流 MIMD

Amdahl定律及其应用

系统中某一部件由于采用更快的执行方式，整个系统性能的提高与这种执行方式的使用频率有关

$可改进部分的比例：Fe=\frac{可改进部分的执行时间}{改进前整个任务的执行时间}\\ 改进部分的加速比：Se=\frac{改进前改进部分的执行时间}{改进后改进部分的执行时间}$

假设 $T_0$ 为改进前整个任务的执行时间，则改进后整个任务的执行时间为

$T_n=T_0(1-Fe+\frac{Fe}{Se})$

改进后整个系统的加速比为

$S_n=\frac{T_0}{T_n}=\frac{1}{1-Fe+\frac{Fe}{Se}}$

CPU性能公式

CPU的程序执行时间 $T_{CPU}$ 取决于：

程序执行的总指令条数 $IC$ 取决于指令集结构和编译技术
平均每条指令的时钟周期数 $CPI$ 取决于计算机组成和指令集结构
$CPI=\frac{\sum_{i=1}^n(CPI_i\times I_i)}{IC}=\sum_{i=1}^n(CPI_i\times \frac{I_i}{IC})$
时钟主频 $f_c$ 取决于硬件实现技术和计算机组成

$T_{CPU}=IC\times CPI\times \frac{1}{f_c}$

程序访问的局部性规律

时间局部性：近期被访问的信息很可能马上被再次访问

空间局部性：在访问地址上相邻近的信息很可能被一起访问

软件的移植方法

模拟：用机器语言程序解释实现软件移植

仿真：用微程序直接解释另一种机器指令

第二章指令系统

数据表示与数据结构

数据表示：计算机硬件能够直接识别，可以被指令系统直接调用的数据类型

数据结构：串、队、栈、向量、阵列、链表、树、图等软件要处理的各种数据结构，反映了应用中要用到的各种数据元素或信息单元之间的结构关系

数据结构要通过软件映像才能变换成机器所具有的数据表示来实现，不同的数据表示可为数据结构的实现提供不同的支持

数据结构和数据表示实际上是软硬件的交互面，需要在系统结构设计时确定

标志符数据表示

一般的计算机中，数据存储单元只存放纯数据，数据的属性通过指令中的操作码来解释；高级语言使用类型说明语句指明数据类型，运算符不反映数据类型

为缩短高级语言与机器语言之间的语义差距，可以让机器中的每个数据都加上类型标志位。标识符由编译器或其他系统软件建立，对程序员透明。结果是数据存储量增加，指令存储量减少

数据描述符

为进一步减少标识符所占用的存储空间，对向量、数据、记录等数据，由于元素属性相同，采用数据描述符

数据描述符与标志符的区别：标志符只作用于一个数据，而数据描述符作用于一组数据

浮点数的表示方式

尾数决定了浮点数的表示精度，阶值决定了浮点数的表示范围

非负阶、规格化、正尾数

最小尾数（小数点后第一个$r_m$进制数位为1）：$r_m^{-1}$
最大尾数（$r_m$进制尾数均为$r_m-1$）：$1-r_m^{-m’}$
最大阶值（阶值部分全为1）：$2^p-1$
最小值（$最小尾数\times r_m^0$）：$r_m^{-1}$
最大值（$最大尾数\times r_m^{最大阶值}$）：$(1-r_m^{-m’})\times r_m^{2^p-1}$
可表示的尾数个数（小数点后第一个$r_m$进制数位为1）：$r_m^{m’-1}(r_m-1)$
可表示的阶个数：$2^p$
可表示的数个数：$2^pr_m^{m’-1}(r_m-1)$

特性：尾数基值$r_m$增大，会扩大浮点数表示范围，增加可表示数的个数，减少移位次数，降低右移造成的精度损失，提高运算速度；但也会降低数据的表示精度，数值的分布变稀疏

尾数下溢处理

截断法：将尾数超出机器字长的部分截去
舍入法：在机器运算的规定字长之外增设一位附加位，存放溢出部分的最高位，每当进行尾数下溢处理时，将附加位加1
恒置1法：把有效字长的最低一位置成$r_m/2$
查表舍入法：用ROM或者PLA存放下溢处理表

编址方式

编址单位：字编址、字节编址、位编址、块编址

编址单位与访问字长：

一般：字节编址字访问
部分机器：位编址字访问
辅助存储器：块编址位访问

字节编址的大小端问题 例0x12345678

小端：高位字节放高地址，低位字节放低地址

低地址			高地址
0x78	0x56	0x34	0x12

大端：低位字节放高地址，高位字节放低地址

低地址			高地址
0x12	0x34	0x56	0x78

模m高位交叉编址：主要用来扩大存储器容量

体地址A/m 体内地址A mod m

模m高位交叉编址

模m低位交叉编址：主要用来提高存储器速度

体地址A mod m 体内地址A/m

模m低位交叉编址

寻址方式

立即数寻址方式：直接在指令中给出操作数

面向寄存器的寻址方式：指令在执行过程中所需要的操作数来自于寄存器，运算结果也写回寄存器

面向主存储器的寻址方式：

直接寻址：在指令中直接给出参加运算的操作数及运算结果所存放的主存地址
间接寻址：指令中给出的是操作数地址的地址
变址寻址：指令执行时，用硬件加法器将变址寄存器中的基地址与指令给出的偏移量相加，才得到有效地址

面向堆栈的寻址方式：是隐含的，在指令中不需要给出操作数地址

定位方式

直接定位：在程序装入主存之前，程序中的指令和数据的物理地址就已经确定

静态定位：在程序装入主存的过程中进行地址变换

动态定位：在程序执行过程中访问到相应的指令或数据时才进行地址变换

操作码优化设计

RISC

特点：

减少指令和寻址方式种类
固定指令格式
大多数指令在单周期内完成
采用LOAD/STORE结构
硬布线逻辑
优化编译

思想：减少CPI

技术：

延时转移技术
指令取消技术
重叠寄存器窗口技术
指令流调整技术
采用高速缓冲存储器Cache
优化设计编译系统

第三章存储系统

存储系统的定义和评价标准

两个或两个以上速度、容量和价格各不相同的存储器用硬件、软件、或软件与硬件相结合的方法连接起来成为一个存储系统

对应用程序员透明，速度=max，容量=max，价格=min

Cache存储系统由Cache和主存储器构成，对系统程序员以上均透明

主要目的是提高存储器速度

虚拟存储系统由主存储器额硬盘构成，对应用程序员透明

主要目的是扩大存储器容量

容量S要求提供尽可能大的地址空间，能够随机访问

只对系统中存储容量最大的存储器进行编址，如Cache存储系统
另设计一个容量很大的逻辑地址空间，把相关存储器映射到该地址空间中，如虚拟存储系统

价格C

$C=\frac{C_1 S_1+C_2S_2}{S_1+S_2}\\$

速度用访问周期T表示，命中率H，访问效率e

$e=\frac{T_1}{T}=\frac{T_1}{H\cdot T_1+(1-H)\cdot T_2}=\frac{1}{H+(1-H)\frac{T_2}{T_1}}=f(H,\frac{T_2}{T_1})$

提高存储系统速度的两种方法：

提高命中率
两个存储器的速度不要相差太大

存储系统的层次结构

存储系统频带平衡的解决方法

多个存储器并行工作
设置各种缓冲存储器
采用存储系统

并行存储器

把m字w位的存储器变为m/n字n*w位的存储器

主要缺点：访问冲突大

取指令冲突
读操作数冲突
写数据冲突
读写冲突

虚拟存储器工作原理

把主存储器、磁盘存储器和虚拟存储器都划分成固定大小的页，进行内部地址变换

页式

段式

段页式

加快内部地址变换的方法

多级页表

页表级数的计算公式

$g=\lceil\frac{虚页总数}{每页能容纳的页表项个数}\rceil=\lceil\frac{\log_2{N_v}-\log_2{N_p}}{\log_2{N_p}-\log_2{N_d}}\rceil$

$N_v$为虚拟存储空间大小，$N_p$为页面大小，$N_d$为一个页表存储字的大小

采用多级页表使访问主存次数增加，需要加快查表速度

目录表法：压缩页表，用一个容量比较小的高速存储器来存放页表
快慢表：时间局部性，用快表保存最近访问的虚页到实页的映射
散列函数：把按内容的相联访问变为按地址访问

页面替换算法

随机算法RAND

最优替换算法OPT：选将来最久没有被访问的页

近期最少使用算法LRU：选最久未被访问的页

先进先出算法FIFO：选最早装入主存的页

提高主存命中率

页面大小增加命中率增加，当达到某个值时命中率最大，之后页面增大命中率降低

主存容量S增加命中率H增加，随着S的增加，H增加的速度逐渐降低，当S增加到某个值之后H几乎不再增加

页面调度方式分为请求式和预取式

Cache存储系统工作原理

地址映像：把主存中的程序按照某种规则装入到Cache中，并建立主存地址与Cache地址之间的对应关系

地址变换：当程序已经装入到Cache之后，在程序运行过程中把主存地址变换成Cache地址

全相联映像

直接映像

组相联映像

Cache的一致性问题

Cache与主存不一致的原因：

CPU写Cache时没有立即写主存
IO设备写主存时没有更新Cache

解决办法：

写直达法：CPU的数据写入Cache时同时也写入主存
写回法：CPU的数据只写入Cache不写入主存，只有当替换时才把修改过的Cache块写回主存
比较：
- 可靠性：写直达法优于写回法
- 与主存的通信量：写回法少于写直达法
- 控制的复杂性：写直达法比写回法简单
- 硬件实现的代价：写回法要比写直达法好

Cache的预取算法

按需取：当出现Cache不命中时，才把需要的一个块取到Cache中

恒预取：无论Cache是否命中，都把下一块取到Cache中

不命中预取：当出现Cache不命中，把本块和下一块都取到Cache中

第四章 I/O系统

基本的输入输出方式

程序控制方式 Polling

中断方式 Interrupts

当出现(…)事件时，CPU暂停执行现行程序，转去处理这些事件，等处理完成后再返回来继续执行原先的程序

直接存储器访问方式 DMA

周期窃取方式：在每一条指令执行结束时，CPU测试有没有DMA服务申请
直接存取方式：DMA控制器的数据传送申请直接发往主存储器
数据块传送方式：在设备控制器中设置一个数据缓冲存储器，设备控制器与主存储器之间的数据交换以数据块为单位，并采用程序中断方式进行

中断源分类和优先级

由外围设备引起的中断
由处理机本身产生的中断

如算术溢出、除数为零、数据校验错等
由存储器产生的中断

如地址越界、页面失效、访问存储器超时等
由控制器产生的中断

如非法指令、堆栈溢出、时间片到、切换到特权态
由总线产生的中断

如输入输出总线出错、存储总线出错等
实时过程控制产生的中断
实时钟的定时中断
多处理机系统中从其他处理机发送来的中断
程序调试过程中由断点产生的中断
硬件故障中断
电源故障中断

安排中断优先顺序主要由下列因素来决定：

中断源的急迫性
设备的工作速度
数据恢复的难易程度
要求处理机提供的服务量

按照中断优先级响应中断请求的原则：

CPU同时接受到几个中断时，首先响应优先级最高的中断请求
正在进行的中断过程不能被新的同级或低级中断请求中断
正在进行的低优先级中断服务能被高级中断请求中断

中断处理过程及软硬件分配

硬件实现：保存中断点和进入中断服务程序入口软件实现：中断服务和返回到中断点

1 现行指令结束，且没有更紧急的服务请求

2 关CPU中断

3 保存断点，主要保存PC中的内容

4 撤销中断源的中断请求

5 保存硬件现场，主要是PSW及SP等

6 识别中断源

7 改变设备的屏蔽状态

8 进入中断服务程序入口

9 保存软件现场，在中断服务程序中使用的通用寄存器等

10 开CPU中断，可以响应更高级别的中断请求

11 中断服务，执行中断服务程序

12 关CPU中断

13 恢复软件现场

14 恢复屏蔽状态

15 恢复硬件现场

16 开CPU中断

17 返回到中断点

中断响应时间

从中断源向处理机发出中断服务请求开始，到处理机开始执行这个中断源的中断服务程序时为止

中断屏蔽

设置中断屏蔽位

几个例子(最后一个有问题)

同时来按响应优先级响应

到开中断的时候看屏蔽码，未屏蔽的按响应优先级去处理

执行过程中来新请求看屏蔽码去处理

执行完返回到入口位置再去响应剩下的请求

改变处理机优先级

处理机、每个中断源的硬件中断和中断向量都设置优先级

处理机只能响应硬件中断优先级比他高的中断（响应优先级按硬件中断优先级排），然后把自己的优先级变成该中断源对应的中断向量的优先级

一个例子好好理解

通道处理机的作用和功能

分担CPU的输入输出负担

接受CPU发来的指令，选择一台指定的外围设备与通道相连接
执行CPU为通道组织的通道程序
管理外围设备的有关地址
管理主存缓冲区的地址
控制外围设备与主存缓冲区之间数据交换的个数
指定传送工作结束时要进行的操作
检查外围设备的工作状态是正常或故障
在数据传输过程中完成必要的格式变换

通道处理机的工作过程

在用户程序中使用访管指令进入管理程序，由CPU通过管理程序组织一个通道程序，并启动通道
通道处理机执行CPU为它组织的通道程序，完成指定的数据输入输出工作
通道程序结束后向CPU发送中断请求，CPU响应该中断请求，第二次进入操作系统，调用管理程序进行处理

字节多路通道：每连接一个中低速外围设备，传送一个字节，再连接下一个设备传送一个字节

选择通道：每连接一个高速外围设备，传送n个字节，再连接下一个设备传送n个字节

数组多路通道：每连接一个高速设备，传送一个数据块，再连接下一个设备传送一个数据块

通道处理机流量分析

通道流量：单位时间内能够传送的最大数据量

通道最大流量：通道在满负荷工作状态下的流量

$T_S$ 设备选择时间 $T_D$ 传送一个字节所用的时间

$p$ 一个通道连接的设备台数 $n$ 每一个设备传送的字节个数

$k$ 一个数据块中的字节个数

字节多路通道

$f_{BYTE}=\sum_{i=1}^p{f_i}\\ f_{MAX.BYTE}=\frac{p\cdot n}{(T_S+T_D)\cdot p\cdot n}=\frac{1}{T_S+T_D}字节/秒$

选择通道

$f_{SELECT}=\max_i\{f_i|i=1,...,p\}\\ f_{MAX.SELECT}=\frac{p\cdot n}{(\frac{T_S}{n}+T_D)\cdot p\cdot n}=\frac{1}{\frac{T_S}{n}+T_D}字节/秒$

数组多路通道

$f_{BLOCK}=\max_i\{f_i|i=1,...,p\}\\ f_{MAX.BLOCK}=\frac{p\cdot n}{(\frac{T_S}{k}+T_D)\cdot p\cdot n}=\frac{1}{\frac{T_S}{k}+T_D}字节/秒$

为保证通道不丢失数据，通道的实际流量应不大于通道最大流量

出现设备请求未响应

原因分析：对所有设备的请求时间间隔取最小公倍数，在这一段时间内通道的流量是平衡的，但在任意一台设备的任意两次时间传送请求之间并不能保证都能得到通道的响应

解决方法：

增加通道的最大工作流量

动态改变设备的优先级

增加缓冲存储器

第五章标量处理机

指令的重叠执行方式

指令的三个阶段：取指令，指令分析，指令执行

顺序执行方式

一次重叠执行方式

二次重叠执行方式

先行控制技术的基本结构

流水线的基本原理

把一个重复的过程分解为若干个子过程，每个子过程可以与其他子过程同时进行

每个流水段的末尾或开头必须设置一个流水寄存器

流水线的分类

线性和非线性

线性流水线：每一个流水段都流过且仅流过一次，能用流水线连接图唯一表示
非线性流水线：某些流水段之间有反馈回路或前馈回路，必须用流水线连接图和流水线预约表共同表示

单功能和多功能

单功能流水线：只能完成一种固定功能的流水线
多功能流水线：流水线的各段通过不同连接实现不同功能

静态和动态

静态流水线：同一段时间内，各个功能段只能按照一种方式连接，实现一种固定功能
动态流水线：同一时间段内，各个功能段可以按照不同方式连接，同时执行多种功能

线性流水线的性能分析

吞吐率 Throughput

$TP=\frac{任务数}{完成所有任务用时}=\frac{n}{T_k}$

各流水段时间相等时

$TP=\frac{n}{(k+n-1)\Delta t}\quad TP_{max}=\lim_{n\to\infty}{TP}=\frac{1}{\Delta t}$

各流水段时间不等时

$TP=\frac{n}{\sum_{i=1}^k{t_i}+(n-1)\max{(\Delta t_1,...,\Delta t_k)}}\quad TP_{max}=\lim_{n\to\infty}{TP}=\frac{1}{\max{(\Delta t_1,...,\Delta t_k)}}$

加速比 Speedup

$S=\frac{顺序执行时间}{流水线执行时间}=\frac{T_0}{T_k}$

效率 Efficiency

$E=\frac{n个任务占用的时空区}{k个流水段总的时空区}=\frac{T_0}{k\cdot T_k}$

非线性流水线的调度

找出一个最小的循环周期，按照这个周期向流水线输入新任务，流水线的各个功能段都不会发生冲突，且流水线的吞吐率和效率最高

禁止向量：预约表中每一行任意两个X之间距离的集合

冲突向量：$C=(C_mC_{m-1}…C_2C_1)$，m是禁止向量中的最大值

状态图：将冲突向量逻辑右移，若移出去的位是1，则表示用相应启动距离向流水线输入新任务时会产生功能段冲突；若移出去的位是0，则表示不会产生功能段冲突，将右移结果与初始冲突向量逻辑或，结果为新的状态

简单循环：在状态图中各种冲突向量只经过一次的启动循环

启动距离：连续输入两个任务之间的时间间隔

全局相关

动态分支预测技术

根据近期转移是否成功的记录来预测下一次转移的方向
- 最近的一次或几次转移是否成功的信息记录在转移指令中
- 用一个高速缓冲栈保存条件转移指令地转移目标地址
- 用Cache保存转移目标地址之后的n条指令
所有的动态转移预测方法都能够随程序的执行过程动态地改变转移的预测方向

静态分支预测技术

转移预测的方向是确定的，在程序实际执行过程中转移预测的方向不能改变
可以只用软件实现，也可用硬件来实现，还可以在转移的两个方向上都预取指令

提前形成条件码

乘除法，两个源操作数的符号相同结果为正，相反结果为负
乘法，有一个操作数为0，乘积为0
除法，被除数为0，商为0；除数为0，结果溢出
同号加或异号减，结果符号与第一操作数相同
异号加或同号减，结果符号与绝对值大的操作数相同
溢出及是否为0可通过一个比较器提前产生

第六章向量处理机

向量处理机的两种基本结构

存储器-存储器结构

利用几个独立的存储器模块来支持相对独立的数据并发访问，从而达到所要求的存储器带宽

寄存器-寄存器结构

构造一个具有所要求带宽的高速中间存储器，并实现该高速中间存储器与主存储器之间的快速数据交换

向量处理方式

横向处理方式：向量计算按行的方式从左到右进行

纵向处理方式：向量计算按列的方式自上而下进行

纵横处理方式：分组处理，组内纵向，组间横向

向量链接技术的基本原理和执行时间的计算

向量运算中的数据相关和功能部件冲突

两条流水线的链接技术：当前一条指令的结果寄存器可以作为后继指令的操作数寄存器时，多条有数据相关的向量指令并行执行

执行时间的计算

向量长度N 相加6拍相乘7拍在存储器读数6拍打入寄存器1拍启动功能部件1拍

三条指令串行
$[(1+6+1)+N-1]+[(1+6+1)+N-1]+[(1+7+1+N-1)]=3N+22$
前两条指令并行，第三条串行
$[(1+6+1)+N-1]+[(1+7+1)+N-1]=2N-15$
采用向量链接技术
$1\left\{\begin{aligned}启动访存\\送浮加部件\end{aligned}\right\}+6\left\{\begin{aligned}访存\\浮加\end{aligned}\right\}+1\left\{\begin{aligned}存V_3\\存V_2\end{aligned}\right\}+1\left\{\begin{aligned}送浮乘部件\\送浮乘部件\end{aligned}\right\}+7\left\{\begin{aligned}浮乘\end{aligned}\right\}+1\left\{\begin{aligned}存V_4\end{aligned}\right\}+N-1=N+16$

向量循环开采技术

当向量的长度大于向量寄存器的长度时，必须把长向量分成长度固定的段，采用循环结构处理这个长向量

向量处理机的性能评价

向量指令处理时间 $T_{vp}$

$T_{vp}=T_s+T_{vf}+(n-1)T_c$

$T_s$为向量流水线的建立时间 $T_{vf}$为向量流水线的流过时间 $T_c$为流水线的时钟周期

$T_{vp}=(T_{start}+n)T_c$

启动时间$T_{start}$为从第一条向量指令开始执行到还差一个时钟周期就产生第一个结果所需的时钟周期数

编队：能在一个时钟周期内一起开始执行的几条向量指令（同一编队中的向量指令一定不存在流水部件冲突和数据相关性）

$T_{all}=\sum编队=\sum_{i=1}^m{T_{vp}^{(i)}}=\sum_{i=1}^m(T_{start}^{(i)}+n)T_c=(T_{start}+mn)T_c$

当向量长度$n$大于向量寄存器长度$MVL$时需要分段开采

$T_{all}=\lceil\frac{n}{MVL}\rceil\times(T_{start}+T_{loop})+mn$

最大性能 $R_\infty$

当向量长度为无穷大时向量处理机的最高性能

$R_{\infty}=\lim_{n\to\infty}\frac{向量执行序列中浮点运算次数\times 时钟频率}{向量指令序列执行所花费的时钟周期数}$

一个例子

半性能向量长度 $n_{1/2}$

当向量处理机的性能为其最大性能的一半所需要的向量长度

接上例

向量长度临界值 $n_v$

对于某一计算任务而言，向量方式的处理速度优于标量串行方式处理速度时所需要的最小向量长度

继续接上例

第七章互联网络

互连网络的作用

互连网络是一种由开关元件按照一定的拓扑结构和控制方式构成的网络

用来实现计算机系统中节点之间的相互连接
已成为并行处理系统的核心组成部分
对整个计算机系统的性能价格比有着决定性影响

互连函数

恒等函数 输入输出相同

$I(x_{n-1}x_{n-2}...x_0)=x_{n-1}x_{n-2}...x_0$

交换函数 第k位取反

$C_k(x_{n-1}x_{n-2}...x_0)=x_{n-1}x_{n-2}...\bar{x_k}...x_0$

均匀洗牌函数 循环左移一位

$\sigma(x_{n-1}x_{n-2}...x_1x_0)=x_{n-2}...x_1x_0x_{n-1}$

子洗牌 低k位循环左移一位

$\sigma_{(k)}(x_{n-1}...x_k{x_{k-1}...x_0})=x_{n-1}...x_k{x_{k-2}...x_0x_{k-1}}$

超洗牌 高k位循环左移一位

$\sigma^{(k)}({x_{n-1}...x_{n-k}}x_{n-k-1}...x_0)={x_{n-2}...x_{n-k}x_{n-1}}x_{n-k-1}...x_0$

逆混洗 循环右移一位

$\sigma^{-1}(x_{n-1}x_{n-2}...x_1x_0)=x_0x_{n-1}x_{n-2}...x_1$

蝶式互连函数 最高位和最低位互换

$\beta(x_{n-1}x_{n-2}...x_1x_0)=x_0x_{n-2}...x_1x_{n-1}$

子蝶式 低k位中的最高位和最低位互换

$\beta_{(k)}(x_{n-1}...x_k{x_{k-1}...x_0})=x_{n-1}...x_k{x_0x_{k-2}...x_1x_{k-1}}$

超蝶式 高k位中的最高位和最低位互换

$\beta^{(k)}({x_{n-1}...x_{n-k}}x_{n-k-1}...x_0)={x_{n-k}x_{n-2}...x_{n-k+1}x_{n-1}}x_{n-k-1}...x_0$

反位序函数 位置全部颠倒

$\rho(x_{n-1}...x_0)=x_0...x_{n-1}$

子反位序 低k位的位置颠倒

$\rho_{(k)}(x_{n-1}...x_k{x_{k-1}...x_0})=x_{n-1}...x_k{x_0...x_{k-1}}$

超反位序 高k位的位置颠倒

$\rho^{(k)}({x_{n-1}...x_{n-k}}x_{n-k-1}...x_0)={x_{n-k}...x_{n-1}}x_{n-k-1}...x_0$

移数函数 算每个位置的十进制

$\alpha(x)=(x\pm k)\mod N$

PM2I函数 一种移位函数

$PM2_{+i}(x)=(x+2^i)\mod N\\ PM2_{-i}(x)=(x-2^i)\mod N$

静态互连网络的基本类型

各节点之间有固定的连接通路，且在运行中不能改变

线性阵列

环和带弦环

循环移数网络

在环上每个节点到所有与其距离为2的整数幂的节点之间增加一条附加链

树形和星形

胖形树

网格形与环网形

超立方体

n立方体把两个n-1立方体中相对应的节点用链路连接起来

带环立方体

用n个节点构成的环取代n立方体中的每个节点

动态互连网络

由交换开关构成、可按运行程序的要求动态地改变连接状态

多级立方体网络

采用2功能（直送和交换）的2x2开关
当第$i$级开关处于交换状态时，实现$Cube_i$互连函数
一个N输入的多级立方体网络有$\log_2 N$级，每级用$N/2$个2x2开关模块

Omega网络 多级混洗交换网络

采用4功能的2x2开关
级间互连采用均匀洗牌连接方式
一个N输入的多级立方体网络有$\log_2 N$级，每级用$N/2$个2x2开关模块

Note

SDU ComputerSystemArchitecture

本文作者: 31
本文链接: http://uuunni.github.io/2022/06/24/CSAreview/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

SDU计算机网络复习笔记上一篇

SDU软件工程复习笔记下一篇

SDU计算机体系结构复习笔记

第一章 概念