CSE 240A Homework 1
Due: April 14, 2022, 1:50 PM
Instructions
• Submit as a PDF via Gradescope.
• Due: April 14, 2022, 1:50 PM
• Homework is to be done individually.
• Start each question in a new page and mark the pages in Gradescope.
I. Problems
1. Consider the following fragment of C code:
for (i=0; i<100; i++) {
A[i]=B[i]+C;
}
Assume that A and B are arrays of 64-bit integers, and C and i are 64-bit integers. Assume that all
data values and their addresses are kept in memory (at addresses 1000, 3000, 5000, and 7000 for A,
B, C, and i, respectively) except when they are operated on. Assume that values in registers are lost
between iterations of the loop.
(a) Write the code for MIPS. How many instructions are required dynamically?
(b) How many memory data references will be executed? What is the code size in bytes?
2. For the following, we consider instruction encoding for instruction set architectures. Consider the case
of a processor with an instruction length of 12 bits and with 32 general-purpose registers so the size of
the address fields is 5 bits. Is it possible to have instruction encoding for the following?
(a) 3 two-address instructions
(b) 30 one-address instructions
(c) 45 zero-address instructions
3. Program A runs 20 billion instructions on a 2 GHz processor, and achieves a CPI of 1.5. Introduction
of a new instruction to the ISA (and recompiling the code) would allow a reduction in the instruction
count to 19 billion instructions, resulting in a speedup of 1.2. What is the CPI for the new code on
the improved processor?
4. Machine B runs at 2 GHz and has a CPI of 1.3 for a particular program. Machine C runs at 5 GHz and
has a CPI of 2.4 for that program, while executing 20% more instructions. Which machine is faster?
What is the speedup over the slower machine?
1
5. You have an optimization that speeds up floating point operations by a factor of 2, but does not
help other instructions. You have another optimization that only speeds up non-FP instructions by
10% (that is, it speeds up those instructions by a factor of 1.1), and you want to decide which to
use. Suppose your favorite program has 10% of its instructions FP operations. Further, assume FP
operations have a CPI of 3.0, while non-FP instructions have a CPI of 1.0.
6. (Amdahl’s law backwards) You improve your memory subsystem so that memory latencies are sped
up by a factor of 2.4. After applying the optimization, you observe that you now spend half your time
on waiting for memory. What percentage of the original execution (before the optimization) was spent
waiting for memory?
7. Suppose we wanted to add the auto-increment addressing mode to the MIPS ISA – e.g., lw R1, 1000(R2++).
This saves an instruction every time we observe a load followed by an increment of the address register.
Is this a good idea? Consider only performance, and assume that we have to increase cycle time by 5%
to accommodate the new instruction, that 20% of our instructions are loads, that we can apply this
change to 40% of all loads, and that the CPI doesn’t change.
8. Assume we are executing MIPS code where 15% of instructions are conditional branches, 20% are load
instructions, 5% are stores, and the rest are arithmetic. For this code,
(a) what percentage of all accesses to memory are for data?
(b) what percentage of all data accesses are reads?
(c) what percentage of all memory accesses are reads? [minor hint – what do we access memory for
besides loads and stores to data memory?]
2