资讯详情

国科大计算机体系结构习题整理

基础知识和解题思路在横线上方，具体问题在横线下方回答

学习效率最高的是基于考题的课堂视频片段回放(我意识到了) 不仅仅是考试，有时间做所有的练习

计算机系统结构

第二章

  1. 在三个不同指令系统的计算机上运行同一程序P时，A机需要执行 1.0 ? 1 0 8 1.0 * 10^8 1.0?108 条指令，B机需要执行 2.0 ? 1 0 8 2.0 * 10^8 2.0?108 条指令，C机需要执行 4.0 ? 1 0 8 4.0 * 10^8 4.0?108 但实际执行时间为10s。在运行程序P时，请单独计算这三台机器的实际速度MIPS为单位。这三台计算机在运行程序P时哪一台性能最高？为什么？

M I P S = ( 指 令 数 / 执 行 时 间 ) / 1 0 6 = 指 令 数 / ( 执 行 时 间 ? 1 0 6 ) MIPS = (指令数/执行时间 )/ 10^6=指令数/(执行时间 * 10^6) MIPS=(指令数/执行时间)/106=指令数/(执行时间∗106)，执行时间的单位是 s

运行程序P的实际速度为：A 为 10MIPS，B 为 20MIPS，C 为 40MIPS

在运行程序P时，三台计算机的运行时间相同，所以性能相同

  1. 对某处理器进行功耗测试，得到如下数据：时钟不翻转，电压1.05V时，电流为500mA；时钟频率为1GHz，电压1.1V时，电流为2500mA。请计算在1.1V下，此处理器的静态功耗以及500MHz下的总功耗。
  • 功 率 P = U ∗ I ， 电 压 U = I ∗ R 功率P = U*I，电压U = I*R 功率P=U∗I，电压U=I∗R 功率单位是W，电压单位是V，电流单位是A
  • 时钟不翻转的静态功耗计算时等效成电阻R ( R = U / I )
  • 动态功耗与时钟频率（翻转率）成正比
  • 总功耗 = 动态功耗 + 静态功耗

$1.1V 下静态功耗P = U^2/R = 1.11.1/(1.05/0.5)=0.576W $ $1.1V 下 1\mathrm{GHz} 时，动态功耗 = 总功耗-静态功耗 = 1.12.5-0.576=2.174W $ $1.1V 下 0.5\mathrm{GHz}时， 动态功耗为 2.174*0.5/1=1.087W $ $ 1.1V 下 0.5\mathrm{GHz}时，总功耗为 1.087+0.576=1.663W $

第三章

  1. 画出$ e = a & b| c & d$的晶体管级电路图

逻辑等价变换

  1. A ∣ 0 = A ， A & 1 = A ， A ∣ 1 = 1 ， A & 0 = 0 A|0 = A，A\&1 = A，A|1 = 1，A\&0 = 0 A∣0=A，A&1=A，A∣1=1，A&0=0
  2. A ∣ A = A ， A & A = A ， A ∣ ∼ A = 1 ， A    & ∼ A = 0 A|A = A，A\&A = A，A|\sim A = 1，A\;\&\sim A = 0 A∣A=A，A&A=A，A∣∼A=1，A&∼A=0
  3. A ∣ B = B ∣ A ， A & B = B & A ， A|B = B|A，A\&B = B\&A， A∣B=B∣A，A&B=B&A，
  4. A ∣ ( B ∣ C ) = ( A ∣ B ) ∣ C ， A & ( B & C ) = ( A & B ) & C A|(B|C) = (A|B)|C，A\&(B\&C) = (A\&B)\&C A∣(B∣C)=(A∣B)∣C，A&(B&C)=(A&B)&C
  5. A & ( B ∣ C ) = A & B ∣ A & C ， A ∣ ( B & C ) = ( A ∣ B ) & ( A ∣ C ) A \& (B|C) = A \& B|A \& C，\color{red}A | (B\&C) = (A | B)\&(A| C) A&(B∣C)=A&B∣A&C，A∣(B&C)=(A∣B)&(A∣C)
  6. ∼ ( A & B ) = ∼ A    ∣ ∼ B ， ∼ ( A ∣ B ) = ∼ A    & ∼ B \sim (A\&B) = \sim A \;| \sim B，\sim (A|B) = \sim A\;\& \sim B ∼(A&B)=∼A∣∼B，∼(A∣B)=∼A&∼B
  7. A ∣ A & B = A ， A ∣ ∼ A & B = A ∣ B \color{red}A|A\&B = A，A|\sim A \& B = A|B A∣A&B=A，A∣∼A&B=A∣B
  8. 非门、与非门、或非门可以组成任何逻辑电路，并且非逻辑电路通常规模小，延时短。
    • 非门 image-20211224195047860
    • 与非门
    • 或非门
  • A & B ∣ C & D = ∼ (    ∼ ( A & B )    &    ∼ ( C & D )    ) A\&B|C\&D=\sim(\;\sim(A\&B) \; \& \; \sim(C\&D) \;) A&B∣C&D=∼(∼(A&B)&∼(C&D))，两级与非门的逻辑 ，不是全展开

  • (老师上课画的，用上面就行)
  1. 计算一个FO4的延迟，假设反相器的输入电容为0.0036pF，平均每个负载连线电容为0.0044pF，翻转延迟为0.023ns，每pF延迟为4.5ns

