vestifmИзвестия Национальной академии наук Беларуси. Серия физико-математических наукProceedings of the National Academy of Sciences of Belarus. Physics and Mathematics Series1561-24302524-2415The Republican Unitary Enterprise Publishing House "Belaruskaya Navuka"10.29235/1561-2430-2018-54-1-50-61vestifm-298Research ArticleМАТЕМАТИКАMATHEMATICSФОРМАЛИЗОВАННОЕ ПОЛУЧЕНИЕ КОММУНИКАЦИОННЫХ ОПЕРАЦИЙ ПАРАЛЛЕЛЬНЫХ ЗЕРНИСТЫХ АЛГОРИТМОВFORMALIZED OBTAINING OF THE COMMUNICATION OPERATIONS OF GRAINED PARALLEL ALGORITHMSЛиходедН. А.LikhodedN. A.

доктор физико- математических наук, профессор кафедры вычислительной математики факультета прикладной математики и информатики

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

старший преподаватель кафедры вычислительной математики факультета прикладной математики и информатики

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

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

Algorithms designed for implementation on parallel computers with distributed memory consist of computational macro operations (calculation grains) and communication operations specifying the data arrays exchange between computing nodes. The major difficulty is how to find an efficient way to organize the data exchange. To solve this problem, it is first necessary to identify information dependences between macro operations and then to generate the communication operations caused by these dependences. To automate and simplify the process of code generation, it is necessary to formalize communication operations. The formalization is known for the case of homogeneous information dependences. Such formalization uses the vectors of global dependences as a representation of dependences between the calculation grains. Also, there is a way that makes it possible to obtain the data arrays exchange, but it requires the usage of tools to work with polyhedra and does not formalize communication operations. This article presents a formalization method and a method of inclusion of communication operations into the algorithm structure (receiving and sending data arrays) in case of a parallel algorithm with affine dependences. The usage of functions determining the relationship between macro operations allowed obtaining explicit representations of communication operations. This work is a generalization of the formalization of the operations of sending data in a parallel algorithm, where operations are not divided into macro operations, as well as a generalization of some aspects of obtaining the communication operation method.

 

