计算题方法&要点

一、计算机性能计算

关键指标：

  • ff：时钟频率，单位时间内执行最基本操作的次数（单位时间内的时钟周期），单位Hz
  • tt：时钟周期，执行每次操作最基本的时间，时钟频率的倒数，单位s
  • CPIiCPI_i：执行指令i所需要的周期数
  • CPICPI：程序中每条指令的平均需要的周期数
  • T：一个程序的处理时间
  • MIPS：每秒百万条指令

公式：

  • T=Ic×CPI×tT = I_c \times CPI \times t 计算程序执行时间
  • MIPS=IcT×106=fCPI×106MIPS = \frac{I_c}{T \times 10^6} = \frac{f}{CPI \times 10^6}（通常用的更多的是后面的公式，即知道计算机的频率和程序的CPI就可以求出MIPS）
  • MFLOPS=Nfloating−pointopT×106MFLOPS = \frac{N_{floating-point op}}{T \times 10^6}（每秒百万条浮点数操作，相当于将MIPS的公式1中的Ic换成浮点数操作的个数）

注意点：

  • 一定要注意单位换算，1s = 10^3ms = 10^6us = 10^9ns
  • 有的时候如果想不起来公式，可以通过理解的办法去思考，例如计算MIPS即计算每秒百万条指令，只需要算出一秒钟可以执行几条指令，可以通过将程序的总指令数除以程序的总执行时间去算，而程序的总执行时间就是程序的时钟周期数除以程序每秒钟可以处理的时钟周期数（频率）。
  • 算数均值就是将所有样本加起来除以样本数，几何均值就是将所有样本乘起来再开n次方，调和均值就是将所有样本的倒数加起来再整体进行倒数运算，再乘以二。

其他：

各个平均值的使用场景：

  • 算数平均值：适用于度量值的总和也是一个有意义的值的时候（系统执行时间），因为稳定
  • 调和平均值：适用于计算整体效率的情况（系统的执行速率来衡量系统整体价值），因为需要保证系统中不能出现太小的极端。太小的极端会对调和平均值产生显著影响。
  • 几何平均值：计算相对性能（基准测试），所有数据需要被赋予相同的权重。

二、整数、浮点数二进制表示计算

知识点：

整数：最左边符号位，其余数值位

  • 原码：最左边符号位，其余位数的大小表示数值大小本身。
  • 反码：原码符号位不变，其余为取反
  • 补码：如果是正数，则为原码不变，如果为负数则原码取反+1
  • 移码：原码整体加减一个偏置常数（主要用于浮点数运算）

负数原码变补码：原码除符号位的其他为取反+1

负数补码变原码：用原码变补码一样的方法再操作一次就能变回去（取反+1）

补码变成相反数：所有位取反+1

注意：有符号整数能够表示的最大值为所有位全取1，最小值是最大值的相反数再减去1（数值上）

浮点数：符号位、阶码、尾数

  • 符号位S：1位，表示正负（确定符号）
  • 阶码E：8位，表示最后的数值有2的几次方（确定大小）
  • 尾数M：23位，表示精确数值（确定精确值）

注意：规格化数的尾数通常在最前面有一位隐藏位为1

规格化表示：(−1)S×M×2E(-1)^S \times M \times 2^E

注意： 阶码E是移码，通常偏置常数为127，因此这里E实际表示的值应该为E的原码减去127。

规格化数：阶码不为全0或全1

通常，移码的偏置常数应该是最高位取1，其他位取0所得的数（无符号数）减去1。例如：6位阶码的移码应该是63

非规格化数：特指阶码全为0，但是尾数不为0的数，这种数也可以表示数值，不过与一般规格化数的区别是尾数中的隐藏位为0

非规格化表示：(−1)S×0.bbb...b×2−126(-1)^S \times 0.bbb...b \times 2^{-126}

要点

十进制与二进制的转换方法：

  • 整数十进制转二进制，对十进制进行短除法，结果把每一位的商从下往上写出来
  • 整数二进制转十进制：用每一位的基数去求和
  • 十进制小数转二进制浮点数尾数：每次尾数乘以2，如果大于等于1就减1并取该位商为1，否则取商为0，循环此步骤直到为0或精度达到要求。最后的结果把每一位的商从上往下写出来