本课对 FO4 定义为 1 个反相器驱动 4 个相同的反相器

FO4 延迟=本征延迟+负载延迟

  • 本征延迟：元器件固有延迟，对于 反相器 是指 翻转延迟
  • 负载延迟 = 每pF延迟 * (（输入电容 + 单个负载连续电容）* 负载个数)

FO4 延迟=本征延迟+负载延迟=0.023+4.5*((0.0036+0.0044)*4)=0.167ns

第四章

  1. 假定在指令系统设计中需要考虑两种条件转移指令的设计方法，这两种方法如下。

    • CPU A：先通过一条比较指令设置条件码A，再用一条分支指令检测条件码
    • CPU B：比较操作包含在分支指令中

    在两种CPU中，条件转移指令都需要两个时钟周期，所有其他指令都需要一个时钟周期。在CPU A中，全部指令的25%是条件转移指令，因为每次条件转移都需要进行一次比较，所以比较指令约占所有指令的25%。因为CPU A不需要在转移中包含分支，所以它的时钟频率是CPU B的1.2倍。请问哪一种CPU性能更高？如果CPU A的时钟频率知识CPU B的1.1倍，结果又是多少？

比性能实际是比时间，性能要联想到时间 时间 = 指令数 * 平均每条指令的时钟周期（指令延迟） 时钟频率 = 1 / 时钟周期数 $A相对于B的性能;(求A对B性能的倍数) = \dfrac{T_B}{T_A} = \dfrac{\frac{B的周期数}{B的频率}}{\frac{A的周期数}{A的频率}} $，因为时间越长性能越差

  • 假设 CPU A 总指令数为 x，根据题意，转移指令有 0.25x，每条需要两个时钟周期，比较指令 0.25x，其它指令 0.5x，因此 A 执行周期数为2*0.25x+0.75x=1.25x
  • CPU B 相比CPU A少了0.25x的比较指令，所以总指令数为 0.75x，其中转移指令 0.25x，其它指令 0.5x。所以B 执行周期数 2*0.25x+0.5x=1x
  • 当 CPU A 频率为 1.2 倍时，性能是 CPU B 的 1.2/1.25=0.96 倍 当 CPU A 频率为 1.1 倍时，性能是 CPU B 的 1.1/1.25=0.88 倍 因此 CPU A 两种情况下都差

第五章

  1. 假定某RISC处理器采用如下图所示的5级流水线（IF/ID/EX/MEM/WB）结构，对于下列指令序列：

    LW	R1,0(R0)	; 从地址0+R0处读值到R1中
