sibsutisВестник СибГУТИThe Herald of the Siberian State University of Telecommunications and Information Science1998-6920СибГУТИsibsutis-86Research ArticleСтатьиПодход к построению системы детерминированного параллельного программирования на основе монотонных объектовAn approach to deterministic parallel programming system construction based on monotonic objectsАдамовичА. И.AdamovichA. I.

Адамович Алексей Игоревич, старший научный сотрудник Исследовательского центра мультипроцессорных систем

152021, Ярославская  обл., Переславский район, с. Веськово, ул. Петра Первого, д. 4 «а», тел. (4852) 695-228

lexa@adam.botik.ruКлимовА. В.KlimovA. V.

Климов Андрей Валентинович, старший научный сотрудник отдела «Программное обеспечение высокопроизводительных вычислительных систем и сетей»

125047, Москва, Миусская пл., д. 4, тел. (4852) 695-228

klimov@keldysh.ruИнститут программных систем им. А. К. Айламазяна РАНRussian FederationИнститут прикладной математики им. М. В. Келдыша РАНRussian Federation201919042022031426Copyright © Адамович А.И., Климов А.В., 20222022Адамович А.И., Климов А.В.Adamovich A.I., Klimov A.V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://vestnik.sibsutis.ru/jour/article/view/86

В связи с взрывным ростом сложности программ для многоядерных процессоров и суперкомпьютеров в последние десятилетия приобретает популярность и становится всё более актуальной идея параллельных вычислений с детерминированностью, гарантированной языком и системой программирования. В статье анализируется проблема, как сделать параллельное программирование как можно более детерминированным, а также некоторые существующие подходы к её решению. Описываются принципы построения системы объектно-ориентированного программирования, разрабатываемой авторами, предоставляющей возможность писать как детерминированный, так и недетерминированный код с гарантиями прикладному программисту, что его программа будет детерминированной. Система и входной язык имеют два уровня: верхний – для пользователей, разрабатывающих прикладные программы; нижний – для разработчиков библиотек классов, называемых монотонными. Входной язык подсистемы верхнего уровня похож на функциональный язык с возможностью создания и использования неизменяемых и монотонных объектов. Библиотеки монотонных классов гарантируют, что все программы на подъязыке верхнего уровня, использующие только монотонные классы, являются детерминированными и идемпотентными при их распараллеливании асинхронными вызовами всех функций. Обсуждаются показательные задачи, реализуемые на данной системе.

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.

