Thread: MPI - linear pipeline solution for jacobi iteration

hello

i have a problem on how to write 2 parallel code by using MPI programming with c/c++ to solve a system of linear equation by using jacobi and gauss-seidel iteration method. and it is using pipelining.

here is sample code of an equation solve by using pipeline:



F = a0x0 + a1x1 + a2x2 …….+ k + an-1xn-1

Code:

#include <stdio.h>
#include <stdlib.h>
#include "mpi.h"
#define n 100

void main(int argc,char** argv) {

int my_id,i,data[n],a,p,F,x,Tx;

MPI_Status status;
MPI_Init(&argc,&argv);
MPI_Comm_rank(MPI_COMM_WORLD,&my_id);
MPI_Comm_size(MPI_COMM_WORLD,&p);

if (my_id==0) {
x=rand()%5;
	
for (i=0;i<p;i++) {
		data[i]=rand()%5;
		MPI_Send(&data[i],1,MPI_INT,I,0,MPI_COMM_WORLD);
		MPI_Send(&x,1,MPI_INT,i,0,MPI_COMM_WORLD);
	}
	
}
	
MPI_Recv(&a,1,MPI_INT,0,0,MPI_COMM_WORLD,&status);
MPI_Recv(&x,1,MPI_INT,0,0,MPI_COMM_WORLD,&status);

if (my_id==0) {
F=a;
x=1;

MPI_Send(&F,1,MPI_INT,1,0,MPI_COMM_WORLD);
MPI_Send(&x,1,MPI_INT,1,0,MPI_COMM_WORLD);

}

if (my_id>0) {
MPI_Recv(&F,1,MPI_INT,my_id-1,0,MPI_COMM_WORLD,&status);
MPI_Recv(&Tx,1,MPI_INT,my_id-1,0,MPI_COMM_WORLD,&status);


x=Tx*x;
F=F+a*x;

MPI_Send(&F,1,MPI_INT,(my_id+1)%p,0,MPI_COMM_WORLD);
MPI_Send(&x,1,MPI_INT,(my_id+1)%p,0,MPI_COMM_WORLD);
}

if (my_id==0) {
MPI_Recv(&F,1,MPI_INT,p-1,0,MPI_COMM_WORLD,&status);
printf("F= %d\n",F);
}

MPI_Finalize();

}

so how can i modified this code so that
i can do the pipeline jacobi iteration and pipeline gauss-seidel iteration

assuming the equation is like

a11x1 + a12x2 + … + a1nxn = b1;
a21x1 + a22x2 + … + a2nxn = b2;
. .
. .
. .
an1x1 + an2x2 + … + annxn = bn


for the jacobi iteration :

suppose that one process is allocated for each unknown ( p=n)
and each process iterate the same number of time.on each iteration the newly computed values of the unknow will need to be broadcast to all other process.
the parallel algorithm should be like this

Code:

x[i] = b [i]    /*initialize unknown
for (iteration =0; iteration<limit; iteration++){ 
    sum = -a[i][i] * x[i];
    for (j = 0; j < n; j++)   /* compute summation */
           sum = sum + a[i][j] * x[j];
    new_x[i] = (b[i] - sum) / a[i][i];   /*compute unknown*/
    broadcast_receive (xnew[i]);   /*broadcast value*/
    global_barrier ();     /* wait for all process */
}

an alternative simple solution is to return to basic send() and recv() , for broadcast_receive(); that is process i might have:

Code:

for (j=0; j<n; j++) if (i !=j) send (&x[i], Pj);
           for (j=0; j<n; j++) if (i !=j) send (&x[j], Pj);

i need to modify this sequential code for gauss-seidel so that in can be done in parallel

Code:

for (i = 0; i < n -1; i++) /*for each row except last*/
                  for (j = i+1; j<n; j++){ /* step through subsequent row*/
                     m = a[j] [i]/a[i][i]; /*compute multiplier*/
                     for (k= i; k<n; k++) /*modify last n-i-1 element of row j */
                            a [j][k] = a[j][k] - a[i][k] * m ;
                     b[j] = b[j] - b[i] *m; /* modify right side */

The master process (rank 0) accepts the size of the system and reads the coefficients a’s
and b’s. Then, it will distribute them to the corresponding slave processes. The master
process should collect the final solution from the slave processes and display


i wish if there is solution for this problem