MIPS Programming (Part 1) PDF

Preview

Summary

Part 1 of the summarised MIPs notes. 93% for this exam using these notes....

Description

Introduction Thursday, 26 July 2018

11:47 AM

What are registers? • A register is a sequence of logic gates (one per binary digit represented within the register) which (while power persists) continually run current through themselves to maintain a 0 or 1 state until it is changed • The value they store are like global variables that every function can and will use Machine Code • To run programs on a computer we need machine code • Each machine code instruction is executed by the CPU • Machine code is hard to read • Corresponding to each machine code instruction is an assembly instruction • Assembly is easier to read • MIPS is an Assembly Language

•

Why learn Assembly? • Understand how high level code works to be a better programmer • Might need to write it in when timing is critical or when memory size is limited (e.g. device drivers, embedded computers) • Might need to read it (e.g. to inspect optimisations made by the compiler) What are instructions? • Basically "what it is you want to do" • Registers is the temporary storage to help operate the instructions Immediate values: Any number that can fit in 16 bits What is MIPS? • MIPS stand for "Microcomputer without Interlocking Pipeline Stages" • Ancestor to popular systems today, good starting point for system architectures • Programs must be translated into machine code so the system can understand how to execute them • Machine code is difficult to read, but each instruction that can be executed in machine code has a corresponding MIPS Assembly command • MIPS Assembly is easier to read because it was made to be programmed with

RISC vs CISC • MIPS was the first computer to use RISC ○ Reduced Instruction Set Computer • All instructions are ○ Same length (4 bytes) ○ Similar complexity (simple) ○ Able to run in the same time (1 clock cycle)

MIPS Programming Page 1

○ Easily decoded and executed by computer hardware Advantages: Easier to build, cheaper, consumes less power • • Intel x86 is considered CISC ○ Complex Instruction Set Computer • Features ○ Instructions vary in length, complexity and execution time ○ Decoding and running instructions requires hardware-embedded program (microcode) ○ Advantage: potential for optimisation of complex instructions

MIPS Programming Page 2

MIPS Architecture Thursday, 26 July 2018

11:49 AM

Simplified MIPs Architecture

•

Overview • MIPS machines contain 32 general-purpose registers for use during computation • Registers allow for fast usage but at the expense of more memory • Each register are 32 bits in size and are all located on the CPU chip • The Arithmetic Logic Unit (ALU) provides arithmetic computation using register values as opposed to main memory ○ Performs computations on register values (not main memory) ▪ Register-to-register (or load-store) architecture ▪ Integer and bitwise arithmetic (including comparisons) ○ Fetching: Retrieving values from memory • Several special purpose registers ○ PC (Program Counter) ○ HI, LO (multiplication/division results) ○ IR (Instruction Register) ○ MAR/MRR/MWR (Memory Address/Read/Write Register) • These are used in specific tasks during computation and are usually read only

MIPS Programming Page 3

General Purpose Registers (GPRs) Thursday, 26 July 2018

11:52 AM

• The 32 general-purpose registers range from $0 to $31 ○ Prefixed with $ in assembly language • Each register is used for a specific purpose as defined by convention • These registers can be used in any way ○ Exception: $zero which is a read only register with the integer 0 in it • Unlike variables, their names are hard coded and cannot be changed

•

• $aX for arguments • $tX and $Sx for anything, they are general purposed

MIPS Programming Page 4

Arithmetic Logic Unit (ALU) Thursday, 26 July 2018

12:07 PM

Diagram

Purpose • Performs all arithmetic operations in the systems • Addition and subtraction can sometimes cause overflow issues (where the number calculated cannot be represented in 32 bits) • But there is only fail safes for this occurrence in multiplication and division ○ This is because the problem occurs mostly using these operations HI and LO Registers • Multiplying two 32 bit numbers may require 64 bits to represent the answer • After an integer multiplication: ○ HI contains the "high" 32 bits ○ LO contains the "low" 32 bits • After an integer division: ○ LO contains the result ○ HI contains the remainder • Integer division might be used to get the result or get the remainder • There are instructions to move the contents of LO and HI back to a GPR

MIPS Programming Page 5

Special Purpose Registers Thursday, 26 July 2018

12:07 PM

Table of SPRs

•

IR Register • Stores the instructions to be executed (32 bits, 4 bytes, 1 word) • Bits encode what type the instruction it is (known as the opcode) • Rest of the content is entirely dependent on the type indicated ○ The opcode will tell the control circuitry which set of microinstructions need to be followed PC Register • Stores where the computer is up to in the current program ○ Basically a bookmark • Holds the memory address of the machine instruction currently being executed • Counter is advanced (PC = PC + 4) by most instructions • Jump commands can take the PC to specific locations in the code for the purposes of if statements, loops or function calls

