Binääristen kertojien arkkitehtuurit ja suorituskyky

(1)

Henrik Kaakkolammi

BINÄÄRISTEN KERTOJIEN ARKKITEHTUURIT JA SUORITUSKYKY

Kandidaatintyö

Informaatioteknologian ja viestinnän tiedekunta

Tarkastaja: Matti Haavisto

Huhtikuu 2021

(2)

Henrik Kaakkolammi: Binääristen kertojien arkkitehtuurit ja suorituskyky Kandidaatintyö

Tampereen yliopisto

Tietotekniikan tutkinto-ohjelma Huhtikuu 2021

Tässä työssä tutkitaan erilaisia vaihtoehtoja toteuttaa kertolasku prosessorissa. Laskenta tapahtuu prosessorin ALU-yksikössä, jonka tehokas toiminta on hyvin tärkeää koko prosessorin suorituskyvyn kannalta. Yhteen- ja vähennyslaskua voidaan pitää triviaaleina operaatioina, mutta kertoja jakolasku eivät ole yksinkertaisia tehtäviä. Kertolaskun optimointi muodostaa mielenkiintoisen tutkimusongelman. Työssä on tavoitteena löytää hyvä ratkaisu laskennan nopeuden, käytetyn pinta-alan ja virrankulutuksen kannalta. Ratkaisujen testaamisessa käytetään uudelleen ohjelmoitavaa FPGA-mikropiiriä.

Työ jakautuu kahteen osaan. Teoriaosuudessa aluksi luodaan katsaus, kuinka prosessorit käsittelevät lukuja ja miten binääriluvut ilmaistaan. Seuraavaksi kertolaskulle tarkastellaan yksinkertaisia tapoja, jotka perustuvat käsin laskemisesta tuttuun allekkain laskuun. Tästä edetään monimutkaisempiin tapoihin suorittaa kertolasku, millä vältetään kertolaskun iteratiivinen luonne. Iteratiivisesta rakenteesta eroon pääsemiseksi tarkastellaan rinnakkaista laskentaa ja sen optimointia.

Työn toisessa puolessa käydään läpi, kuinka kertojien mittaus suoritetaan. Työssä osa kertojista on ohjelmoitu työtä varten VHDL-laitteistokuvauskielellä ja osalle kertojista on käytetty avoimen lähdekoodin toteutuksia GitHubista. Luvussa 4 käydään läpi käytettävät ohjelmistot, FPGA:n ohjelmointi ja kuinka suorituskykymittaukset suoritetaan. Kertojien testaaminen ei ole yksinkertaista ja kertojien ympärille rakennettava testipenkki vaatii huolellista suunnittelua.

Suorituskykymittausten lopputuloksena havaittiin, että rinnakkaisen laskennan edut ovat kiistattomat kaikilta osin. Työhön lähdettiin ajatuksella verrata tuloksia kaupallisiin sovelluksiin, mutta valitettavasti kaupallisten prosessorien arkkitehtuurit eivät ole julkista tietoa.

Avainsanat: prosessori, ALU, kertolasku, suorituskyky, FPGA

Tämän julkaisun alkuperäisyys on tarkastettu Turnitin OriginalityCheck –ohjelmalla.

(3)

1. JOHDANTO ... 1

2.TAUSTA... 2

2.1 Lukujärjestelmät ... 2

2.2 Lukujärjestelmien rajoitteet ja lukujen leveys ... 4

3. KERTOJIEN ARKKITEHTUURIT ... 5

3.1 Allekkain kertominen ... 5

3.2 Boothin algoritmi ... 7

3.3 Wallace-puut ja Daddan algoritmi ... 8

4.METODOLOGIA ... 13

4.1 Laitteistokuvauskieli VHDL ... 13

4.2 Laite ja ohjelmistot ... 13

4.3 Vertailtavat kertojat ... 15

4.4 Testipenkki ... 16

4.5 Mitattavat ominaisuudet ... 17

5.SUORITUSKYKYMITTAUKSET ... 19

5.1 Suurin kellotaajuus ... 19

5.2 Pinta-ala ... 22

5.3 Tehonkulutus ... 25

6.YHTEENVETO ... 27

LÄHTEET ... 28

LIITE 1: SUMMAIN-KERTOJA ... 29

LIITE 2: SUMMAINPUU ... 31

LIITE 3: TESTIPENKKI ... 34

(4)

FPGA Field-programmable gate array, mikropiiri, joka voidaan ohjelmoida uudestaan. FPGA koostuu tyypillisesti toistuvista yksiköistä, jotka sisältävät hakutauluja ja muutamia loogisia yksiköitä, mitä ohjelmoimalla ja kytkemällä yhteen saadaan haluttu toiminta.

ALU Arithmetic Logic Unit, aritmeettis-looginen laskuyksikkö, joka suorittaa sekä aritmeettisia laskutoimituksia ja myös bittioperaatioita.

MSB Most significant bit, merkitsevin bitti eli binääriluvun vasemmanpuolimmaisin bitti. Desimaaliluvuksi muutettuna sen arvo on suurin.

LSB Least significant bit, vähiten merkitsevä bitti. Binääriluvun oikeanpuolimmaisin bitti, jonka lukuarvo on pienin.

WNS Worst negative slack, ei vakiintunutta suomennosta. Tarkoittaa käytännössä kuinka pitkä aika logiikkaelementeillä on vähimmillään ollut ylimääräistä aikaa asettua lopulliseen arvoonsa.

(5)

1. JOHDANTO

Tietokoneen tärkein osa on prosessori, joka on vastuussa tietokoneen eri osien ohjaamisesta ja yhteensovittamisesta. Prosessorin tehtävä yksinkertaistetusti on suorittaa sille annettuja käskyjä. Suurin osa käskyistä on prosessorin sisällä vain aritmeettisia operaatioita, siis muun muassa yhteen- ja vähennyslaskuja sekä kertoja jakolaskuja. Prosessorin tehokas toiminta vaatii sen, että laskutoimitukset pystytään suorittamaan nopeasti ja energiatehokkaasti. Prosessori sisältää aritmeettis-loogisen ALU-yksikön (en. arithemetic-logic unit), joka suorittaa muun muassa mainitut laskutoimitukset.

Yhteen- ja vähennyslasku ovat prosessorille yksinkertaisia operaatiota, mutta kertolasku on huomattavasti monimutkaisempi operaatio ja jakolasku vielä sitäkin vaikeampi operaatio. Prosessorin logiikkaa ja algoritmeja kehitettiin jo kauan ennen kuin prosessoreita pystyttiin valmistamaan. Muun muassa tässä työssä myöhemmin käsiteltävä Boothin kertolaskualgoritmi [1] kehitettiin jo vuonna 1950. Vertailun vuoksi ensimmäinen kaupallinen prosessori, Intel 4004, tuli myyntiin vasta vuonna 1971 [2], yli kaksikymmentä vuotta myöhemmin. Erilaisia algoritmeja aritmeettisiin operaatioihin löytyy lukemattomia määriä ja jokaiseen tehtävään yhtä kaikilta ominaisuuksilta parasta on mahdoton löytää. Kaikki prosessorit eivät ole samanlaisia, ja eri käyttötarkoitukset vaativat erilaisia ominaisuuksia. Joskus tavoitteena on vain maksimaalinen suorituskyky, kun taas joskus matala energiankulutus on tärkeämpää.

