Rask 128bits adderer

[Dr_VingTor]

Holder på å skal implementere en addisjons/subtraksjons krets (2s komplement) som skal kunne legge sammen/trekke fra hverandre to 128 bits tall. Den må være rask da det er denne som er flaskehalsen i systemet vi skal lage, men den må heller ikke bruke for mye areal (vi skal ha den på en FPGA, så arealet måles i LUTer)

 

Lurer på om det er noen som har noen gode forslag til hvordan jeg kan gjøre den raskere enn hva jeg har klart til nå (se under)? Er det noen som har linker til hvordan en adderer kan pipelines o.l. så kan det også være interessant.

 

Det jeg har gjort til nå er å lage en 4bits carry look ahead blokk, som jeg har brukt til å lage en 4 bits adderer med carry look ahead. Denne bruke jeg igjen til å lage en 16bit, så en 64bits, så en 128 bits, hvor alle disse hadde carry look ahead.

 

Fra syntese av kretsen fikk jeg disse tallene:

ant. bit; areal; kritisk sti; ca maks klokke (regnet ut fra kritisk sti)

4 bit; 17 LUT; 3,09ns; ~ 300MHz

16bit; 80 LUT; 5,14ns; ~ 200MHz

64bit; 308 LUT; 8,20ns; ~ 122MHz

128bit; 619 LUT; 10,64ns; ~ 94 MHz

 

Til sammenlikning bruker en ripple carry adderer på 128bit 166ns, som gir ca 6MHz.

 

som dere ser så er forholdet mellom bits/forsinkelse alt ganske bra, men kan jeg få det bedre på noen måte? er det andre ting som er bedre enn CLA?

[ToMmM]

Si ifra hvis du klarer å lage noe, Vet at man kan lage noe jævlig rask ting med FPGA hvis man optimaliserer til en ting..

[DargarWhiteFang]

humm.. Dersom det var resultatet av "automatisk" kompilering av VHDL koden din, sår kan du klare å vinne en del på å "leke" med precompiler-innstillinger. Nå har jeg bare hatt ett kurs i VHDL (med den svenske eksperten innen VHDL), så jeg er langt fra flink, men han viste oss at optimalisering og kompilering var en meget avansert prosess der man kan ha relativt mye å hente med å manuelt tweake kompileringen. Dette er nok desverre noe man må ha relativt mye erfaring med for å få til.. Han viste noen slides, tenk som en ski-bakke med "trappetrinn" i. Han sa at en kompilator vil prøve å lage raskere kode, men at den kan nå "flaten" i et trappetrinn og dermed "gi opp". Av og til kan det også være at man må "gå opp" i bakken litt igjen for å komme lengre ned ved å følge en annen sti.. (der ned, såklart er kjappere kode, eller mindre areal, eller et kompromiss, avhengig av hva man prioriterer.)

 

 

... hummm... med andre ord, I have nothing... Lykke til iallefall! ... Kanskje bedre å prøve på xilinx sitt forum???

[Dr_VingTor]

synteseverktøyet har nok en del å si ja, har ikke så mye peil på tweaking av det enda da, men får vell se litt på det. Nå har jo jeg bygd opp koden gjennom flere entiteter så kanskje det hjelper å "flate den ut" eller hva det kalles.

 

Er bare 2. faget hvor jeg bruker VHDL også, så er langt fra ekspert...

 

får prøve å søke litt på forumet til xilinx, er jo en fpga fra de vi skal bruke så...

[jajajalla]

Hmm, hvordan ser designet ditt av 4 bits CLAen

ut da? Og portforsinkelsene?

 

mvh

[kurant]

Det finnes en del raskere adder-arkitekturer enn den tree-lookahead utgaven du har valgt nå, men jeg har ikke boken som beskriver disse foran meg for øyeblikket. jeg kan ta en titt når jeg kommer på skolen i morgen.

 

Bruker dere boken "CMOS VLSI design" på ntnu? isåfall kan du slå det opp der.

[Dr_VingTor]

4bits CLAen er koka rett ut fra en bok jeg har "Principles of Digital Design" av D. D. Gajski. 4 porter i kritisk sti. Nå har vell den FPGAen vi skal bruke LUTer med 4 innganger, så trur ikke det er smart å lage en større CLA, da det vil gi mer forskinkelse.

 

Eneste boka jeg har i VHDL er "HDL chip design" av D. J. Smith.

[kons]

Du nevner LUT og FPGA og et sted lenger nede Xilinx. Xilinx har mange familier men de aller fleste med LUTs har også innebygget "fast carry" for å bygge addere med høy ytelse.

 

Det er lettere å svare om du kan fortelle hvilken familie det handler om og hvor mye resurser du ser for deg å bruke.

Det er også av interesse om den skal levere ett resultat per klokke?

Hvilke frihetsgrader har du mhp. pipelining?

 

Jeg vil tro du i utgangspunktet kan glemme CLA og lignende lavnivåstrukturer, sørg for at den innebygde fastcarry strukturen blir syntetisert inn i middels store blokker (16 bits eller mer), så kan du bygge hele adderen av disse etterpå, piplining osv avhenger av hva du kan gjøre for sprell.

