ФОРМАЛИЗОВАННОЕ ПОЛУЧЕНИЕ КОММУНИКАЦИОННЫХ ОПЕРАЦИЙ ПАРАЛЛЕЛЬНЫХ ЗЕРНИСТЫХ АЛГОРИТМОВ

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

1. Xue, J. Time-minimal tiling when rise is larger than zero / J. Xue, W. Cai // Parallel Computing. – 2002. – Vol. 28, №. 5. – P. 915–939.

2. Kim, 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.

3. Dathathri, R. Compiling Affine Loop Nests for a Dynamic Scheduling Runtime on Shared and Distributed Memory /

4. R. Dathathri, R. T. Mullapudi, U. Bondhugula // ACM Transactions on Parallel Computing (TOPC). – 2016. – Vol. 3, №. 2. – P. 1–28.

5. Лиходед, Н. А. Формализация коммуникационных операций многомерных циклов / Н. А. Лиходед, A. А. Толстиков // Вес. Нац. акад. навук Беларусi. Сер. фiз.-мат. навук. – 2010. – № 3. – С. 109–114.

6. Лиходед, Н. А. Коммуникационные операции параллельного алгоритма, порождаемые однородными зависимостями / Н. А. Лиходед, П. И. Соболевский, A. А. Толстиков // Докл. Нац. акад. наук Беларуси. – 2011. – Т. 55, № 3. – С. 21–26.

7. Лиходед, Н. А. Информационная структура зернистых алгоритмов с однородными зависимостями / Н. А. Лиходед, П. И. Соболевский // Докл. Нац. акад. наук Беларуси. – 2011. – Т. 55, № 2. – С. 22–26.

8. Bondhugula, 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.

9. Generating 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.

10. 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.

11. Воеводин, В. В. Вычислительная математика и структура алгоритмов / В. В. Воеводин. – М.: Изд-во МГУ, 2006. – 112 с.

12. Лиходед, Н. А. Функции, задающие зависимости зернистых алгоритмов / Н. А. Лиходед, A. А. Толстиков // Докл. Нац. акад. наук Беларуси. – 2014. – Т. 58, № 4. – С. 35–41.

13. Воеводин, В. В. Параллельные вычисления / В. В. Воеводин, Вл. В. Воеводин. – СПб.: БХВ-Петербург, 2002. – 608 с.

14. Воеводин, В. В. Массивный параллелизм и декомпозиция алгоритмов / В. В. Воеводин // Журн. вычисл. математики и мат. физики. – 1995. – Т. 35, № 6. – С. 988–996.

15. Лиходед, Н. А. Параллельные последовательности зернистых вычислений / Н. А. Лиходед, A. А. Толстиков // Докл. Нац. акад. наук Беларуси. – 2010. – Т. 54, № 4. – С. 36–41.

16. Lim, 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.

17. Automatic 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.

18. Лиходед, Н. А. Достаточные условия определения и использования данных в одном параллельном зернистом вычислительном процессе / Н. А. Лиходед // Журн. вычисл. математики и мат. физики. – 2014. – Т. 54, № 8. – С. 1356–1367.