ParallelsumDC.c

#include

#include

#include

#include

int main$($int argc, char$*$ argv$[])\{$

MPI$\_$Init$($&argc, &argv$)$;

int rank, size;

MPI$\_$Comm$\_$rank$($MPI$\_$COMM$\_$WORLD, &rank$)$;

MPI$\_$Comm$\_$size$($MPI$\_$COMM$\_$WORLD, &size$)$;

int n $=256$; $//$ total numbers

std::vector data$($n$)$;

if$($rank $==0)\{$

for$($int i $=0$; i $<$ n; i$++)\{$

data$[$i$]=$ i $+1$;

$\}$

$\}$

int logSize $=$ log$2($size$)$;

for$($int i $=$ logSize $-1$; i $>=0$; i$--)\{$

if$(($rank & $($int$($pow$(2,$ i$))-1))==0)\{$

if$(($rank & $($int$($pow$(2,$ i $+1))-1))==0)\{$

printf$("$Processor $\%$d sends sublist to processor $\%$d at level $\%$d

$",$ rank, rank $^$ int$($pow$(2,$ i$)),$ i$)$;

MPI$\_$Send$($&data$[$n$/2],$ n$/2,$ MPI$\_$INT, rank $^$ int$($pow$(2,$ i$)),0,$ MPI$\_$COMM$\_$WORLD$)$;

n $/=2$;

$\}$ else $\{$

printf$("$Processor $\%$d receives sublist from processor $\%$d at level $\%$d

$",$ rank, rank $^$ int$($pow$(2,$ i$)),$ i$)$;

MPI$\_$Recv$($&data$[0],$ n$,$ MPI$\_$INT, rank $^$ int$($pow$(2,$ i$)),0,$ MPI$\_$COMM$\_$WORLD, MPI$\_$STATUS$\_$IGNORE$)$;

$\}$

$\}$

$\}$

int sum $=0$;

for$($int i $=0$; i $<$ n; i$++)\{$

sum $+=$ data$[$i$]$;

$\}$

printf$("$The partial sum on processor $\%$d is $\%$d

$",$ rank, sum$)$;

if$($rank $!=0)\{$

printf$("$Processor $\%$d sends sublist to processor $0$ at level $0$

$",$ rank$)$;

MPI$\_$Send$($&sum, $1,$ MPI$\_$INT, $0,0,$ MPI$\_$COMM$\_$WORLD$)$;

$\}$ else $\{$

int temp;

for$($int i $=1$; i $<$ size; i$++)\{$

MPI$\_$Recv$($&temp, $1,$ MPI$\_$INT, i$,0,$ MPI$\_$COMM$\_$WORLD, MPI$\_$STATUS$\_$IGNORE$)$;

printf$("$Processor $0$ receives sublist from processor $\%$d at level $0$

$",$ i$)$;

sum $+=$ temp;

$\}$

printf$("$The final sum is $\%$d

$",$ sum$)$;

$\}$

MPI$\_$Finalize$()$;

return $0$;

$\}$

Probelm Statement :

Find the Parallel Sum Using Divide and Conquer $.$

$1.$ Assume there are $8$ processing nodes and there are $256$ numbers $(1,2,...,256)$ to be added. The original list is initialized at processor $0,$ and then is divided into two halves to broadcast level by level until the leaves are reached as shown below $($each processor will have $256/8=32$ numbers$).$ After each processor receives its final sublist $(32$ numbers$),$ it calculates its partial sum. The partial sums will be reduced level by level as shown below. The final sum will be obtained and printed out on processor $0.$

Expected

Processor $0$ sends sublist to processor $4$ at level $1$

Processor $0$ sends sublist to processor $2$ at level $2$

Processor $0$ sends sublist to processor $1$ at level $3$

The partial sum on processor $0$ is $528$

Processor $1$ receives sublist from processor $0$ at level $3$

The partial sum on processor $1$ is $1552$

Processor $1$ sends sublist to processor $0$ at level $0$

Processor $2$ receives sublist from processor $0$ at level $2$

Processor $2$ sends sublist to processor $3$ at level $3$

The partial sum on processor $2$ is $2576$

Processor $4$ receives sublist from processor $0$ at level $1$

Processor $4$ sends sublist to processor $6$ at level $2$

Processor $4$ sends sublist to processor $5$ at level $3$

The partial sum on processor $4$ is $4624$

Processor $6$ receives sublist from processor $4$ at level $2$

Processor $6$ sends sublist to processor $7$ at level $3$

The partial sum on processor $6$ is $6672$

Processor $4$ receives sublist from processor $5$ at level $3$

Processor $0$ receives sublist from processor $1$ at level $3$

Processor $5$ receives sublist from processor $4$ at level $3$

The partial sum on processor $5$ is $5648$

Processor $5$ sends sublist to processor $4$ at level $0$

Processor $4$ receives sublist from processor $6$ at level $2$

Processor $4$ sends sublist to processor $0$ at level $2$

Processor $6$ receives sublist from processor $7$ at level $3$

Processor $6$ sends sublist to processor $4$ at level $1$

Processor $7$ receives sublist from processor $6$ at level $3$

The partial sum on processor $7$ is $7696$

Processor $7$ sends sublist to processor $6$ at level $0$

Processor $3$ receives sublist from processor $2$ at level $3$

The partial sum on processor $3$ is $3600$

Processor $3$ sends sublist to processor $2$ at level $0$

Processor $2$ receives sublist from processor $3$ at level $3$

Processor $2$ sends sublist to processor $0$ at level $1$

Processor $0$ receives sublist from processor $2$ at level $2$

Processor $0$ receives sublist from processor $4$ at level $1$

The final sum is $32896$

Correction:

This is my code i have worked on$.$ there are some mistakes in distributing and reducing steps i guess i am unable to figure it out correct the code to solve the below problem. the out put should look the same $.$

Output I got:

The partial sum on processor $1$ is $6176$

Processor $1$ sends sublist to processor $0$ at level $0$

Processor $2$ receives sublist from processor $0$ at level $1$

Processor $2$ sends sublist to processor $3$ at level $0$

The partial sum on processor $2$ is $24640$

Processor $2$ sends sublist to processor $0$ at level $0$

Processor $0$ sends sublist to processor $2$ at level $1$

Processor $0$ sends sublist to processor $1$ at level $0$

The partial sum on processor $0$ is $2080$

Processor $0$ receives sublist from processor $1$ at level $0$

Processor $0$ receives sublist