内容

整数,浮点数,十进制数的计算机表示

整数的表示

无符号整数

有符号整数

  1. 原码:第一位表示符号,0表示正,1表示负。
  2. 反码:正数不变,负数就是将每一位取反。
  3. 补码:正数不变,负数就是在反码的基础上+1即取反+1.

补码运算

加减法运算

补码的加减法运算除了从低到高一位一位相加,模拟人的竖式运算之外,还有一种快速计算的方法。即Carry Look Ahead Adder先行进位加法器。这种加法首先会把每一位的PG算好(1t),然后给CLA计算出进位C,同时下面的按位加法器把每一位XxorY的值计算出来(2t),最后根据每一位的异或和每一位前一位的进位,再取异或,可以计算出每一位的最终值(3t)。最高位的进位也输出。

如果是部分先行进位加法,比如4个8位的先行进位加法器,则下一个要等上一个的t3过完后才能得到他的C0,但是他因为可以实现进行PG的运算,则得到C0后两个t之后就可以把下一个加法器需要的C0算出来。因此总时间是3t+2t+2t+5t=12t就可以算出32位结果。

乘除法计算——布思乘法

直接将被乘数放入共64位的结果寄存器的低32位中。然后Y0=0,每次计算出一个Yi-Yi-1。如果这个数是0直接将结果寄存器右移。如果为-1,就将结果寄存器高32位加-X。如果是1,就将结果寄存器高32位+X。最后可以产生一个64位的结果。

除法过于难以理解,略过。

浮点数的表示

IEEE754标准

  1. IEEE754能够表示的数的范围是从0~1.1111…*2^127^。
  2. 指数位的范围是0~255.其中0和255有特殊含义,表示非规约数。取0时默认的隐藏整数部分为0,指数为-126.取255时,如果小数全为零,表示正负无穷,否则表示NaN。
  3. 其他情况下为规约数,即实际指数是指数位-127,默认隐藏整数部分为1

运算

加减法

基本思想:通过把指数小的向指数大的移动指数,把两个数的小数点对齐然后相加。

乘除法

重点问题:小数点问题

乘法产生双倍位数的结果,并且小数位数在这个大结果中等于两个源的小数位数之和。

除法产生单倍位数结果,格式和被除数相同。

DCB数

DCB数每4位01串作为一个单元,表示0-9的十进制数。最开始的一个单元表示符号。1100表示+,1101表示-。

运算

加法

每一位的进位单独判断,如果超过了9(不包括9)就在+6.

减法

对减数求补:逐位+6然后按位取反。然后和被减数相加。如果有大进位说明结果是正数,把进位换成1100。否则说明结果为负数,前加1101.

内存

内存的分类

RAM 随机访问存储器

两种类型:

  1. 动态 DRAM:这种内存使用电容器存储,结构简单但是要经常刷新。

    刷新策略上:集中刷新,每个读写动作后刷新,和比较好的异步刷新,即每过一定时间在空闲时间内去刷新。

    更进一步的是SDRAM,能够随着时钟节奏来传送数据,和DDR SDRAM,时钟周期的开始和结束都传输数据,能够传输双倍的数据。

  2. 静态 SRAM:这种使用复杂的门电路来存储数据,结构复杂,但是稳定不需要刷新。

Read-only Memory

ROM

普通的ROM一旦出厂不能更改只能读。

PROM

可以由用户写唯一一次,然后就不能改了。

Read-Mostly Memory

EPROM

使用紫外线可以清除整块存储器上的数据。实现再次写入。

EEPROM

使用电进行写入,但是写入速度很慢。

Flash Memory

闪存,可以快速擦除一整块的内容。

内存的组织

由芯片组合成整块内存的方法分为字拓展和位拓展。

Cache

三种映射方式和三种替换策略。

外部存储

磁盘

组成结构

扇区

关于扇区的组织有两种,一种是不管距离中心的远近,每个扇区的角度都是一样的。这种组织虽然方便但是浪费了大量空间。另一种是从中心到外围,将所有的磁道划分成地带,地带内的扇区角度一致,跨地带会增加扇区的数量。这样能更好的利用空间。

扇区内部数据结构

现有一个ID区,有同步字节,位置信息和冗余校验码,然后gap之后是数据区,数据区开头有一个同步字节,最后有2个字节校验码。

访问时间

分为寻道时间,旋转延迟和数据传输时间。

可能出计算题。

光盘

DVD有的可以在两面都有数据

磁带

校验

奇偶校验

奇校验:加上校验位之后一共有奇数个1

偶校验:加上校验位之后一共有偶数个1

奇校验的表达式比偶校验长。