Tässä työssä tarkastellaan erilaisia vaihtoehtoja kertojien toteuttamiseen prosessoreissa. Ensimmäisenä tarkastellaan kuinka tietokoneet käsittelevät lukuja ja minkälaisia rajoituksia ja vaatimuksia se aiheuttaa kertojille. Kolmannessa luvussa käydään läpi työssä mitattavien kertojien rakenteet. Täysin tarkka kertojien toiminta porttitasolla ei ole tässä työssä olennaista ja monimutkaisemmat kertojat käydään läpi pintapuolisesti. Neljännessä luvussa perehdytään kertojien käytännön toteutukseen, laitteistoon, ohjelmistoon ja ohjelmoitaviin arkkitehtuureihin. Lisäksi käydään läpi, mitä kertojista mitataan ja kuinka mittaukset tehdään.

(6)

2. TAUSTA

Tässä työssä keskitytään pelkästään kokonaisluvuilla laskemiseen. Murtoluvut ja desimaaliluvut vaativat liukulukujen (en. floating point number) käyttöä, joilla operoiminen on monimutkaisempaa paitsi algoritmien kannalta, että myös käytännössä kaupallisissa prosessoreissakin.

2.1 Lukujärjestelmät

Tavallisesti numeroiden esitykseen käytetään desimaalijärjestelmää, jossa luvut esitetään käyttämällä kymmentä numeroa 0–9. Desimaalijärjestelmä on niin sanottu kantalukujärjestelmä, jossa luku esitetään kertoimen ja kantaluvun potenssien tulona.

Esimerkiksi luku 17810 tulkitaan

17810 = 1x10² + 7x10¹ + 8x10⁰.

Tietokoneella luontainen numerojärjestelmä muistin rakenteen takia on kuitenkin binäärijärjestelmä eli lukujärjestelmä, jonka kantaluku on kaksi desimaalijärjestelmän kymmenen sijaan. Lukujen esittäminen ei kuitenkaan eroa oleellisesti desimaalijärjestelmästä. Ylempänä esitetty 17810 on binäärilukuna esitettynä

1011 00102 = 1x2⁷ + 0x2⁶ + 1x2⁵ + 1x2⁴ +0x2³ +0x2² +1x2¹ + 0x2⁰ = 1x128 + 1x32 + 1x16 + 1x2

= 17810.

Selkeyden vuoksi binääriluvut esitetään neljän numeron eli bitin ryhmissä. Esitystavasta voidaan nähdä, että suurin mahdollinen esitettävä luku esimerkin kolmella numerolla on 999=10³-1 ja binäärijärjestelmän tapauksessa kahdeksalla bitillä 1111 1111=2⁸-1.

Binäärinumeroista puhuttaessa käytetään usein termiä leveys, joka tarkoittaa luvun bittien määrää. Yleisesti siis kantalukujärjestelmän suurin esitettävissä oleva luku on kⁿ- 1, jossa k on käytettävä kantaluku ja n numeroiden määrä. Kun mukaan lasketaan nolla, voidaan kantalukujärjestelmillä esittää kⁿ eri lukua.

Edellä esitelty lukujärjestelmä käsittelee vain positiivisia lukuja, joita kutsutaan myös etumerkittömiksi luvuiksi. Desimaalijärjestelmässä negatiiviset luvut eli etumerkilliset luvut esitetään lisäämällä miinusmerkki luvun eteen. Vastaava miinusmerkki ei ole käytännöllinen tietokoneelle, joten negatiiviset luvut joudutaan esittämään eri tavalla.

Yleisesti käytössä on kaksi eri tapaa: yhden ja kahden komplementti.

(7)

Yhden komplementissa negatiiviset luvut muodostetaan muuttamalla jokainen ykkönen nollaksi ja nolla ykköseksi. Tarkastellaan esimerkkinä lukua 15010.

15010 = 1001 01102

-15010 = 0110 10012.

Toisaalta aiemman esimerkin mukaan 0110 1001 = 105¹⁰.

Tämä yksiselitteisyyden puute johtuu suoraan siitä, että kahdeksalla bitillä voidaan esittää vain 2⁸=256 eri lukua. Välillä -150–150 on kuitenkin 301 lukua, joten näin suurta lukua ei voida esittää. Yhden komplementtia käytettäessä suurin mahdollinen luku on k^n-

1. Käytännössä siis vasemmanpuoleisin bitti (MSB, most significant bit, merkitsevin numero) ilmaisee luvun negatiivisuuden (sign bit, merkkibitti). Käytetään edelleen kahdeksaa bittiä ja otetaan esimerkiksi 106.

10610 = 0110 10102 ja -106¹⁰ = 1001 0101².

Yhteenlasku yhden komplementin luvuilla yksinkertaista ja toimii positiivisilla luvuilla kuten desimaalijärjestelmässä allekkain:

0011 10012 = 5710

+ 0010 01012 = 3710

==================

= 0101 11102 = 9410

Negatiivisilla luvuilla laskutapa ei kuitenkaan tuota oikeaa tulosta:

0011 10012 = 5710

1101 10102 = -3710

==================

= 0001 00112 = 1910

Prosessorin yrittäessä suorittaa laskutoimitusta se joutuisi käyttämään ylimääräistä vaivaa ongelman ratkaisemiseksi. Ongelma voidaan kuitenkin ratkaista helposti käyttämällä kahden komplementin lukuja sen sijaan. Kahden komplementin luvuissa negatiivinen luku ilmaistaan muuttamalla samalla tavalla ensin ykköset nolliksi ja nollat ykkösiksi, mutta sen lisäksi lukuun lisätään yksi. Samoin negatiivinen luku voidaan muuttaa takaisin positiiviseksi toistamalla sama operaatio. Toistetaan yllä olevat laskutoimitukset käyttämällä kahden komplementtia. Positiivisilla luvuilla laskutoimitus on sama, mutta negatiivisilla luvuilla saadaan oikea tulos.

(8)

0011 10012 = 5710

+ 1101 10112 = -3710

==================

= 0001 01002 = 2010

Vähennyslasku voidaan suorittaa täysin samalla tavalla vaihtamalla vähennettävän luvun merkkiä. Tässä luvussa laskutoimituksissa on merkitty luvun kantaluku, mutta jatkossa se merkitään vain, jos luvun tulkinta on epäselvää. [3, luku 3.2.3]

2.2 Lukujärjestelmien rajoitteet ja lukujen leveys

Edellä käsiteltiin lukujen esitystapaa ja kuinka suuria lukuja tietyllä numeromäärällä voidaan esittää. Yhteen- ja vähennyslaskun tapauksessa voidaan näyttää, että kahden luvun summa ei koskaan vaadi enempää kuin yhden bitin lisää. Tuloon tarvittava bittimäärä ei ole yhtä yksinkertainen.

Helpoin tapa osoittaa tarvittava bittimäärä on kertoa suurin mahdollinen luku itsellään.

Neljän bitin tapauksessa suurin etumerkitön luku on 11112, joka itsellään kerrottuna on 1110 00012. Etumerkillinen suurin luku on 01112, joka vastaa kolme bittistä etumerkitöntä lukua ja tulo itsellään kerrottuna on 011 00012, jossa täytyy muistaa säilyttää etumerkin bitti. Etumerkittömien lukujen kertolaskun tulo vaatii siis enimmillään 2n bittiä. Tässä työssä käytettävät etumerkilliset luvut vaativat 2n-1 bittiä. Käytännössä tällä on vähän merkitystä ja tulokselle käytetään aina kaksi kertaa suurempaa leveyttä.

(9)

3. KERTOJIEN ARKKITEHTUURIT

Tässä luvussa käydään läpi erilaisia kertojien arkkitehtuureita ja niiden rakennetta.