三、int与float在计算机中的转换计算

知识点：

int在计算机中占用4字节，float在计算机中也占用4字节。double占用8字节

判断会不会丢失精度可以从有效位的位数来判断。

  • int的有效位为32位，float的有效位为24位，因此int精度比float高，int转float可能丢失精度
  • float可表示的最大数远大于int，因此float转int也会导致不相等。
  • 因此，int转float或者float转int都可能丢失精度
  • double的有效位和最大可表示数值都比int和float大，因此int和float转double都不会丢失精度

在代入具体数值时，需要判断的是表示这个数值需要多少位的精度

  • 假如一个整数需要10位表示（1024），那么这个数的有效位低于24，因此转float不会丢失精度。但是如果这个数需要28位表示，则会丢失精度

要点

  • 判断一个数经过变换以后是否还和原来相等的几大注意点：

    1、数据的精度（有效位个数）

    2、数据的最大可表示数

    3、数据会不会溢出
  • int转换成float不会丢失精度的最大值为16777216（2242^{24}），大概是一个八位整数。这是因为浮点数一共只有24位表示数值的有效位
  • 浮点数加减一个数可能会不相等，因为可能发生溢出（但是整数一般不会，因为浮点数的溢出会变成Infinity）
  • 一个整数除以0会抛出异常，一个浮点数除以0会变成非数值NaN

四、DRAM芯片存储计算

知识点

芯片组合方式：

  • 字扩展：横向扩展，变宽，地址变大
  • 位扩展：纵向扩展，变厚，每个地址表示的位数变大
    刷新方式：
  • 集中刷新：所有存储器一起刷新
  • 分散刷新：每一行分开刷新，夹杂在存取的过程当中
  • 异步刷新：每一行按固定间隔刷新（最短刷新信号间隔取决于每单元的最短刷新间隔）

注意点

  • 当使用小的芯片拼成一个大芯片时，如果发生了位扩展（每个地址可表示的位数大于原本的小芯片的每个地址的位数，比如4K*4芯片拼成4K*8），那么在选片时是一次选择多片的。因此，计算地址中用于选片的位数时，不能根据片的个数来推断，而需要根据每个片中包含的内容大小来推断片内选址的位数，然后反推选片位数。
  • 芯片刷新时是每次刷新一行。如果是多个小芯片组合成大芯片，那么刷新大芯片时，所有小芯片都是同时刷新一行的，因此计算大芯片刷新一次需要刷新的趟数也就是计算小芯片刷新一次的趟数，也就是小芯片的行数（与组合方式无关）

五、Cache计算

知识点

主存地址分成：标记、组号、块内地址

映射方式的分类：

  • 直接映射：每组一行（组号即为行号）

  • 全相联映射：一组即为全部（没有组号）

  • 组相联映射：一组包含多行

这三种映射方式其实都可以归为组相联映射，只不过直接映射是1路组映射，全相联是n路组映射（n为Cache行号）

一般而言，一块即为一行

程序访问的局部性：

  • 时间局部性：执行的指令在不久后就会再次执行（常见于循环当中）
  • 空间局部性：访问了一个空间后会接着访问它的相邻空间

替换算法：

  • FIFO：先进先出算法，谁最先进入谁最先被替换
  • LRU：最近最少使用算法，谁最久没有被访问就替换谁
  • LFU：最不经常使用算法：谁被访问的次数最少就替换谁（有可能会导致新来的总是被替换）

Cache一行中的内容：

  • 数据
  • 标记
  • 有效位（1位）
  • 标记位（看情况而定）（如果题目没有说明则不用添加）
  • 脏位（修改位）（1位，在写回时使用）

做题方法

首先先把内存地址示意图画出来，先根据一块（一行）有多少内容算出块内地址的位数，然后算出Cache一共有几行（块）（可以使用Cache总容量除以一行的容量算出来），再根据映射方式算出组号需要几位表示，最后再将内存地址的位数减去组号和块内地址

技巧

  • 一个K即为2的十次方，一个M即为2的二十次方。因此我们拿到一个带有K或M单位的数，可以先算出数字（不看K或M）本身是几次方，然后根据后面带的是K还是M，在指数上对应添加10或20
  • 计算Cache命中率时，可以尝试将Cache画出来，并使用铅笔表示其中的内容。计算循环时，只需要计算第一次循环和第二次循环时候的情况，其余的情况都与第二次循环的情况一致

