Implementation of Lookahead Parallelism and Experimental Implementation of Its Efficiency
Abstract
A method for implementing parallel lookahead computations is proposed, the use of which makes possible to increase the degree to which computer programs are set to run in parallel flows and, under certain conditions, significantly reduce their execution time on computer systems. A conditional operator is the typical case of possible application of lookahead computations in programming languages. In executing it, it is possible to simultaneously compute the predicate values with predicting the function value. This kind of parallelism has not been currently implemented in many well-known parallel programming environments: PVM, MPI, MULTITHREADING, HOPE, etc. The proposed method is implemented as an extension of the functional parallel programming system created on the basis of the Functional Parallel Typified Language (FPTL).
The article gives a brief description of the FPTL language and its capabilities presents formulas for evaluating the effectiveness of lookahead computations in terms of criteria of accelerating and reducing the execution time of parallel programs, describes the key parts of the FPTL interpreter and the software implementation of the proposed method, and presents the results of experiments that demonstrate the possible efficiency limits of using lookahead computations in executing parallel FPTL programs on multicore computers.
References
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)
