danДоклады Национальной академии наук БеларусиDoklady of the National Academy of Sciences of Belarus1561-83232524-2431The Republican Unitary Enterprise Publishing House "Belaruskaya Navuka"dan-117Research ArticleМАТЕМАТИКАMATHEMATICSМЕТОД РАНЖИРОВАНИЯ ПАРАМЕТРОВ РАЗМЕРА БЛОКОВ ВЫЧИСЛЕНИЙ ПАРАЛЛЕЛЬНОГО АЛГОРИТМАMETHOD OF RANKING TILES SIZE PARAMETERS OF а PARALLEL ALGORITHMЛИХОДЕДН. А.LIKHODEDN. A.likhoded@bsu.byПОЛЕЩУКМ. А.PALIASHCHUKM. A.poleschuma@bsu.byБелорусский государственный университет, МинскBelаrusian State University, Minsk2015020620165942533Copyright © ЛИХОДЕД Н.А., ПОЛЕЩУК М.А., 20162016ЛИХОДЕД Н.А., ПОЛЕЩУК М.А.LIKHODED N.A., PALIASHCHUK M.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/117

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

A method for obtaining tiles of operations of a parallel algorithm is developed. Propositions for ranking tiles size parameters are stated and proved. Statements to assess the amount of communication operations generated by the partition of the set of iterations are stated and proved.

параллельные вычисленияраспараллеливание алгоритмовграфический процессорминимизации объема коммуникационных операцийparallel computingparallelization of algorithmsGPUminimization of communicationsReferencesBaskaran, M. Automatic C-to-CUDA code generation for affine programs / M. Baskaran, J. Ramanujam, P. Sadayappan // Proceedings of the Compiler Construction, 19th International Conference. Part of the Joint European Conferences onBaskaran, M. Automatic C-to-CUDA code generation for affine programs / M. Baskaran, J. Ramanujam, P. Sadayappan // Proceedings of the Compiler Construction, 19th International Conference. Part of the Joint European Conferences onTheory and Practice of Software. – Paphos, Cyprus, March 2010.Theory and Practice of Software. – Paphos, Cyprus, March 2010.Xue, J. Time-minimal tiling when rise is larger than zero / J. Xue, W. Cai // Parallel Computing. – 2002. – Vol. 28, N 5. – P. 915–939.Xue, J. Time-minimal tiling when rise is larger than zero / J. Xue, W. Cai // Parallel Computing. – 2002. – Vol. 28, N 5. – P. 915–939.Kim, D. G. Parameterized tiling for imperfectly nested loops / D. G. Kim, S. Rajopadhye // Technical Report CS-09-101, Colorado State University, Department of Computer Science, February 2009. – 21 p.Kim, D. G. Parameterized tiling for imperfectly nested loops / D. G. Kim, S. Rajopadhye // Technical Report CS-09-101, Colorado State University, Department of Computer Science, February 2009. – 21 p.Automatic parallelization of tiled loop nests with enhanced fine-grained parallelism on GPUs / P. Di [et al.] // 41st International Conference on Parallel Processing. – Pittsburgh, PA, USA, September 2012. IEEE Computer Society, 2012. – P. 350–359.Automatic parallelization of tiled loop nests with enhanced fine-grained parallelism on GPUs / P. Di [et al.] // 41st International Conference on Parallel Processing. – Pittsburgh, PA, USA, September 2012. IEEE Computer Society, 2012. – P. 350–359.Bandishti, V. Tiling stencil computations to maximize parallelism / V. Bandishti, I. Pananilath, U. Bondhugula // Proceedings of Supercomputing. – Los Alamitos, CA, USA. IEEE Computer Society Press, 2012. – P. 40:1–40:11.Bandishti, V. Tiling stencil computations to maximize parallelism / V. Bandishti, I. Pananilath, U. Bondhugula // Proceedings of Supercomputing. – Los Alamitos, CA, USA. IEEE Computer Society Press, 2012. – P. 40:1–40:11.Воеводин, В. В. Параллельные вычисления / В. В. Воеводин, Вл. В. Воеводин. – СПб.: БХВ-Петербург, 2002. – 608 с.Воеводин, В. В. Параллельные вычисления / В. В. Воеводин, Вл. В. Воеводин. – СПб.: БХВ-Петербург, 2002. – 608 с.Feautrier, P. Some efficient solutions to the affine scheduling problem. Part 1 / P. Feautrier // International J. of Parallel Programming. – 1992. – Vol. 21, N 5. – P. 313–348.Feautrier, P. Some efficient solutions to the affine scheduling problem. Part 1 / P. Feautrier // International J. of Parallel Programming. – 1992. – Vol. 21, N 5. – P. 313–348.Automatic 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.Automatic 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.Лиходед, Н. А. Оценка объема коммуникационных операций параллельного зернистого алгоритма / Н. А. Лиходед, М. А. Полещук // Междунар. конгресс по информатике: информационные системы и технологии CSIST’2013, 4–7 ноября 2013 г., Минск, Беларусь. Бел. гос. ун-т. – Минск, 2013. – С. 377–381.Лиходед, Н. А. Оценка объема коммуникационных операций параллельного зернистого алгоритма / Н. А. Лиходед, М. А. Полещук // Междунар. конгресс по информатике: информационные системы и технологии CSIST’2013, 4–7 ноября 2013 г., Минск, Беларусь. Бел. гос. ун-т. – Минск, 2013. – С. 377–381.Лиходед, Н. А. Характеристика локальности параллельных реализаций многомерных циклов / Н. А. Лиходед // Докл. НАН Беларуси. – 2010. – Т. 54, № 1. – С. 26–32.Лиходед, Н. А. Характеристика локальности параллельных реализаций многомерных циклов / Н. А. Лиходед // Докл. НАН Беларуси. – 2010. – Т. 54, № 1. – С. 26–32.Адуцкевич, Е. В. К распараллеливанию последовательных программ: распределение массивов между процессорами и структуризация коммуникаций / Е. В. Адуцкевич, Н. А. Лиходед, А. О. Сикорский // Кибернетика и системный анализ. – 2012. – Т. 48, № 1. – С. 144–163.Адуцкевич, Е. В. К распараллеливанию последовательных программ: распределение массивов между процессорами и структуризация коммуникаций / Е. В. Адуцкевич, Н. А. Лиходед, А. О. Сикорский // Кибернетика и системный анализ. – 2012. – Т. 48, № 1. – С. 144–163.

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