注意点

  • 需要注意单位，是B（字节）还是b（位）
  • 需要注意编址方式：按字节编址还是按字编址
  • 在计算命中率时，如果刚开始Cache中不存在东西，那么放进去时也算不命中的。最简单的方法是判断有几次Cache中的项没有发生变化
  • 需要注意访问内存包括读内存和写内存。如果涉及到的操作同时包含了读取和写入，需要分开计算次数。（在一些根据程序代码判断命中率的题目中会遇到，例如a[k] =a[k] + 32就涉及到了读和写）
  • 如果有多级Cache，那么当Cache没命中时，它会按顺序访问下一级Cache，并且访问上一级Cache的时间也要加上。这意味着，计算访问时间的时候，如果有多级Cache，并且都没命中，那么就需要将每一级Cache的访问时间和访问内存的时间全部求和，而不能只计算访问内存的时间。

六、磁盘计算

关键指标

  • 旋转速率：单位时间内旋转的圈数，单位rpm（每分钟旋转的圈数）
  • 磁道数：一个面上的磁道个数
  • 扇区数：一个磁道上分为不同扇区的个数
  • 寻道时间：越过一定数量磁道所需要的时间
  • 数据传输率：传输数据时的速度

计算方法

首先，可以先根据旋转速率rpm算出每秒钟旋转的圈数（rmp除以60），然后用你需要旋转的圈数去除以这个数就可以算出旋转延迟。然后可以用你期望跨越的磁道数去除以寻道速度得到寻道时间，最后再通过数据传输率计算传输数据所需要的时间，将其相加，就是读取硬盘数据的时间。

注意点

  • 平均寻道时间和平均旋转时间都是越过一半磁道数和越过一半盘面所需要的时间
  • 一个扇区的默认大小是512B，也就是0.5KB
  • 磁盘读出数据需要分为三步：选择磁道、旋转到对应位置，再是读取数据。因此计算从磁盘上读取数据的时间时需要将三者时间求和，不能漏掉任何一项
  • 从磁道的一段走到另一端跨国的磁道数不为n，而是n-1（n为磁道总数）
  • 注意Mbps和Mb/s是不同的单位，因此你不能通过直接将数据量Mb除以时间s得到Mbps，只能得到Mb/s。而Mb/s转化为Mbps只需要乘以1.02421.024^2。同理，Kb/s转为Kbps只需要乘以1.024，Gb的话乘的就是三次方
  • 同时也需要注意B、KB、MB之间的换算，1MB=1024KB，1KB=1024B，在计算的时候很容易忘记。
  • 必须要注意的一点：你只要切换到了一个新的磁道，你就必须重新算一次平均旋转延迟，因为两个磁道的开始位置并不一定都在相同的一个位置。尽管你可能是你要读的数据超出了一个磁道的范围，然后切换到了第二个磁道，那么当你切换到第二个磁道的时候，你也还是必须要再次加上一个平均旋转延迟，尽管你自己觉得现在的磁头就在开始的位置。

七、冗余磁盘阵列计算

知识点

不同冗余磁盘阵列的冗余盘数量特性：

  • RAID0：没有冗余盘

  • RAID1：所有磁盘中一半为数据盘，一半为冗余盘

  • RAID2：所有磁盘中冗余盘的数量为相当于磁盘数量的长度的海明码中校验位的数量（通常为log2nlog_2n向下取整再+1）（不用纠结如果正好由2n2^n个盘的时候需要几个校验盘，因为这样的话你最后一个盘如果是校验盘，它就不校验任何东西；如果不是校验盘，它就没有被其他校验盘覆盖，这个盘是一个薛定谔的盘，处于校验和不校验的叠加态，所以一般题目不会出成这样）

  • RAID3：所有磁盘中冗余磁盘的数量为1

  • RAID4：所有磁盘中冗余磁盘的数量为1

  • RAID5：所有磁盘中冗余磁盘的数量为1

  • RAID6：所有磁盘中冗余磁盘的数量为2

