Анализ глобальных зависимостей в гексагональном тайлинге


https://doi.org/10.29235/1561-2430-2020-56-1-114-126

Полный текст:


Аннотация

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


Об авторах

П. И. Соболевский
Институт математики Национальной академии наук Беларуси
Беларусь

Соболевский Павел Иосифович – доктор физико-математических наук, профессор, главный научный сотрудник

ул. Сурганова, 11, 220072, г. Минск



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

Баханович Сергей Викторович – кандидат физико-математических наук, заместитель директора по научной и инновационной работе

ул. Сурганова, 11, 220072, г. Минск



Список литературы

1. Xue, J. Loop Tiling for Parallelism / J. Xue. – Norwell: Kluwer Academic Publ., 2000. https://doi.org/10.1007/978-1-4615-4337-4

2. Parameterized tiled loops for free / L. Renganarayanan [et al.] // ACM SIGPLAN Notices. – 2007. – Vol. 42, № 6. – P. 405–414. https://doi.org/10.1145/1273442.1250780

3. DynTile: Parametric Tiled Loop Generation for Parallel Execution on Multicore Processors / A. Hartono [et al.] // IEEE Int.l Symp. on Parallel & Distributed Processing (IPDPS). – Atlanta, 2010. https://doi.org/10.1109/ipdps.2010.5470459

4. Соболевский, П. И. Параметризованный тайлинг: точные аппроксимации и анализ глобальных зависимостей / П. И. Соболевский, С. В. Баханович // Журн. вычисл. математики и мат. физики. – 2014. – Т. 54, № 11. – С. 1817–1828.

5. Лиходед, Н. А. Информационная структура зернистых алгоритмов с однородными зависимостями / Н. А. Лиходед, П. И. Соболевский // Докл. Нац. акад. наук Беларуси. – 2011. – Т. 55, № 2. – С. 22–26.

6. The Relation Between Diamond Tiling and Hexagonal Tiling / T. Grosser [et al.] // Parallel Processing Letters. – Vol. 24, № 3. – P. 1441002. https://doi.org/10.1142/s0129626414410023

7. Соболевский, П. И. Плотные покрытия области вычислений гексагональными тайлами / П. И. Соболевский, С. В. Баханович // Докл. Нац. акад. наук Беларуси. – 2018. – Т. 62, № 5. – С. 525–530. https://doi.org/10.29235/1561-8323-2018-62-5-525-530


Дополнительные файлы

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

Обратные ссылки

  • Обратные ссылки не определены.


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


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