Аннотация.

Работа посвящена разработке параллельных технологий для численного решения задач энтропийно-робастного оценивания характеристик рандомизированных моделей при малом объеме данных. Предлагается использовать итерационный алгоритм, базирующийся на пакетных итерациях Монте Карло. Алгоритм вместе с большим объемом вычислений, потенциально обладает высокой степенью параллелизма по данным, поэтому его реализация ориентирована на современные вычислительные системы, допускающие массивно-параллельную обработку на разных уровнях параллелизма. Реализация алгоритма ориентирована на стек технологий MPI+OpenMP+CUDA, которые эффективно отображаются на современные гетерогенные архитектуры вычислительных систем. Работоспособность и эффективность предлагаемой технологии подтверждается экспериментальными исследованиями на тестовой задаче.

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

энтропийно-робастное оценивание, параллельные вычисления, Монте Карло, пакетные итерации, гетерогенная архитектура.

Стр. 51-60.

A.Y. Popkov, D.V. Zubarev

"Parallel implementation of the algorithm for solving entropy-robust estimation problem on heterogeneous computer systems"

Paper is devoted to development of parallel technologies for numerical solving of problems to entropy-robust estimation of randomized models’ characteristics under limited amount of data. We propose to use an iterative algorithm based on batch Monte Carlo iterations. The algorithm being very computational intensive, potentially possesses high level of parallelism. Its implementation is aimed to modern computer systems with massive-parallel processing. The implementation is aimed to MPI+OpenMP+CUDA technology stack, which can be effectively mapped to modern heterogeneous computer architectures. Workability and efficiency of proposed technologies have been approved by experiments on test problem.

Keywords: entropy-robust estimation, parallel computing, Monte Carlo, batch iterations, heterogeneous architecture.

 Полная версия статьи в формате pdf.

REFERENCES

1. Kendal M.D., Styuart A. Statisticheskie vyvody i svyazi. − M.: Nauka, 1973.
2. Kramer G. Matematicheskie metody statistiki. − M.: Mir, 1975.
3. Kobzar A.I. Prikladnaya matematicheskaya statistika. − M. : Fizmatlit, 2006.
4. Ayvazyan S.A., Mkhitaryan V.S. Prikladnaya statistika i osnovy ekonometriki. − M.: Yuniti, 2001.
5. Golan A., Judge G., Miller D. Maximum Entropy Econometrics: Robust Estimation with Limited Data. − New York: John Wiley & Sons, 1996.
6. Golan A. Information and entropy econometrics - a review and synthesis // Foundation and Trends in Econometrics. 2006. Vol. 2, No. 1-2. P. 1–145.
7. Shiryaev A. N. Stokhasticheskaya finansovaya matematika. − M.: Nauka, 2002.
8. Polyak B.T., Shcherbakov P.S. Robastnaya ustoychivost i upravlenie. − M.: Nauka, 2002.
9. Vapnik V.N., Chervonenkis A.Ya. Teoriya raspoznavaniya obrazov. − M.: Nauka, 1974.
10. Merkov A.B. Raspoznavanie obrazov: Vvedenie v metody statisticheskogo obucheniya. − M. : URSS, 2011.
11. Merkov A.B. Raspoznavanie obrazov: Postroenie i obuchenie veroyatnostnykh modeley. − M.: LYeNAND, 2014.
12. Popkov Yu.S., Popkov A.Yu., Lysak Yu.V. Otsenivanie kharakteristik randomizirovannykh staticheskikh modeley dannykh (entropiyno-robastnyy podkhod) // Avtomatika i telemekhanika. 2013. № 11. S. 114–131.
13. Popkov Yu.S., Popkov A.Yu., Lysak Yu.V. Otsenivanie kharakteristik randomizirovannykh dinamicheskikh modeley dannykh (entropiyno-robastnyy podkhod) // Avtomatika i telemekhanika. 2013. № 5. S. 83–90.
14. Darkhovskiy B.S., Popkov A.Yu., Popkov Yu.S. Metod paketnykh iteratsiy Monte Karlo dlya resheniya sistem nelineynykh uravneniy i neravenstv: veroyatnostnye kharakteristiki // Avtomatika i telemekhanika. 2015. № 5. S. 87–98.
15. Darkhovskiy B.S., Popkov A.Yu., Popkov Yu.S. Iteratsionnyy MK-algoritm resheniya zadach globalnoy optimizatsii // Avtomatika i telemekhanika. 2015, v pechati.
16. Boltsman L. O svyazi mezhdu vtorym nachalom mekhanicheskoy teorii teploty i teoriey veroyatnostey v teoremakh o teplovom ravnovesii // Boltsman L.E. Izbrannye trudy. Seriya «Klassiki nauki.» / Pod red. L.S. Shlak. − M.: Nauka, 1984.
17. Mittal S., Vetter J.S. A Survey of CPU-GPU Heterogeneous Computing Techniques // ACM Computing Surveys. 2015. Vol. 47, No. 4. P. 1–35.
18. Vajda A. Multi-core and many-core processor architectures // Programming Many-Core Chips / Ed. by András Vajda. − Boston, MA: Springer US, 2011. P. 9–43.
19. Dongarra J.J. Sourcebook of parallel computing. – San Francisco CA : Morgan Kaufmann Publishers, 2003.
20. Voevodin V. V., Voevodin Vl. V. Parallelnye vychisleniya. − SPb.: BKhV-Peterburg, 2004.
21. Bell N., Hoberock J. Thrust: A Productivity-Oriented Library for CUDA // GPU Computing Gems Jade Edition / Ed. by Wen-mei W. Hwu. − San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 2011. P. 359–371.
22. Thrust — Parallel Algorithms Library. URL: http://thrust.github.io/ (Data obrashcheniya: 2.11.2015).
23. OpenMP Specifications. URL: http://openmp.org/wp/openmp-specifications/ (Data obrashcheniya: 2.11.2015).
24. Threading Building Blocks Documentation. URL: https://www.threadingbuildingblocks.org/ documentation/(Data obrashcheniya: 2.11.2015).
25. About CUDA. URL: https://developer.nvidia.com/about-cuda (Data obrashcheniya: 2.11.2015).__
26. Lin C., Snyder L. Principles of parallel programming. − Boston, MA : Pearson/Addison Wesley, 2009.
27. STL Function Objects. URL: http://www.sgi.com/tech/stl/functors.html (Data obrashcheniya: 2.11.2015).
28. Sobol I.M. Metod Monte-Karlo. − M.: Nauka, 1968.
29. Sobol I.M. Chislennye metody Monte-Karlo. − M.: Nauka, 1973.
30. Tesla M2050 / M2070 GPU Computing Module. URL: http://www.nvidia.co.uk/object/ product_tesla_M2050_ M2070_uk.html (Data obrashcheniya: 2.11.2015).
31. NVidia Tesla Kepler Family Datasheet. URL: http://www.nvidia.com/content/tesla/pdf/ nvidia-teslakepler-family-datasheet.pdf (Data obrashcheniya: 2.11.2015).
32. Kirk D., Hwu Wen-mei. Programming massively parallel processors: A Hands-on approach. 2nd edition. − Amsterdam and Boston: Elsevier/Morgan Kaufmann, 2013.