Анализ глобальных зависимостей в гексагональном тайлинге
Соболевский П. И.,
Баханович С. В.
2020
Техника тайлинга широко применяется на практике для решения задач эффективного использования многоуровневой памяти и оптимизации обменов данными при разработке как последовательных, так и параллельных программ. В работе исследуется задача получения глобальных, уровня тайлов, зависимостей. Задача решается в контексте применения параметризованного гексагонального тайлинга к алгоритмам с двумерной областью вычислений. Приведено формализованное определение гексагонального тайла, а также представлены критерии плотного покрытия области вычислений гексагональными тайлами. 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
Похожие публикации