Global dependences in hexagonal tiling
https://doi.org/10.29235/1561-2430-2020-56-1-114-126
Abstract
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.
Supporting agencies: This paper was supported by the State Scientific Research Program “Convergence 2020”.
About the Authors
P. I. Sobolevsky
Institute of Mathematics of the National Academy of Sciences of Belarus
Belarus
Belarus
Pavel I. Sobolevsky – Dr. Sc. (Physics and Mathematics), Professor, Chief Researcher
Surganov Str., 11, 220072, Minsk
S. V. Bakhanovich
Institute of Mathematics of the National Academy of Sciences of Belarus
Belarus
Belarus
Sergey V. Bakhanovich – Ph. D. (Physics and Mathematics), Deputy Director for Sciences and Innovation
Surganov Str., 11, 220072, Minsk
References
1. Xue J. Loop Tiling for Parallelism. Norwell, MA, USA, Kluwer Academic Publ., 2000. 256 p. https://doi.org/10.1007/978-1-4615-4337-4
2. Renganarayanan 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.1250780
3. Hartono 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
4. 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
5. 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).
6. Grosser 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
7. Sobolevsky 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
Review
Views: 1043
Email this article 