Assignment 1, due Jan. 19

Solutions

Part of the homework for CS:3620, Spring 2018
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

Prerequisite material:

a) What computer instruction set(s) have you studied? Commercially available CPUs and fictional processors are equally relevant. (0.3 points)

A typical answer might say something like Intel x86 or MIPS or ARM or some mixture of these.

b) Pick an instruction set you identified in part a and translate the following function to assembly language: (0.7 points)

int fib( int i ) { if (i < 2) return i; return f( i - 1 ) + f( i - 2 ); }

There's a typo above, f() was supposed to be fib(). The following solution in the fictional Hawk instruction corrects the typo. Regardless of this correction, all solutions, regardless of the architecture used, will vaguely resemble the following:

; activation record format for FIB
RETAD   =       0
I       =       4
TMP     =       8
ARSIZE  =       12
; FIB expects R3 = i, the parameter and returns the result in R3
; FIB uses R4 as a scratch register
; by convention, R2 is the stack pointer and R1 holds the return address
FIB:
        CMPI    R3,2
        BLT     ENDIF           ; if (i > 1) {
        STORES  R1,R2           ;    -- save return addr
        STORE   R3,R2,I         ;    -- save parameter i
        ADDSI   R3,-1
        ADDI    R2,R2,ARSIZE    ;    -- push the activation record
        JSR     R1,FIB          ;    -- recursive call
        STORE   R3,R2,TMP-ARSIZE;    temp = fib( i - 1 )
        LOAD    R3,R2,I-ARSIZE
        ADDSI   R3,-2
        JSR     R1,FIB          ;    -- recursive call
        ADDI    R2,R2,-ARSIZE   ;    -- pop the activation record
        LOAD    R4,R3,TEMP
        ADD     R3,R3,R4        ;    i = fib( i - 2 ) + temp
        LOADS   R1,R2           ;    -- restore return addr
ENDIF:                          ; }
        JUMPS   R1              ; return i

Background: A paper by Parnas and Siewiorek is referenced in the notes for Jan. 17 that contains a preliminary example. What is the example? (1 point)

The example involves a 4-wheeled cart.
That would have been a sufficient answer, but you could go on as follows: The cart had independent steering controls on both front wheels. This gives extreme flexibility in steering while being dangerous at any speed faster than a slow walk. Parnas then discussed a higher level control system that links the two front wheels. This is not a transparent layer in the design hierarchy because it eliminates the ability to make very sharp turns, but it makes the cart much safer at high speeds.
Background: If you do not have a CLAS Linux account, create one. The instructions are here:
— http://clas.uiowa.edu/linux/
Go to the sub-page listing CLAS Linux Services and follow the instructions there for "Create a CLAS Account". Note that this is easier from on campus, for example, in one of the Information Technology Centers, because off campus users may have to tunnel through the University's firewall using a VPN. (The link for how to set that up is there too.)
Use your account to sign in to linux.cs.uiowa.edu (an alias for a cluster of Linux servers) using FastX. The following link takes you to FastX:
— http://fastx.divms.uiowa.edu
FastX opens a remote Linux desktop. The MATE desktop has an icon at the top to let you open a command line shell interface in the a terminal window.
When it is time to end your session, the exit shell command will close your terminal window. To close your FastX session and log out of Linux, click on the LogOut button in the System pull-down menu on your Linux desktop.
For additional guidance, see:
— http://clas.uiowa.edu/linux/help/remote_access
A question: Use a shell window on a CLAS Linux machine. Type the following command:
[HawkID@serv16 ~]$ ~dwjones/opsys
(Boldface in the above is the command you type, non-bold is the prompt from the system; type the requested text verbatim, do not change a thing, do not replace dwjones with your HawkID.) Report the output you got. If you did not make it all the way to the point where you could do the above, report how far you got. (1 point)
Here's what I got when I did it:
```
[dwjones@fastx06 ~]$ ~dwjones/opsys
On Thu Jan 25 10:27:44 CST 2018,  completed CS:3620 assignment 1.
```