Evalvacija polinomov na podatkovno-pretokovnih računalnikih

Sodja, Anže (avtor), Mihelič, Jurij (mentor)

V magistrskem delu smo implementirali algoritme za evalvacijo polinomov na podatkovno-pretokovni arhitekturi. Čeprav je evalvacija polinomov enostaven problem za današnje centralne procesne enote, pa z večjim številom točk tudi ta postane počasna. Tako smo implementirali algoritme za evalvacijo redkih in gostih polinomov v eni in več točkah na podatkovno-pretokovnem računalniku družbe Maxeler. Naše algoritme smo eksperimentalno preizkusili na realnih in kompleksnih polinomih. Dosegli smo do dvajsetkratne pospešitve za goste polinome v več točkah in do sedemdesetkratne pospešitve za redke polinome v več točkah. Poleg tega smo naše algoritme prilagodili tudi za evalvacijo podproblema gručenja točk in diskretne Fourierove transformacije. Vse rezultate smo analizirali in grafično predstavili.

• Jezik: Slovenski jezik
• Ključne besede: podatkovno-pretokovna arhitektura, evalvacija polinomov, algoritmi, Maxeler
• Vrsta gradiva: Magistrsko delo/naloga
• Organizacija: FRI - Fakulteta za računalništvo in informatiko
• Leto izida: 2017
• PID: 20.500.12556/RUL-96536
• Datum objave v RUL: 05.10.2017

SODJA, Anže, 2017, Evalvacija polinomov na podatkovno-pretokovnih računalnikih [na spletu]. Magistrsko delo. [Dostopano 2 maj 2025]. Pridobljeno s: https://repozitorij.uni-lj.si/IzpisGradiva.php?lang=slv&id=96536

Sekundarni jezik

• Jezik: Angleški jezik
• Naslov: Polynomial evaluation on data-flow computers

Izvleček

In this master thesis we implemented algorithms for polynomial evaluation on data-flow architecture. Polynomial evaluation is relatively simple problem for today's central processing units. However with an increasing number of points in which we evaluate polynomial, time of evaluation can become a problem. We implemented algorithms for evaluation of sparse and dense polynomials on Maxeler data-flow computers. We tested our algorithms on real polynomials as well as on complex polynomials. We have achieved up to 20-fold speedup for dense and up to 70-fold speedup for sparse polynomials. Additionally, we customised our algorithms for evaluation of subproblem of point clustering and also for evaluation of Discrete Fourier transform. We analysed our results and presented them graphically.

• Ključne besede: data-flow architecture, polynomial evaluation, algorithms, Maxeler