include/oned/rec_bisect_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.hpp>

template<typename T, typename Pr>
double oned::RecursiveBisection<T, Pr>::calculateDiff(const Pr& prefixSum, int low, int high,
                                           int leftProc, int rightProc, int candidate)
{
  assert(low>0);
  assert(candidate>=0);

  //  std::cout<<"high is "<<high<<std::endl;
  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::RecursiveBisection<T, Pr>::findEvenCut(const Pr& prefixSum, int low, int high, int leftProc, int rightProc)
{
  using namespace util;
  assert (low<=high);
  assert(leftProc != 0);
  assert(rightProc != 0);
  assert (low>0);
  if (debugFEC)
    {
      std::cerr << "##findEvenCut(" << low << " " << high << " " << leftProc << " " << rightProc << ")" << std::endl;
    }


  T cutWeight = (T) ((prefixSum[high] - prefixSum[low - 1]) * (double)leftProc / ((double)leftProc + (double)rightProc));
  int cutPoint = binarySearch(prefixSum, low, high, cutWeight+prefixSum[low-1]);
  
  if (debugFEC)
    {
      std::cerr << cutWeight << " " << cutPoint << std::endl;
    }


  if (cutPoint == -1)
    return low;
  double d1 = calculateDiff (prefixSum, low, high, leftProc, rightProc, cutPoint);
  double d2 = calculateDiff (prefixSum, low, high, leftProc, rightProc, cutPoint+1);  

  assert (cutPoint >= low);
  assert (cutPoint <= high);
  return d1 < d2 ? cutPoint  : cutPoint+1;
}


//partition [low:high]
template<typename T, typename Pr>
T oned::RecursiveBisection<T, Pr>::rec_bisection_internal(int numProc, int low, int high, const Pr& prefixSum, int *cutPoints)
{
  using namespace util;
  int leftProc, rightProc, cutPointHere, candidate1, candidate2;
  T  candidate1diff, candidate2diff;

  if (debugRB)
    {
      std::cerr << "**rec_bisection_internal(" << numProc << " " <<low << " " <<high << " " << cutPoints << ")" << std::endl;
    }
  
  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)
    {
      if (debugRB)
        {
          std::cerr << "numProc==1, load = " <<  prefixSum[high] - prefixSum[low - 1]  << ",  prefixSum[high] = " << prefixSum[high] << ", prefixSum[low-1] = " << prefixSum[low-1] << ", high = " << high << ", low = " <<low << std::endl;
        }
      
      return prefixSum[high] - prefixSum[low-1];
    }


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

      if (debugRB)
        {
          fprintf (stderr, "high-low+1 <= numProc; m = %lf\n",m);
        }


      //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;
        }

      if (debugRB)
        {
          fprintf (stderr,
                   "load = %lf\n", m);
        }

      
      return m;
    }

  if(numProc > 1)
    {
      leftProc = (numProc >> 1);
      rightProc = numProc - leftProc;


      //Try to assign as #rightproc+#leftproc and #leftproc+#rightproc combinations
      assert(leftProc != 0);
      assert(rightProc != 0);
      candidate1 = findEvenCut(prefixSum, low, high, leftProc, rightProc);
      candidate2 = findEvenCut(prefixSum, low, high, rightProc, leftProc);

      assert (candidate1<=high);
      assert (candidate1>=low);
      assert (candidate2<=high);
      assert (candidate2>=low);
      //Find the difference between patitions
      candidate1diff = calculateDiff(prefixSum, low, high, leftProc, rightProc, candidate1);
      if (leftProc != rightProc)
        candidate2diff = calculateDiff(prefixSum, low, high, rightProc, leftProc, candidate2);
      else
        candidate2diff = candidate1diff*2;

      if (debugRB)
        {
          fprintf (stderr,
                   "left/right = %d/%lf, right/left = %d/%lf\n",
                  candidate1, candidate1diff,
                  candidate2, candidate2diff);
        }

      //Get the combination with minimum difference
      if (candidate1diff < candidate2diff)
        {
          cutPointHere = candidate1;
        }
      else
        {
          //If a #rightproc+#leftproc assignment is desired, switch numbers too
          cutPointHere = candidate2;
          int tmp = rightProc;
          rightProc = leftProc;
          leftProc = tmp;
        }
      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::RecursiveBisection<T, Pr>::rec_bisection(int procCount, const Pr& prefixSumArray,
                                       int length, int *cutIndexes, T )
{
  return rec_bisection_internal(procCount, 1, length - 1, prefixSumArray, cutIndexes);
}