不同冗余磁盘阵列的小IO读写特性

  • RAID0：读写都只需要一次，性能快
  • RAID1：读写都只需要一次，读略快于RAID0（单盘的两倍），写也只需要一次（数据盘和冗余盘并行写入），虽然受限于较慢磁盘
  • RAID2：读写只需要一次（所有磁盘并行读取），但是由于海明码硬件开销大，已淘汰使用
  • RAID3：读写只需要一次（并行读取全部），都比单盘快（两倍）
  • RAID4：读与RAID0类似（一次），写显著低于单盘（需要修改数据和相应的校验位）
  • RAID5：读与RAID0类似（一次），写显著低于单盘（最坏情况下需要两读两写，不并行，需要四次操作）
  • RAID6：读与RAID0类似，写显著低于单盘（每次写要读三个写三个磁盘）

方法

可以先判断出它一共有几个磁盘，然后根据raid的类型判断出它有几个冗余盘，然后进行进一步的计算。

八、虚拟存储器计算

知识点

  • 虚拟地址分为：虚拟页号和页内地址
  • 物理地址分为：物理页号和页内地址
  • 页表：分为不同的行，需要根据虚拟页号的数字找到页表中对应的行，找到行中的物理页号。
  • 虚拟地址转变成物理地址的方法：将虚拟地址中的虚拟页号取出，查询页表，找到对应行的存储的物理页号，将这个物理页号替换掉原来虚拟地址中的虚拟页号，页内地址不变，就变成了物理地址。

  • TLB类似Cache，都是需要根据标记来找到对应的行。TLB中每一行存放的是虚拟页号中的标记以及对应的物理页号
  • 虚拟地址中的虚拟页号可以划分为标记和组号。我们可以根据TLB中一共有多少组算出组号需要几位，剩下的就是标记的位数。

计算方法

首先，我们可以把虚拟地址和物理地址的长度画出来，然后先根据每个页的大小算出页内地址需要几位，然后减去整个地址的长度就是对应的虚拟页号和物理页号的长度。然后再把虚拟页号分为标记和组号，可以根据TLB中一共有多少组来算出组号的位数，剩下的就是标记的位数。我们就可以根据组号和标记的内容去在TLB中寻找对应的行，如果TLB中找不到，就去页表中直接根据虚拟页号查找，如果还是找不到说明缺页，需要从硬盘中加载这个页。

取到了物理地址之后，如果还涉及到了Cache，就可以使用Cache的方法继续完成。

注意点

  • 页表是存储在内存中的，TLB是存储在Cache中的。
  • 在取出页表或TLB中的物理页号时，需要先检查装入位（valid），如果valid位为1，才说明这一行中存储的是对应的物理页号，否则就需要从硬盘中先加载这个页。

九、指令周期计算和微操作设计

知识点

要执行一个指令，需要经过以下步骤：

  • 将地址从PC传送给MAR
  • 从内存中读取指令到MBR中
  • 将MBR中的指令读到IR中
  • 执行指令

在执行指令时，如果需要使用ALU，则需要使用以下步骤：

  • 将数据存入ALU的输入寄存器中
  • 进行ALU运算，将结果存入到ALU结果寄存器中

一条微指令通常由以下几个部分组成：

  • 控制字：每一位代表了一条控制线，这些位是0是1就表示了这几根控制线的或开或关的控制
  • 分支条件：指示一个条件，如果满足条件，下一条指令就执行微指令地址字段所指向的那一条指令，否则就按顺序执行
  • 微指令地址：指示了一条微指令的地址，当分支条件满足时就使用这个字段的地址作为下一个指令的地址。通常指令存放在控制寄存器中。

做题格式

微操作序列的设计：

1、如果想要从IR指令中取出立即数，你可以使用IR(Address)表示这个立即数。这就代表IR中的地址字段现在存放的是一个立即数

2、如果想要将某个数据作为地址从内存中读取数据，你可以这样写：

  • MAR <- (地址)
  • MBR <- Memory

这里的地址是存放了地址的寄存器或指令字段。假如需要根据PC中的地址取出指令，那么需要将PC放入MAR中，并且最后要将MBR中的指令存入IR当中。当然如果不是取指令就不需要继续存入IR中了。