海明码

SEC

设计步骤:

  1. 先用 2^k >= M+K+1 公式算出校验码的位数K。
  2. 然后设计故障字:先将只有一个1的情况对应到相应的校验码出错上。然后剩下的从右往左排,分配给第1~最后一位数据出错的情况。
  3. 最后设计校验码生成函数:对于每一位校验码,去故障字表中挑选这一位对应为1的数据位。如果是基于偶校验的海明码,直接把所有的这些数据位异或。如果是奇校验,再多异或一个1。

计算步骤:将读到的串分为数据和校验码,然后用校验码生成函数对读到的数据部分生成一个校验码。用新校验码和读到的校验码按位异或得到故障字,对应故障字表去找哪一位出错了。

SEC-DED

额外增加一位校验码,这一位校验码的生成函数是:找出故障字表中有且仅有两个1的故障字对应的数据位,把这些数据位进行奇偶校验的异或,得到一个新的校验位。

处理方法:如果读数据后产生的故障字有3个1出现,就说明只有一位数据位出错,并且可以找出和纠正。如果有一个1,说明有一位校验码出错了。如果有两个1说明有两个位出错了但是无法纠正。如果出现更多的1,说明问题很大。

循环冗余校验

有一个人为规定的生成多项式,根据这个多项式写出一个二进制表示,k位。

首先将数据右边补k-1个零,然后用二进制除法去除数据。二进制除法:每次的余数最高位是1就上1,是0就上0,计算下一级余数时按位异或。然后得到一个k-1位的余数,直接将这个余数加在数据后面,这个余数就是校验码。

磁盘冗余阵列

RAID 0

无冗余

RAID 1

镜像

RAID 2

细致划分,使用多余的盘来储存海明码,每个冗余磁盘对应海明码的一位。

RAID 3

细致划分,使用多余一个盘存奇偶校验码。

RAID 4

划分成块,奇偶校验码集中储存在一个盘。

RAID 5

划分成块,奇偶校验码分散到各个盘中。

读写问题:每次修改数据时要两读两写:读要修改的块的原始数据,读要修改的块对应的校验码,计算出新的校验码(P’=B \bigoplus B’ \bigoplus P),写入数据,写入校验码。

RAID 6

使用两个奇偶校验码盘,分散到各个盘。每个盘有两个奇偶校验码块P和Q。

虚拟内存

分区

固定大小的区

非固定大小的区:问题是内存空间碎片化。

分页

将所有可能载入的程序内存分成页,将内存分成相同大小的页框。

会议室例子

所有学生被划分成大小相同的小组,比如8个人一个组,一开始会被安排在班里,有些甚至还不在班里坐着

会议室的座位被分成排,和组人数相同,8个座位一排。

校长发出逻辑地址:要问第4组第5个同学问题。

班里有一张表,按照组的顺序从上往下记录着每个组的情况。页表,实际上在内存里。

每个组的情况包括:在不在会议室,有没有被修改,发言情况(用于替换),位置。页表项

位置分为三种:在会议室,那么这里记录着这个组坐在会议室哪一排。在班里,记录着在班里的位置(一个引用)。不在班里(未加载),这时记录为null。

校长手里有张表,只记录了一部分的页表项。但是看的非常方便,这样校长就不需要下来去内存里面看了。快表

从页到页框的映射方式是关联映射,即一个组可以坐在会议室的任何一排。

物理地址一定是一个内存里的地址。如果要访问的数据还不在内存里,一定是先通过一定的替换策略把这一块放入内存然后再返回一个内存地址。在这个例子里,内存地址是会议室座位号。比如第4组被安排到了会议室第6排,那校长要找的物理地址就是65即第六排第五个。

快表和页表之间类似于Cache和主存的关系。快表也有关联映射和组关联映射,有相应的替换策略。

访存问题:

  1. 访问页表+1次内存访问。
  2. Cache未命中+1次内存访问。
  3. 访问磁盘并将磁盘数据写入内存不算访存,也就是invalid只+1磁盘访问,不加内存访问。

段式和段页式

段页式是先分段然后段内分页。

总线

类型有系统总线,芯片内总线(如CPU总线),交流总线(如IO总线)

还可以分为专用和复用总线。

由地址线,数据线和控制线组成。

裁决类型

要兼顾优先级和公平原则。

集中式

链式

传递令牌

优点:方便决定优先级,可以灵活的增加新的设备。

缺点:不能很好的兼顾公平,而且没有容错性,链上的一台设备出现问题全完蛋。

计数器问询式

有一个计数器,不断向所有设备叫号发送问询,如果被叫到的设备有使用需求就相应。

