Анализ глобальных зависимостей в гексагональном тайлинге
https://doi.org/10.29235/1561-2430-2020-56-1-114-126
Анатацыя
Техника тайлинга широко применяется на практике для решения задач эффективного использования многоуровневой памяти и оптимизации обменов данными при разработке как последовательных, так и параллельных программ. В работе исследуется задача получения глобальных, уровня тайлов, зависимостей. Задача решается в контексте применения параметризованного гексагонального тайлинга к алгоритмам с двумерной областью вычислений. Приведено формализованное определение гексагонального тайла, а также представлены критерии плотного покрытия области вычислений гексагональными тайлами. Cформулировано и доказано утверждение, позволяющее получить все глобальные зависимости между тайлами. Построены формулы, дающие возможность определить множества итераций гексагональных тайлов, порождающих эти зависимости. Множества итераций, порождающих глобальные зависимости, получены в виде многогранников с явным выражением их границ.
Аб аўтарах
П. Соболевский
Институт математики Национальной академии наук Беларуси
Беларусь
Беларусь
С. Баханович
Институт математики Национальной академии наук Беларуси
Беларусь
Беларусь
Спіс літаратуры
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
##reviewer.review.form##
Праглядаў: 1046
Паслаць артыкул па эл. пошце 