Tiled parallel 2D computational processes

The algorithm implemented on a parallel computer with distributed memory has, as a rule, a tiled structure: a set of operations is divided into subsets, called tiles. One of the modern approaches to obtaining tiled versions of algorithms is a tiling transformation based on information sections of the iteration space, resulting in macro-operations (tiles). The operations of one tile are performed atomically, as one unit of calculation, and the data exchange is done by arrays. The method of construction of tiled computational processes logically organized as a two-dimensional structure for algorithms given by multidimensional loops is stated. Compared to one-dimensional structures, the use of two-dimensional structures is possible in a smaller number of cases, but it can have advantages when implementing algorithms on parallel computers with distributed memory. Among the possible advantages are the reduction of the volume of communication operations, the reduction of acceleration and deceleration of computations, potentially a greater number of computation processes and the organization of data exchange operations only within the rows or columns of processes. The results are a generalization of some aspects of the method of construction of parallel computational processes organized in a one-dimensional structure to the case of a two-dimensional structure. It is shown that under certain restrictions on the structure and length of loops, it is sufficient to perform tiling on three coordinates of a multidimensional iteration space. In the earlier theoretical studies, the parallelism of tiled computations was guaranteed in the presence of information sections in all coordinates of the iteration space, and for a simpler case of a one-dimensional structure, in two coordinates.

1. Xue J., Cai W. Time-minimal tiling when rise is larger than zero. Parallel Computing, 2002, vol. 28, no. 6, pp. 915–939. https://doi.org/10.1016/s0167-8191(02)00098-4

2. Kim D., Rajopadhye S. Parameterized Tiling for Imperfectly Nested Loops. Technical Report CS-09-101. Colorado State University, Department of Computer Science, February 2009. 21 p.

3. Dathathri R., Mullapudi R. T., Bondhugula U. Compiling Affine Loop Nests for a Dynamic Scheduling Runtime on Shared and Distributed Memory. ACM Transactions on Parallel Computing (TOPC), 2016, vol. 3, no. 2, pp. 1–28. https://doi.org/10.1145/ 2948975

4. Likhoded N. A., Tolstikov A. A. Parallel sequences of grain computations. Doklady Natsional’noi akademii nauk Belarusi = Doklady of the National Academy of Sciences of Belarus, 2010, vol. 54, no. 4, pp. 36–41 (in Russian).

5. Tolstikov A. A., Likhoded N. A. Correctness of tiling of algorithms for organization of tiled parallel computational processes. Mezhdunarodnyi kongress po informatike: informatsionnye sistemy i tekhnologii CSIST’2011, 31 oktyabrya – 3 noyabrya 2011 g. T. 2 [International Congress on Computer Science: Information Systems and Technologies CSIST’2011, November 2011. Vol. 2]. Minsk, Belarusian State University, 2011, pp. 122–126 (in Russian).

6. Voevodin V. V., Voevodin Vl. V. Parallel Computations. St. Petersburg, BKhV-Petersburg Publ., 2002. 608 p. (in Russian).

7. Sobolevsky P. I., Bakhanovich S. V. Two-level tiling and its application in the space-time mapping of algorithms onto parallel architectures. Vestsі Natsyianal’nai akademіі navuk Belarusі. Seryia fіzіka-matematychnykh navuk = Proceedings of the National Academy of Sciences of Belarus. Physics and Mathematics series, 2016, no. 2, pp. 85–97 (in Russian).

8. Renganarayanan L., Kim D., Rajopadhye S., Strout M. M. Parameterized tiled loops for free. Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation - PLDI ‘07. San Diego, California, USA, June 2007, pp. 126–138. https://doi.org/10.1145/1250734.1250780

9. Samarskii A. A., Nikolaev E. S. Methods for Solving of the Grid Equations. Moscow, Nauka Publ., 1978. 592 p. (in Russian).