О параллельном моделировании кинетических процессов методом Монте-Карло (посвящается памяти Главного Теоретика Космонавтики академика М.В. Келдыша в год 60-летия запуска первого ИСЗ)

Авторы

  • М.А. Марченко Институт вычислительной математики и математической геофизики СО РАН (ИВМиМГ СО РАН)
  • Т.А. Сушкевич Институт прикладной математики имени М.В. Келдыша РАН (ИПМ РАН) https://orcid.org/0000-0002-5531-3595

DOI:

https://doi.org/10.26089/NumMet.v18r436

Ключевые слова:

Keywords: information and mathematical software, kinetic processes, Monte Carlo method, distributed parallel computing

Аннотация

В 2017 году мировая общественность отмечает 60-летний юбилей запуска 4 октября 1957 года в СССР первого искусственного спутника Земли, положившего начало космической эры. Баллистические расчеты проводились на первой серийной ЭВМ «Стрела» в Институте Келдыша. При решении сложнейших задач создания «ракетно-ядерного щита» были заложены основы новых направлений в математике — вычислительной математики и математического моделирования. И в СССР и в США параллельно разрабатывались детерминированные и статистические численные методы. Методы Монте-Карло (ММК) как инструмент для прямого статистического моделирования были разработаны в США в рамках Манхэттонского проекта создания ядерного оружия. Джон фон Нейман первым предложил использовать саму ЭВМ для генерации случайных чисел. В 1949 году Джон фон Нейман и Станислав Улам предложили первый алгоритм получения псевдослучайных величин, который впоследствии был назван ММК и послужил основой для развития методики генерации псевдослучайных чисел с использованием ЭВМ. Разработка ММК и эффективность его применения всегда начинается с разработки генератора случайных или псевдослучайных чисел, который зависит от класса решаемых задач и конкретной структуры и архитектуры ЭВМ. Методы Монте-Карло стали массово применять на всех архитектурах вычислительных систем с параллельными и распределенными вычислениями. Сейчас в эпоху супервычислений преобладают ММК как следствие простоты их реализации. Но эта простота обманчива. В статье представлен разработанный отечественный комплексный методический подход, в котором на примере трех сложных «больших» задач, описывающих пространственно-неоднородные кинетические процессы диффузии, коагуляции и переноса заряженных частиц, системно рассматриваются теория методов и алгоритмов ММК и практика их реализации в формате не просто программ, а также параллельных генераторов псевдослучайных чисел, библиотек программ, средств обработки данных, управляющих программ и т.д., т.е. все этапы создания «цифрового продукта». На примере вероятностных моделей для численного моделирования кинетических процессов диффузии, коагуляции и переноса заряженных частиц, когда ансамбли траекторий или частиц содержат по 10 в 7-13 степени элементов, продемонстрированы возможности и эффективность новых параллельных алгоритмов и распределенных вычислений ММК для решения «больших» и «сложных» задач не только для расчета отдельных функционалов или оценок, но и для всего фазового объема задачи. Это важнейшее достижение, которое повышает конкурентность ММК с детерминированными конечно-разностными и сеточными методами при параллельном моделировании.

Авторы

М.А. Марченко

Институт вычислительной математики и математической геофизики СО РАН (ИВМиМГ СО РАН)
просп. Лаврентьева, 6, 630090, Новосибирск
• заведующий лабораторией

Т.А. Сушкевич

Институт прикладной математики имени М.В. Келдыша РАН (ИПМ РАН)
Миусская пл., 4, 125047, Москва
• главный научный сотрудник

