PARAMETERIZED TILING: THE DEFINITION OF THE BOUNDARIES OF LOCAL LOOPS IN PARTIAL TILES
Abstract
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.
About the Authors
P. I. Sobolevsky
Институт математики Национальной академии наук Беларуси, Минск
Belarus
Belarus
S. V. Bakhanovich
Institute of Mathematics of the National Academy of Sciences of Belarus, Minsk
Belarus
Belarus
References
1. Xue J. Loop Tiling For Parallelism. Norwell, 2000.
2. 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.
3. 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.
4. Соболевский П. И., Баханович С. В. // Докл. НАН Беларуси. 2013. Т. 57, № 1. С. 21–26.
5. Баханович С. В., Соболевский П. И. Параметризованный тайлинг: точные аппроксимации и анализ глобальных зависимостей // Журн. вычисл. математики и мат. физики. 2014. Т. 54, № 11. С. 1817–1828.
6. Hartono A., Baskaran M., Ramanujam J., Sadayappan P. // 24th Intern. Parallel and Distributed Proc. Symp. (2010 IPDPS Conf.), Atlanta, April 2010. [S. l.], 2010.
7. Tavarageri S., Hartono A., Baskaran M. et al. // Proc. 15th Workshop on Compilers for Parallel Computers, Vienna, Austria, July 2010. [S. l.], 2010.
8. Лиходед Н. А., Соболевский П. И. // Весцi НАН Беларусi. Сер. фiз.-мат. навук. 2012. № 2. С. 107–113.
Review
Views: 731
Email this article 