Problem 2: Primary Processes

2.1

Explain how a (1,3) GPR instruction set architecture (ISA) differs from a (0,3) GPR ISA.

Answer: The ALU instructions of a (0,3) machine can never have a memory reference as an operand. These are typically called register-register machines.

The ALU instructions of a (1,3) machine are allowed to have up to one (1) memory reference. They are typically called memory-register machines.

So, the instructions (DADD R1, R2, R3) and (DADDI R1, R1,#10) are valid for both ISA's.

The instructions (DADD R1, (R2), R3) and (DADDI R1, (R2), #34) are only valid for the (1,3) ISA.

2.2

Suppose your memory is byte addressable and Little Endian, with four (4) bytes per word and eight (8) bytes per double word. Write an expression for Z, the address from which I would load the most significant byte (MSB) of a double word.

That is, choose A and B such that any byte loaded from an address, $Z$, where

$$Z \;\equiv \; A \;{\rm mod}\; B$$

will be properly aligned, and will contain the most significant bit (msb) of the associated double word.

Answer: This answer is embedded in the answer to problem 1.1. Because memory is little endian, the least significant byte (LSB), which happens to contain the least significant bit (lsb), of a word must be stored at an address $Y$, where

$$Y \;\equiv \; 0 \;{\rm mod}\; 4$$

.

That means that the MSB (the most significant byte, which contains the msb) must be stored at address $W$, where

$$W \;\equiv \; 3 \;{\rm mod}\; 4$$

Similarly, for a double word of 8 bytes, the LSB is at address

$$U \;\equiv \; 0 \;{\rm mod}\; 8$$

.

That means that the MSB (the most significant byte, which contains the msb) must be stored at address $W$, where

$$Z \;\equiv \; 7 \;{\rm mod}\; 8$$

2.3

Write an expression for memory access time, given that the miss rate is 10% and the miss penalty is 500 times the hit time (HT).

Answer: Since the actual hit time was not included in the problem, you get to have the blessed variable HT in your answer. Let AT be the memory access time. Then, we have:

$$\textrm{AT} = \textrm{HT} + 0.10 * 500 \textrm{HT}$$

While it doesn't make a difference in the answer to this problem if the hit time, HT, is in terms of number of clock cycles or time, it DOES matter if that number, 500, only applies if the HT is in terms of number of clock cycles, and not, say some portion of seconds.

2.4

Suppose that we consider a slightly different memory model. The miss penalty is still 500 times the hit time. However, separate memories are used for instructions and data. Furthermore,

• The miss rate for instructions is 7%,
• The miss rate for data is 13%.
• Loads transfer data from memory to registers, and make up 30% of the the instructions.
• Stores transfer data from registers to memory, and comprise 15% of the instructions.

Write an expression for the CPU execution time when the cache is not perfect.

Answer: This was the hard nasty question, because it made you think.

First, you are supposed to know that $\textrm{CPU} = \texttt{IC} * \textrm{CPI} * \textrm{CC}$ is the equation for CPU execution time.

Second, you are supposed to recognize that the memory related stuff has NO impact on the number of instructions (IC) and the clock cycle time (CC). So, the problem boils down to one that asks:

What is the CPI, assuming that the cache is NOT perfect?

From the wording of the problem, we have to distinguish between instruction memory access and data memory access. However, the read miss penalty is identical to the write miss penalty. So, we don't have to separate memory reads from writes.

One way to do this is to write:

$$\textrm{CPI} = \textrm{CPI}_{\rm perfect} + \textrm{CPI}_{{\r... ... \textrm{misses}} + \textrm{CPI}_{{\rm data}\; \textrm{misses}}$$

$$\textrm{CPI}_{{\rm ins}\;{\rm misses}} = \textrm{ins}\; \text... ...\textrm{rate} * \textrm{ins}\; \textrm{miss}\; \textrm{penalty}$$

$$\textrm{CPI}_{{\rm data}\; \textrm{misses}}= \% \texttt{data}... ...textrm{rate} * \textrm{data}\; \textrm{miss}\; \textrm{penalty}$$

Note: if the miss penalty differed for reads and writes, we'd have to break down the right hand side further into (data miss rate $*$ read miss penalty $*$ percentage of loads) added to (data miss rate $*$ write miss penalty $*$ percentage of stores)

But, we don't have that. So, we get the following pieces to work with.

$$\textrm{CPI}_{{\rm ins}\;{\rm misses}} = 0.07 * 500 \textrm{HT}$$

$$\textrm{CPI}_{{\rm data}\;{\rm misses}} = 0.45 * 0.137 * 500 \textrm{HT}$$

Now, notice that for this problem, the hit rate (HT) is assumed to be in terms of number of clock cycles.