## 4 Parallel Version of the Improved Algorithm and Its Software Implementation
### Taking into Account the Capabilities of the Standard MPI-4
``` defconjugate_gradient_method(A_part,b_part,x_part,comm_row,comm_col,N): N_part=size(x_part);M_part=size(b_part) x_classic_part=None delta=info(float64).eps requests=[MPI.Request()foriinrange(5)] scalar_product_temp=empty(1,dtype=float64) scalar_product_rr=array(0,dtype=float64) scalar_product_pq=array(0,dtype=float64) Ap_part_temp=empty(M_part,dtype=float64) Ap_part=empty(M_part,dtype=float64) q_part_temp=empty(N_part,dtype=float64) q_part=empty(N_part,dtype=float64) criterion_temp=empty(1,dtype=float64) criterion=array(0,dtype=float64) requests[0]=comm_row.Allreduce_init([scalar_product_temp,1,MPI.DOUBLE],[scalar_product_rr,1,MPI.DOUBLE],op=MPI.SUM) requests[1]=comm_row.Allreduce_init([Ap_part_temp,M_part,MPI.DOUBLE],[Ap_part,M_part,MPI.DOUBLE],op=MPI.SUM) requests[2]=comm_row.Allreduce_init([criterion_temp,1,MPI.DOUBLE],[criterion,1,MPI.DOUBLE],op=MPI.SUM) requests[3]=comm_col.Allreduce_init([q_part_temp,N_part,MPI.DOUBLE],[q_part,N_part,MPI.DOUBLE],op=MPI.SUM) requests[4]=comm_row.Allreduce_init([scalar_product_temp,1,MPI.DOUBLE],[scalar_product_pq,1,MPI.DOUBLE],op=MPI.SUM) s=1 P_part=zeros(N_part,dtype=float64) whileTrue: ifs==1: Ax_part_temp=dot(A_part,x_part) Ax_part=empty(M_part,dtype=float64) comm_row.Allreduce([Ax_part_temp,M_part,MPI.DOUBLE],[Ax_part,M_part,MPI.DOUBLE],op=MPI.SUM) b_part=Ax_part-b_part r_part_temp=dot(A_part.T,b_part)r_part = empty(N_part,dtype=float64)  comm_col.Allreduce([r_part_temp, N_part, MPI.DOUBLE],  [r_part, N_part, MPI.DOUBLE],  op=MPI.SUM)

sigma2_r_part = zeros(N_part,dtype=float64)  else :  r_part = r_part - q_part/scalar_product_pq

scalar_product_temp[:] = array(dot(r_part, r_part),  dtype=float64)

MPI.Prequest.Start(requests[0])  MPI.Request.Wait(requests[0], status=None)  p_part = p_part + r_part/scalar_product_rr

Ap_part_temp[:] = dot(A_part, p_part)  MPI.Prequest.Start(requests[1])  if s >= 2 :  sigma2_r_part = sigma2_r_part + \  q_part**2/scalar_product_pq**2  criterion_temp[:] = array(delta**2*sum(sigma2_r_part)/  scalar_product_rr, dtype=float64)

MPI.Prequest.Start(requests[2])  MPI.Request.Wait(requests[1], status=None)  q_part_temp[:] = dot(A_part.T, Ap_part)  MPI.Prequest.Start(requests[3])  MPI.Request.Wait(requests[3], status=None)

scalar_product_temp[:] = array(dot(p_part, q_part),  dtype=float64)

MPI.Prequest.Start(requests[4])  MPI.Request.Wait(requests[4], status=None)

MPI.Request.Wait(requests[2], status=None)  if criterion >= 1 :  return x_part, s, x_classic_part

x_part = x_part - p_part/scalar_product_pq

if s == N + 1 :  x_classic_part = x_part.copy()

Estimation of the Efficiency and Scalability of a Software Implementation of the Parallel Algorithm

This section discusses the efficiency and scalability of the proposed software implementation of the parallel algorithm. First (see Section 5.1), a description of the test example and the multiprocessor system used for test calculations is given. Then (see Section 5.2), the results of studying the proposed software implementations for the presence of strong and strict scaling are discussed. ### Description of the Test Example

To test the efficiency of software implementations of the parallel algorithm, the section \"compute\" of the supercomputer \"Lomonosov-2\" [28] of the Research Computing Center of Lomonosov Moscow State University was used. Each node in the section contains 14-coreIntel Xeon E5-2697 v3 2.60 GHz processors with 64 GB of RAM (4.5 GB per core) and a Tesla K40s video-card with 11.56 GB of video memory. The problem with \(M=90,000\), \(N=70,000\) was chosen as a test problem. The choice of such parameters is due to the fact that we want to carry out calculations for a system with the largest possible matrix \(A\), but at the same time this matrix should fit into the RAM of one computing node (otherwise we will not be able to detect the running time \(T_{1}\) of the sequential version of programs). In the case of the chosen parameters, \(N\times M\times 8\) bytes \(=46.93\) GB is required to store matrix \(A\).