2022年复旦计算机级春季期末考试试题A .pdf

《2022年复旦计算机级春季期末考试试题A .pdf》由会员分享，可在线阅读，更多相关《2022年复旦计算机级春季期末考试试题A .pdf（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 复旦大学计算机科学技术学院计算机原理期末考试试卷A卷共 13 页课程代码： INFO130054.01-02 _ 考试形式：开卷2010 年 6 月（本试卷答卷时间为100 分钟，答案必须写在答卷上，做在试卷上无效）专业学号姓名成绩题号1 2 3 4 5 6 7 总分得分Problem 1.Number Conversion: IEEE 754 single precision 32-bit float standard representation with a little change is illustrated below. Normalized: (-1)sign * (1.f

2、raction) * 2exponent-127(exp=1 to 254)Denormalized: (-1)sign * (0.fraction) * 2-126(when exp=0, fraction0)Zero: all 0s in all 3 fields1)Convert the number -35.390625 into this changed IEEE 754 FP single precision representation (in hex). (-35.390625)10= (0 x )16名师资料总结 - - -精品资料欢迎下载 - - - - - - - - -

3、 - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 20 页 - - - - - - - - - 2 2)With changed 32-bit float representation, what is the equivalent value as a decimal number? A: (0011 1111 0001 0000 0000 0000 0000 0000)2B: (0000 0000 0011 0101 0000 0000 0000 0000)23)Calculate the sum of (35.390625)10 and (0

4、011 1111 0001 0000 0000 0000 0000 0000)2using changed 32-bit float representation, and then round the sum (in binary number value, e.g. (1000.11)2for (8.75)10 ) to 4 bits to the right of the binary point by both round-up and round-down. Give your steps detailed. 4)Given three numbers f1, f2 and f3 o

5、f this changed 32-bit representation, none of them equals +, -or NaN, and x is signed 32-complement representation. Please tell whether two C expressions below are always true. If yes, give the reason in detail; If no, give a counterexample and show the detail computation steps to get false. A: x =

6、= (int) (float) x; B: (f1 f2) = = (f1 + f3) (f2 + f3) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 20 页 - - - - - - - - - 3 Problem 2.Please read the following C code and assembly code and then fill in the blanks. #include int p54 = 43,56,78,69,-7,89,7,23,24,

7、36,88,67, 12,56,78,90,62,93,-78,9; int main(void) int result = cal(5,4); printf(The result is %dn, result); int cal(int a, int b) int i; int result=0; for ( i = 0; i b; i+) if (i a-1) result -= i*pi+1i; return result; The assembly code:cal: pushl %ebp movl %esp, %ebp subl $8, %esp movl $0, -8(%ebp)

8、movl $0, -4(%ebp) .L3: movl -4(%ebp), %eax cmpl 12(%ebp), %eax jl .L6 jmp .L4 .L6: movl 8(%ebp), %eax decl %eax cmpl %eax, -4(%ebp) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 20 页 - - - - - - - - - 4 jge .L5 movl -4(%ebp), %eax sall _ _, %eax movl %eax, %ed

9、x addl -4(%ebp), %edx movl -4(%ebp), %eax imull _ _(,%edx,4), %eax movl %eax, %edx leal -8(%ebp), %eax subl %edx, (%eax) .L5: leal -4(%ebp), %eax incl (%eax) jmp .L3 .L4: movl -8(%ebp), %eax leave retPlease give the reason for the blanks you filled in the assembly code and the result of the printf i

10、n main function.名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 20 页 - - - - - - - - - 5 Problem 3.The following figure illustrates a five stage pipeline processor similar to that in your text book (Figure 4.53, Page 334 in English Book). Notice there are three

11、differences for this architecture from that in your book. First difference is that Function Units in Stage E become multi-cycle function units. Now stage E contains three function units, two Adder and one Subtracter. The Subtracter can only handle subtraction operations and takes 3 cycles to complet

12、ion. The Adder can handle other calculation exception subtraction and takes 2 cycles to completion. Notice one Adder or Substracter can handle only one instruction at a time, that is, other instructions must wait in its Stage D until the expected Adder or Substracter is free. Second difference is th

13、at Memory Units will consume different cycle to complete a memory access. For a cache hit, it takes 1 cycle; for a cache miss , it takes 6 cycles; for a non-memory instruction , it takes 1 cycle to pass Stage M. And only one instruction can occupy the memory units, that is, if two memory instruction

14、s are entering the Stage M at the same time, the second instruction will wait the first instruction to complete before retrieve its own memory data. Third difference is that this architecture is 2-issue in-order pipeline processor. It means the fetch stage can fetch at most two instructions and all

15、the state registers between stages can also store at most two instructions states. The fetch units will fetch as many instructions as possible to fill the state registers between Stage F and Stage D. 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 20 页 - - - - -

16、 - - - - 6 1)This problem is based on the code in figure, which will be executed on the processor described above. Assume in cycle 0, no instruction is executed, and in cycle 1, the first two instructions are fetched. Fill in the blanks. (Stage: F, D, E, M, W, finished or not fetched , undecidable v

17、alue marked with “-”) (10 )名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 20 页 - - - - - - - - - 7 2) The cache miss in the above code cause the CPU to waste several cycles, because the next instruction depends on the value fetched by the cache miss instruction

18、. So, we have a technical called “ code motion” which changes the order of instructions so that the time used to load the data from memory can be hidden by the instructions do not use memory and do not depends on the memory instruction. Use this technology to optimize the original code in figure to

19、get least execution time and write you code down. 3) How many cycles are saved from this optimization?_1_ 4) The last instruction in this optimized instruction flow will exit its write-backstage in Cycle_2_ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 20 页 -

