ДВУХУРОВНЕВЫЙ ТАЙЛИНГ И ЕГО ПРИМЕНЕНИЕ ПРИ ПРОСТРАНСТВЕННО-ВРЕМЕННОМ ОТОБРАЖЕНИИ АЛГОРИТМОВ НА ПАРАЛЛЕЛЬНЫЕ АРХИТЕКТУРЫ
Аннотация
Предложена идея использования двухуровневого тайлинга для решения задачи пространственно-временного отображения алгоритмов на параллельные вычислительные системы заданной размерности и размера. Разработан формализованный метод параметризованного двухуровневого тайлинга. Получены формулы для определения векторов глобальных зависимостей между тайлами первого и второго уровней, а также формальное представление множеств итераций, порождающих эти зависимости, в виде многогранников с явным выражением их границ. На основе разработанного метода двухуровневого тайлинга и локально параллельной глобально последовательной cтратегии отображения предложен формализованный метод решения задачи пространственно-временного отображения алгоритмов в интеграции с тайлингом.
Об авторах
П. И. Соболевский
Институт математики Национальной академии наук Беларуси
Беларусь
Беларусь
С. В. Баханович
Институт математики Национальной академии наук Беларуси
Беларусь
Беларусь
Список литературы
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.
Рецензия
Просмотров: 692
Послать статью по эл. почте 