\documentstyle[11pt,times,prob]{cmu-art}

\setlength{\parindent}{0em}
\setlength{\parskip}{1ex}

\newcommand{\hfile}[1]{{\it HOMEDIR}{\tt /#1}}
\newcommand{\afile}[1]{{\it ASSTDIR}{\tt /#1}}

\begin{document}

\begin{center}
{\Large CS/ECE 347, Spring 1998}\\[1ex]
{\Large Homework 3: Alpha Assembly Language}\\[1ex]
{\large Assigned: Thursday, February~19\\Due: Thursday, February~26, 3:00pm}
\end{center}

\section*{Introduction and Logistics}

The purpose of this assignment is to get hands-on experience with
machine-level programming.  Our interest is in being able to
understand, measure, and optimize the machine code generated by a
compiler.  This is a far more useful skill than being able to churn
out pages of assembly code by hand.

{\bf WARNING:} There are a lot of logistical skills you'll need to
master for this assignment.  You will want to refer to the following
instructions frequently.

The files you will need for this assignment are in the directory
\begin{verbatim}
/afs/cs.cmu.edu/academic/class/15347-s98/public/asst/h3
\end{verbatim}

Parts of this assignment involve compiling, disassembling, and running code on
one of our Alpha-based machines.  For information on how to access these
machines, please refer to the link labeled ``Information about our Alpha
systems'' on the class WWW page.

The {\tt Makefile} contains rules for generating the object code ({\tt .o})
files that you need for this assignment.  You can safely ignore the warning
messages printed for the files given to you.

You can examine object code by disassembling it with the program {\tt
 dis}.  For example, to disassemble the file {\tt code.o} and put the
 result in the file {\tt code.dis}, you give the command:
\begin{verbatim}
dis -h code.o > code.dis
\end{verbatim}
For the remainder of this discussion, when we ask you questions about
 object code, you should answer these by examining the disassembled
 version.

When asked to generate an ``annotated'' version of the disassembled
code, you should follow the conventions used in lecture:
\begin{itemize}
\item
Put comments at the top of a code segment describing register usage and initial conditions.
\item
Put comments along the right hand side describing what each
instruction does.
\end{itemize}
\begin{description}
\item[NOTE:] Comments of the form:
\begin{verbatim}
      # I won't tell you anything about the registers.
      s8addq  r1, r2, r2   # r2 = 8*r1 + r2
      ldq     r3, 0(r2)    # r3 = Mem[r2]
\end{verbatim}
are useless and will receive little (if any) credit.  Instead, we
would like to see comments like the following:
\begin{verbatim}
      # Throughout the loop: r1 holds i, r7 holds n
      # At the beginning of the loop: r2 = &v[0]
      s8addq  r1, r2, r2   # r2 = 8*i + &v[0]
      ldq     r3, 0(r2)    # r3 = v[i]
\end{verbatim}
In other words, your comments should convey semantic information 
from the source code, and not simply reiterate what would be obvious
to anyone who can read Alpha assembly code.
\end{description}

When you report the performance of a routine, express your answer in units of
clock cycles.  You will need to use the {\tt ftime} routine you wrote for
assignment H1, and you can use the program {\tt freq} to determine the clock
rate of your processor.  (FYI, the clock rate of our Alphas is 433 MHz.)  You
will need to write your own code to run {\tt ftime} on the given test routines.

\vspace{0.1in}
\hrule

\section*{Hand In}

You should turn in a printed report.  Here are some guidelines:
\begin{itemize}
\item Generate a single, typeset document, not a hodgepodge of code
listings and handwritten scrawl.
\item Start the answer to each problem on a new page.
\item Clearly indicate the members of your group.  (One report/group).
\item
Don't include massive code dumps.  Just provide the segments of code
relevant to the particular discussion.
\item Much of the data requested would best be presented in tables.
\end{itemize}

\vspace{0.1in}
\hrule

\section*{Examining and Measuring Code}

Consider the following C procedure for swapping two consecutive elements
within an array:
\begin{verbatim}
  void swapC(int v[], int k)
  {
    int temp;
    temp = v[k];
    v[k] = v[k+1];
    v[k+1] = temp;  
  }
\end{verbatim}
This code is included in the file {\tt code2.c} (along with several
other routines that we will examine later in this assignment).

The file {\tt asm.s} contains a (somewhat naive) hand-coded implementation of
the swap routine written in Alpha assembly language.  This latter version of
the swap routine is called ``{\tt swapA}''.

\begin{problem}{Understanding Swap Routines}
Use the {\tt Makefile} to compile {\tt code2.c} and {\tt asm.s} into the object
files {\tt code2.o} and {\tt asm.o}, respectively.  Then disassemble these object
files using the {\tt dis} command.

\begin{subproblems}
\item
Generate an annotated version of the disassembled code for {\tt swapC}.
\item
Compare the object code generated for {\tt swapC} to that generated
for {\tt swapA}.  What allowable optimizations did the C compiler take
advantage of that were not exploited by the author of {\tt swapA}?
\item
How many instructions are required by the object code routines {\tt swapA} and
{\tt swapC}?  Call these values $A$ and $C$, respectively.
\end{subproblems}
\end{problem}

\begin{problem}{Measuring Swap Routines}
The file {\tt tests.c} contains three test routines: {\tt swapAtest},
{\tt swapCtest}, and {\tt swapDtest}.  In conjunction with the {\tt
ftime} routine, you can use these tests to measure the performance of
routines {\tt swapA}, {\tt swapC}, and {\tt swapDummy}, respectively.
Procedure {\tt swapDummy} is a ``dummy'' used to subtracting out the
overhead caused by the rest of the test code.
\begin{subproblems}
\item
Examine the disassembled code for {\tt swapDummy}.  How many instructions does it
require?  Call this value $D$.
\item
Measure and report the times taken by the three test routines,
expressed as the average number of
clock cycles per call to the respective swap or dummy routine.  Call
the three results $a$, $c$, and $d$, respectively.  What are the
values of $a-d$ and $c-d$, indicating the time difference (in cycles) between 
{\tt
swapA} and {\tt swapC}?
\item
If we assume each that Alpha instruction requires one clock cycle to execute
(this is not quite true in reality, of course), then our measurements of $a-d$
and $c-d$ should match the instruction counts $A-D$ and $C-D$.  How do your
measurements compare to these estimates?  [Do not be alarmed if they are
somewhat off.]
\end{subproblems}
\end{problem}

\begin{problem}{Understanding Loop Code}

The functions {\tt bubbleUp1}, {\tt bubbleUp2}, and {\tt bubbleUp3} in
the file {\tt code2.c} each perform the same task.  They shift the
elements of an array down by one, moving the first element to the end.
Procedure {\tt bubbleUp1} does this by stepping through the array and
calling the procedure {\tt swapC}.  Procedure {\tt bubbleUp2} does the
same, but with a macro-expanded version of {\tt swapC}.  Procedure
{\tt bubbleUp3} more directly implements the specified behavior, and
contains low-level optimizations using pointer code.

Examine the disassembled version of {\tt code2.o} to see how the C compiler has
translated each of these routines into Alpha machine code.  Our main interest
is in the operation and performance of the inner loops.

\begin{subproblems}
\item
Identify the inner loops in the disassembled code for these three
routines.  Generate annotated versions of these loops.  
\item
Describe qualitatively the savings made by using the macro-expanded
version of swap compared to the procedure version.
\item
Describe qualitatively the further savings made by the direct
implementation ({\tt bubble3}), versus a swap-based version ({\tt
bubble2}).
\item
How many instructions are required by each of these loops?
\end{subproblems}

\vspace{0.3in}
\end{problem}

\begin{problem}{Measuring Loop Code} 
Use the routines {\tt b1test}, {\tt b2test}, and {\tt b3test} in the
file {\tt tests.c} to measure the performance of the three bubble
routines.  Express the performance in terms of the average number of
clock cycles per execution of the inner loop of the bubble routine.
How do these results compare to each other, and to the number of
instructions in each loop?  Express your result as a table with 6 entries.
\end{problem}

\section*{Long Jumps}

{\em (NOTE: this last section is for extra credit only.)}

In this section, you will enhance your understanding of Alpha
calling and returning conventions by examining the Unix \verb.setjmp.
library, which in effect cheats on the standard procedure calling
conventions.

\verb.setjmp. provides a mechanism for nonlocal procedure exits.
By using {\tt setjmp} and {\tt longjmp}, a procedure can exit to a
function a long way up the procedure chain, bypassing its calling
procedure.

This is typically used for error handling, in the following style:

\begin{verbatim}
jmp_buf env;

main()
{
   int jval;
   if ((jval = setjmp(env)) != 0) {
     /* Do error recovery and cleanup. */
     /* And possibly try to execute again. */
   } else {
     /* Do normal case. */
     ...
   }
}
\end{verbatim}

The first time \verb.setjmp(). is called, it sets up the buffer env with
enough information to reconstruct the state of the registers and the
stack. It returns 0 to the calling function.

The calling function then does other code, and deep within some
complicated hierarchy of other functions, it may find some error:

\begin{verbatim}
deep_within_some_complicated_hierarchy ()
{
  if (error_detected) {
     longjmp(env, ERROR_CONSTANT);
  }
  ...  
}
\end{verbatim}

\verb.longjmp(). restores the state that was saved in \verb.setjmp(). and
resets the stack pointer to the position it was in when \verb.setjmp().
was called.

The file {\tt ljdemo.c} contains a somewhat contrived example of the
use of \verb.setjmp(). and \verb.longjmp()..  Study this code to
better understand the behavior of these constructs.  Try compiling and
running it (it should work on any Unix machine).


\begin{problem}{{\em (For Extra Credit)} Understanding the Implementation of Long Jumps}
The file {\tt longjmp.dis} contains a disassembly of the code for
\verb.___setjmp(). and \verb._longjmp()., which are simplified versions of
\verb.setjmp(). and \verb.longjmp()..  (Note that \verb.__longjump_resume().,
which is included in this file, is called by \verb._longjmp().)  This code was
extracted from the Unix library {\tt /usr/lib/libc.a} on one of our Alpha
machines.  Your job is to create annotated versions of these two procedures.
Show clearly what state is being saved and restored, and how longjmp subverts
the Alpha calling routines to appear to `return' to a place other than that
from which it was called.

It may help you understand the code to write down what data is stored
in which places in the \verb.jmp_buf.. If you write this information down,
turn that in too.
\end{problem}

\subsection*{Things You Need To Know}

This section covers information that you are not expected to know from
previous lectures.

The {\tt ldt} and {\tt stt} instructions load and store 64-bit numbers
into/from the {\em floating-point} register file.  Their behavior is analogous
to {\tt ldq} and {\tt stq} for integer data.

The value {\tt 0xacedbade} is used as a ``magic token'' to identify
a buffer that has (probably) been set by \verb.setjmp(). (A moment's
thought should convince you that doing a \verb.longjmp(). to a buffer
that has not been set up by \verb.setjmp(). is likely to result in
errors that are very difficult to track down.) This value is generated
by a combination of three instructions:
\begin{verbatim}
    ldah r1, 22135(r31)
    lda  r1, -8849(r1)
    addq r1, r1, r1
\end{verbatim}
The {\tt ldah} instruction, which stands for Load Address High, multiplies a
signed 16-bit constant by 65536, and then adds this value into the destination
register.  The {\tt lda} instruction, which stands for Load Address, generates
the effective address address in the destination register (in this case, it
subtracts 8849 from {\tt r1}).

\end{document}
