3. Instrukční sada procesoru a přepis algoritmu

Osnova cvičení

  1. základní instrukce procesoru a jejich popis (instrukční sada RISC-V riscvcard.pdf)
  2. implementace jednoduchých programů v assembleru, přepis programu z jazyka C do assembleru

Náplň cvičení

Použitý simulátor: 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 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 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

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í

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<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;
}

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

  1. Seznámení se simulátorem a vývojovým řetězcem (toolchain)
  2. Rozšíření jednoduchého programu na sčítání čísel
  3. Práce s vektorem
  4. Implementace výpočtu n-tého členu Fibonacciho řady
  5. Začátek práce na programu bubble-sort
    1. Výpis řetězce na terminál
    2. Doplnění programu pro výpočet Fibonacciho posloupnosti o výstup na terminál
Co bych si měl na příští cvičení zopakovat/připravit
  1. Zopakovat si jak pracuje cache
  2. Zopakovat si co znamená
    • plně asociativní cache
    • cache s omezeným stupněm asociativity
    • přímo mapovaná cache
  3. Zopakovat si význam pojmů write-through a write-back.
  4. Dokončit program pro Bubble sort z minulého cvičení.

Užitečné odkazy

courses/b35apo/tutorials/03/start.txt · Last modified: 2024/03/07 12:45 by lencmich