LW	R2,4(R0)	; 从地址4+R0处读值到R2中
ADD	R3,R1,R2	; R3 = R1 + R2
SW	R3,12(R0)	; 将12+R0地址处的值存入R3
LW	R4,8(R0)	; 
ADD	R5,R1,R4	;
SW	R5,16(R0)
// *********必错点，重命名，重排序，指令地址
指令相关（前后相同的寄存器）：
    R1在1，3，8存在指令相关
    R2在2，3存在指令相关
    R3在3，4存在指令相关
    R4在5，6存在指令相关
    R5在6，7存在指令相关

    分析上述指令序列的相关，并重排序执行序列避免相关，重排序指令序列，可以比原先指令序列的执行减少多少拍？

    1. 采用五级静态流水线，即取指IF、译码ID、执行EX、访存MEM、写回WB，那么如果不发生堵塞，将执行 （5+指令数-1 = 4+指令数）的拍数。（ALU只能使用寄存器进行运算，所以需要先从内存中取得寄存器的值，在运算后再将结果存入到内存中）

    2. 如果发生指令相关的冲突，则需要进行延迟，程序计数器PC（取指）和指令寄存器IR（译码）将保持当前值不变，共执行（4+指令数+延迟拍数）的拍数

    3. 前递技术|旁路技术： 指令阻塞会引起流水线效率降低，当前后指令存在数据相关时，流水线中的运算器通过多路选择直接把前面的指令的运算输出作为后面指令的输入 ，即前面的指令直接将运算结果传给后面的指令，从而减少后面指令的等待。

    4. 完全前递forward

      • EX执行结果到ID译码（同一拍的执行EX可以前递给译码ID）
      • WEW访存结果到ID译码
      • 写回WB结果要到ID译码
      • 其中，需要结果的指令阻塞在ID，下一拍指令被阻塞在IF（同一时间内，五级流水中的一级不能存在两条指令）
      • 运算操作在EX即可前递，LW操作在MEM才可前递（EX阶段没有值，访存MEM才获取值）

    5. 指令相关

      • 寄存器相关
        • 数据相关
        • 名字相关
      • 控制相关

    6. 只使用前递技术处理写后读的数据相关的原因

      • 分支指令由单发射五级流水译码级处理了
      • MIPS指令有延迟槽时候，控制相关不需要处理
      • 读后写和写后写相关不会触发流水线冲突，不会引起阻塞

    7. 指令的相关性（指令的相关判断和阻塞控制都是在译码级进行的）

      • 先读后读：实际上没有相关性，调转执行顺序对结果没有影响
      • 先写后读：存在数据依赖性，不可调序，称为数据相关。（可以使用前递技术）
      • 先读后写：不可调序，称为反相关
      • 先写后写：不可调序，称为伪相关
      • 控制相关：指令执行依赖于前面的控制指令结果

    8. MIPS指令基础

      https://blog.csdn.net/zhang_danf/article/details/20037329?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522164048538616780264048507%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=164048538616780264048507&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2allfirst_rank_ecpm_v1~rank_v31_ecpm-1-20037329.pc_search_result_control_group&utm_term=LW%09R1%2C0%28R0%29&spm=1018.2226.3001.4187

    原题：在写回级没有forward通路，运算需要的两个源寄存器需要同时进行前递，因为图中的译码ID电路没有触发器进行存储

    ：认为具有完全前递情况下，发生指令相关冲突：总拍数 = 4+指令数+延迟拍数 = 4+7+2 = 13

    • LW指令在MEM时，才取到值可以进行前递，其他运算指令在EX阶段即可前递
    • 重排策略：只与前面有关的向后调，只与后面有关的向前调，无关指令可以灵活调。一般调LW和SD 画出五级流水，将指令代入进行思考，再画出时空图

第六章

  1. 以下这个循环是高斯消元法中的核心操作，称为DAXPY循环（双精度的a乘以X再加上Y），以下代码实现了对长度为100的向量进行DAXPY操作： Y = a ∗ X + Y Y = a*X+Y Y=a∗X+Y。

    bar:
	LDC1	F2,0(R1)	;取数
	MUL.D	F4,F2,FO	;乘法操作a * X(i)
	LDC1	F6,0(R2)	;取数Y(i)
	ADD.D	F6,F4,F6	;加法操作a*X(i)
	SDC1	F6,0(R2)	;存数Y(i)，F6寄存器的值存入R2指向的内存单元
	DADDIU	R1,R1,#8	;#8表示立即数，R1+8表示下标＋1，一个双精度数8字节
	DADDIU	R2,R2,#8	;Y的下标+1
	DSGTUI	R3,R1,#800	;测试循环是否结束，注意800
	BEQZ	R3,bar		;如果循环没有结束，转移到bar
	NOP

    在单发射静态流水线上，假定浮点流水线的延迟如下表所示（延迟为N表示第T拍操作数准备好开始运算，第T+N-1拍可以写回结果），分支指令在译码阶段（ID）计算结果，采用了分支延迟槽技术，整数操作在一拍之内发射和完成，并且结果是完全旁路的（fully bypassed）。浮点流水线的延迟表：

    产生结果的指令 使用结果的指令 延迟（时钟周期）
    FP ALU op Another FP ALU op 4（计算—计算需要4个延迟槽）
    FP ALU op Store double 3
    Load double FP ALU op 2（加载—计算需要2个延迟槽）
    Load double Store double 1
    • 把这个循环展开足够的次数，要求消除所有停顿周期和循环开销指令。循环将会被展开多少次？写出调度后的代码，每产生一个结果需要多少执行时间？
    • 写出DAXPY循环在软件流水后的代码，可以省略软件流水的装入代码和排空代码，每产生一个结果需要多少执行时间？