параллельные вычисленияраспараллеливание алгоритмовпараллельный компьютер с распределенной памятьюформализация коммуникационных операцийparallel computationsparallelization of algorithmsdistributed memory parallel computerformalization of communication operationsReferencesXue, J. Time-minimal tiling when rise is larger than zero / J. Xue, W. Cai // Parallel Computing. – 2002. – Vol. 28, №. 5. – P. 915–939.Xue J., Cai W. Time-minimal tiling when rise is larger than zero. Parallel Computing, 2002, vol. 28, no. 5, pp. 915–939. Doi: 10.1016/s0167-8191(02)00098-4Kim, D. Parameterized tiling for imperfectly nested loops: Technical Report CS-09-101 / D. Kim, S. Rajopadhye. – Colorado State University, Department of Computer Science, February 2009. – 21 p.Kim D., Rajopadhye S. Parameterized Tiling for Imperfectly Nested Loops. Technical Report CS-09-101. Colorado State University, Department of Computer Science, February 2009. 21 p.Dathathri, R. Compiling Affine Loop Nests for a Dynamic Scheduling Runtime on Shared and Distributed Memory /Dathathri 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, pp. 1–28. Doi: 10.1145/2948975R. Dathathri, R. T. Mullapudi, U. Bondhugula // ACM Transactions on Parallel Computing (TOPC). – 2016. – Vol. 3, №. 2. – P. 1–28.Likhoded N. A., Tolstikov A. A. Formalization of communication operations of multidimensional loops. Vestsі Natsyia nal’nai akademіі navuk Belarusі. Seryia fіzіka-matematychnykh navuk = Proceedings of the National Academy of Sciences of Belarus. Physics and Mathematics series, 2010, no. 3, pp. 109–114 (in Russian).Лиходед, Н. А. Формализация коммуникационных операций многомерных циклов / Н. А. Лиходед, A. А. Толстиков // Вес. Нац. акад. навук Беларусi. Сер. фiз.-мат. навук. – 2010. – № 3. – С. 109–114.Likhoded N. A., Sobolevsky P. I., Tolstikov A. A. Parallel algorithm communication operations generated by uniform dependences. Doklady Natsional’noi akademii nauk Belarusi = Doklady of the National Academy of Sciences of Belarus2011, vol. 55, no. 3, pp. 21–26 (in Russian).Лиходед, Н. А. Коммуникационные операции параллельного алгоритма, порождаемые однородными зависимостями / Н. А. Лиходед, П. И. Соболевский, A. А. Толстиков // Докл. Нац. акад. наук Беларуси. – 2011. – Т. 55, № 3. – С. 21–26.Likhoded N. A., Sobolevsky P. I. Information structure of grained algorithms with homogeneous dependencies. Doklady Natsional’noi akademii nauk Belarusi = Doklady of the National Academy of Sciences of Belarus, 2011, vol. 55, no. 2, pp. 22–26 (in Russian).Лиходед, Н. А. Информационная структура зернистых алгоритмов с однородными зависимостями / Н. А. Лиходед, П. И. Соболевский // Докл. Нац. акад. наук Беларуси. – 2011. – Т. 55, № 2. – С. 22–26.Bondhugula U. Compiling affine loop nests for distributed-memory parallel architectures. Supercomputing 2013. Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis, ACM, 2013. Article №. 33. Doi: 10.1145/2503210.2503289Bondhugula, U. Compiling affine loop nests for distributed-memory parallel architectures / U. Bondhugula // Supercomputing 2013: Proc. of the Int. Conf. on High Performance Computing, Networking, Storage and Analysis. ACM, 2013. – Article №. 33.Dathathri R., Reddy C., Ramashekar T., Bondhugula U. Generating efficient data movement code for heterogeneous architectures with distributed-memory. Proceedings of the 22th International Conference on Parallel Architectures and Compilation Techniques (PACT), 2013, pp. 375–386. Doi: 10.1109/pact.2013.6618833Generating efficient data movement code for heterogeneous architectures with distributed-memory / R. Dathathri [et al.] // Proc. of the 22th Int. Conf. on Parallel Architectures and Compilation Techniques (PACT), 2013. – P. 375–386.PLUTO: An automatic parallelizer and locality optimizer for affine loop nests. Available at: http://pluto-compiler. sourceforge.net (accessed 23 October 2017).PLUTO: An automatic parallelizer and locality optimizer for affine loop nests [Electronic resourсe]. – Mode of access: http://pluto-compiler.sourceforge.net. – Date of access: 23.10.2017.Voevodin V. V. Computational mathematics and the structure of algorithms. Moscow, Moscow State University Publishing House, 2006. 112 p. (in Russian).Воеводин, В. В. Вычислительная математика и структура алгоритмов / В. В. Воеводин. – М.: Изд-во МГУ, 2006. – 112 с.Likhoded N. A., Tolstikov A. A. Functions assigning the dependences of grained algorithms. Doklady Natsional’noi akademii nauk Belarusi = Doklady of the National Academy of Sciences of Belarus, 2014, vol. 58, no. 4, pp. 35–41 (in Russian).Лиходед, Н. А. Функции, задающие зависимости зернистых алгоритмов / Н. А. Лиходед, A. А. Толстиков // Докл. Нац. акад. наук Беларуси. – 2014. – Т. 58, № 4. – С. 35–41.Voevodin V. V., Voevodin Vl. V. Parallel Computations. Saint Petersburg, BKhV-Peterburg Publ., 2002. 608 p. (in Russian).Воеводин, В. В. Параллельные вычисления / В. В. Воеводин, Вл. В. Воеводин. – СПб.: БХВ-Петербург, 2002. – 608 с.Voevodin V. V. Massive parallelism and decomposition of algorithms. Zhurnal vychislitel’noi matematiki i matematicheskoi fiziki = Computational Mathematics and Mathematical Physics, 1995, vol. 35, no. 6, pp. 988–996 (in Russian).Воеводин, В. В. Массивный параллелизм и декомпозиция алгоритмов / В. В. Воеводин // Журн. вычисл. математики и мат. физики. – 1995. – Т. 35, № 6. – С. 988–996.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).Лиходед, Н. А. Параллельные последовательности зернистых вычислений / Н. А. Лиходед, A. А. Толстиков // Докл. Нац. акад. наук Беларуси. – 2010. – Т. 54, № 4. – С. 36–41.Lim A. W., Lam M. S. Maximizing parallelism and minimizing synchronization with affine partitions. Parallel Computing, 1998, vol. 24, no. 3–4, pp. 445–475. Doi: 10.1016/s0167-8191(98)00021-0Lim, A. W. Maximizing parallelism and minimizing synchronization with affine partitions / A. W. Lim, M. S. Lam // Parallel Computing. – 1998. – Vol. 24, № 3/4. –P. 445–475.Bondhugula 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. Doi: 10.1007/978-3-540-78791-4_9Automatic transformations for communication-minimized parallelization and locality optimization in the polyhedral model / U. Bondhugula [et al.] // Lecture Notes in Computer Science. – 2008. – № 4959. – P. 132–146.Likhoded N. A. Sufficient conditions for the determination and use of data in the same granular parallel computa -tion process. Computational Mathematics and Mathematical Physics, 2014, vol. 54, no. 8, pp. 1316–1326. Doi: 10.1134/ s0965542514080077Лиходед, Н. А. Достаточные условия определения и использования данных в одном параллельном зернистом вычислительном процессе / Н. А. Лиходед // Журн. вычисл. математики и мат. физики. – 2014. – Т. 54, № 8. – С. 1356–1367.Лиходед, Н. А. Достаточные условия определения и использования данных в одном параллельном зернистом вычислительном процессе / Н. А. Лиходед // Журн. вычисл. математики и мат. физики. – 2014. – Т. 54, № 8. – С. 1356–1367.

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