北京大学 计算机系统导论 期中 带答案

admin管理员组

文章数量:1568304

2024年3月6日发(作者：)

第一题选择题（每小题2分，共34分）（每小题有一个或多个正确答案）（ch2,kaigui）1、变量x的值为0x01234567，地址&x为0x100；则该变量的值在x86和Sun机器内存中的存储排列顺序正确的是（选项ABCD机器类型x86Sunx86Sunx86Sunx86Sun0x1670101）地址0x14523230x12345450x1016767答案：A考察大端、小端；同时sun是大端、x86是小端（ch2,kaigui）2、假设下列int和unsigned数均为32位，intx=0x80000000;unsignedy=0x00000001;intz=0x80000001;以下表达式正确的是（）A.(-x)<0B.(-1)>yC.(z<<3)==(z*8)D.y*24==z<<5-z<<3答案:ABCD；考虑到运算符的优先顺序，选ABC也算对中0x80000000的相反数还是自己(-1)和unsingedy比较，都按照unsigned，所以强制类型转换后（-1）很大C:unsigned,signed左移三位=*8D：应该是相等关系；signed左移之后，和unsignedy*24相比都看成unsigned（ch2,kaigui）3、对x=（和y=）B.1,进行小数点后两位取整（roundingtonearesteven),结果正确的是A.,C.,D.1,答案：Dx=1.00100halfwayanddown-->1.00y=1.01100halfwayandup-->1.101

（ch3，yingfei）4、在完成BombLab的时候，通常先执行gdbbomb启动调试，然后执行___上述两个空格对应的命令是（,,go答案：c）,ruexplode_bomb命令以防引爆炸弹，之后在进行其他必要的设置后，最后执行___命令以便开始执行程序。,go说明：根据之前的讨论，出一道题目检查同学们是否自己做过lab（ch3，yingfei）5、已知函数intx(intn){returnn*____;}对应的汇编代码如下：lea(%rdi,%rdi,4),%rdilea(%rdi,%rdi,1),%eaxretq请问横线上的数字应该是（）A.4B.5C.2D.10答案：D说明：此题目考察对于乘法的转换，难度较低，适合出选择题。还可以把乘法换成除法，就可以出大题或者简答题。（ch3,Guangyu）6、32位x86计算机、Windows操作系统下定义的一个structureS包含三个部分：doublea,intb,charc,请问S在内存空间中最多和最少分别能占据多少个字节（32位Windows系统按1、4、8的原则对齐char、int、double）？答：（）A.16,13B.16,16C.24,13D.24,16答案：D考虑对齐,windowsdouble按8字节对齐，最长c,a,b，最短a,b,c（ch3,Guangyu）7、x86体系结构的内存寻址方式有多种格式，请问下列哪些指令是正确的：（$34,(%eax)(%eax),%$23,10(%edx,%eax)(%eax),8(%ebx)答案：ABC，寻址不支持内存到内存的访问（ch3,Guangyu）8、x86体系结构中，下面哪些选项是错误的？答：（指令只能够用来计算内存地址B.x86_64机器可以使用栈来给函数传递参数C.在一个函数内，改变任一寄存器的值之前必须先将其原始数据保存在栈内D.判断两个寄存器中值大小关系，只需要SF（符号）和ZF（零）两个conditionalcode答案：ACD））2

(ch4,Jiangfang)9、下面对RISC和CISC的描述中，错误的是：（通常指令数目较少，指令的执行周期都较短。）指令系统中的指令数目较多，有些指令的执行周期很长；而RISC指令系统中指令系统中的指令编码长度不固定；RISC指令系统中的指令编码长度固定，这样使得RISC机器可以获得了更短的代码长度。指令系统支持多种寻址方式，RISC指令系统支持的寻址方式较少。机器中的寄存器数目较少，函数参数必须通过栈来进行传递；RISC机器中的寄存器数目较多，可以通过寄存器来传递参数，避免了不必要的存储访问。答案：BD(ch4,Jiangfang)10、下面对流水线技术的描述，正确的是：（）A.流水线技术不仅能够提高执行指令的吞吐率，还能减少单条指令的执行时间。B.不断加深流水线级数，总能获得性能上的提升。C.流水级划分应尽量均衡，吞吐率会受到最慢的流水级影响。D.指令间的数据相关可能会引发数据冒险，可以通过数据转发或暂停流水线来解决。答案：CD（ch4,Junlin）(11-13)、在教材所描述的流水线处理器（thePIPEprocessor）上分别运行如下四段Y86程序代码。请分析其中数据冒险的具体情况，并回答后续3个小题。#Program1:#Program2:mrmovl8(%ebx),%edxmrmovl8(%ebx),%edxrmmovl%edx,16(%ecx)noprmmovl%edx,16(%ecx)#Program3:mrmovl8(%ebx),%edxnopnoprmmovl%edx,16(%ecx)#Program4:mrmovl8(%ebx),%edxnopnopnoprmmovl%edx,16(%ecx)11、对于每段程序，请指出是否会因为数据冒险导致流水线停顿（Stall）。Program1：（），Program2：（-Stall答案：A,B,B,BProgram1：（ding答案:A,A,A,B），Program2：（-Forwarding），Program3：（），Program4：（）；12、对于每段程序，请指出流水线处理器内是否会产生数据转发（Forwarding）。），Program3：（），Program4：（）；13、对于每段程序，请指出流水线处理器内使用哪个信号进行数据转发，如果不进行数3

