АНАЛИЗ ВОЗМОЖНОСТЕЙ СОВРЕМЕННЫХ ВЫЧИСЛИТЕЛЬНЫХ ТЕХНОЛОГИЙ ДЛЯ РАСЧЕТА ТОЧНЫХ ПРИБЛИЖЕНИЙ РАСПРЕДЕЛЕНИЙ ВЕРОЯТНОСТЕЙ ЗНАЧЕНИЙ СТАТИСТИК
Аннотация
В статье рассматривается решение вычислительно-трудоемкой задачи – расчета
распределений вероятностей значений статистик – с помощью современных вычисли-
тельных технологий. Для сокращения вычислительной сложности при обеспечении доста-
точного уровня эффективности критериев не ниже заданного порога предложено исполь-
зование Δ-точных приближений. Для расчета точных приближений используется метод
второй кратности, основанный на решении системы линейных уравнений, который позво-
ляет при заданном вычислительном ресурсе рассчитывать точные приближения для мак-
симальных значений параметров выборок. Наиболее трудоемкая часть метода второй
кратности состоит в процедуре последовательного получения векторов возможных реше-
ний и их проверки на принадлежность к самим решениям. Проверка векторов возможных
решений на принадлежность к решениям системы информационно независима, поэтому
алгоритм расчета можно распараллелить по данным. Приведена формула определения
алгоритмической сложности расчета точных приближений распределений вероятностей
значений статистик, на основе которой получены оценки сложности современных прак-
тических задач для выборок со следующими значениями (N, n) мощности алфавита и объё-
ма выборки: (256,1280), (128,640), (128, 320) и (192,3200) при точности расчета =10-5.
Вычислительная сложность расчета составляет от 9,68·1022 до 1,60·1052 операций, сред-
няя порядка 4,55·1025 операций, число проверяемых векторов – от 6,50·1023 до 1,39·1050, а
число решений – от 4,67·1012 до 5,60·1025 соответственно. Общее время решения при круг-
лосуточном режиме вычислений не должно превышать 30 дней или 2,592·106 сек. Для полу-
ченных оценок сложности проанализированы возможности современных кластерных вы-
числительных систем на основе универсальных процессоров, графических ускорителей и
реконфигурируемых вычислительных систем на основе программируемых логических инте-
гральных схем. Для каждой технологии определено число вычислительных узлов, требуе-
мых для расчета точных приближений с указанными параметрами в заданное время. По-
казано, что ни одна из рассмотренных вычислительных технологий на современном уровне
развития техники не позволяет получить решение для необходимых параметров расчета
точных приближений распределений вероятностей значений статистик. В заключении
сделан вывод о необходимости анализа возможностей перспективных вычислительных
технологий на основе квантовых и фотонных компьютеров, а также гибридных вычисли-
тельных систем для расчета точных приближений распределений вероятностей значений
статистик с заданными параметрами в оперативно-приемлемое время.
Литература
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.
