izpis_h1_title_alt

Evalvacija polinomov na podatkovno-pretokovnih računalnikih
ID Sodja, Anže (Author), ID Mihelič, Jurij (Mentor) More about this mentor... This link opens in a new window

.pdfPDF - Presentation file, Download (14,77 MB)
MD5: 27970248EA201378EECB97EB30945660
PID: 20.500.12556/rul/db8a61de-d7ba-41a3-89fa-b604a0c79a35

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

Language:Slovenian
Keywords:podatkovno-pretokovna arhitektura, evalvacija polinomov, algoritmi, Maxeler
Work type:Master's thesis/paper
Organization:FRI - Faculty of Computer and Information Science
Year:2017
PID:20.500.12556/RUL-96536 This link opens in a new window
Publication date in RUL:05.10.2017
Views:1127
Downloads:334
Metadata:XML RDF-CHPDL DC-XML DC-RDF
:
Copy citation
Share:Bookmark and Share

Secondary language

Language:English
Title:Polynomial evaluation on data-flow computers
Abstract:
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.

Keywords:data-flow architecture, polynomial evaluation, algorithms, Maxeler

Similar documents

Similar works from RUL:
Similar works from other Slovenian collections:

Back