Monimutkaisempien arkkitehtuurien tapauksissa aivan kaikkiin yksityiskohtiin ei mennä, vaan niitä tarkastellaan niiden pohjalla olevien algoritmien kautta. Luvussa käytetään aritmeettisten ja loogisten operaattoreiden lisäksi puoli- ja kokosummaimia (en. half adder, full adder). Summaimet operoivat vain yhden bitin leveillä luvuilla. Puolisummain laskee kahden luvun summan ja tuottaa summan sekä muistinumeron (en. carry bit).

Kokosummain laskee kolme lukua yhteen ja sillä on samat ulostulot.

3.1 Allekkain kertominen

Allekkain yhteenlaskemista käsiteltiin luvussa 2.2, jossa havaittiin sen toimivan samalla tavalla kuin desimaalijärjestelmässä. Samoin kertolasku voidaan suorittaa allekkain laskuna. Tarkastellaan laskutoimitusta esimerkin kautta kertomalla luvut 1110 ja 1410

etumerkittömillä esityksillä.

1011 = 1110

* 1110 = 1410

==========

0000 = 0¹⁰ 1011 = 2210

1011 = 4410

+ 1011 = 88¹⁰

==========

= 10011010 = 15410

Ensimmäinen tapa toteuttaa kertolasku on suorittaa yhteenlaskut yksi kerrallaan.

Laskennassa hyödynnetään sitä, että välisummat muodostetaan siirtämällä kerrottavaa vasemmalle [4, luku 4.1]. Kuvassa 1 on esitelty kertojan yksinkertaistettu rakenne.

Kuvassa A ja B ovat kerrottava ja kertoja, tulo tallennetaan tulokseen ja kontrolli ohjaa summainta sekä merkillä << on ilmaistua vasemmalle siirtäjää (en. left shifter), joka suorittaa allekkain kertolaskussa vastaavan luvun siirtämisen. Summaimen sisäisellä toteutuksella ei ole merkitystä toimintaan.

(10)

Kuva 1. Summain-kertoja

Summain-kertojan huono puoli on se, että tuloksen saaminen vaatii monta kellojaksoa, koska jokaisella kellojaksolla suoritetaan vain yksi yhteenlasku. Tuloksen saaminen kestää siis yhtä monta kellojaksoa kuin kertojassa on bittejä. Yllä oleva rakenne toimii vain etumerkittömille luvuille, mutta se voidaan muuttaa toimimaan kahden komplementin luvuilla muun muassa laskemalla tuloksen merkki erikseen [4, luku 4.2.4].

Kaikki yhteenlaskut voidaan suorittaa yhtä aikaa rakentamalla Ripple-Carry- summainpuu, jossa yhteenlaskujen tulokset siirtyvät suoraan seuraavaan yhteenlaskuun eteenpäin. Kuvassa 2 kertoja on kolme bittiä leveä x ja kerrottava neljä bittiä leveä y.

Jokainen solu on kokosummain, jossa lasketaan yhteen suluilla ilmaistujen x:n ja y:n valittujen bittien tulo, ylemmän solun summa ja edellisen yhteenlaskun muistinumero (en. carry bit).

(11)

Kuva 2. Ripple-carry-summainpuu [3, kuva 5.2]

Lukujen leveyden kasvaessa kriittinen polku, eli pisin läpimenoviive signaalille rakenteen läpi, pidentyy merkittävästi. Puurakenne voidaan toteuttaa tehokkaammin Cellular Carry- Save -algoritmilla [3, kuva 5.3], jota tullaan käyttämään myöhemmin. [3, luku 5.1.2.4]

3.2 Boothin algoritmi

Boothin algoritmi muistuttaa paljon edellä esiteltyä summain-kertojaa ja perustuu myös iteraatioon. Tässä esitetty kuvaus mukailee kahta eri tapaa esittää algoritmin toiminta.

Merkitään

A = 𝑎𝑛−1… 𝑎1𝑎0 kerrottava B = 𝑏𝑛−1… 𝑏1𝑏0 kertoja P = 𝑝_2𝑛−1… 𝑝₀𝑝₋₁ tulo.

Algoritmissa on viisi vaihetta:

1. aseta 𝑝₋₁= 0 ja p:n alimmat bitit B:ksi, 𝑝_𝑛−1… 𝑝₀ = 𝐵.

2. jos 𝑝₀𝑝₋₁= 10, lisää -A P:n ylimpiin bitteihin, 𝑝_2𝑛−1… 𝑝_𝑛 = 𝑝_2𝑛−1… 𝑝_𝑛− 𝐴.

3. jos 𝑝₀𝑝₋₁= 01, lisää A P:n ylimpiin bitteihin, 𝑝_2𝑛−1… 𝑝_𝑛 = 𝑝_2𝑛−1… 𝑝_𝑛+ 𝐴.

4. siirrä P:tä aritmeettisesti oikealle.

5. toista vaiheesta 2 alkaen n kertaa.

Algoritmi toimii etumerkittömille ja etumerkillisille luvuille täysin samanlaisena.

Huomioitavaa on vain vaiheen 4 aritmeettinen siirto. Jos 𝑝_2𝑛−1= 1 niin siirrettäessä

(12)

uudeksi numeroksi tulee 0 ja kun 𝑝_2𝑛−1= 1 uudeksi numeroksi tulee 1. Tällä säilytetään luvun merkkisyys.

Kuva 3. Boothin algoritmin esimerkkisuoritus [4, kuva 4.12]

Kuvassa 3 on esimerkki Boothin algoritmin laskennasta. Esimerkissä ei ole käytetty erikseen lukua P, johon tulos tallennetaan, vaan B on laajennettu 2n-1 bittiä leveäksi. [1]

[4, luku 4.4.3]

3.3 Wallace-puut ja Daddan algoritmi

Edellä summainpuu rakennettiin yksinkertaisesti ketjuttamalla kokosummaimia peräkkäin. Rakenteesta nähdään, että oikeanpuoleisimman kokosummaimen muistinumero kulkee kaikkien muiden kokosummaimien läpi, mikä hidastaa laskentaa

(13)

tarpeettomasti. Bittien yhteenlaskut voidaan tehdä tehokkaammin käyttämällä Wallace- puuta [4]. Puurakenteen tavoite on jakaa yhteenlaskut pienempiin osiin ja vähentää yhteenlaskujen kokonaismäärää. Wallace-puu laskee kerrallaan yhden sarakkeen kaikki bitit yhteen ja jokaiselle tulon bitille tarvitaan siis oma puu. Puu rakennetaan rekursiivisesti siten, että jokaisessa seuraavassa vaiheessa käytetään pienempää puuta.

Kuvassa 4 on esimerkkinä 15 bitin Wallace-puun rakentaminen.

Kuva 4. 15-bittisen Wallace-puun rakenne [4]

Puussa käytetään carry-save-kokosummaimia ja Wn merkitsee Wallace-puun leveyttä n.

Katkoviivalla on merkitty kriittinen polku, jonka pituus on 5 kokosummainta. Vertailun vuoksi 15-bittisen summainpuun luvussa 3.1 kriittinen polku olisi 29 kokosummainta.

Huomattavaa on se, että Wallace-puu ei tuota lopputulosta suoraan, vaan jokaisen

(14)

sarakkeen summat ja muistinumerot on laskettava yhteen käyttämällä tavallista summainta.

Kuva 5. 8-bittinen Wallace-puu.

Kuvassa 5 on kokonaan vaiheittain rakennettu 8-bittinen Wallace-puu. Jokainen piste merkkaa yhtä bittiä ja laatikot kuvaavat puoli- ja kokosummaimia. Tärkeää on huomata, että summaimet tuottavat muistinumeroita aina vasemmalla seuraavaan sarakkeeseen.

