Home
Authors Papers Year of conference Themes Organizations To MES conference
Development and Investigation of Algorithm of Sparse Matrices Multiplication Task for the Parallel Dataflow Computing System "Buran" 




Authors 
 Zmejev D.N. 
 Okunev A.S. 
Date of publication 
 2018 
DOI 
 10.31114/20787707201831623 

Abstract 
 Operations with sparse matrices are relevant in solving scientific and engineering problems. One of these operations is the multiplication of sparse matrices. There are many algorithms for traditional computing systems that solve this task. A sequential algorithm, consisting of nested loops system, is inefficient and is only applicable for singleprocessor systems. Parallel algorithms are much more efficient and run on supercomputers and clusters. The creation of such algorithms requires certain knowledge of parallel programming and taking into account different levels of parallelism, and the creation of an effective program also requires complex system of data organization. Other aproach for solving the task of sparse matrices multiplication is considered in the article  the application of the parallel dataflow computing system (PDCS) "Buran" that implements the dataflow computing model with a dynamicaly formed context. The process of developing an algorithm in dataflow programming paradigm, which is completely different from the traditional (imperative) one, is shown. The dataflow algorithm consists of two parts  the description of program nodes and the formation of initial data. Coding of program nodes is carried out using the highlevel programming language HPL (Highparallel language). The resulting program code, as well as the algorithm described by it, is simple and universal. The program allows the multiplication of two full/sparse matrices or the multiplication of the matrix by a vector or number. The choice of multiplication objects is determined at the stage of initial data formation. When creating dataflow programs, hardware acceleration is possible, which allows reducing the code of the program or completely abandon the use of program nodes. This is also setted up during the stage of initial data formation. The use of this programming mechanic allowed the creation of three dataflow programs: fully programmed implementation, fully hardware implementation and an intermediate version. The experimental part of the work was divided into two components. In the first part, the dataflow program and the program created using traditional methods were compared. The comparison was performed on the "Lomonosov" cluster supercomputer and the results showed a high efficiency of the dataflow program when solving tasks with a sparse data structure and with equal programming complexity. In the second part of the experiments, three implementation variants of dataflow algorithm were compared. The results of the comparison showed the high efficiency of applying special approaches to programming, especially when creating small (in terms of the number of computational cores) special computers. In general, the article demonstrated on a concrete example: the potential of using the PDCS "Buran" for solving tasks with a sparse data structure; the simplicity of programming; and the versatility and high efficiency of the created dataflow programs. 
Keywords 
 sparse matrices multiplication, dataflow computing model, parallel dataflow computing system. 
Library reference 
 Zmejev D.N., Okunev A.S. Development and Investigation of Algorithm of Sparse Matrices Multiplication Task for the Parallel Dataflow Computing System "Buran" // Problems of Perspective Micro and Nanoelectronic Systems Development  2018. Issue 3. P. 1623. doi:10.31114/20787707201831623 
URL of paper 
 http://www.mesconference.ru/data/year2018/pdf/D116.pdf 