3、如果想要对两个数据进行ALU运算，假设这两个数据来自R1和R2，ALU的两个输入的寄存器分别是X和Y，输出结果寄存器是Z，那么你可以这样写：

  • X <- (R1)
  • y <- (R2)
  • Z <- (X) + (Y)

这里的加号就已经隐含了使用ALU的意思。注意：如果有的题目ALU只给了一个输入寄存器，那么你只要把其中一个需要计算的数据存入这个输入寄存器中，而另一个数据的寄存器可以在ALU计算时直接表示出来。例如：ALU的一个数据寄存器是X，你想要执行R1+R2，你可以这样写；

  • X <- (R1)
  • Z <- (X) + (R2)

4、如果你想要将数据存回到内存中去，你可以这样写：

  • MAR <- 地址
  • Memory <- MBR

其实和从内存中读取数据相似。你只需要记住MAR是地址寄存器，MBR是数据寄存器，并且两者都是可以作为内存的输入或输出的，不仅仅只能写入内存或者从内存中读出。

设计一个微指令格式时，需要为每一种不同的单元提供的操作分别分配不同数量的位数。例如ALU有16种操作，移位器有8种操作，那么你需要首先为ALU分配4位，然后为移位器分配3位。除此之外，你还要指定ALU的两个输入寄存器和一个输出寄存器。这意味着你需要根据寄存器的数量计算出每个寄存器需要几位表示，再将这个数乘以3。

注意点

  • 控制存储器的位数/宽度就是一个微指令的长度（因为控存中存放的就是微指令）

  • 假如题目让你设计微操作序列来实现一种操作，通常不需要给出取址阶段的操作（地址放入MAR，从内存中读取数据到MBR并存入IR中），也就是说在写微操作的时候，可以默认已经在IR中存放了这条指令。

  • 通常，ALU相关的操作都是需要使用ALU的输入和输出寄存器的，也就是你不能直接令ALU计算的结果存放到你想存放的任何一个寄存器中，而只能先存放到结果寄存器中。

  • 微指令中，如果你是想要取出一个寄存器中的数据，那么你需要在这个寄存器的外面加上括号。比如你想把R1中的数据取出来存入X中，那么你需要写成X <- (R1)的形式，即外面需要带上一个括号。

  • 需要区分间接寻址和间接寄存器寻址的区别：间接寻址意思是IR中的地址字段指向一个内存地址，而这个内存地址所在的内容也是一个内存地址。并不是说IR中指示的一个寄存器中存储了一个内存地址（这应该叫做间接寄存器寻址）。如果要间接寻址，只需要将第一次从内存中取出的数据再作为地址存入MAR中从内存中读第二次数据即可。

  • 有时候，如果题目指定了一种操作，或是寄存器，但是没有给出具体名字的话，你需要自己设一下这些寄存器。比如你可以设ALU的输入寄存器是X和Y，输出寄存器是Z，或者设取反操作是Neg(X)。

十、控制器计算

知识点

通常，处理器进行I/O数据传输的方式有以下几种：

1、查询方式：处理器定期去检查I/O数据准备是否就绪，如果就绪，就读取该数据，将其传输至内存缓冲区中。

2、中断驱动方式：当I/O设备准备完一个数据时，就执行中断操作，通知处理器。然后处理器就执行中断服务程序来接收这个数据。

3、直接存储器读取（DMA）：无需经过处理器，直接由DMA访问内存模块进行存取。它又分为不同的方法

  • CPU停止法（突发模式）：DMA全程接管总线控制权，直到数据全部读取完再释放。
  • 周期窃取：每隔几个周期就暂停CPU并开始一次DMA的I/O数据传输，通常可以是每次外设传输完一个数据的时候就进行一次DMA的周期。
  • 交替分时访问：每个时钟周期划分为两段，前半段给CPU，后半段给DMA。

做题要点

在中断相关的题中，需要注意的点有：

  • 一次中断分为前后两个过程：中断响应和中断处理。会先执行中断响应，然后再执行中断处理。
  • 中断响应时看的是中断响应优先级，中断处理时看的是中断处理优先级
  • 在中断响应期间是不允许其他中断的，只有在中断处理期间才会允许其他中断。