Esimerkiksi sarakkeeseen 6 tulee toisessa vaiheessa kahden kokosummaimen summabitit sekä sarakkeen 5 summaimista kaksi bittiä. Rakenne on esitetty eri tavalla kuin kuvassa 4, mutta on toiminnalta samanlainen. Kuudelle ylimmälle riville on muodostettu vastaavasti 3-bittiset Wallace-puut, jotka yhdistyvät lopulta 8-bittisiksi.

Puussa on 38 kokosummainta ja 15 puolisummainta. Alimpana kuvassa on summat ja muistinumerot, jotka lisätään yhteen tavallisella summaimella. Välivaiheiden

(15)

sarakkeiden koot ovat esimerkissä 8, 6, 4, 3 ja 2. Voidaan osoittaa, että optimaalinen rakenne saavutetaan, kun edellisen välivaiheen koko on

𝑘_𝑛+1= 𝑓𝑙𝑜𝑜𝑟 (3 2𝑘_𝑛),

jossa k on vaiheen suurin päällekkäin olevien bittien lukumäärä (sarakkeen korkeus), n vaiheen järjestysluku ja floor lattiafunktio, joka palauttaa luvun kokonaislukuosan. Tästä saadaan sarja 2, 3, 6, 9…

(16)

Daddan kertoja on Wallace-puun optimoidumpi versio, joka käyttää vähemmän puoli- ja kokosummaimia. Wallace-puussa bittien yhteenlasku aloitettiin oikeanpuolimmaisesta mahdollisesta sarakkeesta. Kuvassa 5 sarakkeet 2-7 sisältävät koko- ja puolisummaimia vaikka sarakkeen korkeus olisi riittävän pieni seuraavaan vaiheeseen ilmankin niitä.

Kuva 6. 8-bittisen Daddan kertojan puurakenne.

Daddan kertojassa käytetään aina pienintä mahdollista määrää puoli- ja kokosummaimia tarvittavan sarakkeen korkeuden saavuttamiseksi. Kuvassa 6 on rakennettu 8-bittinen puurakenne. Merkittävin ero Wallace-puuhun on ensimmäisen vaiheen summaimien määrä. Kokonaisuudessaan puussa on 34 kokosummainta (Wallace 38) ja 6 puolisummainta (Wallace 15). [5]

(17)

4. METODOLOGIA

Tässä luvussa käydään läpi työssä käytettävät työkalut ja kuinka kertojien testaaminen suoritetaan. Työkaluja ovat ohjelmointikielet, ohjelmistot testaamiseen ja ohjelmoimiseen, ja ohjelmoitava FPGA-piiri. Lisäksi luvussa esitellään vertailuun valitut kertojat.

4.1 Laitteistokuvauskieli VHDL

Työssä toteutettavat kertojat ohjelmoidaan käyttämällä laitteistokuvauskieltä VHDL (VHSIC Hardware Description Language). Kielellä voidaan kuvata digitaalisten järjestelmien rakennetta ja toimintaa yksittäisten porttien tai abstraktimmilla tasoilla.

Kieltä käytetään tyypillisesti ASIC ja FPGA piirien ohjelmoimiseen, joista lisää luvussa 4.2. Kielen suurin hyöty on se, että kirjoitettua koodia voidaan simuloida helposti ennen sen ohjelmointia laitteelle. Kirjoitettu koodi ei ole laiteriippuvainen ja ennen laitteen ohjelmointia koodi täytyy muuntaa toimimaan kohdelaitteen kanssa.

4.2 Laite ja ohjelmistot

Kertojat ohjelmoidaan PYNQ-Z1 FPGA-kehitysalustalle [6]. Kehitysalusta pohjautuu Xilinxin Zynq-7000 FPGA-piirille ja sisältää muun muassa kaksiytimisen ARM- prosessorin ja runsaasti eri I/O-liittimiä ja merkkivaloja. Tässä työssä käytetään lähinnä vain FPGA-piiriä. FPGA-piiri sisältää 13,300 logiikkaelementtiä (en. logic slice), joissa on neljä 6-bittistä hakutaulua ja kahdeksan kiikkua (en. flip-flop). Piirillä on 125 MHz kellosignaaligeneraattori, joka voidaan jakaa pienemmäksi noin 6 MHz asti.

PYNQ-Z1 ohjelmoidaan käyttämällä Xilinxin Vivado-ohjelmistoa [7]. Kuvassa 7 on Vivadossa kytketty Daddan kertoja testipenkkiin ja kellosignaaligeneraattoriin.

(18)

Kuva 7. Daddan kertoja yhdistettynä testipenkkiin Xilinx Vivadossa Koko ohjelmoitavalle rakenteelle käytetään nimeä design. Kertojien ohjelmoimisessa laitteelle on neljä vaihetta. Design täytyy syntetisoida, implementoida, luoda siitä bittivirtatiedosto (en. bitstream file) ja lopuksi ohjelmoida se FPGA-piirille.

Syntetisoinnissa korkeamman tason rakenne jaetaan FPGA:n logiikkaelementeille, ja luodaan verkko (en. netlist), joka määrittää kuinka elementit liitetään toisiinsa.

Syntetisointi on laitekohtaista ja se suoritetaan niiden resurssien mukaan, jotka kohdelaitteella on käytettävissä. Syntetisointi myös optimoi designia. Implementaatiossa syntetisoitu design sovitetaan kohdelaitteelle. Logiikkaelementtien paikat valitaan ja niiden välille luodaan verkot. Implementaatiossa myös kytketään laitteen I/O-portit designiin. Kytkennät määritetään Vivadossa erillisessä tiedostossa. Kolmannessa vaiheessa luodaan bittivirtatiedosto, joka sisältää tarvittavan tiedot laitteen ohjelmoinnista ja viimeisenä tiedosto ohjelmoidaan laitteelle. [8, luvut 6, 7]

Kertojien ohjelmointi FPGA:lle on hidas prosessi ja siksi ennen ohjelmointia on järkevää varmistaa niiden oikea toiminta simuloimalla. Tässä työssä simulointi tehtiin ModelSim- ohjelmalla [9]. Kuvassa 8 on tyypillinen näkymä ohjelmasta. Alareunassa piirretään valitut signaalit ja niiden arvoja voidaan muuttaa automaattisesti tai manuaalisesti.

(19)

Kuva 8. Kertojan simulointi ModelSim-ohjelmassa

4.3 Vertailtavat kertojat

Tässä työssä vertaillaan neljää eri luvussa 3 esiteltyä tapaa toteuttaa kertoja.

Yksinkertaisin allekkain kertoja on toteutettu muuttamalla kertoja ensin positiiviseksi ja sitten kertomalla kerrottava ja kertoja ilman merkkibittiä. Tuloksen merkki on sen jälkeen korjattu. Käytetty koodi on luotu työtä varten ja on liitteessä 1. Samaa allekkain laskun periaatetta on käytetty rakentamalla summainpuu. Ripple-carry-summaimella on pitkä läpimenoviive ja niiden käyttäminen hidastaisi kertojaa tarpeettomasti. Sen sijaan käytetään Carry-lookahead-summainta, joka toimii samalla tavalla, mutta lyhentää läpimenoviivettä merkittävästi ja pienentää myös pinta-alaa hieman [10]. Toisaalta virrankulutus kasvaa huomattavasti. Summainpuun koodi on liitteessä 2.

Kolmas vertailtava kertoja käyttää Boothin kertolaskualgoritmia. Algoritmista on käytetty avoimen lähdekoodin VHDL toteutusta [11]. VHDL mahdollistaa rakenteen geneerisen kuvauksen ja koodissa voidaan suoraan muuttaa kuinka leveitä lukuja kerrotaan.

