Preview

Известия Национальной академии наук Беларуси. Серия физико-математических наук

Расширенный поиск

ДВУХУРОВНЕВЫЙ ТАЙЛИНГ И ЕГО ПРИМЕНЕНИЕ ПРИ ПРОСТРАНСТВЕННО-ВРЕМЕННОМ ОТОБРАЖЕНИИ АЛГОРИТМОВ НА ПАРАЛЛЕЛЬНЫЕ АРХИТЕКТУРЫ

Аннотация

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


Рецензия

Просмотров: 628


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1561-2430 (Print)
ISSN 2524-2415 (Online)