Алгоритмические параллельные процессы и их сложность
Ключевые слова:
параллельные процессы, оценка сложности
Аннотация
Предложен метод оценки сложности параллельных процессов по критериям среднего времени их абсолютно параллельного выполнения и необходимых для этого ресурсов (количеству узлов выполняющей процесс системы). Указанные критерии рассматриваются для достаточно общего языка параллельных процессов, по их значениям можно судить, насколько реальные их значения, полученные при выполнении процесса на конкретной системе, отличаются от предельно возможных.
Важно отметить, что рассматриваемый язык параллельных процессов реализован на многоядерных компьютерах, на его основе разработаны операционные средства для эффективного управления выполнением функциональных параллельных программ. В качестве языка описания параллельных программ взят созданный и успешно применяемый на практике язык функционального параллельного программирования. Описанные в статье методы оценки сложности параллельных процессов необходимы на стадии проектирования и оптимизации функциональных параллельных программ.
Литература
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)
Опубликован
2019-10-24
Выпуск
Раздел
Матем. и программное обеспеч. вычислит. машин, комплексов и компьютерных сетей (05.13.11)