Neljäs vertailtava kertoja käyttää Daddan algoritmia. Tällekin käytetään avoimen lähdekoodin toteutusta [12], jonka kanssa tarvitaan Vivadon Adder/Subtract-moduuli.

Tämä toteutus käyttää vain etumerkittömiä lukuja ja mitataan sekä etumerkittömänä että

(20)

myös muuttamalla luvut ensin etumerkittömiksi kuten allekkain kertomisessa. Kertojan rakentamiseen joudutaan käyttämään erillistä ohjelmaa, joka on toteutettu käyttämällä C++ -kieltä.

Boothin ja Daddan kertojien rakenteet ovat liian monimutkaisia rakenteen oikeellisuuden tarkistamiseen. Tässä työssä joudutaan olettamaan, että ne ovat toteutettu oikein.

4.4 Testipenkki

Pelkkä kertoja ei laitteelle ohjelmoituna tee mitään ja vaatii ympärille rakenteen, joka ikään kuin simuloi prosessoria, jossa kertojaa voitaisiin käyttää. Vertailtaville kertojille rakennetaan niin sanottu testipenkki, joka huolehtii kertojien syötteistä ja tuloksesta.

Testipenkki antaa kertojille kerrottavat luvut ja ilmoittaa kun halutut testit on suoritettu ja niiden tulosten oikeellisuuden. Koska testipenkki kasvattaa ohjelmoitavaa pinta-alaa sekä läpimenoviivettä, se halutaan suunnitella mahdollisimman yksinkertaiseksi.

Yksinkertaisin tapa saada käytyä läpi kattavasti erilaisia syötteitä on hyödyntää aina edellisen testin kertolaskun tulosta. Vertailtavat kertojat testataan myös simuloimalla, mikä todentaa niiden toimivuuden millä tahansa syötteillä ja täten ei ole tärkeää, että FPGA-piirillä testaus on yhtä kattava.

Yleisesti n-bittisten lukujen kertolaskun tulo on 2n bittiä leveä kuten luvussa 2.3 todettiin.

Tällöin voitaisiin käyttää tulon ensimmäistä n:ää bittiä kerrottavana ja jälkimmäistä n:ää bittiä kertojana. Toistamalla tätä laskutoimitusta monta kertaa huomataan kuitenkin nopeasti, että kertoja ja kerrottava pysyvät hyvin pieninä lukuina eikä koko kertojaa tule testattua luotettavasti. Lisäksi on mahdollista, että tulon ylemmät n-bittiä ovat kaikki nollia ja kertolaskun tulo jää pysyvästi nollaksi. Jälkimmäinen ongelma voidaan ratkaista riittävällä tasolla tarkastamalla olisiko kertoja tai kerrottava nolla ja asettamalla niille jokin vakio siinä tapauksessa. Samoja vakioarvoja käytetään ensimmäisessä kertolaskussa.

Kerrottavien arvojen pienuus voidaan ratkaista käyttämällä eri aluetta kertolaskun tulosta. Simulaatiossa kokeilemalla havaittiin, että käyttämällä kerrottavana tulon keskimmäistä n:ää bittiä ja kertojana viimeistä n:ää bittiä saadaan käytyä lukualue kattavasti läpi.

Koska kertojien syötteenä käytetään edellistä tuloa, on mahdollista, että joko sama tulos saadaan toistuvasti uudelleen tai jokin määrä tuloksia toistuu säännöllisesti. Tätä ongelmaa ei ole mahdollista ratkaista ja ainoaksi vaihtoehdoksi jää laskennan lopettaminen, kun saavutetaan arvo, jonka tiedetään toistuvan. Tätä kuitenkin hyödynnetään testin päättämiseksi ja se jättää ongelmaksi vain sellaisten alkuarvojen löytämisen, joilla saadaan riittävä määrä eri syötteitä testatuiksi. Testin lopetusarvot ovat

(21)

taulukossa 1. Daddan etumerkitön kertoja tarvitsee eri loppuarvot ja ne ovat myös taulukossa 1.

Kertojien testin lopetusarvot.

Lukujen

leveys Kerrottava Kertoja Kerrottava (Dadda etumerkitön)

Kertoja (Dadda etumerkitön)

8 -26 126 244 94

16 -5918 -7474 50.960 826

32 1.884.454.992 -2.142.238.530 209.461.240 536.421.074

Alkuarvot on helpoin löytää simuloimalla. Kerrottavalle käytettiin binäärimuodossa lukua, jonka MSB ja LSB ovat 1 ja muut nollia. Kertojassa kaksi merkitsevintä ja toiseksi vähiten merkitsevä numero ovat 1 ja muut nollia. Esimerkiksi 8-bittiä leveiden lukujen tapauksessa luvut ovat 1000 00012 ja 1100 00102.

Yllä läpikäydyistä ongelmista huolimatta testipenkin yksinkertaisuus on niitä tärkeämpää.

Monimutkaisemmat ratkaisut pienentäisivät kertojien mitattuja eroja, koska testipenkki kasvaisi liian suureksi osaksi koko ohjelmoitavaa toteutusta. Testipenkin koodi on liitteessä 3.

4.5 Mitattavat ominaisuudet

Tärkeimmät mitattavat ja vertailtavat ominaisuudet ovat kertojien pinta-ala ja suurin mahdollinen kellotaajuus, jolla niitä pystytään operoimaan. Toissijaisesti mitataan myös kertojien virrankulutusta, mutta käytettävän FPGA-laitteen rajoitusten takia todellista virrankulutusta ei pystytä mittaamaan ja joudutaan käyttämään Vivadon laskemaa viitteellistä arvoa. Virrankulutus on kuitenkin lähes suoraan verrannollinen pinta-alaan.

Pinta-alan mittauksissa otetaan huomioon testipenkin osuus. Tuloksissa listataan erikseen vertailtavien kertojien ja koko toteutuksien pinta-alat. Läpimenoviipeet mitataan kertojista yksinään ja testipenkkiin yhdistettynä.

FPGA:n suurin kellotaajuus on 125 MHz, joka saattaa olla hitaampi kuin kertojien suurin mahdollinen kellotaajuus. Tällöin kellotaajuus on laskettava käyttämällä kriittisen polun pituutta. Suurin kellotaajuus saadaan laskettua kaavalla

𝑓_𝑚𝑎𝑥 = ¹

𝑡_𝑐𝑝,

jossa fmax on suurin mahdollinen kellotaajuus ja tcp kriittisen polun pituus eli läpimenoviive. Läpimenoviive saadaan laskettua Vivadon ilmoittamasta WNS-arvosta

(22)

(en. worst negative slack). Käytännössä WNS kertoo kuinka paljon lyhyempi kellojakso voisi olla niin, että designissa ei esiinny epävakautta. Kriittinen polku saadaan laskettua kaavalla

𝑡_𝑐𝑝 = ¹

𝑓− 𝑊𝑁𝑆,

jossa f on implementaatiossa käytetty kellotaajuus. Kaikki testit suoritetaan 10 MHz kellotaajuudella, jolloin suurin mahdollinen kellotaajuus fmax on

𝑓_𝑚𝑎𝑥 = 1 ¹ 𝑓−𝑊𝑁𝑆.

Kaikista kertojista toteutetaan 8-, 16- ja 32-bittiset versiot. Käyttämällä eri luvun leveyksiä saadaan tietoa arkkitehtuurien skaalautuvuudesta.

(23)

5. SUORITUSKYKYMITTAUKSET

Tässä luvussa on listattuna kaikki mittaustulokset. Kaikki suorituskykymittaukset on suoritettu Vivadossa ja saatu joko suoraan tai laskemalla luvun 4.5 mukaan. Tuloksia analysoidaan ja niille tarjotaan mahdollisia selityksiä. Tuloksia on visualisoitu kertojien leveyden vaikutusten havainnollistamiseksi.