Библиографические ссылки

  1. 4 oktjabrja 1957 goda nachalo kosmicheskoj jery. Pervaja kosmicheskaja [October 4, 1957 the beginning of the space age. The first space. Collection of articles dedicated to the fiftieth anniversary of the launch of the First artificial Earth sputnik]. Moscow, SRI RAS, OOO &quotRegion Invest&quot , 2007. 169 p.
  2. Prikladnaja nebesnaja mehanika i upravlenie dvizheniem [Applied Celestial Mechanics and Motion Control. Collection of papers dedicated to the 90th anniversary of the birth of D.E. Okhotsimsky]. Moscow, KIAM RAS, 2010. 368 p. URL:
    http://keldysh.ru/memory/okhotsimsky/index.htm
  3. Begieva-Kuchmezova R. Svet zvezdy i svechi... K 90-letiju Timura Magometovicha Jeneeva [Light of a star and a candle... To the 90th anniversary of Timur Magometovich Eneev]. Moscow, KIAM RAS, 2015. 192 p.
  4. Keldysh M.V. Tvorcheskii portret po vospominaniyam sovremennikov [Creative portrait on the memoirs of contemporaries]. Moscow, Nauka, 2001. 416 p.
  5. Mstislav Vsevolodovich Keldysh. 100 let so dnja rozhdenija [Mstislav Vsevolodovich Keldysh. 100th Birthday Anniversary]. Yaroslavl, Publishing OOO RMP, 2011. 344 p.
  6. Mstislav Keldysh [Mstislav Keldysh. The series &quotGREAT MINDS of Russia&quot under the editorship of V.S.Gubarev]. Moscow, Publishing house &quotKomsomolskaya Pravda&quot , 2016. Issue 2. 96 p.
  7. Informacionnaja sistema &quotArhivy Rossijskoj akademii nauk&quot (ISARAN): Fond M.V. Keldysha (Nauchnye trudy i materialy k nim, biograficheskie dokumenty, dokumenty po dejatel’nosti, perepiska, trudy i materialy drugih lic) [Information system &quotArchives of the Russian Academy of Sciences&quot (ISARAN): M.V. Keldysh Foundation (Scientific works and materials to them, biographical documents, activity documents, correspondence, works and materials of other persons)]. (accessed 12.04.2017) URL:
    http://isaran.ru/?q=ru/opis-guid=31F9162F-4408-4E75-A1B2-A76BF7C46345-ida=48 (in Russian)
  8. Tihonov A.N. Sobranie nauchnyh trudov. Tom 2. Matematika: Vychislitel’naja matematika. 1956-1979. Matematicheskaja fizika. 1933-1948. [Collection of scientific works. Vol. 2. Mathematics: Computational Mathematics. 1956-1979. Mathematical physics. 1933-1948. Editor and compiler T.A. Sushkevich, A.V. Gulin]. Moscow, Nauka, 2009. 590 p.
  9. Kuznetsov E.S. Izbrannye nauchnye trudy (v svyazi so 100-letiem so dnya rozhdeniya). Otvet. redaktor i sostavitel’ Sushkevich T.A. [Selected scientific papers (in connection with the 100th anniversary of his birth). Editor and compiler Sushkevich T.A.]. Moscow, FIZMATLIT, 2003. 784 p.
  10. Vladimirov V.S. Matematicheskie zadachi odnoskorostnoj teorii perenosa chastic [Mathematical problems of the one-velocity theory of particle transfer].Trudy MIAN im. V.A. Steklov. Vol. LXI (61). Moscow, Publishing of Academy of Sciences of USSR, 1961. 158 p.
  11. Marchuk G.I. Chislennye metody rascheta jadernyh reaktorov [Numerical methods for calculating nuclear reactors]. Moscow, Atomizdat, 1958. 381 p.
  12. Chentsov N.N. Izbrannye trudy. Matematika [Selected works. Mathematics]. Moscow, FIZMATLIT, 2001. 400 p.
  13. Ermakov S.M., Mihajlov G.A. Statisticheskoe modelirovanie [Statistical modeling]. Moscow, FIZMATLIT, 1982. 296 p.
  14. Marchuk G.I., Mihajlov G.A., Nazaraliev M.A., Darbinjan R.A. Reshenie prjamyh i nekotoryh obratnyh zadach atmosfernoj optiki metodom Monte-Karlo [The solution of some direct and inverse problems of atmospheric optics by Monte Carlo method]. Novosibirsk, Nauka, 1968. 100 p.
  15. Metod Monte-Karlo v atmosfernoj optike. Pod red. G.I. Marchuka [Monte-Carlo method in atmospheric optics. Editor G.I. Marchuk]. Novosibirsk, Nauka, 1976. 283 p.
  16. Buslenko N.P., Golenko D.I., Sobol’ I.M., Sragovich V.G., Shrejder Ju.A. Metod statisticheskih ispytanij (metod Monte-Karlo) [The method of statistical tests (Monte Carlo method)]. Moscow, GIFML, 1962. 334 p.
  17. Sobol’ I.M. Metod Monte-Karlo. Populjarnye lekcii po matematike [The Monte Carlo method. Popular lectures on mathematics]. Moscow, Nauka, 1968. 64 p.
  18. Sobol’ I.M. Chislennye metody Monte-Karlo [Numerical Monte Carlo methods]. Moscow, FIZMATLIT, 1973. 312 p.
  19. Nicholas Metropolis, Stanislaw Ulam. The Monte Carlo method // J. Amer. statistical assoc. 1949. Vol. 44, № 247. P. 335-341.
  20. Albert G.E. A general theory of stochastic estimates of the Neumann series for the solution of certain Fredholm integral equations and related series // Sympos. on Monte Carlo Methods, ed. H.A.Meyer, Wiley. 1956. P. 37-46.
  21. Chavchanidze V.V. Metod sluchajnyh ispytanij (metod Monte-Karlo). Trudy Instituta fiziki AN Gruzinskoj SSR [Method of random testing (Monte Carlo method). Proceedings of Institute of physics, Academy of Sciences of the Georgian SSR]. 1955. Vol. 3. P. 105. (in Russian)
  22. Chavchanidze V.V. The application of the random test method to the calculation of the intranuclear cascade. Izvestija AN SSSR, serija fizicheskaja [Izvestija of Academy of Sciences of the USSR. Physical series]. 1955. Vol. 19, № 6. P. 629-638. (in Russian)
  23. Shrejder Ju.A. Method of statistical samples (Monte-Carlo method) and its use in digital computers. Priborostroenie [Instrument engineering]. 1955, № 7, P. 1-5. (in Russian)
  24. Vladimirov V.S. On the application of the Monte Carlo method for finding the smallest characteristic number and the corresponding eigenfunction of the linear integral equation. Teorija verojatnostej i ee primenenija [Theory of probability and its applications]. 1956, Vol. 1, № 1. P. 113-130. (in Russian)
  25. Voevodin V.V. Nekotorye mashinnye aspekty rasparallelivanija vychislenij [Some machine aspects of parallelization]. Moscow, VINITI (Preprint № 22), 1981. 10 p.
  26. Voevodin V.V., Voevodin Vl.V. Parallel’nye vychislenija [Parallel computing]. SPb: BHV-Peterburg, 2002. 608 p.
  27. Voevodin V.V. Vychislitel’naja matematika i struktura algoritmov. Serija &quotSuperkomp’juternoe obrazovanie&quot [Computational mathematics and algorithms. Series: &quotSupercomputing education&quot )]. Moscow, Publising of M.V.Lomonosov Moscow State University, 2010. 168 p.
  28. Jakobovskij M.V. Vvedenie v parallel’nye metody reshenija zadach. Serija &quotSuperkomp’juternoe obrazovanie&quot [Introduction to parallel methods for solving problems. Series: &quotSupercomputing education&quot )]. Moscow, Publishing of M.V.Lomonosov Moscow State University, 2013. 328 p.
  29. Sushkevich T.A., Strelkov S.A., Ioltuhovskij A.A. Metod harakteristik v zadachah atmosfernoj optiki [The method of characteristics in problems of atmospheric optics]. Moscow, Nauka, 1990. 296 p.
  30. Sushkevich T.A. Matematicheskie modeli perenosa izlucheniya [Mathematical models of radiation transfer]. Moscow, Binom. Laboratory of Knowledge, 2005. 661 p.
  31. Sushkevich T.A., Kozoderov V.V., Kondranin T.V., Strelkov S.A., Dmitriev E.V., Maksakova S.V. Parallel computations in problems of space environmental monitoring and hyperspectral remote sensing. Nauchnyj servis v seti Internet: poisk novyh reshenij: Trudy mezhdunarodnoj superkomp’juternoj konferencii, (Novorossijsk, 17-22 sentjabrja 2012) [Scientific Service in the Internet: the Search for New Solutions: Proceedings of the International Supercomputing Conference (Novorossiysk, Russia, September, 17-22, 2012)]. Moscow, Publishing of M.V.Lomonosov Moscow State University, 2012. P. 320-324. (in Russian)
  32. Sushkevich T.A., Strelkov S.A., Maksakova S.V. Information and mathematical software for the aerospace systems of remote sensing and the radiation forcing on the Earth’s climate to predict the consequences of development of the Arctic region and computing. Superkomp’juternye Dni v Rossii: Trudy mezhdunarodnoj konferencii (Moscow, 28-29 sentjabr’) [Supercomputer Days in Russia: Proceedings of the International Conference (Moscow, Russia, September, 28-29, 2015)]. Moscow, Publishing of M.V.Lomonosov Moscow State University, 2015. P. 163-169. (in Russian)
  33. Ermakov S.M., Sipin A.S. Metod Monte-Karlo i parametricheskaja razdelimost’ algoritmov [The Monte Carlo method and the parametric separability of algorithms]. Saint Petersburg, Publishing of St. Petersburg University, 2014. 248 p.
  34. Artem’ev S.S., Marchenko M.A., Korneev V.D., Jakunin M.A., Ivanov A.A., Smirnov D.D. Analiz stohasticheskih kolebanij metodom Monte-Karlo na superkomp’juterah [Analysis of stochastic oscillations by the Monte Carlo method on supercomputers]. Novosibirsk, Publishing of SB RAS, 2016. 294 p.
  35. Marchenko M.M. Chislennoe statisticheskoe modelirovanie kineticheskih processov diffuzii, koaguljacii i perenosa zarjazhennyh chastic s ispol’zovaniem raspredeljonnyh vychislenij. Dissert. doktor. fiz-mat. nauk [Numerical statistical modeling of the kinetic processes of diffusion, coagulation and transport of charged particles using distributed computations. Dissert. doktor. fiz-mat. nauk]. Novosibirsk, ICMMG SB RAN, 2017. 281 p.
    https://icmmg.nsc.ru/ru/content/marchenko-mihail-aleksandrovich-0
  36. The Marsaglia Random Number CDROM including the Diehard Battery of Tests of Randomness.
    http://stat.fsu.edu/pub/diehard/ 31.08.2016.
  37. Knut D.E. Iskusstvo programmirovanija. T. 2. Poluchislennye algoritmy. Perevod s angl. 3-e izdanie [The Art of Computer Programming. Vol. 2. Seminumerical Algorithms. (The translation from English. 3rd Edition)]. Moscow, Williams, 2001. 832 p.
  38. Barash L.Ju., Shhur L.N. Generacija sluchajnyh chisel i parallel’nyh potokov sluchajnyh chisel dlja raschetov Monte-Karlo. Modelirovanie i analiz informacionnyh system [Modeling and analysis of information systems]. 2012, Vol. 19, № 2. P. 145-161. (in Russian)
  39. Barash L.Y., Shchur L.N. Program library for random number generation. More generators, parallel streams of random numbers and Fortran compatibility // Computer Physics Communications. 2013. Vol. 184. P. 2367-2369.

Загрузки

Опубликован

2017-10-22

Как цитировать

Марченко М.А., Сушкевич Т.А. О параллельном моделировании кинетических процессов методом Монте-Карло (посвящается памяти Главного Теоретика Космонавтики академика М.В. Келдыша в год 60-летия запуска первого ИСЗ) // Вычислительные методы и программирование. 2017. 18. 434-446. doi 10.26089/NumMet.v18r436

Выпуск

Раздел

Раздел 1. Вычислительные методы и приложения