Warning
This page is located in archive.

3. Processor organization, instruction set

Exercise outline

  1. Basic instructions and their description
  2. Introduction to development and simulation and environment (MipsIt, Mips) and simulated execution of simple program.
  3. Transformation source code in C to assembler (MIPS instruction set).

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:



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:


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 (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 Objectsubdirectory in your project. If everything goes right, the Output window in MipsIt should look like following picture:



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:



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:


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 BuildUploadTo 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<N; i++)
		for(j=0; j<N-1-i; j++)
			if(pole[j+1]<pole[j])
			{
				tmp = pole[j+1];
				pole[j+1] = pole[j];
				pole[j] = tmp;
			}
	return 0;
}

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

  • mipsit.zip - MipsIT simulator to download
  • GNU Cross Compiler for MIPS-ELF architecture - GNU Compatible Compiler for MIPS architecture for Debian Linux OS (x86_64/i586).
  • 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.
  • Popis procesoru MIPS - description of MIPS processor and complete instruction set.
    • 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

courses/b35apo/en/tutorials/03/start.txt · Last modified: 2018/09/23 18:45 by pisa