Как создавать параллельные программы, детерминированные по построению? Постановка проблемы и обзор работ

Автор: Адамович Алексей Игоревич, Климов Андрей Валентинович

Журнал: Программные системы: теория и приложения @programmnye-sistemy

Рубрика: Программное и аппаратное обеспечение распределенных и суперкомпьютерных систем

Статья в выпуске: 4 (35) т.8, 2017 года.

Бесплатный доступ

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

Еще

ID: 143164275 Короткий адрес: https://sciup.org/143164275

Список литературы Как создавать параллельные программы, детерминированные по построению? Постановка проблемы и обзор работ

А. И. Адамович. Струи как основа реализации понятия Т-процесса для платформы JVM//Программные системы: теория и приложения, Т. 6, № 4. (27) 2015. С. 177-195, URL: http://psta.psiras.ru/read/psta2015_4_177-195.pdf
А. И. Адамович. Язык программирования Ajl: автоматическое динамическое распараллеливание для платформы JVM//Программные системы: теория и приложения, Т. 7, № 4. (31) 2016. С. 83-117, URL: http://psta.psiras.ru/read/psta2015_4_177-195.pdf
А. И. Адамович, Анд. В. Климов. Об опыте использования среды метапрограммирования Eclipse/TMF для конструирования специализированных языков//Научный сервис в сети Интернет, Труды XVIII Всероссийской научной конференции (19-24 сентября 2016 г., г. Новороссийск), ИПМ им. М.В. Келдыша, М., 2016. С. 3-8, URL: http://keldysh.ru/abrau/2016/45.pdf
R.L̇. Bocchino (Jr.), V. S. Adve, S. V. Adve, M. Snir. "Parallel Programming Must Be Deterministic by Default", Fifth USENIX Conference on Hot Topics in Parallelism, HotPar'09, USENIX Association, Berkeley, CA, USA, 2009. P. 4-4.
J. R. Gurd, C. C. Kirkham, I. Watson. "The Manchester Prototype Dataflow Computer", Commun. ACM, V. 28. No. 1. 1985. P. 34-52.
K. Hammond, G. Michelson (eds.). Research Directions in Parallel Functional Programming, Springer-Verlag, London, UK, UK, 2000.
С. М. Абрамов, А. И. Адамович, М. Р. Коваленко. Т-система -среда программирования с поддержкой автоматического динамического распараллеливания программ. Пример реализации алгоритма построения изображений методом трассировки лучей//Программирование, Т. 25, № 2. 1999. С. 100-107.
And. V. Klimov. "Dynamic Specialization in Extended Functional Language with Monotone Objects", SIGPLAN Not., V. 26. No. 9. 1991. P. 199-210.
W. D. Hillis, G. L. Steele (Jr.). "Data Parallel Algorithms", Commun. ACM, V. 29. No. 12. 1986. P. 1170-1183.
R. S. Nikhil. ID Language Reference Manual, Tech. Rep. CSG Memo 284-2, MIT Lab. for Computer Science, Massachusetts Institute of Technology, Cambridge, MA, 1991.
А. Н. Андрианов, К. Н. Ефимкин, И. Б. Задыхайло. Непроцедурный язык для решения задач математической физики//Программирование, 1991, №2. С. 80-84.
А. Н. Андрианов, Т. П. Баранова, А. Б. Бугеря, К. Н. Ефимкин. Трансляция непроцедурного языка Норма для графических процессоров//Препринты ИПМ им. М.В. Келдыша, 2016, 073, 24 с.
Hadoop: MapReduce Tutorial, https://hadoop.apache.org/docs/stable/hadoop-mapreduce-client/hadoop-mapreduce-client-core/MapReduceTutorial.html, Apache Hadoop, 2017.
Дж. Блох. Java. Эффективное программирование, Лори, М., 2014, ISBN: 978-5-85582-348-6.
The Rust Programming Language, Mozilla Research (Accessed Nov. 2017), URL: https://www.rust-lang.org
A. Potanin, J. Östlund, Y. Zibin, M. D. Ernst. "Immutability", Aliasing in Object-Oriented Programming, eds. D. Clarke, J. Noble, T. Wrigstad, Springer-Verlag, Berlin-Heidelberg, 2013. P. 233-269.
M. Coblenz, J. Sunshine, J. Aldrich, B. Myers, S. Weber, F. Shull. "Exploring Language Support for Immutability", Proceedings of the 38th International Conference on Software Engineering, ICSE '16, ACM, New York, NY, USA, 2016. P. 736-747.
J. Östlund, T. Wrigstad, D. Clarke, B. Åkerblom. "Ownership, Uniqueness, and Immutability", Objects, Components, Models and Patterns, 46th International Conference, TOOLS EUROPE 2008 (Zurich, Switzerland, June 30-July 4, 2008), eds. R. F. Paige, B. Meyer, Springer, Berlin-Heidelberg, 2008. P. 178-197.
Y. Zibin, A. Potanin, P. Li, M. Ali, M. D. Ernst. "Ownership and Immutability in Generic Java", Proceedings of the ACM International Conference on Object Oriented Programming Systems Languages and Applications, OOPSLA '10, ACM, New York, NY, USA, 2010. P. 598-617.
M. Coblenz, W. Nelson, J. Aldrich, B. Myers, J. Sunshine. "Glacier: Transitive Class Immutability for Java", Proceedings of the 39th International Conference on Software Engineering, ICSE '17, IEEE Press, Piscataway, NJ, USA, 2017. P. 496-506.
R.L̇. Bocchino (Jr.), V. S. Adve, D. Dig, S. V. Adve, S. Heumann, R. Komuravelli, J. Overbey, P. Simmons, H. Sung, M. Vakilian. "A Type and Effect System for Deterministic Parallel Java", SIGPLAN Not., V. 44. No. 10. 2009. P. 97-116.
M. Kawaguchi, P. Rondon, A. Bakst, R. Jhala. "Deterministic Parallelism via Liquid Effects", ACM SIGPLAN Not., V. 47. No. 6. 2012. P. 45-54.
Arvind, R. S. Nikhil, K. K. Pingali. "I-structures: Data Structures for Parallel Computing", ACM Trans. Program. Lang. Syst., V. 11. No. 4. 1989. P. 598-632.
G. Kahn. "The Semantics of Simple Language for Parallel Programming", IFIP Congress, 1974. P. 471-475.
M. G. Burke, K. Knobe, R. Newton, V. Sarkar. "Concurrent Collections Programming Model", Encyclopedia of Parallel Computing, ed. D. Padua, Springer, Boston, MA, 2011. P. 364-371.
L. Kuper. Lattice-based Data Structures for Deterministic Parallel and Distributed Programming, Ph.D. Thesis, 2015,URL: http://www.cs.indiana.edu/~lkuper/papers/lindsey-kuper-dissertation.pdf
L. Kuper, A. Todd, S. Tobin-Hochstadt, R. R. Newton. "Taming the Parallel Effect Zoo: Extensible Deterministic Parallelism with LVish", ACM SIGPLAN Not., V. 49. No. 6. 2014. P. 2-14.
R. Alverson, D. Callahan, D. Cummings, B. Koblenz, A. Porterfield, B. Smith. "The Tera Computer System", SIGARCH Comput. Archit. News, 18:3b 1990. P. 1-6.
L. Kuper, A. Turon, N. R. Krishnaswami, R. R. Newton. "Freeze After Writing: Quasi-deterministic Parallel Programming with LVars", ACM SIGPLAN Not., V. 49. No. 1. 2014. P. 257-270.
M. Shapiro, N. Preguiça, C. Baquero, M. Zawirski. "Conflict-free Replicated Data Types", Proceedings of the 13th International Conference on Stabilization, Safety, and Security of Distributed Systems, SSS'11, Springer-Verlag, Berlin-Heidelberg, 2011. P. 386-400.
L. Kuper, R. R. Newton. "LVars: Lattice-based Data Structures for Deterministic Parallelism", 2nd ACM SIGPLAN Workshop on Functional High-performance Computing, FHPC'13, ACM, New York, NY, USA, 2013. P. 71-84.
Анд. В. Климов. Детерминированные параллельные вычисления с монотонными объектами//Научный сервис в сети Интернет: многоядерный компьютерный мир. 15 лет РФФИ, Труды Всероссийской научной конференции (24-29 сентября 2007 г., г. Новороссийск), Изд-во Московского университета, М., 2007. С. 212-217.

Еще

Ред. заметка