\documentclass[11pt, twoside]{article}
\usepackage{alltt}
\input{homework}

\begin{document}

\solutions{1}

\begin{problems}
\bigskip

\problem{Instruction Set Architecture Style}
\medskip

\begin{problemparts}
\problempart{Computing the lengths of the various instructions}

\begin{alltt}
Memory to Memory: \\
MOVE A,B ; 5 bytes \\
ADD A, B, C ; 7 bytes \\
SUB A, B, C ; 7 bytes \\ 

Stack: \\
PUSH A ; 3 bytes \\
POP A ; 3 bytes \\
ADD ; 1 byte \\
SUB ; 1 byte \\

Load-Store \\
LOAD R1, A ; 4 bytes (really 3.5) \\
STORE A, R1 ; 4 bytes (really 3.5) \\
ADD R1, R2, R3 ; 3 bytes  (really 2.5) \\
SUB R1, R2, R3 ; 3 bytes (really 2.5) \\

\end{alltt}

\problempart{Memory Efficient Code for Basic Arithmetic Routine}
For this problem, we assume that the A is initially stored in address 
ADDRA, B is initially stored in address ADDRB, C is initially stored in
address ADDRC, and D is initially stored in ADDRD. 

\begin{alltt}

Memory to Memory: \\
SUB ADDRA ADDRB ADDRC  ;  A=B-C
ADD ADDRC ADDRA ADDRB  ;  C=A+B
ADD ADDRD ADDRA ADDRC  ;  D=A+C

Stack: \\
PUSH ADDRC 
PUSH ADDRB
SUB             ; B-C is on top of the stack
POP ADDRA       ; A=B-C 
PUSH ADDRB
PUSH ADDRA
ADD             ; A+B is on top of the stack
POP C           ; C=A+B
PUSH A
PUSH C
ADD             ; A+C is on top of the stack
POP D           ; D=A+C

Load-Store: \\
LOAD R1, ADDRB  ; R1 contains B
LOAD R2, ADDRC  ; R2 contains C
SUB R3, R1, R2  ; R3 contains B - C
STORE ADDRA R3  ; A = B - C
ADD R2, R3, R1  ; R2 = A + B
STORE ADDRC, R2 ; C = A + B 
ADD R1, R3, R2  ; R1 = A + C 
STORE ADDRD, R1 ; D = A + C

\end{alltt} 

\problempart{Calculating Instruction Bytes and total memory-data bytes fetched}

The instruction bytes fetched and the memory bytes transferred are specified
next to each line of code.  The first number consists of the memory bytes,
the second is the instruction bytes.

\begin{alltt}

Memory to Memory: \\
(7, 12) SUB ADDRA ADDRB ADDRC  ;  A=B-C
(7, 12) ADD ADDRC ADDRA ADDRB  ;  C=A+B
(7, 12) ADD ADDRD ADDRA ADDRC  ;  D=A+C
------
total instruction bytes fetched: 21 bytes
total memory bytes transferred:  36 bytes

Stack: \\
(3, 4) PUSH ADDRC 
(3, 4) PUSH ADDRB
(1, 0) SUB             ; B-C is on top of the stack
(3, 4) POP ADDRA       ; A=B-C 
(3, 4) PUSH ADDRB
(3, 4) PUSH ADDRA
(1, 0) ADD             ; A+B is on top of the stack
(3, 4) POP C           ; C=A+B
(3, 4) PUSH A
(3, 4) PUSH C
(1, 0) ADD             ; A+C is on top of the stack
(3, 4) POP D           ; D=A+C
------
total instruction bytes fetched: 30 bytes
total memory bytes transferred:  36 bytes
 
Load-Store: \\
(4, 4) LOAD R1, ADDRB  ; R1 contains B
(4, 4) LOAD R2, ADDRC  ; R2 contains C
(3. 0) SUB R3, R1, R2  ; R3 contains B - C
(4, 4) STORE ADDRA R3  ; A = B - C
(3, 0) ADD R2, R3, R1  ; R2 = A + B
(4, 4) STORE ADDRC, R2 ; C = A + B 
(3, 0) ADD R1, R3, R2  ; R1 = A + C 
(4, 4) STORE ADDRD, R1 ; D = A + C
------
total instruction bytes fetched: 29 bytes
total memory bytes transferred:  20 bytes

\end{alltt} 

The most code efficient architecture is the memory-to-memory architecture.
The architecture with the greatest demand on memory bandwith is the stack
architecture (since even though the instruction lengths are short, you need
more of them).
 