MIPS Programming Page 6

Assembly Programming Thursday, 26 July 2018

12:16 PM

Introduction • Python code (like below) can be simple, but when encoded in Assembly, it becomes more complicated • Each little step must be written out in order for the computer to run it ○ • When written in MIPS Assembly, the code becomes like below

•

Assembler Directives • Always start with . (dot) • Instruct the assembler to allocate space or data, or switch modes • Assembler directives don't assembler to machine language instructions List of possible directives

•

Labels and Symbols • Labels are names for locations in memory ○ Needs to be translated into numbers before execution • Assembler uses a symbol table to do this ○ When it sees a label being defined: ▪ Puts the label name and the current address in the table ○ When it sees a label being used: ▪ It looks the name up in the table to find what address it refers to • Labels can be used for jumping or referencing arrays MIPs Instructions • Instructions to be compiled by the system • Each instruction has a format that indicates its operation and its required parameters Comments • Not compiled • Exists to document the program and to assist the programmers understanding

MIPS Programming Page 7

Input/Output • I/O is complicated → Usually handled by the operating system (OS) • MIPS program request I/O from the OS using a command called syscall System Call • When syscall is called, the system will perform a specific task depending on the value stored in $v0

•

Making a system call 1. Work out which service you want 2. Put service's call code in register $v0 3. Put argument (if any) in registers $a0, $a1 4. Perform the syscall instruction 5. Result (if any) will be returned in register $v0 Data Movement Instructions • To move from HI • To move from LO

MIPS Programming Page 8

Decision Making Saturday, 28 July 2018

10:33 PM

Jump Instructions • The goto statement is a function that 'jumps' from one part of the code to another • Jumps using labels found inside of the code structure • Python (fake) example

○

• Modern code has moved away from this use but still remains in Assembly • In MIPS, goto is implemented using 'Jump' instructions

•

Selection Instructions • Programs make decisions through the use of selection ('if' or 'if-else' clauses) • In MIPs, the first instruction set needed to implement selection is Comparison Instructions •

Branching Instructions • This instruction set allows for 'branching' (jumping) based on what was set using the above instructions • In MIPs, branching is implemented using Conditional Branch instructions •

Note: These commands are NOT exhaustive Note: Comparisons are performed by the ALU, so comparison instructions are really arithmetic ones Note: See negative.asm

MIPS Programming Page 9

Instructions Monday, 30 July 2018

1:26 PM

Shift left logical: Allows you to shift a given (binary) number by n times to the left • Basically multiplying it by 2n

Shift right logical: Allows you to shift a given (binary) number by n times to the right • Basically dividing it by 2n MIPs Instruction Execution • Programs are run by the MIPs hardware performing fetch-decode-execute cycles

•

Example

•

MIPS Instruction Format • Every MIPS instruction is 32-bits in size and occupies 4 bytes of memory or 1 word • Each instruction contains: ○ Opcode ○ Operation code: Specifies type of instruction ○ Operands ○ Values or location to perform operation on ▪ Registers ▪ Immediate (constant numbers) ▪ Labels (Addresses of other lines of program)

Types of Instructions

MIPS Programming Page 10

•

• Instructions take up certain proportions of the message length available to the system • In this case, MIPS works with 32 bits • Diagram of what the instructions look like

•

•

•

I-type Instruction: Example

MIPS Programming Page 11

•

MIPS Programming Page 12

Main Memory Thursday, 26 July 2018

1:42 PM

Von Neumann Architectures • Separate modules for Processing and Main Memory • Programs are stored in main memory • Each instruction must be loaded in the processor before execution

•

Accessing the Main Memory • MIPs is a load-store architecture ○ Computations take place in registers • Programs and their data live in main memory, not CPU ○ We need to load data into a register to work on it ○ And then store it back into memory when we're done • To do this loading/storing, we need to know ○ Which register we're loading to/storing from ○ Where in memory to find/put in data MIPS Architecture: Memory

•

Memory addresses • Memory addresses in MIPS are 32 bits long and unsigned • Each address refer to one byte of memory ○ Total potential address space: 4 GB = 232 • Usually only use addresses for words ○ Addresses are multiples of 4

MIPS Programming Page 13

Getting data out of main memory • We use a load instructions ○ Can load 1,2, or 4 bytes at a time ○ In this unit, usually 4: "load word" or lw • To execute a load instruction ○ The address to be loaded from goes into the MAR ○ The memory controller gets told to do a read ○ The data at that address goes into the MRR ○ The MRR is copied to the destination register (GPR) specified in instructions Putting data into main memory • We use a store instruction for this ○ Can store 1,2, or 4 bytes at a time ○ Usually, 4: "store word" or sw • To execute a store instruction ○ The contents of the GPR specified in the instruction are copied to the MWR ○ The address to be stored to goes into the MAR ○ The memory controller gets told to do a write ○ The data in the MWR gets written to memory