现在分几种情况讨论：

  • 假如最初没有中断，然后同时出现了多个中断请求，那么就先选择中断响应优先级最高的进行中断响应
  • 在一个中断响应结束后，中断处理之前，需要先观察有没有比自己的中断处理优先级更高的请求。如果有的话，就先去响应并处理那个中断处理优先级更高（最高）的请求。（注意：这个时候不需要考虑这些请求的中断响应优先级是因为自己在当初响应的时候就已经选择的是中断响应优先级最高的请求了，并且中断响应过程中也不会有新请求加入，因此在中断处理时自己仍然是中断响应优先级最高的，所以我们在处理前响应处理优先级更高的就不以中断响应优先级为依据）
  • 注意：如果在响应一个中断后，处理这个中断前，去响应并处理了别的一个中断，那么别的那个中断处理结束后必须立即返回到这个原来的中断中，不允许在返回到原来这个中断前再去其他中断的地方。例如处理L1前先去处理了L2，那么L2结束后必须立刻返回L1，而不允许再去什么L3（你可以返回L1之后再去L3）。当然，如果从刚开始主程序期间响应了一个中断，那么这个中断结束后也得立即先返回主程序，然后再去搞别的中断。
  • 如果在中断处理期间发生了新的中断请求，那么我们需要响应的是所有未被自己屏蔽（中断处理优先级高于自己）的请求中中断响应优先级最高的那个。也就是说，假如L1中断处理时发生了L2、L3、L4的中断，假如中断响应优先级是L4>L3>L2，中断处理优先级是L2>L3>L1>L4，这个时候尽管L4的中断响应优先级最高，但是由于中断处理优先级低于自己，因此被自己屏蔽，只需要先处理剩下两个中断响应优先级最高的，即L3。L3结束后先返回L1，再去响应L2，返回L1。而L4就只能等L1处理结束后返回后再去找机会处理。（注意：这个时候就需要考虑中断响应优先级了，原因是当同时发生新的中断请求的时候，这些新的中断请求中可能就含有比自己中断响应优先级更高的请求，和刚才不一样，刚才没有新的请求加入，所以自己仍然是中断响应优先级最高的，这里就不一定了。）

画图时需要画成以下的形式：

其中较短的表示的是中断响应，较长的是中断处理。并且当在中断处理时或主程序期间发生新中断并处理完后，必须返回原来的那个中断或是主程序。

计算步骤

在计算占用时间时，第一步可以先确定时钟周期，然后分别求出I/0设备向主机传输每个字节的时间（通常都是直接给多少kbps的）、以及处理器读取每个字节到内存缓冲区中的时间（一般会给出每次执行的时钟周期），比较两者哪个更高。（一般情况下都是I/O传给主机所花的时间更长。）然后就根据不同情况来算时间。

计算要点

计算设备占用总线的时间：

  • 查询方式：最坏的情况就是每次读取数据前刚刚查询完，因此处理器接收每个字节的时间就是一次查询+一次数据处理的时间。而设备总占用时间就是I/O从外设传输完所有内容的时间+最后处理器接收一个字节（查询+数据处理）的时间；并且CPU处理I/O时间就是设备总占用时间。

  • 中断驱动方式：一般处理器接收每个字节的时间就是中断响应+中断服务程序的时间。因此总的设备占用时间就是I/O从外设传输完所有内容的时间+最后处理器中断接收一个字节（查询+数据处理）的时间。（与查询方式非常类似）；并且CPU处理I/O时间就是处理器中断响应和中断一次的时间乘以数据总量。

  • CPU停止DMA（突发模式）：首先DMA初始化和后处理需要一定时间，然后交给DMA全权处理。此时我们要判断是I/O传输数据的速度快还是处理器接收数据的速度快。DMA传输数据的时间就是速度慢的那一方处理完所有数据的时间+速度慢的那一方处理完一个字节数据的时间。所以总的占用时间就是DMA传输数据的时间+DMA初始化和后处理的时间；而CPU处理I/O时间仅仅只有DMA初始化和后处理的时间。

  • 周期窃取DMA：我们就可以当成是中断驱动，但是不同之处在于无需等到I/O从外设传输的时间，只需要执行一次处理器接收数据即可。但是每次接收一个数据都需要DMA初始化和后处理，因此设备占用总时间即为每次DMA初始化+接收数据+后处理的时间乘以数据总量；而CPU处理I/O时间就是DMA初始化+后处理的时间乘以数据总量。

  • 交替分时访问：略

