## 3 Approaches to Building a Parallel Algorithm and Its Software Implementation
### Distribution of Data by MPI Processes Participating in Computations
Then, the corresponding summands \(b_{part\_temp_{(m,n)}}\) along each line of the process grid (i.e., index \(m\) is fixed) must be collected (due to message exchange between processes) at least on one process and summed up. Thus, this parallel algorithm (taking into account the two-dimensional division of matrix \(A\) into blocks) contains the following features. 1. Each process should store not the whole vector \(x\), but only a part \(x_{part\_{(n)}}\) of this vector. The vector \(x_{part\_{(n)}}\) will have to be sent not to all processes of the comm communicator, but only to a part of the processes of this communicator--to the processes of the column with index \(n\) of the process grid. In this case, the transfer of data among the processes of each column of the process grid can be organized in parallel with the transfer of data among the processes of other columns of the grid of processes, which will give a gain in time. 2. When calculating part \(b_{part\_{(m)}}\) of the final vector \(b\), it is necessary to exchange messages not to all processes of the comm communicator, but only to part of the processes of this communicator--to the processes of the line with index \(m\) of the introduced grid of processes. In this case, the data transfer along each line of the process grid can be organized in parallel with the transfer of data among the processes of other lines of the process grid, which will also give a gain in time. Let us now describe some features of the software implementation of this algorithm, taking into account the capabilities of the MPI parallel programming technology. As is known, message exchange between processes for the aforementioned algorithm, organized using the MPI functions Send() and Recv(), is possible, but inefficient. It is much more efficient to use the MPI functions of the collective interaction of processes. However, such functions must be called on all processes of the communicator. At the moment, we are working only with the communicator comm, which, in addition to the processes that we want to use (processes from a separate column or row of the process grid), also contains other processes that will not interact with one another. Thus, we come to the need to create additional communicators that will contain only those groups of processes within which we want to organize data exchange interactions using the functions of collective interaction of processes. Such communicator groups can be created, for example, as follows. comm_col = comm.Split(rank % num_col, rank) comm_row = comm.Split(rank // num_col, rank)  
Here, for example, the communicators comm_col are generated in the first line. Let us pay attention to the fact that it is the communicators (in the plural) that are generated, and not just one communicator. Let us give an explanatory example for the case of nine MPI processes (that is, numprocs = 9). The first argument of the Split() function is the color value, defined by us as rank % num_col, which, for processes with rank = 0, 1, 2, 3, 4, 5, 6, 7, 8, will be 0, 1, 2, 0, 1, 2, 0, 1, 2. Thus, three communicators will be created: the first one will include processes with the value color = 0, the second one--with the value color = 1, the third one--with the value color = 2. One can give a visual interpretation of such a grouping of processes--see Figure 2: if the processes of the communicator comm form a two-dimensional grid, then the processes of the communicators comm_col are columns of this two-dimensional grid of processes. In this case, the object comm_col on each MPI process will contain information about different processes. For example, on processes with rank = 1, 4 of the communicator comm, the object comm_col will contain information about processes with rank = 1, 4, 7 of the communicator comm. And on a process with rank = 2 of the communicator comm, the object comm_col will contain information about processes with rank = 2, 5, 8 of the communicator comm.