Matrični algoritmi na podatkovno-pretokovnih računalnikih

Žniderič, Matej (avtor), Mihelič, Jurij (mentor)

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.

• Jezik: Slovenski jezik
• Ključne besede: podatkovno-pretokovna arhitektura, matrično množenje, matrični algoritmi, grafni algoritmi, Maxeler Technologies
• Vrsta gradiva: Magistrsko delo/naloga
• Organizacija: FRI - Fakulteta za računalništvo in informatiko
• Leto izida: 2017
• PID: 20.500.12556/RUL-91339
• Datum objave v RUL: 28.03.2017

Sekundarni jezik

• Jezik: Angleški jezik
• Naslov: Matrix algorithms on data-flow computers

Izvleček

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.

• Ključne besede: dataflow architecture, matrix multiplication, matrix algorithms, graph algorithms, Maxeler Technologies