!SOMMA AD ALBERO
!sia N numero di processi
!sia M la prima potenza di 2 >= N
!allo step I dell'algoritmo (I comincia da 1) i processi per cui (M - rank) è un multiplo di 2 alla I
!sommano i contributi dei processi rank + 2 alla I-1

Program sumtree
  implicit none
  include 'mpif.h'
  
  integer :: ierr,myid, numprocs, i, d, sum, val, proc
  integer :: status (MPI_Status_size) 
  integer :: M=1
  
  
  call MPI_Init(ierr)
  call MPI_Comm_size(MPI_COMM_WORLD,numprocs,ierr)
  call MPI_Comm_rank(MPI_COMM_WORLD,myid,ierr)
  
  ! M: prima potenza di 2 maggiore di numprocs 
  do while (M < numprocs)
     M = M * 2
  end do
  i = M - myid
  d = 1
  sum = myid
  
  do while (mod(i,2) == 0)

     proc = myid + d
     if (proc < numprocs) then
        call MPI_Recv(val, 1, MPI_INTEGER, proc, 0, MPI_COMM_WORLD, status, ierr)
        sum = sum + val
     endif
     
     i = i / 2
     d = d * 2
  end do
  if (myid == 0) then
     print *, 'Sum =', sum
  else
     proc = myid - d
     call MPI_Send(sum, 1, MPI_INTEGER, proc, 0, MPI_COMM_WORLD,ierr)
  end if
  call MPI_Finalize(ierr)  

end program sumtree

