An approach to deterministic parallel programming system construction based on monotonic objects
Abstract
Due to the explosive growth of the complexity of programs for multi-core processors and supercomputers, the idea of parallel computation with determinism guaranteed by the programming language and system is becoming increasingly significant. This paper analyzes the problem of making parallel programming as deterministic as possible and some of the existing approaches to its solution. It describes the principles of constructing the object-oriented programming system developed by the authors, which allows expert programmers to write both deterministic and non-deterministic code with guarantees to application developers that their programs are deterministic. The system and its input language have two levels: the higher level is intended for application developers; the lower level is for developers of class libraries referred to as monotonic. The input language of the higher-level subsystem is like a functional language with the possibility of creating and using immutable and monotonic objects. The libraries of monotonic classes ensure that all programs in the higher-level sublanguage that use only these classes are deterministic and idempotent when they are parallelized by asynchronous calls of all functions. Some representative applications implemented on this system are described.
About the Authors
A. I. Adamovich
Институт программных систем им. А. К. Айламазяна РАН
Russian Federation
Russian Federation
A. V. Klimov
Институт прикладной математики им. М. В. Келдыша РАН
Russian Federation
Russian Federation
References
1. Абрамов С. М., Адамович А. И., Коваленко М. Р. Т-система – среда программирования с поддержкой автоматического динамического распараллеливания программ. Пример реализации алгоритма построения изображений методом трассировки лучей // Программирование. 1999. Т. 25, № 2. С. 100–107.
2. Адамович А. И. Струи как основа реализации понятия Т-процесса для платформы JVM // Программные системы: теория и приложения. 2015. Т. 6, № 4. С. 177–195. DOI: 10.25209/2079-3316-2017-8-4-221-244.
3. Адамович А. И. Язык программирования Ajl: автоматическое динамическое распараллеливание для платформы JVM // Программные системы: теория и приложения. 2016. Т. 7, № 4. С. 83–117. DOI: 10.25209/2079-3316-2016-7-4-83-117.
4. Адамович А. И., Климов А. В. Об опыте использования среды метапрограммирования Eclipse/TMF для конструирования специализированных языков // Научный сервис в сети Интернет: труды XVIII Всероссийской научной конференции. М.: ИПМ им. М. В. Келдыша РАН, 2016. С. 3–8. DOI: 10.20948/abrau-2016-45.
5. Адамович А. И., Климов А. В. Как создавать параллельные программы, детерминированные по построению? Постановка проблемы и обзор работ // Программные системы: теория и приложения. 2017. Т. 8, № 4. С. 221–244. DOI: 10.25209/2079-3316-2017-8-4-221-244.
6. Адамович А. И., Климов А.В. Принципы построения системы детерминированного параллельного программирования // Наукоемкое программное обеспечение: труды семинара 12-й Междунар. Ершовской конф. по информатике (ПCИ’19). 2–3 июля 2019 г., Новосибирск. С. 26–33. ISBN 978-5-4437-0909-3.
7. Андрианов А. Н., Баранова Т. П., Бугеря А. Б., Ефимкин К. Н. Трансляция непроцедурного языка Норма для графических процессоров // Препринты ИПМ им. М. В. Келдыша. 2016. № 73. 24 с. DOI: 10.20948/prepr-2016-73.
8. Климов А. В. Детерминированные параллельные вычисления с монотонными объектами // Научный сервис в сети Интернет: многоядерный компьютерный мир: труды Всероссийской научной конференции. М.: Изд-во Московского университета, 2007. С. 212–217.
9. Скин Д., Гринхол Д. Kotlin. Программирование для профессионалов. СПб.: Питер, 2020.
10. Adamovich A.I., Klimov A.V. Building Cyclic Data in a Functional-Like Language Extended with Monotonic Objects // X Workshop PSSV: Program Semantics, Specification and Verification: Theory and Applications. Abstracts. 2019. P. 11-19. ISBN 978-5-4437-0918-5.
11. Arvind, Nikhil R. S., Pingali K. K. I-structures: Data Structures for Parallel Computing // ACM Trans. Program. Lang. Syst. 1989. V. 11, № 4. P. 598–632. DOI: 10.1145/69558.69562.
12. Bocchino R. L. (Jr.), Adve V. S., Adve S. V., Snir M. Parallel Programming Must Be Deterministic by Default // Fifth USENIX Conference on Hot Topics in Parallelism, HotPar’09. USENIX Association, 2009.
13. Burke M. G., Knobe K., Newton R., Sarkar V. Concurrent Collections Programming Model // Encyclopedia of Parallel Computing / ed. D. Padua. Springer US, 2011. P. 364–371. DOI: 10.1007/978-0-387-09766-4_238.
14. Hammond K., Michelson G. (eds.). Research Directions in Parallel Functional Programming, London, UK: Springer, 1999.
15. Klimov A. V. Dynamic Specialization in Extended Functional Language with Monotone Objects // SIGPLAN Not. 1991. V. 26, № 9. P. 199–210. DOI: 10.1145/115865.376287.
16. Potanin A., Östlund J., Zibin Y., Ernst M. D. Immutability // Aliasing in Object-Oriented Programming / eds. D. Clarke, J. Noble, T. Wrigstad. LNCS 7850. Springer, 2013. P. 233–269.
17. Kahn G. The Semantics of a Simple Language for Parallel Programming // IFIP Congress, 1974. P. 471–475.
18. Kuper L. Lattice-based Data Structures for Deterministic Parallel and Distributed Programming, Ph.D. Thesis. IN, USA: Indiana University, 2015. 253 p.
19. Kuper L., Todd A., Tobin-Hochstadt S., Newton R. R. Taming the Parallel Effect Zoo: Extensible Deterministic Parallelism with LVish // ACM SIGPLAN Not. 2014. V. 49, № 6. P. 2–14. DOI: 10.1145/2666356.2594312.
20. Marlow S. Parallel and Concurrent Programming in Haskell. CA, USA: O’Reilly, 2013.
Review
For citations:
Adamovich A.I., Klimov A.V. An approach to deterministic parallel programming system construction based on monotonic objects. The Herald of the Siberian State University of Telecommunications and Information Science. 2019;(3):14-26. (In Russ.)
Views:
206
Email this article 
