====== 3. Základní struktura procesoru, instrukční soubor ======
* pro vyučující: [[..:..:internal:tutorials:03:start|cvičení 3]]
===== Osnova cvičení =====
- Význam a použití základních instrukcí
- Seznámení se s vývojovým a simulačním prostředím (programy MipsIt a Mips) a simulace vykonávání jednoduchého programu
- Přepis programu z jazyka C do asembleru (instrukční sada MIPS)
- Upozornění na 1. domácí úkol ([[https://dcenet.felk.cvut.cz/apo/]])
===== Náplň cvičení =====
První část - Význam a použití základních instrukcí
Bližší popis instrukcí:
^ Instrukce ^ Syntax ^ Operace ^ Význam ^
| Add | add \$d, \$s, \$t | \$d = \$s + \$t; | Add: Sečte dva registry \$s + \$t a výsledek uloží do registru \$d |
| Addi | addi \$t, \$s, C | \$t = \$s + C; | Add immediate: Sečte hodnotu v \$s a znaménkově rozšířenou přímou hodnotu, a výsledek uloží do \$t |
| Sub | sub \$d,\$s,\$t |\$d = \$s - \$t | Subtract: Odečte znaménkově obsah registru \$t od \$s a výsledek uloží do \$d |
| Bne | bne \$s, \$t, offset | if \$s != \$t go to PC+4+4*offset; else go to PC+4 | Branch on not equal: Skáče pokud si registry \$s a \$t nejsou rovny |
| Beq | beq \$s, \$t, offset | if \$s == \$t go to PC+4+4*offset; else go to PC+4 | Branch on equal: Skáče pokud si registry \$s a \$t jsou rovny |
| slt | slt \$d,\$s,\$t | \$d = (\$s < \$t) | Set on less than: Nastavi registr \$d, pokud plati podminka \$s < \$t |
| sll | sll \$d,\$s,C | \$d = \$s << C | Shift Logical Left: Posune hodnotu v registru o C bitu doleva (ekvivalentni k operaci nasobeni konstantou 2C ) |
| jump | j C | PC = (PC ∧ 0xf0000000) ∨ 4*C | Jump: Skáče bezpodmíněčně na návěstí C |
| lw | lw \$t,C(\$s) | \$t = Memory[\$s + C] | Load word: Načte slovo z paměti a uloží jej do registru \$t |
| sw | sw \$t,C(\$s) | Memory[\$s + C] = \$t | Store word: Uloží obsah registru \$t do paměti |
| lui | lui \$t,C | \$t = C << 16 | Load upper immediate: Uloží předanou přímou hodnotu C do horní části registru. Registr je 32-bitový, C je 16-bitová. |
| la |la \$at, LabelAddr | lui \$at, LabelAddr[31:16]; \\ ori \$at,\$at, LabelAddr[15:0] | Load Address: 32-bitové návěstí uloží do registru \$at. Jedná se o pseudoinstrukci - tzn. při překladu se rozloží na dílčí instrukce. |
\\
----
\\
Druhá část - Seznámení se s vývojovým a simulačním prostředím (programy MipsIt a Mips) a simulace vykonávání jednoduchého programu
==== Vývojové prostředí MipsIt ====
Tento program budeme používat pro psaní vlastního programu v asembleru a následné generování výstupního souboru pro simulátor Mips, MipsPipeS a MipsPipeXL (dnes budeme používat jenom simulátor Mips).
Na instalaci **Ubuntu APO** se prostředí a ikonky na desktopu nastaví příkazem
mipsit-setup
V případě, že již je prostředí nastavené, tak lze provést jeho kompletní reset.
**POZOR** příkaz způsobí smazání veškerých dat ve složce ~/.wine. To zahrnuje i veškeré projekty v prostředí MipsIT, pokud jsou ukládané do standardní/nezměněné složky
mipsit-setup force
=== 1. Vytvoření nového projektu ===
Úvodní obrazovka po spuštění programu:
{{courses:A0B36APO:tutorials:03:01mipsit.png?400|}}
\\
\\
Postupujeme v těchto krocích: File -> New -> karta Project,\\
kde vybereme Assembler, vyplníme jméno vytvářeného projektu a zvolíme umístění \\
Dále pak: File -> New -> karta File,\\
kde vybereme Assembler, vyplníme jméno souboru a zkontrolujeme zda máme zaškrtnuto "Add to project"
\\
=== 2. Psaní vlastního programu ===
Do nově otevřeného okna (s příponou *.s) pak píšeme vlastní program: \\
{{courses:A0B36APO:tutorials:03:02mipsit.png?400|}}
\\
\\
K tomuto účelu můžeme využít připravenou šablonu:\\
#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:
// Zde je místo pro Váš vlastní kód...
nop
.end start
\\
\\
Pro ukázku si můžete zkusit napstat krátký program, který sečte dvě čísla uložená v registrech s0 a s1, a výsledek uloží do registru s2.
addi s0, $0, 0x15
addi s1, $0, 0x45
add s2, s0, s1
\\
Klíčová slova .globl, .data, .text, .word jsou pseudoinstrukce překladače
assembleru. Podrobný popis lze nalézt v dokumentaci
([[http://sourceware.org/binutils/docs/as/index.html|GNU Assembler Manual]]).
=== 3. Kompilace ===
Projekt přeložíme výběrem v menu: Build -> Build xx, kde xx je jméno Vašeho projektu. Alternativou je klávesa F7. Vygenerují se tři soubory s příponou *.o, *.out a *.sreg umístěné v podadresáři Objects aktuálního pracovního adresáře projektu. Při správném postupu by měla být obrazovka programu (výpis v okně "Output") nasledující: \\
{{courses:A0B36APO:tutorials:03:03mipsit.png?400|}}
\\
\\
Důležitá poznámka: Nikde v cestě nesmí být mezera. Pokud nefunguje překlad projektu je zapotřebí zkontrolovat cestu k projektu (a/nebo také: File -> Options -> karta Directories, a zde cesty pro: Executable files, Include files a Library files.
\\
\\
==== Simulační prostředí Mips ====
Tento program budeme používat pro simulaci vykonávání napsaného programu - sledování (krokování) vykonávání programu a ověření jeho funkčnosti.
=== 1. Otevření souboru pro simulaci a příprava ===
Úvodní obrazovka po spuštění programu:
{{courses:A0B36APO:tutorials:03:01_mips.png?400|}}
\\
\\
Soubor vygenerovaný programem MipsIt (s příponou *.out nebo *.sreg) načteme cez: File -> Open. Dále pak zobrazíme pracovní registry procesoru (View -> Register) a paměť programu (View -> Memory).
=== 2. Simulace ===
Po vykonání výše uvedeného postupu a odkrokování programu (Cpu -> Step nebo klikáním na ikonu {{courses:A0B36APO:tutorials:03:step.png?18|}}) dostaneme:
{{courses:A0B36APO:tutorials:03:03_mips.png?804|}}
\\
Upozornění: Před opakovaným načtením souboru *.out nebo *.sreg je zapotřebí nejdřív zresetovat procesor: Cpu -> Reset. Po každém zresetováni procesoru je zapotřebí soubor *.out nebo *.sreg načíst znovu. Okno pro vykreslování paměti (to žluté) má problémy s překreslováním - pokud se obsah paměti modifikuje instrukcemi sw nemusí být zápis vidět. Postačí jej na chvíli překrýt jiným oknem.
\\
=== 3. Opětovné načtení kódu do spuštěného simulátoru ===
Pokud je již některý ze simulátorů Mips.exe, MipsPipeS.exe
nebo MipsPipeXL.exe spuštěný, lze kód do simulátoru načíst
z prostředí MipsIT.exe aktivací položky
Build -> Upload -> To Simulator (F5)
Volba zároveň provede inicializaci CPU do počátečního stavu.
-------
\\
Třetí část cvičení
==== Přepis programu z jazyka C do asembleru ====
V praktických aplikacích se častokrát setkáváme s použitím mediánového filtru. Ten nám pomáhá odstranit ze signálu (nebo obrazu) zcela zjevné výkmity (nebo poškozené pixely). Narozdíl od průměrovacího filtru, který spočítá aritmetický průměr nejakého okolí a stávající hodnotu signálu nahradí vypočteným průměrem, mediánový filtr ji nahradí prostřední hodnotou (mediánem) tohoto okolí. Pro realizaci mediánového filtru je potřebné nejdříve seřadit všechny hodnoty a pak z nich vybrat onu prostřední. Klíčovou roli zde sehrává řazení. Mějme následující problém. V datové paměti nech je uloženo N celých čísel (1 < N < 21) počínaje od nějaké adresy (například 0x00), přičemž jedno číslo v paměti zabírá velikost jednoho slova. Našim úkolem je uvedená čísla vzestupně seřadit. Nejsnažší způsob jak tento problém řešit je použít bublinkové řazení. Princip tohoto algoritmu spočívá v tom, že se postupně a opakovaně prochází seřazované pole, přičemž se porovnávají každé dva sousedící prvky, a pokud nejsou ve správném pořadí, prohodí se. Hodnotu N si zvolte sami.
int pole[5]={5,3,4,1,2};
int main()
{
int N = 5,i,j,tmp;
for(i=0; i
\\
Princip algoritmu: Řazení prvků se uskutečňuje ve dvou vnořených cyklech - vnějším a vnitřním. Vnější cyklus zabezpečuje opakované spouštění vnitřního cyklu. Vnitřní cyklus postupně procházení pole a vzájemně vyměňuje dvě sousedící položky pokud nejsou v správném pořadí (má být menší vlevo, větší napravo). Protože vnitřní cyklus prochází polem zleva doprava (od menších indexů k větším) důsledkem je, že na konci pole se objeví vždy největší prvek z celého pole - největší prvek "probublal" na konec pole. Proto při dalším spuštění vnitřního cyklu nemusíme již procházet celým polem, ale jenom doposud neseřazenou částí tohoto pole. Postačuje N spuštění vnitřního cyklu aby se pole seřadilo.\\
\\
5, 3, 4, 1, 2 --> počáteční stav \\
3, 4, 1, 2, **5** --> po prvním průchodu vnějším cyklem \\
3, 1, 2, **4**, **5** --> po druhém průchodu vnějším cyklem \\
1, 2, **3**, **4**, **5** ... \\
1, **2**, **3**, **4**, **5** \\
**1**, **2**, **3**, **4**, **5** --> po pátém průchodu cyklem - seřazeno \\ \\
Přepište výše uvedený program z jazyka C do asembleru. Vykonávání programu oveřte v simulátoru Mips. Tento program budete potřebovat na příštím cvičení - to co nestihnete na cvičeních bude nutno dodělat doma..
\\
Můžete využít předpripravenou šablonu k tomuto úkolu:
#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 pole
.data
.align 2
pole:
.word 5,3,4,1,2
.text
.globl start
.ent start
start:
// Zde muzete psat Vas program
nop
.end start
\\
==== Příklady přepisu krátkých fragmentů kódu z jazyka C do asembleru ====
^ Příkaz **//if//** ^^
|
if (i ==j)
f = g + h;
f = f – i;
|
// s0=f, s1=g, s2=h, s3=i, s4=j
bne s3, s4, L1 // Pokud i!=j, skoč na L1
add s0, s1, s2 // if blok: f=g+h
L1:
sub s0, s0, s3 // f = f-i
|
^ Příkaz **//if-else//** ^^
|
if (i ==j)
f = g + h;
else
f = f – i;
|
// s0=f, s1=g, s2=h, s3=i, s4=j
bne s3, s4, else // Když i!=j, skoč na else
add s0, s1, s2 // if blok: f=g+h
j L2 // přeskoč blok else
else:
sub s0, s0, s3 // blok else: f = f-i
L2:
|
^ Cyklus **//while//** ^^
|
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 pro porovnávání
while:
beq s0, t0, done // Když pow==128, ukončení cyklu while
sll s0, s0, 1 // pow = pow*2
addi s1, s1, 1 // x = x+1
j while
done:
|
^ Cyklus **//for//** ^^
|
int sum = 0;
for(int i=0; i!=10; i++)
{
sum = sum + i;
}
|
//Ekvivalentní k následujícímu cyklu while:
int sum = 0;
int i = 0;
while(i!=10){
sum = sum + i;
i++;
}
|
^ Načtení slova z datové paměti ^^
|
// Jenom pro účely ukázky...
int a, *pa=0x80020040;
int b, *pb=0x80020044;
int c, *pc=0x00001234;
a = *pa;
b = *pb;
c = *pc;
|
// s0=pa (bazova adresa), 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;
|
^ Inkrementování prvků pole ^^
|
int pole[4] = { 7, 2, 3, 5 };
int main()
{
int i,tmp;
for(i=0; i<4; i++)
{
tmp = pole[i];
tmp += 1;
pole[i] = tmp;
}
return 0;
}
| Kompletní program v prostředí MipsIt:
#define s0 $16
#define s1 $17
#define s2 $18
#define s3 $19
.globl pole // nazev "pole" bude globalni (viditelny ze vsech souboru projektu)
.data // direktiva oznacujici zacatek datove casti
.align 2 // zarovnani dat po slovech (4 Bytech)
pole: // pojmenovani mista v pameti
.word 7, 2, 3, 5 // inicializace pole...
.text // zacatek textove casti / programu
.globl start
.ent start
start:
la s0, pole // ulozeni adresy pocatku pole do registru s0 (pseudoinstrukce)
addi s1, $0, 0 // inicializacni prikaz cyklu for: i=0, kde i=s1
addi s2, $0, 4 // nastaveni horni meze cyklu
for:
beq s1, s2, done // kdyz s1==s2 ukonceni cyklu skokem na navesti done
lw s3, 0x0(s0) // nacteni polozky pole do registru s3
addi s3, s3, 0x1 // inkrementace registru s3
sw s3, 0x0(s0) // prepsani (ulozeni) hodnoty registru s3 do pole
addi s0, s0, 0x4 // posun na dasli polozku pole
addi s1, s1, 0x1 // inkrementace pocitadla poctu pruchodu cyklem (i++)
j for // nepodmineny skok na navesti for
done:
nop
.end start
|
\\
===== Odkazy =====
* {{courses:A0B36APO:tutorials:03:mipsit.zip|}} - simulátor MipsIT ke stažení
* [[.:mips-elf-gnu:start|Křížový překladač GNU pro MIPS-ELF]] - překladač kompatibilní s GNU překladačem použitým v MipsIT, balíčky pro Debian GNU/Linux x86_64 a i586, konfigurace a kompilace ze zdrojových kódů
* {{courses:A0B36APO:tutorials:03:gcc-binutils-newlib-mips-elf_4.4.4-1_mingw32.zip|}} - MIPS-ELF GCC 4.4.4 zkompilované pro MinGW32 (Windows) - pro složitější programy vyžaduje přidat přepínače -lm -lgcc -lc , pro pokusy v MipsIT pak nejčastěji i další -nostdlib -nodefaultlibs -nostartfiles -Wl,-Ttext,0x80020000
* [[http://en.wikipedia.org/wiki/MIPS_architecture|Popis procesoru MIPS]] - včetně kompletní instrukční sady.
* [[http://courses.missouristate.edu/KenVollmar/MARS/|MARS (MIPS Assembler and Runtime Simulator)]]
* Missouri State University - Velmi povedený simulátor v jazyce Java
* Vyžaduje assembler bez makro definic (předzpracovaný). Pro předzpracování lze použít např. GCC
''gcc -E assembler.S -o predzpracovany-pro-mips.s''
* [[http://www.linux-mips.org/wiki/Emulators|Emulátory MIPS na Linux-MIPS.org]]