include/oned/rec_bisect_minmax_impl.hpp

Go to the documentation of this file.

// This file is part of SPart, Spatially Located Workload Partitioner.

// Copyright (C) 2011, The Ohio State University
// SPart developed by Erdeniz O. Bas, Erik Saule and Umit V. Catalyurek 

// For questions, comments, suggestions, bugs please send e-mail to: 
// Umit V. Catalyurek   catalyurek.1@osu.edu

// SPart is free software; you can redistribute it and/or modify it under
// the terms of the GNU General Public License as published by the Free
// Software Foundation; either version 2 or (at your option) any later
// version.

// SPart is distributed in the hope that it will be useful, but WITHOUT
// ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
// FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
// for more details.

// You should have received a copy of the GNU General Public License
// along with SPart; if not, write to the Free Software Foundation, Inc.,
// 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

// As a special exception, if other files instantiate templates or use
// macros or inline functions from this file, or you compile this file
// and link it with other works to produce a work based on this file,
// this file does not by itself cause the resulting work to be covered by
// the GNU General Public License. However the source code for this file
// must still be made available in accordance with section (3) of the GNU
// General Public License.

// This exception does not invalidate any other reasons why a work based
// on this file might be covered by the GNU General Public License.

// The full text of the GPL license version 2 is available in "gpl.txt".

#include <oned/rec_bisect_minmax.hpp>


template<typename T, typename Pr>
double oned::RecursiveBisectionMinMax<T, Pr>::pointDiff(const Pr prefixSum, int low, int high, int leftProc, int rightProc, int point)
{
  double y1 = RecursiveBisectionMinMax<T,Pr>::calculateDiff (prefixSum, low, high, leftProc, rightProc, point - 1);
  double y2 = RecursiveBisectionMinMax<T,Pr>::calculateDiff (prefixSum, low, high, leftProc, rightProc, point);
  return y2-y1;
}


//-1 means we are in decreasing side
//+1 means we are in increasing side
template<typename T, typename Pr>
int oned::RecursiveBisectionMinMax<T, Pr>::slopeAt(const Pr prefixSum, int low, int high, int leftProc, int rightProc, int point)
{
  if(prefixSum[point - 1] == 0)
    return -1;
  double diff = pointDiff(prefixSum, low, high, leftProc, rightProc, point);
  if(diff <0)
    return -1;
  else if(diff>0)
    return 1;
  else
    {
      //if slope is zero at that point
      while((low<point) && (prefixSum[point] == prefixSum[point-1]))
        {
          point--;
        }
      if(diff <= 0)
        return -1;
      else
        return 1;
      
    }
}

template<typename T, typename Pr>
int oned::RecursiveBisectionMinMax<T, Pr>::bimonsearch(const Pr prefixSum, int low, int high, int leftProc, int rightProc)
{
  assert(low<high);
  int lowlimit=low;
  int highlimit=high;
  int mid;
  while(lowlimit<highlimit)
    {
      mid = (lowlimit+highlimit)/2;
      if(slopeAt(prefixSum, low, high,  leftProc, rightProc,  mid) == -1)
        {
          lowlimit = mid+1;
        }
      else
        highlimit = mid;
      
    }
  return lowlimit;
}

template<typename T, typename Pr>
double oned::RecursiveBisectionMinMax<T, Pr>::calculateDiff(const Pr prefixSum, int low, int high,
                                           int leftProc, int rightProc, int candidate)
{
  assert(low>=0);
  assert(candidate>=0);
  double a = (prefixSum[candidate] - prefixSum[low - 1]) / ((double)leftProc);
  double b = (prefixSum[high] - prefixSum[candidate])/ ((double)rightProc);

  return (a>b?a:b);
}
template<typename T, typename Pr>
int oned::RecursiveBisectionMinMax<T, Pr>::linsrch(const Pr prefixSum, int low, int high, int leftProc, int rightProc)
{
  double cutWeight;
  int cutPoint;
  //Guess a cut point
  cutWeight = ((prefixSum[high] - prefixSum[low - 1]) * (double)leftProc / ((double)leftProc + (double)rightProc));
  cutPoint = binarySearch(prefixSum, low, high, cutWeight+prefixSum[low-1]);

  //If minmax is active search for minimum cut point
  //Refresh cut weight with actual weight
  if(cutPoint == -1)
    cutWeight = (double)prefixSum[high];
  else
    cutWeight = calculateDiff (prefixSum, low, high, leftProc, rightProc, cutPoint);

  int tmpCutPoint;
  double tmpWeight;
  for(tmpCutPoint = low; tmpCutPoint < high; tmpCutPoint++)
    {
      tmpWeight = calculateDiff (prefixSum, low, high, leftProc, rightProc, tmpCutPoint);
      if(tmpWeight < cutWeight)
        {
          cutWeight = tmpWeight;
          cutPoint = tmpCutPoint;
        }
    }
  return cutPoint;
}
template<typename T, typename Pr>
int oned::RecursiveBisectionMinMax<T, Pr>::findEvenCut(const Pr prefixSum, int low, int high, int leftProc, int rightProc)
{
  assert (low<=high);
  assert(leftProc != 0);
  assert(rightProc != 0);
  //bianary search cut point
  int cutPoint = bimonsearch( prefixSum, low, high,  leftProc, rightProc)-1;

  assert(cutPoint < high);
  assert(cutPoint >= low);

  return cutPoint;
}