题1相关基础知识

  1. 考试一般不会展开四次以上或者除不尽，循环展开需要对寄存器重命名，最后进行重排序减少指令阻塞

  2. 静态指令调度可以大大减少平均每次循环计算的时钟周期，主要方法：

    • 循环展开：可以降低循环开销，但是增加代码空间，降低cache的命中率
    • 寄存器重命名：可以消除WAW和WAR相关，但需要更多的寄存器
    • 指令重排序：可以消除数据相关

  3. 每次循环最后的延迟槽NOP可以放一条指令，不受转移指令影响肯定会执行，通常是SD指令( 向内存写值 )

  4. 每次循环展开，计算内存地址变换一个元素的内存长度（Double为8字节）

  5. 在64位CPU上，LDC1 是 L . D 的别名

  6. 指令 功能 应用实例
    LB 从存储器中读取一个字节的数据到寄存器中 LB R1, 0(R2)
    LH 从存储器中读取半个字的数据到寄存器中 LH R1, 0(R2)
    LW/LWC1 R2+0指向的内存单元的一个字加载到R1中 LW R1, 0(R2)
    LD 从存储器中读取双字的数据到寄存器中 LD R1, 0(R2)
    L . S 从存储器中读取单精度浮点数到寄存器中 L.S R1, 0(R2)
    L . D/LDC1 从存储器中读取双精度浮点数到寄存器中 L.D R1, 0(R2)
    SB 把一个字节的数据从寄存器存储到存储器中 SB R1, 0(R2)
    SH 把半个字节的数据从寄存器存储到存储器中 SH R1，0(R2)
    SW 把一个字的数据从寄存器存储到存储器中 SW R1, 0(R2)
    SD 把两个字节的数据从寄存器存储到存储器中 SD R1, 0(R2)
    S . S 把单精度浮点数从寄存器存储到存储器中 S.S R1, 0(R2)
    S . D 把双精度数据从存储器存储到存储器中 S.D R1, 0(R2)
    DADDIU R2+立即数k后存入R1 DADDIU R1，R2，#k

  7. 定点寄存器R1存储初始计算元素数组的最后一个元素的起始下标，每计算一个元素，下标-8（一个双精度浮点数占8个字节）后计算下一个元素

  8. 易错点

    • 寄存器的重命名
    • 展开后寄存器的offset
    • 排序号的寄存器offset，特别是非展开的指令

学长解释：https://blog.csdn.net/csdn_muxin/article/details/112284481?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522164051627316780357256181%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fblog.%2522%257D&request_id=164051627316780357256181&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2blogfirst_rank_ecpm_v1~rank_v31_ecpm-3-112284481.nonecase&utm_term=%E5%9B%BD%E7%A7%91%E5%A4%A7%E8%AE%A1%E7%AE%97%E6%9C%BA%E4%BD%93%E7%B3%BB%E7%BB%93%E6%9E%84&spm=1018.2226.3001.4450

题1解答：假设R1、R2存放数组X、Y的首地址，F0 存储浮点常量a的值

  1. 先进行循环展开（不需要写在答题卡上，写完检查 **偏移 **和 ）
