====== 3. Processor organization, instruction set ====== * for lecturer: [[..:..:..:internal:tutorials:03:start|tutorial 3]] ===== Exercise outline ===== - Basic instructions and their description - Introduction to development and simulation and environment (MipsIt, Mips) and simulated execution of simple program. - Transformation source code in C to assembler (MIPS instruction set). - 1st homework ([[https://dcenet.felk.cvut.cz/apo/]]) ===== What shall we do ===== ==== Part 1 - Basic instruction - description and use ==== Detailed description: ^ Instruction ^ Instruction Syntax ^ Operation ^ Description ^ | add | add \$d, \$s, \$t | \$d = \$s + \$t; | Add: Add together values in two registers (\$s + \$t) and stores the result in register \$d. | | addi | addi \$t, \$s, C | \$t = \$s + C; | Add immediate: Adds a value in \$s and a signed constant (immediate value) and stores the result in \$t. | | sub | sub \$d,\$s,\$t | \$d = \$s - \$t | Subtract: Subtracts a value in register \$t from value of \$s and stores result in \$d. | | bne | bne \$s, \$t, offset | if \$s != \$t go to PC+4+4*offset; else go to PC+4 | Branch on not equal: (conditional) jump if value in \$s is not equal to a value in \$t. | | beq | beq \$s, \$t, offset | if \$s == \$t go to PC+4+4*offset; else go to PC+4 | Branch on equal: (conditional) jump if value in \$s is equal to a value in \$t. | | jump | j C | PC = (PC ∧ 0xf0000000) ∨ 4*C | Jump: Unconditional jump to label C. | | lw | lw \$t,C(\$s) | \$t = Memory[\$s + C] | Load word: Loads a word from address in memory and stores it in register \$t. | | sw | sw \$t,C(\$s) | Memory[\$s + C] = \$t | Store word: Stores a value in register \$t to given address in memory. | | lui | lui \$t,C | \$t = C << 16 | Load upper immediate: Stores given immediate value (constant) C to upper part of register \$t. Register is 32 bits long and C is 16 bits. | | la |la \$at, LabelAddr | lui \$at, LabelAddr[31:16]; \\ ori \$at,\$at, LabelAddr[15:0] | Load Address: stores a 32 bit (address of) label and stores it to register \$at. This is a pseudo-instruction - it is translated into sequence of actual instructions. | \\ ---- \\ ==== Part 2 - Introduction to development and simulation environment (MipsIt, Mips) and simple program execution ==== ==== Development environment MipsIt ==== This program we will use for writing of our programs, compiling them and generating output (object) file for Misp, MipsPipeS and MipsPipeXL simulators. (We shall use only Mips simulator today). === 1. Create the new project === Empty screen after MipsIt starts: {{courses:B35APO:tutorials:03:01mipsit.png?400|}} \\ \\ Follow these steps: File -> New -> Project tab,\\ there select Assembler, fill-in name for the project and select folder for it.\\ Then continue with File -> New -> File tab.\\ there select Assembler, fill-in name for your file and check that you have checked "Add to project" === 2. Write your code === Into newly opened window (with *.s suffix) write your own program: \\ {{courses:B35APO:tutorials:03:02mipsit.png?400|}} \\ \\ You can use this template for your code:\\ #define t0 $8 #define t1 $9 #define t2 $10 #define s0 $16 #define s1 $17 #define s2 $18 .globl start .set noat .ent start start: // TODO: Write your code here. nop .end start \\ \\ As an example we will try following simple code. It adds two integers stored in registers s0 and s1 and store result into register s2. addi s0, $0, 0x15 addi s1, $0, 0x45 add s2, s0, s1 \\ Keywords .globl, .data, .text, .word are compiler pseudoinstructions. Detailed description is in ([[http://sourceware.org/binutils/docs/as/index.html|GNU Assembler Manual]]). === 3. Compiling === To compile the project use Build //XX// from Build menu (//XX// is name of your project). Alternatively you can use F7 key. Three files will be generated with suffix *.o, *.out and *.sreg. These will be placed in ''Object''subdirectory in your project. If everything goes right, the ''Output'' window in MipsIt should look like following picture: {{courses:B35APO:tutorials:03:03mipsit.png?400|}} \\ \\ There must not be any space the path, otherwise the compilation will crash. If there are problems with compilation, please check the path to the project (eg. File -> Options -> Directories tab, and paths for Executable files, Include files and Library files). \\ \\ ==== Mips simulation environment ==== The Mips program simulates MIPS processor and we will use it to execute our program, investigate what is doing and to debug it. === 1. Open compiled file === The first screen after the Mips simulator starts: {{courses:B35APO:tutorials:03:01_mips.png?400|}} \\ \\ Open the compiled file (File -> Open). Compiled file has *.out or *.sreg suffix. Open window with values in registers (View -> Register) and content of memory (View -> Memory). === 2. Simulation === Now we are ready to go step by step through our code. To go step by step use CPU -> Step from main menu or green arrow icon from the toolbar. The result should look as follows: {{courses:B35APO:tutorials:03:03_mips.png?804|}} \\ Before you can load new compiled program (*.out or *.sreg file) to simulator, you have to reset the processor first (CPU -> Reset). Without reset the values in PC and other registers will remain the same. After each reset, you have to load compiled program. Memory Window does not redraw itself properly. Therefore if you reset the processor or load new code, you have to hide the Memory window behind some other window to see the changes. \\ === 3. Code reload and run simulator anew === If any of Mips, MipsPipeS or MipsPipeXL is running, you can load code from the development environment (MipsIT) by clicking on //Build// -> //Upload// -> //To Simulator (F5)//. This item will also reset the processor into initial state. ------- \\ ==== Part 3 - Transcribe a program from C to Assembler ==== In many practical applications we have to use median filter. This median filter removes noise (obvious outliers/dead pixels) from a signal or an image. The median filter takes a neighborhood of a sample (10 samples before and 10 after), finds median value and replaces the sample value with this median. Very similar to this filter is mean filter that replaces the sample value with average value of the nearby samples. The median value is usually calculated by sorting the samples by value and picking the sample in the middle. The sorting algorithm is a cornerstone to median filter implementation. Lets assume we have 21 integers stored in array in memory. The array begins in some given address (e.g. 0x00). On integer occupies one word in the memory. The task is to sort the integers in ascending order. To do this we will implement the bubble sort algorithm. In this algorithm two adjacent values are compared and if they are in wrong order, they are swapped. And this comparisons goes repetitively through array until no swaps are done. The code for bubble sort is bellow: int pole[5]={5,3,4,1,2}; int main() { int N = 5,i,j,tmp; for(i=0; i \\ The example of sorting 5 numbers is bellow: \\ 5, 3, 4, 1, 2 --> initial state \\ 3, 4, 1, 2, **5** --> after the first outer cycle finished \\ 3, 1, 2, **4**, **5** --> after the second outer cycle finished \\ 1, 2, **3**, **4**, **5** ... \\ 1, **2**, **3**, **4**, **5** \\ **1**, **2**, **3**, **4**, **5** --> after the last outer cycle finished - sorted \\ \\ Transcribe C code above to MIPS assembler. Verify correctness of your implementation in Mips simulator. We will be using this program in the next class. So finish the program at home, if you have not finished it during the class. \\ Here is a template, you can use: #define t0 $8 #define t1 $9 #define t2 $10 #define t3 $11 #define t4 $12 #define s0 $16 #define s1 $17 #define s2 $18 #define s3 $19 .globl array .data .align 2 array: .word 5 3 4 1 2 .text .globl start .ent start start: // TODO: Write your code here nop .end start \\ ==== How to transcribe short fragments of C code into assembler ==== ^ **//if//** Command ^^ | if (i ==j) f = g + h; f = f – i; | // s0=f, s1=g, s2=h, s3=i, s4=j bne s3, s4, L1 // If i!=j, go to label L1 add s0, s1, s2 // if block: f=g+h L1: sub s0, s0, s3 // f = f-i | ^ **//if-else//** Command^^ | if (i ==j) f = g + h; else f = f – i; | // s0=f, s1=g, s2=h, s3=i, s4=j bne s3, s4, else // If i!=j, go to **else** label add s0, s1, s2 // if block: f=g+h j L2 // jump behind the **else** block else: sub s0, s0, s3 // else block: f = f-i L2: | ^ **//while//** Cycle ^^ | int pow = 1; int x = 0; while(pow != 128) { pow = pow*2; x = x + 1; } | // s0=pow, s1=x addi s0, $0, 1 // pow = 1 addi s1, $0, 0 // x = 0 addi t0, $0, 128 // t0 = 128 to compare (always have to compare two registers) while: beq s0, t0, done // If pow==128, end the cycle. Go to done label. sll s0, s0, 1 // pow = pow*2 addi s1, s1, 1 // x = x+1 j while done: | ^ **//for//** Cycle ^^ | int sum = 0; for(int i=0; i!=10; i++) { sum = sum + i; } | //Is equivalent to following while cycle: int sum = 0; int i = 0; while(i!=10){ sum = sum + i; i++; } | ^ Read values from the data memory. ^^ | // Just as an example... int a, *pa=0x80020040; int b, *pb=0x80020044; int c, *pc=0x00001234; a = *pa; b = *pb; c = *pc; | // s0=pa (Base address), s1=a, s2=b, s3=c lui s0, 0x8002 // pa = 0x80020000; lw s1, 0x40(s0) // a = *pa; lw s2, 0x44(s0) // b = *pb; addi s0, $0, 0x1234 // pc = 0x00001234; lw s3, 0x0(s0) // c = *pc; | ^ Increment values in an array ^^ | int array[4] = { 7, 2, 3, 5 }; int main() { int i,tmp; for(i=0; i<4; i++) { tmp = array[i]; tmp += 1; pole[i] = tmp; } return 0; } | Complete code for MipsIt simulator: #define s0 $16 #define s1 $17 #define s2 $18 #define s3 $19 .globl array // label "array" is declared as global. It is visible from all files in the project. .data // directive indicating start of the data segment .align 2 // set data alignment to 4 bytes array: // label - name of the memory block .word 7, 2, 3, 5 // values in the array to increment... .text // beginning of the text segment (or code segment) .globl start .ent start start: la s0, array // store address of the "array" to the register s0 addi s1, $0, 0 // initialization instruction of for cycle: i=0, kde i=s1 addi s2, $0, 4 // set the upper bound for cycle for: beq s1, s2, done // if s1 == s2, go to label done and break the cycle lw s3, 0x0(s0) // load value from the array to s3 add s3, s3, 0x1 // increment the s3 register sw s3, 0x0(s0) // replace (store) value from s3 register addi s0, s0, 0x4 // increment offset and move to the other value in the array addi s1, s1, 0x1 // increment number of passes through the cycle (i++). j for // jump to **for** label done: nop .end start | \\ ===== Odkazy ===== * {{courses:B35APO:tutorials:03:mipsit.zip|}} - MipsIT simulator to download * [[..:..:..:tutorials:03:mips-elf-gnu:start|GNU Cross Compiler for MIPS-ELF architecture]] - GNU Compatible Compiler for MIPS architecture for Debian Linux OS (x86_64/i586). * {{courses:B35APO:tutorials:03:gcc-binutils-newlib-mips-elf_4.4.4-1_mingw32.zip|}} - GNU Compatible compiler for MIPS architecture for MS Windows with MinGW32. To compile programs for MipsIT simulator you will need to specify following parameters: ''-nostdlib -nodefaultlibs -nostartfiles -Wl,-Ttext,0x80020000''. For more complex programs you will probably have to specify ''-lm -lgcc -lc'' parameters. * [[http://en.wikipedia.org/wiki/MIPS_architecture|Popis procesoru MIPS]] - description of MIPS processor and complete instruction set. * [[http://courses.missouristate.edu/KenVollmar/MARS/|MARS (MIPS Assembler and Runtime Simulator)]] * Missouri State University - Alternative MIPS simulator in JAVA * The source code in this simulator has to be without macro definitions. If you have source code from MipsIT simulator, you have to preprocess it. To do this, you can use e.g. GCC compiler in following way: ''gcc -E assembler.S -o preprocessed_assembler.s'' * [[http://www.linux-mips.org/wiki/Emulators|Other MIPS emulators/simulators on Linux-MIPS.org]]