Dnes si vezmime taku jednoduchu ulohu. Dajme tomu, ze na zaciatku mame v spodnych troch bitoch registra A cislo N od 0 do 7. Ulohou je vymysliet rutinku, ktora na vystupe vrati v registri A N-tu mocninu dvojky. Napriklad pre A=3 vrati 2^3=8.
Podme si to rozobrat. Umocnit nejake cislo na N-tu znamena N-krat toto cislo medzi sebou vynasobit. Teda nas priklad bude 2^3=2*2*2. Hned sa nam tu ako prve riesenie automaticky ponuka nejaka slucka, ktora by sa vykonavala N-krat a vyuzivala by nasobenie ktore sme si preberali kedysi davno v stvrtej lekcii. Skuste si v ramci takej malej rozcvicky sami napisat takuto rutinku. Nezabudnite osetrit aj pripad ked je N nulove.
Ale skusme vymysliet nieco efektivnejsie. Nasobenie X*Y je vlastne to iste ako keby sme X-krat scitali medzi sebou Y. Cize napriklad 4*5 = 5+5+5+5. Pametate sa na to este z vyssie spominanej stvrtej lekcie ? Teraz vsak mame vyhodu, lebo vieme presne ze budeme nasobit dvomi. A uz velmi dobre vieme, ze nasobit dane cislo dvomi znamena pripocitat k danemu cislu to iste cislo. Ak mame dane cislo v registri A, potom to mozeme spravit instrukciou add a,a. A prichadzame k zaveru, ze N-krat nasobit dvomi je to iste, ako N-krat vykonat instrukciu add a,a.
Tymto sposobom pracuje nasa dnesna prva rutinka. Obsahuje slucku, ktora sa vykona N-krat a ktorej telo obsahuje instrukciu add a,a. Idealna instrukcia pre ukoncenie slucky je djnz, pretoze staci do registra B vlozit N a tato instrukcia nam uz sama zabezpeci aby sa slucka vykonala N-krat. Avsak je tu maly zadrhel alebo hacik - pre N=0 sa vykona slucka 256 krat, a to nechceme. Preto pripad N=0 osetrime zvlast. Nasa rutinka bude vyzerat takto:
| rut1 | and | %00000111 | Vymaskovanie nepotrebnych bitov |
| ld | b,a | Register B bude pocitadlo rotacii | |
| ld | a,#01 | Inicializacna hodnota registra A | |
| ret | z | Ak bola na zaciatku v A nula, nastane navrat | |
| aaa | add | a,a | Vynasobenie medzivysledku dvomi |
| djnz | aaa | Vynasobenie sa vykona potrebny pocet krat | |
| ret | Ked je vsetko hotove, urobime navrat. |
Rutinka je dlha 10 bajtov, a ked by ste spocitali cas trvania pre krajne pripady, vyjde vam 28 taktov pre N=0 a 147 taktov pre N=7. Priemerna doba trvania rutinky je (28+147)/2 = 87 a pol taktu. Urcitou nevyhodou tejto rutinky je to, ze pouziva register B, takze ak mame v B odlozene nejake dolezite udaje, je treba urobit pred volanim rutinky PUSH BC a po nom POP BC, pripadne sa postarat o odlozenie udaja v B do bezpecia inym sposobom.
Nedala by sa tato rutinka nejak zrychlit ? Jednym z casto pouzivanych sposobov zrychlenia rutinky je tzv. rozvinutie slucky. Je to to iste, ako keby sme telo slucky napisali za sebou tolko krat, kolko krat sa ma slucka vykonat. Co tym ziskame ? Vsimnite si, kolko taktov trva vykonanie instrukcie add a,a. 4 takty. A teraz kolko trva djnz. Ak je B nenulove, tak 13 taktov. Jeden prechod sluckou potom dohromady trva 17 taktov, z coho len 4 sa robi pre nas naozaj uzitocna cinnost. Ak by sme vykonavali len samotne add a,a, usetrime az 76% casu procesora! Nestalo by za to sa o to pokusit ?
Lenze mame tu mensi problem. Nevieme kolkokrat sa slucka vykona. Maximalne sa ale moze vykonat 7-krat, lebo N moze byt maximalne 7. Potrebujeme preto za sebou napisanych 7 instrukcii add a,a. A ak bude N mensie, tak potrebny pocet instrukcii jednoducho preskocime. Ten potrebny pocet bude samozrejme 7-N.
| rut2 | cpl | Invertovanie bitov v registri A | |
| and | #07 | Vymaskovanie nepotrebnych bitov | |
| ld | c,a | Vysledok ulozime do registra C | |
| ld | b,#00 | Parovy register BC obsahuje hodnotu 7-N | |
| ld | a,#01 | Inicializacna hodnota registra A | |
| ld | hl,bbb | Do HL vlozime adresu zaciatku postupnosti | |
| add | hl,bc | a pripocitame k nej BC cim ziskame | |
| jp | (hl) | adresu na ktoru napokon skocime. | |
| bbb | add | a,a | |
| add | a,a | Postupnost siedmych instrukcii add a,a | |
| add | a,a | Kolko z nich sa vykona, | |
| add | a,a | zavisi od toho, | |
| add | a,a | do ktoreho miesta | |
| add | a,a | tejto postupnosti sa skoci. | |
| add | a,a | ||
| ret |
Rutinka zabera v pameti sice az 22 bajtov a pre N=0 trva 64 taktov, avsak pre N=7 trva len 92 taktov, co znamena ze rutinka priemerne trva 78 taktov, co je voci predchadzajucemu pripadu uspora priblizne 11%. Ale kde je tych slubovanych 76% ??? Treba si uvedomit, ze pomerne vela casu zabral vypocet adresy, kam do postupnosti instrukcii add a,a musime skocit.
Instrukcie cpl a and #07 na zaciatku rutinky zariadia, aby v registri A bolo cislo 7-N. Skuste si do A napriklad vlozit hodnotu 4 (binarne 00000100), potom po vykonani cpl bude v A hodnota 11111011 a po vykonani and #07 bude A obsahovat bity 00000011, co je vlastne 3 a tiez aj 7-4.
Instrukcia add a,a je dlha prave jeden bajt, preto ak vezmeme ze bbb je adresa zaciatku postupnosti tychto instrukcii, potom treba skocit prave na adresu bbb+7-N aby sme vykonali N tychto instrukcii. Scitanie bbb + A, kde A = 7-N, sa vykonava instrukciou add hl,bc; pricom sa predtym do registra BC vlozi hodnota 7-N.
Ak citate pozorne, uz urcite presne viete, aku urcitu nevyhodu ma tato rutinka. A ak to presne neviete, skuste si tuto lekciu este raz precitat a prist na to.
V tejto lekcii sme si ukazali jeden zo sposobom, ako mozno zrychlit vykonavanie programu, ktory obsahuje slucky. Dosiahli sme zrychlenie sice len 11%, ale vo vseobecnosti plati, ze cim viackrat sa ma slucka vykonat, tym vyssia je uspora casu. Je to dane skutocnostou, ze zaciatocny vypocet skoku do rozvinutej slucky trva vzdy rovnako dlho a preto pri dlhsom vykonavani rozvinuteho tela skucky (t.j. pri vecsom pocte prechodov povodnou sluckou) sa podiela na celkovom case mensou mierou a celkova casova uspora je vyssia.
Rozvinutie slucky ma vsak jednu velku nevyhodu - je narocne na pamet. V nasom pripade nebude ta spotreba pameti az taka velka, ale vezmime si napriklad ze telo nejakej slucky ma 4 bajty a chceme ho vykonat az 2000 krat. Potom rozvinutie slucky bude zaberat celych 8000 bajtov, co uz nie je zrovna malickost.
V buducej lekcii si ukazeme metodu, ako mozno riesit nas problem ovela elegantnejsie a bez prilis velkej spotreby pameti.
Vas Busy.