Instructions:
You are encouraged to work on the problem set in groups and turn in one problem set for the entire group. Remember to put all your names on the solution sheet. Also remember to put the name of the TA in whose discussion section you would like the problem set returned to you.

1. For both Part A and B, assume that the system call initiated by the HALT instruction takes 20 cycles to execute. Note that this does not include the number of cycles it takes to execute the HALT instruction itself.

   A. What does the following LC-3b program do? How many cycles does each instruction take to execute on the LC-3b microarchitecture described in Appendix C? How many cycles does the entire program take to execute? (Assume that a memory access takes 5 cycles)

   	.ORIG x4000
   	AND   R1, R1, #0
   	ADD   R1, R1, #5
   	LSHF  R1, R1, #12
   	LDW   R2, R1, #0
   	RSHFL R3, R2, #8
   	LSHF  R4, R2, #8
   	ADD   R2, R3, R4
   	STW   R2, R1, #1
   	HALT
   	.END
   	    

   B. What does the following LC-3b program do? How many cycles does it take to execute? (Assume that a memory access takes 5 cycles)

   	.ORIG x4000
   	AND   R1, R1, #0
   	ADD   R1, R1, #5
   	LSHF  R1, R1, #12
   	LDB   R2, R1, #0
   	STB   R2, R1, #3
   	LDB   R2, R1, #1
   	STB   R2, R1, #2
   	HALT
   	.END
   	    

2. In the LC-3b datapath, PCMUX has three inputs. For each of those inputs, list all the instructions which make use of that input and show the corresponding state in the LC-3b state diagram.

 
3. States 18, 33, and 35 of the LC-3b state machine are:

   	
   	State 18: MAR <- PC, PC <- PC + 2
           State 33: MDR <- M
           State 35: IR <- MDR
   

   Which of the following different organizations would still work correctly, why or why not? (Assume that a memory access takes five cycles).
   1. 
      

      	State 18: PC <- PC + 2
      	State 33: MAR <- PC, MDR <-M
      	State 35: IR <- MDR
      

   2. 
      

      	State 18: MAR <- PC
      	State 33: PC <- PC + 2, MDR <-M
      	State 35: IR <- MDR
      
      

   3. 
      

      	State 18: MAR <- PC
      	State 33: MDR <- M
      	State 35: IR <- MDR, PC <- PC + 2
      

   
   
   
4.     1.In which state(s) in the LC-3b state diagram should the LD.BEN signal be asserted? Is there a way for the LC-3b to work correctly without the LD.BEN signal? Explain.
       2.Suppose we want to get rid of the BEN register altogether. Can this be done? If so, explain how. If not, why not? Is it a good idea? Explain.
       3.Suppose we took this further and got rid of state 0. The figure below shows a modified microsequencer. What is the 4-bit signal denoted as A in the figure? What is the 1-bit signal denoted as B?
   
   
   
    
    
5.   Little Computer Inc. has decided to modify the LC-3b ISA to include the PUSH and POP instructions. The description of these operations are as follows:

Assembler format for PUSH:
PUSH SR

Encoding:


Operation:
R6 = R6 - 2;
MEM[R6] = SR;

Description:
SR is pushed onto the stack.

Example:
PUSH R1




Assembler format for POP:
POP DR

Encoding:


Operation:
DR = MEM[R6];
setcc(DR);
R6 = R6 + 2;

Description:
Top word is popped off the stack and loaded into DR. Condition codes are set based on the value loaded into DR.

Example:
POP R1



Your job:
A. Append the current state machine for supporting PUSH and POP instructions.
B. Will the current datapath support the above state machine? If not, then draw the new datapath to implement the above state machine. Show the new structures you added to support PUSH and POP operations.
C. Are there any additional control signals needed for the new states? If so, what are they? Give the values of these new control signals in each new state you added and show them clearly in your datapath figure for Part B.
D. How many cycles will each of the following set of instructions take to execute? 

      1. PUSH R4

      2. ADD R6, R6, # -2
           STW R4, R6, #0

      3. POP R0

      4. LDW R0, R6, #0
          ADD R6, R6, #2
 
 