5.1 Suurin kellotaajuus

Taulukoissa 2, 3 ja 4 on listattu kertojien WNS ja niistä lasketut suurimmat kellotaajuudet fmax testipenkin kanssa ja ilman testipenkkiä. Tulokset on jaettu kertojien leveyksien mukaan.

Kertojien läpimenoviive ja suurin mahdollinen kellotaajuus, 8 bittiä.

Kertoja, 8 bittiä

WNS, testipenkin kanssa (ns)

WNS, ilman testipenkkiä (ns)

fmax, testipenkin kanssa (MHz)

fmax, ilman testipenkkiä (MHz) Summain-

kertoja 42,837 95,065 17,5 202,6

Summainpu

u 84,133 96,395 63,0 277,4

Booth 77,427 79,127 44,3 47,9

Dadda,

etumerkitön 91,551 94,571 118,4 184,2

Dadda, etumerkilline n

87,666 92,249 81,1 129,0

(24)

kertoja 43,083 94,070 17,6 168,6

Summainpuu 67,428 75,371 30,7 40,6

Booth 63,277 64,724 27,2 28,3

Dadda,

etumerkitön 87,532 90,461 80,2 104,8

Dadda,

etumerkillinen 81,418 86,160 53,8 72,3

kertoja 40,752 92,228 16,9 128,7

Summainpu

u 42,416 55,430 17,4 22,4

Booth 31,584 36,321 14,6 15,7

Dadda,

etumerkitön 82,673 83,940 57,7 62,3

75,110 81,457 40,2 53,9

Tuloksista nähdään välittömästi, että testipenkin osuus hyvinkin merkittävä pienillä leveyksillä, vaikka sitä yritettiin välttää. Etenkin summain-kertojan tulos muuttuu huomattavasti. Kuitenkin testipenkin merkitys selvästi vähenee kertojien leveyden kasvaessa. 32 bittiä leveillä kertojilla tulokset ovat lähes samat pois lukien summain- kertoja.

Tulokset ovat pitkälti sitä mitä arkkitehtuurien perusteella voitiin odottaa. Poikkeuksen muodostaa Boothin kertoja, jonka voisi olettaa olevan summainpuuta parempi. Kuitenkin Boothin kertoja oli hitain yhden kellojakson kertoja. Ensimmäinen mahdollinen selitys siihen on, että käytetty avoimen lähdekoodin toteutus kertojasta on heikko tai se ei noudata arkkitehtuuria tarkasti. Toinen vaihtoehto on, että Vivado ei pysty syntetisoimaan ja optimoimaan Boothin kertojaa yhtä hyvin kuin muita kertojia.

(25)

Kuva 9. Boothin kertojan kriittinen polku Vivadossa.

Kuvassa 9 on Vivadon visualisaatio 8-bittisen Boothin kriittisen polun rakenteesta.

Yksittäiset elementit eivät ole olennaisia, mutta kuvasta voidaan erottaa kertojan 8 vaihetta, jotka tapahtuvat täysin peräkkäin. Vivado on siis vain avannut for-silmukan koodissa eikä ole optimoinut sitä enempää.

Kuva 10. Kertojien suurimman mahdollisenkellotaajuuden kehitys Kuvassa 10 on visualisoitu kertojien suurimman mahdollisen kellotaajuuden suhde kertojan leveyteen. Summain-kertojan suorituskyky laskee selvästi vähiten leveyden kasvaessa. Kuitenkin on muistettava, että kertoja vaatii leveyden verran kellojaksoja, joka tekee siitä yhteensä hitaimman. Samoin Boothin kertoja hidastuu vähiten samankaltaisesta syystä. Daddan kertojien ero kutistuu leveyden kasvaessa, koska lukujen muuntaminen etumerkittömiksi on verrattain pienempi operaatio. Summainpuun kehitys on muista poikkeavaa. On hyvin todennäköistä, että Vivado on löytänyt jonkin optimoinnin vain 8 bittiä leveään versioon ja arkkitehtuuri ei tarkasti vastaa kuvattua.

0 50 100 150 200 250 300

8 16 24 32

fmax (MHz)

Kertojan leveys

Summain-kertoja Summainpuu Booth

Dadda etumerkitön Dadda etumerkillinen

(26)

5.2 Pinta-ala

Kertojien pinta-ala koostuu hakutauluista (LUT) ja kiikuista (flip-flop, FF) ja ne ovat listattu taulukoissa 5, 6 ja 7.

Kertojien pinta-alat, 8 bittiä.

LUT, testipenkin kanssa (kpl)

FF, testipenkin kanssa (kpl)

LUT, ilman testipenkkiä (kpl)

FF, ilman testipenkkiä (kpl) Summain-

kertoja 81 47 30 35

Summainpu

u 109 25 80 0

Booth 229 25 224 0

Dadda,

etumerkitön 83 25 73 0

136 25 99 0

kertoja 176 74 57 60

Summainpuu 436 38 409 0

Booth 805 38 818 0

Dadda,

etumerkillinen 523 38 467 0

(27)

kertoja 449 136 129 109

Summainpu

u 2776 74 2909 0

Booth 3157 74 3177 0

Dadda,

1854 74 1803 0

Tuloksista nähdään ensinnäkin, että vain summain-kertoja ja testipenkki käyttävät kiikkuja. Kaikki muut kertojat ovat yhdistelmäprosesseja, joissa ulostulo riippuu vain sisääntuloista eikä aiemmasta tilasta. Summain-kertoja taasen tallentaa jatkuvasti edellisen välivaiheen tuloksen. Kiinnostavampi havainto on joidenkin kertojien pinta- alojen epäjohdonmukaisuus. Muun muassa etumerkitön 32-bittinen Daddan kertoja käyttää enemmän hakutauluja ilman testipenkkiä. Mahdollinen selitys liittyy siihen, kuinka Vivado optimoi designia.

(28)

Kuva 11. Hakutauluja Vivadossa.

Kuvassa 11 nähdään, että hakutauluista ei aina käytetä kaikkia kuutta bittiä. On mahdollista, että joko optimaalisempaa tapaa käyttää hakutauluja ei ole tai Vivado ei sitä löytänyt. Joka tapauksessa tuloksissa muodostuu tästä huolimatta selkeä trendi.

Kuvassa 12 on esitetty kertojien hakutaulujen määrän kasvu ilman testipenkkiä.

(29)

Kuva 12. Kertojien hakutaulujen määrän kehitys

Merkittävin havainto on, että summain-kertojan pinta-ala kasvaa hyvin vähän muihin kertojiin verrattuna. Kertojan kompleksisuus on lähellä lineaarista, koska leveyden kasvaessa vain summainta ja välituloksen säilyttävää rekisteriä tarvitsee leventää.

Toinen poikkeus tuloksissa on summainpuun muita verraten nopeampi pinta-alan kasvu.

Boothin algoritmin tehottomuus näkyy myös pinta-alan käytössä, jossa se on huonoin.

5.3 Tehonkulutus

Tehonkulutuksista ei saatu hyviä mittauksia. Erot jäivät hyvin pieniksi ja vasta 32 bittiä leveillä luvuilla saatiin merkittäviä eroja, jotka ovat listattu taulukossa 8.

Kertojien tehokulutus, 32 bittiä.

Kertoja,

32 bittiä Tehonkulutus (mW) Summain-

kertoja 206

Summainpu

u 236

Booth 225

Dadda,

etumerkitön 222

226 0

500 1000 1500 2000 2500 3000 3500

8 16 24 32

Hakutalut, LUT (kpl)

Kertojan leveys

