20.500.12556/RUL-91339 Matrični algoritmi na podatkovno-pretokovnih računalnikih Matrix algorithms on data-flow computers Medtem ko se frekvenca procesorjev že desetletje bistveno ne povečuje več, se potrebe znanosti po računski moči večajo. Podatkovno-pretokovna računalniška arhitektura predstavlja dobro alternativo klasičnemu ukazno-pretokovnemu računalniku. V okviru dela je bil razvit sklop algoritmov za množenje matrike z vektorjem in množenje dveh matrik na podatkovno-pretokovni arhitekturi. Primerjali so se časi izvajanja v primerjavi z ukazno-pretokovnimi rešitvami. Pohitritve pri množenju matrike in vektorja ni bilo. Pri množenju matrike z naborom vektorjem so bile dosežene skoraj 4-kratne pohitritve. Algoritem za množenje dveh matrik je dosegel več kot 100-kratno pohitritev. Dodatno sta bila implementirana algoritem za matrično potenciranje in algoritem iskanja najkrajših poti med vsemi pari vozlišč. Prvi je dosegel okoli 100-kratno pohitritev, drugi pa je bil približno enako hiter kot ukazno-pretokovni algoritem Floyd-Warshall. While the processor frequency has failed to significantly increase in the last decade, the needs of science for computing power continue to increase. Data-flow computer architecture presents a good alternative to traditional control-flow computer. In this work a set of algorithms for matrix-vector multiplication and matrix-matrix multiplication was developed. It was compared with control-flow implementations. With matrix-vector multiplication there was no speedup. Algorithm for multiplying matrix with a set of vectors achieved almost 4-fold speedup. Matrix-matrix multiplication algorithm achieved more than 100-fold speedup. Further matrix exponentiation and all-pairs shortest path search algorithm were implemented. First algorithm achieved 100-times speedup, while the second one was about the same speed as control-flow Floyd-Warshall algorithm. podatkovno-pretokovna arhitektura matrično množenje matrični algoritmi grafni algoritmi Maxeler Technologies dataflow architecture matrix multiplication matrix algorithms graph algorithms Maxeler Technologies true false false Slovenski jezik Angleški jezik Magistrsko delo/naloga 2017-03-28 13:38:53 2017-03-28 13:38:55 2022-08-09 21:23:19 0000-00-00 00:00:00 2017 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 1970-01-01 17383 Znideric_Matej_-_Matricni_algoritmi_na_podatkovno-pretokovnih_racunalnikih.pdf Znideric_Matej_-_Matricni_algoritmi_na_podatkovno-pretokovnih_racunalnikih.pdf 1 595CE58D3FE0001FA912CA4914E88074 aa1425624450325e28f635741f0b5cef9067b2ea046cf085056959c8967e60f6 cef5908d-a1b2-11eb-a523-00155dcfd717 20.500.12556/rul/18eec10c-eb10-44ed-9a77-4a42fd1fc8c3 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=97320 Fakulteta za računalništvo in informatiko 0 0 0