程序代写代做 C algorithm kernel assembler assembly EXAM CODES: TITLE OF PAPER: TEST DURATION: READING TIME:

EXAM CODES: TITLE OF PAPER: TEST DURATION: READING TIME:
Monash University Semester Two Mid Semester Test 2016
Faculty of Information Technology
FIT1008
INTRODUCTION TO COMPUTER SCIENCE 35 minutes
5 minutes
THIS PAPER IS FOR STUDENTS STUDYING AT:
oBerwick oCaulfield oPharmacy
üClayton üMalaysia oGippsland oPeninsula oOther (specify)
oOff Campus Learning oEnhancement Studies
oOpen Learning oSth Africa
During an exam, you must not have in your possession, a book, notes, paper, electronic device/s, calculator, pencil case, mobile phone or other material/item which has not been authorised for the exam or specifically permitted as noted below. Any material or item on your desk, chair or person will be deemed to be in your possession. You are reminded that possession of unauthorised materials in an exam is a discipline offence under Monash Statute 4.1.
No examination papers are to be removed from the room.
AUTHORISED MATERIALS
CALCULATORS
OPEN BOOK
SPECIFICALLY PERMITTED ITEMS
o YES oYES oYES
ü NO üNO üNO
A – Official Use Only
STUDENT ID __ __ __ __ __ __ __ __
Page
Mark
3
5
7
9
Total
Page 1 of 9

This page intentionally left blank, use if needed but it will not be marked.
Page 2 of 9

Question 1 [3 marks]
This question is about MIPS programming. Translate the following Python code faith- fully into MIPS assembly language. Note that in this piece of code all variables are global variables. Add comments to your MIPS code to facilitate readability. Use only instructions or pseudo-instructions in the MIPS reference sheet.
a=3 b=5 c=0
while b > a:
if b % 2 == 0:
c=c+b else:
c = c -b b = b-1
Page 3 of 9
3

This page intentionally left blank, use if needed but it will not be marked.
Page 4 of 9

Question 2 [2 marks]
For each function below, provide best and worst case complexity in Big O notation. Explain your answer – no explanation means no marks.
1. def
2. def
function_a(a_list):
n = len(a_list)
for i in range(n-1, -1, -1):
for j in range(10): a_list[i] = j + i- 1
function(a_list):
n = for
len(a_list)
j in range(n):
i=j
while a_list[i] < 0: a_list[i] = j + i- 1 i=i-1 a_list[j] = i Page 5 of 9 2 This page intentionally left blank, use if needed but it will not be marked. Page 6 of 9 Question 3 [3 marks] A quick-sort implementation is given below: def quick_sort(a_list): start = 0 end = len(a_list) -1 quick_sort_aux(a_list, start, end) def quick_sort_aux(a_list, start, end): if start < end: boundary = partition(a_list, start, end) quick_sort_aux(a_list, start, boundary-1) quick_sort_aux(a_list, boundary+1, end) • Write a method partition, that completes this implementation. Your partition algorithm should have linear time complexity. • Is quick-sort stable? Explain your answer. No explanation means no marks. Page 7 of 9 3 This page intentionally left blank, use if needed but it will not be marked. Page 8 of 9 Question 4 [2 marks] Consider the following python code, which you wish to translate into MIPS. a=2 b=3 def my_function(a, b): i=a # HERE while i < b: a=a+b i +=1 return a my_function(a, b) Draw the memory diagram of the stack segment when code execution reaches the line marked with the comment HERE. The diagram should show, the stack pointer and frame pointer and any information that may be stored as part of the function calling convention discussed in the lectures. Global variables are not on the stack, so they are not to be shown. Before reaching my_function, ra = 0x00400000 and fp = 0x7FFFB3114. Page 9 of 9 3 Call code ($v0) 1 Service Arguments Returns Notes .data .text .byte b1[, b2, ...] .half h1[, h2, ...] .word w1[, w2, ...] .space n .align n .ascii ”string” .asciiz ”string” 4 string must be terminated with ’\0’ value is signed 5 8 Input integer Input string - $v0 = entered integer – 9 10 Allocate memory Exit $a0 = number of bytes - $v0 = address of first byte - - On function return: Callee: Caller: Number R00 R01 R02, R03 R04–R07 R08–R15 R16–R23 R24, R25 R26, R27 R28 Name Purpose provides constant zero reserved for assembler system call code, return value system call and function arguments temporary storage (caller-saved) temporary storage (callee-saved) temporary storage (caller-saved) reserved for kernel code pointer to global area stack pointer frame pointer return address R29 R30 R31 $sp $fp $ra Instruction Format Rsrc, Rsrc1, Rsrc2: source operand(s), - must be a register value(s) Src2; source operand - may be an immediate value or a register value Rdest: destination, must be a register Imm: Immediate value, may be 32 or 16 bits Imm16: Immediate 16-bit value Addr: Address in the form: o↵set(Rsrc) ie. absolute address = Rsrc + o↵set label: label of an instruction ?: pseudoinstruction Immediate Form -: no immediate form, or this is the immediate form ?: immediate form synthesized as pseduoinstruction Unsigned form (append ’u’ to instruction name): - : no unsigned form, or this is the unsigned form Print integer Print string $a0 = value to print $a0 = address of string to print - - value is signed assemble into text (code) segment allocate byte(s), with initial value(s) allocate halfword(s), with initial value(s) allocate word(s) with initial value(s) allocate n bytes of uninitialized, unaligned space align the next item to a 2n-byte boundary allocate ASCII string, do not terminate allocate ASCII string, terminate with ’\0’ Table 1: SPIM system calls Table 3: Assembler directives assemble into data segment $a0 = address to store string at $a1 = max- imum number of chars returns if $a1-1 charac- ters or Enter typed, the string is ter- minated with ’\0’ Caller: Table 4: Function calling convention On function call: Table 2: General-purpose registers $zero $at $v0, $v1 $a0--$a3 $t0--$t7 $s0--$s7 $t8, $t9 $k0, $k1 $gp Table 5: Instruction Set FIT1008 Supplementary Material - MIPS Reference Sheet ends simula- tion sets $v0 to return value clears local variables o↵ stack restores saved $fp and $ra o↵ stack returns to caller with jr $ra clears arguments o↵ stack restores temporary registers o↵ stack uses return value in $v0 saves temporary registers on stack passes arguments on stack calls function using jal fn label saves $ra and $fp on stack copies $sp to $fp allocates local variables on stack A partial instruction set is on the next page. The following conventions apply. Page 1 Callee: Table 6: MIPS instruction set Instruction format Meaning Operation Immediate form Unsigned form(u) add Rdest, Rsrc1, Rsrc2 sub Rdest, Rsrc1, Rsrc2 mul Rdest, Rsrc1, Rsrc2 ? mulo Rdest, Rsrc1, Rsrc2 ? mult Rsrc1, Rsrc2 div Rdest, Rsrc1, Rsrc2 ? div Rsrc1, Rsrc2 rem Rdest, Rsrc1, Rsrc2 ? neg Rdest, Rsrc ? Add Subtract Multiply Multiply (with 32-bit overflow) Multiply (machine instruction) Divide Divide (machine instruction) Remainder Negate Rdest = Rsrc1 + Rsrc2 Rdest = Rsrc1 - Rsrc2 Rdest = Rsrc1 * Rsrc2 Rdest = Rsrc1 * Rsrc2 Hi:Lo = Rsrc1 * Rsrc2 Rdest=Rsrc1/Rsrc2 Lo = Rsrc1/Rsrc2; Hi = Rsrc1 % Rsrc2 Rdest = Rsrc1 % Rsrc2 Rdest = -Rsrc1 addi ? ? ? - ? - ? - no overflow trap no overflow trap unsigned operands unsigned operands unsigned operands unsigned operands unsigned operands unsigned operands no overflow trap and Rdest, Rsrc1, Rsrc2 or Rdest, Rsrc1, Rsrc2 xor Rdest, Rsrc1, Rsrc2 nor Rdest, Rsrc1, Rsrc2 not Rdest, Rsrc ? Bitwise AND Bitwise OR Bitwise XOR Bitwise NOR Bitwise NOT Rdest = Rsrc1 & Rsrc2 Rdest = Rsrc1 | Rsrc2 Rdest = Rsrc1 ^ Rsrc2 Rdest = ⇠(Rsrc1 | Rsrc2) Rdest = ⇠(Rsrc) Rdest = Rsrc1 << Rsrc2 Rdest = Rsrc1 >> Rsrc2 (MSB=0)
Rdest = Rsrc1 >> Rsrc2 (MSB preserved)
andi ori xori ?

