Barrier

int MPI_Barrier(MPI_Comm comm)
{
  MPI_Status status;
  int i, nmasters, myrank, mynum, dim, hibit, mask;

  MPI_Comm_rank(comm, &myrank);

  /* local phase */
  fan in to local master;

  /* global phase */
  if (is_master(myrank, comm)) {
    nmasters = num_masters(comm);
    if (nmasters <= MAXLINEARBARRIER) {
      /* linear barrier among the masters */
      if (myrank == 0) {
        for (i = 1; i < nmasters; i++) {
          MPI_Recv(MPI_BOTTOM, 0, MPI_BYTE, rank_master(i, comm), 
                   IMPI_BARRIER_TAG, comm, &status);
        }

        for (i = 1; i < nmasters; i++) {
          MPI_Send(MPI_BOTTOM, 0, MPI_BYTE, rank_master(i, comm),
                   IMPI_BARRIER_TAG, comm);
        }
      } else {
        MPI_Send(MPI_BOTTOM, 0, MPI_BYTE, 0, IMPI_BARRIER_TAG, comm);
        MPI_Recv(MPI_BOTTOM, 0, MPI_BYTE, 0, 
								 IMPI_BARRIER_TAG, comm, &status);
      }
    } else {
      /* tree barrier among the masters */
      mynum = master_num(myrank, comm);
      dim = cubedim(nmasters);
      hibit = hibit(mynum, dim);
      --dim;

      /* receive from children */
      for (i = dim, mask = 1 << i; i > hibit; --i, mask >>= 1) {
        peer = mynum | mask;
        if (peer < nmasters) {
          MPI_Recv(MPI_BOTTOM, 0, MPI_BYTE, rank_master(peer, comm),
                   IMPI_BARRIER_TAG, comm, &status);
        }
      }

      /* send to and receive from parent */
      if (mynum > 0) {
        peer = rank_master(mynum & ~(1 << hibit), comm);
        MPI_Send(MPI_BOTTOM, 0, MPI_BYTE, peer, IMPI_BARRIER_TAG, comm);

        MPI_Recv(MPI_BOTTOM, 0, MPI_BYTE, peer, 
                 IMPI_BARRIER_TAG, comm, &status);
      }

      /* send to children */
      for (i = hibit + 1, mask = 1 << i; i <= dim; ++i, mask <<= 1) {
        peer = rank | mask;
        if (peer < nmasters) {
          MPI_Send(MPI_BOTTOM, 0, MPI_BYTE, rank_master(peer, comm),
                   IMPI_BARRIER_TAG, comm);
        }
      }
    }
  }

  /* local phase */
  fan out from local master;

  return(MPI_SUCCESS);
}