计算机组织结构期中复习.docx
《计算机组织结构期中复习.docx》由会员分享，可在线阅读，更多相关《计算机组织结构期中复习.docx（68页珍藏版）》请在冰点文库上搜索。
计算机组织结构期中复习
计算机组织结构
ⅠIntroduction总述
结构architecture
对程序员可见（程序员必须清楚）
包括：
指令集、各种数据类型的大小
组织organization（内部实现）
对程序员透明（程序员没有必要清楚）
包括：
控制信号、存储技术
计算机发展史:
第一代电子管/真空管ENIAC十进制
IAS二进制存储程序思想
亦叫做冯诺依曼模型
分为•CentralArithmetical（CA）运算器
•CentralControl（CC）控制器
•Memory（M）存储器
•Input（I）/Output（O）输入输出
四部分组成
第二代晶体管
第三代到N代集成电路
摩尔定律（Moore'slaw）:
在一个芯片上所放的晶体管数目每年翻倍（69年前）/18个月翻倍（69年后）
说明计算机逻辑内存单元制作更加便宜/会变得更小/提高了运算速度/降低了电源和散热要求/集成电路的可靠性更高
计算机性能:
CPU:
速度Memory:
容量/速度I/O:
容量/速度
主要目的是提高CPU速度
CPU的性能:
时钟:
时钟率（Hz）:
每秒能处理的基本指令
时钟周期（s）:
1/时钟率
Clocktick?
指令处理每秒钟执行的百万指令数（MIPS）每秒百万个浮点操作指令数（MFLOPS）
例题：
1.在逛商店时，你听到一位顾客问店主，他在商店里能买到的最快的计算机是什么。
店主回答说“你正在看的是Macintosh，最快的Mac机以1.2GHz时钟速率运行，如果你想要最快的机器，你应该购买我们的2.4GHz的IntelPentium4计算机。
”店主的说法对吗？
为什么？
解：
不能依靠时钟频率来衡量一台计算机的性能，更科学的衡量标准是每秒所执行的浮点数计算有多少百万次。
相同的功能在不同的指令集中需要的指令数量是不同的，同一条指令在不同计算机上需要的时钟周期是不同的。
而且，即便在指令相同的情况下，如果采用并行或者流水线等技术，也可以加速程序的执行
2.ENIAC是一个十进制机器，用10个真空管来代表一个寄存器。
任何时刻只有一个真空管处于ON状态，表示10个数字中的一个。
假定，ENIAC有能力使多个真空管同时处于ON和OFF态，这种表示方法是否合理？
为什么？
不合理，当ENIAC有能力使得多个真空管同时处于ON或者OFF状态，应该采用二进制，可以减少所需要的真空管数量，而且如果10个真空管中出现了多个处于ON状态，则会无法判断是哪个数字。
3.IBM360Model75的指令周期的时间是360Model30的5倍，而相对性能确提高为原来的50倍。
为什么会出现这种现象？
计算机系统性能衡量的常用标准是每秒进行多少百万次的浮点数运算，虽然IBM360Model75的指令周期是360Model30的5倍，但它可能采用不同的指令集使得完成相同功能的指令数目减少，或者采用了流水线、并行等技术，使得计算机的性能得到了提高。
4.时钟以固定频率f（或等价地说，以固定周期时间t）来驱动处理器，这里t=1/f。
程序的规模能用程序所包含的机器指令数，或者指令计数IC来衡量。
不同的指令会要求不同的时钟周期数来执行。
一个重要参数是程序的平均每条指令周期数（averagecyclesperinstruction，CPI）。
执行一个给定程序所需的处理器时间能表示成：
T=IC×CPI×t
在指令执行期间处理器只是做了部分工作，一部分时间是花费在处理器与存储器之间的字传送上。
在后一种情况下，传送时间取决于存储器周期时间，而它会比处理器周期大很多。
我们能将上面等式改写成：
T=IC×[p+（m×k）]×t
这里，p是用于译码和执行指令所需的处理器周期数，m是所需的存储器访问次数，k是存储器周期时间和处理器周期时间之比。
上面等式中5个性能因子（IC,p,m,k,t）受到4个系统属性影响：
（1）指令集设计（亦称指令集体系结构）；
（2）编译技术（在由高级语言程序产生机器语言程序时编译器如何有效）；（3）处理器实现；（4）Cache和存储器的层次。
请用表格形式说明这4个系统属性对这5个性能因子的影响。
指令集规模小编译技术好处理器快存储层次多
IC变多变少无影响无影响
P变多变少无影响无影响
M变多变少无影响变多
K无影响无影响变大变小
T无影响无影响变小无影响
5.处理器性能的一个普通度量是指令执行的速率，表示为每秒百万条指令（MIPS）。
请用时钟速率和CPI来表示MIPS速率。
解：
设时钟频率为f，平均每条指令周期数为CPI.所以平均每条指令所需要的时间为CPI/f
1/（CPI/f）*10^6=f/CPI*10^-6即每秒指令的百万条指令数
6.一个测试程序在一个40MHz的处理器上运行，其目标代码有100000条指令，由如下各
类指令及其时钟周期计数混合组成：
请确定这个程序的有效CPI、MIPS速率和执行时间。
CPI=（45000+32000*2+15000*2+8000*2）/（45000+32000+15000+8000）
MIPS=f/CPI*10^-6
T=100000/MIPS
ⅡATop-LevelViewofComputerFunctionandInterconnection总观计算机功能及内部联系
冯诺依曼模型（thevonNeumannmachine）:
计算机组成:
I/O主存（Mainmemory）
系统总线（Systembus）CPU
内存:
数据和指令被存贮在内存中内存中的数据按地址寻找顺序执行指令
问题:
主存与CPU之间的传输速度差距越来越大
解决:
包含寄存器（cache）缓冲数据减少对内存访问量
增加每次读取的字节数
I/O:
和CPU/内存交换数据
问题:
和CPU/内存的速度差距越来越大
解决:
缓冲新的接口技术
CPU:
顺序执行指令数据和指令被存贮在内存中按地址寻找数据
问题:
等待I/O设备时CPU的空闲问题
解决:
中断（Interrupt）:
嵌套中断处理（Nestedinterruptprocessing）
连续中断处理（Sequentialinterruptprocessing）
总线:
链接两个或更多设备是一种共用的传输介质
数据传输类型:
地址线数据线控制线
总线类型:
专用总线（高效传输/规模成本高）
复用总线（节省空间和成本/复杂的机制）
总线仲裁:
总线可被多个设备监听但每次只能由其中一个发出信息
集中式/分布式
计时:
同步/异步/半同步/分割
总线宽度（Buswidth）:
每次传输的位数
ⅢCache寄存器
内存设计瓶颈:
容量速度价格成本
实际要求:
大容量高速
解决方式:
层次式设计
Cache基本思想:
运用一个更小更快的寄存器来减少内存的访问次数
是对主存的部分拷贝
处于CPU和主存之间可能集成在CPU或其他模块中
Cache的基本工作机制
1.Check:
当处理器试图从主存访问数据时，先检查该数据是否在Cache中
2.若命中，数据直接从Cache传输至Cpu
3.若没有命中，Cpu访问主存，将一块数据传输至Cache中，然后再从Cache传输到Cpu
如何判断命中
Cache中使用标签（tags）来判断需要访问的数据在主存中的地址。
判断丢失后为何将主存中的块（block）传输至Cache
引用的局部性原理
1.时间的局部性
2.空间的局部性
3.序列的局部性
传回一块利用空间局部性，提高命中率，节省时间
计算平均访问时间
Cache使用的一些策略
1.增加容量：
缺点成本过高，且会增加Tc
2.映射函数：
1．直接映射：
设j为主存中的块数，C为Cache中的行数，则主存中每块对应在Cache中的行数i=jmodC
（Cache中每行存一块）
例：
假设Cache中有四行，每行有8个字，主存中有128个字，因此需要7位来表示地址。
每块中有8个字，所以用3位来表示字（即字长），Cache中有4行，因此中间用2位来表示占据的是哪一行，M=16（主存中的块数）C=4（Cache中的行数）,所以n=4-2=2,2位表示Tag即标签位。
优点：
简单，匹配快，查找快
缺点：
抖动
比如如果一个程序每次都轮流查找映射于同一行的两个块，会大大影响命中率
所以这种映射方法适用于大容量的Cache
2．关联映射
规则：
每个块可以被载入任意一行
例：
假设Cache有4行，每行有8个字，主存包含128个字，
那么主存用7位地址，3位为字长，剩下四位作标签。
优点：
防止抖动，
缺点：
复杂而且浪费资源。
3．组关联映射（折衷）
策略：
Cache被分为多个组，假设j为主存中的块数，S是Cache中的组数，那么相应的块对应在Cache中的组号s=Smodj
K路组：
k=C/S,每组的行数
组内采用关联映射
例：
假设Cache中有4行且被分成2组，每行8个字，主存中含有128个字节，所以7位地址。
三位表示字长，因为组数=2，中间一位用来表示位于哪一组，最高3位用作Tag.
即M=16，S=2所以n=4-1=3.
比较:
K=1直接映射K=C关联映射
关联度（Correlation每块对应寄存器中行的可能数）:
直接映射1关联映射C组关联映射K
相关度越小，命中率越低，check时间更少，Tag长度越短
3.替换机制
LRULeastRecentlyUsed最近最少用
FIFOFirstInFirstOut先进先出
LFULeastFrequentlyUsed最不常用
4.写操作策略
1．写入
为保证Cache与主存的一致性，往Cache写入时同时也要往主存写入
但降低写入速度，容易产生瓶颈
2．写回
在Cache中增加一位（脏位）表示是否被修改过，若“脏”，则替换整个块时前将其写回
减少写入操作，但会有不必要的麻烦（如输出时会取得主存中未修改的数据）
策略：
输出时候强制修改主存
5.行的大小即每个块的容量
行变大，提高命中率。
行再变大，也可能降低命中率（原因:
Cache总大小不变时，行变大，减少了行数，使得替换频繁）
6.Cache的个数
单个：
方便集成到处理器，简化电路设计
层次式：
L1L2
设计复杂：
要保证3个之间数据的一致性
L2可以使用另外一条路，也可以放在处理器上
注意：
L1与L2的关系可以类比于单个Cache时候Cache与主存的关系
7.数据与指令是否分开
例题分析：
关于Cache的映射关系
1.假设Cache有4K字，每行32字。
对十六进制主存地址：
111111、666666、BBBBBB，请
用十六进制格式表示如下信息：
（1）直接映射Cache的地址格式，
（2）全关联映射Cache的地址格式，（3）两路组关联Cache的地址格式。
（提示：
每个映射方式下，需要将标记、
块内地址等分开表示。
）
解：
Cache字数：
4K=4*2^10=2^12总共12位地址
块的大小32=2^55位字长行数2^7用7位表示
主存地址为6位16进制即24位二进制，其中5位表示字长.
1．直接映射：
标记位：
19-7=12
行数:
7
块内地址：
5
2．全关联映射
标记为19
块内地址5
3．两路组关联映射
组数2^66位表示组数
标记为19-6=13
块内地址5位
以BBBBBB为例化为二进制位101110111011101110111011
直接映射101110111011101110111011
BBB5D1B
全关联映射101110111011101110111011
5DDDD1B
两路组关联映射101110111011101110111011
17771D1B
对命中的判断以及LRU算法的应用
2.计算机系统包含容量为32K×16位的主存，按字编址，每字16位。
Cache采用4路组关
联的映射方式，数据区大小为4K字，主存块大小为64字。
假设Cache初始时是空的，
处理器顺序地从存储单元（每个存储单元中包含1个字）0,1,…,4351中取数，然后再
重复这一顺序9次，并且Cache的速度是主存的10倍，同时假设块替换用LRU算法。
请说明使用Cache后的改进。
主存共32K=2^15个字，每块2^6=64个字，所以一共2^9块.
Cache共2^12字所以一共2^6=64行采用4路组关联
组数=2^4=16
所以标记位为9-4=5
组：
4
设Cache的速度为t，则主存的速度为10t
采用cache:
第一次：
0miss11t
1-63hit1t*15
64miss11t
64-127hit1t*15
4351/64=68
所以一共有68次miss.
第二次：
因为第一次中0123行中的内容被替换成了64656667块.
根据LRU原则0123换下的是16171819那一路，以此类推、
012316171819323334354849505164656667永远miss
所以综上p=（4352*10-68-20*9）/43520=99.43%
时间10V/（V+10*（1-0.9943））=9.5倍
LRU算法与FIFO算法的应用与比较
3.假设主存中的5个块{1,2,3,4,5}映射到cache的同一组，对于主存块访问地址流
{1,2,3,4,1,2,5,1,2,3,4,5}，在3-路组关联、4-路组关联、5-路组关联方式下，分别
说明LRU算法和FIFO算法的命中情况。
下面只考虑3-路组关联：
LRU算法
111444555333
22211111144
3332222225
最近最少使用的123412512
FIFO
111444555555
22211111333
3332222244
最先进的11234111255
多层次Cache的计算
4：
对一个有两级Cache的系统，定义：
TC1=第一级Cache存取时间；TC2=第二级Cache
存取时间；H1=第一级Cache命中率；H2=组合的第一/二级Cache命中率。
请给出读
操作时间的表示。
（提示：
需要假设主存的存取时间）
解：
设主存存取时间为Tm
T=Tc1+（1-H2）Tm+（1-H1）Tc2
5:
假设某处理器的时钟频率为1.2GHz，当L1cache无缺失时的CPI为1（即CPU可以快
速地从L1cache中读取指令，并在1个时钟周期内完成）。
访问一次主存的时间为100ns
（包括所有缺失处理），L1cache的局部缺失率为2%。
若增加一个L2cache，并假定
L2cache的访问时间为5ns，而且其容量足够大到使全局缺失率仅为0.5%。
分析增加
L2cache后处理器执行程序的效率提高了多少？
解：
1.2Ghz=1.2*10^9次/s所以处理一次需要1/1.2=0.833nm
未增加L2时平均读取一条指令的时间为0.833+0.02*100=2.833nm
增加L2后平均读取一条指令的时间为0.833+0.005*100+0.02*5=1.433nm
2.833/1.433=1.97倍
ⅣInternalMemory主存
存储位元:
有0/1两个稳定状态
可以至少被写入一次
可以读取状态
RAM（RandomAccessMemory,随机访问存储器）:
特性:
可以简单迅速地读取和写入数据
易失性（volatile）
类型:
DRAM（DynamicRAM,动态随机访问存储器）:
电容存储需要刷新
SRAM（StaticRAM,静态随机访问存储器）:
门
相似:
易失性都需要提供电能来维持数据
区别:
DRAM设计简单但是需要刷新
SRAM比DRAM更快，但是集成度低造价高
DRAM多用于主存SRAM多用于寄存器
ROM（ReadOnlyMemory,只读存储器）:
特性:
非易失性（Nonvolatile）
可读取但是不可写入数据
应用:
微编程系统程序函数表
问题:
无出错空间成本高
PROM（ProgrammableROM,可编程只读存储器）:
特性:
非易失性（Nonvolatile）
只能写入一次:
电子写入并且需要特殊的环境
与ROM的区别:
更加灵活方便
Read-MostlyMemory:
读的次数比写的次数多很多非易失
类型:
EPROM（ErasablePROM,可擦除编程只读存储器）:
特性:
可读写紫外线擦除整块比PROM更贵
EEPROM（ElectricallyEPROM,可电擦除编程只读存储器）:
特性:
可写入并且无需擦除数据可按字节写入（覆盖）比EPROM擦除速度快但造价更高
FlashMemory（闪存）:
特性:
电擦除可擦除几块集成度高
寻址单元（AddressingUnit）:
包含同样类型的几个位元
寻址模式:
字（Byte）更加常见/字节（Word）
存储阵列:
线的复用先行后列
刷新:
集中刷新（CentralizedFresh）停止读写，集中刷新，会有一段时间停止工作：
死区
分散刷新（DecentralizedFresh）不会出现死区但是时间过长
异步刷新（AsynchronousFresh）高效
芯片的引脚:
Address/Data/Vcc（powersupply）/Vss（groundpin）/CE（chipenable）/Vpp（programvoltage）
WE（writeenable）/OE（outputenable）/RAS（rowaddressselect）/CAS（columnaddressselect）
模块的扩展:
字扩展/位扩展/字位扩展
位扩展：
增加数据量。
地址线数量不变，数据线数量增加
例如：
使用8个4K*1的芯片来组成4K*8的芯片
字扩展：
增加寻址空间
地址线数目增加
数据线数目不变
例如：
使用4个16K*8bit的芯片组成64K*8bit的主存
内存是字扩展
主存=RAM+ROM主存大小=RAM大小
其他的DRAM:
SDRAM（SynchronousDRAM,同步动态访问存储器）:
只允许在一个特定时刻传输
DDRSDRAM（Double-data-rateSDRAM,两倍速率SDRAM）
RambusDRAM/CacheDRAM
纠错:
奇偶校验:
奇校验:
校验位=所有位作异或后再与1异或若1的个数为奇数，则校验码为0,
偶校验:
校验位=所有位异或若1的个数为偶数，则校验码为0
出错条件：
比较C’（新读出的校验码）与C’’（重新计算后得到的校验码）（作异或），注意，与原先的数据无关。
结果为1时，有奇数位出错，为0，没有出错或者偶数位出错。
优点:
成本低
缺点:
只能知道出错不能找出错误之处
海明码:
分K组产生校验码
将一个M字节的数据分成K组，则有K位校验码
2^k>=M+k+1
记八字节的数,海明码为4位.
规则：
1.将两次海明码作异或，若所有位上都是0，则没有错误
2.若有一位是1，则海明码错误，不需要纠正
3.超过一位是1，根据相应规则可以判断哪一位出错，并纠正。
记8字节数D=D8D7D6D5D4D3D2D1，它的四位校验码是C=C4C3C2C1
C1=D1⊕D2⊕D4⊕D5⊕D7
C2=D1⊕D3⊕D4⊕D6⊕D7
C3=D2⊕D3⊕D4⊕D7
C4=D5⊕D6⊕D7⊕D8
纠错码110010111010100110000111011001010100001100100001
数据位D8D7D6D5D4D3D2D1
C4C3C2C1
D8D7D6D5C4D4D3D2C3D1C2C1包括校验码的12位的储存顺序
例1：
D=01101010使用偶校验
C1=D1⊕D2⊕D4⊕D5⊕D7=1
C2=D1⊕D3⊕D4⊕D6⊕D7=1
C3=D2⊕D3⊕D4⊕D8=0
C4=D5⊕D6⊕D7⊕D8=0
所以为011001010011
例2:
若取得时12位为011001010011
D’=01101010得到C’=0011
C’’=0011
S=C’’⊕C’=0000
所以没有出错
若取得时12位为011101010011
D’=01111010C’=1010
C’‘=0011
S=C’’⊕C’=1001所以第五位出错
SEC只能纠错一位
SEC-DEC增加一位校验码C5=D1⊕D2⊕D3⊕D5⊕D6⊕D8
如果有一位数据发生错误，则有三位的校验码将发生改变
CRC（CyclicRedundancyCheck,循环冗余校验码）:
例子说明一切：
数据：
100111。
生成校验码1001（x^3+1）校验码111
例题分析：
关于各种存储器的比较以及应用
1.说明下面概念间的区别
RAM和ROM
RAM,随机访问存储器，可读可写，但是易失
ROM，只读存储器，只能读不能写，不具有易失性
两者的共同点都是半导体存储器
SRAM和SDRAM
SRAM静态随机访问存储器，相对于动态的DRAM，不需要刷新电路来维持位元的状态
SDRAM是DRAM的一种，需要刷新来维持位元状态，但是相比普通的DRAM，它采用外部时钟与处理器同步，具有更高的数据传输速率
PROM、EPROM、和EEPROM
PROM，可编程只读存储器，非易失，可以一次电写入，但之后无法修改
EPROM可擦除可编程只读存储器，可以写入多次，但需要通过紫外光擦除整个芯片的信息，时间长，但是造价相对较低集成度高
EEPROM电子EPROM,可以擦除单个字节，消耗时间相对较短，但是造价贵且集成度低
SDRAM和DDR
DDR是一种特殊的SDRAM，也采用外部时钟与处理器同步，但是与SDRAM相比，DDR允许在一个时钟周期内读/写两次数据，可以加快数据传输速率
2.传统的RAM组织成每芯片只有一位，而ROM通常组织成每芯片多位，请说明原因。
当RAM组织成每芯片只有一位时，所需要的地址线只要一根，这样有利于减少芯片的引脚数
升级会员 