ОЦЕНКА ВОЗМОЖНОСТЕЙ ПЕРСПЕКТИВНЫХ ВЫЧИСЛИТЕЛЬНЫХ ТЕХНОЛОГИЙ ДЛЯ РАСЧЕТА ТОЧНЫХ ПРИБЛИЖЕНИЙ РАСПРЕДЕЛЕНИЙ ВЕРОЯТНОСТЕЙ ЗНАЧЕНИЙ СТАТИСТИК

  • А.К. Мельников АО «Вычислительные решения»
  • И.И. Левин Южный федеральный университет
  • А.И. Дордопуло НИЦ супер-ЭВМ и нейрокомпьютеров
  • Л.М. Сластен НИЦ супер-ЭВМ и нейрокомпьютеров
Ключевые слова: Вероятность, статистика, точное распределение, точное приближение, алгоритмическая сложность, квантовые вычисления, фотонные технологии, архитектурно- независимое программирование, язык Set@l

Аннотация

Статья посвящена оценке аппаратного ресурса вычислительных систем для решения
вычислительно-трудоемкой задачи – расчета распределений вероятностей значений ста-
тистик методом второй кратности на основе Δ-точных приближений для выборок объе-
мом от 320 до 1280 знаков при мощности алфавита от 128 до 256 символов с точностью
=10-5. Общее время решения не должно превышать 30 дней или 2,592·106 секунд при круг-
лосуточном режиме вычислений. Использование свойств метода второй кратности позво-
ляет привести вычислительную сложность расчета к диапазону 9,68·1022–1,60·1052 опера-
ций с числом проверяемых векторов – от 6,50·1023 до 1,39·1050. Решение этой задачи для
указанных параметров выборок в заданное время с помощью современных вычислительных
средств (процессоров, графических ускорителей, программируемых логических интеграль-
ных схем) требует недостижимого на практике аппаратного ресурса. Поэтому в статье
анализируются возможности перспективных квантовых и фотонных технологий для ре-
шения задачи с заданными параметрами. Основным преимуществом квантовых вычисли-
тельных систем является высокая скорость вычислений для всех возможных значений па-
раметров. Однако, для расчета распределений вероятностей значений статистик кванто-
вое ускорение не будет достигнуто из-за необходимости проверки всех полученных реше-
ний, число которых соответствует размерности задачи. Кроме того, текущий уровень
развития элементной базы не позволяет создавать и использовать квантовые вычислите-
ли с разрядностью 120 кубитов, необходимой для решения рассматриваемой задачи. Фо-
тонные вычислители могут обеспечить высокую скорость вычислений при низком энерго-
потреблении и для решения рассматриваемой задачи требуют наименьшее число узлов.
Однако, нерешенные проблемы с физической реализацией элементов оперативного хране-
ния данных и отсутствием доступной элементной базы не позволяют в обозримой пер-
спективе (5–7 лет) использовать фотонные вычислительные технологии для расчета рас-
пределений вероятностей значений статистик, поэтому наиболее целесообразно примене-
ние гибридных вычислительных систем, содержащих узлы различных архитектур.
Для реализации задачи на различных аппаратных платформах (универсальные процессоры,
графические ускорители, программируемые логические интегральные схемы) и конфигура-
циях гибридных вычислительных систем предложено использование архитектурно-
независимого языка программирования высокого уровня SET@L, объединяющего представ-
ление вычислений в виде множеств и совокупностей с помощью альтернативной теории
множеств П. Вопенка с абсолютным параллелизмом информационного графа и парадиг-
мами аспектно-ориентированного программирования.

Литература

