vestifmИзвестия Национальной академии наук Беларуси. Серия физико-математических наукProceedings of the National Academy of Sciences of Belarus. Physics and Mathematics Series1561-24302524-2415The Republican Unitary Enterprise Publishing House "Belaruskaya Navuka"10.29235/1561-2430-2020-56-1-114-126vestifm-510Research ArticleИНФОРМАТИКАINFORMATICSАнализ глобальных зависимостей в гексагональном тайлингеGlobal dependences in hexagonal tilingСоболевскийП. И.SobolevskyP. I.

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

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

Pavel I. Sobolevsky – Dr. Sc. (Physics and Mathematics), Professor, Chief Researcher

Surganov Str., 11, 220072, Minsk

sobolevsky@im.bas-net.byБахановичС. В.BakhanovichS. V.

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

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

Sergey V. Bakhanovich – Ph. D. (Physics and Mathematics), Deputy Director for Sciences and Innovation

Surganov Str., 11, 220072, Minsk

bsv@im.bas-net.byИнститут математики Национальной академии наук БеларусиInstitute of Mathematics of the National Academy of Sciences of Belarus202006042020561114126Copyright © Соболевский П.И., Баханович С.В., 20202020Соболевский П.И., Баханович С.В.Sobolevsky P.I., Bakhanovich S.V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://vestifm.belnauka.by/jour/article/view/510

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

Tiling is a widely used technique to solve the problems of the efficient use of multilevel memory and optimize data exchanges when developing both sequential and parallel programs. This paper investigates the problem of obtaining global dependencies, i.e. informational dependencies between tiles. The problem is solved in the context of parametrized hexagonal tiling in application to algorithms with a two-dimensional computational domain. The paper includes a formalized definition of the hexagonal tile and the criteria for dense coverage of the computational domain with hexagonal tiles. Herein, we have formulated a statement that permits to obtain all global dependencies between tiles. Formulas are constructed for the determination of sets of iterations of hexagonal tiles generating these dependencies. The sets of iterations that generate global dependencies are obtained in the form of polyhedra with an explicit expression of their boundaries.

тайлинггексагональный тайлингтайлоптимизация программсуперкомпьютерtilinghexagonal tilingtilecode optimizationsupercomputerРабота выполнена в рамках подпрограммы «Математические методы» Государственной программы научных исследований «Конвергенция 2020».This paper was supported by the State Scientific Research Program “Convergence 2020”.ReferencesXue, J. Loop Tiling for Parallelism / J. Xue. – Norwell: Kluwer Academic Publ., 2000. https://doi.org/10.1007/978-1-4615-4337-4Xue J. Loop Tiling for Parallelism. Norwell, MA, USA, Kluwer Academic Publ., 2000. 256 p. https://doi.org/10.1007/978-1-4615-4337-4Parameterized tiled loops for free / L. Renganarayanan [et al.] // ACM SIGPLAN Notices. – 2007. – Vol. 42, № 6. – P. 405–414. https://doi.org/10.1145/1273442.1250780Renganarayanan L., Kim D., Rajopadhye S., Strout M. Parameterized tiled loops for free. ACM SIGPLAN Notices, 2007, vol. 42, no. 6, pp. 405–414. https://doi.org/10.1145/1273442.1250780DynTile: 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.5470459Hartono A., Baskaran M., Ramanujam J., Sadayappan P. DynTile: Parametric Tiled Loop Generation for Parallel Execution on Multicore Processors. IEEE International Symposium on Parallel & Distributed Processing (IPDPS). Atlanta, 2010. https://doi.org/10.1109/ipdps.2010.5470459Соболевский, П. И. Параметризованный тайлинг: точные аппроксимации и анализ глобальных зависимостей / П. И. Соболевский, С. В. Баханович // Журн. вычисл. математики и мат. физики. – 2014. – Т. 54, № 11. – С. 1817–1828.Bakhanovich S. V., Sobolevsky P. I. Parametrized Tiling: Accurate Approximations and Analysis of Global Dependences. Computational Mathematics and Mathematical Physics, 2014, vol. 54, no. 11, pp. 1748–1758. https://doi.org/10.1134/S0965542514110037Лиходед, Н. А. Информационная структура зернистых алгоритмов с однородными зависимостями / Н. А. Лиходед, П. И. Соболевский // Докл. Нац. акад. наук Беларуси. – 2011. – Т. 55, № 2. – С. 22–26.Likhoded N. А., Sobolevsky P. I. Information structure of grained algorithms with homogeneous dependencies. Doklady Natsional’noi akademii nauk Belarusi = Doklady of the National Academy of Sciences of Belarus, 2011, vol. 55, no 2. pp. 22–26 (in Russian).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/s0129626414410023Grosser T., Verdoolaege S., Cohen A., Sadayappan P. The Relation Between Diamond Tiling and Hexagonal Tiling. Parallel Processing Letters, vol. 24, no. 3, pp. 1441002. https://doi.org/10.1142/s0129626414410023Соболевский, П. И. Плотные покрытия области вычислений гексагональными тайлами / П. И. Соболевский, С. В. Баханович // Докл. Нац. акад. наук Беларуси. – 2018. – Т. 62, № 5. – С. 525–530. https://doi.org/10.29235/1561-8323-2018-62-5-525-530Sobolevsky P. I., Bakhanovich S. V. Dense coverage of the computational domain by hexagonal tiles. Doklady Natsional’noi akademii nauk Belarusi = Doklady of the National Academy of Sciences of Belarus, 2018, vol. 62, no 5, pp. 525–530 (in Russian). https://doi.org/10.29235/1561-8323-2018-62-5-525-530

The authors declare that there are no conflicts of interest present.