据转发，则用none表示。Program1：（），Program2：（），Program3：（A.m_valMB.W_答案:A,A,B,C（ch5,Guangyu）14、下面哪些选项是错误的？答：（）A.同一个任务采用时间复杂度为O(logN)算法一定比采用复杂度为O(N)算法的执行时间短B.编译器进行程序优化时，总是可以使用算数结合律来减少计算量C.增大循环展开（loopunrolling）的级数，有可能降低程序的执行性能（即增加执行时间）D.分支预测时，“总是预测不跳转”（branchnottaken）一定比“总是预测跳转”（branchtaken）预测准确率高答案：ABD（ch5,Guangyu）15、以下哪些程序优化编译器总是可以自动进行？（假设inti,intj,intA[N],intB[N],intm都是局部变量，N是一个整数型常量，intfoo(int)是一个函数）答：（优化前(j=0;j

（ch2,kaigui）第二题（8分）1）判断下表中每一行表达式对或错。如果错，请举出反例或简要说明原因（每行1分）intx,y;unsignedu,v;Trueorfalseifx<0,thenx*2<0u<=-1ifx>y,then-x<-yifu>v,then-u>-v答案Trueorfalseifx<0,thenx*2<0u<=-1ifx>y,then-x<-yifu>v,then-u>-vFTFF原因或举出反例X=-2w-1-1作为无符号来比大于uX=0,y=-2w-1U=2,v=1原因或举出反例2）请按IEEE浮点标准的单精度浮点数表示下表中的数值，首先写出形如(-1)s×M×2E的表达式，然后给出十六进制的表示。（每格1分）注：单精度浮点数的字段划分如下：符号位（s）：1-bit；阶码字段（exp）：8-bit；小数字段（frac）：23-bit；偏置值（bias）：127。Value(-1)s×M×2E，1<=M<2Hexrepresentation2-149答案Value(-1)sxMx2E1<=M<2(-1)x1.1x201.0x2-149Hexrepresentation0xBFC000000x000000012-1495

(ch3Xuetao)第三题（11分）阅读下面的C代码：/**Copyright(C)2013DavidlohrBueso<@>**Basedontheshift-and-subtractalgorithmforcomputinginteger*.*//***int_sqrt-roughapproximationtosqrt*@x:integerofwhichtocalculatethesqrt**Averyroughapproximationtothesqrt()function.*/unsignedlongint_sqrt(unsignedlongx){unsignedlongb,m,y=0;if(x<=1)returnx;m=1UL<<(BITS_PER_LONG-2);while(m!=0){b=y+m;y>>=1;if(x>=b){x-=b;y+=m;}m>>=2;}returny;}1）在64位的机器上BITS_PER_LONG的定义为long类型的二进制位数，它是多少位？2）填写下面反汇编中的缺失的内容：:4004c4:push%rbp4004c5:mov%rsp,%rbp4004c8:mov%rdi,-0x28(%rbp)4004cc:4004d4:4004d9:4004db:4004df:4004e1:4004e8:4004ef:4004f1:movqcmpqjamovjmpmovlmovljmpmov(1),-0x8(%rbp)$0x1,-0x28(%rbp)(2)-0x28(%rbp),%rax(3)$0x0,-0x10(%rbp)(4)(5)-0x10(%rbp),%rax,-0xc(%rbp)6

4004f5:4004f9:4004fd:400501:400505:400509:40050d:40050f:400513:400517:40051b:40051f:400524:400529:40052b:40052f:400530:答案：1、答：642、:4004c4:4004c5:4004c8:4004cc:4004d4:4004d9:4004db:4004df:4004e1:4004e8:4004ef:4004f1:4004f5:4004f9:4004fd:400501:400505:400509:40050d:40050f:400513:400517:40051b:40051f:400524:400529:40052b:40052f:400530:mov-0x8(%rbp),%rdxlea(6),%raxmov%rax,-0x18(%rbp)shrq-0x8(%rbp)mov-0x28(%rbp),%raxcmp-0x18(%rbp),%raxjb(7)mov-0x18(%rbp),%raxsub%rax,-0x28(%rbp)mov-0x10(%rbp),%raxadd%rax,-0x8(%rbp)shrq(8),-0x10(%rbp)cmpq$0x0,-0x10(%rbp)jne(9)mov-0x8(%rbp),(10)leaveqretqpush%rbpmov%rsp,%rbpmov%rdi,-0x28(%rbp)movq$0x0,-0x8(%rbp)cmpq$0x1,-0x28(%rbp)ja4004e1mov-0x28(%rbp),%raxjmp40052fmovl$0x0,-0x10(%rbp)movl$0x40000000,-0xc(%rbp)jmp400524mov-0x10(%rbp),%raxmov-0x8(%rbp),%rdxlea(%rdx,%rax,1),%raxmov%rax,-0x18(%rbp)shrq-0x8(%rbp)mov-0x28(%rbp),%raxcmp-0x18(%rbp),%raxjb40051fmov-0x18(%rbp),%raxsub%rax,-0x28(%rbp)mov-0x10(%rbp),%raxadd%rax,-0x8(%rbp)shrq$0x2,-0x10(%rbp)cmpq$0x0,-0x10(%rbp)jne4004f1mov-0x8(%rbp),%raxleaveqretq7

(ch3Xuetao)第四题（10分）阅读下面的汇编代码：:4004c4:4004c5:4004c8:4004cc:4004cf:4004d3:4004d5:4004da:4004dc:4004df:4004e2:4004e4:4004e6:4004ec:4004ef:4004f5:4004f8:4004fb:4004fd:4004ff:400505:400508:40050e:400511:400514:400516:40051b:400521:400524:40052a:40052d:40052e:pushmovsub%rbp%rsp,%rbp$0x10,%rspmov%edi,-0x4(%rbp)cmpl$0x1,-0x4(%rbp)4004dc$0x1,%eax40052d-0x4(%rbp),%eaxand$0x1,%eax%eax,%eax4004f50x200440(%rip),%eaxadd$0x1,%eaxmov%eax,0x200437(%rip)mov-0x4(%rbp),%eaxand$0x1,%eaxtest%al,%alje40050emov0x20042b(%rip),%eax$0x1,%eax%eax,0x200422(%rip)-0x4(%rbp),%eax$0x1,%eax%eax,%edi4004c40x20040f(%rip),%edx(%rax,%rdx,1),%edx0x200402(%rip),%eax(%rdx,%rax,1),%eaxjamovjmpmovtestjnemov#60092c#60092c#600930#600930addmovmovsubmovcallqmovleamovlealeaveqretq#600930#60092c1）程序main(){unsignedintn;for(n=1;n<4;n++){printf("f(%d)=%xn",n,f(n));}}的运行结果为：f(1)=1，f(2)=4e，f(3)=9f，请填写f函数所需要的内容（每空1分）：#defineN#defineM(1)(2)structP1{charc[N];char*d[N];chare[N];}P1;structP2{inti[M];charj[M];shortk[M];}P2;unsignedintf(unsignedintn){(3)unsignedintx=sizeof(P1);(4)unsignedinty=sizeof(P2);8

if((5))return1;if((6))x++;if((7))y++;return(8);}2、程序main(){printf("%x,%xn",f(2),f(2));}的运行结果为：（2分）1、答案：#defineN3#defineM5structP1{charc[N];char*d[N];chare[N];}P1;structP2{inti[M];charj[M];shortk[M];}P2;unsignedintf(unsignedintn){staticunsignedintx=sizeof(P1);staticunsignedinty=sizeof(P2);if(n<=1)return1;if((n&1)==0)x++;if((n&1)==1)y++;returnf(n-1)+(y)+(x);}2、答案：4f,4e（回答4e,4f给一半的分）9

