vestifmИзвестия Национальной академии наук Беларуси. Серия физико-математических наукProceedings of the National Academy of Sciences of Belarus. Physics and Mathematics Series1561-24302524-2415The Republican Unitary Enterprise Publishing House "Belaruskaya Navuka"vestifm-180Research ArticleИНФОРМАТИКАINFORMATICSДВУХУРОВНЕВЫЙ ТАЙЛИНГ И ЕГО ПРИМЕНЕНИЕ ПРИ ПРОСТРАНСТВЕННО-ВРЕМЕННОМ ОТОБРАЖЕНИИ АЛГОРИТМОВ НА ПАРАЛЛЕЛЬНЫЕ АРХИТЕКТУРЫTWO-LEVEL TILING AND ITS APPLICATION IN THE SPACE-TIME MAPPING OF ALGORITHMS ONTO PARALLEL ARCHITECTURESСоболевскийП. И.SobolevskyP. I.sobolevsky@im.bas-net.byБахановичС. В.BakhanovichS. V.bsv@im.bas-net.byИнститут математики Национальной академии наук БеларусиInstitute of Mathematics of the National Academy of Sciences of Belarus201603082016028597Copyright © Соболевский П.И., Баханович С.В., 20162016Соболевский П.И., Баханович С.В.Sobolevsky P.I., Bakhanovich S.V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://vestifm.belnauka.by/jour/article/view/180

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

 

The idea of application of two-level tiling at space-time mapping of algorithms onto parallel computing systems is proposed. A formalized method of parameterized two-level tiling is developed. The formulas for determination of global dependences between different-level tiles are constructed. The formal representation of sets of iterations generating these dependences is obtained. The representation is given in the form of polyhedra with an explicit expression of their boundaries. A formalized method of space-time mapping onto supercomputers is developed. The method is based on the locally parallel globally sequential mapping strategy and the designed method of two-level tiling. The method realizes the proposed idea of space-time mapping in integration with tiling.

 

тайлингпространственно-временное отображениелокально параллельная глобально последовательная стратегияпараллельная архитектурасуперкомпьютерtilingspace-time mappinglocally sequential globally parallel strategyparallel architecturesupercomputerReferencesXue, J. Loop Tiling For Parallelism / J. Xue. – Norwell: Kluwer Academic Publishers, 2000.Xue, J. Loop Tiling For Parallelism / J. Xue. – Norwell: Kluwer Academic Publishers, 2000.Irigoin, F. Supernode partitioning / F. Irigoin, R. Triolet // Proceedings of the ACM SIGPLAN Symposium on Principles of Programming Languages, San Diego, California, Jan. 1988. – San Diego, 1988. – P. 319–329.Irigoin, F. Supernode partitioning / F. Irigoin, R. Triolet // Proceedings of the ACM SIGPLAN Symposium on Principles of Programming Languages, San Diego, California, Jan. 1988. – San Diego, 1988. – P. 319–329.Parameterized tiled loops for free / L. Renganarayanan [et al.] // SIGPLAN Conf. on Programming Language Design and Implementation. – New York: ASM Press, 2007. – P. 405–414.Parameterized tiled loops for free / L. Renganarayanan [et al.] // SIGPLAN Conf. on Programming Language Design and Implementation. – New York: ASM Press, 2007. – P. 405–414.DynTile: Parametric Tiled Loop Generation for Parallel Execution on Multicore Processors / A. Hartono [et al.] // 24th International Parallel and Distributed Proc. Symposium (2010 IPDPS Conference), Atlanta, April 2010. – Atlanta, 2010.DynTile: Parametric Tiled Loop Generation for Parallel Execution on Multicore Processors / A. Hartono [et al.] // 24th International Parallel and Distributed Proc. Symposium (2010 IPDPS Conference), Atlanta, April 2010. – Atlanta, 2010.Parametric tiling of affine loop nests / S. Tavarageri [et al.] // Proc. 15th Workshop on Compilers for Parallel Computers, Vienna, Austria, July 2010. – Vienna, 2010.Parametric tiling of affine loop nests / S. Tavarageri [et al.] // Proc. 15th Workshop on Compilers for Parallel Computers, Vienna, Austria, July 2010. – Vienna, 2010.Баханович, С. В. Параметризованный тайлинг: точные аппроксимации и анализ глобальных зависимостей / С. В. Баханович, П. И. Соболевский // ЖВМ. – 2014. – Т. 54, № 11. – С. 1817–1828.Баханович, С. В. Параметризованный тайлинг: точные аппроксимации и анализ глобальных зависимостей / С. В. Баханович, П. И. Соболевский // ЖВМ. – 2014. – Т. 54, № 11. – С. 1817–1828.Primetile: A Parametric Multi-Level Tiler for Imperfect Loop Nests / A. Hartono [et al.] // Proc. of the 23rd Int. Conf. on Supercomputing (ICS’09). – P. 147–157.Primetile: A Parametric Multi-Level Tiler for Imperfect Loop Nests / A. Hartono [et al.] // Proc. of the 23rd Int. Conf. on Supercomputing (ICS’09). – P. 147–157.Баханович, С. В. Отображение алгоритмов на параллельные архитектуры заданной размерности и заданного размера / С. В. Баханович, Н. А. Лиходед // Вес. Нац. акад. навук Беларусi. Сер. фiз.-мат. навук. – 2003. – № 1. – C. 101–108.Баханович, С. В. Отображение алгоритмов на параллельные архитектуры заданной размерности и заданного размера / С. В. Баханович, Н. А. Лиходед // Вес. Нац. акад. навук Беларусi. Сер. фiз.-мат. навук. – 2003. – № 1. – C. 101–108.Лиходед, Н. А. Получение аффинных преобразований для улучшения локальности гнезд циклов / Н. А. Лиходед, С. В. Баханович, А. В. Жерело // Программирование. – 2005. – № 5. – С. 52–65.Лиходед, Н. А. Получение аффинных преобразований для улучшения локальности гнезд циклов / Н. А. Лиходед, С. В. Баханович, А. В. Жерело // Программирование. – 2005. – № 5. – С. 52–65.

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