Memory Segments The Text Segment • Starts at 0x00400000 (that’s 4194304 in decimal) • Executable code goes here (in machine readable format) • PC register value is effectively a CPU "reference" into the text segment • How does code get here? ○ For compiled programs, the OS puts it there when you tell it to run a program ○ Process known as "loading" • Memory addresses lower than the start of the text segments are reserved for the OS The Data Segment • Starts at 0x10000000 • Contains program's static data ○ Global variables ○ String constants • Contains dynamically allocated memory ○ Heap segment The Heap Segment • Grows "downwards" as more memory is allocated • Shrinks when memory when is deallocated ○ Either by the garbage collector or programmer • Empty at the start of program execution • Note: "heap" means "pile", NOT the data structure The Stack Segment • Starts at 0x7FFFFFFC • Grows "upwards" towards the Data segment • Contains System stack ○ Local variables in functions ○ Function arguments ○ Function return address ○ Saved registers ○ Frame pointer Why does the heap and stack segment grow towards each other?

MIPS Programming Page 14

•

Why keep text and data segment separate?

•

Why 32 registers? • 25 → With 5 bits you can make 32 numbers, 0 - 31 • Any more registers than 32, we will need more than 5 bits • 32 is the lowest you can get with 5 bits, also didn’t need 16 because 16 wasn’t enough • Programs will be sufficiently fast

•

•

MIPS Programming Page 15

•

What advantages are there to having instructions the same length? And what disadvantages are there? • Instructions are always in 32 bits in MIPS • If you have a fixed length system, you need all instructions to be of the same length • Variable length instructions will be more complicated

•

•

MIPS Programming Page 16

Iteration Tuesday, 31 July 2018

1:39 PM

Iteration: The repetition of a section of code • In Python with while and for • while test condition before loop entry • for is a shorthand for while • Achieved by sending control from the end of the loop back to the beginning ○ Test some condition to prevent an infinite loop Iteration: for • A for loop is basically a simpler version of a while loop: ○ Initialisation, condition and increment code all in one place ○ • To translate a for loop into MIPS → Write it as a while loop • Before attempting translation of a for structure, turn it into while • Iteration is truly a special case of selection

•

• See factorial.asm Note: Try to load as frequently as possible when writing instructions so that you can be fully safe Note: Check for condition first for while/for loops, check for condition last for do-while loop

MIPS Programming Page 17

Arrays Tuesday, 31 July 2018

2:31 PM

Lists vs Arrays • Arrays have a fixed length • All the items will have the same size • All the items in the list are initialised to 0 • We will store length before the items • In MIPS, arrays are stored in the heap

Arrays in MIPS

•

•

•

MIPS Programming Page 18

•

•

•

Five ways to specify an address

•

• sw will store the value from a register $t1 into the ADDRESS that another register is holding • Brackets basically mean treat the contents of the register as an address

MIPS Programming Page 19

Creating Arrays in MIPS • 1. Allocate memory on the Heap for the list together with the length of the list (at the start) ○ For integers, space (number of bytes) required: 4 *size + 4 ○ A word for every item + the size itself 2. Store the address (after syscall in $v0) into the_list and add the size of the list into the address of the list (using brackets) 3. Store the address of the first byte of memory allocated in the_list

•

Accessing arrays • To access an element a. Get address from the_list to a register b. Increment 4 to get to the address of the zeroth element c. Offset = Index of element * 4 d. Add offset to register e. Result = Address of the element in a register Example • construct_list.py ○

Creating the list

•

MIPS Programming Page 20

•

Read the values into the list

•

•

•

Print list

MIPS Programming Page 21

•

MIPS Programming Page 22

Examples Thursday, 16 August 2018

1:54 PM

Q1

•

MIPS Programming Page 23

Q2

•

Q3

MIPS Programming Page 24

•

Q4

MIPS Programming Page 25

•

Question

•

Question

MIPS Programming Page 26

•

Question

•

Question

MIPS Programming Page 27

•

•

Question

MIPS Programming Page 28

•

Question

MIPS Programming Page 29

Example

•

•

MIPS Programming Page 30

•

•

Next

MIPS Programming Page 31

•

Next

•

Next

MIPS Programming Page 32

•

•

Example

MIPS Programming Page 33

•

Example

MIPS Programming Page 34

Example

•

•

Example

MIPS Programming Page 35

•

MIPS Programming Page 36...