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/2078-7707-2018-3-16-23
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 single-processor systems. Parallel algorithms are much more effi-cient 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 imple-ments the dataflow computing model with a dynamicaly formed context. The process of developing an algorithm in dataflow programming paradigm, which is completely dif-ferent 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 high-level program-ming language HPL (High-parallel 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 cre-ating 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 data-flow programs: fully programmed implementation, fully hardware implementation and an intermediate version. The experimental part of the work was divided into two compo-nents. In the first part, the dataflow program and the pro-gram 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 vari-ants 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. 16-23. doi:10.31114/2078-7707-2018-3-16-23
URL of paper
	http://www.mes-conference.ru/data/year2018/pdf/D116.pdf