\end{problemparts}

%%%%%%%%%  Problem 2

\problem{Making Ends Meet on the EDSACjr}
\medskip

For this problem set, we also used the following macro:

\begin{alltt}
{\bf .macro:}   LOAD (n)
                CLEAR
                ADD n
{\bf .end macro}
\end{alltt}

We also have a global variable in memory whose value is  \\
   one:    0000000000000001 \\
Since we can't actually manipulate constants in this language (sigh).

\begin{problemparts}
\problempart{Writing Macros for Indirection}
The ADDind(n) macro is written using self-modifying code. This
inherently means that this macros is {\bf NOT} re-entrant, which makes
it not as useful as it could be. A temporary variable to hold the
value of the accumulator uses the first line of the macro (replacing a
NOP with the value). This is done to avoid any need for branching
calls (which is usually optimal on most modern CPUs which use
lookahead) and it turns out that assuming one cycle per instruction,
is faster than alternative options and uses as much space. Also, since
we are guaranteed by the problem to have addresses that don't use the
MSB of the number (there are at most 1024 addresses), then we don't
have to worry about the ADD causing some sort of negative number to be
added:

\begin{alltt}
{\bf .macro:}   ADDind (n)
        temp:   NOP
                STORE temp
                LOAD n		\hfill ; first six bits are zero
                STORE instr
                LOAD temp	\hfill ; Accumulator has original value again
        instr:  NOP		\hfill ; Add the indexed address to Accum
{\bf .end macro}
\end{alltt}

The STOREind(n) macro is written by adding the address of the variable
to be stored to a pre-written instruction which contains a zero
address. Again the assumption is that the address is at most a 10 bit
number. This new 'instruction' is written out at the end and is
executed as the last line of the macro:

\begin{alltt}
{\bf .macro:}   STOREind (n)
        temp:   NOP
                STORE temp
                LOAD n
                ADD instr
                STORE instr
                LOAD temp
        instr:  00010 00000000000	\hfill ; STORE 0
{\bf .end macro}
\end{alltt}

The BGEind and BLTind macros are exactly the same as the STOREind
macro, since none of the opcodes have a '1' as the MSB:

\begin{alltt}
{\bf .macro:}   BGEind (n)
        temp:   NOP
                STORE temp
                LOAD n
                ADD instr
                STORE instr
                LOAD temp
        instr:  00111 00000000000	\hfill ; BGE 0
{\bf .end macro}
\end{alltt}


\begin{alltt}
{\bf .macro:}   BLTind (n)
        temp:   NOP
                STORE temp
                LOAD n
                ADD instr
                STORE instr
                LOAD temp
        instr:  01000 00000000000	\hfill ; BLT 0
{\bf .end macro}
\end{alltt}


\problempart{Subroutine Calling Conventions}
One way of calling functions is to place the arguments after the
subroutine call and pass the return address in the accumulator. There
is an issue of where the return values go, and we decided to place
them in memory AFTER the arguments, and before the return address.

In particular, for the special case of two arguments and one return
value, we would (after the branch to the subroutine) leave three
unused memory addresses. In those, we would place the first two
arguments and nothing in the third.  When we return from the
subroutine, the third should hold the returned valued.

It is therefore assumed that the subroutine knows in advance how many
arguments it expects, and the caller knows how many return values
there will be. Not much needs to be done around the calling point,
except saving the value in the accumulator and then restoring it
(since the accumulator was used to pass a return address).

An alternative to returning the result and passing arguments in as
described above is to have a set place in memory where arguments and
return values are stored (probably right after the last instruction of
the subroutine).  This has the advantage of making the program smaller
should the function be called many times.

