Fibonacci (15p)¶
Syksyllä 2023 y86-assemblykielen harjoitustyö on ohjelma, joka tarkistaa annetusta lukujonosta ovatko kaikki luvut Fibonaccin lukuja. Fibonaccin lukujonolle on paljon käyttötapauksia kaikkialla luonnossa, taiteessa ja tekniikassa yleisesti. Meitä tietysti kurssila kiinnostaa lukujonon käyttö tietotekniikassa ja käyttötapauksia onkin esimerkiksi tehokkaiden hakualgoritmien toteutuksessa ja nopeuttamassa moninaisia muita algoritmejä.
Esimerkkejä työssä tarkoitettavista Fibonaccin lukujonoista.
1,1,2,3,5,8,13,21,34,55 233,377,610,987,1597,2584 1346269,2178309,3524578,5702887,9227465,14930352,24157817 160500643816367088,259695496911122585,420196140727489673,679891637638612258
Työssä vaadittava kaava, jolla tarkistetaan onko luku Fibonaccin luku, on varsin yksinkertainen. Alla esimerkkinä C-kielinen toteutus.
bool isPerfectSquare(int x) {
int s = sqrt(x);
return (s*s == x);
}
// Returns true if n is a Fibonacci Number, else false
bool isFibonacci(int x) {
return isPerfectSquare(5*x*x + 4) || isPerfectSquare(5*x*x - 4);
}
Huomataan, että työssä tarvitaan tehokas algoritmi laskemaan kertolaskuja ja neliöjuuria, jotka tietysti löytyvät harjoitustehtävistä..
Hox!!! Fibonaccin lukujen laskemiseen on myös olemassa ns. helppo ratkaisu kun asiaa hetken miettii tai googlailee, mutta sitä ei kurssisuorituksena hyväksytä. Haluttu algoritminen ratkaisu on yleinen ja tarpeeksi isoja lukuja käytettäessä selvästi tehokkaampi kuin brute force..
Vaatimukset¶
Työssä tulee toteuttaa Fibonacci-tarkistin, joka tarkistaa muistissa olevasta lukujonosta, että ovathan kaikki siinä olevan luvut Fibonacci-lukuja.
- Työssä ei tarvitse tarkistaa, että onko koko lukujono Fibonaccin sarja. Ts. lukujen välistä suhdetta ei tarvitse tarkistaa.
- Harjoitustyön toteutuksen on perustuttava ylläesitettyyn algoritmiin, muita ratkaisuja ei hyväksytä. Muista ratkaisuista mitä esim. netistä löytyy, voi kyllä keskustella harjoitustyön pohdintaosiossa esimerkiksi vertailemalla omaan toteutukseen.
- y86-suorittimen arkkitehtuuri on 64-bittinen, mutta suurin luku jota ohjelmassa tarvitsee käsitellä on 1000, eli koko lukualue ei ole käytössä.
- Valmista assemblykoodia yo. algoritmin toteuttamiseen saa harjoitustehtävävastauksista..
Ohjelmassa tulisi olla seuraavat ominaisuudet:
- Ohjelmaa alkaa
main:
-lohkosta eikä sitä ennen ole mitään alustuksia. - Ohjelma lukee tarkistettavan lukujonon alkaen muistipaikasta 0x700.
- Lukujono alkaa aina vähintään 1:sestä, eli nollaa ei alussa ole.
- Lukujono päättyy aina nollaan.
- Ohjelman suoritus pysähtyy ensimmäiseen lukuun, joka ei ole Fibonaccin luku. Tämä luku palautetaan ohjelman lopuksi
%rax
rekisterissä. - Jos kaikki luvut ovat Fibonacin lukuja, palautetaan
%rax
-rekisterissä luku 0. - Tavoitteena on, että ohjelman suoritukseen annetuilla testitapauksilla menisi noin
20-30.000
konekielen käskyä. Tämä ei ole ehdoton vaatimus, katso ohjeet alla.
Ohjelman alustus voisi olla esimerkiksi seuraava:
# Alussa kirjoitetaan lukujono 3,5,8 muistiin
# Hox! Lovelacen tarkistin tekee tämän automaattisesti
.pos 0
irmovq array,%r11 # muistipaikka 0x700
irmovq $3,%r12 # 3
rmmovq %r12,(%r11)
irmovq $5,%r12 # 5
rmmovq %r12,8(%r11)
irmovq $8,%r12 # 8
rmmovq %r12,16(%r11)
irmovq $0,%r12 # loppunolla
rmmovq %r12,24(%r11)
# Tästä alkaa palautettava koodi
main:
# Oma koodi
# ...
.pos 0x700
array:
Ohjeita työhön¶
- Harjoitustyön toteutus tehdään itsenäisesti.
- Työstä saa toki keskustella muiden kanssa, mutta oma koodi on kirjoitettava itse.
- Harjoitustyön voi palauttaa puutteellisena.
- Bugeja saa olla, eikä työn tarvitse mennä täysin tarkistimesta läpi.
- Jotta työ hyväksytään, palautetusta koodista tulee näkyä että työtä on oikeasti yritetty tehdä ja se toimii ainakin osittain. Alkutekijöissään olevaa koodia ei tule palauttaa.
- Työn tarkistuksessa katsotaan toteutuksen puutteet ja vähennetään harjoitustyöpisteitä niiden mukaan.
- Palautettavan assembly-kielisen ohjelman tulee olla hyvin kommentoitu.
- Plagiointia koskevat samat säännöt kuin Johdatus-kurssin harjoitustyötä.
- Koodin kommenteissa listatkaa muut, joiden kanssa olette keskustelleet tehtävästä, ettei tule plagiointiepäilyksiä samankaltaisten ratkaisujen johdosta.
- Toisen opiskelijan koodia ei saa palauttaa omanaan.
Työn toteutus¶
Työhän on suoraviivainen toteuttaa uudelleenkäyttämällä omaa koodia harjoitustehtävävastauksista. Tällöin tosin ohjelma voi olla varsin tehoton, koska kerto-, jako- ja neliöjuurilaskuissa isoilla luvuilla käskyjen määrä nopeasti kasvaa. Joten tässä voisi olla miettimisen paikka, saako koodia jotenkin optimoitua..
Erinomainen idea voisi olla toteuttaa työstä ensin toimiva versio, jossa ei välitetä ohjelman ajonaikaisten käskyjen määrästä. Kun tämä versio toimii, vasta sen jälkeen lähteä miettimään optimoimista.
Käskyjen määrää voi joko arvioida käymällä läpi koodia ja laskemalla itse suoritusaikainen käskyjen määrä. (Hox! silmukat ja ehtolauseet).
- Koodia voi myös ajaa simulaattori-ohjelmalla, joka kertoo täsmälleen montako käskyä suoritukseen meni. Ohjeet simulaattorin asennukseen kotiin assembly-harjoitustehtävissä / kurssin virtuaalikoneen voi kopioida itselle työasemilta.
- Verkosta löytyy useita y86-simulaattoreita, joista esimerkiksi tämä 32-bittinen y86-simulaattori, joka myös kertoo täsmällisen käskyjen määrän. Koodin ajamiseksi tässä simulaattorissa tosin pitää käskyjen q-pääte muuttaa l-päätteeksi. Esim
irmovq
->irmovl
.
Työn pohdinta-osuudessa mieti miten ohjelmaa voisi saada tehokkaamaksi. Esimerkiksi:
- Raportoi / arvioi ohjelman ajonaikaisten käskyjen määrä. Arvio on perusteltava.
- Jos ohjelman suoritukseen menee testitapauksilla yli 30.000 käskyä, pohdiskele asiaa. Käskyjen määrä ei muuten vaikuta harjoitustyöstä saataviin pisteisiin.
- Löytyikö toteutuksestasi joku selkeä pullonkaula?
- Kuinka paljon Peasant multiplication auttaa vai auttaako? Esim käskyjen määrissä..
- Miten jakolaskua voisi optimoida, auttaisiko jakojäännöksen hyödyntäminen?
- Bittisiirtoon MSB:tä kohti (=vasemmalle) löytyy elegantti yhden käskyn ratkaisu..
- Voiko silmukoita / aliohjelmien suoritusta optimoida?
- Millä perusteella lähdit optimoimaan ja mikä oli sen vaikutus (esim. käskymäärissä)?
- jne..
Työn pisteytys¶
Työstä voi saada yhteensä max
15 pistettä
. Joka jakautuu seuraavasti:- Toimiva y86-assemblykielinen ohjelma, joka toteuttaa speksit:
0-9 pistettä
- Työstä hyväksytään versio, joka ylittää 100.000 käskyä suorituksessa ja ohjelmassa saa olla bugeja. Käskyjen määrä vaikutaa pisteisiin. Pohdintaosuudessa kannattaa antaa vaihtoehtoja koon pienentämiseksi.
- Palautetusta koodista on nähtävä, että ratkaisua on oikeasti yritetty.
- Löydetyistä bugeista vähennetään
1-2 pistettä
vakavuuden mukaan - Esimerkiksi onko kyseessä pieni laskuvirhe jossain testitapauksessa vai pysähtyykö ohjelman toiminta kokonaan. Myös katsotaan että onko ohjelman toteutus muutoin toimiva.
- Henkilökunta käy palautetut koodit käsin läpi, tarkistaa bugit ja laskee pisteet.
- Hyvin kommentoitu ja luettava assembly-koodi. Code is well structured with call to subroutines and consistent use of registers:
0 / 3 pistettä
- Pohdinta omasta toteutuksesta:
0-3 pistettä
- Vastaa vaikkapa ylläoleviin kysymyksiin. Ohjelman ajonaikaisten käskyjen määrä / arvio siitä on oltava.
- Pelkkä pohdinta ei tietenkään riitä hyväksyttyyn suoritukseen!
- Pituus 10-15 riviä kooditiedoston kommenteissa. Esimerkki:
# TKJ-harjoitustyö 2021 Fibonacci # Olli Opiskelija, opiskelijanro, sähköposti # # Pohdinta: # - Ajonaikaisten käskyjen määrä: xxxx # - Optimoinnin tein tavalla x.. # - ... # Tästä alkaa koodi main:
Ohjeita Assembly-koodaamiseen¶
Assembly-kielellä koodaaminen on astetta vaativampaa kuin korkean tason kielillä, joten muutama yleisohje on paikallaan:
- Suunnittele ohjelma aluksi, ihan kuten tekisit ohjelmaa korkean tason kielellä.
- try and error-tapa koodata assembly-kielellä ei enää yksinkertaisesti toimi monimutkaisemmissa ohjelmissa..
- Rakenteellisen ohjelmoinnin-materiaalista on tässäkin hyötyä. Jaa ohjelma toiminnallisuuden mukaan osiksi, jotka voit toteuttaa erikseen aliohjelmina ja lopuksi yhdistää ne toimivaksi ohjelmaksi.
- Mitä aliohjelmia tarvitaan? Miten ne sijoitetaan muistissa hyppykäskyjen / ehtolauseiden minimoiseksi? Miten niiden parametrit välitetään?
- Onko tässä harjoitustehtävien koodista apua?
- Rekistereille kannattaa valita johdonmukaisesti käyttötarkoitus etukäteen (eikä siitä pidä poiketa).
- Tietyt rekisterit ovat vain globaaleille muuttujille.
- Tietyt rekisterit ovat vain apumuuttujille.
- Tietyt rekisterit ovat vain aliohjelmakutsujen parametreille (tarvitseeko käyttää pinoa?)
- Pinon käytöstä:
- Pinohan kasvaa muistissa alaspäin, joten varmista ettei pino mene koodin päälle..
- Pinossa saa olla ylimääräistä tavaraa ohjelman loputtua, kunhan pinon pohjalla/alimpana/muistissa ylimpänä on aina vaadittu lopputulos.
- Omaa algoritmiä voi laskea paperilla tai toteuttaa C-kielellä, ja selvittää siitä mitä välituloksia assembly-koodin pitäisi saada.
- C-kielen koodissa voi vaikka nimetä muuttujat rekisterien mukaan
- Omaa koodia kannattaa (lue: pitää) testata simulaattorissa.
- Aliohjelmien testaus erillisinä pieninä ohjelmina.
- Ehtolauseet samoin ohjelmina. Testaa kaikilla erityyppisillä tuloksen arvoilla
<0, ==0, >0
. - Hyppykäskyissä riittää usein pelkästään
ZF
-tilabitin tarkastelu, siis onko operaation tulos nolla tai erisuuri kuin nolla. - Jos ohjelman suoritukseen menee enemmäin kuin 10.000 käskyä, komentorivisimulaattorissa maksimikäskyjen määrää voi siirtää lipulla.
- Esimerkiksi kun simulaattorin käynnistää käskyllä
ssim fibonacci.yo -l 50000
, on käytössä 50.000 ohjelmakäskyä. - Koodin tulee olla erittäin hyvin kommentoitua.
- Tätä voi itse testata unohtamalla koodin muutamaksi päiväksi ja palaamalla siihen sitten..
- Omaa ohjelmaa voi kätevästi debugata / testata kviljelemällä
halt
-käskyä koodissa sopivissa paikoissa ja sen jälkeen tarkistamalla että suoritus siihen asti / välitulos meni oikein. Esimerkiksi kun saa jonkun osan algoritmistä tehtyä, voi ohjelman suorituksen pysäyttää siinä kohti halt-käskyllä ja tarkastella simulaattorissa miltä rekisterit ja muisti näyttää. - Harjoituksista / Discord-chatista kannattaa tarvittaessa ehdottomasti kysellä apuja. Henkilökunta on palkattu teitä auttamaan.
Työn palautus¶
Harjoitustyölle takaraja on 18. Joulukuuta 2023.
Huom! Tarkistimessa on assemblykoodille 100.000 käskyn suoritusraja, mutta sitä ei ole pakko alittaa, jotta työ hyväksytään (kuten yllä kerrottiin). Tarkistimen lisäksi työt käydään myös käsin läpi opettajien toimesta.
Kurssiarvosana¶
Seuraava koskee tätä 3op:n osuutta.
- Harjoitustehtävistä saa max 25p
- Harjoitustyöstä saa max 15p
- Hyväksyttyyn kurssisuoritukseen pisteitä vaaditaan 50% harjoitustehtävien ja harjoitustyön yhteenlasketusta maksimista eli 21 / 40p
- Hyväksyttyjä suorituksia tulee olla molemmista: sekä harjoitustehtäviä että harjoitustyö.
Koko kurssin Tietokonejärjestelmät (8op) arvosana tulee kurssien Lovelace-etusivulla kerrotun mukaisesti.