Article information
2020 , Volume 25, ¹ 1, p.66-81
Levin I.I., Dordopulo A.I.
On the problem of automatic development of parallel applications for reconfigurable computer systems
To solve applied problems, the hardware costs of which exceed the available computing resource of FPGA-based computer systems, an original technique was developed for mapping the information graph of an application program to the architecture of a reconfigurable computing system. The proposed technique is based on the performance reduction methods that reduce the productivity of an applied task, which, along with the reducing productivity, does so for the hardware costs of its implementation and, thereby, solve the problem on the available computing resource. We demonstrate that the decrease in hardware costs for the computing structure realization occurs only during the reduction the basic subgraph number, the number of computing devices in a basic subgraph and the data width. The influence of sequential reduction transformations on the computing structure of a problem is examined. The proved theorems are concerned with the possibility of representing the reduction coefficient as a product of the coefficients of successive reductions, on the inability of additive increase in reduction coefficient during sequential reductions and on the superposition commutativity of different sequential reductions. The proved theorems and the corollaries presented in the article allow formulating the basic principles for the method of reduction transformations of the information graph of the problem for adaptation to the architecture of a hybrid reconfigurable computing system. A distinctive feature of the technique is a relatively small number of transformations for a balanced reduction of the information graph of the problem and the implementation of the task on a reconfigurable computer system.The comparatively small number of transformations required for the balanced reduction of the information graph of the problem and for the implementation of calculations on a reconfigurable computer system is the distinctive feature of the technique. For the developed technique, we estimated the maximal number of transformations and found out the decrease in the quantity of analyzed reduction variants from each class. The proposed technique permits the significant reduction of the time needed to create the computational structure of a parallel program adapted to the architecture and configuration of the reconfigurable computing system. Furthermore, the technique allows automatization of this process using the specialized software and providing at least 50–75% efficiency in comparison with the solutions of the same problems by specialists.
[full text] Keywords: performance reduction, hardware costs, reconfigurable computer system, parallel applications development, information graph
doi: 10.25743/ICT.2020.25.1.005
Author(s): Levin Ilya Izrailevich Dr. , Professor Position: Director Office: Supercomputers and Neurocomputers Research Center Address: 347900, Russia, Taganrog
Phone Office: (8634)612-111 E-mail: levin@superevm.ru SPIN-code: 2700-6512Dordopulo Alexey Igorevich PhD. Position: Senior Research Scientist Office: Southern Scientific Centre of the Russian Academy of Sciences Address: 344006, Russia, Rostov
Phone Office: (8634)315491 E-mail: scorpio@mvs.tsure.ru SPIN-code: 3037-3418 References:
[1] Klinov, M.C., Kryukov V.A. Automatic parallelization of Fortran programs. The mapping on the cluster. Proc. of the XI All-Russ. Conf. “Scientific Service on the Internet”, Novorossiysk, 2009. Moscow: IPM im. Keldysha RAN; 2009: 227–237. (In Russ.)
[2] Ovchinnikov V.A. Grafy v zadachakh analiza i sinteza struktur slozhnykh sistem [Graphs in the problems of analysis and synthesis of structures of complex systems]. Moscow: MGTU im. N.E. Baumana; 2014: 423. (In Russ.)
[3] Bakhtin, V.A., Zhukova, O.F., Kataev, N.A., Kolganov A.C., Kryukov V.A., Podderyugina N.V., Pritula M.N., Savitskaya O.A., Smirnov A.A. Automation of parallelization of software systems. Proc. of the XI All-Russ. Conf. “Scientific Service on the Internet”, Novorossiysk, 2009. Moscow: IPM im. Keldysha RAN; 2016: 76–85. (In Russ.)
[4] System for Automated Parallelization of FORtran programs (SAPFOR) Available at: http://www.keldysh.ru/dvm/SAPFOR/ (accessed 26.02.2019).
[5] Shteynberg B.Ya. Matematicheskie metody rasparallelivaniya rekurrentnykh tsiklov dlya superkomp'yuterov s parallel'noy pamyat'yu [Mathematical methods of parallelization of recurrent cycles for supercomputers with parallel memory]. Rostov-na-Donu: Rostov State University; 2004: 172. (In Russ.)
[6] Kalyaev, A.V., Levin I.I. Modul'no-narashchivaemye mnogoprotsessornye sistemy so strukturno-protsedurnoy organizatsiey vychisleniy [Modular-scalable multiprocessor computer systems with structural-procedural organization of calculations]. Moscow: Yanus-K; 2003: 380. (In Russ.)
[7] Levin I.I., Sorokin D.A., Melnikov A.K., Dordopulo A.I.. Solving tasks with considerably variable data flow density on reconfigurable computer systems. Herald of computer and information technologies. 2012; (2):49-56. (In Russ.)
[8] Graham R.L., Knuth D.E., Patashnik O. Concrete mathematics. A foundation for computer science. Second Edition. United States of America: Addison-Wesley Publishing Company, Inc.; 1994: 670.
[9] Petrovskiy, A.B. Prostranstva mnozhestv i mul'timnozhestv [Spaces of sets and multisets]. Moscow: Editorial URSS; 2003: 248. (In Russ.)
[10] Levin, I.I., Dordopulo, A.I., Gudkov, V.A., Gulenok A.A., Bovkun A.V., Evstafev G.A., Bezzubova M.I. Programming tools for FPGAbased reconfigurable and hybrid computer systems. XIII international conference “Parallel computational technologies 2019” (PCT-2019), short articles and descriptions of posters. Chelyabinsk: Izdatel'skiy tsentr YuUrGU; 2019: 477. (In Russ.) ISBN 978-5-696-05020-1.
Bibliography link: Levin I.I., Dordopulo A.I. On the problem of automatic development of parallel applications for reconfigurable computer systems // Computational technologies. 2020. V. 25. ¹ 1. P. 66-81
|