指令的执行过程MIPS
IF(Instruction fetch,取指令)
ID(Instruction decode/register fetch cycle,指令解码)
- 如果该指令只有一个跳转指令,则在此阶段需要根据跳转指令的意义进行比较。如果比较结果是true如果比较结果是false不执行跳转,继续执行下一个指令;
EX(Execution/effective address cycle,执行)
- 计算所需寄存器的值EX这些寄存器的值需要根据指令的意义来计算。根据因指令而异。主要有三种类型ALU计算:1. ALU根据ID计算有效地址单元,最终获得所需的内存地址;2. 根据指令的意义,操作从寄存器中获得的值,如添加两个寄存器的值;3. 立即数的结果根据寄存器的值和补充值计算。
MEM(Memory access,内存访问)
- 若当前指令为Load然后,指令,依据EX计算出的内存地址,从内存中获取对应的值;若当前指令为store,那么,根据EX计算的内存地址和寄存器值将寄存器值存储在内存地址中。其他指令通常不设计内存访问。
WB(Write-back cycle,写回)。
汇编
MIPS指令
https://www.cnblogs.com/jiading/p/12189871.html
R3=R2 396
这个次历访问数组元素加一操作每个元素
等价于下列
int[] array = new int[0]; for (int i = 0; i < 98; i ) {
array[i] = array 1; }
396/4 = 99 数组下标0—98
Lw R1,0 (R2) 读取地址R2的数据到R1寄存器 DADDIU R1,R1,#1 R1寄存器数据 1 sw R1,0 (R2) 将R1写回地址R2 上面做的是 1操作 DADDIU R2,R2,#4 地址R2 4 做地址右移操作 DSUB R4,R3,R2 BNEZ R4,LOOP 以上两个判断i<98(R3-R2)
MIPS的指令序列
延迟等待
没有延迟表
例题:
DADDIU等待LW的值R1
1.寄存器文件可以在一个时钟周期内定向读写同一个寄存器。
- 非save指令
LOAD的MEM操作结束后,写回寄存器,DADDIU即可正常ID解码
因为没有定向技术,所以ID需要等待才能等待Load已经读取完(MEM),然后ID同时,顺便取操作数到寄存器
即下一个指令ID在前一个M之后
- save指令
无冲突
2.假设流水线在1条件下有正常的定向路径
-
非save指令
-
- load指令:有定向技术,可以先ID,然后等待Load已经读取完(MEM)定向发送到DADDIU的EX段
下一个指令EX在前一个M之后
-
- add等待指令:等待ALU操作(EX结果定向发送至段)DADDIU的EX段
下一条指令的EX在前一条的EX之后
- save指令
无冲突
第一章
计算机系统结构的定义及研究对象
- 定义:程序员所看到的计算机系统的属性,即概念性结构和功能特性
- 计算机系统结构主要研究软硬件的功能分配和软硬件界面的确定
- 趋势:硬件比例越来越高
计算机系统的层次结构
----硬件----
-
-
-
- 硬件
- 微程序
-
-
----以下虚拟机----
-
-
-
- 机器语言 (软硬件分界)
- 操作系统
- 汇编语言
- 高级语言
- 应用语言
-
-
评价计算机系统的常用方法
性能和成本
Amdahl定律 加速比
Sn = T0 / Tn = 1/((1-Fe) + Fe/Se)
CPU性能公式
CPI 每条指令所花的时钟周期
IC 指令条数
t 时钟周期长
CPU时间 = 时钟周期数 * t = CPI * IC * t
MIPS
IPC 每个时钟周期平均执行的指令条数
Fz是主频
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-nDnTM0ld-1656418432333)(https://myblogimgbed.oss-cn-shenzhen.aliyuncs.com/img/1948cf9409137fc9c33dfcc72558486f.svg)]
MFLOPS
只能用于衡量机器计算浮点数的性能
冯·诺依曼结构及其发展
- 存储程序 运算器为中心 集中控制 指令和数据一样可以参与计算
- 改进:以存储器为中心 总线结构 分散控制
透明性、系列机、兼容性、模拟与仿真等概念
透明性
不关心 CPU型号对于应用程序员来说是透明的
兼容性
向后兼容(最重要):在某一时刻生产的机器上运行的目标软件能够直接运行于更晚生产的机器上。
系列机
计算机组成是系统结构的逻辑实现,计算机实现是计算机组成的物理实现
有相同的系统结构,但是采用不同的组成和实现的一系列计算机系统
模拟与仿真
在一台现有的计算机上实现另一台计算机的指令系统
模拟
- 纯软件
- 解释/编译方法
- A:宿主机 B:虚拟机
仿真
- 有硬件
- 微程序
- A:宿主机 B:目标机
系统结构差别大的难以完全用仿真
了解计算机系统的分类方法
按处理机个数和种类划分
SMP 对称多处理机
MPP 大规模并行处理机
Cluster 机群
按器件
电子管 晶体管 集成电路(LSI) 大规模集成 (VLSI)智能计算机
按并行度
CU控制器 PU运算器 MM存储器 IS指令流 DS数据流
-
佛林Flunn分类法
-
- 指令流 数据流
- SISD SIMD MISD(实际不存在) MISD
-
库克分类法
-
- 指令流 执行流
- SISE SIME MISE MIME
-
冯泽云分类法
-
- 最大并行度:Pm = n * m (字宽 * 位宽)
- WSBS WSBP WPBS WPBP
-
汉德勒ESC分类法
-
- 程序级k 操作级d 逻辑级w
- t = (k,d,w)
第三章
存储系统的定义及主要性能
定义:各种信息储存和交换的中心
速度 T
命中率H 不命中率F
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-zCHQejv2-1656418432334)(https://myblogimgbed.oss-cn-shenzhen.aliyuncs.com/img/af4af141a43859868eb760dda05fe202.svg)]
N1:对M1的访问次数
N2:对M2的访问次数
- 访问周期[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-dWy9xsnv-1656418432334)(https://myblogimgbed.oss-cn-shenzhen.aliyuncs.com/img/02ff3f43bd9337ce6f88fdc9d49ac1e8.svg)]
- 访问效率[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-89L7OlUh-1656418432335)(https://myblogimgbed.oss-cn-shenzhen.aliyuncs.com/img/6d55e4e1093d37461c74d14cfb4bf45c.svg)]
预取技术提高命中率:不命中时,把M2存储器中相邻几个单元组成的一个数据块都取出来放入M1。
n:数据块大小与数据重复次数的乘积
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-LmhEorvB-1656418432335)(https://myblogimgbed.oss-cn-shenzhen.aliyuncs.com/img/6477f075d7840eb5556c510b5f577773.svg)]
容量 S
整个系统容量等于M2
方法:(1)只对M2编址 M1不编址或只在内部编址
(2)设计一个大容量逻辑空间 M1 M2都映射到逻辑地址空间
价格C
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-GK6eqbjw-1656418432336)(https://myblogimgbed.oss-cn-shenzhen.aliyuncs.com/img/feec89f2517f305147ebb0c3b84a0f95.svg)]
S2>>S1 时 C≈C2
【.】两种存储系统
Cache存储系统:Cache + 主存 【提高速度】速度≈Cache 容量和价格≈主存
虚拟存储系统:主存 + 磁盘存储器 【扩大容量】速度≈主存 容量和价格≈磁盘
RAM:随机访问存储器 断电丢数据
- SRAM:静态 不需要刷新电路
- DRAM:需要刷新电路
SSD和HDD 硬盘
- SSD:固态硬盘 快 贵
- HDD:机械硬盘 慢 便宜
并行存储器和无冲突访问存储器的工作原理
主存两大指标:延迟(cache解决)和带宽 并行以及无冲突解决的是带宽低的问题
并行存储器
= 单体多字存储器 同时拿出n个字
缺点:访存效率不高 容易发生冲突
- 取指令冲突:如果一次读取的m个指令字中有分支指令,而且分支成功,那么该分支指令之后的指令是无用的
- 一次取出的m个数据不一定都是有用的。另一方面,当前执行指令所需要的多个操作数也不一定正好都存放在同一个长存储字中
- 写数据冲突:写入有可能变得复杂
- 读写冲突:当要读出的数据字和要写入的数据字处于同一个长存储字内时读和写的操作就无法在同一个存储周期内完成
【.】多体交叉访问存储器
- 高位交叉访问(竖式)
用于扩容
高位交叉编址指的是对存储单元按体内地址顺序存放,(故又称顺序存储)
作用于多用户多任务或者指令和数据分开,每一列都互不相干,扩容很方便
- 低位交叉访问(横式)
和并行存储器目的一样,都是为了提高速度(带宽)
流水线式,在一个时间段内拿出一整串,不容易发生冲突
低位交叉编址:对存储单元矩阵按行优先进行编址
无访问冲突存储器
解决冲突的本质是让访问时可以并发的读取不同存储体,而不是只读取一个
一维数组
向量子集(一维数组)的元素逐次按2的整数次幂相间访问
- 先间隔2^0=1访问
- 再间隔2^1=2访问
- 间隔2^2=4访问
存储体个数为质数,保证不冲突
二维数组
要求:nxn二维数组要求按行、列、对角线、反对角线访问,且在不同变址位移量都能实现无冲突访问
列冲突
对角线冲突
解决方案1
通用,但是会浪费一个存储体的资源
在上述第2个的基础上,解决列冲突即可,解决方案如下
- 存储体个数m>=n,且取质数
- 同一列相邻元素在存储体中错开d1个存储体
- 同一行相邻元素在存储体中错开d2个存储体
- m=22p+1, d1=2p,d2=1
计算公式:
解决方案2
有前提,要满足存在 n = 22p
优先选这个,节省存储体资源
虚拟存储系统的工作原理
在没有虚拟存储器之前,按照 冯诺依曼计算机工作原理:存储程序、程序控制 cpu是无法运行比主存空间更大的程序的。【提高容量】
分类:页式虚拟存储器、段式虚拟存储器 、段页式虚拟存储器
虚拟存储的实现:本质是没有对主存空间扩大的,只是增加一个页表,cpu给的是逻辑地址(页号 + 页内偏移地址),根据MMU找到页表,根据页号到页表中查看对应有效位,有效位为1则该页存在于主存,将页号转化为物理地址(这个页在主存中的地址)然后与页内偏移地址进行拼接,就可以找到要的数据。如果为0,则从外存(磁盘)中调入主存(如果主存满了,则发生页面置换)。
- MMU(页表寄存器):指出页表的基址,用于在主存中找出页表
- cpu地址:逻辑地址(页号 + 页内偏移地址)
- MMU找到页表,页号定位到具体的页表项,查看有效位
- 页式虚拟存储,所有的外存分为一页页,页表项里存放对应全部外存的所有页号,因此cpu可根据这个页表访问到外存的所有数据,从而实现运行内存扩大,但是实际内存不变
例题
虚拟存储器中加快地址变换的方法
引入TLB前命中
访问主存两次
- 在主存查找页表一次
- 根据页表查找对应页一次
引入TLB前未命中
访问主存三次
- 在主存查找页表一次
- 从外存将所需要的页调入主存一次
- 缺页异常处理之后再次进行虚实地址转换访问主存拿到目标页
TLB
根据局部性原理,增加一个小容量、高速存储部件存放当前访问页表地址变换条目,该存储部件称为TLB(Translation Lookaside Buffer:地址转换后备缓冲器)。 按照功能可以称为快表。
使用快表之后,可以加快访问速度,一般可以不去查找页表,直接查快表,节省一次访问主存
虚拟存储系统的页面替换算法
最佳置换算法
FIFO先进先出
LRU最近最久未使用
LFU最久未使用算法
需要为每个页面设置移位寄存器,访问则将高位置1,定时右移动,硬件实现与LRU完全相同,但是移动时间更久
简单Clock置换算法
只考虑访问位
近似LRU,但是使用的硬件更少
改进Clock置换算法
考虑访问位A + 修改位M
优先级方面:
- A= 0 M= 0 最佳
- A= 0 M= 1 没访问过 但修改过
- A= 1 M= 0 没修改过 访问过
- A= 1 M= 1 修改+访问过
执行流程:
- 先找A= 0 M= 0进行淘汰
- 1类找不到,则寻找A= 0 M= 1进行淘汰,遍历过程中将A= 1 的都置为A= 0
- 1、2类都找不到,此时只剩下3、4类,且A=1的在第二轮循环都被置为0 再次重复1操作,寻找A= 0 M= 0(实际上寻找的是A= 1 M= 0)
- 1、2、3类都找不到寻找A= 0 M= 1进行淘汰(实际上寻找的是A= 1 M= 1)
Cache存储系统的地址映象及变换方法
CPU工作时给出的是主存的地址,要从Cache存储器中读写信息,就要将主存地址转换为Cache存储器的地址,这种地址转换称之为地址映像。
Cache的数据结构:有效位 + 标志位 + 偏移量(块内地址)
一个cache地址对应一个字的数据
相联存储器
快速判断主存对应的地址是否在cache中
步骤如下:
-
把拿到的主存地址通过不同的映射方式拿到标志key
-
使用多路并发比较线路进行在cache中查找符合的
-
- 在有效位为1的块中进行查找(提高效率)
- 并发比较标记字
- 找到则使用块内地址找到精准的唯一地址
- 拿到该地址的数据
-
找到就放进符合寄存器取出命中行的数据
全相联映射
工作原理
主存地址的标记放进比较器寻找是否命中,命中则取出对应cache的数据
案例理解
假设cpu需要的访问序列如下,
- 1F对应000011111 在cache中找不到,去主存中取整个块,在cache中随机找一个空的块放入,不仅放块数据,还有放标志位,有效位变为1 ,然后在cache中取出对应块内地址的数据(11对应1C)
- 找20 24 (同1F)
- 找到1E000011110 cache命中 直接拿出1D数据
特点
- 主存地址 = 主存块号 + 块内地址
- cache利用率高
- 块冲突率低
- 淘汰算法复杂(要一一检索所有cache块)
- 适用于小容量cache
直接映射
工作原理
案例理解
- 1F 0000 111 10 从主存中拿到后放到第7cache块
- 20 24 miss 同1F
- 1E 0000 11110 hit 直接拿到1D数据
- 44 0010 001 00 先找到第1个cache块 比较标志tag 不一致 miss 从主存中取出覆盖
特点(与全相联完全相反)
- 主存地址 = 主存区号 + 区内块号 +块内地址
- cache利用率低
- 块冲突率高
- 淘汰算法简单(只比较一个)
- 适用于大容量cache
组相联映射
工作原理
案例理解
- 1F 00001 11 11 11对应第三组 miss 从主存取出 随机放入组内块
- 20 24都miss 同上
- 1E 00001 11 10 11对应第三组 存在标志00001 hit 直接取出块内10对应的1D数据
- 48 54 都miss
- 107时 10000 01 11 对应第一组 没有对应标志块,进行替换
特点(折中)
- 主存地址 = 主存组号 + 组内块号 +块内地址
- 折中
- k路组相联的k表示一组内多少行 所以8路就是全相连 1路就是直接映射
例题1 直接映射
\1) 直接映射 主存地址 = 区号 + 区内块号 + 块内偏移量
- 块内偏移量 cache块大小 16B 所以4位表示
- 区内块号就是cache行数 64KB/16B 2^12bit 12位
- 区号: 32-4-12 = 16位
2)数据字长32位 16B 可以知道有4个字 因此块内偏移量的4位:2位字偏移 2位字节偏移
3)容量 = cache行数 * 每行的位数 = 2^12行 * (1+16+128)
例题2 组相联映射
\1) 组相联映射 主存地址 = 组号 + 组内块号 + 块内偏移量
- 块内偏移量 cache块大小 8*32bit=32B 所以5位表示
- 组内块号就是cache组数 cache行数16KB/32B 2^9bit 所以组数2^9bit/4 = 2^7bit 7位
- 组号: 总位数(16MB = 2^24位)组号24-7-5 =12位
2)100个字 在主存中占100%8 = 13块<2^7组 所以都在主存的第0组
不命中的字是0 8 16…
3)加速比由第二问得出
Cache存储系统的块替换算法
FIFO
- 每次进来一个,就把所有块计数器+1
- 计数器 每次淘汰数值最大的(表示最先进来)
LFU 最不经常使用
- 计数器记录的是使用次数累积量 使用到就加一
- 淘汰计数器值最小的 当有多个相同的时,可以配合FIFO或其他使用
LRU 最近最少使用
- 命中则计数器清零 其他加一
- 最终淘汰计数器最大的块
随机替换
随机
- Cache存储系统的一致性问题。
cache命中
当CPU 访存读一个字时,首先 Cache 控制逻辑根据地址判断这个字是否在 Cache 中,若在,就立即送给 CPU,称为 Cache “读命中”;否则,称为 Cache “读不命中”
通常有两种方法解决 Cache 的“读不命中”情况:其一,将主存中该字所在的数据块复制到 Cache 中,然后再把这个字传送给 CPU;其二,启动常规的主存读周期,把此字从主存读出送到 CPU,与此同时,把包含这个字的数据块从主存中读出送到 Cache 中。在以上这两种方法中,都有可能发生 Cache 中行数据的替换,即当 Cache 已没有空闲的位置容纳即将装入的新行时,只能按照某种替换算法选择某一旧行被新行替换掉。
当 CPU 访存写一个字时,Cache 控制逻辑根据地址判断这个字是否在 Cache 中,若不在,称为 Cache“写不命中”,此时,直接将该字写入主存中,且不再调入 Cache;否则,称为 Cache“写命中”
对于 Cache 的“写命中”通常也有两种方法进行处理:其一,CPU 的写操作既对Cache 也对主存进行,保证主存总是有效的,称为“写贯穿策略”;其二,CPU 的写操作只对Cache 进行,仅当此 Cache 行被替换时,相应的主存内容才被修改,称为“写回策略
虚拟地址cache
第五章
【.】先行控制技术
重叠方式
-
顺序执行
-
- T=3nt
-
一次重叠
-
- T = (1+2n)t
-
二次重叠
-
- T=(2+n)t
- 优秀,但是需要使用先行控制方式
要解决的问题
-
有独立的取指令部件、指令分析部件和指令执行部件,一个集中的指令控制器要分解成三个相对独立的控制器,【存储控制器、指令控制器、运算控制器】
-
解决冲突问题
-
- 取指令、分析指令、执行指令都可能要访问存储器
技术
- 缓冲技术:在工作速度不固定的两个功能部件之间设置缓冲栈,用以平滑它们的工作
- 预处理技术:把进入运算器的指令都处理成RR型指令
- 三个独立的控制器
存储控制器、指令控制器、运算控制器
-
四个缓冲栈
先行指令缓冲栈、先行操作栈、先行读数缓冲栈、 后行写数栈
时间并行性
-
- 装入时间 = k-1 全空–>全满, 指第一个任务进入流水线到填满流水线的时间
- 排空时间 = k-1 全满–>全空, 指第n个(最后一个)任务进入流水线到输出流水线的时间
分类
- 线性流水线&非线性流水线
线性(无反馈电路) 非线性(有)
-
处理机级流水线(指令)& 部件级流水线(操作)& 处理机流水线(宏流水线 —— 多个处理机处理一个数据流)
-
单功能流水线 & 多功能流水线
-
- 多功能又可分为静态流水线 & 动态流水线
- 静态流水线:同一时间段只可以实现一种功能
-
- 动态流水线:同一时间段可以实现不同功能
- 标量流水线 & 向量流水线 (数据表示不同)
- 同步流水线 & 异步流水线 (控制方式)
- 顺序流水线 & 乱序流水线 (输入输出顺序)
流水线的性能分析及计算
吞吐率
定义:
n为任务数,Tk为完成n个任务所用时间
执行时间相等
吞吐率
最大吞吐率
执行时间不等
Tk=第1个任务流过时间+余后(n-1)个任务*瓶颈段时间
吞吐率
最大吞吐率
解决执行时间不等
- 细分流水线
把原来3t细分为3个t
- 瓶颈段重复设置
把瓶颈段“分成多个部件”重复设置
加速比
时间相等
不设置流水线时 T0 = nt
加速比:
最大:k
时间不相等
效率
看图计算
E = (4nt)/(4*(k+n-1)*t)
相等
最高趋近于1
不相等
E = TP * t (吞吐率 * t)
S = E *k
非线性流水线的调度方法【重点】
预约表:一个任务的处理过程
横坐标是时钟周期
纵坐标是流水段
预约表不唯一 多图可以对应同一个表 一个图也可以对应多个表
启动距离:(全集)连续两个任务的间隔
-
- 将预约表移位即可得到
- 启动循环:不发生冲突的循环数列(启动距离剔除禁止启动距离剩下的集合的所有子集)加入{1,5,7}为剩下的 则{1,5} {1,7}都是启动循环
禁止启动距离:(启动距离的子集 – 要剔除的、会发生冲突的)
-
- 现象:出现同一个格子多个x
- 所有禁止启动距离的集合(数列)叫做禁止向量
任务:
禁止向量 冲突向量(从右往左看):
用初始冲突向量生成所有可能的情况,构建状态转移图
例题
- 计算过程
- 转移图
- 简单循环 遍历找回路
一个预约表对应一个状态图
少了(5,3)
最小启动循环:所有情况中的最小
平均启动距离最小额的恒定循环:循环括号里只有一个,即循环间隔不变
优化调度
插入非计算延迟单元 增加流过时间增加,但平均启动距离最小
插入后的最小平均启动距离变为预约表中“X”最多的一行的X的个数
改变预约表
计算最大吞吐率
直接就是用最小启动距离算
计算插入实际任务的实际吞吐率
- 对最小启动循环为(1,7)这种不是恒定循环的
用最大吞吐率算
- 对于恒定循环(5):直接用公式计算
TP = 任务数/(段数 * t + (任务数-1)*最小启动距离 *t)
数据相关的种类,发生的情况及解决的办法
数据相关
指令相关
下一条指令的指令内容与前一条执行结果相关,导致两条指令不能并行
解决:不允许修改指令,即使得指令内容与其他指令无关
主存操作数相关
指令执行结果写到主存,下一条指令所需要的操作数也来自主存
解决:
- 数据写入到通用寄存器,不写入主存
- 对访问主存请求,写操作优先读操作
- 设置有先行操作栈的处理机,先行操作栈从主存中读入操作数之前,先将主存地址与后行写数栈的所有主存地址比较,发现有正在写的,则先不读,等到写完,再开始读
通用寄存器相关
解决:
变址相关
解决方法:推后分析法、设置专用路径法
控制相关
条件分支指令、转子程序指令、中断等引起的相关
条件分支的解决措施:
1)延迟转移技术
遇到转移指令,依靠编译器把无关的指令调度到转移指令后,当被调度的指令执行完,转移指令的有效目标地址也就计算完毕
2)指令取消技术
分支预测技术
静态预测技术
预测方向固定
- 软件猜测法 通过编译器编译执行
- 硬件猜测法 在先行指令缓冲栈的入口处增加一个指令分析器,当指令分析器检测到转移指令,按照猜测提前预期指令,保留原来的PC地址,如果正确则不影响,错误则需要清空缓冲栈,恢复PC
- 设置两个指令缓冲栈 执行到转移指令时,把转移成功方向的预取指令放在指令缓冲栈 A,把转移失败方向的预取指令放在指令缓冲栈 B,看情况分析哪一个
动态预测技术
两个关键问题:记录历史转移信息,根据转移信息预测转移方向
在Cache中设置转移历史表
可以记录一次或多次
设置转移目标地址缓存栈
用高速缓冲栈保存最近k条转移指令的“转移历史表”和转移目标地址
有转移指令时,比较转移指令地址,匹配则查看转移历史表,进行预测
设置转移目标指令缓冲栈
直接存放转移后的n条指令
提前形成条件码
- 对于大多数运算,在运算部件入口处设置比较器,提前形成条件码
- 对于循环条件转移指令,使用专门的条件码寄存器进行判断条件转移,把条件转移指令和循环体分开
乱序流动方式中的数据相关及解决办法
数据相关
写后读
重定向技术
变量名相关 输出相关
- 读后写
- 写后写
把引起冲突的寄存器通过变量换名技术消除冲突
循环展开实现流水线调度
循环展开实现流水线调度
循环展开是展开循环体若干次,将循环级并行转化为指令级并行的技术
这个过程既可以通过编译器静态完成,也可以通过硬件动态进行
浮点流水线的延迟表
1.指令调度代码
2.循环展开
3.循环展开+指令调度
1.没有循环展开,有指令调度
·每个元素6拍
2.循环展开,没有指令调度
·每个元素7拍
3.循环展开四次+指令调度
·每遍循环时间下降为14个时钟节拍,每个元素平均使用3.5个时钟节拍
·对指令进行移动是有效的
·展开是有用的
·用不同的寄存器
换名
更多的寄存器
·消除额外的测试开销
·在循环展开时分析LOAD/STORE指令进行
·内存地址换名
·保留真相关
单发射、多发射与先行指令窗口
单发射 每个时钟周期平均执行一条指令 ILP = 1
多发射 ILP > 1
先行指令窗口
超标量处理机的指令执行时序及性能
超标量 多发射
增加硬件资源 同时性并行
性能:
超流水线处理机的指令执行时序及性能
多发射 时间并行性 通过各硬件部件充分重叠工作
- 每隔1/n个时钟周期发射一条指令
性能:
第七章
主要的互连函数
恒等置换
交换置换
二进制地址编号中第0位位值不同的输入和输出端间的连接
000 001
001 000
010 011
…
方体置换Cube
n=3时
C0循环表示(0,1), (2,3), (4,5), (6,7)
均匀洗牌置换Perfect shuffle
把二进制位循环左移一位
-
逆混洗:把二进制位循环右移一位
-
-
子混洗 最低k位循环左移一位
-
-
超混洗牌 最高k位循环左移一位
-
均匀洗牌: 由上到下分两组,两组互相交错
- 0组0,1,2,3接至0,2,4,6, 偶数位
- 1组4,5,6,7接至1,3,5,7, 奇数位
- 均匀洗牌循环表示(0), (1,2,4), (3,6,5), (7)
均匀洗牌与非均匀洗牌以它们代表的链路与以交换置换代表的开关多级组合起来可构成Omega(Ω)网络与逆Omega(Ω^-1)网络
蝶式置换Butterfly
将输入端二进制结点号的最高位和最低位互换位置
-
子蝶式:B(k)最低k位的最高位与最低位互换位置
-
-
超蝶式:B(k)最高k位的最高位与最低位互换位置
-
蝶式函数循环表示(0), (2), (5), (7), (1,4), (3,6)
位序颠倒置换Bit Reversal
将输入端二进制地址的位序反过来就得相应输出的地址
-
子反位序函数:最低k位的位序反过来
-
-
超反位序函数:最高k位的位序反过来
-
移数置换A
加减2i置换PM2I
i < n-1
几种典型互连网络的构成方法及特点
4种寻径方式
STARAN、Omega 网络等连接特性
- Omega网络的每一层按照的是均匀洗牌置换Perfect shuffle
- Omega网络是STARAN网络的逆网 把一三级对调 第二级中间两个开关对调
- 画两个图的思路,先画Omega网络,用洗牌置换画出第一层,然后复制多个,数字对应输出,然后对调顺序放到STARAN网(1,3对调,2中间两个对调)然后数字对应
第八章
- 并行处理的基本结构和特点
- 阵列结构
- 典型的并行处理机算法
第九章
- 多处理机结构及特点
- 多处理机通信模型
- MPP、SMP和 Cluster的特点
AMAT
简答题
流水线的特点
流水线的特点:
- 在流水线中处理的必须是连续任务;
- 把一个任务(一条指令或一个操作)分解为几个有联系的子任务,每个子任务由一个专门的功能部件来实现;
- 在流水线的每一个功能部件的后面要要设置一个缓冲寄存器,用于保存本段的执行结果;
- 流水线各段的时间应尽量相等, 否则将引起“堵塞”、“断流”;
- 流水线需要有“装入时间”和“排空时间”,流过时间k
并行性
**答:**在同一时刻或同一时间间隔内完成两种或两种以上工作,只要在时间上相互重叠,均存在并行性。
分类:
同时性--指两个或多个事情在同一时刻发生的并行性;
并发性--指两个或多个事情在同一时间间隔内发生的并行性。
CISC RISC
CISC结构特点:机器指令系统庞大复杂。
RISC结构特点:机器指令系统简单,规模小,复杂度低。
CISC的问题:
- 指令系统庞大,一般200条以上;
- 指令操作繁杂,执行速度很低;
- 难以优化生成高效机器语言程序,编译也太长,太复杂;
- 由于指令系统庞大,指令的使用频度不高,降低系统性能价格比,增加设计人员负担。
RISC的问题;
- 由于指令少,在原CISC上一条指令完成的功能现在需多条RISC指令才能完成,加重汇编语言程序设计负担,增加了机器语言程序长度,加大指令信息流量。
- 对浮点运算和虚拟存储支持不很强。
- RISC编译程序比CISC难写。
由于RISC和CISC各有优缺点,在设计时,应向着两者结合,取长补短方向发展。
分别从执行程序的角度和处理数据的角度来看,计算机系统中并行性等级从低到高可分为哪几级?
答:
从处理数据的角度来看,并行性等级从低到高可分为:
(1)字串位串:每次只对一个字的一位进行处理。这是最基本的串行处理方式,不存在并行性;
(2)字串位并:同时对一个字的全部位进行处理,不同字之间是串行的。已开始出现并行性;
(3)字并位串:同时对许多字的同一位(称为位片)进行处理。这种方式具有较高的并行性;
(4)全并行:同时对许多字的全部位或部分位进行处理。这是最高一级的并行。
从执行程序的角度来看,并行性等级从低到高可分为:
(1)指令内部并行:单条指令中各微操作之间的并行;
(2)指令级并行:并行执行两条或两条以上的指令;
(3)线程级并行:并行执行两个或两个以上的线程,通常是以一个进程内派生的多个线程为调度单位;
(4)任务级或过程级并行:并行执行两个或两个以上的过程或任务(程序段),以子程序或进程为调度单元;
(5)作业或程序级并行:并行执行两个或两个以上的作业或程序。
访问的局部性原理
是取决于存储器访问模式频繁访问相同值或相关存储位置的现象的术语。
1、时间局部性:是指若一条指令被执行,则在不久的将来,它可能再被执行 2、空间局部性:是指一旦一个存储单元被访问,那它附近的单元也将很快被访问
采用组相联映象,LRU 替换算法的 Cache存储器,发现等效访问速度不高,为此建议:
- 增大主存容量;
- 增大 Cache的块数(块的人小不变);
- 增大组相联组的大小(块的大小不变);
- 增大块的大小(组的大小和Cache总容量不变);
- 提高Cache本身器件的访问速度。
计算机系统结构的Flynn分类法是按仆么来分类的?共分为哪儿类?
- SISD 单处理机计算机
- SIMD 并行处理机
- MISD (流水线计算机)
- MIMD (多处理机)
计算机指令集结构设计所涉及的内容有哪些?
(1) 指令集功能设计:主要有RISC和CISC两种技术发展方向。
(2) 寻址方式的设计。
(3) 操作数表示和操作数类型。
(4) 寻址方式的表示:可以将寻址方式编码于操作码中,也可以将寻址方式作为一个单独的域来表示。
(5) 指令集格式的设计:有变长编码格式、固定长度编码格式和混合型编码格式三种。
降低Cache失效率的方法
- 强制性失效
当第一次访问一个块时,该块不在Cache中,需从下一级存储器中调入Cache,这就是强制性失效
- 增大块大小 预取技术
- 容量失效
如果程序执行时所需的块不能全部调入Cache中,则当某些块被替换后,若又重新被访问,就会发生失效。这种失效称为容量失效。
- 增大容量防止抖动
- 冲突
在组相联或直接映象Cache中,若太多的块映象到同一组(块)中,则会出现该组中某个块被别的块替换(即使别的组或块有空闲位置),然后又被重新访问的情况。这就是发生了冲突失效。
- 提高相联度
并行处理机
并行处理机定义: 多个PE按照一定方式互连,在同一个CU控制下,对各自的数据完成同一条指令规定的操作