Automatic bit-width minimization framework based on information theoretic degradation measures.
Author
Johansen, Jeppe
Term
10. term
Education
Publication year
2012
Submitted on
2012-05-12
Abstract
Designing DSP implementations on FPGAs requires careful selection of fixed-point bit widths to balance accuracy, area, speed, and power, a task that is typically manual and guided by statistical error measures. This thesis investigates information-theoretic measures to quantify the degradation introduced by finite-precision implementations and proposes an automatic bit-width minimization framework. The approach covers number representation and the effects of bit truncation, estimates implementation costs on FPGAs/DSPs, and defines degradation metrics including Kullback–Leibler divergence alongside traditional statistics. A domain-specific language is used to describe algorithm dataflows; from an initial safe allocation, heuristic optimizers (e.g., simulated annealing, genetic algorithms, hill climbing) search for reduced bit widths under quality constraints, producing a tuned high-level description. Tests on common algorithms, including an exponential function and a complex non-linear case, compare mappings guided by statistical versus information-theoretic measures; the resulting optimized implementations perform very close to each other, indicating the viability of the proposed methodology.
Design af DSP-implementeringer på FPGA’er kræver nøje valg af fixed-point bitbredder for at balancere nøjagtighed, areal, hastighed og effektforbrug, en opgave der typisk er manuel og styret af statistiske fejlmål. Denne afhandling undersøger informationsteoretiske mål til at kvantificere den forringelse, som endelig præcision introducerer, og foreslår en automatisk ramme for bitbredde-minimering. Tilgangen dækker talrepræsentation og effekterne af bittrunkering, estimerer implementeringsomkostninger på FPGA’er/DSP’er, og definerer forringelsesmål inklusive Kullback–Leibler-divergens sammen med traditionelle statistikker. En domænespecifik beskrivelsessprog bruges til at modellere algoritmers dataflow; fra en initial sikker allokering søger heuristiske optimere (fx simulated annealing, genetiske algoritmer, hill-climbing) efter reducerede bitbredder under kvalitetskrav og producerer en tunet høj-niveau beskrivelse. Test på almindelige algoritmer, herunder en eksponentialfunktion og et komplekst ikke-lineært tilfælde, sammenligner mapping styret af statistiske versus informationsteoretiske mål; de resulterende optimerede implementeringer præsterer meget tæt på hinanden, hvilket indikerer metodens levedygtighed.
[This apstract has been generated with the help of AI directly from the project full text]