6.    Design the "WE Logic" block of the LC-3b datapath as shown on Figure C.3 in Appendix C.  The inputs to the block are MAR[0], R.W, and DATA.SIZE. The outputs of the block are WE0 and WE1. Show the truth table for this logic block and give a gate-level implementation.

 
 
7.   The Address Control Logic in the LC-3b datapath of Figure C.3 in Appendix C allows the LC-3b to support memory-mapped I/O. There are three inputs to this logic:
   • 16-bit address in MAR. This signal can take the following values: xFE00, xFE02, xFE04, xFE06, and OTHER (any other address between x0000 and xFDFF).
   • 1-bit control signal R.W. The access is a read access if this signal is R, write access if it is W.
   • 1-bit control signal MIO.EN. If this signal is 1, a memory or I/O access should be performed in this cycle.
   
     The logic has five outputs:
   • 1-bit MEM.EN signal. Memory is enabled if this signal is 1.
   • 2-bit select signal for INMUX. This signal can take the following values: KBDR, KBSR, DSR, MEMORY.
   • 1-bit LD.KBSR signal. KBSR will be load-enabled at the end of the current cycle if this signal is 1.
   • 1-bit LD.DDR signal. DDR will be load-enabled at the end of the current cycle if this signal is 1.
   • 1-bit LD.DSR signal. DSR will be load-enabled at the end of the current cycle if this signal is 1.
   
     Your task is to draw the truth table for this Address Control Logic. Mark don't care values with X in your truth table. Use the conventions described above to denote the values of inputs and outputs. Please read Section C.6 in Appendix C on Memory-mapped I/O before answering this question. Also, refer to Appendix A to find out the addresses of device registers.

 
8. A processor supports byte-addressable memory with a 26-bit address space. The processor is connected to memory via a 64-bit data bus. Design an eight-way interleaved memory that supports the full address space of the processor. Use only 512Kbit (2^19 * 1 bit) memory chips. Draw a diagram of your memory system, with chip enables, write enables, data bus, and address bus. On your diagram, label memory locations 0 through 31. How big is this memory? Give a breakdown of each field in a memory address. (Do not worry about the logic for unaligned accesses.)



9. Suppose the processor in the previous problem is updated to support a 28-bit address space with byte-addressable memory. Assume that user programs can make use of the whole 28-bit virtual address space. Using the physical memory developed above, we would like to support virtual memory. The virtual memory will support the following features:

        8KB page size
        3 levels of access (similar to VAX architecture discussed in class):
                none (-)
                read (R)
                write (W)
        4 privilege levels (again similar to VAX architecture discussed in class):
                user (U)
                supervisor (S)
                executive (E)
                kernel (K)
        page replacement using a reference bit for each page

How many pages are there in virtual memory? How many frames are there in physical memory? What is the minimum number of bits required to encode all the valid combinations of privilege levels and access levels? Show which access level/privilege level combinations are valid and which are invalid.

Show a PTE for this memory, and specify the number of bits required for each field in the PTE. Finally, describe how a 28-bit virtual address is translated into a 26-bit physical address. 
 
 
10. The virtual address of variable x is x3456789A. Using the VAX's virtual memory architecture, find the physical address of x.

    You will need to know the contents of P0BR: x8AC40000 and SBR: x000C8000.

    You will also need to know the contents of the following physical memory locations:

    x1EBA6EF0:    x80000A72
    x0022D958:    x800F5D37

    Some intermediate questions to help you:
    • What virtual page of P0 Space is x on?
    • What is VA of the PTE of the page containing x?
    • What virtual page of System Space is this PTE on?
    • What is the PA of the PTE of this page of System Space?
    • What is the PA of the PTE of the page containing x?

 
11.   The figure below illustrates the logic and memory to support 512 MB (byte addressable) of physical memory, supporting unaligned accesses.  The ISA contains LDByte, LDHalfWord, LDWord, STByte , STHalfWord and STWord instructions, where a Word is 32 bits. 

 




    Construct the truth table to implement the LOGIC block, having inputs SIZE, R/W, 1st or 2nd access, PHYS_ADDR[1:0] and the outputs shown in the above figure. Assume that the value of SIZE can be Byte (00), HalfWord (01), and Word (10). Clearly explain what function each output serves.