10.14489/vkit.2019.09.pp.043-049

DOI: 10.14489/vkit.2019.09.pp.043-049

Дордопуло А. И.
ПРИМЕНЕНИЕ МЕТОДОВ РЕДУКЦИИ ПРОИЗВОДИТЕЛЬНОСТИ ДЛЯ СОКРАЩЕНИЯ ЧИСЛА АНАЛИЗИРУЕМЫХ ВАРИАНТОВ ПАРАЛЛЕЛЬНОЙ ПРОГРАММЫ
(с. 43-49)

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

Ключевые слова: автоматическое распараллеливание; редукция производительности; реконфигурируемые вычислительные системы; программирование многопроцессорных вычислительных систем.

Dordopulo A. I.
APPLICATION OF PERFORMANCE REDUCTION METHODS FOR MINIMIZATION OF ANALYZED NUMBER OF PARALLEL PROGRAM VARIANTS
(pp. 43-49)

Abstract. In this paper, we review and compare the methods of parallel applications’ development based on the automatic program parallelizing for computer systems with shared and distributed memory and on the information graph’s hardware costs and performance reduction for reconfigurable computer systems. The increase in the number of computer system’s units or in the problem’s dimension leads to the significant growth of the automatic parallelization complexity for a procedural program. As a result, the obtainment of parallelizing results in acceptable time using state-of-the-art computer systems is very problematic. In reconfigurable computer systems, the reduction of absolutely parallel information graph of a problem is applied for the parallel program creation. The information graph illustrates the parallelizing and pipelining of computations. In addition to the traditionally practiced reduction of basic subgraphs’ number, the reductions of computational operations’ quantity and of data digit capacity can be utilized for the performance or hardware costs’ scaling. We have proved that the methods of information graph hardware costs and performance reduction provide a considerable decrease in the number of steps needed for adaptation of parallel application to reconfigurable computer systems’ architectures in comparison with automatic parallelizing. We have proved the theorem of coefficient value at sequential reduction, the theorem of increase in reduction coefficient at custom value and the theorem of commutativity of various reduction transformations. The proved theorems help to find a rational sequence of reduction transformations.

Keywords: Automatic parallelizing; Performance reduction; Reconfigurable computer systems; Programming of multiprocessor computer systems.

+ - Информация об авторах (About the Authors) Click to collapse

Рус

А. И. Дордопуло (ООО «Научно-исследовательский центр супер-ЭВМ и нейрокомпьютеров», Таганрог, Россия) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

Eng

A. I. Dordopulo (Supercomputers and Neurocomputers Research Center, Co Ltd., Taganrog, Russia) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

+ - Библиографический список (References) Click to collapse

Рус

1. Автоматизация распараллеливания программных комплексов / В. А. Бахтин, О. Ф. Жукова, Н. А. Катаев и др. // Научный сервис в сети Интернет: тр. XVIII Всерос. науч. конф. Новороссийск, 2016. М.: ИПМ имени М. В. Келдыша РАН, 2016. С. 76 – 85.
2. Kasahara H., Obata M., Ishizaka K. Automatic Coarse Grain Task Parallel Processing on SMP Using OpenMP // Proc. of 13-th International Workshop on Languages and Compilers for Parallel Computing, 2000. Aug. 2000.
3. Getting Started with OpenMP*. [Электронный ресурс]. URL: https:// software.intel.com/en-us/articles/ getting-started-with-openmp (дата обращения: 26.02.2019).
4. ParaWise Automatic Parallelisation of C and Fortran. [Электронный ресурс]. URL: www.parallelsp.com (дата обращения: 23.05.2019).
5. Vikram K., Avijit K., Aggarwal S. K. OlyMPIx – A Program Parallelization Tool using MPI on Computational Grids. URL: www.cs.cornell.edu/ ~kvikram/papers/pdcn.ps (дата обращения: 23.05.2019).
6. Intel Parallel Studio. URL: https://software. intel.com/en-us/parallel-studio-xe (дата обращения: 23.05.2019).
7. Система САПФОР. URL: http://www.keldysh. ru/dvm/SAPFOR/ (дата обращения: 23.05.2019).
8. Штейнберг Б. Я. Математические методы распараллеливания рекуррентных циклов для суперкомпьютеров с параллельной памятью. Ростов н/Д: Изд-во Ростовского государственного ун-та, 2004. 172 с.
9. Т-система. URL: http://www.botik.ru/~t-system/ Parallel-Russia/projects/t-system-psi_ras.ru.html (дата обращения: 23.05.2019).
10. Система V-Ray. URL: https://parallel.ru/russia/ map/data/project01.html (дата обращения: 23.05.2019).
11. Янг Дж. Программное обеспечение супер-ЭВМ: открываются широкие перспективы // Электроника. 1988. Т. 61, № 5(787). С. 52 – 56.
12. Клинов М. С., Крюков В. А. Автоматическое распараллеливание Фортран-программ. Отображение на кластер // Научный сервис в сети Интернет: тр. XI Всерос. науч. конф. Новороссийск, 2009. М.: ИПМ имени М. В. Келдыша РАН, 2009. С. 227 – 237.
13. Каляев А. В., Левин И. И. Модульнонаращиваемые многопроцессорные системы со структурно-процедурной организацией вычислений. М.: Янус-К, 2003. 380 с.
14. Решение задач с существенно-переменной интенсивностью потоков данных на реконфигурируемых вычислительных системах / И.И. Левин и др. // Вестник компьютерных и информационных технологий. 2012. № 2. С. 49 – 56.
15. Кнут Д., Грэхем Р., Паташник О. Конкретная математика. Основание информатики. М.: Мир; Бином. Лаборатория знаний, 1998. 703 с.

