Final Exam
CSC 252
8 May 2019
Computer Science Department
University of Rochester

Instructor: Yuhao Zhu
TAs: Jessica Ervin, Yu Feng, Max Kimmelman, Olivia Morton, Yawo Alphonse Siatitse,
Yiyang Su, Amir Taherin, Samuel Triest, Minh Tran

​Name​: ____________________________________

Problem 0 (3 points):
Problem 1 (17 points):
Problem 2 (10 points):
Problem 3 (20 points):
Problem 4 (20 points):
Problem 5 (30 points):
Total (100 points):

Remember “​I don’t know​” is given 15% partial credit, but you must erase everything else. This
does not apply to extra credit questions.

Your answers to all questions must be contained in the given boxes. The lengths of the boxes
should be more or less indicative of the lengths of your answers. Use spare space to show all
supporting work to earn partial credit.

You have 2 hours 45 minutes to work.

Please sign the following. I have not given nor received any unauthorized help on this exam.

Signature:___________________________________________________________

GOOD LUCK!!!
And have a great summer break.


1
Problem 0: Warm-up (3 Points)

Some people say 252 shouldn’t be required for the BS. What say you? (Hint: the correct answer
is YES, IT SHOULD BE, but we are not necessarily looking for the correct answer here.)



Problem 1: Floating-Point Arithmetics (17 points)

In this problem, we assume that IEEE decided to add a new N-bit representation, with its main
characteristics consistent with the other IEEE standards. This N-bit representation could
represent the value exactly, but cannot represent the value exactly. The smallest21 8
1 43 4
1

positive normalized value it can represent is 2​-62​.

Part a) (3 points)​ Put in binary normalized form.21 8
1




Part b) (3 points)​ Of the N bits, how many bits are fraction bits?



Part c) (3 points)​ Of the N bits, how many bits are exponent bits?



Part d) (4 points)​ What is N?



Part e) (4 points)​ What is the bias?


2
Problem 2: Pipelining (10 points)

A pipelined processor has 5 stages with delays as follows:

Stage 1 28 ns
Stage 2 59 ns
Stage 3 23 ns
Stage 4 34 ns
Stage 5 36 ns

The delay of pipeline registers between two stage is 1 ns.

Part a) (4 points)​ What is the cycle time of this processor? Recall the cycle time refers to the
delay of a single clock cycle.




Part b) (6 points) ​Now we execute 8 instructions on this pipelined processor. What is the
speedup that the pipeline achieves compared to a non-pipelined design? Assume that there are
no pipeline stalls. Show your work to earn partial credit.




3
Problem 3: Assembly Programming (20 points)

Clark Kent has taken CSC 252 and is working on research project on ISA. Clark defines
Kryptonian numbers and Xenonian numbers as follows.
● A binary number is said to be ​Kryptonian ​if and only if there are more 0’s than 1’s when
we discard the leading zeros. For example, 100100​
2​ is Kryptonian and 000001111​2​ is not.
● A binary number is said to be ​Xenonian ​if and only if there are exactly 4 1’s. For example,
110110​
2​ is Xenonian and 11111​2​ is not.

Part a) (8 points) ​ Consider the 32-bit two’s complement representation. Is 18​
10​ a Kryptonian,
and is -18​
10 ​a Xenonian? Show your work to earn partial credit.



Part b) (12 points) ​Clark wants to add two new flags to the standard x86-64 ISA.
● Krypton Flag: set if a number is Kryptonian.
● Xenon Flag: set if a number is Xenonian.

According to Clark’s ISA specification, the ​addl ​ instruction sets these two flags according to the
addition result, and the ​movl ​ instruction sets these two flags according to the content of the
source operand, i.e., the content that is being moved. No other instructions change these two
flags. Other flags are set as in the standard x86-64 ISA.

Further, Clark implemented the following two instructions:
● jkr addr ​: jump to the address specified by ​addr ​ if the Krypton flag is set and the
Overflow flag is not set.
● jxn addr ​: jump to the address specified by ​addr ​ if the Xenon flag is set and the
Overflow flag is not set.

He wrote the following function in assembly language to test his work. Recall from the
programming assignments that ​movl ​ instructions move a 4 byte integer to the destination, and
the size of the data moved by the ​mov ​ instructions is implicit in the operands. We assume an
assembly syntax where the source is the first operand and the destination is the second operand.

00000000000005fa :
5fa: 55 push %rbp
5fb: 48 89 e5 mov %rsp,%rbp
4
5fe: 89 7d ec mov %edi,-0x14(%rbp)
601: 48 89 75 e0 mov %rsi,-0x20(%rbp)
605: c7 45 f8 00 00 00 00 movl $0x0,-0x8(%rbp)
60c: c7 45 fc 12 00 00 00 movl $0x12,-0x4(%rbp)
613: eb 0e jmp 61f
615: 7e 04 jkr 61b
617: 83 45 f8 01 addl $0x1,-0x8(%rbp)
61b: 83 45 fc 01 addl $0x1,-0x4(%rbp)
61f: 83 7d fc 35 cmpl $0x35,-0x4(%rbp)
624: 7e ec jle 615
626: b8 00 00 00 00 mov $0x0,%eax
62b: 5d pop %rbp
62c: c3 retq