//partition [low:high]
template<typename T, typename Pr>
T oned::RecursiveBisectionMinMax<T, Pr>::rec_bisection_internal(int numProc, int low, int high, const Pr prefixSum, int *cutPoints)
{

  int leftProc, rightProc, cutPointHere, candidate;
  T  candidatediff;
  
  if(low > high)
    {
      int p;
      for (p = 0;p<numProc - 1;p++)
        {
          cutPoints[p] = high;
        }
      return 0;
    }

  //the prefixsum array is supposed to be non-decreasing
  assert (prefixSum[high-1]<=prefixSum[high]);
  assert (prefixSum[low]<=prefixSum[high]);
  assert (numProc>0);

  if (numProc == 1)      
    return prefixSum[high] - prefixSum[low-1];

  if (high-low+1 <= numProc)
    {
      int p;
      T m=prefixSum[low] - prefixSum[low - 1];

      //allocates the first high-low processor to a different index
      for (p = 0;p < high-low; p++)
        {
          cutPoints[p] = low+p;
          m = std::max(m, prefixSum[low+p] - prefixSum[low+p-1]);
        }
      //the remaining processors are empty
      for (;p<numProc - 1;p++)
        {
          cutPoints[p] = high;
        }

      
      return m;
    }

  if(numProc > 1)
    {
      leftProc = 1;
      rightProc = numProc - leftProc;
      
      
      int tmpcandidate = findEvenCut(prefixSum, low, high, leftProc, rightProc);
      T tmpcandidatediff = calculateDiff(prefixSum, low, high, leftProc, rightProc, tmpcandidate);      
      candidate = tmpcandidate;
      candidatediff = tmpcandidatediff;
      //Try different processor numbers
      for(int tmpleft = leftProc + 1;tmpleft < numProc; tmpleft++)
        {
          int tmpright = numProc - tmpleft;
          //Try to assign as #rightproc+#leftproc and #leftproc+#rightproc combinations
          tmpcandidate = findEvenCut(prefixSum, low, high, tmpleft, tmpright);
          tmpcandidatediff = calculateDiff(prefixSum, low, high, tmpleft, tmpright, candidate);
          //if found a less weight, save its info
          if(candidatediff > tmpcandidatediff)
            {
              candidatediff = tmpcandidatediff;
              candidate = tmpcandidate;
              leftProc = tmpleft;
              
            }
        }
      //refresh right proc
      rightProc = numProc - leftProc;

      assert (candidate<=high);
      assert (candidate>=low);

      cutPointHere = candidate;


      if(cutPointHere == -1)
        cutPointHere = low;
      assert(cutPointHere > -1);

      assert (cutPointHere<=high);
      assert (cutPointHere>=low);

      *(cutPoints+leftProc-1) = cutPointHere;
      assert(cutPointHere >= low);
      assert(leftProc + rightProc == numProc);
      T a = rec_bisection_internal(leftProc, low, cutPointHere, prefixSum, cutPoints);
      T b = rec_bisection_internal(rightProc, cutPointHere+1, high, prefixSum, cutPoints+leftProc);
      return std::max(a,b);
    }
  assert (0);
  return -1;
}

template <typename T, typename Pr>
T oned::RecursiveBisectionMinMax<T, Pr>::rec_bisection(int procCount, const Pr prefixSumArray,
                                       int length, int *cutIndexes, T )
{
  return rec_bisection_internal(procCount, 1, length - 1, prefixSumArray, cutIndexes);
}