(ch4Jiangfang)第五题（9分）在“取指-译码-执行-写回”的四级流水线中，各流水级的工作内容和延迟如上图所示，寄存器的延迟也已标出。数据和指令分别存放在不同的存储器中。CycleN写入寄存器文件的数据CycleN+1才可读出。请问：1）若不考虑流水线填充和清空时间，请计算该处理器的吞吐率。（1分）2）若将该处理器改造为单周期处理器（SEQ），请计算SEQ处理器的吞吐率。（1分）3）在上述流水线中，执行阶段包含了访问数据存储的时间。对于如下的Y86程序段，指令间存在哪些数据相关（dependence），会引起哪些数据冒险（hazard）？（5分）Prog:irmovl$128,%edx#instr1irmovl$3,%ecx#instr2rmmovl%ecx,0(%edx)#instr3irmovl$10,%ebx#instr4mrmovl0(%edx),%eax#instr5addl%ebx,%eax#instr64）以上的数据冒险，可以通过转发（forward）的方法解决。请结合上述程序代码和流水线结构图逐个说明解决方案。（2分）答案：1）1000/(280+20)=1000/300=3.33GIPS2）1000/(80+60+280+60+20)=1000/500=2GIPS3）Prog：irmovl$128,%edxirmovl$3,%ecxrmmovlmrmovladdlirmovl$10,%ebx;1、dx=128;2、cx=3;4、bx=10;6、bx=bx+ax%ecx,0(%edx);3、[dx]=cx0(%edx),%eax;5、ax=[dx]%ebx,%eax相关：1-3，2-3,1-5，4-6，5-6冒险：1-3，2-3，4-6，5-64）2-3，5-6：执行到译码的转发通路解决；1-3,4-6：写回到译码的转发通路解决。10

