Просмотр статьи


Номер журнала: 2019.3

Заголовок статьи: Подход к построению системы детерминированного параллельного программирования на основе монотонных объектов

Резюме

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

Авторы

А. И. Адамович, А. В. Климов

Библиография

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 Pro-gramming / 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.

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

модели параллельных вычислений, детерминированные программы, функциональное программирование, объектно-ориентированное программирование, монотонные объекты

Скачать полный текст