CPSC 5155                                                                 Computer Architecture
Fall 2009                                                                                        Final Exam

This final exam is assigned on–line and is to be submitted on–line.  Students with access to
WebCT should probably use that tool to submit the answers.

Answers to this exam must be submitted not later than 11:30 PM on December 14, 2009.

Each student is expected to do his or her own work, and not to discuss any aspect of any
question with any other student.  This includes issues on interpretation of the questions.

1.   (15 points)    How many flip-flops are required for the following sequence detectors?

a)      10101010     an eight bit sequence
b)      11110000     an eight bit sequence
c)      110110         a six bit sequence
d)      1011             a four bit sequence

The first step is to determine the number of states required for the detector.  To detect an
N-bit sequence, one needs N states.  The number of flip-flops required is p, where p is the
solution to the equation 2p–1 < N
£ 2p.
a)      N = 8            p = 3
b)      N = 8            p = 3    same as a).  Only the number of bits is important.
c)      N = 6            p = 3    as 22 < 6
£ 23

d)      N = 4            p = 2.

2.   (15 points)    A byte-addressable memory is one in which each byte (collection of 8 bits)
has an individual address and in which each memory operation accesses a single byte.
You are given twelve 64K x 4 memory chips and construct a byte-addressable memory.
You use all of the chips in constructing the memory.
a)      How many bits are in the MBR?
b)      What is the size of the constructed memory (in bytes or KB)?
c)      How many bits must be in the MAR to address this memory?

Answer:  The chips must be used in pairs to create 8-bit entries.  Thus we have 6 pairs of
64K by 4 chips to make 6
· 64KB of memory or 384 KB.  384K = (28 + 27) · 210 =
218 + 217.  Obviously 218 < 218 + 217.  We also see that 218 + 217 < 218 + 218= 219, so
218 < 218 + 217
£ 219, or218 < 384K £ 219.  The address must have at least 19 bits.
a)      There are 8 bits in the MBR as the memory is byte addressable.
b)      The size of the memory is 384KB or 393,216 bytes.
c)      The MAR must contain 19 bits to address this memory.

3.   (10 points)             Draw a circuit diagram to show how to implement
a) a three-input AND gate using only two-input AND gates.
b) a four-input AND gate using only three-input AND gates.

a)   There are a number of solutions to this problem.  Here are three solutions.

b)   There are quite a number of solutions to this problem.  Here are six.

There were very few surprises here.  Most students got one of the above answers or another
correct variant of the answer.

The figure at the left is the most common incorrect answer.

One should note that this does implement a four-input AND
gate, but that it uses two-input AND gates.  The problem
specifies three-input AND gates to be used.

4.   (10 points)     Use a JK flip-flop and (optionally) a NOT gate to implement
a)             a D flip-flop.
b)            a T flip-flop.

ANSWER:  Only the D flip-flop uses a not gate.  Here are the two circuits.

The following table shows that the two designs really act as D and T flip-flops.

 D Q(t) J K Q(t+1) T Q(t) J K Q(t+1) 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 1 1 0 1 0 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 0

NOTE: This problem has been solved in class and is covered in the course notes.

5.   (15 points)       Calculate the effective address for each of the following instructions.  Assume
that the contents of the index register 3 are (%R3) = – 7; W is the memory location 0x007D and
that a partial memory map looks as follows:

 Address 75 76 77 78 79 7A 7B 7C 7D 7E 7F 80 81 82 Contents 4D 7F 4F BA BA 77 8F 22 82 DD E1 23 F0 0D

a)   LDR, %R1      W                    Remember that W refers to address 0x7D

b)   BR *                W                    Remember that this is indirect addressing

c)   BR *                W, 3                Handle this the way that the Boz–5 does

a)   Effective address is W, W = 0x7D.
b)   Effective address is EA = M[W] = M[0x7D] = 0x82.
c)   Pre-Indexed    EA = M[W + (%R3)] = M[0x7D – 7] = M[0x76] = 0x7F
Post-Indexed  EA = M[W] + (%R3) = M[0x7D] – 7 = 0x82 – 7 = 0x7B

The Boz–5 is post-indexed, so the second answer is correct.

6.   (15 points)   Examine the following memory map of a byte–addressable memory.
Let W refer to address 109.   All numbers are HEXADECIMAL.

 107 108 109 10A 10B 00 11 23 17 CA

a)     Assuming big–endian organization, what is the value of the 16–bit integer at W?

b)     Assuming little–endian organization, what is the value of the 16–bit integer at W?

c)     Assuming little–endian organization, what is the value of the 8–bit integer at W?

Answer:  The 16–bit entry at address 109 occupies bytes 109 and 10A, as follows.

 107 108 109 10A 10B 00 11 23 17 CA

a)     In big–endian, the “big end” is stored first:             0x2317

b)     In little–endian, the “little end” is stored first          0x1723.

c)     This is a trick question.  The answer is 0x23.

COMMENT: The 16–bit (two byte) entry at location 109 will always occupy bytes 109 and 10A.

7.   (20 points) A computer memory system uses a primary memory with 100 nanosecond
access time, fronted by a cache memory with 4 nanosecond access time.  What is the
effective access time if
a)  The hit ratio is 0.7?
b)  The hit ratio is 0.9?
c)  The hit ratio is 0.95?
d)  The hit ratio is 0.99?

ANSWER:  There is a problem with names here.  For the cache scenario, we have
TP as the access time of the cache
TS as the access time of the primary memory.

The equation is TE = h·4 + (1 – h)·100.

a)   h = 0.7         TE = 0.7·4 + (1 – 0.7)·100 = 0.7·4 + 0.3·100 = 2.8 + 30.0                = 32.8

b)   h = 0.9         TE = 0.9·4 + (1 – 0.9)·100 = 0.9·4 + 0.1·100 = 3.6 + 10.0                = 13.6

c)   h = 0.95       TE = 0.95·4 + (1 – 0.95)·100 = 0.95·4 + 0.05·100 = 3.8 + 5.0            = 8.8

d)   h = 0.99       TE = 0.99·4 + (1 – 0.99)·100 = 0.99·4 + 0.01·100 = 3.96 + 1.0         = 4.96