CS2200 Question 1: Calling Convention Solution

Recall that the stack is used for communication between the caller and the callee. It stores information as shown below:

Q1.1 (4 Points)
Before executing JALR, the caller saves $ra on the stack. Explain why.
Q1.2 (4 Points)
Explain the benefit of dividing the register save/restore chore between the caller and the callee.
Q1.3 (4 Points)
Explain the benefit of having a frame pointer. Who saves the "prev frame pointer" on the stack? In the above picture, show where the frame pointer is currently pointing to on the stack.
Question 2: Switch Statement and Jump Table (10 points) (5 minutes)
High-level languages provide a “switch” statement that looks as follows.
switch (k) { case 0: case 1: case 2: case 3:
……
}
The compiler writer knows that “k” can take contiguous integer values from 0 to 9 during execution. She decides to use a jump table data structure (implemented as an array indexed by the value contained in k) to hold the start address for the code for each of the case values as shown below:

Assuming we are using the LC-2200 instruction set architecture (See Appendix). The architecture is word addressable.
Q2.1 (5 Points)
Assume the base address of the jump table is stored in the register $t0, the value of k is stored in register $t1. Write a series of instructions that reaches the code for case k.
Q2.2 (5 Points)
Can this implementation of a switch statement be simulated by a series of conditional branch instructions without accessing memory? If so, which approach is more time-efficient? Why? (Hint: think about space and time complexity)
Question 3: Datapath (12 points) (7 minutes)
The datapath shown below corresponds to the familiar LC-2200, 32-bit word addressable architecture, with the difference that the ALU also supports a multiply operation, selected by setting the ALU’s func control signal to 100.

We are introducing a new instruction MULTADD Rx, Ry, Rz to the LC-2200 ISA. The semantics of the instruction is as follows:
● Rx ← Rx + (Ry * Rz)
The instruction’s format is as shown below:

Given the above datapath, write the sequence of micro-states and signals within that are required to implement the MULTADD instruction (you ONLY need to write the sequence for the execution macrostate of the instruction). For each microstate, show the datapath action (in register transfer format such as A ← Ry), followed by the set of control signals you need to enable for the datapath action (such as DrALU).
NOTE: In each microstate, state the value for all control signals. Signals you don’t explicitly specify will be assumed to be taking the value 0.
Question 4: Halt Instruction (12 points) (7 minutes)
Assume the following datapath of LC-2200 and part of microcode. Take a look at the “NextState” of the halt instruction.


Q4.1 (6 Points)
Would this microcode achieve the intended semantics of halt? Describe in detail.
(Hint: the instruction hex for halt is always 0x70000000.)
Q4.2 (6 Points)
Would the microcode achieve the intended semantics of halt if the halt micro-state’s “NextState” value was 5 (i.e., br3) instead of 4 (i.e., br2)? Describe why or why not.
Question 5: Interrupts 1 (6 points) (3 minutes)
Consider an architecture that has 8 priority levels. The interrupt handler for every device enables interrupts for higher priority levels before executing the device-specific code.
Two devices -- timer and keyboard are the same lowest priority level. The timer device is electrically closer to the processor. The INTA line is chained through the two devices.
Q5.1 (3 Points)
Both devices simultaneously assert the interrupt line. Whose interrupt will be serviced first?
Q5.2 (3 Points)
When will the second device get serviced?
Question 6: Interrupts 2 (6 points) (4 minutes)
In LC-2200, $k0 contains the address to which the processor has to return from an interrupt handler. Before returning from the handler, the interrupts have to be enabled. Thus we can return from the interrupt by executing the following two instructions:
● Enable interrupt
● Jump via $k0
What is the problem with this idea?
Question 7: Performance Metrics 1 (6 points) (3 minutes)
Consider the following program that contains 1000 instructions:

NAND instruction occurs exactly once in the program as shown. Instructions I110–I144 constitute a loop that gets executed 250 times. All other instructions execute exactly once
Q7.1 (2 Points)
What is the static frequency of NAND instruction?
Q7.2 (4 Points)
What is the dynamic frequency of NAND instruction?
Note: Show your work in detail for credit
Question 8: Performance Metrics 2 (6 points) (5 minutes)
An architecture has three types of instructions that have the following CPI:
Type CPI
A 4
B 2
C 6
An architect determines that she can reduce the CPI for C to 4, with no change to the CPIs of the other two instruction types, but with an increase in the clock cycle time of the processor. What maximum permissible increase in clock cycle time will make this architectural change worthwhile? Assume that all the workloads executing on this processor use 40% of A, 30% of B, and 30% of C types of instructions.
Note: Show your work in detail for credit
Question 9: Performance Metrics 3 (10 points) (7 minutes)
A program spends 25% of its runtime in multiplications. LC-2200 simulates the multiplication instructions through a sequence of additions. A student in CS 2200 decides to add a MULT instruction to LC-2200, which does not affect the execution time of any other instructions in LC-2200. How much faster should MULT instruction be compared to the simulated code sequence for the program's overall speedup of 1.25?
Note: Show your work in detail for credit
Question 10: Hidden (10 points) (7 minutes)
Question 11: Hidden (10 points) (5 minutes)
Appendix A
LC2200 ISA

Appendix B
Performance Formulas