ANALYSIS OF ADVANCED COMPUTER TECHNOLOGIES FOR CALCULATION OF EXACT APPROXIMATIONS OF STATISTICS PROBABILITY DISTRIBUTIONS
Abstract
In the paper we consider the solution of a computationally expensive problem such as calcu-lation of statistics probability distribution with the help of modern computer technologies. To re-duce computational complexity and to provide a sufficient level of criteria efficiency not less than the specified threshold, we suggest to use Δ-exact approximations. To calculate exact approxima-tions, we use the method of second order, based on solution of a system of linear equations. Owing to this method, it is possible to calculate exact approximations for the maximum values of sample parameters for available computational resource. The most laborious part of the method of second order is the procedure of sequential detection of the vectors of possible solutions and test if the vectors belong to the set of solutions. The system solution set membership test for the vectors of possible solutions is data independent, so the algorithm can be data-parallelized. We give the al-gorithm complexity equation for calculation of exact approximations of statistics probability dis-tributions. Using this equation, we calculated the complexity of modern practical problems for the samples with the parameters (N, n) of the alphabet power and the sample size: (256,1280), (128,640), (128, 320), and (192,3200) for the accuracy of calculations =10-5. The computational complexity is 9.68·1022-1.60·1052 operations, and its average value is about 4.55·1025 operations, the number of tested vectors is 6.50·1023-1.39·1050, and the number of solutions is 4.67·1012-5.60·1025, respectively. The total solution time for clock-round duration of calculations cannot exceed 30 days or 2.592·106 sec. For the obtained complexity evaluation, we analysed abilities of modern cluster computer systems based on general-purpose processors, graphic accelerators, and FPGA-based reconfigurable computer systems. For each technology, we determined the number of computational nodes needed for calculation of exact approximations with the specified parameters during the specified time. We proved that it is impossible to obtain a solution for the required pa-rameters of exact approximations of statistics probability with the help of the reviewed modern computer technologies. In conclusion, we claim that it is necessary to analyse the abilities of ad-vanced computer technologies based of quantum and photonic computers, and also hybrid com-puter systems for calculation of exact approximations of statistics probability distributions with the specified parameters during reasonable time
References
1. Mel'nikov A.K. Sravnenie effektivnosti obrabotki tekstov pri primenenii v statisticheskikh kriteriyakh tochnykh i predel'nykh priblizheniy bazovykh raspredeleniy veroyatnostey znacheniy testovykh statistik [Comparison of the effectiveness of text processing when using exact and marginal approximations of basic probability distributions of test statistics values in statistical criteria], Obozrenie prikladnoy i promyshlennoy matematiki [Review of Applied and Industrial Mathematics], 2018, Vol. 25, Issue 4, pp. 375-378. ISSN 0869-8325.
2. Mel'nikov A.K. Slozhnost' rascheta tochnykh raspredeleniy veroyatnosti simmetrichnykh additivno razdelyaemykh statistik i oblast' primeneniya predel'nykh raspredeleniy [The com-plexity of calculating the exact probability distributions of symmetric additively separable sta-tistics and the scope of marginal distributions], Doklady TUSUR [Reports of TUSUR], 2017, Vol. 20, No. 4, pp. 126-130. ISSN 1818-0442.
3. Mel'nikov A.K. Primenenie tochnykh i predel'nykh priblizheniy raspredeleniy veroyatnostey znacheniy statistik pri reshenii zadachi obrabotke tekstov [Application of exact and marginal approximations of probability distributions of statistical values in solving the problem of text processing], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2018, No. 8 (202), pp. 114-135.
4. Kramer G. Matematicheskie metody statistiki [Mathematical methods of statistics: trans. from English]. Moscow: Mir, 1975, 648 p.
5. Mel'nikov A.K., Ronzhin A.F. Obobshchennyy statisticheskiy metod analiza tekstov, osnovannyy na raschete raspredeleniy veroyatnosti znacheniy statistik [Generalized statistical method of text analysis based on the calculation of probability distributions of statistical val-ues], Informatika i ee primeneniya [Computer science and its applications], 2016, Vol. 10, Issue 4, pp. 91-97. ISSN 1992-2264.
6. Mel'nikov A.K. Algoritmicheskaya slozhnost' rascheta tochnykh priblizheniy raspredeleniy veroyatnostey znacheniy statistik metodom resheniya uravneniya pervoy kratnosti tipov [Algo-rithmic complexity of calculating exact approximations of probability distributions of statisti-cal values by solving the equation of the first multiplicity of types], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2020, No. 7 (217), pp. 52-67.
7. Mel'nikov A.K. Metodika rascheta raspredeleniy veroyatnostey znacheniy statistik, blizkikh k ikh tochnym raspredeleniyam [Methodology for calculating probability distributions of statistical values close to their exact distributions], Obozrenie prikladnoy i promyshlennoy matematiki [Re-view of Applied and Industrial Mathematics], 2017, Vol. 24, Issue 5, pp. 320-323.
8. Mel'nikov A.K. Algoritmicheskaya slozhnost' rascheta tochnykh priblizheniy raspredeleniy veroyatnostey znacheniy statistik [Algorithmic complexity of calculating exact approximations of probability distributions of statistical values], Superkomp'yuternye tekhnologii: sbornik trudov molodykh uchenykh [Supercomputer technologies: a collection of works of young sci-entists], ed. by Academician of the Russian Academy of Sciences Kalyaeva I.A. Rostov-on-Don; Taganrog: Izd-vo YuFU, 2020, pp. 66-70. ISBN 978-9275-3612-2.
9. Fisher R.A. Statisticheskie metody dlya issledovateley [Statistical methods for researchers: trans. from engl.]. Moscow: Gosstatizdat., 1958, 73 p.
10. Stivens Rod. Algoritmy. Teoriya i praktika primeneniya [Algorithms. Theory and practice of application]. Moscow: Eksmo, 2019, 544 p. ISBN 978-5-699-81729-0.
11. Svidetel'stvo o gosudarstvennoy registratsii programmy dlya EVM № 2018664398. Raschet raspredeleniy veroyatnostey znacheniy statistik maksimal'no priblizhennykh k ikh tochnomu raspredeleniyu. Pravoobladatel' i avtor Mel'nikov A.K. Zayavka № 2018662120. Data postupleniya 01 noyabrya 2018 g. Data gosudarstvennoy registratsii v Reestre programm dlya EVM 16 noyabrya 2018 g. [Certificate of state registration of the computer program No. 2018664398. Calculation of probability distributions of statistical values as close as possi-ble to their exact distribution. Copyright holder and author Melnikov A.K. Application No. 2018662120. Date of receipt 01 November 2018 Date of state registration in the Register of computer programs November 16, 2018].
12. Svidetel'stvo o gosudarstvennoy registratsii programmy dlya EVM № 2020664143. Raschet chisla resheniy sistemy lineynykh uravneniy vtoroy kratnosti tipov. Pravoobladatel' Kolodzey A.V. Avtor: Kolodzey A.V. i Mel'nikov A.K. Zayavka № 2020662473. Data postupleniya 19 oktyabrya 2020 g. Data gosudarstvennoy registratsii v Reestre pro-gramm dlya EVM 9 noyabrya 2020 g. [Certificate of state registration of the computer program No. 2020664143. Calculation of the number of solutions of a system of linear equations of the second multiplici-ty of types. Copyright holder Kolodzey A.V. Author: Kolodzey A.V. and Melnikov A.K. Ap-plication No. 2020662473. Date of receipt October 19, 2020 The date of state registration in the Register of computer programs is November 9, 2020].
13. Spisok TOP500 [TOP500 list]. Available at: https://www.top500.org (accessed 18 November 2021).
14. Antonov A.S., Afanas'ev I.V., Voevodin Vl.V. Vysokoproizvoditel'nye vychislitel'nye platformy: tekushchiy status i tendentsii razvitiya [High-performance computing platforms: current status and development trends], Vychislitel'nye metody i programmirovanie [Computational methods and pro-gramming], 2021, Vol. 22, pp. 135-177. DOI: 10.26089/NumMet.v22r210.
15. Videokarta GeForce RTX 3090 NVIDIA [NVIDIA GeForce RTX 3090 graphics card]. Avail-able at: https://3dnews.ru/1021405/obzor-videokarti-nvidia-geforce-rtx-3090 (accessed 18 No-vember 2021).
16. Graficheskaya karta NVIDIA Quadro RTX 6000 [NVIDIA Quadro RTX 6000 Graphics Card]. Available at: https://3dnews.ru/1027931/nvidia-obyavila-o-dostupnosti-sverhmoshchnoy-videokartirtx-a6000-s-48-gbayt-gddr6-i-tsenoy-5500 (accessed 18 November 2021).
17. Levin I.I., Fedorov A.M., Doronchenko Yu.I., Raskladkin M.K Guzik V.F., Kalyaev I.A. Rekonfiguriruemye vychislitel'nye sistemy [Reconfigurable computing systems], under the general ed. of I.A. Kalyaeva. Taganrog: Izd-vo YuFU, 2016, 472 p. ISBN 978-5-9275-1918-7.
18. Levin Ilya I. et al. Reconfigurable computer systems: from the first FPGAs towards liquid cooling systems, Supercomputing Frontiers and Innovations, 2016, Vol. 3 (1), pp. 22-40. DOI: 10.14529/jsfi160102.
19. Levin I.I., Fedorov A.M., Doronchenko Yu.I., Raskladkin M.K. Perspektivnye vysoko-proizvoditel'nye rekonfiguriruemye vychisliteli s immersionnym okhlazhdeniem [Promising high-performance reconfigurable computers with immersion cooling], Superkomp'yuternye tekhnologii: Sb. trudov molodykh uchenykh [Supercomputer technologies: Collection of works of young scien-tists]. Rostov-on-Don; Taganrog: Izd-vo YuFU, 2020, pp. 29-34. ISBN 978-5-9275-3612-2.
20. Trimberger S.M. Three Ages of FPGAs: A Retrospective on the First Thirty Years of FPGA Technology, in Proceedings of the IEEE, March 2015, Vol. 103, No. 3, pp. 318-331. DOI: 10.1109/JPROC.2015.2392104.
21. Nane R. et al. A Survey and Evaluation of FPGA High-Level Synthesis Tools, in IEEE Trans-actions on Computer-Aided Design of Integrated Circuits and Systems, Oct. 2016, Vol. 35, No. 10, pp. 1591-1604.
22. Nane R., Sima V.-M., Olivier B., Meeuws R., Yankova Y., Bertels K. DWARV 2.0: A CoSy-based C-to-VHDL Hardware Compiler, In FPL, 2012, pp. 619-622.
23. Pilato C. and Ferrandi F. Bambu: A Modular Framework for the High Level Synthesis of Memory-intensive Applications, In FPL, 2013, pp. 1-4.
24. Canis A., Choi J., Aldham M., Zhang V., Kammoona A., Anderson J.H., Brown S., Czajkowski T. LegUp: High-Level Synthesis for FPGA-based Processor, Accelerator Systems. In ACM FPGA, 2011, pp. 33-36.
25. Make Slow Software Run Fast with Vivado HLS. Available at: https://www.xilinx.com/ publi-cations/xcellonline/run-fast-with-Vivado-HLS.pdf, last accessed 2021/03/10 (accessed 18 No-vember 2021).
26. Vitis Unified Software Platform Documentation. Application Acceleration Development. Available at: https://www.xilinx.com/support/documentation/sw_manuals/xilinx2019_2/ug 1393-vitis-application-acceleration.pdf, last accessed 2021/03/10 (accessed 18 November 2021).
27. Ilya Levin, Alexey Dordopulo, Vyacheslav Gudkov, Andrey Gulenok, Alexander Bovkun, Georgyi Yevstafiyev, Kirill Alekseev. Software development tools for fpga-based reconfigura-ble systems programming, In: communications in computer and information science, 2019, Vol. 1129, Chapter parallel computing technologies, pp. 1-16.
