FE Electrical Computer Systems Practice Problems

Answer: B) 11.0 ns

The average is the expected value over the two outcomes, each weighted by its probability:

$$T = h\,t_{hit} + (1 - h)\,t_{miss} = (0.92)(5) + (0.08)(80) = 4.6 + 6.4 = 11.0\text{ ns}$$

Only 8% of accesses go to main memory, yet they contribute more to the average than the 92% that hit, because each miss costs sixteen times a hit. That is the arithmetic behind the Handbook's description of the cache on p. 413 as a faster but smaller memory buffering data from slower memories: the hit rate is what makes it worth having, and the average moves toward the cache time only as the hit rate approaches one. Here a hit rate of 0.99 would give 5.75 ns and a hit rate of 0.80 would give 20 ns; the sensitivity to the last few percent of hits is why cache size, associativity and the replacement policies of p. 413 matter so much. Whether the miss time includes the cache lookup or is added to it is a convention that must be stated, which is why the stem does.

11.4 ns is \(5 + (0.08)(80)\), the model in which the 80 ns is an additional penalty on top of the lookup; the stem gives 80 ns as the total miss time.

42.5 ns is the unweighted mean of 5 and 80, the hit rate ignored.

5.0 ns counts the hits only.

Answer: D) 11 bits

The five fields have to add up to the width of the word, so the last one is the word less the other four:

$$6 + 5 + 5 + 5 = 21 \text{ bits allocated}$$

$$32 - 21 = 11 \text{ bits left for funct}$$

Two of the numbers in the figure are worth checking rather than taking on trust. Five bits per register field is exactly right for 32 registers, because 2^5 = 32; a machine with 64 registers would need six, and the fields would not fit. And 11 bits of funct encode 2^11 = 2,048 operations within each opcode class, which is why a fixed 32-bit word is not as cramped as it looks: the opcode names a family and funct picks the member.

Note that the 64-bit register width plays no part. It says how much data a register holds, not how many bits are needed to name one, and the two are independent: this instruction word could not carry a 64-bit constant even if every one of its bits were free.

10 bits is the answer with one bit lost in the addition, 6 + 5 + 5 + 5 read as 22 rather than 21; it is worth adding the three fives first, as 15, and then the six. 5 bits and 6 bits are the widths of a register field and of the opcode, read straight off the figure. They are the answers to a question one field away from the one asked, and the figure labels every width except the one wanted, which is precisely why they tempt.

Answer: A) 130 Ω

One loop, so one application of Kirchhoff's voltage law. Going round it, the rise supplied by the pin equals the two drops:

$$V_{OH} = I_F R + V_F$$

The diode is not a resistor and does not obey Ohm's law, but a forward-biased one holds a nearly fixed voltage across itself whatever the current, so it is treated as a constant drop of 2.0 V and the resistor takes what is left:

$$R = \dfrac{V_{OH} - V_F}{I_F} = \dfrac{3.3 - 2.0}{10 \times 10^{-3}} = \dfrac{1.3}{0.01} = 130\ \Omega$$

Two things are worth checking before this goes on a board. The pin has to be able to source 10 mA, which is within reach of most parts but not all, and the resistor dissipates I²R = (0.01)² x 130 = 13 mW, so any ordinary part will do.

The three wrong answers are the three ways this loop equation gets mishandled, and each is a different slip. 330 Ω is 3.3 V divided by the current, which is the answer if the diode is treated as a plain wire; that would leave the whole supply across the resistor and, with a real LED in place, the current would come out near 4 mA instead of 10. 200 Ω is 2.0 V divided by the current: the forward drop used as though it were the voltage across the resistor rather than the part taken away from it. 530 Ω adds the two voltages instead of subtracting, a sign error in the loop; it is worth noticing that it fails a sanity check, since a resistor cannot need more voltage across it than the supply provides.

Answer: C) 2^20 entries and 17 bits

The two halves come from two different address spaces, and keeping them apart is the whole of the question.

The entries come from the virtual side. A page of 4 KB is 2^12 bytes, which is the 12-bit offset the figure already gives. The virtual address is 32 bits, so the page number is what is left:

$$32 - 12 = 20 \text{ bits, hence } 2^{20} = 1{,}048{,}576 \text{ entries}$$

There is one entry per virtual page and the process can name 2^20 of them, so the table has that many entries whether or not the machine has the memory to back them.

The frame number comes from the physical side. The memory is 512 MB, which is 2^29 bytes, and it is divided into frames of the same 4 KB:

$$\dfrac{2^{29}}{2^{12}} = 2^{17} = 131{,}072 \text{ frames, hence } 17 \text{ bits}$$

So the page table has 2^20 entries, each holding a 17-bit frame number, plus the valid, dirty and protection bits that every entry also carries.

The asymmetry is the point and it is worth naming: 20 bits of virtual page number against 17 bits of frame number means the virtual space is eight times the physical memory, which is why the system is called virtual in the first place. Most of those 2^20 entries will be marked invalid at any moment.

Each wrong answer swaps one side for the other. 2^20 entries and 20 bits uses the virtual page number for both, as though every virtual page had a frame waiting for it. 2^17 entries and 17 bits does the reverse and sizes the table by the physical memory, which would be an inverted page table, a real design but not the one drawn. 2^17 entries and 20 bits swaps the two numbers outright.

Answer: C) 524 ms

The prescaler divides the clock before it reaches the counter:

$$f_{timer} = \dfrac{8 \times 10^6}{64} = 125\,000\text{ Hz}, \qquad T_{tick} = \dfrac{1}{125\,000} = 8\text{ µs}$$

A 16-bit counter runs from 0 to \(2^{16} - 1 = 65\,535\) and overflows on the next pulse, so the overflow period is \(2^{16}\) ticks:

$$T_{max} = 65\,536 \times 8\text{ µs} = 0.524\text{ s} = 524\text{ ms}$$

The two parameters trade range for resolution: without the prescaler the timer would resolve 125 ns but overflow every 8.19 ms, and a prescaler of 1024 would stretch the range to 8.4 s at a resolution of 128 µs. Longer intervals are measured by counting overflow interrupts in software or by cascading to a 32-bit counter, and a shorter period is obtained by loading a reload value so that the count starts above zero. The counter is the Handbook's binary number system of p. 393 in hardware, and timers are the peripheral behind every periodic interrupt, pulse-width modulation output and input capture measurement in an embedded system.

8.19 ms leaves the prescaler out, \(65\,536/8 \times 10^6\).

262 ms counts only to \(2^{15}\), half the range, as if one bit were lost to sign.

4194 ms applies the prescaler twice, \(65\,536 \times 64\text{ µs}\).