mg_load_balance Subroutine

public subroutine mg_load_balance(mg)

Load balance all boxes in the multigrid tree. Compared to mg_load_balance_simple, this method does a better job of setting the ranks of parent boxes

Note that in a typical application the load balancing of the leaves is already determined, then mg_load_balance_parents can be used.

Arguments

Type IntentOptional Attributes Name
type(mg_t), intent(inout) :: mg

Calls

proc~~mg_load_balance~2~~CallsGraph proc~mg_load_balance~2 mg_load_balance proc~most_popular~2 most_popular proc~mg_load_balance~2->proc~most_popular~2 proc~update_lvl_info~2 update_lvl_info proc~mg_load_balance~2->proc~update_lvl_info~2

Source Code

  subroutine mg_load_balance(mg)
    type(mg_t), intent(inout) :: mg
    integer                   :: i, id, lvl, single_cpu_lvl
    integer                   :: work_left, my_work(0:mg%n_cpu), i_cpu
    integer                   :: c_ids(mg_num_children)
    integer                   :: c_ranks(mg_num_children)
    integer                   :: coarse_rank

    ! Up to this level, all boxes have to be on a single processor because they
    ! have a different size and the communication routines do not support this
    single_cpu_lvl = max(mg%first_normal_lvl-1, mg%lowest_lvl)

    ! Distribute the boxes equally. Due to the way the mesh is constructed, the
    ! mg%lvls(lvl)%ids array already contains a Morton-like ordering.
    do lvl = mg%highest_lvl, single_cpu_lvl+1, -1
       ! For parents determine the rank based on their child ranks
       my_work(:) = 0

       do i = 1, size(mg%lvls(lvl)%parents)
          id = mg%lvls(lvl)%parents(i)

          c_ids = mg%boxes(id)%children
          c_ranks = mg%boxes(c_ids)%rank
          i_cpu = most_popular(c_ranks, my_work, mg%n_cpu)
          mg%boxes(id)%rank = i_cpu
          my_work(i_cpu) = my_work(i_cpu) + 1
       end do

       work_left = size(mg%lvls(lvl)%leaves)
       i_cpu     = 0

       do i = 1, size(mg%lvls(lvl)%leaves)
          ! Skip this CPU if it already has enough work
          if ((mg%n_cpu - i_cpu - 1) * my_work(i_cpu) >= work_left + &
             sum(my_work(i_cpu+1:))) then
             i_cpu = i_cpu + 1
          end if

          my_work(i_cpu) = my_work(i_cpu) + 1
          work_left = work_left - 1

          id = mg%lvls(lvl)%leaves(i)
          mg%boxes(id)%rank = i_cpu
       end do
    end do

    ! Determine most popular CPU for coarse grids
    if (single_cpu_lvl < mg%highest_lvl) then
       coarse_rank = most_popular(mg%boxes(mg%lvls(single_cpu_lvl+1)%ids)%rank,&
           my_work, mg%n_cpu)
    else
       coarse_rank = 0
    end if

    do lvl = mg%lowest_lvl, single_cpu_lvl
       do i = 1, size(mg%lvls(lvl)%ids)
          id = mg%lvls(lvl)%ids(i)
          mg%boxes(id)%rank = coarse_rank
       end do
    end do

    do lvl = mg%lowest_lvl, mg%highest_lvl
       call update_lvl_info(mg, mg%lvls(lvl))
    end do

  end subroutine mg_load_balance