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.
|
