Denne oppgaven beskriver hvilke algoritmer og metoder som kan benyttes til å utføre regneoperasjonen multiplikativ divisjon i maskinvare. Videre beskrives arkitekturen til de mest egnete metodene for å beregne divisorens resiprokal. Dette resiprokalet multipliseres så med dividenden for å produsere en kvotient. Av de grunnleggende aritmetiske operasjonene addisjon, subtraksjon og multiplikasjon, er divisjon den som er mest krevende å utføre. Kongsberg Defence & Aerospace har gidd denne oppgaven med å undersøke mulighetene for å realisere en divisjonsmodul på en FPGA. Divisjonsmodulen skal være pipelinet, operere med 16 og 32 bits operander og basert på algoritmer for multiplikativ divisjon. Det ble valgt å benytte Newton-Raphson-algoritmen for å iterere over en approksimert verdi av divisorens resiprokal. Denne approksimasjonsverdien hentes fra en bipartit oppslagstabell som adresseres med divisoren. Resiprokalene som er lagret i oppslagstabellen har en nøyaktighet på 1 ULP og Newton-Raphson-algoritmen dobler antall riktige bit for hver iterasjon. Dermed er det kun nødvendig med en iterasjon for å beregne en korrekt verdi av resiprokalet. Selve den iterative regneoperasjonen består av to sekvensielle multiplikasjoner og en subtraksjon. Arkitekturmessig er arbeidet med divisjonsprosessen fordelt på ulike hovedblokker som er sekvensielt sammenkoblet og som hver utfører sin del av prosessen. For hver blokk i de spesifiserte løsningene i denne rapporten, kommer divisjonsoperasjonen et steg nærmere en kvotient og en rest. Det ble ikke tid til å implementere de spesifiserte løsningene i VHDL så det er ikke utarbeidet noen synteserapport for løsningene. Det burde imidlertid være relativt ukomplisert å utføre implementeringen basert på arkitekturene som er spesifisert i denne rapporten. Ut i fra teoristudiet med egnete algoritmer og metoder, ble de metodene som virket best med tanke på ytelse benyttet til å spesifisere løsninger for 16 og 32 bits operander. Løsningene er like med unntak av den bipartite oppslagstabellen som får plass i RAM på FPGA for 16 bits operander, men blir så stor at den må legges i ekstern RAM for 32 bits operander. Ytelsesmessig er det ingen forskjeller på disse to løsningene, men realiseringen av løsningen for 32 bits operander er litt mer komplekst.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:ntnu-10470 |
| Date | January 2008 |
| Creators | Stafto, Karl Marius |
| Publisher | Norges teknisk-naturvitenskapelige universitet, Institutt for elektronikk og telekommunikasjon, Institutt for elektronikk og telekommunikasjon |
| Source Sets | DiVA Archive at Upsalla University |
| Language | Norwegian |
| Detected Language | Norwegian |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0023 seconds