Matrični algoritmi na podatkovno-pretokovnih računalnikih

Žniderič, Matej (author), 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.

• Language: Slovenian
• Keywords: podatkovno-pretokovna arhitektura, matrično množenje, matrični algoritmi, grafni algoritmi, Maxeler Technologies
• Work type: Master's thesis/paper
• Organization: FRI - Faculty of Computer and Information Science
• Year: 2017
• PID: 20.500.12556/RUL-91339
• Publication date in RUL: 28.03.2017

Secondary language

• Language: English
• Title: Matrix algorithms on data-flow computers

Abstract

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.

• Keywords: dataflow architecture, matrix multiplication, matrix algorithms, graph algorithms, Maxeler Technologies