\iffalse INSTRUCTIONS: (if this is not ps1, use the right file name) Clip out the ********* INSERT HERE ********* bits below and insert appropriate TeX code. Once you are done with your file, run ``latex template.tex'' from the Athena shell. If your TeX code is clean, the latex will exit back to a prompt. Once this is done, run ``dvips template.dvi -o template.ps'' which should print your file to the nearest printer. There will be residual files called ps1.log, ps1.aux, and ps1.dvi. All these can be deleted, but do not delete ps1.tex. \fi \documentclass[11pt]{article} \usepackage{amsfonts} \usepackage{latexsym} \setlength{\oddsidemargin}{.25in} \setlength{\evensidemargin}{.25in} \setlength{\textwidth}{6in} \setlength{\topmargin}{-0.4in} \setlength{\textheight}{8.5in} \newcommand{\handout}[5]{ \renewcommand{\thepage}{#1-\arabic{page}} \noindent \begin{center} \framebox{ \vbox{ \hbox to 5.78in { {\bf 6.823 Computer Architecture} \hfill #2 } \vspace{4mm} \hbox to 5.78in { {\Large \hfill #5 \hfill} } \vspace{2mm} \hbox to 5.78in { {\it #3 \hfill #4} } } } \end{center} \vspace*{4mm} } \newcommand{\ho}[5]{\handout{#1}{#2}{Instructor: #3}{Teaching Assistant: #4}{Handout #1: #5}} \newcommand{\al}{\alpha} \newcommand{\Z}{\mathbb Z} \begin{document} \handout{P1}{DUE: 2/27/2002, EXTENSION: 3/4/2002}{Problem Set 1} {Instructors: Krste Asanovic, Srinivas Devadas} {Timothy Danford, Killian Pohl, Bryan Russell} % Problem 2 \section*{Problem 2} \bigskip {\bf (a)} In the DLX pipeline, we need to modify the Execution (EX) and Memory access (MEM) stages. In the EX stage, we need to carry the information from the ``A'' register to the MEM stage for the PUSH instruction. Hence, there needs to be an extra datapath going from the ``A'' register (between the pipe stages ID and EX) to the set of registers between the EX and MEM pipe stages. In the MEM pipe stage, we need to add two multiplexors (MUX) and an ALU. The ALU is added so that we can update the stack pointer register $R29$. The output of this ALU is of course put into register $R29$. The two MUXes control the data and address input to the Data Memory. For the data input, we must choose between the output from the ALU in the previous pipe stage and the data in the register from the PUSH instruction. For the address input, we must choose between register ``B'' from the previous pipe stage, register $R29$ (for the POP instruction), and the output from the added ALU in this pipe stage (for the PUSH instruction). We would not want to add anything beyond this because we have the needed circuitry to do everything else (except handle hazards). We note here that for the POP instruction, $R_{DEST}$ is forwarded through the pipeline and eventually gets back to the Registers for the Write Back stage. We would not want to allow one to call the pop instruction with the $R_{DEST}$ register. If we allowed this, one could pop the top element and replace the stack pointer with the ``popped'' contents. In short, we would overwrite the stack pointer and lose track of the stack in memory. \bigskip\noindent {\bf (b)} Making the push and pop instructions 11 bits long might not be a good idea because we would have to completely change the design of the memory storing/fetching hardware. In the current implementation of the memory storing/fetching, we are allowed to store/fetch 1 word (32 bits) at a time. With an 11 bit instruction in the current memory implementation, we would have major alignment issues when fetching and storing instructions from/in memory. A better length would be 16 bits since it would allow the instruction to be better-aligned in memory with 2 push/pop instructions per word. Even with this, we have to add additional hardware to implement these fetches/stores which may decrease the clock speed. Also, if we allow the instruction to be 16 bits we still have to be careful with the branch delay and jump instructions. When calculating the address to branch/jump to, we have to take into account these shorter instructions. \bigskip\noindent {\bf (c)} We have 22 instructions with each instruction requiring 4 bytes of space in memory. Hence, we would need to fetch 88 bytes of instructions. \bigskip\noindent {\bf (d)} Here's the code using push and pop instructions for any stack loads and stores: \begin{verbatim} bar: ADDI sp,sp,#12 # Set the stack pointer to start position PUSH R6 # Push f ADD R6,sp,R0 # Put address of f into R6 PUSH R5 # Push e ADD R5,sp,R0 # Put address of e into R5 PUSH R4 # Push d ADD R4,sp,R0 # Put address of d into R4 PUSH R31 # Push link register PUSH R16 # Save callee-saved register R16 SUBI sp,sp,#16 # Adjust stack pointer for subroutine ADD R16,R7,R0 # Put g into R16 JAL foo # Jump and link to foo ADDI sp,sp,#16 # Set stack pointer to last item in stack ADD R6,R16,R0 # Put g into R6 POP R16 # Restore callee-saved register R16 POP R31 # Restore link register POP R3 # Put d into R3 POP R4 # Put e into R4 POP R5 # Put f into R4 ADD R3,R3,R4 # (d+e+f+g+h) ADD R3,R3,R5 ADD R3,R3,R6 ADD R2,R2,R3 SUBI sp,sp,#12 # Restore stack J R31 # Return to caller \end{verbatim} For this implementation, we have 15 instructions occupying 4 bytes in memory and 10 instructions (push/pop) occupying 2 bytes in memory. Hence, we need to fetch 80 bytes from memory, which is a slight improvement from the original implementation. From this, we see that using push and pop does not give us much savings in memory. \bigskip\noindent {\bf (e)} The problem here is encoding the instructions so that we do not have alignment issues as in problem {\bf 2.B}. To encode, let us allow the first 6 bits of the instruction for the op-code and the remaining bits to represent the registers. We can represent the registers in one of two ways. The first way is to encode each register using the standard 5 bit representation as in the ADD instruction. The problem with this is that we can only allow 4 registers to be specified in the register list for the 32 bit representation (6 bits for the op-code, 5 bits for the $R_{BASE}$, 20 bits for the register list, and 1 bit left over). We can allow more registers to be represented with this representation, but we would have to extend the length of the instruction (of course taking into account the issues raised in problem {\bf 2.B}). So, in short we would either have to allow the instruction to vary in size or restrict the number of registers that can be listed in the register list. The second way to encode the registers is the allow the remaining bits to represent each of the registers. To encode the register list, we just need to flip the corresponding bits to 1 (keeping those registers not listed as 0). The problem with this representation is that we only have 26 bits to work with in the 32 bit encoding scheme, which is less than the total number of registers that we have. Again, we could extend the length of the instruction so that we can include all of the registers. Else, we could just choose the registers that can be listed in the instruction. \bigskip\noindent {\bf (f)} \begin{verbatim} bar: ADDI sp,sp,#12 # Set the sp to start position STMFD sp,R4,R5,R6,R16,R31 # Store d,e,f,R16, and link register ADDI R6,sp,#8 # Put address of f into R6 ADDI R5,sp,#12 # Put address of e into R6 ADDI R4,sp,#16 # Put address of d into R6 SUBI sp,sp,#16 # Adjust sp for subroutine ADD R16,R7,R0 # Put g into R16 JAL foo # Jump and link to foo ADD R6,R16,R0 # Put g into R6 ADDI sp,sp,#16 # Set sp to last item in stack LDMFD R3,R4,R5,R16,R31,sp # Restore d,e,f,R16,link reg ADD R3,R3,R4 # (d+e+f+g+h) ADD R3,R3,R5 ADD R3,R3,R6 ADD R2,R2,R3 SUBI sp,sp,#12 # Restore stack J R31 # Return to caller \end{verbatim} In this implementation, we have 15 instructions requiring 4 bytes and 2 instructions requiring either 4 bytes (32 bits) or 8 bytes (64 bits). Hence, for the 32 bit encoding, we need to fetch 68 bytes and for the 64 bit encoding, we need to fetch 76 bytes. Compared to the original implementation, this new implementation reduces the size of the instructions by 14\% or 23\% respectively for the 64 bit and 32 bit encodings. Compared to the push/pop implementation, we only get 5\% or 15\% savings respectively for the 64 bit and 32 bit encodings. Hence we get quite a bit of savings compared to the original implementation and not so much for the push/pop implementation. This says that with the load and store multiple instructions, we can get varied savings depending on the instruction set that we are comparing it to. \end{document}