Parallel Evaluation Of Fixed-Point Polynomials
Independent thesis Advanced level (degree of Master (Two Years)), 80 credits / 120 HE creditsStudent thesisAlternative title
Parallell evaluering av polynom i fix-talrepresentation (Swedish)
In some applications polynomials should be evaluated, e.g., polynomial approximation of elementary function and Farrow ﬁlter for arbitrary re-sampling. For polynomial evaluation Horner’s scheme uses the minimum amount of hardware resources, but it is sequential. Many algorithms were developed to introduce parallelism in polynomial evaluation. This parallelism is achieved at the cost of hardware, but ensures evaluation in less time.
This work examines the trade-off between hardware cost and the critical path for different level of parallelism for polynomial evaluation. The trade-offs in generating powers in polynomial evaluation using different building blocks(squarers and multipliers) are also discussed. Wordlength requirements of the polynomial evaluation and the effect of power generating schemes on the timing of operations is also discussed. The area requirements are calculated by using Design Analyzer from Synopsys (tool for logic synthesis) and the GLPK (GNU Linear Programming Kit) is used to calculate the bit requirements.
Place, publisher, year, edition, pages
2010. , 82 p.
Horner, Estrin, parallel, polynomial, evaluation, Addition chains
Other Electrical Engineering, Electronic Engineering, Information Engineering
IdentifiersURN: urn:nbn:se:liu:diva-60054ISRN: LiTH-ISY-EX--10/4406--SEOAI: oai:DiVA.org:liu-60054DiVA: diva2:354917
2010-09-14, Nollstället, B-huset, Campus Valla, Linköping, Sweden, 10:30 (English)
Abbas, Muhammad, Ph.D. student
Gustafsson, Oscar, Associate Professor, Head