20、- - - - - - - - 8 Problem 4.Implement the following 2 functions and make their functionalities be the same with the description. The coding rules are also same as Lab1. (If you think there is nothing to do, just fill the blank with “-” ) 1)bitOr (10? + 2 ? ) /* bitOr * x|y using only and &. * * Exam

21、ple: bitOr(6, 5) = 7. * Legal ops: , & * Max ops: 8 */ int bitOr (int x, int y) /* Please fill your code in the answer paper */ return ret; 2)logicalShift (2? * 6) /* logicalShift * shift x to the right by n, using a logical shift. * can assume that 1 = n = 31. * * Examples: logicalShift(0 x87654321

22、,4) = 0 x08765432, * Legal ops: & | + */ int logicalShift (int x, int n) int mask= 0 x7f _1_ | 0 xff _2_ | 0 xff _4_) _5_ ( mask (_6_); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 20 页 - - - - - - - - - 9 Problem 5.A computer has main memory(MM) with 256K wo

23、rds size, and a 8K words set associative cache. Each set of cache has 4 pages with 64 words in each page. Suppose the cache is initially empty. CPU read data from MM at the address of 0, 1, 2, , 8447(When read misses in cache, the full page containing destination bytes is written into the cache firs

24、t and read from the cache). This reading process repeats for 20 times. We know that cache access time is 10% of that of MM. LRU replacement policy is used on cache. Please figure out how many times the total reading operations will be faster using cache compared with no cache? You must write out com

25、plete steps with necessary descriptions. Problem 6.You are given the following definitions: struct pc int x; int y; int z; ; struct pc sq1616; int i,j; Assume the following: sizeof(int) = 4. sq begins at memory address 0. The machine has a 2048-byte direct-mapped data cache with 32-byte blocks. The

26、cache is initially empty. The only memory accesses are to the entries of the array sq. Variables i and j are stored in registers. 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 20 页 - - - - - - - - - 10 Determine the cache performance of the following code: for

27、 (i = 0; i 16; i +) for (j = 0; j 16; j +) sqij.x = 0; sqij.y = 0; sqij.z = 1; 1) What is the total number of writes? 2) What is the total number of writes that miss the cache? Given the above assumptions, determine the cache performance of the following code: for (i = 0; i 16; i +) for (j = 0; j 16

28、; j +) sqji.x = 0; sqji.y = 0; sqji.z = 1; 3) What is the total number of writes? 4) What is the total number of writes that miss the cache 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 20 页 - - - - - - - - - 11 Problem 7.Virtual Address Translation We consid

29、er a virtual address system with the following parameters. The memory is byte addressable. Virtual addresses are 20 bits wide. Physical addresses are 16 bits wide. The page size is 4096 bytes. The TLB is 4-way set associative with 16 total entries. In the following tables, all numbers are given in h

30、exadecimal. The contents of the TLB and the page table for the first 16 virtual pages are as follows. If a VPN is not listed in the page table, assume it generates a page fault. TLB Page Table Index Tag PPN Valid VPN PPN Valid 0 03 B 1 00 7 1 07 6 0 01 8 1 28 3 1 02 9 1 01 F 0 03 A 1 1 31 0 1 04 6 0

31、 12 3 0 05 3 0 07 E 1 06 1 0 0B 1 1 07 8 0 2 2A A 0 08 2 0 11 1 0 09 3 0 1F 8 1 0A 1 1 07 5 1 0B 6 1 3 07 3 1 0C C 1 3F F 0 0D D 0 10 D 0 0E E 0 32 0 0 0F D 1 1)In the four rows below, mark the bits that constitute the indicated part of the virtual address with an X. Leave the remaining bits of each

32、 row blank. Virtual Page Number 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 VPN 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 20 页 - - - - - - - - - 12 Virtual Page Offset 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 VPO TLB Tag 19 18 17 16 15 14 1

33、3 12 11 10 9 8 7 6 5 4 3 2 1 0 TLBT TLB Index 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 TLBI 2)For the virtual address 0 x7E37C, indicate the physical address and various results of the translation. If there is a page fault, enter “” for the PPN and Physical Address. All answers should be gi

34、ven in hexadecimal. Virtual Address (one bit per box) 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 Parameter Value VPN TLB Tag TLB Index TLB Hit? (Y/N) Page Fault? (Y/N) PPN Physical Address 3)For the virtual address 0 x16A48, indicate the physical address and various results of the translation

35、. If there is a page fault, enter “” for the PPN and Physical Address. All answers should be given in hexadecimal. Virtual Address (one bit per box) 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 Parameter Value VPN TLB Tag TLB Index 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理

36、 - - - - - - - 第 12 页，共 20 页 - - - - - - - - - 13 TLB Hit? (Y/N) Page Fault? (Y/N) PPN Physical Address 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 20 页 - - - - - - - - - 14 复旦大学计算机科学技术学院计算机原理期末考试答题纸A卷课程代码： INFO130054.01-02 _ 考试形式：开卷2010 年 6 月（本试卷答卷时间为100 分

37、钟，答案必须写在答卷上，做在试卷上无效）专业学号姓名成绩题号1 2 3 4 5 6 7 总分得分Problem 1.名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 20 页 - - - - - - - - - 15 Problem 2.名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 20 页 - - - - - - - - - 16 Proble

38、m 3.名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 20 页 - - - - - - - - - 17 Problem 4.名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 20 页 - - - - - - - - - 18 Problem 5.名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - -

39、 - - - 名师精心整理 - - - - - - - 第 18 页，共 20 页 - - - - - - - - - 19 Problem 6.名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 20 页 - - - - - - - - - 20 Problem 7.名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 20 页 - - - - - - - - -