====== 3. Instrukční sada procesoru a přepis algoritmu ====== * pro vyučující: [[..:..:internal:tutorials:03:start|cvičení 3]] ===== Osnova cvičení ===== - základní instrukce procesoru a jejich popis (instrukční sada RISC-V {{ :courses:b35apo:tutorials:03:riscvcard.pdf | riscvcard.pdf}}) - implementace jednoduchých programů v assembleru, přepis programu z jazyka C do assembleru ===== Náplň cvičení ===== Použitý simulátor: [[https://cw.fel.cvut.cz/wiki/courses/b35apo/documentation/qtrvsim/start|QtRvSim]] ==== Základní instrukce - popis a použití ==== ^ Instrukce ^ Syntax ^ Operace ^ Význam ^ | add | add rd, rs1, rs2 | rd ← rs1 + rs2; | Add: Sečte dva registry rs1 + rs2 a výsledek uloží do registru rd | | addi | addi rd, rs1, imm12 | rd ← rs1 + imm12; | Add immediate: Sečte hodnotu v rs1 a znaménkově rozšířenou přímou 12-bitovou hodnotu, a výsledek uloží do rd | | sub | sub rd,rs1,rs2 | rd ← rs1 - rs2 | Subtract: Odečte znaménkově obsah registru rs2 od rs1 a výsledek uloží do rd | | bne | bne rs1, rs2, Label | if rs1 != rs2 go to PC+2*imm12; else go to PC+4 | Branch on not equal: Skáče pokud si registry rs1 a rs2 nejsou rovny (imm12 = Label - PC)| | beq | beq rs1, rs2, Label | if rs1 == rs2 go to PC+2*imm12; else go to PC+4 | Branch on equal: Skáče pokud si registry rs1 a rs2 jsou rovny (imm12 = Label - PC)| | slt | slt rd,rs1,rs2 | rd ← (rs1 < rs2) | Set on less than: Nastavi registr rd, pokud plati podminka rs1 < rs2 | | slli | slli rd,rs1,imm5 | rd ← rs1 << imm5 | Shift Left Logical: Posune hodnotu v registru o C bitu doleva (ekvivalentni k operaci nasobeni konstantou 2C ) | | srli | srli rd,rs1,imm5 | rd ← rs1 >> imm5 | Shift Right Logical: Posune hodnotu v registru o C bitu doprava (ekvivalentni k operaci deleni konstantou 2C ) | | j | j Label | PC ← PC + 2*imm20 | Jump: Skáče bezpodmíněčně na návěstí Label (imm20 = Label - PC)| | lw | lw rd, imm12(rs1) | [rd] ← Mem[[rs1] + imm12]; | Load word: Načte slovo z paměti a uloží jej do registru rd | | sw | sw rs2, imm12(rs1) | Mem[[rs1] + imm12] ← [rs2]; | Store word: Uloží obsah registru rs2 do paměti | | lui | lui rd, imm20 | [rd] ← imm20<<12 | Load upper immediate: Uloží předanou přímou hodnotu do horní části registru. Registr je 32-bitový, hodnota imm20 je 20-bitová. | | li | li rd, Immediate | lui rd, (Immediate+0x800)[31:12]; \\ addi rd,rd, Immediate[11:0] | Load Immediate: 32-bitovou konstantu uloží do registru \$t. Jedná se o pseudoinstrukci, při překladu se rozloží na dílčí instrukce podle potřeby. | | la | la rd, LabelAddr | auipc rd, (LabelAddr - pc + 0x800)[31:12]; \\ addi rd, rd, (LabelAddr - pc)[11:0]; | Load Address: 32-bitové návěstí uloží do registru rd. Jedná se o pseudoinstrukci - tzn. při překladu se rozloží na dílčí instrukce podle potřeby. | ==== Překlad vlastního zdrojového souboru v assembleru ==== Připravíme jednoduchý zdrojový soubor v assembleru s názvem ''simple-lw-sw.S''. Podstatná je přípona velké "''.S''", ta je v standardních vývojových nástrojích vyhrazena pro zdrojový (Source) kód v assembleru a překladač se podle ní rozhoduje, jak bude se souborem nakládat. Další přípony jsou ''.c'' pro zdrojový kód v jazyce C, ''.cc'' nebo ''.cpp'' pro %%C++%%, ''.o'' (object file) pro objektové soubory (soubory kde je již zdrojový kód přeložen do nativních instrukcí procesoru ale ještě bez finálního umístění na adresy), Knihovní soubory ''.a'' (archive) slouží jako knihovny funkcí, které jsou do cílového programu vloženy podle potřeby. Výsledný spustitelný program pak bývá na systémech Unixového typu uložen bez přípony. .globl _start .option norelax .text _start: loop: // load the word from absolute address lw x2, 0x400(x0) // store the word to absolute address sw x2, 0x404(x0) // stop execution wait for debugger/user // ebreak // ensure that continuation does not // interpret random data beq x0, x0, loop nop nop ebreak .data .org 0x400 src_val: .word 0x12345678 dst_val: .word 0 Zdrojový kód v assembleru se sestává ze * zápisu instrukcí, kdy se používají zkrácená jména operací (''lw'' - load word, ''sw'' - save word, ''add'', ''sub'' - subtract ), za identifikátorem operace mohou následovat operandy, to jsou většinou čísla nebo jiné označení registrů a dále přímé číselné hodnoty * návěští (zakončená dvojtečkou), na která se lze při zápisu instrukcí a přímých dat vkládaných do paměti odkazovat. Hodnota vkládaná na místo užití je adresa instrukce nebo datové položky, která za návěštím následuje * řídicí konstrukce (pseudo-instrukce) pro kompilátor assembleru, většinou začínají tečkou ''.'' * komentáře, v zdrojových souborech označených velkým ''.S'' probíhá před vlastním překladem fáze předzpracování se shodnými pravidly jako pro programy v jazyce C V kódu jsou použity následující řídicí příkazy * .globl - následující uvedené symboly jsou viditelné i vně kompilační jednotky. Symbol ''_start'' nebo ''_ _start'' je pak konvencí definovaný jako vstupní bod programu. * .option norelax - zákaz záměny a optimalizace instrukcí během linkování (například dvou instrukcí generovaných li x2, 35 za jednu instrukci addi x2, 35) * .set noat - zákaz používání pomocného registru pro realizaci některých instrukcí sestavovaných navíc assemblerem. Například ''la'' (load address), kdy se jedná o makro, které je assemblerem převedeno na sekvenci instrukcí ''lui'' a ''ori''. * .set noreorder - zákaz úpravy pořadí. Assembler je schopen optimalizovat pořadí některých instrukcí a vyplňovat delay-sloty (pro začátek pro jednoduchost zakázané), pro uvedený kód to není žádoucí * .ent jméno - označení počátku funkce * .end jméno - označení konce funkce * .text - přepnutí na plnění sekce ''.text'', do které jsou ukládané vlastní instrukce programu * .data - přepnutí na plnění sekce ''.data'', do které jsou ukládaná inicializovaná data * .word - požadavek na vložení přímo zapsané hodnoty do obsahu aktuálně plněné sekce Kompletní popis lze nalézt v manuálu [[https://sourceware.org/binutils/docs/as/index.html|GNU assembleru]]. Překlad provedeme vestavěným překladačem v rámci editoru v QtRvSim nebo křížovým překladačem: riscv64-unknown-elf-gcc -Wl,-Ttext,0x200 -Wl,-Tdata,0x400 -march=rv32i -mabi=ilp32 -nostdlib simple-lw-sw.S -o simple-lw-sw Volání obsahuje množství parametrů, protože běžné programy v jazyce C jsou doplněné o inicializační sekvence a knihovní funkce. Účelem našeho výkladu je nejdříve ukázat, jak pracuje úplný základ a poté pochopit, jak může být obalen a rozšířen automaticky pracující inicializace a konstrukce, které umožňují pohodlné psaní programů na vyšší úrovni i ve vyšších jazycích. Volby ''-Wl,'' jsou přidávané sestavovacímu programu (linkeru) a určují, na jaké adresy bude umístěna sekce s instrukcemi ''.text'' a případně i datová sekce ''.data''. Další volby postupně zakazují vložení standardní startovací sekvence (''-nostartfiles'') a automatické použití knihoven. Volba ''-o'' a následující argument určují jméno výstupního souboru (output). Dále následuje jeden nebo více zdrojových souborů. Zdrojový soubor k projektu **simple-lw-sw** a příslušné instrukce pro kompilaci (Makefile) jsou dostupné v adresáři ''/opt/apo/qtrvsim/qtrvsim_template''. Pro provedení programu použijeme simulátor [[..:..:documentation:qtrvsim:start|QtRVSim]]. Volíme nejednodušší variantu procesoru "No pipeline no cache". Do pole "Elf executable" vložíme po vyhledání přes tlačítko "Browse" zkompilovaný soubor ''simple-lw-sw'' (bez přípony). Spuštění simulátoru s větším fontem pro projektor ''QT_SCALE_FACTOR=1.5 qtrvsim_gui'' {{..:qtmips-newdialog-basic.png|}} V zobrazeném diagramu dvojklikem na čítači instrukcí (PC) otevřeme okno s programem. Dvojklikem na bloku zápisníkové paměti (Registers) je otevřený náhled na soubor registrů a nakonec dvojklikem na datech dojde k zobrazení paměti. Doporučené rozložení oken může být následující {{..:qtmips-basic-layout.png}} V okně "Program" navolíme "Follow fetch", kdy je vždy v okně vybraná právě procesorem načtená instrukce/řádka. V okně "Memory" nastavíme adresu 0x400 na kterou byla umístěna data 0x12345678. Program krokujeme příkazem v menu "Machine" -> "Step" nebo z nástrojové lišty příslušným tlačítkem. Hodnota je nejdříve načtena do registru a poté zapsaná do paměti o jednu buňku dále. Nyní upravte program tak, aby prováděl kopírování periodicky. Při úpravách bude potřeba vypustit instrukci ''ebreak'', která slouží k zastavení/přechodu do ladícího stavu. Vyzkoušejte, že modifikovaná hodnota na adrese 0x400 je vždy překopírovaná na adresu 0x404. ==== Další programy v assembleru ==== 1) Modifikujete program tak, aby sečetl dvě hodnoty z adres 0x400 a 0x404 a výsledek uložil na adresu 0x408. 2) Program upravte tak, aby sečetl osm 32-bitových čísel čísel uložených od adresy vect_a. Využijte k nastavení registru na počáteční adresu seznamu čísel makroinstrukce assembleru ''la x3, vect_a'' (load address). .data vect_a: .word 1, 2, 3, 4, 5, 6, 7, 8 prumer: .word 0 vect_b: .word 0, 0, 0, 0, 0, 0, 0, 0 3) Zjistěte, jak se makroinstrukce assembleru ''la x3, vect_a'' přeložila do assembleru RISC-V. 4) Dále upravte program, aby do paměti ''prumer'' uložil dolní celou část z průměru (pro dělení 8 použijte posun o 3 bity doprava ''x >> 3'') 5) Napište program, který zkopíruje osm čísel z adresy ''vect_a'' na adresu ''vect_b''. 6) Napište program, který prohodí číslo z adresy ''vect_a'' a ''vect_a+4'' 7) Upravte program, aby čísla z adresy ''vect_a'' a ''vect_a+4'' prohodil pouze pokud bude číslo z adresy ''vect_a'' menší než číslo z adresy ''vect_a+4''. 8) Napište program, který provede jeden průchod bublinkového třídění čísel z ''vect_a''. ==== Přepis programu 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 slli s0, s0, 1 // pow = pow*2 addi s1, s1, 1 // x = x+1 j while done: | // 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í j podminka // otestuj podminku while: slli s0, s0, 1 // pow = pow*2 addi s1, s1, 1 // x = x+1 podminka: bne s0, t0, while // Když pow!=128, proveď tělo cyklu while done: | ^ Cyklus **//for//** ^^ | int sum = 0; int i; for(i=0; i!=10; i++) { sum = sum + i; } | //Lze nahradit while: int sum = 0; int i = 0; while(i!=10) { sum = sum + i; i++; } | //ale zde i rychlejším do-while, //z konst.mezí víme,že se vždy vykoná: int sum = 0; int i = 0; do { sum = sum + i; i++; } while(i!=10) | ^ Načtení slova z datové paměti ^^ | // Jenom pro účely ukázky... int a, *pa=0x80020040; int b, *pb=0x80020044; int c, *pc=0x00000124; a = *pa; b = *pb; c = *pc; | // s0=pa (bazova adresa), s1=a, s2=b, s3=c lui s0, 0x80020 // pa = 0x80020000; lw s1, 0x40(s0) // a = *pa; lw s2, 0x44(s0) // b = *pb; addi s0, 0, 0x124 // pc = 0x00000124; 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í QtRVSim: .globl pole // nazev "pole" bude viditelny pro linker .text // zacatek textove casti / programu .globl _start // opet symbol viditelný pro linker .ent _start // vstupní bod _start: // la je pseudoinstrukce la s0, pole // ulozi do registru s0 adresu pocatku pole addi s1, zero, 0 // inicializacni prikaz cyklu for: i=0, kde i=s1 addi s2, zero, 4 // nastaveni horni meze cyklu for: // mame konst. meze, lze prelozit jako do-while 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 // +1 k pocitadlu poctu pruchodu cyklem (i++) bne s1, s2, for // kdyz s1!=s2 opakuj cyklus skokem na navesti for konec: ebreak nop .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... | ==== Bubble Sort ==== Ř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. int pole[5]={5,3,4,1,2}; int main(){ int N = 5,i,j,tmp; for(i=0; i **Využití v praxi** 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. === Průběh === 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 RISC-V. Tento program budete potřebovat na příštím cvičení - to co nestihnete na cvičeních bude nutno dodělat doma.. === Soubor buble_sort.S === // Directives to make interresting windows visible #pragma qtrvsim show registers #pragma qtrvsim show memory .globl _start .globl array_size .globl array_start .option norelax .text _start: la a0, array_start la a1, array_size lw a1, 0(a1) // number of elements in the array //Insert your code there //Final infinite loop end_loop: ebreak // stop the simulator j end_loop nop .data // .align 2 // not supported by QtRVSim yet array_size: .word 15 array_start: .word 5, 3, 4, 1, 15, 8, 9, 2, 10, 6, 11, 1, 6, 9, 12 // Specify location to show in memory window #pragma qtrvsim focus memory array_start ===== Úkoly ===== - Seznámení se simulátorem a vývojovým řetězcem (toolchain) - Rozšíření jednoduchého programu na sčítání čísel - Práce s vektorem - Implementace výpočtu n-tého členu Fibonacciho řady - Začátek práce na programu bubble-sort - [[courses:b35apo:tutorials:03:qtrvsim-c|Opakování: Překlad z C pro simulátor QtRvSim]] - [[courses:b35apo:tutorials:03:periferie|Bonus: Periferie mapované do paměťového adresního prostoru]] - Výpis řetězce na terminál - Doplnění programu pro výpočet Fibonacciho posloupnosti o výstup na terminál - [[courses:b35apo:tutorials:03:makefile|Bonus: Makefile vol. 2: použití pro řízení překladu]] **Co bych si měl na příští cvičení zopakovat/připravit** - Zopakovat si jak pracuje cache - Zopakovat si co znamená * plně asociativní cache * cache s omezeným stupněm asociativity * přímo mapovaná cache - Zopakovat si význam pojmů write-through a write-back. - Dokončit program pro Bubble sort z minulého cvičení. ===== Užitečné odkazy ===== * Souhrnný popis instrukcí {{ :courses:b35apo:tutorials:03:riscvcard.pdf | riscvcard.pdf}} * Popis RISC-V architektury na Wikipedii [[https://en.wikipedia.org/wiki/RISC-V]]. * Autoritativní popis architektury [[https://riscv.org/technical/specifications]] * [[https://github.com/riscv/riscv-isa-manual/releases/download/Ratified-IMAFDQC/riscv-spec-20191213.pdf|The RISC-V Instruction Set Manual, Volume I: Unprivileged ISA, Version 20191213]]