1. 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 [TUSUR reports]. Tomsk,
2017, Vol. 20, No. 4, pp. 126-130. ISSN 1818-0442.
2. Mel'nikov A.K., Levin I.I., Dordopulo A.I., Pisarenko I.V. Analiz vozmozhnostey sovremennykh
vychislitel'nykh tekhnologiy dlya rascheta tochnykh priblizheniy raspredeleniy
veroyatnostey znacheniy statistik [Analysis of the possibilities of modern computing technologies
for calculating accurate approximations of probability distributions of statistical values],
Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2021, No. 7
(224), pp. 6-19. ISSN 1999-9429. DOI: 10.18522/2311-3103-2021-7-6-19.
3. Timonin V.I., Chernomordik O.M. Metod vychisleniya tochnogo raspredeleniya statistik tipa
Kolmogorova-Smirnova pri al'ternativakh Lemana [A method for calculating the exact distribution
of Kolmogorov-Smirnov type statistics with Lehman alternatives], Teoriya
veroyatnostey i ee primenenie [Probability theory and its application], 1985, Vol. 30, Issue 3,
pp. 572-573.
4. Tyannikova N.D, Timonin V.I. Metod vychisleniya tochnykh raspredeleniy statistik tipa
Kolmogorova-Smirnova v sluchae narusheniya odnorodnosti i nezavisimosti analiziruemykh
vyborok [Method for calculating exact distributions of Kolmogorov-Smirnov type statistics in case
of violation of uniformity and independence of the analyzed samples], Nauka i obrazovanie [Science
and Education], 2014, No. 11, pp. 227–237. DOI: 10.7463/1114.0740251 ISSN 1994-0448.
5. Raschet raspredeleniy metodom Monte-Karlo [Calculation of distributions by the Monte Carlo
method].
6. Feynman R.P. Simulating physics with computers, International Journal of Theoretical Physics,
1982, Vol. 21, Iss. 6, pp. 467-488. DOI: 10.1007/BF02650179.
7. Benioff P. Quantum mechanical hamiltonian models of turing machines, Journal of Statistical
Physics, 1982, Vol. 29, No. 3, pp. 515-546. DOI: 10.1007/BF01342185. Bibcode:
1982JSP....29..515B.
8. Valiev K.A., Kokin A.A. Kvantovye komp'yutery: nadezhdy i real'nost' [Quantum computers:
Hopes and Reality]. Izhevsk: RKHD, 2004, 320 p.
9. Manin Yu.I. Vychislimoe i nevychislimoe [Computable and non–computable]. Moscow: Sov.
radio, 1980, 128 p. (Cybernetics).
10. Moren K. Metody gil'bertova prostranstva [Methods of Hilbert space]. Moscow: Mir, 1965,
570 p.
11. Fiziki iz Rossii i SSHA sozdali pervyy 51-kubitnyy kvantovyy komp'yuter [Physicists from
Russia and the USA have created the first 51-qubit quantum computer]. Available at:
https://ria.ru/20170714/1498476410.html? (accessed 2 May 2022).
12. Kak Rossiya potratit 15 mlrd. na sozdanie kvantovogo komp'yutera [How will Russia spend 15
billion? to create a quantum computer]. Available at: https://gov.cnews.ru/articles/2020-01-
9_kak_rossiya_potratit_15_mlrd_na_sozdanie? (accessed 2 May 2022).
13. IonQ zayavila o sozdanii samogo moshchnogo v mire kvantovogo komp'yutera [IonQ has
announced the creation of the world's most powerful quantum computer]. Available at:
https://3dnews.ru/1060908/kompaniya-ion-q-soobshchila-o-sozdanii-samogo-moshchnogo-vmire-
kvantovogo-kompyutera? (accessed 2 May 2022).
14. IBM prodemonstrirovali kvantovyy komp'yuter s «kvantovym ob"emom» 64. Available at:
https://habr.com/ru/company/raiffeisenbank/news/t/516062/? (accessed 2 May 2022).
15. Stepanenko S.A. Fotonnaya vychislitel'naya mashina. Printsipy realizatsii. Otsenka parametrov [Photonic
computing machine. Principles of implementation. Estimation of parameters], Vychislitel'naya
tekhnika. Doklady Akademii nauk [Computer engineering. Reports of the Academy of Sciences].
Moscow, 2017, Vol. 476, No. 4, pp. 389-394. DOI: 10.1134/S1064562417050234.
16. Stepanenko S.A. Fotonnyy komp'yuter: struktura i algoritmy, otsenka parametrov [Photonic
computer: structure and algorithms, estimation of parameters], Fotonika [Photonics], 2017,
No. 7 / 67, pp. 72-83. DOI: 10.22184/1993-7296.2017.67.7.72.83.
17. Stepanenko S.A. Interferentsionnye logicheskie elementy [Interference logic elements], presented
by Academician of the Russian Academy of Sciences Yu.A. Trutnev. Doklady
Akademii nauk. Matematika, informatika, protsessy upravleniya [Reports of the Academy of
Sciences. Mathematics, Computer Science, Management processes]. Moscow, 2020, Vol. 493,
pp. 64-69. DOI: 10.31857/S2686954320040189.
18. Soifer V.A., Kharitonov S.I., Khonina S.N. etc. Spiral caustics of vortex beams, Photonics,
2021, Vol. 8, Issue 1, pp. 1-20. DOI: 10.3390/photonics8010024.
19. Soifer V.A., Doskolovich L.L., Bezus E.A. etc. Spatial differentiation of optical beams using a
resonant metal-dielectric-metal structure, Journal of Optics, 2021, Vol. 23, Issue 2.
DOI: 10.1088/2040-8986/abe63b.
20. Soifer V.A., Doskolovich L.L., Bezus E.A. etc. An Optical Differentiator Based on a Three-
Layer Structure with a W-Shaped Refractive Index Profile, Journal of Experimental and Theoretical
Physics, 2018, Vol. 127, Issue 2, pp. 202-209. DOI: 10.1134/S1063776118080174.
21. Levin I.I., Mel'nikov A.K. Upravlenie gibridnymi vychislitel'nymi sistemami na yazyke
SET@L [Management of hybrid computing systems in the SET@L language], Materiály XI
mezinárodní vědecko-praktická konference «Aktuální vymoženosti vědy – 2015» Díl 7.
Moderní informační technologie [Materials XI international scientific and practical conference
"current achievements of science-2015" Part 7. Modern information technology"]. Praha. Publishing
House «Education and Science», 2015. – 96 s. – P. 23-28. – ISSN 978-966-8736-05-6.
22. Levin I.I., Dordopulo A.I., Pisarenko I.V., Mel'nikov A.K. Podkhod k arkhitekturnonezavisimomu
programmirovaniyu vychislitel'nykh sistem na osnove aspektnoorientirovannogo
yazyka Set@l [Approach to architecture-independent programming of computing
systems based on aspect-oriented language Set@l], Izvestiya YuFU. Tekhnicheskie nauki
[Izvestiya SFedU. Engineering Sciences], 2018, No. 3, pp. 46-58.
23. Safonov V.O. Using Aspect-Oriented Programming for Trustworthy Software Development.
New York: John Wiley & Sons, 2008, 352 p.
24. Vopenka P. Al'ternativnaya teoriya mnozhestv: Novyy vzglyad na beskonechnost' [Alternative
Set Theory: A New View of Infinityъ: Transl. from Slavack. Novosibirsk: Izd-vo Instituta
matematiki, 2004, 612 p.
25. Levin I.I., Dordopulo A.I., Pisarenko I.V., Mel'nikov A.K. Opisanie algoritma resheniya sistem
lineynykh algebraicheskikh uravneniy metodom Yakobi na yazyke arkhitekturnonezavisimogo
programmirovaniya Set@l [Description of the algorithm for solving systems of
linear algebraic equations by the Jacobi method in the language of architecture-independent
programming Set@l], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering
Sciences], 2018, No. 5, pp. 34-48.
26. Levin I.I., Dordopulo A.I., Pisarenko I.V., Mel'nikov A.K. Arkhitekturno-nezavisimaya programma
bystrogo preobrazovaniya Fur'e na yazyke programmirovaniya SET@L [An architectureindependent
fast Fourier transform program in the SET@L programming language], Vestnik
RGRTU [Vestnik of RSREU], 2019, No. 68, pp. 28-36. ISSN 1995-4565. DOI: 10.21667/1995-
4565-2019-68-2-28-36. Available at: http://vestnik.rsreu.ru/ru/archive/2019/vypusk-68/805-1995-
4565-2019-68-2-28-36.
Опубликован
2022-11-01
Выпуск
Раздел
РАЗДЕЛ I. АНАЛИЗ ДАННЫХ И МОДЕЛИРОВАНИЕ