Summain-kertoja Summainpuu Booth

Dadda etumerkitön Dadda etumerkillinen

(30)

Vivado ilmoittaa tehonkulutuksen arvion syntetisoinnin ja implementoinnin perusteella.

Taulukossa ilmoitetut luvut ovat implementoinnin tehonkulutukset. Syntetisoinnin perusteella Vivado raportoi kuinka virrankulutus jakautuu. Kuvassa 13 on erään kertojan tehonkulutuksen analyysi.

Kuva 13. Kertojan tehonkulutuksen analyysi Vivadossa

Puolet virrasta on laitteen staattista virtaa ja toinen puoli lähes kokonaan PLL- kellosignaaligeneraattorin. Tyypillisesti logiikan suuruus oli vähemmän kuin 1 milliwattia muutamaa poikkeusta lukuun ottamatta. 32-bittisten kertojien mittaustuloksista voidaan tehdä vain vähän johtopäätöksiä. Pinta-alan perusteella olisi voinut olettaa Boothin kertojan kuluttavan myös eniten virtaa, mutta summainpuun kulutus oli suurempi.

Summain-kertojan kulutuksen vähäisyys taasen johtuu pinta-alasta.

(31)

6. YHTEENVETO

Mittaustuloksissa huomattiin selkeästi rinnakkaisen laskennan hyöty. Daddan kertoja oli suorituskyvyltään kokonaisuudessa selkeästi paras. Johdannossa mainittiin prosessoreille kaksi eri tavoitetta: maksimaalinen suorituskyky ja virrankulutus.

Valitettavasti jälkimmäisessä ei saatu merkittäviä eroja. Daddan kertoja vaikuttaa kuitenkin pinta-alan perusteella parhaalta vaihtoehdolta myös sen kannalta. Summain- kertoja saattaisi käyttää vähemmän virtaa, mutta sitä olisi käytettävä suuremmalla kellotaajuudella tai tuloksen saaminen kestäisi paljon kauemmin. Kummassakin tapauksessa kokonaisvirrankulutus olisi suurempi. Daddan kertojaa voidaan siis pitää parhaana kaikkiin käyttötarkoituksiin.

On hyvin valitettavaa, että vertailuun ei ollut saatavissa kaupallista ratkaisua, koska kaupallisten prosessorien arkkitehtuurit eivät ole julkista tietoa. Käytetyllä FPGA-piirillä tulokset näyttävät kuitenkin hyvältä. Yleisesti käytettävillä 32-bittisilä luvuilla Daddan kertojalla saavutettiin yli 50 MHz kellotaajuus, jota voidaan pitää hyvänä FPGA:n suurimman kellotaajuuden ollessa 125 MHz.

Summain-kertojaa lukuun ottamatta kaikki vertaillut kertojat antoivat tuloksen yhden kellojakson aikana. Kaupallisissa prosessoreissa tämä ei kuitenkaan ole välttämätöntä ja luopumalla siitä voidaan kellotaajuutta nostaa moninkertaiseksi. Niin kutsuttu liukuhihnoittaminen (en. pipelining) tarjoaa suurempia hyötyjä kuin kertojien välillä saatiin tässä työssä. Tutkimusta kertojien optimoinnista kannattaa jatkaa liukuhihnoittamisella.

(32)

LÄHTEET

[1] Andrew D. Booth: A signed binary multiplication technique. 1950. Saatavissa:

http://bwrcs.eecs.berkeley.edu/Classes/icdesign/ee241_s00/PAPERS/archive/b ooth51.pdf

[2] Intel 4004 -prosessorin historia. Osoitteessa:

https://www.intel.co.uk/content/www/uk/en/history/museum-story-of-intel- 4004.html. Viitattu 10.3.2021.

[3] Deschamps J-P, Bioul GJA, Sutter GD. Synthesis of arithmetic circuits: FPGA, ASIC and embedded systems. Hoboken: WILEY; 2006.

[4] Lu M. Arithmetic and logic in computer systems. 1st edition. Hoboken, NJ:

Wiley-Interscience; 2004.

[5] L. Dadda: Some schemes for parallel multipliers. 1965. Saatavissa:

https://www.ece.ucdavis.edu/~vojin/CLASSES/EEC280/Web- page/papers/Arithmetic/Dadda_mult.pdf

[6] Xiling PYNQ-Z1. Osoitteessa: https://www.xilinx.com/support/university/boards- portfolio/xup-boards/XUPPYNQ.html. Viitattu 15.4.2021.

[7] Xilinx Vivado Design Suite. Osoitteessa:

https://www.xilinx.com/products/design-tools/vivado.html. Viitattu 18.4.2021.

[8] Smith G. FPGAs 101. 1st ed. Newnes; 2010.

[9] Modelsim HDL Simulator. Osoitteessa: https://eda.sw.siemens.com/en- US/ic/modelsim/. Viitattu 20.4.2021.

[10] J. Kaur, L. Sood: Comparison Between Various Types of Adder Topologies.

2015. Saatavissa: https://www.ijcst.com/vol61/1/13-Jasbir-Kaur.pdf [11] Booth's Multiplication Algorithm in VHDL. Saatavissa:

https://github.com/taneroksuz/vhdl-multiplier-generator. Viitattu 20.3.2021.

[12] VHDL Multiplier Generator. Saatavissa: https://github.com/taneroksuz/vhdl- multiplier-generator. Viitattu 24.3.2021

(33)

LIITE 1: SUMMAIN-KERTOJA

2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46

library ieee;

use ieee.std_logic_1164.all;

use ieee.numeric_std.all;

entity adder_multiplier is generic (

width_g : integer );

port (

clk : in std_logic;

rst_n : in std_logic;

mult_a_in : in std_logic_vector(width_g-1 downto 0);

mult_b_in : in std_logic_vector(width_g-1 downto 0);

result_out : out std_logic_vector(2*width_g-1 downto 0) );

end entity adder_multiplier;

architecture structural of adder_multiplier is

signal result_r : std_logic_vector(2*width_g-1 downto 0);

-- Counter for adding and shifting.

-- The range can be one bit less

-- than the numbers because the sign bit is ignored signal counter_r : integer range 0 to width_g-1;

begin

calculate : process (clk, rst_n) is

-- Variable for converting multiplier mult_b positive -- if it is negative

variable mult_b_temp : std_logic_vector(width_g-1 downto 0);

begin -- process calculate

if rst_n = '0' then -- asynchronous reset (active low) result_r <= (others => '0');

counter_r <= 0;

elsif clk'event and clk = '1' then -- rising clock edge -- Convert mult_b positive if negative

if mult_b_in(width_g-1) = '1' then

mult_b_temp := std_logic_vector(signed(not mult_b_in) + 1);

else

(34)

48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 84 86 88 90

mult_b_temp := mult_b_in;

end if;

-- If mult_b_temp's corresponding bit to the counter -- is set 1 then add mult_a_in shifted by counter -- to result_r

if counter_r = 0 then

if mult_b_temp(counter_r) = '1' then -- Set result_r = mult_a_in

result_r <= std_logic_vec-

tor(resize(signed(mult_a_in), 2*width_g));

else

result_r <= (others => '0');

end if;

else -- counter 1...width_g-1

if mult_b_temp(counter_r) = '1' then -- Add mult_a_in to the result

-- mult_a_in resized to 16 bits and then -- shifted arithmetically

result_r <= std_logic_vector(

signed(result_r) +

shift_left(resize(signed(mult_a_in), 2*width_g), counter_r));

else

-- No change

result_r <= result_r;

end if;

-- Counter

if counter_r = width_g-1 then counter_r <= 0;

else

counter_r <= counter_r + 1;

end if;

end process calculate;