модели параллельных вычисленийдетерминированные программыфункциональное программированиеобъектно-ориентированное программированиемонотонные объектыmodels of parallel computationdeterministic programsfunctional programmingobject-oriented programmingmonotonic objectsReferencesАбрамов С. М., Адамович А. И., Коваленко М. Р. Т-система – среда программирования с поддержкой автоматического динамического распараллеливания программ. Пример реализации алгоритма построения изображений методом трассировки лучей // Программирование. 1999. Т. 25, № 2. С. 100–107.Абрамов С. М., Адамович А. И., Коваленко М. Р. Т-система – среда программирования с поддержкой автоматического динамического распараллеливания программ. Пример реализации алгоритма построения изображений методом трассировки лучей // Программирование. 1999. Т. 25, № 2. С. 100–107.Адамович А. И. Струи как основа реализации понятия Т-процесса для платформы JVM // Программные системы: теория и приложения. 2015. Т. 6, № 4. С. 177–195. DOI: 10.25209/2079-3316-2017-8-4-221-244.Адамович А. И. Струи как основа реализации понятия Т-процесса для платформы JVM // Программные системы: теория и приложения. 2015. Т. 6, № 4. С. 177–195. DOI: 10.25209/2079-3316-2017-8-4-221-244.Адамович А. И. Язык программирования Ajl: автоматическое динамическое распараллеливание для платформы JVM // Программные системы: теория и приложения. 2016. Т. 7, № 4. С. 83–117. DOI: 10.25209/2079-3316-2016-7-4-83-117.Адамович А. И. Язык программирования Ajl: автоматическое динамическое распараллеливание для платформы JVM // Программные системы: теория и приложения. 2016. Т. 7, № 4. С. 83–117. DOI: 10.25209/2079-3316-2016-7-4-83-117.Адамович А. И., Климов А. В. Об опыте использования среды метапрограммирования Eclipse/TMF для конструирования специализированных языков // Научный сервис в сети Интернет: труды XVIII Всероссийской научной конференции. М.: ИПМ им. М. В. Келдыша РАН, 2016. С. 3–8. DOI: 10.20948/abrau-2016-45.Адамович А. И., Климов А. В. Об опыте использования среды метапрограммирования Eclipse/TMF для конструирования специализированных языков // Научный сервис в сети Интернет: труды XVIII Всероссийской научной конференции. М.: ИПМ им. М. В. Келдыша РАН, 2016. С. 3–8. DOI: 10.20948/abrau-2016-45.Адамович А. И., Климов А. В. Как создавать параллельные программы, детерминированные по построению? Постановка проблемы и обзор работ // Программные системы: теория и приложения. 2017. Т. 8, № 4. С. 221–244. DOI: 10.25209/2079-3316-2017-8-4-221-244.Адамович А. И., Климов А. В. Как создавать параллельные программы, детерминированные по построению? Постановка проблемы и обзор работ // Программные системы: теория и приложения. 2017. Т. 8, № 4. С. 221–244. DOI: 10.25209/2079-3316-2017-8-4-221-244.Адамович А. И., Климов А.В. Принципы построения системы детерминированного параллельного программирования // Наукоемкое программное обеспечение: труды семинара 12-й Междунар. Ершовской конф. по информатике (ПCИ’19). 2–3 июля 2019 г., Новосибирск. С. 26–33. ISBN 978-5-4437-0909-3.Адамович А. И., Климов А.В. Принципы построения системы детерминированного параллельного программирования // Наукоемкое программное обеспечение: труды семинара 12-й Междунар. Ершовской конф. по информатике (ПCИ’19). 2–3 июля 2019 г., Новосибирск. С. 26–33. ISBN 978-5-4437-0909-3.Андрианов А. Н., Баранова Т. П., Бугеря А. Б., Ефимкин К. Н. Трансляция непроцедурного языка Норма для графических процессоров // Препринты ИПМ им. М. В. Келдыша. 2016. № 73. 24 с. DOI: 10.20948/prepr-2016-73.Андрианов А. Н., Баранова Т. П., Бугеря А. Б., Ефимкин К. Н. Трансляция непроцедурного языка Норма для графических процессоров // Препринты ИПМ им. М. В. Келдыша. 2016. № 73. 24 с. DOI: 10.20948/prepr-2016-73.Климов А. В. Детерминированные параллельные вычисления с монотонными объектами // Научный сервис в сети Интернет: многоядерный компьютерный мир: труды Всероссийской научной конференции. М.: Изд-во Московского университета, 2007. С. 212–217.Климов А. В. Детерминированные параллельные вычисления с монотонными объектами // Научный сервис в сети Интернет: многоядерный компьютерный мир: труды Всероссийской научной конференции. М.: Изд-во Московского университета, 2007. С. 212–217.Скин Д., Гринхол Д. Kotlin. Программирование для профессионалов. СПб.: Питер, 2020.Скин Д., Гринхол Д. Kotlin. Программирование для профессионалов. СПб.: Питер, 2020.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.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.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.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.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.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.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.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.Hammond K., Michelson G. (eds.). Research Directions in Parallel Functional Programming, London, UK: Springer, 1999.Hammond K., Michelson G. (eds.). Research Directions in Parallel Functional Programming, London, UK: Springer, 1999.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.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.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.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.Kahn G. The Semantics of a Simple Language for Parallel Programming // IFIP Congress, 1974. P. 471–475.Kahn G. The Semantics of a Simple Language for Parallel Programming // IFIP Congress, 1974. P. 471–475.Kuper L. Lattice-based Data Structures for Deterministic Parallel and Distributed Programming, Ph.D. Thesis. IN, USA: Indiana University, 2015. 253 p.Kuper L. Lattice-based Data Structures for Deterministic Parallel and Distributed Programming, Ph.D. Thesis. IN, USA: Indiana University, 2015. 253 p.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.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.Marlow S. Parallel and Concurrent Programming in Haskell. CA, USA: O’Reilly, 2013.Marlow S. Parallel and Concurrent Programming in Haskell. CA, USA: O’Reilly, 2013.

The authors declare that there are no conflicts of interest present.