bar：// 不要忘记展开后的地址和最后的ADDIU为展开次数*8
	1  L.D    F2, 0(R1) 	 // 取X[i]
	2  L.D    F3, 8(R1) 	 // 取X[i+1] ，注意偏移值offset为8和寄存器重命名
	3  MUL.D  F4, F2, F0 	 // 计算a*X[i]
	4  MUL.D  F5, F3, F0	 // 计算a*X[i+1]
	5  L.D    F6, 0(R2)		 // 取Y[i]
	6  L.D    F7, 8(R2)		 // 取Y[i+1]
	7  ADD.D  F6, F4, F6 	 // a*X[i] + Y[i]
	8  ADD.D  F7, F5, F6 	 // a*X[i+1] + Y[i+1]
	9  S.D    0(R2), F6	 	 // 存Y[i]
	10 S.D    8(R2), F7	 	 // 存Y[i+1]
	11 DADDIU R1, R1, #16	 // X的下标+2，注意展开的循环次数，offset为次数*8bit
	12 DADDIU R2, R2, #16	 // Y的下标+2
	13 DSGEIU R3, R1, #800	 // 测试循环是否结束
	14 BEQZ   R3, bar		 // 如果循环没有结束，程序跳转到bar位置
	15 NOP

  1. 检查相关性（从题中表得知的，不需要写在答题卡上）

    1 和 3 延迟为2，不需要等待，1执行完进行前递，3正好进入译码阶段 2 和 4 延迟为2，不需要等待 3 和 7 延迟为4，不需要等待 4 和 8 延迟为4，不需要等待 5 和 7 延迟为2，不需要等待 6 和 8 延迟为2，不需要等待 7 和 9 延迟为2，不需要等待 8 和 10 延迟为3，之间需要加上 1 条不相关指令 9 和 11 延迟为3，之间需要加上 1 条不相关指令

  2. 指令重排序

    bar：
	1  L.D    F2, 0(R1) 	 // 取X[i]
	2  L.D    F3, 8(R1) 	 // 取X[i+1] ，注意偏移值offset为8和寄存器重命名********
	3  MUL.D  F4, F2, F0 	 // 计算a*X[i]
	4  MUL.D  F5, F3, F0	 // 计算a*X[i+1]
	5  L.D    F6, 0(R2)		 // 取Y[i]
	6  L.D    F7, 8(R2)		 // 取Y[i+1]
	7  ADD.D  F6, F4, F6 	 // a*X[i] + Y[i]
	8  ADD.D  F7, F5, F6 	 // a*X[i+1] + Y[i+1]
    9   DADDIU R1, R1, #16	 // X的下标+2，注意展开的循环次数，offset为次数*8bit
	10  S.D    0(R2), F6	 // 存Y[i]
	11 S.D    8(R2), F6	 	 // 存Y[i+1] 
	12 DSGEIU R3, R1, #800	 // 测试循环是否结束
	13 BEQZ   R3, bar		 // 如果循环没有结束，程序跳转到bar位置
	14 DADDIU R2, R2, #16	 // Y的下标+2,nop指令在每次执行完一定执行

    （指令延迟均为3或4也满足）

    bar：
	1  L.D    F1, 0(R1) 	 // 取X[i]
	2  L.D    F2, 8(R1) 	 // 取X[i+1] 
	3  L.D    F3, 0(R2)		 // 取Y[i]
	4  L.D    F4, 8(R2)		 // 取Y[i+1] 
	5  MUL.D  F1, F1, F0 	 // 计算a*X[i]
	6  MUL.D  F1, F2, F0	 // 计算a*X[i+1]
	7  DADDIU R1, R1, #16	 // X的下标+2
	8  ADD.D  F3, F1, F3 	 // a*X[i] + Y[i]
	9  ADD.D  F4, F2, F4 	 // a*X[i+1] + Y[i+1]
	10 DADDIU R2, R2, #16	 // Y的下标+2
	11 DSGEIU R3, R1, #800	 // 测试循环是否结束
	12 S.D    -16(R2), F6 	 // 存Y[i]
	13 BEQZ   R3, bar		 // 如果循环没有结束，程序跳转到bar位置
	14 S.D    -8(R2), F6	 // 存Y[i+1],占用延迟槽
所以重排后，14 拍可以执行两个，也就是7 拍1 个

题2相关基础知识

  1. 软流水是通过重组循环体使得不同循环体指令并行执行，新循环体的每个操作来自不同轮的循环，以分开数据相关的指令。
  2. 软流水后，循环体会变成装入、主体循环、排空三个部分。
  3. 在软流水后循环执行时，主要是主体循环部分在执行，装入和排空仅执行一次。其中，装入是为了让主体循环可以正确执行的预处理阶段，排空是保证主体循环执行后结果正确的收尾阶段。

学长解释：https://blog.csdn.net/csdn_muxin/article/details/114491152

题2解答：指令如下，进行软流水处理。

  1. 据指令相关性进行逆序划分，写出从0开始的连续n轮循环体（地址+8，从地址从n开始则-8）(与ADDIU符号相反)
  2. 从最后一轮开始，取最后一个或多个，依次向上取得到计算指令，再加上控制指令得到循环主体
  3. 装入代码是倒序剩下的后几轮的指令序列，排空代码倒序剩下的前几轮代码
  4. 调整地址（指令间的顺序和地址差值不变），装入代码从0开始，结尾是ADDIU (正负号和题中的ADDIU相同)(n+1)*8，循环和排空的第一个地址和装入代码的最后一个是相反（指令间的顺序和地址差值不变）

主循环体代码：

S.D 	-24(R2),F6 ; 第i-3 次循环的5
ADD.D 	F6, F4, F8 ; 第i-2 次循环的4
MUL.D 	F4, F2, F0 ; 第i-1 次循环的2
L.D		F2, 0(R1) ;
L.D 	F8, -8(R2) ; 进行了指令重排序
DADDUI 	R1, R1, #8 ;
DSGTUI 	R3, R1, #800 
        标签： 54c8分类电阻器
 
锐单商城拥有海量元器件数据手册、
          IC替代型号，打造
          电子元器件IC百科大全！

锐单商城 - 一站式电子元器件采购平台