TWO-LEVEL TILING AND ITS APPLICATION IN THE SPACE-TIME MAPPING OF ALGORITHMS ONTO PARALLEL ARCHITECTURES
Abstract
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.
About the Authors
P. I. Sobolevsky
Institute of Mathematics of the National Academy of Sciences of Belarus
Belarus
Belarus
S. V. Bakhanovich
Institute of Mathematics of the National Academy of Sciences of Belarus
Belarus
Belarus
References
1. Xue, J. Loop Tiling For Parallelism / J. Xue. – Norwell: Kluwer Academic Publishers, 2000.
2. 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.
3. 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.
4. 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.
5. Parametric tiling of affine loop nests / S. Tavarageri [et al.] // Proc. 15th Workshop on Compilers for Parallel Computers, Vienna, Austria, July 2010. – Vienna, 2010.
6. Баханович, С. В. Параметризованный тайлинг: точные аппроксимации и анализ глобальных зависимостей / С. В. Баханович, П. И. Соболевский // ЖВМ. – 2014. – Т. 54, № 11. – С. 1817–1828.
7. 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.
8. Баханович, С. В. Отображение алгоритмов на параллельные архитектуры заданной размерности и заданного размера / С. В. Баханович, Н. А. Лиходед // Вес. Нац. акад. навук Беларусi. Сер. фiз.-мат. навук. – 2003. – № 1. – C. 101–108.
9. Лиходед, Н. А. Получение аффинных преобразований для улучшения локальности гнезд циклов / Н. А. Лиходед, С. В. Баханович, А. В. Жерело // Программирование. – 2005. – № 5. – С. 52–65.
Review
Views: 697
Email this article 