Subject: Basic Assembly Language as per instruction set below.

The function F is defined as F(1) = F(2) = F(3) = 1 and for n 3, F(n + 1) = F(n) + (F(n 1) F(n 2))

i.e., the (n + 1)th value is given by the sum of the nth value and the multiplication of the (n 1)th and (n 2)th values.

(a) Write an assembly program for computing the kth value F(k), where k is an integer bigger than 3 read from a memory location M, and storing F(k) at memory location M. Use the instruction set in the Instruction Set Architecture document

(b) Consider a pipelined processor, where the pipeline stages are F (fetch), D (decode), R (register read), E (execute) and W (write back). Describe what happens in the pipeline stages for the various types (data movement, data processing, control) of instructions.

(c) Show the execution of your program on the above pipelined processor for k = 5 by drawing a diagram. Assume that the fetched and decoded instructions are stored in an instruction window IW with a capacity of 12 instructions, and that there is no resource conflict between fetching instructions and executing data transfer instructions. Explain where and why delay slots appear.

Instruction Set Architecture We present a list of instructions typical of a RISC (reduced instruction set computer) machine. In data-movement and control instructions, the addresses may be immediate #X, direct (memory) M, indirect (memory) [M], register r, or register indirect [r] addresses. Data-processing instructions use immediate or register addressing. PC is the programme counter and a <- b indicates that the value of b is placed in a.

LOAD a, b STOR a, b ADD a, b, c SUB a, b, c MUL a, b, c DIV a, b, c AND a, b, c OR a, b, c NOT a, b ASH a, b, c LSH a, b, c BR a BEQ a, b, c BNE a, b, c BLT a, b, c BGT a, b, c BLE a, b, c BGE a, b, c

a <- b a <- b a <- b + c a <- b - c a <- b * c a <- b / c a <- b & c a <- b | c a <- !b a <- b arithmetically shifted by c positions a <- b logically shifted by c positions PC <- a PC <- a if b is equal to c PC <- a if b is not equal to c PC <- a if b is less than c PC <- a if b is greater than c PC <- a if b is less than or equal to c PC <- a if b is greater than or equal to c

Most instructions have floating-point versions when special floating-point registers are used (but we will not need these). Most architectures use two addresses, where the first (or second) argument serves both as the target and one of the sources, e.g., ADD a, b means a <- a + b. For branch instructions BR X means to jump to instruction X (i.e., load the address of instruction X into PC). We will use a five-stage pipeline: IF (instruction fetch), ID (instruction decode), RR (register read), EX (execute instruction), WB (write back result). We will assume that for data-movement instructions the data transfer between the CPU and main memory happens in the execute stage. Note that for some instructions (e.g., LOAD r, #X) some of the pipeline stages (e.g., RR) are not needed.