Eng

1. Bahtin V. A., Zhukova O. F., Kataev N. A. et al. (2016). Automation of parallelization of software systems. Proceedings of the XVIII All-Russian Conference “Scientific service on the Internet”, pp. 76-85. Moscow: IPM imeni M. V. Keldysha RAN. [in Russian language]
2. Kasahara H., Obata M., Ishizaka K. (2000). Automatic Coarse Grain Task Parallel Processing on SMP Using OpenMP. Proceedings of 13-th International Workshop on Languages and Compilers for Parallel Computing. Aug. 2000.
3. Getting Started with OpenMP*. Available at: https:// software.intel.com/en-us/articles/getting-started-with-openmp (Accessed: 26.02.2019).
4. ParaWise Automatic Parallelisation of C and Fortran. Available at: www.parallelsp.com (Accessed: 23.05.2019).
5. Vikram K., Avijit K., Aggarwal S. K. OlyMPIx – A Program Parallelization Tool using MPI on Computational Grids. Available at: www.cs.cornell.edu/ ~kvikram/papers/pdcn.ps (Accessed: 23.05.2019).
6. Intel Parallel Studio. Available at: https://software.intel.com/en-us/parallel-studio-xe (Accessed: 23.05.2019).
7. SAPFOR system. Available at: http://www. keldysh.ru/dvm/SAPFOR/ (Accessed: 23.05.2019). [in Russian language].
8. Shteynberg B. Ya. (2004). Mathematical methods of parallelization of recurrent cycles for supercomputers with parallel memory. Rostov-on-Don: Izdatel'stvo Rostovskogo gosudarstvennogo universiteta. [in Russian language].
9. Т-system. Available at: http://www.botik.ru/~t-system/ Parallel-Russia/projects/t-system-psi_ras.ru.html (Accessed: 23.05.2019). [in Russian language]
10. V-Ray system. Available at: https://parallel.ru/ russia/map/data/project01.html (Accessed: 23.05.2019). [in Russian language].
11. Jeremy Young. (1988). Supercomputer software: the floodgates are opening. Elektronika, Vol. 61, 787(5). Pp. 75-77. [in Russian language].
12. Klinov M. S., Kryukov V. A. (2009). Automatic parallelization of Fortran programs. The mapping on the cluster. Proceedings of the XI All-Russian Conference “Scientific service on the Internet”, pp. 227-237. Moscow: IPM imeni M. V. Keldysha RAN. [in Russian language].
13. Kalyaev A. V., Levin I. I. (2003). Modular-scalable multiprocessor computer systems with structural-procedural organization of calculations. Moscow: Yanus-K. [in Russian language].
14. Levin I. I., Sorokin D. A., Mel'nikov A. K., Dordopulo A. I. (2012). Solving problems with essentially variable intensity of data flows on reconfigurable computing systems. Vestnik komp'yuternyh i informatsionnyh tekhnologiy, (2), pp. 49-56. Moscow: Mashinostroenie. [in Russian language].
15. Knut D., Grekhem R., Patashnik O. (1998). Specific mathematics. Foundation for computer science. Moscow: Mir; Binom. Laboratoriya znaniy. [in Russian language].

+ - Заказать электронную версию статьи (Purchase digital version of a single article) Click to collapse

Рус

Статью можно приобрести в электронном виде (PDF формат).

DOI: 10.14489/vkit.2019.09.pp.043-049

Скопируйте DOI статьи и перейдите по ссылке https://id-spektr.ru/product/pokupka-elektronnoy-stati-iz-zhurnala-vestnik-kompyuternyh-i-informatsionnyh-tehnologiy

В комментарии к заказу обязательно укажите DOI статьи.

Eng

This article is available in electronic format (PDF).

DOI: 10.14489/vkit.2019.09.pp.043-049

Copy the article DOI and follow the link https://id-spektr.ru/product/pokupka-elektronnoy-stati-iz-zhurnala-vestnik-kompyuternyh-i-informatsionnyh-tehnologiy

Please specify the article DOI in the order comments.