[Dr_VingTor]

leste et sted at de hadde innebygget carry logikk jeg også, men fant aldri ut hvordan kode skal skrives for at den skal bli brukt (eller noen referanser til innstillinger til synteseverktøy)

 

FPGAen er en Xilinx, Virtex 2, xc2v1000, hele systemet vi skal lage kan ikke bruke mer enn 50% av FPGAen. Foruten om det er kravet at det skal være så raskt som mulig. Nå kommer jeg til å trenge 2 slike adderere i systemet (vell, det går med en, men to er bedre), og alt det andre vi skal ha kommer i tillegg, så den bør jo ikke være for stor. litt vanskelig å si sikkert hvor mye jeg kan bruke på addereren enda, da vi ikke har laget det andre vi trenger(vi skal lage en krets for RSA kryptering).

Får vi til å bruke den innebyggede carry logikken vil vi nok spare en del plass i forhold til hva vi gjør nå også...

 

Et resultat per klokke hadde vært fint, men det er ikke et krav.

 

Noen som vet hva som skal til for å bruke den interne carry logikken? link gjerne til datablader o.l. som omtaler det, for jeg har ikke klart å finne noen.

 

 

--update--

 

dumme meg , hadde jo fått den til å bruke den interne carry logikken tidligere, men får den ikke til å behandel carry in og out på rett måte (det ser ut som det virker under simulering, men ikke under syntese), var vell derfor jeg begynte med lavnivå for å få det til å virke...

 

128 bit med intern carry logikk ga ca 7 ns forskinkelse sammenlignet med de 10 ns jeg hadde, men den brukte jo mye mindre areal, så da jeg jeg bruke det arealte på å gjøre denne raskere, men har problemer med carry in og out...

 

( nå vet jeg i alle fall sikkert at den interne carryen er raskere )

Endret 15. oktober 2006 av Dr_VingTor

[kons]

Kikk på logicore blokker, evt. let fram hvorfor det ikke fungerer med CI/CO.

Carry IN og OUT er dedikerte resurser på utsiden av LUT som bare kan brukes på bestemte måter. Gjør det enklest mulig så kanskje det går igjennom, så kan du legge på mer kompliserte termer til det ikke går lengre.

 

Logicore kan generer hele greia som en fast blokk, det eneste du trenger å gjøre er å sett den inn i designet som en extern blokk. (ferdig design fil som ligger sammen med netlista)

Strukturen internt i blokken er låst, og timing er stort sett garantert (om man ikke fyller veldig fullt om jeg ikke husker helt feil)

Mener du får en simuleringsmodell å teste med også.

 

Om du går på siden til Xilinx ser du at Virtex II er så gammel at den ikke lenger står annonsert på forsiden, litt overasket over valget av denne kretsen, men det kan jo være gode grunner selvsagt.

Spartan3 burde være ca like bra og vesentlig rimligere, og dertil mer kurant teknologi.

[Dr_VingTor]

Fikk det endelig til å syntetisere rett og ved bruk av intern carry logikk ( så da er all den koden jeg skrev opprinnelig bortkastet, men fikk no repetert litt).

 

Hele problemet med carry er at "+" operatoren er definert forskjellig i de bibliotekene som jeg hadde prøvd meg på å bruke. Løsningen ble å gjøre om de 128 bits tallene som tas inn til vectorer med 129 bit, hvor MSB er satt til null. Fant løsningen på "Xilinx Synthesis Technology (XST) User Guide" (http://toolbox.xilinx.com/docsan/3_1i/data/fise/xst/xst.htm)... skulle ha funnet den siden litt tidligere... dette syntetiserte til en 128 bit adderer med carry ut.

 

carryen er nå sykt raskt, men det er en del delay i start og slutt som er stor, men tenker at hvis jeg deler den i to og bruker carry select (en adderer for første 64 bit, og to for siste 64 bit) så bør jeg få en adderer som er så rask at resten av systemet kanskje begynner å bli flaskehalen. Har i alle fall funnet ut hva som var problemet nå. Må bare modifisere litt nå så den kan brukes som subtraksjonskrets også, men det får jeg nok til nå som jeg vet hva problemet var.

 

Grunnen til at vi bruker Virtex II er vell så enkel som at det er den som de har på laben på skolen, vil jeg anta...

 

takker for hjelpa så langt, men kom gjerne med flere forslag om dere har noe smart på lur...

[kons]

Vil tro at om du har plass til 3x64bit add + litt logikk så får du mer ytelse ved å bygge 2x 128bit som jobber i parallell. De blir litt tregere hver for seg en _en_ carry save men gjør mye mer beregninger siden det er 2.

Det er vanskelig å slå fastcarry logikken, erfaringsmessig mye bedre å gjøre grep på overordnet system nivå.

 

Tenk også på hvordan du vil mate den med data, blokk RAM er veldig effektivt til slike regnemotorer. Siden de har synkrone dualport funksjoner innebygget kan samme RAM være source og destination registrer på samme tid.