Parallel Algorithmic Processes and Their Complexity
DOI:
https://doi.org/10.24160/1993-6982-2020-3-102-110Keywords:
parallel processes, complexity estimationAbstract
A method for estimating the complexity of parallel processes according to the criteria of the average time of their absolutely parallel execution and the resources required for executing them (the number of nodes of the system performing the process) is proposed. These criteria are considered for a fairly general language of parallel processes, and their values can be used to judge how their real values obtained during the process on a particular system differ from their ultimately possible levels.
It is important to note that the considered language of parallel processes has been implemented on multi-core computers, and the operating means for effectively managing the execution of functional parallel programs have been developed on its basis. The functional parallel programming language that has been developed and successfully applied in practice is used as a language for describing parallel programs. The described methods for estimating the complexity of parallel processes are necessary at the stage of designing and optimizing functional parallel programs.
References
1. Кутепов В.П. О параллелизме с разных сторон // Параллельные вычисления и проблемы управления: Материалы V Междунар. конф. М: Институт проблем управления, 2010. С. 41—52.
2. Кутепов В.П., Фальк В.Н. Формы, языки представления, критерии и параметры сложности параллелизма // Программные продукты и системы. 2010. № 3. С. 16—25.
3. Кутепов В.П. Интеллектуальное управление процессами и загруженностью в параллельных системах // Известия РАН. Серия «Теория и системы управления». 2007. № 5. С. 58—73.
4. Кутепов В.П., Бражникова Ю.Н., Горицкий Ю.А., Панков Н.А. Исследование методов прогнозирования загруженности компьютеров и компьютерных систем // Программные продукты и системы. 2015. № 2. С. 135—147.
5. Кутепов В.П., Шамаль П.Н. Реализация языка функционального параллельного программирования FPTL на многоядерных компьютерах // Известия РАН. Серия «Теория и системы управления». 2014. № 3. С. 46—60.
6. Кутепов В.П. Модели и языки для описания параллельных процессов // Известия РАН. Серия «Теория и системы управления». 2018. № 3. С. 116—127.
7. Al Geist е. а. PVM: Parallel Virtual Machine. A User's Guide and Tutorial for Networked Parallel Computing. London: MIT Press, 1994.
8. Хьюз К., Хьюз Т. Параллельное и распределенное программирование с использованием C++. М.: Вильямс, 2004.
9. Cesarini F., Thompson S. ERLANG Programming: a Concurrent Approach to Software Development. Sebastopol: O'Really Media, 2009.
10. Carver R.H., Kuo-Chung Tai. Modern Multi-threading: Implementing, Testing, and Debugging Multithreaded Java/C++/Pthreads/Win32. N.-Y.: Wiley-Inters-cience, 2005.
11. Burstall R.M., Sannella D.T. HOPE: An Experimental Applicative Language // Proc. ACM Conf. on LISP and Functional Programming. 1980. P. 136—143.
12. Марлоу С. Параллельное и конкурентное программирование на языке Haskell. М.: ДМК Пресс, 2014.
13. Общая теория систем. М.: Мир, 1966.
14. Заде Л. Понятие состояния в теории систем // Общая теория систем. М.: Мир, 1966, С. 49—65.
15. Майхилл Дж. Абстрактная теория самовоспроизведения // Там же. С. 121—140.
16. Milner R. A Calculus of Communicating Systems Lecture Notes in Computer Science. N.-Y.: Springer-Verlag, 1980.
17. Хоар Ч. Взаимодействующие последовательные процессы. М.: Мир, 1989.
18. Кутепов В.П., Маланин В.Н., Панков Н.А. Граф-схемное потоковое параллельное программирование: язык, процессная модель, реализация на компьютерных системах // Известия РАН. Серия «Теория и системы управления». 2012. № 1. С. 67—82.
19. Кутепов В.П., Зубов М.И. Реализация и экспериментальное исследование эффективности упреждающего параллелизма // Вестник МЭИ. 2019. № 4. С. 119—126.
20. Питерсон Дж. Теория сетей Петри и моделирование систем. М.: Мир, 1984.
21. Бажанов С.Е., Воронцов М.М., Кутепов В.П., Шестаков Д.А. Структурный анализ и планирование процессов параллельного выполнения функциональных программ // Известия РАН. Серия «Теория и системы управления». 2005. № 6. С. 111—126.
22. Кутепов В.П., Фальк В.Н. Функциональные системы: теоретический и практический аспекты // Кибернетика. 1979. № 1. С. 46—58.
23. Кутепов В.П. Исчисление эквивалентности функциональных схем и параллельные алгоритмы // Программирование. 1979. № 6. С. 3—11.
---
Для цитирования: Кутепов В.П., Фальк В.Н. Алгоритмические параллельные процессы и их сложность // Вестник МЭИ. 2020. № 3. С. 102—110. DOI: 10.24160/1993-6982-2020-3-102-110.
---
Работа выполнена при поддержке: РФФИ (грант № 18-01-00548)
#
1. Kutepov V.P. O Parallelizme s Raznykh Storon. Parallel'nye Vychisleniya i Problemy Upravleniya: Materialy V Mezhdunar. Konf. M: Institut Problem Upravleniya, 2010:41—52. (in Russian).
2. Kutepov V.P., Fal'k V.N. Formy, Yazyki Predstavleniya, Kriterii i Parametry Slozhnosti Parallelizma. Programmnye Produkty i Sistemy. 2010;3:16—25. (in Rus- sian).
3. Kutepov V.P. Intellektual'noe Upravlenie Protsessami i Zagruzhennost'yu v Parallel'nykh Sistemakh. Izvestiya RAN. Seriya «Teoriya i Sistemy Upravleniya». 2007;5:58—73. (in Russian).
4. Kutepov V.P., Brazhnikova Yu.N., Goritskiy Yu.A., Pankov N.A. Issledovanie Metodov Prognozirovaniya Zagruzhennosti Komp'yuterov i Komp'yuternykh Sistem. Programmnye Produkty i Sistemy. 2015;2:135—147. (in Russian).
5. Kutepov V.P., Shamal' P.N. Realizatsiya Yazyka Funktsional'nogo Parallel'nogo Programmirovaniya FPTL na Mnogoyadernykh Komp'yuterakh. Izvestiya RAN. Seriya «Teoriya i Sistemy Upravleniya». 2014;3:46—60. (in Russian).
6. Kutepov V.P. Modeli i Yazyki dlya Opisaniya Parallel'nykh Protsessov. Izvestiya RAN. Seriya «Teoriya i Sistemy Upravleniya». 2018;3:116—127. (in Russian).
7. Al Geist e. a. PVM: Parallel Virtual Machine. A User's Guide and Tutorial for Networked Parallel Computing. London: MIT Press, 1994.
8. Kh'yuz K., Kh'yuz T. Parallel'noe i Raspredelennoe Programmirovanie s Ispol'zovaniem C++. M.: Vil'yams, 2004. (in Russian).
9. Cesarini F., Thompson S. ERLANG Programming: a Concurrent Approach to Software Development. Sebastopol: O'Really Media, 2009.
10. Carver R.H., Kuo-Chung Tai. Modern Multi-threading: Implementing, Testing, and Debugging Multithreaded Java/C++/Pthreads/Win32. N.-Y.: Wiley-Inters-cience, 2005.
11. Burstall R.M., Sannella D.T. HOPE: An Experimental Applicative Language. Proc. ACM Conf. on LISP and Functional Programming. 1980:136—143.
12. Marlou S. Parallel'noe i Konkurentnoe Programmirovanie na Yazyke Haskell. M.: DMK Press, 2014. (in Russian).
13. Obshchaya Teoriya Sistem. M.: Mir, 1966. (in Russian).
14. Zade L. Ponyatie Sostoyaniya v Teorii Sistem. Obshchaya Teoriya Sistem. M.: Mir, 1966:49—65. (in Russian).
15. Maykhill Dzh. Abstraktnaya Teoriya Samovosproizvedeniya. Tam zhe:121—140. (in Russian).
16. Milner R. A Calculus of Communicating Systems Lecture Notes in Computer Science. N.-Y.: Springer-Verlag, 1980.
17. Khoar Ch. Vzaimodeystvuyushchie Posledovatel'nye Protsessy. M.: Mir, 1989. (in Russian).
18. Kutepov V.P., Malanin V.N., Pankov N.A. Graf-skhemnoe Potokovoe Parallel'noe Programmirovanie: Yazyk, Protsessnaya Model', Realizatsiya na Komp'yuternykh Sistemakh. Izvestiya RAN. Seriya «Teoriya i Sistemy Upravleniya». 2012;1:67—82. (in Russian).
19. Kutepov V.P., Zubov M.I. Realizatsiya i Eksperimental'noe Issledovanie Effektivnosti Uprezhdayushchego Parallelizma. Vestnik MEI. 2019;4:119—126. (in Russian).
20. Piterson Dzh. Teoriya Setey Petri i Modelirovanie Sistem. M.: Mir, 1984. (in Russian).
21. Bazhanov S.E., Vorontsov M.M., Kutepov V.P., Shestakov D.A. Strukturnyy Analiz i Planirovanie Protsessov Parallel'nogo Vypolneniya Funktsional'nykh Programm. Izvestiya RAN. Seriya «Teoriya i Sistemy Upravleniya». 2005;6:111—126. (in Russian).
22. Kutepov V.P., Fal'k V.N. Funktsional'nye Sistemy: Teoreticheskiy i Prakticheskiy Aspekty. Kibernetika. 1979; 1:46—58. (in Russian).
23. Kutepov V.P. Ischislenie Ekvivalentnosti Funktsional'nykh Skhem i Parallel'nye Algoritmy. Programmirovanie. 1979;6:3—11. (in Russian).
---
For citation: Kutepov V.P., Falk V.N. Parallel Algorithmic Processes and Their Complexity. Bulletin of MPEI. 2020;3:102—110. (in Russian). DOI: 10.24160/1993-6982-2020-3-102-110.
---
The work is executed at support: RFBR (Grant No. 18-01-00548)
2. Кутепов В.П., Фальк В.Н. Формы, языки представления, критерии и параметры сложности параллелизма // Программные продукты и системы. 2010. № 3. С. 16—25.
3. Кутепов В.П. Интеллектуальное управление процессами и загруженностью в параллельных системах // Известия РАН. Серия «Теория и системы управления». 2007. № 5. С. 58—73.
4. Кутепов В.П., Бражникова Ю.Н., Горицкий Ю.А., Панков Н.А. Исследование методов прогнозирования загруженности компьютеров и компьютерных систем // Программные продукты и системы. 2015. № 2. С. 135—147.
5. Кутепов В.П., Шамаль П.Н. Реализация языка функционального параллельного программирования FPTL на многоядерных компьютерах // Известия РАН. Серия «Теория и системы управления». 2014. № 3. С. 46—60.
6. Кутепов В.П. Модели и языки для описания параллельных процессов // Известия РАН. Серия «Теория и системы управления». 2018. № 3. С. 116—127.
7. Al Geist е. а. PVM: Parallel Virtual Machine. A User's Guide and Tutorial for Networked Parallel Computing. London: MIT Press, 1994.
8. Хьюз К., Хьюз Т. Параллельное и распределенное программирование с использованием C++. М.: Вильямс, 2004.
9. Cesarini F., Thompson S. ERLANG Programming: a Concurrent Approach to Software Development. Sebastopol: O'Really Media, 2009.
10. Carver R.H., Kuo-Chung Tai. Modern Multi-threading: Implementing, Testing, and Debugging Multithreaded Java/C++/Pthreads/Win32. N.-Y.: Wiley-Inters-cience, 2005.
11. Burstall R.M., Sannella D.T. HOPE: An Experimental Applicative Language // Proc. ACM Conf. on LISP and Functional Programming. 1980. P. 136—143.
12. Марлоу С. Параллельное и конкурентное программирование на языке Haskell. М.: ДМК Пресс, 2014.
13. Общая теория систем. М.: Мир, 1966.
14. Заде Л. Понятие состояния в теории систем // Общая теория систем. М.: Мир, 1966, С. 49—65.
15. Майхилл Дж. Абстрактная теория самовоспроизведения // Там же. С. 121—140.
16. Milner R. A Calculus of Communicating Systems Lecture Notes in Computer Science. N.-Y.: Springer-Verlag, 1980.
17. Хоар Ч. Взаимодействующие последовательные процессы. М.: Мир, 1989.
18. Кутепов В.П., Маланин В.Н., Панков Н.А. Граф-схемное потоковое параллельное программирование: язык, процессная модель, реализация на компьютерных системах // Известия РАН. Серия «Теория и системы управления». 2012. № 1. С. 67—82.
19. Кутепов В.П., Зубов М.И. Реализация и экспериментальное исследование эффективности упреждающего параллелизма // Вестник МЭИ. 2019. № 4. С. 119—126.
20. Питерсон Дж. Теория сетей Петри и моделирование систем. М.: Мир, 1984.
21. Бажанов С.Е., Воронцов М.М., Кутепов В.П., Шестаков Д.А. Структурный анализ и планирование процессов параллельного выполнения функциональных программ // Известия РАН. Серия «Теория и системы управления». 2005. № 6. С. 111—126.
22. Кутепов В.П., Фальк В.Н. Функциональные системы: теоретический и практический аспекты // Кибернетика. 1979. № 1. С. 46—58.
23. Кутепов В.П. Исчисление эквивалентности функциональных схем и параллельные алгоритмы // Программирование. 1979. № 6. С. 3—11.
---
Для цитирования: Кутепов В.П., Фальк В.Н. Алгоритмические параллельные процессы и их сложность // Вестник МЭИ. 2020. № 3. С. 102—110. DOI: 10.24160/1993-6982-2020-3-102-110.
---
Работа выполнена при поддержке: РФФИ (грант № 18-01-00548)
#
1. Kutepov V.P. O Parallelizme s Raznykh Storon. Parallel'nye Vychisleniya i Problemy Upravleniya: Materialy V Mezhdunar. Konf. M: Institut Problem Upravleniya, 2010:41—52. (in Russian).
2. Kutepov V.P., Fal'k V.N. Formy, Yazyki Predstavleniya, Kriterii i Parametry Slozhnosti Parallelizma. Programmnye Produkty i Sistemy. 2010;3:16—25. (in Rus- sian).
3. Kutepov V.P. Intellektual'noe Upravlenie Protsessami i Zagruzhennost'yu v Parallel'nykh Sistemakh. Izvestiya RAN. Seriya «Teoriya i Sistemy Upravleniya». 2007;5:58—73. (in Russian).
4. Kutepov V.P., Brazhnikova Yu.N., Goritskiy Yu.A., Pankov N.A. Issledovanie Metodov Prognozirovaniya Zagruzhennosti Komp'yuterov i Komp'yuternykh Sistem. Programmnye Produkty i Sistemy. 2015;2:135—147. (in Russian).
5. Kutepov V.P., Shamal' P.N. Realizatsiya Yazyka Funktsional'nogo Parallel'nogo Programmirovaniya FPTL na Mnogoyadernykh Komp'yuterakh. Izvestiya RAN. Seriya «Teoriya i Sistemy Upravleniya». 2014;3:46—60. (in Russian).
6. Kutepov V.P. Modeli i Yazyki dlya Opisaniya Parallel'nykh Protsessov. Izvestiya RAN. Seriya «Teoriya i Sistemy Upravleniya». 2018;3:116—127. (in Russian).
7. Al Geist e. a. PVM: Parallel Virtual Machine. A User's Guide and Tutorial for Networked Parallel Computing. London: MIT Press, 1994.
8. Kh'yuz K., Kh'yuz T. Parallel'noe i Raspredelennoe Programmirovanie s Ispol'zovaniem C++. M.: Vil'yams, 2004. (in Russian).
9. Cesarini F., Thompson S. ERLANG Programming: a Concurrent Approach to Software Development. Sebastopol: O'Really Media, 2009.
10. Carver R.H., Kuo-Chung Tai. Modern Multi-threading: Implementing, Testing, and Debugging Multithreaded Java/C++/Pthreads/Win32. N.-Y.: Wiley-Inters-cience, 2005.
11. Burstall R.M., Sannella D.T. HOPE: An Experimental Applicative Language. Proc. ACM Conf. on LISP and Functional Programming. 1980:136—143.
12. Marlou S. Parallel'noe i Konkurentnoe Programmirovanie na Yazyke Haskell. M.: DMK Press, 2014. (in Russian).
13. Obshchaya Teoriya Sistem. M.: Mir, 1966. (in Russian).
14. Zade L. Ponyatie Sostoyaniya v Teorii Sistem. Obshchaya Teoriya Sistem. M.: Mir, 1966:49—65. (in Russian).
15. Maykhill Dzh. Abstraktnaya Teoriya Samovosproizvedeniya. Tam zhe:121—140. (in Russian).
16. Milner R. A Calculus of Communicating Systems Lecture Notes in Computer Science. N.-Y.: Springer-Verlag, 1980.
17. Khoar Ch. Vzaimodeystvuyushchie Posledovatel'nye Protsessy. M.: Mir, 1989. (in Russian).
18. Kutepov V.P., Malanin V.N., Pankov N.A. Graf-skhemnoe Potokovoe Parallel'noe Programmirovanie: Yazyk, Protsessnaya Model', Realizatsiya na Komp'yuternykh Sistemakh. Izvestiya RAN. Seriya «Teoriya i Sistemy Upravleniya». 2012;1:67—82. (in Russian).
19. Kutepov V.P., Zubov M.I. Realizatsiya i Eksperimental'noe Issledovanie Effektivnosti Uprezhdayushchego Parallelizma. Vestnik MEI. 2019;4:119—126. (in Russian).
20. Piterson Dzh. Teoriya Setey Petri i Modelirovanie Sistem. M.: Mir, 1984. (in Russian).
21. Bazhanov S.E., Vorontsov M.M., Kutepov V.P., Shestakov D.A. Strukturnyy Analiz i Planirovanie Protsessov Parallel'nogo Vypolneniya Funktsional'nykh Programm. Izvestiya RAN. Seriya «Teoriya i Sistemy Upravleniya». 2005;6:111—126. (in Russian).
22. Kutepov V.P., Fal'k V.N. Funktsional'nye Sistemy: Teoreticheskiy i Prakticheskiy Aspekty. Kibernetika. 1979; 1:46—58. (in Russian).
23. Kutepov V.P. Ischislenie Ekvivalentnosti Funktsional'nykh Skhem i Parallel'nye Algoritmy. Programmirovanie. 1979;6:3—11. (in Russian).
---
For citation: Kutepov V.P., Falk V.N. Parallel Algorithmic Processes and Their Complexity. Bulletin of MPEI. 2020;3:102—110. (in Russian). DOI: 10.24160/1993-6982-2020-3-102-110.
---
The work is executed at support: RFBR (Grant No. 18-01-00548)
Downloads
Published
2019-10-24
Issue
Section
Mathematical and Software Support of Computing Machines, Complexes and Computer (05.13.11)
