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

template <typename T, typename Pr>
T oned::DirectCutRefB<T,Pr>::direct_ref_b(int procCount, const Pr& prefixSumArray,
                                         int length, int *cutIndexes, T )
{
  T v = direct_ref_b_internal(procCount, prefixSumArray, length, cutIndexes);
  return v;
}

//Calculates cut points where B=P_iter*(Wtot/P)
//Length is the length of prefix sum array
template <typename T, typename Pr>
T oned::DirectCutRefB<T,Pr>::direct_ref_b_internal(int procCount, const Pr& prefixSumArray,
                                             int length, int *cutIndexes)
{
  using namespace util;
  T avg;
  int inc = length / procCount, p, lastcut = 0;
  int step = inc;
  T bottleneck = 0, val;
  for(p = 0; p < procCount - 1; p++)
    {
      avg = (prefixSumArray[length-1] - prefixSumArray[lastcut])/ (procCount - p);
      val = prefixSumArray[lastcut] + avg;
      inc = (length - lastcut) / (procCount - p);
      if (inc == 0) inc++;
      while(prefixSumArray[step] <= val)
        {
          assert (inc > 0);
          step+=inc;
          if(step > length-1)
            {
              step = length-1;
              break;
            }
        }
      assert (step>=0);
      assert (step<length);
      cutIndexes[p] = binarySearchLeft(prefixSumArray, step - inc, step, val);

      assert((prefixSumArray[cutIndexes[p]] >=val) || (cutIndexes[p]  == length - 1));

      assert(cutIndexes[p] >= step - inc);
      assert(cutIndexes[p] <= step);
      assert(cutIndexes[p] >=0);
      assert(lastcut <= cutIndexes[p]);
      assert(-1 != cutIndexes[p]);

      if(prefixSumArray[cutIndexes[p]] - prefixSumArray[lastcut] > bottleneck)
        bottleneck = prefixSumArray[cutIndexes[p]] - prefixSumArray[lastcut];
      lastcut = cutIndexes[p];
    }
  if(prefixSumArray[length - 1] - prefixSumArray[lastcut] > bottleneck)
    return prefixSumArray[length - 1] - prefixSumArray[lastcut];
  else
    return bottleneck;
}