Global dependences in hexagonal tiling
P. I. Sobolevsky, S. V. Bakhanovich · Proceedings of the National Academy of Sciences of Belarus Physics and Mathematics Series · 2020
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.