(ch4,Junlin)第六题（9分）请分析Y86ISA中定义的两条指令（cmovXX、call）和一条新加入Y86ISA的IA32指令（decl：将操作数减1）。若在教材所描述的SEQ处理器上执行这些指令，请按下表填写每个阶段进行的操作。如果在某一阶段没有任何操作，请填写none指明。注1、所用到的指令编码为：2fnrArBcmovXXrA,rB80DestcallDestC0rAFdeclrA注2、需说明的信号包括：icode,ifun,rA,rB,valA,valB,valC,valE,valP；theregisterfileR[],datamemoryM[],ProgramcounterPC,conditioncodesCC。（每格0.5分）StageFetchcmovXXrA,rBicode:ifun←M1[PC]rA:rB←M1[PC+1]valC←M4[PC+1]valP←PC+2DecodeExecutevalA←R[rA]valB←R[%esp]valE←0+valACnd←Cond(CC,ifun)（也可以写SetCC）MemorynoneWritebackPCupdateif(Cnd)R[rB]←valEPC←valPM4[valE]←valPR[%esp]←valEPC←valCvalE←valB+(-4)valE←valA+(-1)Cnd←Cond(CC,ifun)（也可以写SetCC）noneR[rA]←valEPC←valPvalP←PC+5valP←PC+2valA←R[rA]callDesticode:ifun←M1[PC]declrAicode:ifun←M1[PC]rA:rB←M1[PC+1]11

（ch5，yingfei）第七题（10分）已知如下的汇编程序实现了函数transform(char*src,char*tgt,chardelta)transform:jmpL2L1:add%edx,%eaxadd$1,$rdimov%al,(%rsi)add$1,$rsiL2:movzbl(%rdi),%eaxtest%al,%aljneL1movb$0,(%rsi)retq参考信息：64位指令集中传递前三个参数分别使用寄存器%rdi,%rsi和%rdx1）写出transform函数对应的C语言版本（2分）2）假设读写访存指令延迟为20个时钟周期，其他指令延迟为2个时钟周期，所有分支预测都成功。同时CPU包含足够多的部件来实现指令集并行，那么在最理想情况下CPE最低应该是多少（2分）？为什么（2分）？3）已知src对应字符串中每个字符c都满足0

(Chp6,Guangyu)第八题（9分）假设存在一个能够存储四个数据的Cache，每一个line的长度（B）为2字节。假设内存空间的地址一共是32字节，既内存空间地址长度一共是5个比特：从0（00000）到31（11111），一共有8个数据读取操作，每个操作的地址按顺序如下所示（单位是字节），数据替换采用LRU（leastrecentlyused）策略。数据访问地址：1->4->17–>2–>8->16–>9->01）如果Cache的结构是directedmapped（S=4，E=1），如下图所示，请在下图空白处填入，访问上述数据序列访问后Cache的状态。（注：TAG使用二进制格式，V=1代表数据有效，用[A-B]表示地址A到B之间对应的数据）（4分）V1110000000TAGDATAM[0-1]M[2-3]M[4-5]2）如果cache的结构如下图所示既(S=2,E=2)，请填入访问后的状态（2分）V11TAG000000DATAM[0-1]M[2-3]V10TAG010DATAM[8-9]在这种情况下，数据访问一共产生了多少次Miss_____6_____（1分）（顺序M->M->M->M->M->H->H->M）3）如果cache的结构变成（S=1，E=4），最终存储在Cache里面的数据有那些（注：只需要填写数据部分，顺序不限）？__________,M[0-1],___________,M[8-9],___________,_____________（2分）M[16-17],M[2-3]说明：1->4->17–>2–>8->16–>9->0（后四个不重复数据）13

本文标签： 数据指令执行流水线访问