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

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

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

Виталий Павлович Кутепов
Михаил Игоревич Зубов

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 программ на многоядерных компьютерах.

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

Виталий Павлович Кутепов

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

Михаил Игоревич Зубов

магистрант кафедры прикладной математики НИУ «МЭИ», 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)