доктор физикоматематических наук, профессор кафедры вычислительной математики факультета прикладной математики и информатики
D. Sc. (Physics and Mathematics), Professor of the Department of Applied Mathematics
ассистент кафедры вычислительной математики факультета прикладной математики и информатики
Junior Researcher
Алгоритм, реализуемый на параллельном компьютере с распределенной памятью, имеет, как правило, зернистую структуру: множество операций разбито на подмножества, называемые зернами вычислений. Одним из современных подходов к получению зернистых вариантов алгоритмов является тайлинг – преобразование, основанное на информационных разрезах итерационного пространства, в результате которого получаются макрооперации-тайлы. Операции одного тайла выполняются атомарно, как одна единица вычислений, а обмен данными происходит массивами. В настоящей работе для алгоритмов, заданных вложенными многомерными циклами, предложен способ построения зернистых вычислительных процессов, логически организованных в двумерную структуру. По сравнению с одномерными структурами, использование двумерных структур возможно в меньшем числе случаев, но может иметь преимущества при реализации алгоритмов на параллельных компьютерах с распределенной памятью. К числу возможных преимуществ относятся уменьшение объема коммуникационных операций, уменьшение разгона и торможения вычислений, потенциально большее число вычислительных процессов, организация обменных операций только в пределах строк или столбцов процессов. Представленные исследования обобщают на случай двумерной структуры некоторые аспекты метода построения параллельных вычислительных процессов, организованных в одномерную структуру. В частности, исследована возможность организовать полностью загруженные работой параллельные вычислительные процессы. Показано, что при определенных ограничениях на структуру и длину циклов достаточно произвести тайлинг по трем координатам многомерного итерационного пространства. В более ранних теоретических исследованиях параллельность зернистых вычислений гарантировалась при наличии информационных разрезов по всем координатам итерационного пространства, а для более простого случая одномерной структуры – по двум координатам.
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.
The authors declare that there are no conflicts of interest present.