中断屏蔽字：这个屏蔽字是基于中断处理优先级的，而不是中断响应优先级。需要屏蔽的都是优先级比自己更低的等级（包括自己）。

注意点

  • 使用查询方式时，CPU都是全程参与的，因此CPU处理I/O时间与设备占用时间之比就是100%。其他方式则不会

  • 一般使用查询方式和中断驱动方式时，必须要满足I/O传输数据的速度慢于处理器接收数据的速度，否则就会造成数据丢失，无法使用；如果使用的是突发模式DMA，就可以自由控制I/O传输数据的速度，因此一定是可以的。而它的需要的时间就取决于I/O传输数据与处理器接收数据中的较慢的一方。通常为较慢一方处理全部数据和较快一方处理一个数据的时间之和。

  • 假如I/O传输速度和处理器接收速度相等，那也是可以使用中断或者查询方式的。

  • 中断屏蔽字中，分为自屏蔽和非自屏蔽。我们做题时一般使用的是自屏蔽，即自己可以屏蔽自己。

  • 中断方式时，中断和数据传输是可以并行完成的。这意味着中断期间只需要通知CPU执行一次中断处理，不需要暂停执行数据传输的任务。

  • 如果题目准确告诉你了一共要传输多少数据，那么你就需要除了数据传输以外，还需要将最后一个字节传输完后的操作加上处理器之间中，例如中断一次等。但是如果题目没有说一共要传输多少数据，那么你就不需要加上（默认一直在传输，没有停止过）。

十一、总线计算

知识点

  • 一个总线事务，指的是你发送一个地址，并读取、传输一组数据的操作。
  • 同步总线下，从内存访问一个数据通常需要经过的步骤为三个：传地址、数据读取、数据在总线上传输。并且如果同时需要读取很多数据的话，在读取完第一个单位的数据的时候就可以开始直接在总线上传输这个数据，并且同时也可以继续读取往后的数据。因此，在往后读取每个单位的数据时，需要取读取一个单位数据的时间与传输一个单位数据的时间两者之间的较大值。
  • 因此，同步总线执行一次总线事务的周期数为：传输地址的周期数+读取第一个单位数据的周期数+(max(读取往后的一个单位的周期数，传输一个单位的周期数))×剩下需要读取的单位数据的数量+传输最后一个数据的周期数。（注意，这里需要使用周期数为单位而不是时间为单位）
  • 异步总线下，从内存访问数据需要经过以下几个步骤：第一次握手（准备地址），（传输数据+三次握手），最后的三次握手。通常传输数据和后面三次握手都是并行的，因此这个操作需要取的是三次握手和传输这些数据的时间的较大值。
  • 因此，异步总线执行一次只传送一次数据的总线事务的周期数为：一次握手的时间（用于准备地址）+max(准备数据的时间，三次握手的时间)+传输数据的三次握手时间（注意，这里使用的是正常的时间单位了）

注意点

  • 同步总线下，操作的时间都要以时钟周期的整数倍为单位，如果一个操作是12ns，而时钟周期是5ns，那么你就必须将其看为15ns而不是12ns。也因此，我们在计算关于同步总线的时间时，用的单位都是几个时钟周期，而不是具体的时间数值。例如这里的操作我们就可以将其说成使用3个时钟周期。
  • 异步总线下，操作的时间不需要考虑时钟周期，因此可以直接以时间为单位。
  • 通常来说，第一步传递地址花费的通常是一个时钟周期的时间或者一次握手的时间（如果一次能传的最大数据量比一个地址的大小小，那么可能需要分多次去传，但是每次也都是一个时钟周期或者一次握手）
  • 异步总线下，读取数据都是可以持续进行的，但是每读取一个单位的数据后就必须将其传输掉（这个时候也是可以同步读取下一个单位的数据的）。而每次传输一个单位的数据就要经历四次握手（四次是因为在中间过程中，除了前三次握手用于传输数据外，还需要额外一次握手来通知存储器可以进行下一次的读取任务），因此中间每次准备和读取一个单位数据的时间就是准备数据的时间和4n次握手的时间的较大值。而在传输最后一个单位的数据时，由于无须通知存储器读取往后的任务，因此就只要三次握手。
    同步总线下，传完地址之后在第一个单位数据的准备的时候不需要做其他事情，而异步总线下，传完地址之后在准备第一个单位数据的时候同时还要进行三次握手，因此需要再加比较两者谁更大，使用哪个时间。