The following is an implementation of the C code listed here:
\begin{alltt}
\bf{
int lpf(int n, int *array)\{
   int \(i\);
   int sum = 0;
   if (\(n > 0\)) \{
      for (\(i = 0\); \(i < n\); \(i++\)) \{
         array[\(i\)] = (array[\(i\)] + array[\(i+1\)] / 2 ;
         sum = sum + array[\(i\)] ;
      \}
   \}
   return sum;
\}
}
\end{alltt}

First of all, since C is pass-by-value, we need to actually copy the
values we are given over to some variable that is local to the
subroutine. The subroutine therefore looks something like:
\begin{alltt}
lpf:     STORE ret_addr \hfill ;save the return address from Accum
         SUB one
         STORE retval_addr
         SUB one
         STORE arg2 \hfill ;We now have address of argument
         SUB one
         STORE arg1 
         CLEAR
         ADDind arg1
         STORE arg1 \hfill ;We now have the value of the argument
         CLEAR
         ADDind arg2
         STORE arg2
 \  \hfill ;at this point, we are done with setup
         CLEAR
         STORE sum \hfill ; sum = 0
         LOAD arg1
         SUB one
         BLT return_pt
loop:    CLEAR
         STORE i
loop_c:  LOAD i
         SUB arg1
         BGE return_pt
         LOAD arg2
         ADD i
         STORE temp1
         ADD one
         STORE temp2
         CLEAR
         ADDind temp1
         ADDind temp2 \hfill ;Accum <- array[i] + array[i+1]
         SHIFTR 1
         STOREind temp1
         ADD sum
         STORE sum
         LOAD i
         ADD one
         STORE i
         BGE loop_c
return_pt:
         LOAD sum
         STORE retval_addr
         BGEind ret_addr

ret_addr:     NOP
arg1:         NOP
arg2:         NOP
retval_addr:  NOP
i:            NOP
sum:          NOP
temp1:        NOP
temp2:        NOP
\end{alltt}

Of course, this technique can be generalized to any number of
variables and return values. If they are known in advance, then simply
leave enough space for all of them before the return pt and after the
calling point.  If they are not (a la varargs), then the caller will
need to also include a number indicating how many arguments he is
passing in. If the subroutine can have a variable number of return
values (not possible in C) then we need the return values to be stored
elsewhere (probably after the subroutine) and the function to return a
pointer to them and a number indicating how many there are.

\problempart{Subroutine Calls}
Using the convention suggested in 2B, subroutine calls {\it can} be
made from within subroutine calls, but only by being very
careful. This code is not re-entrant, and so no subroutine may call
itself, or may lead to a chain of subroutine calls that will result in
itself being called again. If all subroutine calls were on a directed
graph, with nodes representing functions and edges representing a
subroutine call from within that function, a cycle must not be allowed
to form. Recursion is just a no-no. Tail-end recursion CAN be
supported easily though by making the subroutine pass the return
address it was given in the accumulator instead of by having it pass
some address within its code.

\problempart{Recursive Subroutines} To support recursion, we chose to use a {\bf stack}
mechanism. To create the stack, we choose some place in memory where
we believe we will not overwrite program code when the stack grows AND
where we hope to not run out of memory. One viable place is right
after all the code and global variables.  We need to create one global
variable (address) called {\tt stack}, which initially holds the
address of the stack. It will change as the stack grows and
diminishes. We also create another global variable {\tt
temp\_stack\_accum}, to hold temporary data. Since this is only being
used for subroutines, we have no reason to worry about underflowing
the stack (unless something much more major has gone wrong), so we do
not bother wasting cycles and memory with a stack length indicator.
We then create two macros:
\begin{alltt}
{\bf .macro:}   PUSH \hfill ;Push the value in the accumulator on the stack
                STORE temp_stack_accum
                STOREind stack
                LOAD stack
                ADD one
                STORE stack;
                LOAD temp_stack_accum
{\bf .end macro}

{\bf .macro:}   POP \hfill ;Pop the value on the stack to the accumulator
                LOAD stack
                SUB one
                STORE stack
                CLEAR
                ADDind stack
{\bf .end macro}
\end{alltt}

Then, whenever a program wishes to call a subroutine, it merely uses
the stack to pass in arguments, and reads the results off the stack
(which the subroutine will have written there). The return address is
now also passed in on the stack.

 So, for a 2 arg / 1 return address, the following is done:
The program pushes the return address, and then the two arguments
onto the stack. It then branches to the subroutine, which pops
a variable when it needs it, and only uses local variables with the
understanding that anything it does with them MAY be modified
as soon as a subroutine is called (therefore, all variables are
presumed global if they are not on the stack). One normal way of
handling this is to, before calling any subroutine, push all your
local variables onto the stack, and then, after the return, pop them
off (this will be shown in the example code).

To generalize this to procedures with different number of arguments
and return values, in the case where these are known in advance, just
use it as above (push the correct number of arguments on, pop the
correct number of return values off).  If they are not (a la varargs),
then simply push one more element on the stack after pushing the
arguments/return values : the number you have pushed. (this way, the
function first pops the stack to find out how many arguments it should
pop off.

The following EDSACjr assembly code attempts to be as true to the C
code as it can. This means it forgoes a lot of optimizations that
could be made to improve performance (notably, reordering statements
that have no effect on the final result can yield a major reduction in
code length. Similarly, only storing the variables we know we will use
after the recursion would save space. This is the job of the optimizer
and the pset did no indicate we should optimize the code, and it
should make grading easier for the TA's. We did put comments as to how
one could optimize it, however. Again, we do pass-by-value since this
is how C works.

\begin{alltt}
\bf{
int lpf(int n, int *array)\{
   int \(i\);
   int sum = 0;
   if (\(n > 0\)) \{
      for (\(i = 0\); \(i < n\); \(i++\)) \{
         array[\(i\)] = (array[\(i\)] + array[\(i+1\)] / 2 ;
         sum = sum + array[\(i\)] ;
      \}
   \}
   return sum;
\}
}
\end{alltt}


SINCE we can't put constants other than 0 in the accumulator, there is
no way to actually set a variable to an address other than starting
the program with that address somewhere in memory (we encountered this
problem with the {\tt stack} variable already). So, we create a global
variable {\tt lpf\_ret\_pt\_var} which holds the address of {\tt
lpf\_ret\_pt}.
\begin{alltt}
lpf:     
         POP
         STORE arg2
         POP
         STORE arg1
 \  \hfill ;at this point, we are done with setup
         CLEAR
         STORE sum
         LOAD arg1 \hfill ; If sum was set earlier, we wouldn't need to reload arg1
         SUB one
         BLT return_pt
         LOAD arg1
         SUB one
         SUB one \hfill ; the above three can be optimized to SUB one
         BLT skip_instr
         LOAD arg1 \hfill ; We are now setting up the recursion
         PUSH
         LOAD arg2 \hfill ; optimizer will skip this as *address is not modified
         PUSH \hfill; temp1, temp2, and ret_addr haven't been used yet.
           \hfill ; Now we do the function call
         LOAD lpf_ret_pt_var
         PUSH
         LOAD arg1
         SUB one
         PUSH
         LOAD arg2
         PUSH
lpf_ret_pt:
         POP
         STORE sum
         POP \hfill ; restore locally saved vars. 
         STORE arg2
         POP
         STORE arg1         
skip_inst:
         LOAD arg2
         ADD arg1
         SUB one
         STORE temp1 \hfill ; temp1 has &array[n-1]
         LOAD arg2 \hfill; really should have optimized here.
         ADD arg1
         STORE temp2 \hfill ; temp2 has &array[n].
         CLEAR
         ADDind temp1
         ADDind temp2
         SHIFTR 1
         STOREind temp1
         ADD sum
         STORE sum
return_pt:
         POP
         STORE ret_addr
         LOAD sum   
         PUSH
         BGEind ret_addr
         BLTind ret_addr \hfill ; we want an unconditional branch.
ret_addr: NOP
arg1:     NOP
arg2:     NOP
sum:      NOP
temp1:    NOP
temp2:    NOP
\end{alltt}


\end{problemparts}

%%%%%%%%%%%%%%%% Problem 3
\problem{Term Rewriting Systems for Architectural Description}

\medskip

\begin{problemparts}

\problempart{Register Indirect plus offset}
The rewrite rule for the {\em Load} instruction in AX' is: \\
{\it Load Rule} \\
{\bf Sys(m, Proc(ia, rf, prog)) {\it if} prog[ia] = 
r:=Load($r_a$, $v_{offset}$)} \\
$\rightarrow$  {\bf Sys(m, Proc(ia+1, rf[r:=m[a]], prog)) where
a=rf[$r_a$]+$v_{offset}$}

\medskip

\problempart{AX/S Stack Architecture}
{\it Push Rule} \\
{\bf Proc(ia, rf, s, prog)) {\it if} prog[ia] = Push(r)}, \\
$\rightarrow$  {\bf Proc(ia+1, rf, a ; s, prog)) where a=rf[r]}

{\it Pop- Non Empty Rule} \\
{\bf Proc(ia, rf, slot(v) ; s, prog)) {\it if} prog[ia] = r := Pop}, \\
$\rightarrow$  {\bf Proc(ia+1, rf[r:=v], s, prog))}

\medskip

\problempart{Synthesizable TRS's Description}
The first fundamental issue that needs to be addressed is that the stack 
size is not specified -- thus from the description given by the TRS, the
stacks have unlimited size.  In addition, there is no specified limit on the
number of registers.  This is a stack related issue since both pushes and
pops require some register access.  Finally, there is no preset size limit
on program variables.   

\end{problemparts} 


\end{problems}
\end{document}
