vestifmИзвестия Национальной академии наук Беларуси. Серия физико-математических наукProceedings of the National Academy of Sciences of Belarus. Physics and Mathematics Series1561-24302524-2415The Republican Unitary Enterprise Publishing House "Belaruskaya Navuka"vestifm-97Research ArticleИНФОРМАТИКАINFORMATICSПАРАМЕТРИЗОВАННЫЙ ТАЙЛИНГ: ОПРЕДЕЛЕНИЕ ГРАНИЦ ЛОКАЛЬНЫХ ЦИКЛОВ В НЕПОЛНЫХ ТАЙЛАХPARAMETERIZED TILING: THE DEFINITION OF THE BOUNDARIES OF LOCAL LOOPS IN PARTIAL TILESСоболевскийП. И.SobolevskyP. I.БахановичС. В.BakhanovichS. V.Институт математики Национальной академии наук Беларуси, МинскBelarusИнститут математики Национальной академии наук Беларуси, МинскInstitute of Mathematics of the National Academy of Sciences of Belarus, Minsk20151805201602112120Copyright © Соболевский П.И., Баханович С.В., 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/97

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

The aspects of parameterized tiling in application to algorithms with index domain represented by a convex polyhedron are investigated. The structure of the set of partial tiles is proposed and the formulas to determine this set are constructed. The formula to define the boundaries of local loops in partial tiles is obtained as well. These formulas enable one to minimize the calculation time of local loop boundaries in the implementation of the tiling in sequential and parallel programs.

 

ReferencesXue J. Loop Tiling For Parallelism. Norwell, 2000.Xue J. Loop Tiling For Parallelism. Norwell, 2000.Irigoin F., Triolet R. // Proc. of the ACM SIGPLAN Symp. on Principles of Programming Languages. San Diego, California, Jan. 1988. [S. l.], 1988. P. 319–329.Irigoin F., Triolet R. // Proc. of the ACM SIGPLAN Symp. on Principles of Programming Languages. San Diego, California, Jan. 1988. [S. l.], 1988. P. 319–329.Renganarayanan L., Kim D., Rajopadhye S., Strout M. // SIGPLAN Conf. on Programming Language Design and Implementation, New York, NY, USA, 2007. [S. l.], 2007. P. 405–414.Renganarayanan L., Kim D., Rajopadhye S., Strout M. // SIGPLAN Conf. on Programming Language Design and Implementation, New York, NY, USA, 2007. [S. l.], 2007. P. 405–414.Соболевский П. И., Баханович С. В. // Докл. НАН Беларуси. 2013. Т. 57, № 1. С. 21–26.Соболевский П. И., Баханович С. В. // Докл. НАН Беларуси. 2013. Т. 57, № 1. С. 21–26.Баханович С. В., Соболевский П. И. Параметризованный тайлинг: точные аппроксимации и анализ глобальных зависимостей // Журн. вычисл. математики и мат. физики. 2014. Т. 54, № 11. С. 1817–1828.Баханович С. В., Соболевский П. И. Параметризованный тайлинг: точные аппроксимации и анализ глобальных зависимостей // Журн. вычисл. математики и мат. физики. 2014. Т. 54, № 11. С. 1817–1828.Hartono A., Baskaran M., Ramanujam J., Sadayappan P. // 24th Intern. Parallel and Distributed Proc. Symp. (2010 IPDPS Conf.), Atlanta, April 2010. [S. l.], 2010.Hartono A., Baskaran M., Ramanujam J., Sadayappan P. // 24th Intern. Parallel and Distributed Proc. Symp. (2010 IPDPS Conf.), Atlanta, April 2010. [S. l.], 2010.Tavarageri S., Hartono A., Baskaran M. et al. // Proc. 15th Workshop on Compilers for Parallel Computers, Vienna, Austria, July 2010. [S. l.], 2010.Tavarageri S., Hartono A., Baskaran M. et al. // Proc. 15th Workshop on Compilers for Parallel Computers, Vienna, Austria, July 2010. [S. l.], 2010.Лиходед Н. А., Соболевский П. И. // Весцi НАН Беларусi. Сер. фiз.-мат. навук. 2012. № 2. С. 107–113.Лиходед Н. А., Соболевский П. И. // Весцi НАН Беларусi. Сер. фiз.-мат. навук. 2012. № 2. С. 107–113.

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