-- Correct signess

result_out <= std_logic_vector(signed(not result_r) + 1) when mult_b_in(width_g-1) = '1'

else result_r;

end structural;

(35)

LIITE 2: SUMMAINPUU

2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46

library ieee;

entity adder_multiplier_cla is generic (

width_g : integer := 8 );

port (

mult_a_in : in std_logic_vector(width_g-1 downto 0);

mult_b_in : in std_logic_vector(width_g-1 downto 0);

result_out : out std_logic_vector(2*width_g-1 downto 0) );

end entity adder_multiplier_cla;

architecture behavior of adder_multiplier_cla is

-- Component declaration component cla is

generic (

SIZE : natural );

port(

a : in std_logic_vector(SIZE-1 downto 0);

b : in std_logic_vector(SIZE-1 downto 0);

c_in : in std_logic;

s : out std_logic_vector(SIZE-1 downto 0);

c_out : out std_logic );

end component cla;

-- Signals for converting multiplier and multiplicand -- positive if negative

signal mult_a_temp : std_logic_vector(width_g-1 downto 0);

signal mult_b_temp : std_logic_vector(width_g-1 downto 0);

-- Signal for result before fixing sign

signal result_temp : std_logic_vector(2*width_g-1 downto 0);

type vector_g is array (width_g-1 downto 0) of std_logic_vec- tor(width_g-1 downto 0);

-- Signals for connecting adders signal cla_conn_s : vector_g;

-- Signals for connecting mult_a to cla

(36)

48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 84 86 88 90 92 94 96 98 100 102 104 106

signal cla_mult_a_s : vector_g;

begin

calculate : process(mult_a_in, mult_b_in, mult_a_temp, mult_b_temp, result_temp, cla_conn_s)

begin

-- Convert mult_a positive if negative if mult_a_in(width_g-1) = '1' then

mult_a_temp <= std_logic_vector(signed(not mult_a_in)+1);

else

mult_a_temp <= mult_a_in;

end if;

-- Convert mult_b positive if negative if mult_b_in(width_g-1) = '1' then

mult_b_temp <= std_logic_vector(signed(not mult_b_in)+1);

else

mult_b_temp <= mult_b_in;

end if;

-- Assign mult_a to cla_mult_a_s for i in 0 to width_g-2 loop if mult_b_temp(i) = '1' then cla_mult_a_s(i) <= mult_a_temp;

else

cla_mult_a_s(i) <= (others => '0');

end if;

end loop;

-- Last cla to result

result_temp(2*width_g-3 downto width_g-2) <=

cla_conn_s(width_g-1)(width_g-1 downto 0);

-- Connect first bits from upper cla's for i in 0 to width_g-3 loop

result_temp(i) <= cla_conn_s(i+1)(0);

end loop;

-- Zero out 2 MSB

result_temp(2*width_g-1 downto 2*width_g-2) <= "00";

-- Fix result signess

if (mult_a_in(width_g-1) xor mult_b_in(width_g-1)) = '1' then

result_out <= std_logic_vector(signed(not result_temp) + 1);

else

result_out <= result_temp;

end if;

end process calculate;

--- -- First cla

cla_conn_s(0) <= (others => '0');

cla_0 : cla generic map(

SIZE => width_g-1 -- Sign bit ignored

(37)

108 110 112 114 116 118 120 122 124 126 128 130 132 134

)

port map(

a => cla_mult_a_s(0)(width_g-2 downto 0), b => cla_conn_s(0)(width_g-1 downto 1), c_in => '0',

s => cla_conn_s(1)(width_g-2 downto 0), c_out => cla_conn_s(1)(width_g-1)

);

--- -- Middle and last cla's

for_generate : for i in 1 to width_g-2 generate

cla_n : cla generic map(

SIZE => width_g-1 -- Sign bit ignored )

port map(

a => cla_mult_a_s(i)(width_g-2 downto 0), b => cla_conn_s(i)(width_g-1 downto 1), c_in => '0',

s => cla_conn_s(i+1)(width_g-2 downto 0), c_out => cla_conn_s(i+1)(width_g-1)

);

end generate;

end behavior;

(38)

LIITE 3: TESTIPENKKI

2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46

library ieee;

entity tb_multiplier_pynq is generic (

width_g : integer;

cycles_g : integer;

-- Values that end the test mult_a_end_value : integer;

mult_b_end_value : integer;

-- Set '1' if Dadda (unsigned) multiplier is used is_unsigned : integer

);

port (

clk : in std_logic;

rst_n : in std_logic;

test_ended_out : out std_logic;

mult_a_out : out std_logic_vector(width_g-1 downto 0);

mult_b_out : out std_logic_vector(width_g-1 downto 0);

result_in : in std_logic_vector(2*width_g-1 downto 0) );

end entity tb_multiplier_pynq;

architecture testbench of tb_multiplier_pynq is

constant result_zeros : std_logic_vector(2*width_g-1 downto 0) := (others => '0');

-- Signals for DUV

signal mult_a_r : std_logic_vector(width_g-1 downto 0);

signal mult_b_r : std_logic_vector(width_g-1 downto 0);

-- Flag for ending the test

signal test_completed_r : std_logic;

-- Flag for initial values for multiplication signal test_start_r : std_logic;

-- Clock cycle counter. 1 bit less than the bit width -- because sign bit is ignored

signal counter_r : integer range 0 to cycles_g-1;

(39)

48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 84 86 88 90 92 94 96 98 100 102 104 106

begin -- architecture testbench multiply : process (clk, rst_n) is

begin -- process multiply

if rst_n = '0' then -- asynchronous reset (active low)

test_start_r <= '1';

test_completed_r <= '0';

counter_r <= 0;

-- Set mult_a 1xxx1 and mult_b 11xxx10

--mult_a_r <= (width_g-1 => '1', 1 => '1', others => '0');

mult_a_r <= '1'&(width_g-2 downto 1 => '0')&'1';

--mult_b_r <= (width_g-1 => '1', width_g-4 => '1', 1 =>

'1', others => '0');

mult_b_r <= '1'&(width_g-2 downto width_g-3 =>

'0')&'1'&(width_g-5 downto 2 => '0')&'1'&'0';

elsif clk'event and clk = '0' and test_completed_r = '0' then -- falling clock edge

-- Start new calculation every cycles_g'th cycle.

-- mult_a is the middle half of the result -- (for example 1100 => 10)

-- and mult_b lower half. Also bit 0 of mult_a

-- and bit 1 of mult_b are flipped to produce longer test.

-- If multiplicands would become zero, a constant is set.

if counter_r = 0 then

if test_start_r = '0' then

-- If middle half is 0 set mult_a 3

if result_in(2*width_g-width_g/2-1 downto width_g- width_g/2) = result_zeros(2*width_g-1 downto width_g) then

mult_a_r <= std_logic_vector(to_signed(3, mult_a_r'length));

else

mult_a_r <= result_in(2*width_g-width_g/2-1 downto width_g-width_g/2);

mult_a_r(0) <= not mult_a_r(0);

end if;

-- If lower half is 0 set mult_b 5

if result_in(width_g-1 downto 0) = result_ze- ros(width_g-1 downto 0) then

mult_b_r <= std_logic_vector(to_signed(5, mult_b_r'length));

else

mult_b_r <= result_in(width_g-1 downto 0);

mult_b_r(1) <= not mult_b_r(1);

end if;

else

test_start_r <= '0';

end if;

-- End the test when predefined values are reached -- Dadda multiplier uses unsigned values

if is_unsigned = 1 then

if unsigned(mult_a_r) = mult_a_end_value and unsigned(mult_b_r) = mult_b_end_value then

test_completed_r <= '1';