include/util/parametric_search_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 "prefix_sum_tools.hpp"
#include <iostream>



template <typename T, typename Pr>
int util::ParametricSearch<T,Pr>::probe(T bottleneck, int cutNumber, const Pr& prefixSumArray, int length)
{
  assert (cutNumber >= 0);
  assert (length >= 0);
  //assert (prefixSumArray != NULL);
  assert (prefixSumArray[0] == 0);
  return probeCut(bottleneck,cutNumber,prefixSumArray,length,NULL);
}


template <typename T, typename Pr>
int util::ParametricSearch<T,Pr>::probeCut(T bottleneck, int cutNumber, const Pr& prefixSumArray, int length, int *cuts)
{
  int processor, step = length / (cutNumber + 1), cutPoint;
  T prefixSumBottleneck = bottleneck, totalLoad = prefixSumArray[length - 1];

  assert (cutNumber >= 0);
  assert (length >= 0);
  //  assert (prefixSumArray != NULL);
  assert (prefixSumArray[0] == 0);

  
  for(processor = 0; (processor < cutNumber) && (prefixSumBottleneck < totalLoad); processor++)
    {
      while((step < length)  && (prefixSumArray[step] < prefixSumBottleneck))
        {
          step += (length / (cutNumber + 1));
        }
      if (step >= length)
        step = length-1;
      assert (step < length);
      cutPoint = binarySearch(prefixSumArray, step - (length / (cutNumber + 1)),
                              step, prefixSumBottleneck);
      if (cuts != NULL)
        cuts[processor] = cutPoint;
      if(cutPoint > -1)
        prefixSumBottleneck = bottleneck + prefixSumArray[cutPoint];
      else
        return 0;
    }

  if(prefixSumBottleneck >= totalLoad)
    {
      if((cuts != NULL) && (processor < cutNumber))
        for(;processor < cutNumber;processor++)
          cuts[processor] = length - 1;
      return 1;
    }
  else
    return 0;
}



template <typename T, typename Pr>
int util::ParametricSearch<T,Pr>::rprobe(const Pr& wpre, int length, const T& bottleneck,
                                   int numproc, int *s, const int *sl, const int *sh)
{
  T bsum = bottleneck;
  int p;

  for(p = 0; p < numproc - 1; p++)
    {
      assert(sl[p] <= sh[p]);
      assert(p < numproc);
      s[p] = binarySearch(wpre, sl[p], sh[p], bsum);
      if (p > 0)
        {
          assert (s[p]>=s[p-1]);
          assert (wpre[s[p]] - wpre[s[p-1]] <= bottleneck);
        }
      bsum = wpre[s[p]] + bottleneck;
    }
  if(bsum >= wpre[length - 1])
    return 1;
  else
    return 0;
}



template <typename T, typename Pr>
int util::ParametricSearch<T,Pr>::rprobe_interval(const Pr& wpre, int length, const T& bottleneck,
                                   int numproc, int *s, const int *sl, const int *sh)
{
  int p;
  for(p = 0; p < numproc - 1; p++)
    {
      assert(p==0 || sl[p]>=sl[p-1]);
      assert(p==0 || sh[p]>=sh[p-1]);
      assert(sl[p] <= sh[p]);
      assert(p < numproc);
      s[p] = binarySearch_interval(wpre, sl[p], sh[p], bottleneck, (p==0?0:s[p-1]));      
      assert (p == 0 || s[p]>=s[p-1] );
      assert (p == 0 || (wpre.interval(s[p-1],s[p]) <= bottleneck));
        
    }
  if(wpre.interval(s[p - 1],length-1) <= bottleneck)//if(bsum >= wpre.interval(0,length - 1))
    return 1;
  else
    return 0;
}


template <typename T, typename Pr>
int util::ParametricSearch<T,Pr>::probeCut_interval(T bottleneck, int cutNumber, const Pr& prefixSumArray, int length, int *cuts)
{
  int processor, step = length / (cutNumber + 1), cutPoint;
  int lastCut = 0;
  assert (cutNumber >= 0);
  assert (length >= 0);
  assert (prefixSumArray.interval(0,0) == 0);

  for(processor = 0; (processor < cutNumber) && (step < length); processor++)
    {
      while((step < length)  && (prefixSumArray.interval(lastCut,step) <= bottleneck))
        {
          step += (length / (cutNumber + 1));
        }
      if (step >= length)
        step = length-1;
      assert (step < length);
      cutPoint = binarySearch_interval(prefixSumArray, step - (length / (cutNumber + 1)), step, bottleneck, lastCut);
      if (cuts != NULL)
        cuts[processor] = cutPoint;
      if(cutPoint > -1)
        lastCut = cutPoint;
      else
        return 0;
    }

  if (processor <= cutNumber)
    {
      if (cuts != NULL)
        for(;processor < cutNumber;processor++)
          cuts[processor] = length - 1;
      return 1;
    }
  else
    return 0;
}