danДоклады Национальной академии наук БеларусиDoklady of the National Academy of Sciences of Belarus1561-83232524-2431The Republican Unitary Enterprise Publishing House "Belaruskaya Navuka"10.29235/1561-8323-2020-64-6-647-656dan-924Research ArticleМАТЕМАТИКАMATHEMATICSМетод оценки локальности параллельных алгоритмов, ориентированных на компьютеры с распределенной памятьюLocality estimation of parallel algorithm for distributed memory computersЛиходедН. А.LikhodedN. A.

Лиходед Николай Александрович – д-р физ.-мат. наук, профессор

пр. Независимости, 4, 220030, Минск

Likhoded Nikolai A. – D. Sc. (Physics and Mathematics), Professor. 

4, Nezavisimosti Ave., 220030, Minsk

likhoded@bsu.byТолстиковА. А.TolstsikauA. A.

Толстиков Алексей Александрович – ст. преподаватель

пр. Независимости, 4, 220030, Минск

Tolstsikau Aliaksei A. – Senior lecturer

4, Nezavisimosti Ave., 220030, Minsk

tolstikov@bsu.byБелорусский государственный университетBelarusian State University202031122020646647–656Copyright © Лиходед Н.А., Толстиков А.А., 20202020Лиходед Н.А., Толстиков А.А.Likhoded N.A., Tolstsikau A.A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://doklady.belnauka.by/jour/article/view/924

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

Locality is an algorithm characteristic describing a usage level of fast access memory. For example, in case of distributed memory computers we focus on memory of each computational node. To achieve the high performance of algorithm implementation one should choose the best possible locality option. Studying the parallel algorithm locality is to estimate the number and volume of data communications. In this work, we formulate and prove the statements for computers with distributed memory that allow us to estimate the asymptotic volume of data communication operations. These estimation results are useful while comparing alternative versions of parallel algorithms during data communication cost analysis.

параллельные вычисленияпараллельный компьютер с распределенной памятьюуменьшение обменов даннымиparallel computingdistributed memory parallel computerdata communication reducingReferencesВоеводин, Вл. В. Спасительная локальность суперкомпьютеров / Вл. В. Воеводин, Вад. В. Воеводин // Открытые системы. – 2013. – № 9. – С. 12–15.Voevodin Vl. V., Voevodin Vad. V. The fortunate locality of supercomputers. Otkrytye sistemy = Open Systems, 2013, no. 9, pp. 12–15 (in Russian).Xue, J. Time-minimal tiling when rise is larger than zero / J. Xue, W. Cai // Parallel Computing. – 2002. – Vol. 28, N 6. – P. 915–939. https://doi.org/10.1016/s0167-8191(02)00098-4Xue J., Cai W. Time-minimal tiling when rise is larger than zero. Parallel Computing, 2002, vol. 28, no. 6, pp. 915–939. https://doi.org/10.1016/s0167-8191(02)00098-4Dathathri, R. Compiling affine loop nests for a dynamic scheduling runtime on shared and distributed memory / R. Dathathri, R. T. Mullapudi, U. Bondhugula // ACM Transactions on Parallel Computing (TOPC). – 2016. – Vol. 3, N 2. – P. 1–28. https://doi.org/10.1145/2948975Dathathri R., Mullapudi R. T., Bondhugula U. Compiling affine loop nests for a dynamic scheduling runtime on shared and distributed memory. ACM Transactions on Parallel Computing (TOPC), 2016, vol. 3, no. 2, p. 1–28. https://doi.org/10.1145/2948975Воеводин, В. В. Параллельные вычисления / В. В. Воеводин, Вл. В. Воеводин. – СПб., 2002. – 608 с.Voevodin V. V., Voevodin Vl. V. Parallel Computing. Saint Petersburg, 2002. 608 p. (in Russian).Адуцкевич, Е. В. Согласованное получение конвейерного параллелизма и распределения операций и данных между процессорами / Е. В. Адуцкевич, Н. А. Лиходед // Программирование. – 2006. – Т. 35, № 3. – С. 52–65.Adutskevich E. V., Likhoded N. A. A consistent generation of pipeline parallelism and distribution of operations and data among processors. Programming and Computer Software, 2006, vol. 32, no. 3, pp. 166–176. https://doi.org/10.1134/s0361768806030078Automatic transformations for communication-minimized parallelization and locality optimization in the polyhedral model / U. Bondhugula [et al.] // Lecture notes in computer science. – 2008. – N 4959. – P. 132–146. https://doi.org/10.1007/978- 3-540-78791-4_9Bondhugula U., Baskaran M., Krishnamoorthy S., Ramanujam J., Rountev A., Sadayappan P. Automatic transformations for communication-minimized parallelization and locality optimization in the polyhedral model. Lecture notes in computer science, 2008, no. 4959, pp. 132–146. https://doi.org/10.1007/978-3-540-78791-4_9Лиходед, Н. А. Достаточные условия определения и использования данных в одном параллельном зернистом вычислительном процессе / Н. А. Лиходед // Журн. вычисл. математики и матем. физики. – 2014. – Т. 54, № 8. – С. 1356. https://doi.org/10.7868/S0044466914080092Likhoded N. A. Sufficient conditions for the determination and use of data in the same granular parallel computation process. Computational Mathematics and Mathematical Physics, 2014, vol. 54, no. 8, pp. 1316–1326. https://doi.org/10.1134/s0965542514080077Лиходед, Н. А. Метод ранжирования параметров размера блоков вычислений параллельного алгоритма / Н. А. Лиходед, М. А. Полещук // Докл. Нац. акад. наук Беларуси. – 2015. – Т. 59, № 4. – С. 25–33.Likhoded N. A., Paliashchuk M. A. Method of ranking tiles size parameters of parallel algorithm. Doklady Natsional’noi akademii nauk Belarusi = Doklady of the National Academy of Sciences of Belarus, 2015, vol. 59, no. 4, pp. 25– 33 (in Russian).Гергель, В. П. Основы параллельных вычислений для многопроцессорных вычислительных систем / В. П. Гергель, Р. Г. Стронгин. – Нижний Новгород, 2003. – 184 с.Gergel V. P., Strongin R. G. Introduction to parallel computing for multiprocessor systems. Nizhny Novgorod, 2003. 184 p. (in Russian).Лиходед, Н. А. Параллельные последовательности зернистых вычислений / Н. А. Лиходед, А. А. Толстиков // Докл. Нац. акад. наук Беларуси. – 2010. – Т. 54, № 4. – С. 36–41.Likhoded N. A., Tolstikov A. A. Parallel sequences of grain computations. Doklady Natsional’noi akademii nauk Belarusi = Doklady of the National Academy of Sciences of Belarus, 2010, vol. 54, no. 4, pp. 36–41 (in Russian).Баханович, С. В. Улучшение локальности параллельных алгоритмов численного решения двумерных квазилинейных параболических уравнений / С. В. Баханович, Н. А. Лиходед, П. А. Мандрик // Вестн. Рос. ун-та дружбы народов. Сер. Математика. Информатика. Физика. – 2014. – № 2. – С. 211–215.Bakhanovich S. V., Likhoded N. A., Mandrik P. A. Improvement of locality of parallel algorithms of the numerical solutions of the two-dimensional quasilinear parabolic equation. Discrete and Continuous Models and Applied Computational Science, 2014, no. 2, pp. 211–215 (in Russian).

The authors declare that there are no conflicts of interest present.