优点:可以很好地兼顾公平,而且设备出现问题没关系。

确定:加入大量的线,而且需要别的手段识别设备。

独立请求式

通过一个裁决器,所有设备连接到它上,有需求的时候就发送请求,如果冲突则由裁决器来决定谁来用。

优点是很快而且优先级可以通过编程决定,可以变化。

缺点是需要很多额外的线,而且裁决器有复杂的控制逻辑。

分散式

自己选择

优先级较高的设备都有一条总线占用线,优先级低的设备要在这些线都没被占用的情况下使用总线。

冲突探测式

每台设备想用总线的时候直接用,但是发送信息后要监听自己发送出去的信息,如果被混杂说明有冲突。此时冲突的两台设备跳出总线,随机停顿后重新回来,大概率可以解决冲突。

总线时间控制

同步式

根据时钟周期的节奏来传递数据,命令和地址。但是由于会有时间偏差所以不是很可靠。

异步式

挥手

需要注意的一点是,一次从内存读取数据的完整操作中一共有七次挥手,第四次虽然看起来不像但是等待的时间也要按照一次挥手时间来处理。

半同步

有一条等待线。CPU和内存按照时钟周期来运作,但是有时候如果内存没有按照约定把数据准备好就设置等待线,让CPU等待。

分割总线事务

一个总线事务分成多个来做,中间需要长时间等待的地方把总线放掉让其他的设备来用。

总线带宽和数据传输率

可出计算题,一定是结合总线通信方式中的同步式和异步式来考。注意如果是同步式,一定要等到一个时钟周期开始的时候才可以操作,不能在半个时钟周期的地方开始传输数据。比如时钟周期50ns,即使内存230ns准备好数据也只能能到250ns的时候才可以开始传输数据。

提供总线带宽的方法:加快时钟速度,整块传输(因为通常读块中的前一些比较慢,后面的很快),加大总线的宽度(加线),分割总线事务,或者将地址线和数据线分开。

总线层次结构

双总线结构有系统总线和内存总线配合,有系统总线和IO总线配合。。

多总线结构有还可能有DMA等等。

指令集

指令执行周期

取指周期,间址周期,执行周期,中断周期

一条指令分为操作码和地址段。地址段就是操作数

操作码

数据传输,算术计算,逻辑计算,IO,转化,系统控制,控制转移(分支跳转调用)

操作数

地址,数字,字符,逻辑值。

大端和小端:大端是后面的存在地址高的地址单元,而小端是后面的存在前面的内存单元中。

寻址模式

立即数寻址

地址字段的就是操作数,不用访存了

直接寻址

地址字段就是操作数的有效地址

间接寻址

地址字段存的是操作数的地址的地址

如果是一次转移,只需要访问一次内存

寄存器寻址

地址字段是操作数所在的寄存器名

寄存器间接寻址

地址字段是存有操作数所在内存地址的寄存器名字

偏移寻址

寄存器相对寻址

通常是PC相对寻址,就是指操作数的有效地址是PC中的值加上指令中的偏移量。用这个结果去访问内存就可以取得操作数。

基址寻址

有一个(人为规定的默认的)基址寄存器,有效地址是这个基址寄存器中内容加上指令里的偏移量。

变址寻址

有一个变址寄存器,有效地址则是变址寄存器加上指令里的偏移量。

栈寻址

有一个寄存器存有栈顶指针,栈顶指针里面指向一个内存地址。所以实际上就是寄存器间接寻址。

指令设计

位的分配

著名问题:多格式指令条数问题

变长度指令

CPU结构和功能

CPU组成

寄存器

用户可见寄存器
  • 通用寄存器
  • 数据寄存器
  • 地址寄存器
控制和状态寄存器

一般情况下用户不可见

  • 程序计数器PC
  • 指令寄存器IR
  • 内存地址寄存器MAR
  • 内存数据缓冲寄存器MBR
  • 程序状态字寄存器PSW(Flags)
  • 其他。。比如页表指针,中断和栈指针之类的

间址周期

考虑到间接寻址,就有可能要访问多次内存,于是在指令周期和执行周期中间加一个间址周期,如果存在间接寻址的情况,就用这个时间去先访问一次内存。

数据流

流水线

如果是正常运行的k步流水线一切顺利时执行n条要用k+(n-1) 周期的时间。

如果是碰到异常情况比如分支跳转和数据冲突,会耽误时间,这个时候中间有多少个没有意义的指令就要耽误多少个周期。比如跳转在最后一步之前发现跳转,并且马上开始执行新的指令,那么中间有(k-2) 条指令都没有意义了,就会多这么多个周期。

提速率:

