Name:_____________________________________________ Login:______________ 1 University of California at Berkeley College of Engineering Department of Electrical Engineering and Computer Sciences CS61c Summer 2001 Aner Ben-Artzi Jeremy Lin Mark Marron Songhwai Oh Woojin Yu Final Exam This is a closed-book exam. No calculators please. You have 2 hours. Each question is marked with its number of points. This exam booklet should have 15 pages. Check to make sure that you have all the pages. Put your name and login neatly on each page. Show your answers in the space provided for them. Write neatly and be well organized. If you need extra space to work out your answers, you may use the back of previous questions. However, only the answers appearing in the proper answer space will be graded. Good luck! Problem Maximum Score 1 11 2 15 3 25 4 15 5 14 6 20 Total 100Name:_____________________________________________ Login:______________ 2 MIPS instructions Important – please note: The MIPS instructions shown in this table are the ones that you must use on the entire exam. Do not use any instructions that are not in this table. If you use any instructions not listed below, you will lose points. The columns under “format” show the bit fields of the instructions. The number in the parentheses following each name is the number of bits in that field. In the table, PC refers to the program counter. You may carefully tear this page from your exam booklet for easy reference. name Format syntax meaning Op(6) rs(5) rt(5) rd(5) shamt(5) func(6) add 0 0 32 add rd,rs,rt rd = rs + rt sub 0 0 34 sub rd,rs,rt rd = rs - rt and 0 0 36 and rd,rs,rt rd = rs AND rt or 0 0 37 or rd,rs,rt rd = rs OR rt sll 0 0 0 sll rd,rt,shamt rd = logical shift rt left shamt bits srl 0 0 2 srl rd,rt,shamt rd = logical shift rt right shamt bits slt 0 0 42 slt rd,rs,rt if rs<rt set rd=1 else rd=0 jr 0 0 0 0 8 jr rs PC=rs Op(6) rs(5) rt(5) immediate(16) addi 8 addi rt,rs,immed rt = rs + immed andi 12 andi rt,rs,immed rt = rs AND immed ori 13 ori rt,rs,immed rt = rs OR immed lw 35 lw rt,immed(rd) rt = MEMORY[rd+immed] sw 43 sw rt,immed(rd) MEMORY[rd+immed] = rt lui 15 lui rt,immed rt = immed shifted left 16 bits beq 4 beq rs,rt,label branch if equal bne 5 bne rs,rt,label branch if not equal Op(6) target address(26) j 2 j label jump jal 3 jal label jump and linkName:_____________________________________________ Login:______________ 3 Question 1(11 points) Part (a) was worth 3 points, and the rest were worth 2 points each. a. Give following float value in IEEE 754 single precision format (in hexadecimal). 118.125 (dec) = _______________________________ (hex) Answer. 1.110110001 x 26 = 42EC4000 (hex) b. Give the truth table and the gate diagram for NOT(P) OR Q, where P and Q are inputs. P Q Output 0 0 1 1 0 0 0 1 1 1 1 1 c. Describe how the relocation information in an object file is used and name a program that makes use of this information. Answer. The linker uses the relocation information to help it figure out what parts of an object file to relocate and where to relocate them when it builds the final executable. Loader was also accepted as a program that uses the relocation information. d. How does the cache block size affect performance? Answer. Increasing the block size increases performance up to a point, but performance decreases if the block size is too large. e. List one pro and one con of increasing the size of the TLB. Answer. Increasing the TLB size tends to decrease TLB misses, but it also increases the complexity of the hardware, makes it harder to make it fast, etc.Name:_____________________________________________ Login:______________ 4 Question 2(15 points) a. In UNIX, directories are special files that contain information about the files in the directory. For example, say you are trying to read the file final-sol.txt, which is in a directory called secret. Then before the OS can read the file, it has to read the special directory file corresponding to secret and find out where final-sol.txt is stored on disk. In order to make accessing the directory files fast, what general area of the disk would be ideal for storing the directory files? Briefly, but specifically, explain why. Assume that no caching of disk reads is involved. This part was worth 2 points. Answer. It should be stored on the middle tracks, since the disk heads are closest to these tracks on average. You got 1 point if you said that it should be placed closest to where the disk heads were or something similar. b. (For this part, use the information and assumptions given in Part a.) On UNIX, your incoming mail is delivered by appending the message contents to a regular file called the mail spool (it basically serves as your inbox). So if your username was “wooj”, new mail might typically be written to the file /var/mail/wooj (a file named “wooj” in the directory /var/mail – remember that directories can contain directories). Suppose that you have PINE (your email client) set up to display your inbox on startup (i.e., PINE will read the mail spool on startup). Assuming that all other non-disk-related work takes negligible time. You know these disk parameters: Average seek time : 20 ms Rotational speed : 3000 RPM Block size : 4 KB Transfer rate : 0.4 MB/sec Overhead from controller, filesystem, etc. : negligible (0 seconds) and that: • Your disk is so fragmented, blocks belonging to a file are effectively spread out on disk randomly. • The three directories accessed on the way to the mail spool are /, var, and mail. The size of / is 4 KB, var is 4 KB, and mail is 128 KB. Your mail spool is 4 MB large. How long do you expect to wait for PINE to start up? Show your work. This part was worth 6 points. Answer. From the rotational speed, the average rotational latency is 10 ms. The average seek time is given as 20 ms. Transfer time takes about 10 ms per block. There are 1024 + 32 + 1 + 1 = 1058 blocks total. Since the blocks are distributed randomly on disk, rotational latency and seek time come into play on every block. Thus, 1058 · (10 ms + 20 ms + 10 ms) ≈ 42.32 seconds. Because
View Full Document
Unlocking...