Реализация и экспериментальное исследование эффективности упреждающего параллелизма

Виталий [Vitaliy] Павлович [P.] Кутепов [Kutepov]; Михаил [Mikhail] Игоревич [I.] Зубов [Zubov]

doi:10.24160/1993-6982-2019-4-119-126

Виталий [Vitaliy] Павлович [P.] Кутепов [Kutepov]
Михаил [Mikhail] Игоревич [I.] Зубов [Zubov]

DOI: https://doi.org/10.24160/1993-6982-2019-4-119-126

Ключевые слова: параллельное программирование, управление параллельными процессами, упреждающие вычисления, FPTL

Аннотация

Предложен метод реализации параллельных вычислений с упреждением, позволяющий увеличивать степень распараллеливания программ и при определённых условиях существенно сократить время их выполнения на компьютерных системах. Типичным случаем возможного применения упреждающих вычислений в языках программирования является условный оператор. При его выполнении можно одновременно вычислять значения предиката с упреждением значения функций. Такого рода параллелизм не реализован в настоящее время во многих известных средах параллельного программирования: PVM, MPI, MULTITHREADING, HOPE и др. Предложенный метод выполнен как расширение системы функционального параллельного программирования, созданной на базе языка FPTL (Functional Parallel Typified Language).

Дано краткое описание языка FPTL и предоставляемых им возможностей, определены формулы для оценки эффективности упреждающих вычислений по критериям ускорения и уменьшения времени выполнения параллельных программ, описаны ключевые части интерпретатора FPTL и выполненная программная реализация предложенного метода, приведены результаты экспериментов, демонстрирующих возможные границы эффективности упреждающих вычислений при выполнении параллельных FPTL программ на многоядерных компьютерах.

Сведения об авторах

Виталий [Vitaliy] Павлович [P.] Кутепов [Kutepov]

доктор технических наук, профессор кафедры прикладной математики НИУ «МЭИ», e-mail: KutepovVP@mpei.ru

Михаил [Mikhail] Игоревич [I.] Зубов [Zubov]

магистрант кафедры прикладной математики НИУ «МЭИ», e-mail: zumisha@yandex.ru

Литература

1. Al Geist e. a. PVM: Parallel Virtual Machine. A User's Guide and Tutorial for Networked Parallel Computing. Massachusetts: MIT Press, 1996.
2. Snir M., Otto S.W., Huss-Lederman S., Walker D., Dongarra J. MPI: The Complete Reference. Massachusetts: MIT Press, 1996.
3. Cesarini F., Thompson S. Erlang Programming: a Concurrent Approach to Software Development. Sebastopol: O'Reilly, 2009.
4. Carver R.H., Kuo-chung Tai. Modern Multithreading: Implementing, Testing, and Debugging Multithreaded Java/C++. N.-Y.: Wiley-Interscience, 2005.
5. Burstall R.M., Sannella D.T. HOPE User's Manual. In preparation // Proc. 1980 ACM Conf. LISP and Functional Programming. Stanford: Stanford University, 1980. Pp. 136—143.
6. Бажанов C.Е., Кутепов В.П., Шестаков Д.А. Язык функционального параллельного программирования и его реализация на кластерных системах // Программирование. 2005. № 5. С. 237—269.
7. Кутепов В.П., Шамаль П.Н. Реализация языка функционального параллельного программирования FPTL на многоядерных компьютерах // Известия РАН. Серия «Теория и системы управления». 2014. № 3. С. 46—60.
8. Кутепов В.П., Фальк В.Н. Формы, языки представления, критерии и параметры сложности параллелизма // Программные продукты и системы. 2010. № 3. С. 16—26.
9. Бочаров И.А., Кутепов В.П., Шамаль П.Н. Система типового контроля программ на языке функционального программирования // Программные продукты и системы. 2014. № 2. С. 11—17.
10. Ахо А.В., Лам М.С., Сети Р., Ульман Д.Д. Компиляторы: принципы, технологии и инструментарий. М.: Вильямс, 2018.
11. Амосов А.А., Дубинский Ю.А., Копченова Н.В. Вычислительные методы для инженеров. М.: Изд-во МЭИ, 2003.
--
Для цитирования: Кутепов В.П., Зубов М.И. Реализация и экспериментальное исследование эффективности упреждающего параллелизма // Вестник МЭИ. 2019. № 4. С. 119—126. DOI: 10.24160/1993-6982-2019-4-119-126.
--
Работа выполнена при поддержке: РФФИ (грант № 18-01-00548)
#
1. Al Geist e. a. PVM: Parallel Virtual Machine. A User's Guide and Tutorial for Networked Parallel Computing. Massachusetts: MIT Press, 1996.
2. Snir M., Otto S.W., Huss-Lederman S., Walker D., Dongarra J. MPI: The Complete Reference. Massachusetts: MIT Press, 1996.
3. Cesarini F., Thompson S. Erlang Programming: a Concurrent Approach to Software Development. Sebastopol: O'Reilly, 2009.
4. Carver R.H., Kuo-chung Tai. Modern Multithreading: Implementing, Testing, and Debugging Multithreaded Java/C++. N.-Y.: Wiley-Interscience, 2005.
5. Burstall R.M., Sannella D.T. HOPE User's Manual. In preparation. Proc. 1980 ACM Conf. LISP and Functional Programming. Stanford: Stanford University, 1980: 136—143.
6. Bazhanov C.E., Kutepov V.P., Shestakov D.A. Yazyk Funktsional'nogo Parallel'nogo Programmirovaniya i Ego Realizatsiya na Klasternykh Sistemakh. Programmirovanie. 2005;5:237—269. (in Russian).
7. 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).
8. Kutepov V.P., Fal'k V.N. Formy, Yazyki Predstavleniya, Kriterii i Parametry Slozhnosti Parallelizma. Programmnye Produkty i Sistemy. 2010;3:16—26. (in Russian).
9. Bocharov I.A., Kutepov V.P., Shamal' P.N. Sistema Tipovogo Kontrolya Programm na Yazyke Funktsional'nogo Programmirovaniya. Programmnye Produkty i Sistemy. 2014;2:11—17. (in Russian).
10. Akho A.V., Lam M.S., Seti R., Ul'man D.D. Kompilyatory: Printsipy, Tekhnologii i Instrumentariy. M.: Vil'yams, 2018. (in Russian).
11. Amosov A.A., Dubinskiy Yu.A., Kopchenova N.V. Vychislitel'nye Metody Dlya Inzhenerov. M.: Izd-vo MEI, 2003. (in Russian).
--
For citation: Kutepov V.P., Zubov M.I. Implementation of Lookahead Parallelism and Experimental Implementation of Its Efficiency. Bulletin of MPEI. 2019;4:119—126. (in Russian). DOI: 10.24160/1993-6982-2019-4-119-126.
--
The work is executed at support: RFBR (grant No. 18-01-00548)