Unfortunately, he made a small mistake in his implementation such that the machine will jump
to the designated address on any ​jkr ​/​jxn ​ instruction regardless of the flags.

(4 points)​ On this faulty machine, what is the value of ​-0x18(%rsp) ​ after the ​foo ​ function
returns? Hint: what do ​pop ​ and ​retq ​ do to ​%rsp ​?



(4 points)​ He then fixes the mistake, and runs the same program again on this correct
machine. What is the value of ​-0x18(%rsp) ​ now after the ​foo ​ function returns?



(4 points)​ To test the Xenon flag and the ​jxn ​ instruction, Clark removes the instruction at
0x61f ​ and replaces the instruction at ​0x624 ​ with ​jxn 615 ​. What is the value of
-0x18(%rsp) ​ after the ​foo ​ function returns?


5
Problem 4: Cache (20 points)

Solar radiation can randomly flip bits in the computer system. Therefore, a cache on a
space-faring vehicle, which is exposed to solar radiation, utilizes error-correcting codes (ECC)
for each of its cache blocks​ to detect if bits have been flipped. These ECC bits add to the
overhead of the cache, in addition to the usual overhead bits such as valid bits and tags, etc.

On a memory access, the cache operates as normal, but in addition to checking hit/miss it will
also check if the content in the cache block has been corrupted. This is done by checking the ECC
bits. How exactly ECC bits are used to detect corruption is irrelevant to this problem. If the ECC
bits associated with a block indicate that the data in the block is corrupted, that cache access is
regarded as a cache miss. For the sake of the problem, assume that the memory is incorruptible.

The physical memory is byte addressable, and is 64 KB in size. Each cache block is 4B, and
requires 6 extra bits for the error-correcting codes. The cache is 2-way associative with the LRU
replacement policy. The entire cache has an overhead of 3712 bits.

Part a) (4 points) ​For this cache to function properly, should it use a write-back policy or a
write-through policy upon a write hit?



Part b) (4 points) ​Determine the number of offset bits.



Part c) (4 points)​ Determine the number of tag bits.



Hint: how many bits does each set have to have to implement the LRU replacement policy? Use
the box below to show your work to earn partial credit.


6
Part d) (8 points)​ Given the following sequence of 9 cache accesses; some cache accesses
result in loads from the physical memory. Assume that the initial state of the cache is empty.

Address Load From Memory?
a) 0x3420 Yes
b) 0x3423 Yes
c) 0x062e Yes
d) 0x1e2f Yes
e) 0x73ec Yes
f) 0x062f No
g) 0x0e2f Yes
h) 0x1e2e Yes
i) 0x0e2e Yes

Determine which accesses were necessarily a result of cache corruption due to solar radiation.
Write the letters corresponding to the memory addresses below:


















7
Problem 5: Virtual Memory (30 points)

The diagram below shows the interactions between components of a computer system resulting
from a ​single​ virtual memory access from the CPU. You are given the following information:
● Assume a single-level virtual memory system.
● The virtual address space is 128 KB.
● The physical memory size is 32 KB.
● The L1 cache block size is 2 B.
● The value stored in the Page Table Base Register (PTBR) is 0x260.
● Each Page Table Entry (PTE) takes 2 B and has the following structure:

Valid <1-bit> Padding of zeros Physical page number


Part a) (22 points)​ Fill in the right column of the table below with answers to the questions
about each step in the diagram above. “I don’t know” is accepted at each entry.
1 CPU reads virtual address 0x_______
2 MMU checks TLB. Is this a hit or a miss?
3 MMU accesses memory at physical address
0x2F0. Is this a hit or a miss?

4 What is the most significant bit of the data
returned to the MMU and TLB?

5 What happens at this step?
(Answer in 15 words or fewer)



8
6 16 bytes are returned. (no question)
7 CPU reads virtual address 0x_______
8 MMU checks TLB. Is this a hit or a miss?
9 Data returned from TLB to MMU is 0x______
10 MMU accesses memory at physical address
0xA48. Is this a hit or a miss?

11 Is this an access to the page table?
12 How many bytes of data are returned here?
13 Requested data is returned to the CPU. (no question)

Part b) (3 points)​ How many pages does the entire page table occupy?



Part c) (3 points)​ How many physical memory accesses were made during this single virtual
memory access?



Part d) (2 points)​ What would the system do differently at step 3 and 4 if the L1 cache block
size is 1 B?



9