nkt/(k+(n-1)+k1)t

冒险

结构冒险

硬件访问冲突

解决方法:空泡、增加额外设备和读写各占半个周期法

数据冒险

下一步要用上一步的结果

增加直接连线,调整指令顺序,空泡

控制冒险

跳转预测

一直跳,总是不跳

状态机,历史表。注意:如果是状态机的话没一个循环语句用一个自己的状态机。

控制单元

微操作

可以分为取指周期,间址周期,执行周期和中断周期。可以互相调换位置而结果不受影响的两个微操作是可以在同一个时间内发生的。

ICC:instruction cycle code,指令周期码。本质上类似一个状态机,指示现在指令运行到了四个周期中的哪一个了。

定义微操作首先要知道处理器的最小组成部分:ALU,寄存器,内部数据通路,外部数据通路,控制单元。所以可以定义四种微操作:寄存器之间的数据转移,寄存器到系统总线之间的数据传输,系统总线(外部通路)到寄存器的数据传输,激活ALU的算术或者逻辑运算。

那么控制单元的一系列控制都是由微操作组成的,而且这些微操作有限,一开始就被人为地写在了硬件中。控制单元执行的过程无非就是对微操作进行排序和执行。

控制单元的输入和输出

控制单元的输入有:

  • 时钟
  • 指令(来自指令寄存器IR)
  • 各种状态标志Flags
  • 来自总线控制线的控制信号(如中断请求)

控制单元的输出是控制信号,分为:

  • 指向处理器内部的控制信号。有激活ALU和激活内部数据通路。
  • 指向外部的控制信号。有向总线控制线发送的控制,激活外部设备和外部数据通路

内部总线

需要运算的数必须先存入ALU上面的Y寄存器中。

控制单元实现

硬连线实现

硬连线实现其实就是构建一个囊括所有情况的真值表。表的输入有IR,时钟,Flags,总线控制线的控制信号。如果从逻辑层面来讲,输入和输出的关系是关于指令,时钟,flags等等的布尔函数。可以把这些函数表示出来。注意:输出的每一位都有特定的含义,因此函数应该是每一个输出位都有一个函数。

微程序和微指令

每一个微操作都可以用一个控制字来表示,控制字就是把所有的输出位并在一起。

那么一条微指令就有以下组成部分(通常而言):

  • 控制字(又可以分为处理器内部的控制信号和到系统总线控制线的控制信号)
  • 跳转条件(也可称作地址选择字段)
  • 地址字段

所有的微指令一开始都被人为地写进了控制单元的Control Memory即控制储存器中。有一个排序逻辑单元来根据现在的情况和微指令中的跳转条件来计算出下一条微指令的地址(在控制储存器中的地址),把这个地址放入控制地址寄存器(类似于PC)中。然后发送读指令的信号,把控制地址寄存器中的地址对应的指令读到控制数据缓冲寄存器中。注意,对于控制单元来说,读出指令就已经完成了执行指令的过程,因为控制数据寄存器的前面控制字的位和对应的控制电路直接相连,就实现了控制信号的发出。然后控制数据寄存器中后面的位数用来帮助排序逻辑单元计算下一条微指令地址。

那么控制单元的任务就是:计算下一条微指令的位置和读(即执行)下一条微指令。

排序的方式还有几种:

  • 双地址段微指令,每次排序逻辑根据外部条件从这两个地址中选择一个。
  • 单地址段,有一个默认的地址就是控制存储器的顺延下一个微指令。
  • 可变格式。有一位来决定这条微指令是双地址段微指令还是单地址段微指令。

比较

微程序控制单元更便宜,简化了控制单元结构,也更少出错。

但是运行起来比较慢。

Input/Output

I/O 模块

功能:解读命令,交换数据,报告状态,地址识别。

并行接口和串连接口。

I/O 操作方式

程序式IO

cpu轮询

中断驱动IO

CPU给IO模块下达命令然后干别的事,IO准备好之后发起中断,CPU回来处理

中断的响应优先级和处理优先级

屏蔽字

DMA

突发式(Stop CPU)

直接从CPU手下获得一整块内存周期,自己传数据。

计算题

周期挪用(周期窃取)

DMA每准备好一块数据,就挪用一个周期传输

计算题

交替分时访问法

内存周期一半给cpu用一半给内存用。

适用于CPU工作周期比主存存取周期更长的情况下。

CPU周期长,天然每个内存周期就有一段是cpu不用的。

DMA连接方法
  1. 直接连在总线上,和IO模块并列
  2. 作为IO模块连接总线之前的接口
  3. 连接在IO总线上,作为IO总线和系统总线的接口