十二、海明码计算

知识点

  • 海明码是一种数据校验码，就是对指定位置的奇偶校验。
  • 假如原来有数据，那么海明码的位置就是：当你给数据插入海明码后，海明码所在的位置即为2的整数倍的位置（即为满足二进制数字中只存在一个1的所有二进制数代表的位置），例如0001、0010、0100、1000等位置。然后假设如果海明码的位置是在0010处，那么它所需要管理的位置就是在添加海明码后的数据中位于xx1x的数据，例如位于0011、0110、0111等等，也就是它需要管理的是所有二进制数字中满足海明码为1的那个位置也为1的二进制数字所代表的位置。注意：这里的位置都是从1开始，并且是从最右边开始往左增大的。
  • 海明码分为奇校验和偶校验，奇校验就是添加校验码可以使得整体有奇数个1，而偶校验就是添加校验码可以使得整体有偶数个1。

做题方法

  • 首先想要安置海明码的话，你可以先把已有的数据写出来，然后把笔指向数据的最右端，也就是最后一个数字的右侧，然后从右往左数数，每数一个数就把笔往左指一格（指在两数之间的间隙处）。这个时候如果数到的是2的正数倍（1，2，4，8等），那么就在你笔指向的位置添加一个X，代表这个位是一个海明码校验位。
  • 然后你需要计算出每个海明码的位。简单的方法就是，先看你这个海明码所在的位置是几，假设为8，那么你就可以这样：从0开始数，一直数到刚刚那个位置的前面一个数，这里就为7，所以你先从0数到7，你一共数了8个数字，并且这些数字都是不需要海明码考虑的。然后接着往后数相当于刚刚所数的数字数量的数，这里就是再数8位，所以你就接着从8往后数8位，你会数到15。那么这个时候你数的这8个数就都是海明码要考虑的数。以此类推，再往后数8位就是不需要考虑的，再往后就是需要考虑的…最后你就可以确定你这个海明码究竟需要考虑哪些位，然后数它们有几个1，你就可以根据是奇校验还是偶校验确定出你这个海明码位是什么了。

十三、加法器门延迟计算

知识点

  • Ci表示进位，Fi表示当前位的输出，Xi和Yi表示这个位的两个要相加的数
  • 单个加法器中，Ci需要Xi和Yi先后经过一次与门和一次或门得到；Fi需要Xi，Yi和上一位的进位Ci-1进行两两异或得到。
  • 串行进位/行波进位加法器中，每个C需要一次与门和一次或门，并且Ci需要使用Ci-1，所以Ci就是i次与门和i次或门，Fi就是在算出Ci-1的基础上进行一次异或门运算得到，
  • 全先行进位加法器中，第一步要计算出Gi和Pi，它们分别是Xi和Yi经过与和或运算得到的。第二步要计算出所有的进位，就是将上一步得到的Xi和Yi再先后经过与运算和或运算，然后第三步要计算出Fi，也就是把上一步得到的Ci再做一次异或运算。
  • 部分先行进位加法器中，第一步也是计算出所有的Gi和Pi，第二步也是求Ci，但是要执行很多次，需要依次求出从C1到Ci的所有进位，具体就是执行相当于全先行进位加法器数量的次数的第二步。然后第三步就是求出最后一位的Fi，只需要将上一步得到的Ci进行异或运算。

计算方法

  • 假设与门和或门的门延迟中的较大值为x，与门和或门门延迟之和为y，异或门延迟为z
  • 串行进位加法器，假设有n个加法器，那么总门延迟=(n-1)y+z。但是如果这个数小于2z，那么需要改成2z。
  • 全先行进位加法器，总门延迟=x+y+z。同样，如果这个数小于2z就要改成2z
  • 部分先行进位加法器，假设由n个全先行进位加法器组合而成，那么总门延迟=x+ny+z。同样需要判断是否要改为2z