tem_find_depProc_globSearch Subroutine

public subroutine tem_find_depProc_globSearch(depProc, nDepProcs, elemPath, p_lb, p_ub, PathFirst, PathLast)

Find the remote partitions holding data on a given path

Using a binary search over the processes first and last elements.

Is the element in question a local or remote element? To look up a certain element by its treeID in the distributed list of elements, it is sufficient to know the splitting positions of all chunks. That is, the first and last treeID of each partition. With a binary search over the splitting positions any requested element can then be identified to be either outside the computational domain at all, or inside of one or several known partitions.

Arguments

Type IntentOptional Attributes Name
integer, intent(out) :: depProc

List of partitions
integer, intent(out) :: nDepProcs

Number of partitions
type(tem_path_type), intent(in) :: elemPath

Element to look up
integer, intent(in) :: p_lb

Left interval bound to search in
integer, intent(in) :: p_ub

Right interval bound to search in
type(tem_path_type), intent(in) :: PathFirst(:)

Left partition bounds
type(tem_path_type), intent(in) :: PathLast(:)

Right partition bounds

Calls

proc~~tem_find_depproc_globsearch~~CallsGraph proc~tem_find_depproc_globsearch tem_find_depProc_globSearch proc~tem_pathcomparison tem_PathComparison proc~tem_find_depproc_globsearch->proc~tem_pathcomparison

Called by

proc~~tem_find_depproc_globsearch~~CalledByGraph proc~tem_find_depproc_globsearch tem_find_depProc_globSearch proc~tem_find_depproc tem_find_depProc proc~tem_find_depproc->proc~tem_find_depproc_globsearch proc~identify_elements identify_elements proc~identify_elements->proc~tem_find_depproc proc~identify_elements->proc~identify_elements proc~create_allparentneighbors create_allParentNeighbors proc~identify_elements->proc~create_allparentneighbors proc~identify_stencilneigh identify_stencilNeigh proc~identify_elements->proc~identify_stencilneigh proc~build_levelelements build_levelElements proc~build_levelelements->proc~identify_elements proc~identify_additionalneigh identify_additionalNeigh proc~build_levelelements->proc~identify_additionalneigh proc~create_allparentneighbors->proc~identify_elements proc~create_allparentneighbors->proc~identify_stencilneigh proc~identify_additionalneigh->proc~identify_elements proc~identify_stencilneigh->proc~identify_elements proc~request_remotehalos request_remoteHalos proc~request_remotehalos->proc~create_allparentneighbors proc~request_remotehalos->proc~identify_stencilneigh proc~tem_find_allelements tem_find_allElements proc~tem_find_allelements->proc~build_levelelements proc~tem_find_allelements->proc~identify_additionalneigh

Source Code

  subroutine tem_find_depProc_globSearch( depProc, nDepProcs, elemPath, p_lb, &
    &                                     p_ub, PathFirst, PathLast)
    ! -------------------------------------------------------------------- !
    !> List of partitions
    integer, intent(out) :: depProc
    !> Number of partitions
    integer, intent(out) :: nDepProcs
    !> Element to look up
    type(tem_path_type), intent(in) :: elemPath
    !> Left partition bounds
    type(tem_path_type), intent(in) :: PathFirst(:)
    !> Right partition bounds
    type(tem_path_type), intent(in) :: PathLast(:)
    !> Left interval bound to search in
    integer, intent(in) :: p_lb
    !> Right interval bound to search in
    integer, intent(in) :: p_ub
    ! -------------------------------------------------------------------- !
    integer :: lb, ub
    integer :: foundProc, lastProc
    integer :: curProc
    integer :: pComp
    ! -------------------------------------------------------------------- !

    lb = p_lb
    ub = p_ub

    ! Find the partition, to which elemPath is definitely right of
    ! the first element.
    do
      curProc = (lb + ub) / 2
      if( curProc <= 0 ) then
        ! Element not found on any proc
        foundProc = 0
        exit
      end if
      pComp = tem_PathComparison(elemPath, PathFirst(curProc))
      if (pComp > 0) then
        ! The first element of curProc is smaller than elemPath, therefore
        ! we do not have to search left of curProc. Can we even go to curProc+1?
        if (tem_PathComparison(elemPath, PathLast(curProc)) > 0) then
          ! The search element is not in the partition curProc at all, continue
          ! search with new lower bound of curProc+1.
          lb = min(curProc + 1, p_ub)
        else
          ! The left element is smaller than the search element and the right
          ! one is larger or equal to it, thus we found the first partition,
          ! which contains information on the element.
          foundProc = curProc
          exit
        end if
      else
        ! The first element of curProc is larger or equal to elemPath, thus
        ! we can restrict our search interval up to this partition.
        ub = curProc
        ! It is OK to not decrease the interval further here, as we always
        ! round down to find the middle, thus, if by this step we set
        ! ub = lb+1, the next iteration will test a new element, as we get
        ! curProc = (lb + lb + 1) / 2 = lb.
      end if
      if (ub <= lb) then
        ! Interval of size 0, found the first process to hold information on
        ! the element in neighpath.
        ! The lower bound was tested strictly, thus it is safe to set the first
        ! process to the lower bound here and exit.
        foundProc = lb
        pComp = tem_PathComparison(elemPath, PathFirst(foundProc))
        ! element is below lower bound of process 1.
        ! Therefor no process is holding the element
        if ( lb == 1 .and. pComp < 0 ) foundProc = 0
        ! element is below lower bound of process and the element is bigger
        ! than upper bound of previous process. -> element doesn't exist
        if ( ub == lb .and. pComp < 0 ) foundProc = 0
        exit
      end if
    end do

    ! Now linearly search for the last process spanned by the searched element.
    ! Usually this is just the single partition identified above or more
    lastProc = foundProc
    if (lastProc > 0) then
      if (lastProc < p_ub) then
        ! Found process that is not the last one, check whether we span
        ! more than this one (it might just be the first partition with that
        ! element).
        nDepProcs = 1
        depProc = lastProc
        do
          if (lastProc == p_ub) exit
          if (tem_PathComparison(elemPath, PathLast(lastProc)) < 0) exit
          if (tem_PathComparison(elemPath, PathFirst(lastProc+1)) < 0) exit
          lastProc = lastProc + 1
          nDepProcs = nDepProcs + 1
        end do
      else
        ! Last process, there can not be any more processes that would contain
        ! this element. Check whether this element actually is found in this
        ! last process.
        if (tem_PathComparison(elemPath, PathLast(lastProc)) <= 0) then
          ! Element is found on this process, return it accordingly.
          nDepProcs = 1
          depProc = lastProc
        else
          ! Element not found on last process, nowhere in all processes to be
          ! found, return accordingly 0 processes.
          nDepProcs = 0
          depProc = 0
        end if
      end if
    else
      ! Element is left of first process in given list, so no process contains
      ! it ...
      nDepProcs = 0
      depProc = 0
    end if

  end subroutine tem_find_depProc_globSearch