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 calculation
of statistics probability distribution with the help of modern computer technologies. To reduce
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 approximations,
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 algorithm
complexity equation for calculation of exact approximations of statistics probability distributions.
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 parameters
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 advanced
computer technologies based of quantum and photonic computers, and also hybrid computer
systems for calculation of exact approximations of statistics probability distributions with
the specified parameters during reasonable time.
References
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 complexity
of calculating the exact probability distributions of symmetric additively separable statistics
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 values],
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 [Algorithmic
complexity of calculating exact approximations of probability distributions of statistical
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 [Review
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 scientists],
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 possible
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 multiplicity
of types. Copyright holder Kolodzey A.V. Author: Kolodzey A.V. and Melnikov A.K. Application
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 programming],
2021, Vol. 22, pp. 135-177. DOI: 10.26089/NumMet.v22r210.
15. Videokarta GeForce RTX 3090 NVIDIA [NVIDIA GeForce RTX 3090 graphics card]. Available
at: https://3dnews.ru/1021405/obzor-videokarti-nvidia-geforce-rtx-3090 (accessed 18 November
2021).
16. Graficheskaya karta NVIDIA Quadro RTX 6000 [NVIDIA Quadro RTX 6000 Graphics Card].
Available at: https://3dnews.ru/1027931/nvidia-obyavila-o-dostupnosti-sverhmoshchnoyvideokartirtx-
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 vysokoproizvoditel'nye
rekonfiguriruemye vychisliteli s immersionnym okhlazhdeniem [Promising highperformance
reconfigurable computers with immersion cooling], Superkomp'yuternye tekhnologii:
Sb. trudov molodykh uchenykh [Supercomputer technologies: Collection of works of young scientists].
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 Transactions
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 CoSybased
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/ publications/
xcellonline/run-fast-with-Vivado-HLS.pdf, last accessed 2021/03/10 (accessed 18 November
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 reconfigurable
systems programming, In: communications in computer and information science, 2019,
Vol. 1129, Chapter parallel computing technologies, pp. 1-16.