– –

– – – – –
sll Rdest, Rsrc1, Rsrc2 srl Rdest, Rsrc1, Rsrc2
sra Rdest, Rsrc1, Rsrc2
Shift Left Logical Shift Right Logical
Shift Right Arithmetic
– –

move Rdest, Rsrc ? mfhi Rdest
mflo Rdest
Move
Move from Hi Move from Lo
Rdest=Rsrc Rdest = Hi Rdest = Lo
– – –
– – –
li Rdest, Imm ?
lui Rdest, Imm16
la Rdest, Addr(or label) ?
Load immediate
Load upper immediate Load Address
Rdest=Imm Rdest=Imm16 << Imm Rdest=Addr (or Rdest=label) - - - - - - lb Rdest, Addr (or label ?) lh Rdest, Addr (or label ?) lw Rdest, Addr (or label ?) Load byte Load halfword Load word Rdest = mem8[Addr] Rdest = mem16[Addr] Rdest = mem32[Addr] - - - zero-extends data zero-extends data - sb Rsrc2, Addr (or label ?) sh Rsrc2, Addr (or label ?) sw Rsrc2, Addr (or label ?) Store byte Store halfword Store word mem8[Addr] = Rsrc2 mem16[Addr] = Rsrc2 mem32[Addr] = Rsrc2 - - - - - - beq Rsrc1, Rsrc2, label bne Rsrc1, Rsrc2, label blt Rsrc1, Rsrc2, label ? ble Rsrc1, Rsrc2, label ? bgt Rsrc1, Rsrc2, label ? bge Rsrc1, Rsrc2, label ? slt Rdest, Rsrc1, Rsrc2 Branch if equal Branch if not equal Branch if less than Branch if less than or equal Branch if greater than Branch if greater than or equal Set if less than if (Rsrc1 PC = if (Rsrc1 PC = if (Rsrc1 PC = if (Rsrc1 PC = if (Rsrc1 PC = if (Rsrc1 PC = if (Rsrc1 Rdest=1 == Rsrc2) label != Rsrc2) label < Rsrc2) label <= Rsrc2) label > Rsrc2) label
>= Rsrc2) label
< Rsrc2) else Rdest=0 ? ? ? ? ? ? slti - - unsigned operands unsigned operands unsigned operands unsigned operands unsigned operands j label jal label jr Rsrc jalr Rsrc Jump Jump and link Jump register Jump and link register PC = label $ra = PC + 4; PC = label PC = Rsrc $ra = PC + 4; PC = Rsrc - - - - - - - - syscall System call depends on call code in $v0 - - Page 2